two_ray_integer_atom_coeff_sum_le_primitive
For an additive subgroup of integer-valued functions, let x have no proper nonzero nonnegative subgroup subvector. Given nonnegative primitive u,v in the subgroup, u nonzero, D positive, a,b smaller than D, and D*x=a*u+b*v, one has a+b at most D. Individual coefficient coprimality is not assumed.
Statement
theorem two_ray_integer_atom_coeff_sum_le_primitive {ι : 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) (hprimu : ∀ d : ℕ, (∀ i, (d : ℤ) ∣ u i) → d ∣ 1) (hprimv : ∀ d : ℕ, (∀ i, (d : ℤ) ∣ v i) → d ∣ 1) (D a b : ℕ) (hD : 0 < D) (ha : a < D) (hb : b < D) (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) : a + b ≤ D
- Source
- Helper for OP-197 / arXiv:2610.16562 Conjecture1, continuing the already verified two_ray_integer_atom_coeff_sum_le from deep session1. This closes primitive-ray denominator normalization and weighted length bookkeeping, not extraction of the two circuit rays or the box conjecture. No research advance claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- integer_primitive_ray_coeff_coprimeLet u,v,x be integer-valued functions, with v primitive in the sense that every common natural divisor of its coordinates divides one. If…
- two_ray_integer_atom_coeff_sum_leLet 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…
- 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
- integer_atom_sum_bound_of_two_primitive_raysIn an additive subgroup of finite integer vectors, an element with no proper nonzero nonnegative subgroup subvector has coordinate sum at…
The proof, explained
The theorem reduces the general bound $a + b \le D$ to the case where the coefficients are coprime to $D$, which is established by `two_ray_integer_atom_coeff_sum_le`. By dividing $a$, $b$, and $D$ by their joint greatest common divisor $d = \gcd(\gcd(a, b), D)$, the original linear relation scales down to $(D/d) x = (a/d) u + (b/d) v$ with $\gcd(\gcd(a/d, b/d), D/d) = 1$. The primitivity of $u$ and $v$ guarantees that $a/d$ and $b/d$ are individually coprime to $D/d$, after which applying the coprime version of the bound and multiplying through by $d$ yields $a + b \le D$.
Define $d = \gcd(\gcd(a, b), D)$, which is strictly positive, divides $D$, $a$, and $b$, and satisfies $d \cdot (D/d) = D$, $d \cdot (a/d) = a$, and $d \cdot (b/d) = b$.
Since $D > 0$, the joint greatest common divisor $d = \gcd(\gcd(a, b), D)$ is strictly positive by `Nat.gcd_pos_of_pos_right`. It divides $D$ and $\gcd(a, b)$, and hence divides both $a$ and $b$ by transitivity (`Nat.gcd_dvd_left` and `Nat.gcd_dvd_right`). Consequently, division by $d$ cancels exactly: $d \cdot (D/d) = D$, $d \cdot (a/d) = a$, and $d \cdot (b/d) = b$ via `Nat.mul_div_cancel'`.
uses
Nat.gcd_pos_of_pos_right,Nat.gcd_dvd_right,Nat.gcd_dvd_left,Nat.mul_div_cancel'let d := Nat.gcd (Nat.gcd a b) D have hd : 0 < d := Nat.gcd_pos_of_pos_right _ hD have hdD : d ∣ D := Nat.gcd_dvd_right _ _ have hda : d ∣ a := (Nat.gcd_dvd_left _ _).trans (Nat.gcd_dvd_left a b) have hdb : d ∣ b := (Nat.gcd_dvd_left _ _).trans (Nat.gcd_dvd_right a b) have hDD : d * (D/d) = D := Nat.mul_div_cancel' hdD have haa : d * (a/d) = a := Nat.mul_div_cancel' hda have hbb : d * (b/d) = b := Nat.mul_div_cancel' hdb
The scaled coefficients satisfy $0 < D/d$, $a/d < D/d$, and $b/d < D/d$.
Because $d > 0$, the identity $d \cdot (D/d) = D > 0$ gives $0 < D/d$. Similarly, since $a < D$ and $b < D$, dividing the products $d \cdot (a/d) < d \cdot (D/d)$ and $d \cdot (b/d) < d \cdot (D/d)$ by $d > 0$ yields $a/d < D/d$ and $b/d < D/d$, as verified by nonlinear arithmetic.
have hD' : 0 < D/d := by nlinarith have ha' : a/d < D/d := by nlinarith have hb' : b/d < D/d := by nlinarith
The joint greatest common divisor $\gcd(a/d, b/d)$ is coprime to $D/d$.
Factoring $d$ out of $\gcd(a, b) = \gcd(d(a/d), d(b/d))$ using `Nat.gcd_mul_left` gives $\gcd(a, b) = d \cdot \gcd(a/d, b/d)$. Cancelling the factor $d > 0$ with `Nat.eq_of_mul_eq_mul_left` establishes that $\gcd(a/d, b/d) = \gcd(a, b)/d$. Since $d = \gcd(\gcd(a, b), D)$, dividing both $\gcd(a, b)$ and $D$ by their greatest common divisor $d$ yields coprime values by `Nat.coprime_div_gcd_div_gcd`.
uses
Nat.gcd_mul_left,Nat.mul_div_cancel',Nat.gcd_dvd_left,Nat.eq_of_mul_eq_mul_left,Nat.coprime_div_gcd_div_gcdhave hg : Nat.gcd a b = d * Nat.gcd (a/d) (b/d) := by conv_lhs => rw [← haa, ← hbb] rw [Nat.gcd_mul_left] have hgdiv : Nat.gcd (a/d) (b/d) = (Nat.gcd a b)/d := by have hh := Nat.mul_div_cancel' (Nat.gcd_dvd_left (Nat.gcd a b) D) exact Nat.eq_of_mul_eq_mul_left hd (hg.symm.trans hh.symm) have htr' : Nat.Coprime (Nat.gcd (a/d) (b/d)) (D/d) := by rw [hgdiv] exact Nat.coprime_div_gcd_div_gcd hd
The scaled equation $(D/d) x(i) = (a/d) u(i) + (b/d) v(i)$ holds for all indices $i$.
Casting the cancellation identities to the integers, multiplying the difference $(D/d) x(i) - (a/d) u(i) - (b/d) v(i)$ by $d$ expands to $D x(i) - a u(i) - b v(i)$, which is zero by the original relation. Since $d \ne 0$, the product being zero implies that the scaled difference itself is zero by `mul_eq_zero.mp`, which rearranges linearly to the scaled relation.
uses
mul_eq_zero.mphave hdne : (d : ℤ) ≠ 0 := by exact_mod_cast hd.ne' have hDz : (d : ℤ) * ((D/d : ℕ) : ℤ) = D := by exact_mod_cast hDD have haz : (d : ℤ) * ((a/d : ℕ) : ℤ) = a := by exact_mod_cast haa have hbz : (d : ℤ) * ((b/d : ℕ) : ℤ) = b := by exact_mod_cast hbb have hrel' (i : ι) : ((D/d : ℕ) : ℤ) * x i = ((a/d : ℕ) : ℤ) * u i + ((b/d : ℕ) : ℤ) * v i := by have he : (d : ℤ) * (((D/d : ℕ) : ℤ) * x i - ((a/d : ℕ) : ℤ) * u i - ((b/d : ℕ) : ℤ) * v i) = 0 := by calc _ = ((d : ℤ) * ((D/d : ℕ) : ℤ)) * x i - ((d : ℤ) * ((a/d : ℕ) : ℤ)) * u i - ((d : ℤ) * ((b/d : ℕ) : ℤ)) * v i := by ring _ = 0 := by rw [hDz, haz, hbz, hrel]; ring have hh := (mul_eq_zero.mp he).resolve_left hdne linarith
Both $a/d$ and $b/d$ are coprime to $D/d$.
Applying `integer_primitive_ray_coeff_coprime` to $(u, v, x)$ with the primitivity of $v$, the scaled relation, and the coprimality of $\gcd(a/d, b/d)$ and $D/d$ establishes that $a/d$ is coprime to $D/d$. By commutativity of addition (`add_comm`) and $\gcd$ (`Nat.gcd_comm`), swapping $u$ and $v$ and applying the same theorem with the primitivity of $u$ establishes that $b/d$ is coprime to $D/d$.
uses
integer_primitive_ray_coeff_coprime,Nat.gcd_comm,add_commhave hca := integer_primitive_ray_coeff_coprime u v x hprimv (D/d) (a/d) (b/d) htr' hrel' have hcb : Nat.Coprime (b/d) (D/d) := by apply integer_primitive_ray_coeff_coprime v u x hprimu (D/d) (b/d) (a/d) · rw [Nat.gcd_comm (b/d) (a/d)] exact htr' · intro i simpa only [add_comm] using hrel' i
The scaled coefficients satisfy $a/d + b/d \le D/d$.
All hypotheses of `two_ray_integer_atom_coeff_sum_le` are fulfilled for the scaled parameters $D/d, a/d, b/d$: the atomicity of $x$, non-negativity of $u$ and $v$ with $u \ne 0$, bounds $0 < D/d$, $a/d < D/d$, $b/d < D/d$, individual coprimality of $a/d$ and $b/d$ with $D/d$, and the linear relation. Applying that theorem immediately gives $a/d + b/d \le D/d$.
uses
two_ray_integer_atom_coeff_sum_lehave hh := two_ray_integer_atom_coeff_sum_le M u v x huM hvM hxM hu0 hv0 hu hmin (D/d) (a/d) (b/d) hD' ha' hb' hca hcb hrel'$a + b \le D$.
Multiplying $a/d + b/d \le D/d$ by $d > 0$ yields $d(a/d) + d(b/d) \le d(D/d)$, which simplifies to $a + b \le D$ via nonlinear arithmetic since $d(a/d) = a$, $d(b/d) = b$, and $d(D/d) = D$.
nlinarith
Nat.gcd_pos_of_pos_right- If $n > 0$, then $\gcd(m, n) > 0$.
Nat.gcd_dvd_right- The greatest common divisor $\gcd(m, n)$ divides $n$.
Nat.gcd_dvd_left- The greatest common divisor $\gcd(m, n)$ divides $m$.
Nat.mul_div_cancel'- If $n$ divides $m$, then $n \cdot (m / n) = m$.
Nat.gcd_mul_left- The greatest common divisor scales with multiplication: $\gcd(m n, m k) = m \cdot \gcd(n, k)$.
Nat.eq_of_mul_eq_mul_left- If $n > 0$ and $n \cdot m = n \cdot k$, then $m = k$.
Nat.coprime_div_gcd_div_gcd- Dividing two numbers by their greatest common divisor yields coprime numbers.
mul_eq_zero.mp- If a product of two numbers is zero, then at least one of the factors is zero.
integer_primitive_ray_coeff_coprime- In an integer relation $D x = a u + b v$ where $v$ is primitive and $\gcd(\gcd(a, b), D) = 1$, the coefficient $a$ is coprime to $D$.
Nat.gcd_comm- The greatest common divisor is commutative: $\gcd(m, n) = \gcd(n, m)$.
add_comm- Addition is commutative: $a + b = b + a$.
two_ray_integer_atom_coeff_sum_le- For an atom $x$ and non-negative $u, v \in M$ with $u \ne 0$, if $D x = a u + b v$ with $0 < D$, $a < D$, $b < D$, and both $a$ and $b$ are individually coprime to $D$, then $a + b \le D$.
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 1000000set_option maxRecDepth 4000theorem two_ray_integer_atom_coeff_sum_le_primitive {ι : 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) (hprimu : ∀ d : ℕ, (∀ i, (d : ℤ) ∣ u i) → d ∣ 1) (hprimv : ∀ d : ℕ, (∀ i, (d : ℤ) ∣ v i) → d ∣ 1) (D a b : ℕ) (hD : 0 < D) (ha : a < D) (hb : b < D) (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) : a + b ≤ D := by let d := Nat.gcd (Nat.gcd a b) D have hd : 0 < d := Nat.gcd_pos_of_pos_right _ hD have hdD : d ∣ D := Nat.gcd_dvd_right _ _ have hda : d ∣ a := (Nat.gcd_dvd_left _ _).trans (Nat.gcd_dvd_left a b) have hdb : d ∣ b := (Nat.gcd_dvd_left _ _).trans (Nat.gcd_dvd_right a b) have hDD : d * (D/d) = D := Nat.mul_div_cancel' hdD have haa : d * (a/d) = a := Nat.mul_div_cancel' hda have hbb : d * (b/d) = b := Nat.mul_div_cancel' hdb have hD' : 0 < D/d := by nlinarith have ha' : a/d < D/d := by nlinarith have hb' : b/d < D/d := by nlinarith have hg : Nat.gcd a b = d * Nat.gcd (a/d) (b/d) := by conv_lhs => rw [← haa, ← hbb] rw [Nat.gcd_mul_left] have hgdiv : Nat.gcd (a/d) (b/d) = (Nat.gcd a b)/d := by have hh := Nat.mul_div_cancel' (Nat.gcd_dvd_left (Nat.gcd a b) D) exact Nat.eq_of_mul_eq_mul_left hd (hg.symm.trans hh.symm) have htr' : Nat.Coprime (Nat.gcd (a/d) (b/d)) (D/d) := by rw [hgdiv] exact Nat.coprime_div_gcd_div_gcd hd have hdne : (d : ℤ) ≠ 0 := by exact_mod_cast hd.ne' have hDz : (d : ℤ) * ((D/d : ℕ) : ℤ) = D := by exact_mod_cast hDD have haz : (d : ℤ) * ((a/d : ℕ) : ℤ) = a := by exact_mod_cast haa have hbz : (d : ℤ) * ((b/d : ℕ) : ℤ) = b := by exact_mod_cast hbb have hrel' (i : ι) : ((D/d : ℕ) : ℤ) * x i = ((a/d : ℕ) : ℤ) * u i + ((b/d : ℕ) : ℤ) * v i := by have he : (d : ℤ) * (((D/d : ℕ) : ℤ) * x i - ((a/d : ℕ) : ℤ) * u i - ((b/d : ℕ) : ℤ) * v i) = 0 := by calc _ = ((d : ℤ) * ((D/d : ℕ) : ℤ)) * x i - ((d : ℤ) * ((a/d : ℕ) : ℤ)) * u i - ((d : ℤ) * ((b/d : ℕ) : ℤ)) * v i := by ring _ = 0 := by rw [hDz, haz, hbz, hrel]; ring have hh := (mul_eq_zero.mp he).resolve_left hdne linarith have hca := integer_primitive_ray_coeff_coprime u v x hprimv (D/d) (a/d) (b/d) htr' hrel' have hcb : Nat.Coprime (b/d) (D/d) := by apply integer_primitive_ray_coeff_coprime v u x hprimu (D/d) (b/d) (a/d) · rw [Nat.gcd_comm (b/d) (a/d)] exact htr' · intro i simpa only [add_comm] using hrel' i have hh := two_ray_integer_atom_coeff_sum_le M u v x huM hvM hxM hu0 hv0 hu hmin (D/d) (a/d) (b/d) hD' ha' hb' hca hcb hrel' nlinarith