AFTD Auto-Formalizing Theoretical Domains

recursive_nae_seven_eighths_split_bounds

theoremverified

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.

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

    line 1

    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

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