two_ray_integer_atom_coeff_sum_le
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- two_ray_integer_atom_coeff_sum_le_primitiveFor an additive subgroup of integer-valued functions, let x have no proper nonzero nonnegative subgroup subvector. Given nonnegative…
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.
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.
classical by_contra hbadThere 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.
uses
coprime_residue_small_rectangleobtain ⟨k, hkD, hk0, hka, hkb⟩ := coprime_residue_small_rectangle D a b hD ha hb hca hcb (by omega)
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.
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 : ℤ))
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.
uses
Nat.mod_add_divhave 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
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.
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
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).
uses
mul_nonneg_iff_of_pos_left,add_nonneg,mul_nonneg,Nat.cast_nonneghave 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))
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.
uses
mul_le_mul_iff_right₀,Nat.le_of_lt,add_le_add,mul_le_mul_of_nonneg_righthave 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))
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.
uses
le_antisymmobtain ⟨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)
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.
uses
Nat.pos_of_ne_zero,Nat.ModEq,Nat.ModEq.cancel_right_of_coprime,Nat.mod_eq_of_lt,Nat.zero_modhave 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
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.
uses
Pi.zero_apply,mul_zero,mul_pos,mul_nonneg,Nat.cast_nonneghave 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
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.
uses
mul_pos,sub_pos.mpr,mul_nonneg,sub_nonneg.mprhave 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
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.
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
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.
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