mondrian_two_chain_prefix_bound
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- 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$.
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.
induction a with | zero => simp
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$.
uses
Finset.sum_range_succ,pow_succ| succ a ih => rw [Finset.sum_range_succ, pow_succ]$(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$.
uses
Nat.mul_le_mul_righthave hm := Nat.mul_le_mul_right (p ^ a) (by omega : r + 2 ≤ p)
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.
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
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 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