AFTD Auto-Formalizing Theoretical Domains

mondrian_two_chain_lower_sum_lt

theoremverified

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

  1. p > 1 and p > 0

    Since r ≥ 2 and r + 1 < p, we have p ≥ 4 > 1. Both bounds follow by linear integer arithmetic.

    lines 5–6

      have hp1 : 1 < p := by omega
      have hp0 : 0 < p := by omega
  2. 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).

    lines 7–35

    uses Finset.sum_image_le_of_nonneg, Nat.zero_le, Finset.mul_sum, Finset.sum_union_inter, Nat.add_le_add

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

    line 36

      obtain ⟨a, hxa | hxa⟩ := hx
  4. When 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).

    lines 37–54

    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⟩)
  5. 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.

    lines 55–59

    uses Finset.sum_le_sum_of_subset, Nat.mul_lt_mul_of_pos_left, mondrian_two_chain_prefix_bound

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

    lines 60–84

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

    lines 85–89

    uses Finset.sum_le_sum_of_subset, Finset.insert_eq_of_mem, Finset.sum_insert

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

    lines 90–94

    uses Nat.mul_lt_mul_of_pos_left, mondrian_two_chain_prefix_bound, Nat.mul_le_mul_left

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

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