mondrian_two_chain_signed_sum_ne_zero
A 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.
Statement
theorem mondrian_two_chain_signed_sum_ne_zero (p r C : ℕ) (hC : 0 < C) (hr : 2 ≤ r) (hpr : r + 1 < p) (L : List (ℕ × Bool)) (hne : L ≠ []) (hnd : (L.map Prod.fst).Nodup) (hrep : ∀ t ∈ L, ∃ a : ℕ, t.1 = C * p ^ a ∨ t.1 = C * r * p ^ a) : (L.map (fun t => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ))).sum ≠ 0
- 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 4
- 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.
- 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…
- 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_partition_width_dvd_of_height_two_chainsIf d divides the square side and all width-indivisible tiles have heights in two superincreasing chains C*p^a and C*r*p^a, with p>r+1 and…
The proof, explained
The proof proceeds by contradiction using an extremal argument. By viewing the list as a finite set of signed terms with distinct magnitudes from the two chains, we isolate the unique element t with maximal absolute value t.1. By the auxiliary lemma mondrian_two_chain_lower_sum_lt, the sum of all smaller terms in the chains is strictly less than t.1, so the sum of the magnitudes of the remaining elements is strictly bounded by t.1. Consequently, the signed sum of the remaining elements cannot have absolute value equal to t.1, making it impossible for the total signed sum to vanish.
Define the set of terms T and the signed term function g, and establish that T is nonempty.
We work classically. We define T as the finite set of pairs in L and define g(t) to be t.1 if t.2 is true and -t.1 otherwise. Since L is assumed to be nonempty, T contains at least one element.
classical let T := L.toFinset let g := fun t : ℕ × Bool => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ) have hT : T.Nonempty := by cases L with | nil => simp at hne | cons t L => exact ⟨t, by simp [T]⟩
The first projection is injective on T, and L has no duplicate entries.
Since the list of first coordinates (L.map Prod.fst) has no duplicates, the list L itself has no duplicates by List.Nodup.of_map. By List.inj_on_of_nodup_map, if two elements in T have the same first coordinate, they must be equal, so their signs cannot differ either.
uses
List.Nodup.of_map,List.inj_on_of_nodup_map,List.mem_toFinset.mphave hLnd : L.Nodup := List.Nodup.of_map Prod.fst hnd have hinj : ∀ x ∈ T, ∀ y ∈ T, x.1 = y.1 → x = y := by intro x hx y hy hxy exact List.inj_on_of_nodup_map hnd (List.mem_toFinset.mp hx) (List.mem_toFinset.mp hy) hxy
Let t ∈ T be a term with maximal magnitude t.1, and let R = T \ {t} with V the set of its magnitudes.
Since T is nonempty and finite, there exists an element t ∈ T that maximizes the first coordinate t.1. We set R to be T with t removed, and define V as the image of R under the first projection (the set of magnitudes of all remaining terms).
obtain ⟨t, ht, hmax⟩ := T.exists_max_image Prod.fst hT let R := T.erase t let V := R.image Prod.fst
Every element in V comes from the two chains and is strictly smaller than t.1.
Every y ∈ V is of the form u.1 for some u ∈ R. Since u ∈ T comes from L, y satisfies the two-chain condition y = C * p^a or y = C * r * p^a. Furthermore, since u ∈ R, u ≠ t; by injectivity of the first projection on T, u.1 ≠ t.1. Combined with maximality u.1 ≤ t.1, linear arithmetic over ℕ establishes that y = u.1 < t.1.
uses
Finset.mem_image.mp,Finset.mem_erase.mp,List.mem_toFinset.mphave hV : ∀ y ∈ V, ∃ a, y = C * p ^ a ∨ y = C * r * p ^ a := by intro y hy obtain ⟨u, hu, rfl⟩ := Finset.mem_image.mp hy exact hrep u (List.mem_toFinset.mp (Finset.mem_erase.mp hu).2) have hVlt : ∀ y ∈ V, y < t.1 := by intro y hy obtain ⟨u, hu, rfl⟩ := Finset.mem_image.mp hy have huT := (Finset.mem_erase.mp hu).2 have hune := (Finset.mem_erase.mp hu).1 have hle := hmax u huT have hneq : u.1 ≠ t.1 := fun he => hune (hinj u huT t ht he) omega
The sum of the magnitudes of the remaining terms is strictly less than t.1.
Because the first projection is injective on R, reindexing via Finset.sum_image gives ∑_{y ∈ V} y = ∑_{u ∈ R} u.1. Since every y ∈ V belongs to the two chains and is strictly less than t.1 (which itself belongs to the two chains), the lemma mondrian_two_chain_lower_sum_lt implies that ∑_{y ∈ V} y < t.1. Thus ∑_{u ∈ R} u.1 < t.1, which also holds when cast to ℤ.
uses
Finset.sum_image,Finset.mem_erase.mp,mondrian_two_chain_lower_sum_lt,List.mem_toFinset.mphave hsumV : V.sum id = R.sum Prod.fst := by apply Finset.sum_image intro x hx y hy he exact hinj x (Finset.mem_erase.mp hx).2 y (Finset.mem_erase.mp hy).2 he have hpref := mondrian_two_chain_lower_sum_lt p r C t.1 hC hr hpr (hrep t (List.mem_toFinset.mp ht)) V hV hVlt rw [hsumV] at hpref have hprefZ : ((R.sum Prod.fst : ℕ) : ℤ) < (t.1 : ℤ) := by exact_mod_cast hpref
The signed sum of the remaining terms in R is bounded in absolute value by the sum of their magnitudes.
For each pair u = (a, b), g(u) ≤ a and -g(u) ≤ a hold directly by evaluating the conditional on b. Summing these inequalities over all u ∈ R via Finset.sum_le_sum gives ∑_{u ∈ R} g(u) ≤ ∑_{u ∈ R} u.1 and -∑_{u ∈ R} g(u) ≤ ∑_{u ∈ R} u.1.
uses
Finset.sum_le_sum,Nat.cast_sum,Finset.sum_neg_distribhave hbound : ∀ u : ℕ × Bool, g u ≤ (u.1 : ℤ) ∧ -g u ≤ (u.1 : ℤ) := by rintro ⟨a, b⟩ cases b <;> simp [g] <;> omega have hpos : R.sum g ≤ ((R.sum Prod.fst : ℕ) : ℤ) := by have hh := Finset.sum_le_sum (fun u (hu : u ∈ R) => (hbound u).1) simpa only [Nat.cast_sum] using hh have hneg : -(R.sum g) ≤ ((R.sum Prod.fst : ℕ) : ℤ) := by have hh := Finset.sum_le_sum (fun u (hu : u ∈ R) => (hbound u).2) simpa only [Finset.sum_neg_distrib, Nat.cast_sum] using hh
The assumption that the total signed sum is zero leads to a contradiction.
Suppose for contradiction that the signed sum over L is 0. Since L has no duplicates, the sum over list L equals the sum over the finset T, so ∑_{u ∈ T} g(u) = 0. Separating the maximal term t from R = T \ {t} gives g(t) + ∑_{u ∈ R} g(u) = 0, which means ∑_{u ∈ R} g(u) = -g(t) = ∓ t.1. But this implies t.1 ≤ ∑_{u ∈ R} u.1, contradicting the strict inequality ∑_{u ∈ R} u.1 < t.1. Linear integer arithmetic (linarith) after case analysis on the boolean sign of t derives False.
uses
List.sum_toFinset,Finset.add_sum_erase,Bool.false_eq_true,if_false,if_trueintro hzero have hsum0 : T.sum g = 0 := by rw [List.sum_toFinset g hLnd] exact hzero have he : g t + R.sum g = 0 := by change g t + (T.erase t).sum g = 0 rw [Finset.add_sum_erase T g ht, hsum0] have hgt : g t = if t.2 then (t.1 : ℤ) else -(t.1 : ℤ) := rfl rw [hgt] at he cases hb : t.2 <;> simp only [hb, Bool.false_eq_true, if_false, if_true] at he <;> linarith
List.Nodup.of_map- If the image of a list under a function has no duplicate elements, then the original list has no duplicates.
List.inj_on_of_nodup_map- If mapping a function across a list yields no duplicates, then the function is injective on the elements of the list.
List.mem_toFinset.mp- An element belonging to the Finset converted from a list is an element of the original list.
Finset.mem_image.mp- An element is in the image of a finite set under a function if and only if it is the image of some element in the set.
Finset.mem_erase.mp- An element in a finite set with a removed is in the original set and is not equal to a.
Finset.sum_image- The sum of a function over the image of a finite set equals the sum of the composite function over the original set, provided the mapping is injective on the set.
mondrian_two_chain_lower_sum_lt- Given positive C, r ≥ 2, and p > r + 1, the sum of any finite set of elements from the chains C * p^a and C * r * p^a that are strictly smaller than an element x from the chains is strictly less than x.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then the sum of f over s is at most the sum of g over s.
Nat.cast_sum- The integer cast of a finite sum of natural numbers equals the sum of their integer casts.
Finset.sum_neg_distrib- The sum of negated terms over a finite set equals the negation of their sum.
List.sum_toFinset- If a list has no duplicates, the sum of a function over its conversion to a Finset equals the sum of the function mapped over the list.
Finset.add_sum_erase- For an element a in a finite set s, f(a) plus the sum of f over s \ {a} equals the sum of f over s.
Bool.false_eq_true- The boolean false is not equal to true.
if_false- A conditional statement with a false condition evaluates to its second branch.
if_true- A conditional statement with a true condition evaluates to its first branch.
- The elements of the list L are represented as pairs (n, b) where n : ℕ is the magnitude and b : Bool encodes the sign (+ for true, - for false).
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_signed_sum_ne_zero (p r C : ℕ) (hC : 0 < C) (hr : 2 ≤ r) (hpr : r + 1 < p) (L : List (ℕ × Bool)) (hne : L ≠ []) (hnd : (L.map Prod.fst).Nodup) (hrep : ∀ t ∈ L, ∃ a : ℕ, t.1 = C * p ^ a ∨ t.1 = C * r * p ^ a) : (L.map (fun t => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ))).sum ≠ 0 := by classical let T := L.toFinset let g := fun t : ℕ × Bool => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ) have hT : T.Nonempty := by cases L with | nil => simp at hne | cons t L => exact ⟨t, by simp [T]⟩ have hLnd : L.Nodup := List.Nodup.of_map Prod.fst hnd have hinj : ∀ x ∈ T, ∀ y ∈ T, x.1 = y.1 → x = y := by intro x hx y hy hxy exact List.inj_on_of_nodup_map hnd (List.mem_toFinset.mp hx) (List.mem_toFinset.mp hy) hxy obtain ⟨t, ht, hmax⟩ := T.exists_max_image Prod.fst hT let R := T.erase t let V := R.image Prod.fst have hV : ∀ y ∈ V, ∃ a, y = C * p ^ a ∨ y = C * r * p ^ a := by intro y hy obtain ⟨u, hu, rfl⟩ := Finset.mem_image.mp hy exact hrep u (List.mem_toFinset.mp (Finset.mem_erase.mp hu).2) have hVlt : ∀ y ∈ V, y < t.1 := by intro y hy obtain ⟨u, hu, rfl⟩ := Finset.mem_image.mp hy have huT := (Finset.mem_erase.mp hu).2 have hune := (Finset.mem_erase.mp hu).1 have hle := hmax u huT have hneq : u.1 ≠ t.1 := fun he => hune (hinj u huT t ht he) omega have hsumV : V.sum id = R.sum Prod.fst := by apply Finset.sum_image intro x hx y hy he exact hinj x (Finset.mem_erase.mp hx).2 y (Finset.mem_erase.mp hy).2 he have hpref := mondrian_two_chain_lower_sum_lt p r C t.1 hC hr hpr (hrep t (List.mem_toFinset.mp ht)) V hV hVlt rw [hsumV] at hpref have hprefZ : ((R.sum Prod.fst : ℕ) : ℤ) < (t.1 : ℤ) := by exact_mod_cast hpref have hbound : ∀ u : ℕ × Bool, g u ≤ (u.1 : ℤ) ∧ -g u ≤ (u.1 : ℤ) := by rintro ⟨a, b⟩ cases b <;> simp [g] <;> omega have hpos : R.sum g ≤ ((R.sum Prod.fst : ℕ) : ℤ) := by have hh := Finset.sum_le_sum (fun u (hu : u ∈ R) => (hbound u).1) simpa only [Nat.cast_sum] using hh have hneg : -(R.sum g) ≤ ((R.sum Prod.fst : ℕ) : ℤ) := by have hh := Finset.sum_le_sum (fun u (hu : u ∈ R) => (hbound u).2) simpa only [Finset.sum_neg_distrib, Nat.cast_sum] using hh intro hzero have hsum0 : T.sum g = 0 := by rw [List.sum_toFinset g hLnd] exact hzero have he : g t + R.sum g = 0 := by change g t + (T.erase t).sum g = 0 rw [Finset.add_sum_erase T g ht, hsum0] have hgt : g t = if t.2 then (t.1 : ℤ) else -(t.1 : ℤ) := rfl rw [hgt] at he cases hb : t.2 <;> simp only [hb, Bool.false_eq_true, if_false, if_true] at he <;> linarith