AFTD Auto-Formalizing Theoretical Domains

mondrian_two_chain_signed_sum_ne_zero

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 6–12

      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]⟩
  2. 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.

    lines 13–16

    uses List.Nodup.of_map, List.inj_on_of_nodup_map, List.mem_toFinset.mp

      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
  3. 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).

    lines 17–19

      obtain ⟨t, ht, hmax⟩ := T.exists_max_image Prod.fst hT
      let R := T.erase t
      let V := R.image Prod.fst
  4. 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.

    lines 20–31

    uses Finset.mem_image.mp, Finset.mem_erase.mp, List.mem_toFinset.mp

      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
  5. 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 ℤ.

    lines 32–39

    uses Finset.sum_image, Finset.mem_erase.mp, mondrian_two_chain_lower_sum_lt, List.mem_toFinset.mp

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

    lines 40–48

    uses Finset.sum_le_sum, Nat.cast_sum, Finset.sum_neg_distrib

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

    lines 49–58

    uses List.sum_toFinset, Finset.add_sum_erase, Bool.false_eq_true, if_false, if_true

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

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