AFTD Auto-Formalizing Theoretical Domains

recursive_nae_seven_eighths_split_correction_square

theoremverified

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.

  1. 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.

    lines 4–5

      dsimp [in868_split]
      omega
  2. 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.

    line 8

      change 2^(d + 2*in868_split d) ≤ 3^(2*in868_split d)
  3. 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.

    lines 9–10

    uses Nat.strong_induction_on

      induction d using Nat.strong_induction_on with
      | h d ih =>
  4. 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.

    lines 11–12

        by_cases h : d < 8
        · interval_cases d <;> norm_num [in868_split]
  5. 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.

    lines 13–17

    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
  6. 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.

    lines 18–19

          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
  7. 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).

    lines 20–23

    uses Nat.mul_le_mul, pow_add

          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]
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

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]
See it in the graphDiscuss this resultChallenge it