proofs
Provedphase-diagrampolynomial-methodattentiondiagram

Degree count: 2(eR/n)^n ≤ δ as soon as n·log(n/(eR)) ≥ log(2/δ)

For all R,δ∈R\htmlData{mx=1}{R, \delta \in \htmlData{mx=0}{\mathbb{R}}} and n∈N\htmlData{mx=1}{n \in \htmlData{mx=0}{\mathbb{N}}}, if 0<n0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{n}, 0<R0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{R}, 0<δ0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{\delta} and log⁡(2δ)≤n⋅log⁡(ne1⋅R)\htmlData{mx=2}{\log \left(\htmlData{mx=1}{\frac{2}{\htmlData{mx=0}{\delta}}}\right)} \mathrel{\htmlData{mx=11}{\leq}} \htmlData{mx=10}{\htmlData{mx=3}{n} \cdot \htmlData{mx=9}{\log \left(\htmlData{mx=8}{\frac{\htmlData{mx=4}{n}}{\htmlData{mx=7}{\htmlData{mx=5}{e^{1}} \cdot \htmlData{mx=6}{R}}}}\right)}}, then

2⋅(e1⋅Rn)n≤δ\htmlData{mx=7}{2 \cdot \htmlData{mx=6}{\left(\htmlData{mx=4}{\frac{\htmlData{mx=2}{\htmlData{mx=0}{e^{1}} \cdot \htmlData{mx=1}{R}}}{\htmlData{mx=3}{n}}}\right)^{\htmlData{mx=5}{n}}}} \mathrel{\htmlData{mx=9}{\leq}} \htmlData{mx=8}{\delta}
What the notation means · or point at any symbol
RReal numbers
The real numbers: every point on the number line. (ℝ)
x ∈ TVariables
R, δ range over real numbers: the statement must hold for every choice. ((R δ : ℝ))
NNatural numbers
The natural numbers 0, 1, 2, …. In Lean they start at 0. (ℕ)
<Less than
0 is strictly smaller than n. (0 < n)
logNatural logarithm
The logarithm of 2/δ to base e: the power e must be raised to to give 2/δ. (Real.log (2 / δ))
≤At most
log(2/δ) is less than or equal to n · log(n/(exp(1) · R)). (Real.log (2 / δ) ≤ n * Real.log (n / (R…)
aᵇPower
exp(1) · R/n raised to the power n. ((Real.exp 1 * R / n) ^ n)
a/bDivision
2 divided by δ. In Lean, dividing by 0 gives 0. (2 / δ)
eˣExponential function
e raised to the power 1, where e ≈ 2.718. (Real.exp 1)
·Multiplication
exp(1) times R. (Real.exp 1 * R)

With R = α ln N and δ = ε/N this is n = κ α ln N with κ ln(κ/e) ≳ 1/α — the constant κ(α) ≥ e whose omission was the Phase-Diagram conjecture's self-corrected error. Together with pd-rank-bound and pd-epoly-mono, the polynomial branch's exponent 1 + e_poly(κ(α)α, c) is now rigorous. Part of 'Phase-Diagram conjecture: sampling versus the polynomial method in dimension c ln n'.

How it was proved

Proved
4 October 2026
By
Ajax, with the agent “Baguette math & proofs (Claude Code, 2026-10-03)”
Checked by
Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
Axioms
Classical.choice, Quot.sound, propext
Proof
23 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.

More proved statements