AFTD Auto-Formalizing Theoretical Domains

two_ray_integer_atom_coeff_sum_le

theoremverified

Let x be an atom in the nonnegative part of an additive subgroup of integer-valued functions. If D*x=a*u+b*v for nonnegative subgroup elements u,v, u is nonzero, a,b<D, and a,b are each coprime to D, then a+b<=D. This is the coefficient triangle inequality for the two-ray reduction.

Statement

theorem two_ray_integer_atom_coeff_sum_le {ι : Type*}
    (M : AddSubgroup (ι → ℤ)) (u v x : ι → ℤ)
    (huM : u ∈ M) (hvM : v ∈ M) (hxM : x ∈ M)
    (hu0 : ∀ i, 0 ≤ u i) (hv0 : ∀ i, 0 ≤ v i) (hu : u ≠ 0)
    (hmin : ∀ y ∈ M, (∀ i, 0 ≤ y i) → (∀ i, y i ≤ x i) → y = 0 ∨ y = x)
    (D a b : ℕ) (hD : 0 < D) (ha : a < D) (hb : b < D)
    (hca : Nat.Coprime a D) (hcb : Nat.Coprime b D)
    (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) :
    a + b ≤ D
Source
Supporting modular proof for the two-dimensional cone atom bound, a standard fact described in Combinatorial Commutative Algebra, Example 7.19 (https://pages.uoregon.edu/njp/MS.pdf). Used toward the four-support reduction for OP-197, arXiv:2610.16562 Conjecture 1; no new research-level result is claimed.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • coprime_residue_small_rectangleIf a and b are each coprime to D, are smaller than D, and sum to more than D, then some nonzero k<D has (k*a) mod D<a and (k*b) mod D<=b.…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The theorem is proved by contradiction: assuming a + b > D, one constructs a nonzero subgroup element y ∈ M strictly smaller than the atom x, contradicting atomicity. The key step applies coprime_residue_small_rectangle to obtain a multiplier 0 < k < D whose residues r = (k * a) % D and s = (k * b) % D satisfy r < a and s ≤ b. Setting y = k • x - qa • u - qb • v, the relation D * x = a * u + b * v implies D * y = r * u + s * v, which forces 0 ≤ y ≤ x; coprimality and u ≠ 0 then ensure that y is neither 0 nor x.

  1. Assume for contradiction that a + b > D.

    We enable classical reasoning and proceed by contradiction, assuming that the inequality a + b ≤ D fails, so D < a + b.

    lines 13–14

      classical
      by_contra hbad
  2. There exists a multiplier 0 < k < D whose residues mod D satisfy (k * a) % D < a and (k * b) % D ≤ b.

    Applying the lemma coprime_residue_small_rectangle to the coprime pairs a, D and b, D with D < a + b (verified by linear arithmetic) produces a multiplier k strictly between 0 and D whose residues mod D strictly decrease a and do not increase b.

    lines 15–16

    uses coprime_residue_small_rectangle

      obtain ⟨k, hkD, hk0, hka, hkb⟩ := coprime_residue_small_rectangle
        D a b hD ha hb hca hcb (by omega)
  3. Define remainder and quotient parameters r, s, qa, qb, and an element y = k • x - qa • u - qb • v in M.

    We define r = (k * a) % D, s = (k * b) % D, qa = (k * a) / D, and qb = (k * b) / D. Since x, u, v ∈ M and M is an additive subgroup closed under integer scalar multiplication and subtraction, the linear combination y belongs to M.

    lines 17–23

      let r := (k * a) % D
      let s := (k * b) % D
      let qa := (k * a) / D
      let qb := (k * b) / D
      let y := (k : ℤ) • x - (qa : ℤ) • u - (qb : ℤ) • v
      have hyM : y ∈ M := M.sub_mem (M.sub_mem (M.zsmul_mem hxM (k : ℤ))
        (M.zsmul_mem huM (qa : ℤ))) (M.zsmul_mem hvM (qb : ℤ))
  4. The division algorithm gives r + D * qa = k * a and s + D * qb = k * b in ℤ.

    By the division theorem (Nat.mod_add_div), the remainder and quotient satisfy r + D * qa = k * a and s + D * qb = k * b; casting to ℤ establishes both identities.

    lines 24–29

    uses Nat.mod_add_div

      have hqa : (r : ℤ) + (D : ℤ) * (qa : ℤ) = (k : ℤ) * (a : ℤ) := by
        dsimp [r, qa]
        exact_mod_cast Nat.mod_add_div (k * a) D
      have hqb : (s : ℤ) + (D : ℤ) * (qb : ℤ) = (k : ℤ) * (b : ℤ) := by
        dsimp [s, qb]
        exact_mod_cast Nat.mod_add_div (k * b) D
  5. For every index i, D * y(i) = r * u(i) + s * v(i).

    Expanding D * y(i) = k * (D * x(i)) - (D * qa) * u(i) - (D * qb) * v(i), substituting D * x(i) = a * u(i) + b * v(i) from the assumption, and collecting terms with the division identities k * a - D * qa = r and k * b - D * qb = s yields the relation.

    lines 30–39

      have hyr : ∀ i, (D : ℤ) * y i = (r : ℤ) * u i + (s : ℤ) * v i := by
        intro i
        dsimp [y]
        calc
          (D : ℤ) * ((k : ℤ) * x i - (qa : ℤ) * u i - (qb : ℤ) * v i) =
              (k : ℤ) * ((D : ℤ) * x i) -
                ((D : ℤ) * (qa : ℤ)) * u i - ((D : ℤ) * (qb : ℤ)) * v i := by ring
          _ = (r : ℤ) * u i + (s : ℤ) * v i := by
            rw [hrel]
            linear_combination -(u i) * hqa - (v i) * hqb
  6. The function y is coordinatewise nonnegative: 0 ≤ y(i) for all i.

    Because D > 0, mul_nonneg_iff_of_pos_left shows that 0 ≤ y(i) is equivalent to 0 ≤ D * y(i). Since D * y(i) = r * u(i) + s * v(i) with r, s ≥ 0 (Nat.cast_nonneg) and u(i), v(i) ≥ 0, add_nonneg and mul_nonneg show that 0 ≤ D * y(i).

    lines 40–46

    uses mul_nonneg_iff_of_pos_left, add_nonneg, mul_nonneg, Nat.cast_nonneg

      have hDz : (0 : ℤ) < D := by exact_mod_cast hD
      have hy0 : ∀ i, 0 ≤ y i := by
        intro i
        apply (mul_nonneg_iff_of_pos_left hDz).mp
        rw [hyr]
        exact add_nonneg (mul_nonneg (Nat.cast_nonneg _) (hu0 i))
          (mul_nonneg (Nat.cast_nonneg _) (hv0 i))
  7. The function y is coordinatewise bounded by x: y(i) ≤ x(i) for all i.

    Because D > 0, mul_le_mul_iff_right₀ shows that y(i) ≤ x(i) is equivalent to D * y(i) ≤ D * x(i). Substituting D * y(i) = r * u(i) + s * v(i) and D * x(i) = a * u(i) + b * v(i), the inequalities r ≤ a (from r < a via Nat.le_of_lt) and s ≤ b combine with u(i), v(i) ≥ 0 via mul_le_mul_of_nonneg_right and add_le_add to give the result.

    lines 47–54

    uses mul_le_mul_iff_right₀, Nat.le_of_lt, add_le_add, mul_le_mul_of_nonneg_right

      have hyle : ∀ i, y i ≤ x i := by
        intro i
        apply (mul_le_mul_iff_right₀ hDz).mp
        rw [hyr, hrel]
        have hrle : (r : ℤ) ≤ a := by exact_mod_cast Nat.le_of_lt hka
        have hsle : (s : ℤ) ≤ b := by exact_mod_cast hkb
        exact add_le_add (mul_le_mul_of_nonneg_right hrle (hu0 i))
          (mul_le_mul_of_nonneg_right hsle (hv0 i))
  8. There is a coordinate i where u(i) > 0.

    If u(i) ≤ 0 for all i, then since u(i) ≥ 0 everywhere, le_antisymm would force u = 0, contradicting the hypothesis that u ≠ 0.

    lines 55–60

    uses le_antisymm

      obtain ⟨i, hi⟩ : ∃ i, 0 < u i := by
        by_contra hnone
        push Not at hnone
        apply hu
        funext i
        exact le_antisymm (hnone i) (hu0 i)
  9. The remainder r is strictly positive: 0 < r.

    By Nat.pos_of_ne_zero, it suffices to rule out r = 0. If r = 0, then k * a ≡ 0 * a [MOD D] (Nat.ModEq). Canceling a coprime to D via Nat.ModEq.cancel_right_of_coprime yields k ≡ 0 [MOD D]. Since 0 < k < D, Nat.mod_eq_of_lt and Nat.zero_mod imply k = 0, which contradicts 0 < k.

    lines 61–70

    uses Nat.pos_of_ne_zero, Nat.ModEq, Nat.ModEq.cancel_right_of_coprime, Nat.mod_eq_of_lt, Nat.zero_mod

      have hr0 : 0 < r := by
        apply Nat.pos_of_ne_zero
        intro hz
        have hh : Nat.ModEq D (k * a) (0 * a) := by
          change (k * a) % D = (0 * a) % D
          simpa [r] using hz
        have hc := Nat.ModEq.cancel_right_of_coprime hca.symm hh
        have hk : k = 0 := by
          simpa only [Nat.ModEq, Nat.mod_eq_of_lt hkD, Nat.zero_mod] using hc
        omega
  10. y ≠ 0.

    If y = 0, then evaluating D * y(i) = r * u(i) + s * v(i) at a coordinate i where u(i) > 0 gives 0 = r * u(i) + s * v(i) via Pi.zero_apply and mul_zero. But r * u(i) > 0 by mul_pos and s * v(i) ≥ 0 by mul_nonneg and Nat.cast_nonneg, which is a contradiction by linear arithmetic.

    lines 71–78

    uses Pi.zero_apply, mul_zero, mul_pos, mul_nonneg, Nat.cast_nonneg

      have hyne : y ≠ 0 := by
        intro hz
        have he := hyr i
        rw [hz] at he
        simp only [Pi.zero_apply, mul_zero] at he
        have hp : (0 : ℤ) < (r : ℤ) * u i := mul_pos (by exact_mod_cast hr0) hi
        have hn := mul_nonneg (Nat.cast_nonneg s) (hv0 i)
        linarith
  11. y ≠ x.

    If y = x, then D * x(i) = r * u(i) + s * v(i), which rearranges to (a - r) * u(i) + (b - s) * v(i) = 0. But r < a implies a - r > 0 by sub_pos.mpr, so (a - r) * u(i) > 0 by mul_pos. Since s ≤ b implies b - s ≥ 0 by sub_nonneg.mpr, the term (b - s) * v(i) is nonnegative by mul_nonneg, so the sum cannot be zero, yielding a contradiction.

    lines 79–87

    uses mul_pos, sub_pos.mpr, mul_nonneg, sub_nonneg.mpr

      have hyx : y ≠ x := by
        intro heq
        have he := hyr i
        rw [heq, hrel] at he
        have hrlt : (r : ℤ) < a := by exact_mod_cast hka
        have hsle : (s : ℤ) ≤ b := by exact_mod_cast hkb
        have hp := mul_pos (sub_pos.mpr hrlt) hi
        have hn := mul_nonneg (sub_nonneg.mpr hsle) (hv0 i)
        nlinarith
  12. Contradiction with the atomicity of x, concluding a + b ≤ D.

    The atomicity assumption on x asserts that any element y ∈ M satisfying 0 ≤ y ≤ x must be either 0 or x. Since we showed y ≠ 0 and y ≠ x, both alternatives are eliminated, completing the proof by contradiction.

    line 88

      exact (hmin y hyM hy0 hyle).elim hyne hyx
coprime_residue_small_rectangle
For coprime natural numbers a and b less than D, if D < a + b, there exists an integer 0 < k < D such that (k * a) % D < a and (k * b) % D ≤ b.
Nat.mod_add_div
For any natural numbers m and k, m % k + k * (m / k) = m.
mul_nonneg_iff_of_pos_left
Multiplying by a strictly positive element preserves nonnegativity: if c > 0, then 0 ≤ c * b if and only if 0 ≤ b.
add_nonneg
The sum of two nonnegative elements is nonnegative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a + b.
mul_nonneg
The product of two nonnegative elements is nonnegative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a * b.
Nat.cast_nonneg
The canonical cast of any natural number into an ordered semiring is nonnegative: 0 ≤ (n : R).
mul_le_mul_iff_right₀
Multiplying by a strictly positive element reflects inequalities: if a > 0, then a * b ≤ a * c if and only if b ≤ c.
Nat.le_of_lt
A strict inequality between natural numbers implies a non-strict inequality: if n < m, then n ≤ m.
add_le_add
Inequalities can be added: if a ≤ b and c ≤ d, then a + c ≤ b + d.
mul_le_mul_of_nonneg_right
Multiplying an inequality b ≤ c by a nonnegative element a ≥ 0 on the right preserves the inequality: b * a ≤ c * a.
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
Nat.pos_of_ne_zero
A natural number is strictly positive if and only if it is nonzero: if n ≠ 0, then 0 < n.
Nat.ModEq
The modular equivalence relation on natural numbers: Nat.ModEq m a b means a % m = b % m.
Nat.ModEq.cancel_right_of_coprime
Right cancellation in modular equivalence: if gcd(m, c) = 1 and a * c ≡ b * c [MOD m], then a ≡ b [MOD m].
Nat.mod_eq_of_lt
If a < b for natural numbers, then a % b = a.
Nat.zero_mod
For any natural number b, 0 % b = 0.
Pi.zero_apply
Evaluating the zero function at any point gives zero: 0(i) = 0.
mul_zero
Multiplication by zero on the right gives zero: a * 0 = 0.
mul_pos
The product of two strictly positive elements is strictly positive: if 0 < a and 0 < b, then 0 < a * b.
sub_pos.mpr
If b < a, then 0 < a - b.
sub_nonneg.mpr
If b ≤ a, then 0 ≤ a - b.

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

open Finsetset_option maxHeartbeats 2000000theorem two_ray_integer_atom_coeff_sum_le {ι : Type*}    (M : AddSubgroup (ι → ℤ)) (u v x : ι → ℤ)    (huM : u ∈ M) (hvM : v ∈ M) (hxM : x ∈ M)    (hu0 : ∀ i, 0 ≤ u i) (hv0 : ∀ i, 0 ≤ v i) (hu : u ≠ 0)    (hmin : ∀ y ∈ M, (∀ i, 0 ≤ y i) → (∀ i, y i ≤ x i) → y = 0 ∨ y = x)    (D a b : ℕ) (hD : 0 < D) (ha : a < D) (hb : b < D)    (hca : Nat.Coprime a D) (hcb : Nat.Coprime b D)    (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) :    a + b ≤ D := by  classical  by_contra hbad  obtain ⟨k, hkD, hk0, hka, hkb⟩ := coprime_residue_small_rectangle    D a b hD ha hb hca hcb (by omega)  let r := (k * a) % D  let s := (k * b) % D  let qa := (k * a) / D  let qb := (k * b) / D  let y := (k : ℤ) • x - (qa : ℤ) • u - (qb : ℤ) • v  have hyM : y ∈ M := M.sub_mem (M.sub_mem (M.zsmul_mem hxM (k : ℤ))    (M.zsmul_mem huM (qa : ℤ))) (M.zsmul_mem hvM (qb : ℤ))  have hqa : (r : ℤ) + (D : ℤ) * (qa : ℤ) = (k : ℤ) * (a : ℤ) := by    dsimp [r, qa]    exact_mod_cast Nat.mod_add_div (k * a) D  have hqb : (s : ℤ) + (D : ℤ) * (qb : ℤ) = (k : ℤ) * (b : ℤ) := by    dsimp [s, qb]    exact_mod_cast Nat.mod_add_div (k * b) D  have hyr : ∀ i, (D : ℤ) * y i = (r : ℤ) * u i + (s : ℤ) * v i := by    intro i    dsimp [y]    calc      (D : ℤ) * ((k : ℤ) * x i - (qa : ℤ) * u i - (qb : ℤ) * v i) =          (k : ℤ) * ((D : ℤ) * x i) -            ((D : ℤ) * (qa : ℤ)) * u i - ((D : ℤ) * (qb : ℤ)) * v i := by ring      _ = (r : ℤ) * u i + (s : ℤ) * v i := by        rw [hrel]        linear_combination -(u i) * hqa - (v i) * hqb  have hDz : (0 : ℤ) < D := by exact_mod_cast hD  have hy0 : ∀ i, 0 ≤ y i := by    intro i    apply (mul_nonneg_iff_of_pos_left hDz).mp    rw [hyr]    exact add_nonneg (mul_nonneg (Nat.cast_nonneg _) (hu0 i))      (mul_nonneg (Nat.cast_nonneg _) (hv0 i))  have hyle : ∀ i, y i ≤ x i := by    intro i    apply (mul_le_mul_iff_right₀ hDz).mp    rw [hyr, hrel]    have hrle : (r : ℤ) ≤ a := by exact_mod_cast Nat.le_of_lt hka    have hsle : (s : ℤ) ≤ b := by exact_mod_cast hkb    exact add_le_add (mul_le_mul_of_nonneg_right hrle (hu0 i))      (mul_le_mul_of_nonneg_right hsle (hv0 i))  obtain ⟨i, hi⟩ : ∃ i, 0 < u i := by    by_contra hnone    push Not at hnone    apply hu    funext i    exact le_antisymm (hnone i) (hu0 i)  have hr0 : 0 < r := by    apply Nat.pos_of_ne_zero    intro hz    have hh : Nat.ModEq D (k * a) (0 * a) := by      change (k * a) % D = (0 * a) % D      simpa [r] using hz    have hc := Nat.ModEq.cancel_right_of_coprime hca.symm hh    have hk : k = 0 := by      simpa only [Nat.ModEq, Nat.mod_eq_of_lt hkD, Nat.zero_mod] using hc    omega  have hyne : y ≠ 0 := by    intro hz    have he := hyr i    rw [hz] at he    simp only [Pi.zero_apply, mul_zero] at he    have hp : (0 : ℤ) < (r : ℤ) * u i := mul_pos (by exact_mod_cast hr0) hi    have hn := mul_nonneg (Nat.cast_nonneg s) (hv0 i)    linarith  have hyx : y ≠ x := by    intro heq    have he := hyr i    rw [heq, hrel] at he    have hrlt : (r : ℤ) < a := by exact_mod_cast hka    have hsle : (s : ℤ) ≤ b := by exact_mod_cast hkb    have hp := mul_pos (sub_pos.mpr hrlt) hi    have hn := mul_nonneg (sub_nonneg.mpr hsle) (hv0 i)    nlinarith  exact (hmin y hyM hy0 hyle).elim hyne hyx
See it in the graphDiscuss this resultChallenge it