The iterated binary logarithm
DefinitionShortBroadcastDom_Supplement_logStardistributed-algorithmsgraph-theoryiterated-logarithmp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a natural number , the iterated binary logarithm is the least such that applying the integer binary logarithm exactly times sends to a value at most one:
Thus , , and . This is the slowly growing function in the deterministic round bound of Theorem D.
Formalization Note One iteration is Mathlib's Nat.log 2. Repeated integer binary logarithms strictly decrease above one, so the defining set is always nonempty.
Definition code
import Mathlib
namespace ShortBroadcastDom.Supplement
/-- **The iterated binary logarithm `log* n`** used in the round bound of Theorem D: the least
number of applications of the integer binary logarithm that sends `n` to a value at most one.
Amiri, Siebertz, Wawrzyniak, *Paying for Fractional Error* (arXiv:2611.02057, sha256 prefix
f4dc98d2), Theorem D, §1.3, p.4 (PDF 7), and §8, pp.49–50 (PDF 52–53): the deterministic scheme
uses `O(log* n)` rounds.
**Formalization Note** One iteration is Mathlib's `Nat.log 2`, i.e. `⌊log₂ n⌋`; thus
`logStar 0 = logStar 1 = 0`, `logStar 2 = logStar 3 = 1`, and `logStar 4 = 2`. The defining set
is nonempty for every natural number because repeated integer binary logarithms strictly decrease
above one. This is deliberately not the published `PredAdvice.logStar`, which iterates the real
binary logarithm and already differs at `n = 3`. -/
noncomputable def logStar (n : ℕ) : ℕ :=
sInf {k : ℕ | (Nat.log 2)^[k] n ≤ 1}
end ShortBroadcastDom.Supplement
Source
Amiri, Siebertz, Wawrzyniak, Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts (arXiv:2611.02057, sha256 f4dc98d2cf73d74a105e5b0e61c4b72d15ae82b3f202490e2e4ecf864b40646a), §1.3, p.4 (PDF p.7), Theorem D; proof §8, pp.49–50 (PDF pp.52–53)