recursive_nae_seven_eighths_split_bounds
For every depth d at least ten, the rounded seven-eighths split is positive and strictly smaller than d, and the shifted depth decreases by at least a factor 31/32.
Statement
theorem recursive_nae_seven_eighths_split_bounds (d : ℕ) (hd : 10 ≤ d) : 1 ≤ (7*d+7)/8 ∧ (7*d+7)/8 < d ∧ 32*((7*d+7)/8+2) ≤ 31*(d+2)- Source
- Balanced split for the recurrence of arXiv:2611.16412, Section 5.2; experiment 27234.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem establishes three inequalities for the integer quotient (7d + 7) / 8 when d ≥ 10: it is at least 1, strictly smaller than d, and satisfies the contraction bound 32 · ((7d + 7) / 8 + 2) ≤ 31 · (d + 2). All three conditions reduce to linear integer arithmetic over the natural numbers with integer division by a constant. The proof delegates the entire verification to the `omega` decision procedure for Presburger arithmetic.
For any natural number d ≥ 10, the inequalities 1 ≤ (7d + 7) / 8, (7d + 7) / 8 < d, and 32 · ((7d + 7) / 8 + 2) ≤ 31 · (d + 2) all hold. automation
The three conjuncts involve linear inequalities over ℕ with integer division by the constant 8. Under the assumption d ≥ 10: first, 7d + 7 ≥ 77 ≥ 8, so the quotient is at least 1; second, (7d + 7) / 8 < d is equivalent to 7d + 7 < 8d, or d > 7, which holds since d ≥ 10; third, 32 · ((7d + 7) / 8 + 2) ≤ 4(7d + 7) + 64 = 28d + 92, which is at most 31(d + 2) = 31d + 62 precisely when 3d ≥ 30 (i.e., d ≥ 10). The `omega` tactic discharges this system of linear integer inequalities automatically.
theorem recursive_nae_seven_eighths_split_bounds (d : ℕ) (hd : 10 ≤ d) : 1 ≤ (7*d+7)/8 ∧ (7*d+7)/8 < d ∧ 32*((7*d+7)/8+2) ≤ 31*(d+2) := by omega
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.
theorem recursive_nae_seven_eighths_split_bounds (d : ℕ) (hd : 10 ≤ d) : 1 ≤ (7*d+7)/8 ∧ (7*d+7)/8 < d ∧ 32*((7*d+7)/8+2) ≤ 31*(d+2) := by omega