AFTD Auto-Formalizing Theoretical Domains

mondrian_two_chain_prefix_bound

theoremverified

If p is greater than r plus one, then (r+1) times the sum of p^i for i below a is strictly smaller than p^a.

Statement

theorem mondrian_two_chain_prefix_bound (p r a : ℕ) (hpr : r + 1 < p) :
    (r + 1) * (Finset.range a).sum (fun i => p ^ i) < p ^ a
Source
For the three-prime extension of OP-280, arXiv:2610.19193, Section 1. This develops the proved mondrian_no_perfect_two_prime_area and the width-free signed-height relation from this session.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2
  • mondrian_two_chain_lower_sum_ltIf C>0, r≥2 and p>r+1, the sum of any finite set of numbers from the chains C*p^a and C*r*p^a that are smaller than a fixed chain element…
  • mondrian_two_chain_signed_sum_ne_zeroA nonempty signed sum of distinct numbers drawn from the chains C*p^a and C*r*p^a cannot vanish when C is positive, r≥2 and p>r+1.

The proof, explained

The theorem is proved by induction on $a$. The base case $a = 0$ holds trivially because an empty sum is $0$. For the inductive step, splitting off the last term $p^a$ and applying the induction hypothesis bounds the sum by $(r + 2) p^a$, which is at most $p^{a+1}$ because $r + 1 < p$ implies $r + 2 \le p$.

  1. The inequality holds in the base case $a = 0$.

    We proceed by induction on $a$. For the base case $a = 0$, the sum over the empty range is $0$ and $p^0 = 1$. The inequality reduces to $(r + 1) \cdot 0 < 1$, or $0 < 1$, which holds trivially.

    lines 3–4

      induction a with
      | zero => simp
  2. In the inductive step, the sum up to $a + 1$ and the power $p^{a+1}$ are rewritten in terms of the sum up to $a$ and $p^a$.

    Assuming the induction hypothesis $(r + 1) \sum_{i=0}^{a-1} p^i < p^a$, we rewrite the sum $\sum_{i=0}^a p^i$ as $(\sum_{i=0}^{a-1} p^i) + p^a$ using `Finset.sum_range_succ`, and rewrite $p^{a+1}$ as $p^a \cdot p$ using `pow_succ`. The goal becomes showing $(r + 1) ((\sum_{i=0}^{a-1} p^i) + p^a) < p^a \cdot p$.

    lines 5–6

    uses Finset.sum_range_succ, pow_succ

      | succ a ih =>
        rw [Finset.sum_range_succ, pow_succ]
  3. $(r + 2) p^a \le p \cdot p^a$.

    From the hypothesis $r + 1 < p$ on natural numbers, we have $r + 2 \le p$. Multiplying both sides on the right by $p^a$ using `Nat.mul_le_mul_right` yields $(r + 2) p^a \le p \cdot p^a$.

    line 7

    uses Nat.mul_le_mul_right

        have hm := Nat.mul_le_mul_right (p ^ a) (by omega : r + 2 ≤ p)
  4. The inductive step is completed, establishing $(r + 1) \sum_{i=0}^a p^i < p^{a+1}$.

    Expanding the left-hand side gives $(r + 1) \sum_{i=0}^{a-1} p^i + (r + 1) p^a$. By the induction hypothesis, the first term is strictly bounded by $p^a$, so the expression is strictly less than $p^a + (r + 1) p^a = (r + 2) p^a$. Combining this with the inequality $(r + 2) p^a \le p \cdot p^a = p^a \cdot p$ established in the previous step, nonlinear arithmetic (`nlinarith`) closes the goal.

    line 8

        nlinarith
Finset.sum_range_succ
Splits off the last term of a sum over a range: $\sum_{x=0}^n f(x) = (\sum_{x=0}^{n-1} f(x)) + f(n)$.
pow_succ
In any monoid, $a^{n+1} = a^n \cdot a$.
Nat.mul_le_mul_right
If $n \le m$, then $n \cdot k \le m \cdot k$ 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

theorem mondrian_two_chain_prefix_bound (p r a : ℕ) (hpr : r + 1 < p) :    (r + 1) * (Finset.range a).sum (fun i => p ^ i) < p ^ a := by  induction a with  | zero => simp  | succ a ih =>    rw [Finset.sum_range_succ, pow_succ]    have hm := Nat.mul_le_mul_right (p ^ a) (by omega : r + 2 ≤ p)    nlinarith
See it in the graphDiscuss this resultChallenge it