Log*-depth iterated/recursive lower-bound constructions (self-similar amplification budgeted by the inverse tower function)

Statement

**The function $\log^*$.** For $n\ge1$, $\log^*n$ ("iterated logarithm" / "log-star") is the number of times $\log_2$ must be applied, starting at $n$, before the result is $\le1$: $$\log^* n = \min\{t\in\mathbb N : \underbrace{\log_2\log_2\cdots\log_2}_{t}(n)\le 1\}.$$ Equivalently, $\log^*$ is the functional inverse of the tower function $T(0)=1,\ T(i)=2^{T(i-1)}$: $\log^*n=\min\{t:T(t)\ge n\}$. $\log^*n$ grows to infinity but does so slower than any fixed number of iterated logarithms — $\log^*(2^{65536})=5$, and $\log^*n\le5$ for every $n$ up to a tower of height 5 (roughly $2^{2^{65536}}$).

The technique (general schema). A *log\*-depth iterated construction* is a lower-bound proof that builds a combinatorial object of target size/parameter $N=N(k)$ by recursively amplifying a small base construction: 1. A base gadget achievable at a bounded scale (density-$\varepsilon$ hitting set, small coloring, etc.). 2. A self-similar amplification step: given one or two good constructions at parameter scale $s$, it produces a new good construction at a much larger scale (exponentially, or a multiplicative-then-exponential jump) — *while consuming, at a fixed rate, a "quality" resource* (a density/discrepancy parameter, a slack probability, an extra color) that only degrades by a bounded (often doubly-exponential-in-$k$) factor each round. 3. Because the resource starts with only $O(1)$ or slowly-growing slack, and each round eats a *multiplicative* (in the log of the resource) bite out of it, the number of rounds $t$ that can be run before the resource is exhausted satisfies exactly the tower/log-star inverse relationship: **$t=\Theta(\log^*(\text{target scale}))$.** 4. Running $\Theta(\log^*k)$ rounds, each contributing a bounded (exponential-type) multiplicative gain to the achieved scale, compounds to a super-exponential-in-$k$ final scale — e.g. $2^{k\cdot\log^*k/4}$ — which beats $2^{ck}$ for *every* fixed constant $c$ (since $\log^*k\to\infty$), even though no single round individually beats any fixed exponential.

Canonical instance (Fox–Hunter 2026). $w(k;3)>2^{k(\log^*k)/4}$ for $k$ sufficiently large: a 3-coloring of $\{1,\dots,2^{k(\log^*k)/4}\}$ with no monochromatic $k$-term arithmetic progression, built by iterating a random-shifted-product amplification step $\Theta(\log^*k)$ times (arxiv.org/abs/2606.02541, Theorem 1; see Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$ for the full worked proof already in this wiki).

Facts

- Origin of the named instance. Jacob Fox, Zach Hunter, "Three-color van der Waerden numbers grow super-exponentially," arXiv:2606.02541 (1 June 2026) — the first proof, at any fixed color count $r\ge2$, that a multicolor van der Waerden number $w(k;r)$ grows faster than exponentially in $k$; the prior best (Hunter, arXiv:2301.06212, *Israel J. Math.* 2025) gave only $w(k;r)\ge(3^{r/3})^{(1-o(1))k}$ for $r\ge6$, a *plain exponential* bound with no iterated/log*-depth recursion. - Exact quantitative machinery (all three lemmas chained in one recursion). (i) Lemma 2.8: a sparse density-$\le\varepsilon$ "hitting set" $S\subseteq\mathbb Z_N$ that still meets a $\delta$-fraction of *every* $k$-AP, with $\delta=2^{-800m/\varepsilon}$ — a Behrend/Sidon-flavored gadget, small enough to be "spent" as one color, but robust along every long AP. (ii) Corollary 3.3: an LLL argument converting the hitting-set gadget into a genuine local no-domination $r$-coloring (no color fills more than a $(1-\delta)$-fraction of any $k$-AP). (iii) Lemmas 4.2–4.3: the amplification engine — given colorings of two smaller groups $H_1,H_2$, a randomly-shifted "fiber recoloring" of the product group $G=H_1\times H_2$ produces a coloring of the much larger $G$ that is still valid, at the cost of a controlled (doubly-exponential-in-$k$) loss in the density/discrepancy parameters. (Definitions and exact validity thresholds per this page's provenance, extracted from arxiv.org/html/2606.02541v1.) - **The recursion runs for $\Theta(\log^*k)$ rounds by construction, not by coincidence.** Each round composes prime factors from a shrinking window (roughly $[2^{0.9k},2^{0.9k+1}]$ in Fox–Hunter's construction) and multiplies the achieved interval length while the density parameter takes something like a repeated exponentiation-down; the number of times this composition can be iterated before the density parameter would go non-positive is exactly the "how many times can you take $\log$ of a doubly-exponentially-shrinking budget before it's used up" count — i.e. $\log^*$ of the target scale, by definition of $\log^*$. - The "resource" consumed per round is a discrete quantity the problem must supply. In Fox–Hunter's construction, the recursion needs three colors: two colors carry the actual anti-monochromatic-domination guarantee, and the third is spending room the random-shift amplification step needs to operate. This is *exactly* why the technique currently resolves $w(k;3)$ (and multicolor $w(k;r)$, $r\ge3$) super-exponentially but has not been ported to the fixed-$r=2$ case — Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?'s open \$500 question — which has no spare color to sacrifice as recursion fuel (per this wiki's problems/138.md and problems/three-color-vdw-super-exponential.md, both independently verified against erdosproblems.com and the arXiv source). - **Structurally analogous (but mechanically different) exemplar outside Ramsey/additive combinatorics: Linial's $\Omega(\log^*n)$ distributed-coloring lower bound.** N. Linial, "Locality in distributed graph algorithms," *SIAM J. Comput.* 21(1) (1992), 193–201, proves any deterministic LOCAL-model algorithm 3-coloring the $n$-cycle requires $\ge\log^*(n)/2-1$ communication rounds, matching Cole–Vishkin's $O(\log^*n)$-round *upper*-bound algorithm (WebSearch-corroborated via arxiv.org/pdf/1402.2552, "Linial's Lower Bound Made Easy," and the original PDF's abstract at cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf — not independently full-text-verified by this page). This is the standard theoretical-CS citation for "$\log^*$ is the exact right answer" to a round-complexity question, and shares the same abstract shape (an exponential-size neighborhood/state space that can only be shrunk by a bounded factor per round, so it takes $\Theta(\log^*n)$ rounds to shrink an $n$-size problem to $O(1)$) even though its internal combinatorial engine (Ramsey-type neighborhood-graph reduction) differs from Fox–Hunter's Behrend/LLL/fiber-product machinery. Flagged explicitly as an *analogy*, not a shared proof, per provenance above. - Contrast with tower-per-step ("stepping-up") recursion. The Erdős–Hajnal stepping-up lemma (used e.g. for the hypergraph-Ramsey tower-growth conjecture Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey)) also iterates a construction, but each single step adds a full extra exponential tower level to the achieved bound, and the number of steps is a *free parameter* $k$ chosen by the prover (uniformity), not a budget forced to $\Theta(\log^*(\text{target}))$ by resource exhaustion. Log*-depth constructions are the much weaker but more delicately budgeted cousin: they buy "beats every fixed exponential" (one log* factor in the exponent), not "one full extra tower level," and the number of rounds is *dictated* by how fast a consumable quality parameter degrades, not chosen freely. Do not confuse the two when deciding which technique a given open problem needs (see Technique, below). - Second Fox–Hunter result reuses the same LLL/hitting-set core but swaps the amplification axis. Theorem 3 ($H(k)\ge k^{(1-o(1))k\log k}$, resolving the Erdős–Graham canonical-van-der-Waerden question, Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED)) lets the number of colors grow with $k$ instead of iterating a fixed-color-count amplification step — a structurally different escalation of the same base gadget, not a log*-depth recursion (per solved/three-color-vdw-super-exponential.md).

Technique

WHEN it applies. 1. You want a lower bound of the shape "beats every fixed exponential $2^{ck}$" (or the polynomial/exponential analogue in your setting) but do not need a full extra tower level of growth — i.e. the target is super-exponential-but-sub-tower, the exact regime $\log^*$-type gains land in. 2. You have (or can build) a base gadget at bounded/small scale with a quantifiable "quality" parameter (density, discrepancy, anti-domination slack, local-independence probability). 3. You have, or can construct, a genuinely self-similar amplification lemma: taking one or two good constructions at scale $s$ and combining them (product group + random shift, tensor/fiber construction, recursive doubling) into a good construction at scale $\gg s$ (exponentially larger), at a *quantifiable, bounded* cost to the quality parameter each round. 4. There is a discrete consumable resource the amplification step needs (an extra color, an extra dimension, extra randomness slack) that the ambient problem actually supplies — if the problem is resource-starved (e.g. a fixed 2-color diagonal Ramsey/van-der-Waerden question), the technique likely needs a genuinely new substitute before it transfers, rather than a direct port.

WHY it works (the mechanism). The core is a pure functional-inverse fact about towers and logs: if each round of amplification (a) multiplies the achieved scale by roughly an exponential factor and (b) divides the remaining "quality budget" by roughly an exponential (or doubly-exponential) factor, then the number of rounds $t$ performable before the budget is exhausted and the scale reached after $t$ rounds are governed by *inverse* functions of each other — one measured in iterated exponentials (the tower function), the other in iterated logarithms ($\log^*$). Running the recursion "until the budget runs out" therefore automatically produces $t=\Theta(\log^*(\text{target scale}))$ rounds, and — because each round's *individual* multiplicative gain is only exponential, never tower-type — the compounded gain across $\Theta(\log^*k)$ such rounds is exactly "beats every fixed exponential in $k$, but does not reach tower-type growth." This is why the technique is the precise tool for super-exponential-but-not-tower lower bounds, and no stronger.

HOW to use it to prove new things (recombination steps)

1. Identify the target growth shape you need. If the open bound you want is "grows faster than $2^{ck}$ for every constant $c$" (super-exponential) but you have no reason to expect (or need) tower-type growth, this technique's output shape ($2^{\Theta(k\log^*k)}$ or similar) is the right target to aim for — check this against what is already known/conjectured for your problem before investing in the construction. 2. Find or build a small, bounded-scale base gadget with a quantifiable quality parameter. In additive-combinatorics/Ramsey settings this is typically a Behrend-type or Sidon-type sparse "hitting set" plus a Lovász-Local-Lemma step converting it into a genuine local coloring/anti-domination guarantee (Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent); in other settings (distributed computing, circuit lower bounds) the analogous gadget is whatever bounded local structure your setting's amplification step consumes. 3. Find or construct the self-similar amplification lemma. This is the load-bearing, problem-specific step: it must take one or two good constructions and produce a new one on a *product*, *tensor*, or *fibered* structure that is exponentially larger, while degrading the quality parameter by only a *bounded, explicitly computable* factor per round (Fox–Hunter's random-shifted fiber-product recoloring is the worked exemplar). If no such lemma exists for your setting, this technique does not apply — you need a different escalation (stepping-up lemma for tower-type growth, or a plain alteration/LLL argument for a single-round exponential bound). 4. Set up the potential/budget recursion explicitly and solve for the round count. Track how the quality parameter (density, discrepancy, etc.) evolves as a function of round number; the number of rounds performable before it would become vacuous/negative is, by the log*/tower inverse relationship, $\Theta(\log^*(\text{target scale}))$ — this is usually the single calculation that turns "an amplification lemma exists" into "a concrete super-exponential numeric bound." 5. Identify explicitly what discrete resource the amplification step consumes per round, and check whether your target problem actually supplies it (an extra color beyond the "real" ones being used, extra dimensions, extra randomness). If the problem is fixed at the minimal resource level (e.g., $r=2$ colors with no spare), the direct port will likely fail; the standard next research move is to search for a "residue" of the technique that survives without the spent resource — exactly the open attack-surface flagged on Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?. 6. Sanity-check against the stepping-up-lemma alternative if the target bound looks like it might actually need tower-type (not just super-exponential) growth — using this weaker technique where stepping-up is really needed will provably fall short by a full exponential level, and vice versa a stepping-up-style argument is overkill (and typically unavailable, since it needs an increase in uniformity/dimension that many settings do not offer) for a merely-super-exponential target.

WHEN it does NOT apply / limitations. - It cannot, by construction, reach tower-type or double-exponential-in-$k$ growth — the entire mechanism tops out at "beats every fixed exponential via a $\log^*k$ multiplier in the exponent," strictly weaker than a genuine extra tower level. For problems that need tower growth (e.g. Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey)'s hypergraph-Ramsey tower conjecture), reach for the stepping-up lemma instead. - It requires an actual self-similar amplification lemma with a quantifiable, boundedly-degrading quality parameter — this is not automatic; if no such structure-preserving product/fiber construction is available for the problem at hand, there is nothing to iterate. - It requires a spendable discrete resource (colors, dimensions) that many "tightest" diagonal/fixed-parameter problems do not have spare — this is the exact reason the technique currently resolves the $r\ge3$-color van-der-Waerden and canonical-Ramsey problems but not the fixed-$r=2$ \$500 question Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers?. - As of this writing (2026-07) the technique has essentially one fully-worked exemplar (Fox–Hunter, a ~1-month-old, not-yet-peer-reviewed preprint) plus one *structurally analogous but mechanically distinct* older exemplar (Linial's distributed-coloring lower bound) — it is not yet a broadly battle-tested toolbox item the way the alteration method or the Lovász Local Lemma are; treat "port this to problem X" attempts as genuinely exploratory.

Related

- Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — the open \$500 two-color van der Waerden question $W(k)^{1/k}\to\infty$; this technique resolves the $r\ge3$-color analogue but is explicitly blocked at $r=2$ by lack of a spare "recursion fuel" color — the sharpest illustration of this technique's resource-consumption limitation. - Fox–Hunter (2026) — three-color van der Waerden numbers $w(k;3)$ grow super-exponentially in $k$ — the fully worked proof this concept page abstracts: Fox–Hunter's $w(k;3)>2^{k(\log^*k)/4}$, with the complete step-by-step (hitting set → LLL coloring → random-shifted-product iteration) recipe. - Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED) — the Erdős–Graham canonical-van-der-Waerden question, resolved by the *same base LLL/hitting-set gadget* but a different (growing-color-count, not log*-depth-recursion) amplification axis — a useful contrast for which escalation a given problem actually needs. - Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent — supplies the "turn a sparse hitting-set gadget into a genuine local no-domination coloring" step (Corollary 3.3) that this technique's base gadget relies on. - Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey) — the hypergraph-Ramsey tower-growth conjecture; contrast target for when the stepping-up lemma (full tower level per step) is the right tool instead of this weaker log*-budgeted technique. - Concept referenced but not yet its own page: "stepping-up lemma" (Erdős–Hajnal) — the tower-per-step iterated-construction sibling technique, already forward-linked from wikiscale/var/erdos/wiki/problems/564.md as concept/stepping-up-lemma; the natural next concept page to write for a full contrast with this one. - Concept referenced but not yet its own page: "Cole–Vishkin / Linial $\log^*$ round complexity" (distributed computing) — N. Linial, *SIAM J. Comput.* 21(1) (1992), 193–201, and its matching Cole–Vishkin upper bound — the standard theoretical-CS parallel instance of an exponential-per-round process whose exact round budget is $\Theta(\log^*n)$, useful as an outside-combinatorics sanity check on why $\log^*$ (and not, say, $\log\log$) is the natural unit for this family of arguments.