recursive_nae_seven_eighths_split_correction_square
For every natural depth d, with k the rounded-up seven-eighths split, two to the power d plus twice k is at most three to the power twice k. This is the squared integer form of the split correction estimate.
Statement
theorem recursive_nae_seven_eighths_split_correction_square (d : ℕ) : 2^(d + 2*((7*d+7)/8)) ≤ 3^(2*((7*d+7)/8))- Source
- Integer form of the balanced correction estimate for arXiv:2611.16412, Section 5.2; experiment 27234.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The inequality 2^(d + 2k) ≤ 3^(2k) for k = (7d + 7)/8 is proved by strong induction on the depth d with step size 8. First, an auxiliary lemma establishes that advancing d by 8 increases the split k by 7. The base cases d < 8 (d = 0, ..., 7) are verified by direct numerical computation. For d ≥ 8, this recurrence reduces the inequality to the induction hypothesis at d - 8 multiplied by the numerical inequality 2^22 ≤ 3^14.
Advancing depth d by 8 increases the split value by 7: in868_split (d + 8) = in868_split d + 7.
Unfolding the definition of in868_split d as (7*d + 7) / 8, the identity becomes (7*(d + 8) + 7) / 8 = (7*d + 7) / 8 + 7. Because 7*(d + 8) + 7 = (7*d + 7) + 56 and 56 = 7 * 8, integer division by 8 distributes to add 7, which omega verifies by Presburger arithmetic.
dsimp [in868_split] omega
The main goal is rephrased using the auxiliary split function in868_split d = (7*d + 7) / 8.
We rewrite the expression (7*d + 7) / 8 as in868_split d in both exponents to make the recurrence relation easier to state and apply.
change 2^(d + 2*in868_split d) ≤ 3^(2*in868_split d)The proof proceeds by strong induction on the depth d.
We set up strong induction on d: for any d, we may assume the claim holds for all strictly smaller depths m < d.
uses
Nat.strong_induction_oninduction d using Nat.strong_induction_on with | h d ih =>
The theorem holds for the base cases d < 8, namely d ∈ {0, 1, 2, 3, 4, 5, 6, 7}. automation
A case split on whether d < 8 separates the base cases from the inductive step. For d < 8, the depth d is exhausted case-by-case across the finite range 0 ≤ d ≤ 7, and in each of the eight cases, direct evaluation of the numerical inequality confirms that the left-hand side is at most the right-hand side.
by_cases h : d < 8 · interval_cases d <;> norm_num [in868_split]
For d ≥ 8, in868_split d = in868_split (d - 8) + 7.
Because d ≥ 8, we have (d - 8) + 8 = d. Instantiating the shift lemma in868_split_add_eight at d - 8 yields in868_split ((d - 8) + 8) = in868_split (d - 8) + 7, which simplifies to in868_split d = in868_split (d - 8) + 7.
uses
in868_split_add_eight· have hd : d-8+8=d := by omega have hs : in868_split d = in868_split (d-8)+7 := by have hh := in868_split_add_eight (d-8) rw [hd] at hh exact hh
The base 2 exponent decomposes as ((d - 8) + 2 * in868_split (d - 8)) + 22, and the base 3 exponent decomposes as 2 * in868_split (d - 8) + 14.
Substituting the recurrence in868_split d = in868_split (d - 8) + 7 and d = (d - 8) + 8 into the exponents, linear arithmetic shows that d + 2 * in868_split d = ((d - 8) + 2 * in868_split (d - 8)) + 22 and 2 * in868_split d = 2 * in868_split (d - 8) + 14.
have he : d+2*in868_split d = ((d-8)+2*in868_split (d-8))+22 := by omega have hf : 2*in868_split d = 2*in868_split (d-8)+14 := by omega
The inductive step holds: 2^(d + 2 * in868_split d) ≤ 3^(2 * in868_split d).
Factoring the powers using the exponent decompositions, 2^(d + 2 * in868_split d) equals 2^((d - 8) + 2 * in868_split (d - 8)) * 2^22. Applying the induction hypothesis at d - 8 (since d - 8 < d) gives 2^((d - 8) + 2 * in868_split (d - 8)) ≤ 3^(2 * in868_split (d - 8)), and numerical calculation confirms 2^22 = 4194304 ≤ 3^14 = 4782969. Multiplying these inequalities and combining powers yields 3^(2 * in868_split (d - 8) + 14) = 3^(2 * in868_split d).
uses
Nat.mul_le_mul,pow_addcalc _ = 2^((d-8)+2*in868_split (d-8))*2^22 := by rw [he, pow_add] _ ≤ 3^(2*in868_split (d-8))*3^14 := Nat.mul_le_mul (ih (d-8) (by omega)) (by norm_num) _ = _ := by rw [hf, pow_add]
Nat.strong_induction_on- Strong induction on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
in868_split_add_eight- For the split function S(d) = (7d + 7)/8, advancing the depth by 8 increases the split by 7: S(d + 8) = S(d) + 7.
pow_add- In any monoid, a^(m + n) = a^m * a^n.
Nat.mul_le_mul- If n₁ ≤ n₂ and m₁ ≤ m₂, then n₁ * m₁ ≤ n₂ * m₂ for natural numbers.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private def in868_split (d : ℕ) := (7*d+7)/8private theorem in868_split_add_eight (d : ℕ) : in868_split (d+8) = in868_split d+7 := by dsimp [in868_split] omegatheorem recursive_nae_seven_eighths_split_correction_square (d : ℕ) : 2^(d + 2*((7*d+7)/8)) ≤ 3^(2*((7*d+7)/8)) := by change 2^(d + 2*in868_split d) ≤ 3^(2*in868_split d) induction d using Nat.strong_induction_on with | h d ih => by_cases h : d < 8 · interval_cases d <;> norm_num [in868_split] · have hd : d-8+8=d := by omega have hs : in868_split d = in868_split (d-8)+7 := by have hh := in868_split_add_eight (d-8) rw [hd] at hh exact hh have he : d+2*in868_split d = ((d-8)+2*in868_split (d-8))+22 := by omega have hf : 2*in868_split d = 2*in868_split (d-8)+14 := by omega calc _ = 2^((d-8)+2*in868_split (d-8))*2^22 := by rw [he, pow_add] _ ≤ 3^(2*in868_split (d-8))*3^14 := Nat.mul_le_mul (ih (d-8) (by omega)) (by norm_num) _ = _ := by rw [hf, pow_add]