AFTD Auto-Formalizing Theoretical Domains

two_ray_integer_atom_coeff_sum_le_primitive

theoremverified

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

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

    lines 15–22

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

    lines 23–25

      have hD' : 0 < D/d := by nlinarith
      have ha' : a/d < D/d := by nlinarith
      have hb' : b/d < D/d := by nlinarith
  3. 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`.

    lines 26–34

    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_gcd

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

    lines 35–49

    uses mul_eq_zero.mp

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

    lines 50–56

    uses integer_primitive_ray_coeff_coprime, Nat.gcd_comm, add_comm

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

    lines 57–58

    uses two_ray_integer_atom_coeff_sum_le

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

    line 59

      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

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