mondrian_two_chain_lower_sum_lt
If 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 x is strictly smaller than x.
Statement
theorem mondrian_two_chain_lower_sum_lt (p r C x : ℕ) (hC : 0 < C) (hr : 2 ≤ r) (hpr : r + 1 < p)
(hx : ∃ a, x = C * p ^ a ∨ x = C * r * p ^ a)
(V : Finset ℕ) (hV : ∀ y ∈ V, ∃ a, y = C * p ^ a ∨ y = C * r * p ^ a)
(hVlt : ∀ y ∈ V, y < x) : V.sum id < x- Source
- Arithmetic helper for the three-prime extension of OP-280, arXiv:2610.19193 Section 1; the superincreasing-chain route was validated in experiment 5706.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- mondrian_two_chain_prefix_boundIf 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.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- 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 proof bounds the sum of elements of V by comparing V to prefixes of the two geometric chains C * p^i and C * r * p^i. It first proves that the sum of the elements in both chains with exponents strictly below a is at most C * (r + 1) * ∑ i < a, p^i, which is strictly less than C * p^a by the prefix bound lemma mondrian_two_chain_prefix_bound. Depending on whether the threshold x is C * p^a or C * r * p^a, every element of V is shown to fall into this prefix set (with at most the single element C * p^a added in the second case). In both cases, the resulting upper bound on the sum of V is strictly less than x.
p > 1 and p > 0
Since r ≥ 2 and r + 1 < p, we have p ≥ 4 > 1. Both bounds follow by linear integer arithmetic.
have hp1 : 1 < p := by omega have hp0 : 0 < p := by omega
For every a, the sum of all elements in the combined prefix U(a) is at most C * (r + 1) * ∑ i < a, p^i
Define U(a) as the union of the length-a prefixes from both chains: {C * p^i | i < a} ∪ {C * r * p^i | i < a}. The sum over each image is bounded by the corresponding sum over Finset.range a using Finset.sum_image_le_of_nonneg and Nat.zero_le. Factoring C and C * r out of these sums via Finset.mul_sum gives C * ∑ i < a, p^i and C * r * ∑ i < a, p^i. By Finset.sum_union_inter, the sum over the union plus the intersection equals the sum of the two image sums. Adding the two bounds via Nat.add_le_add and combining terms using ring gives C * (r + 1) * ∑ i < a, p^i; since the intersection sum is nonnegative, omega concludes the inequality for the union U(a).
uses
Finset.sum_image_le_of_nonneg,Nat.zero_le,Finset.mul_sum,Finset.sum_union_inter,Nat.add_le_addlet U := fun a => (Finset.range a).image (fun i => C * p ^ i) ∪ (Finset.range a).image (fun i => C * r * p ^ i) have hU : ∀ a, (U a).sum id ≤ C * (r + 1) * (Finset.range a).sum (fun i => p ^ i) := by intro a have h0 : ((Finset.range a).image (fun i => C * p ^ i)).sum id ≤ (Finset.range a).sum (fun i => C * p ^ i) := Finset.sum_image_le_of_nonneg (fun _ _ => Nat.zero_le _) have h1 : ((Finset.range a).image (fun i => C * r * p ^ i)).sum id ≤ (Finset.range a).sum (fun i => C * r * p ^ i) := Finset.sum_image_le_of_nonneg (fun _ _ => Nat.zero_le _) have he0 : (Finset.range a).sum (fun i => C * p ^ i) = C * (Finset.range a).sum (fun i => p ^ i) := by rw [Finset.mul_sum] have he1 : (Finset.range a).sum (fun i => C * r * p ^ i) = C * r * (Finset.range a).sum (fun i => p ^ i) := by rw [Finset.mul_sum] rw [he0] at h0 rw [he1] at h1 have hu : ((Finset.range a).image (fun i => C * p ^ i) ∪ (Finset.range a).image (fun i => C * r * p ^ i)).sum id + ((Finset.range a).image (fun i => C * p ^ i) ∩ (Finset.range a).image (fun i => C * r * p ^ i)).sum id = ((Finset.range a).image (fun i => C * p ^ i)).sum id + ((Finset.range a).image (fun i => C * r * p ^ i)).sum id := Finset.sum_union_inter have hs := Nat.add_le_add h0 h1 have he : C * (Finset.range a).sum (fun i => p ^ i) + C * r * (Finset.range a).sum (fun i => p ^ i) = C * (r + 1) * (Finset.range a).sum (fun i => p ^ i) := by ring rw [he] at hs dsimp [U] omega
There exists an exponent a such that either x = C * p^a or x = C * r * p^a
By the hypothesis hx, the fixed upper bound x is an element of one of the two chains, so we split into two cases: x = C * p^a or x = C * r * p^a for some exponent a.
obtain ⟨a, hxa | hxa⟩ := hxWhen x = C * p^a, the set V is a subset of U(a)
Take any y ∈ V. By hypothesis hV, y = C * p^b or y = C * r * p^b for some exponent b. If y = C * p^b, the condition y < x = C * p^a implies p^b < p^a, which gives b < a by strict monotonicity of powers (Nat.pow_lt_pow_iff_right); hence y ∈ U(a) via the left component of the union (Finset.mem_union_left, Finset.mem_image.mpr, Finset.mem_range.mpr). If y = C * r * p^b, using 1 ≤ r and Nat.mul_le_mul_left shows C * p^b ≤ C * r * p^b < C * p^a, which again forces b < a by Nat.pow_lt_pow_iff_right; hence y ∈ U(a) via the right component (Finset.mem_union_right, Finset.mem_image.mpr, Finset.mem_range.mpr).
uses
Nat.pow_lt_pow_iff_right,Finset.mem_union_left,Finset.mem_image.mpr,Finset.mem_range.mpr,Nat.mul_le_mul_left,Finset.mem_union_right· have hsub : V ⊆ U a := by intro y hy obtain ⟨b, hyb | hyb⟩ := hV y hy · have hba : b < a := by apply (Nat.pow_lt_pow_iff_right hp1).mp have hlt := hVlt y hy rw [hyb, hxa] at hlt nlinarith exact Finset.mem_union_left _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr hba, hyb.symm⟩) · have hsc : C * p ^ b ≤ C * r * p ^ b := by have hh := Nat.mul_le_mul_left (C * p ^ b) (by omega : 1 ≤ r) nlinarith have hba : b < a := by apply (Nat.pow_lt_pow_iff_right hp1).mp have hlt := hVlt y hy rw [hyb, hxa] at hlt nlinarith exact Finset.mem_union_right _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr hba, hyb.symm⟩)
When x = C * p^a, the sum of V is strictly smaller than x
Since V ⊆ U(a), the sum of V is at most the sum of U(a) by Finset.sum_le_sum_of_subset. By mondrian_two_chain_prefix_bound, (r + 1) * ∑ i < a, p^i < p^a, so multiplying by C > 0 using Nat.mul_lt_mul_of_pos_left yields C * (r + 1) * ∑ i < a, p^i < C * p^a. Combining this with the upper bound on the sum of U(a), nonlinear arithmetic establishes V.sum id < C * p^a = x.
uses
Finset.sum_le_sum_of_subset,Nat.mul_lt_mul_of_pos_left,mondrian_two_chain_prefix_boundhave hsum : V.sum id ≤ (U a).sum id := Finset.sum_le_sum_of_subset hsub have hpref := Nat.mul_lt_mul_of_pos_left (mondrian_two_chain_prefix_bound p r a hpr) hC have hu := hU a rw [hxa] nlinarith
When x = C * r * p^a, the set V is a subset of insert (C * p^a) (U(a))
Take any y ∈ V. If y = C * p^b, from y < C * r * p^a and r < p we have p^b < p^(a + 1) using Nat.mul_lt_mul_of_pos_right, pow_pos, and pow_succ. Thus b ≤ a by Nat.pow_lt_pow_iff_right. If b = a, y is the inserted element C * p^a (Finset.mem_insert_self). If b < a, y ∈ U(a) via the left component of the union, so it belongs to the inserted set by Finset.mem_insert_of_mem, Finset.mem_union_left, Finset.mem_image.mpr, and Finset.mem_range.mpr. If instead y = C * r * p^b, then C * r * p^b < C * r * p^a with C * r > 0 (Nat.mul_pos) yields b < a by Nat.pow_lt_pow_iff_right; hence y ∈ U(a) via the right component, placing it in the inserted set (Finset.mem_insert_of_mem, Finset.mem_union_right, Finset.mem_image.mpr, Finset.mem_range.mpr).
uses
Nat.mul_lt_mul_of_pos_right,pow_pos,pow_succ,Nat.pow_lt_pow_iff_right,Finset.mem_insert_self,Finset.mem_insert_of_mem,Finset.mem_union_left,Finset.mem_image.mpr,Finset.mem_range.mpr,Nat.mul_pos,Finset.mem_union_right· have hsub : V ⊆ insert (C * p ^ a) (U a) := by intro y hy obtain ⟨b, hyb | hyb⟩ := hV y hy · have hba : b ≤ a := by have hlt := hVlt y hy rw [hyb, hxa] at hlt have hpow : p ^ b < p ^ (a + 1) := by have hh := Nat.mul_lt_mul_of_pos_right (by omega : r < p) (pow_pos hp0 a) rw [pow_succ] nlinarith have := (Nat.pow_lt_pow_iff_right hp1).mp hpow omega by_cases hbeq : b = a · rw [hyb, hbeq] exact Finset.mem_insert_self _ _ · apply Finset.mem_insert_of_mem exact Finset.mem_union_left _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr (by omega), hyb.symm⟩) · have hba : b < a := by apply (Nat.pow_lt_pow_iff_right hp1).mp have hlt := hVlt y hy rw [hyb, hxa] at hlt have hCr := Nat.mul_pos hC (by omega : 0 < r) nlinarith apply Finset.mem_insert_of_mem exact Finset.mem_union_right _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr hba, hyb.symm⟩)
When x = C * r * p^a, the sum of V is bounded by C * p^a + the sum of U(a)
By inclusion V ⊆ insert (C * p^a) (U(a)), the sum of V is bounded by the sum of the inserted set (Finset.sum_le_sum_of_subset). If C * p^a is already in U(a), insert does not change the set (Finset.insert_eq_of_mem). If not, the sum over the inserted set equals C * p^a plus the sum of U(a) by Finset.sum_insert. In either case, the sum is at most C * p^a + (U a).sum id.
uses
Finset.sum_le_sum_of_subset,Finset.insert_eq_of_mem,Finset.sum_inserthave hsum : V.sum id ≤ (insert (C * p ^ a) (U a)).sum id := Finset.sum_le_sum_of_subset hsub have hins : (insert (C * p ^ a) (U a)).sum id ≤ C * p ^ a + (U a).sum id := by by_cases hh : C * p ^ a ∈ U a · rw [Finset.insert_eq_of_mem hh]; omega · simp [Finset.sum_insert hh]
When x = C * r * p^a, the sum of V is strictly smaller than x
By mondrian_two_chain_prefix_bound scaled by C > 0 (Nat.mul_lt_mul_of_pos_left), the sum of U(a) is strictly less than C * p^a. Since r ≥ 2, we have 2 * (C * p^a) ≤ C * r * p^a via Nat.mul_le_mul_left. Thus the sum of V is at most C * p^a + (U a).sum id < C * p^a + C * p^a ≤ C * r * p^a = x, which closes the goal by nonlinear arithmetic.
uses
Nat.mul_lt_mul_of_pos_left,mondrian_two_chain_prefix_bound,Nat.mul_le_mul_lefthave hpref := Nat.mul_lt_mul_of_pos_left (mondrian_two_chain_prefix_bound p r a hpr) hC have hu := hU a have htwo := Nat.mul_le_mul_left (C * p ^ a) hr rw [hxa] nlinarith
Finset.mul_sum- multiplication distributes over finite summation: a * ∑ i, f i = ∑ i, a * f i
Finset.sum_image_le_of_nonneg- for a non-negative function, the sum over the image of a finite set is bounded by the sum over the domain
Finset.sum_union_inter- the sum over a union plus the sum over an intersection equals the sum over the two finite sets
Finset.sum_le_sum_of_subset- if s ⊆ t and values are non-negative, the sum over s is at most the sum over t
Finset.insert_eq_of_mem- inserting an already present element into a finite set leaves the set unchanged
Finset.sum_insert- the sum over insert a s is f(a) plus the sum over s, provided a ∉ s
Finset.mem_union_left- if an element belongs to s, it belongs to s ∪ t
Finset.mem_union_right- if an element belongs to t, it belongs to s ∪ t
Finset.mem_image.mpr- an element is in the image of a set under a function if it has a preimage in the set
Finset.mem_range.mpr- a natural number i is in Finset.range n if and only if i < n
Finset.mem_insert_self- an element a is always in insert a s
Finset.mem_insert_of_mem- if a ∈ s, then a ∈ insert b s
Nat.zero_le- every natural number is at least 0
Nat.add_le_add- inequalities between natural numbers are preserved under addition: a ≤ b and c ≤ d implies a + c ≤ b + d
Nat.pow_lt_pow_iff_right- for base a > 1, powers satisfy a^n < a^m if and only if n < m
Nat.mul_le_mul_left- multiplication by a constant preserves non-strict inequality: n ≤ m implies k * n ≤ k * m
Nat.mul_pos- strictly positive natural numbers have a strictly positive product
Nat.mul_lt_mul_of_pos_left- multiplication by a strictly positive number preserves strict inequality on the left: n < m and k > 0 implies k * n < k * m
Nat.mul_lt_mul_of_pos_right- multiplication by a strictly positive number preserves strict inequality on the right: n < m and k > 0 implies n * k < m * k
pow_pos- a strictly positive natural number raised to any power is strictly positive
pow_succ- the successor power satisfies a^(n + 1) = a^n * a
mondrian_two_chain_prefix_bound- under r + 1 < p, the prefix sum satisfies (r + 1) * ∑ i < a, p^i < p^a
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_lower_sum_lt (p r C x : ℕ) (hC : 0 < C) (hr : 2 ≤ r) (hpr : r + 1 < p) (hx : ∃ a, x = C * p ^ a ∨ x = C * r * p ^ a) (V : Finset ℕ) (hV : ∀ y ∈ V, ∃ a, y = C * p ^ a ∨ y = C * r * p ^ a) (hVlt : ∀ y ∈ V, y < x) : V.sum id < x := by have hp1 : 1 < p := by omega have hp0 : 0 < p := by omega let U := fun a => (Finset.range a).image (fun i => C * p ^ i) ∪ (Finset.range a).image (fun i => C * r * p ^ i) have hU : ∀ a, (U a).sum id ≤ C * (r + 1) * (Finset.range a).sum (fun i => p ^ i) := by intro a have h0 : ((Finset.range a).image (fun i => C * p ^ i)).sum id ≤ (Finset.range a).sum (fun i => C * p ^ i) := Finset.sum_image_le_of_nonneg (fun _ _ => Nat.zero_le _) have h1 : ((Finset.range a).image (fun i => C * r * p ^ i)).sum id ≤ (Finset.range a).sum (fun i => C * r * p ^ i) := Finset.sum_image_le_of_nonneg (fun _ _ => Nat.zero_le _) have he0 : (Finset.range a).sum (fun i => C * p ^ i) = C * (Finset.range a).sum (fun i => p ^ i) := by rw [Finset.mul_sum] have he1 : (Finset.range a).sum (fun i => C * r * p ^ i) = C * r * (Finset.range a).sum (fun i => p ^ i) := by rw [Finset.mul_sum] rw [he0] at h0 rw [he1] at h1 have hu : ((Finset.range a).image (fun i => C * p ^ i) ∪ (Finset.range a).image (fun i => C * r * p ^ i)).sum id + ((Finset.range a).image (fun i => C * p ^ i) ∩ (Finset.range a).image (fun i => C * r * p ^ i)).sum id = ((Finset.range a).image (fun i => C * p ^ i)).sum id + ((Finset.range a).image (fun i => C * r * p ^ i)).sum id := Finset.sum_union_inter have hs := Nat.add_le_add h0 h1 have he : C * (Finset.range a).sum (fun i => p ^ i) + C * r * (Finset.range a).sum (fun i => p ^ i) = C * (r + 1) * (Finset.range a).sum (fun i => p ^ i) := by ring rw [he] at hs dsimp [U] omega obtain ⟨a, hxa | hxa⟩ := hx · have hsub : V ⊆ U a := by intro y hy obtain ⟨b, hyb | hyb⟩ := hV y hy · have hba : b < a := by apply (Nat.pow_lt_pow_iff_right hp1).mp have hlt := hVlt y hy rw [hyb, hxa] at hlt nlinarith exact Finset.mem_union_left _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr hba, hyb.symm⟩) · have hsc : C * p ^ b ≤ C * r * p ^ b := by have hh := Nat.mul_le_mul_left (C * p ^ b) (by omega : 1 ≤ r) nlinarith have hba : b < a := by apply (Nat.pow_lt_pow_iff_right hp1).mp have hlt := hVlt y hy rw [hyb, hxa] at hlt nlinarith exact Finset.mem_union_right _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr hba, hyb.symm⟩) have hsum : V.sum id ≤ (U a).sum id := Finset.sum_le_sum_of_subset hsub have hpref := Nat.mul_lt_mul_of_pos_left (mondrian_two_chain_prefix_bound p r a hpr) hC have hu := hU a rw [hxa] nlinarith · have hsub : V ⊆ insert (C * p ^ a) (U a) := by intro y hy obtain ⟨b, hyb | hyb⟩ := hV y hy · have hba : b ≤ a := by have hlt := hVlt y hy rw [hyb, hxa] at hlt have hpow : p ^ b < p ^ (a + 1) := by have hh := Nat.mul_lt_mul_of_pos_right (by omega : r < p) (pow_pos hp0 a) rw [pow_succ] nlinarith have := (Nat.pow_lt_pow_iff_right hp1).mp hpow omega by_cases hbeq : b = a · rw [hyb, hbeq] exact Finset.mem_insert_self _ _ · apply Finset.mem_insert_of_mem exact Finset.mem_union_left _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr (by omega), hyb.symm⟩) · have hba : b < a := by apply (Nat.pow_lt_pow_iff_right hp1).mp have hlt := hVlt y hy rw [hyb, hxa] at hlt have hCr := Nat.mul_pos hC (by omega : 0 < r) nlinarith apply Finset.mem_insert_of_mem exact Finset.mem_union_right _ (Finset.mem_image.mpr ⟨b, Finset.mem_range.mpr hba, hyb.symm⟩) have hsum : V.sum id ≤ (insert (C * p ^ a) (U a)).sum id := Finset.sum_le_sum_of_subset hsub have hins : (insert (C * p ^ a) (U a)).sum id ≤ C * p ^ a + (U a).sum id := by by_cases hh : C * p ^ a ∈ U a · rw [Finset.insert_eq_of_mem hh]; omega · simp [Finset.sum_insert hh] have hpref := Nat.mul_lt_mul_of_pos_left (mondrian_two_chain_prefix_bound p r a hpr) hC have hu := hU a have htwo := Nat.mul_le_mul_left (C * p ^ a) hr rw [hxa] nlinarith