AFTD Auto-Formalizing Theoretical Domains

integer_atom_sum_bound_of_two_primitive_rays

theoremverified

In an additive subgroup of finite integer vectors, an element with no proper nonzero nonnegative subgroup subvector has coordinate sum at most B if it is a nonnegative rational combination of two nonzero nonnegative primitive subgroup vectors, each of sum at most the nonnegative integer B. The common denominator and coefficients are arbitrary positive/nonnegative integers; coefficients smaller than the denominator are not assumed.

Statement

theorem integer_atom_sum_bound_of_two_primitive_rays {ι : Type*} [Fintype ι]
    (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) (hv : v ≠ 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)
    (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i)
    (B : ℤ) (hB : 0 ≤ B) (hub : (∑ i, u i) ≤ B) (hvb : (∑ i, v i) ≤ B) :
    (∑ i, x i) ≤ B
Source
Supporting lemma or explicit route obstruction for OP-197 / arXiv:2610.16562 Conjecture1, deep session2. The abstract two-ray fact and finite obstruction are not claimed novel or research-level; no part is the full box conjecture. The five-point kernel has columns (1,1),(1,0),(0,1),(-2,0),(0,-2).
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof proceeds by casework on whether either integer coefficient a or b is at least the denominator D. If a ≥ D (or symmetrically b ≥ D), nonnegativity of the other ray implies u ≤ x (or v ≤ x), so the atomicity of x forces x = u (or x = v), directly transferring the coordinate sum bound B. In the remaining case where a < D and b < D, the atomicity of x and primitivity of u and v allow invoking `two_ray_integer_atom_coeff_sum_le_primitive` to deduce a + b ≤ D. Finally, `two_ray_nonnegative_sum_bound` applies to show that any combination with coefficient sum at most D preserves the coordinate sum bound B.

  1. D > 0 holds in ℤ.

    The positivity assumption D > 0 on natural numbers is cast to the integers (`exact_mod_cast`), providing a strictly positive integer denominator for the arithmetic steps that follow.

    line 16

      have hDz : (0 : ℤ) < D := by exact_mod_cast hD
  2. If D ≤ a, then ∑ i, x i ≤ B.

    Consider the case D ≤ a. For each coordinate i, since D ≤ a and u i ≥ 0, multiplying gives D * u i ≤ a * u i via `mul_le_mul_of_nonneg_right`. Combining this with b * v i ≥ 0 (from `mul_nonneg` and `Nat.cast_nonneg`) and the relation D * x i = a * u i + b * v i, nonlinear arithmetic (`nlinarith`) establishes u i ≤ x i for all i. Since u is nonzero, nonnegative, and belongs to M, the minimality hypothesis `hmin` forces u = x (ruling out u = 0 via `resolve_left`). Substituting u = x into the sum bound on u concludes this case.

    lines 17–26

    uses mul_le_mul_of_nonneg_right, mul_nonneg, Nat.cast_nonneg, resolve_left

      by_cases ha : D ≤ a
      · have hau : ∀ i, u i ≤ x i := by
          intro i
          have hai : (D : ℤ) ≤ a := by exact_mod_cast ha
          have hh := mul_le_mul_of_nonneg_right hai (hu0 i)
          have hbv : 0 ≤ (b : ℤ) * v i := mul_nonneg (Nat.cast_nonneg _) (hv0 i)
          have hr := hrel i
          nlinarith
        have hx := (hmin u huM hu0 hau).resolve_left hu
        simpa only [← hx] using hub
  3. If D ≤ b, then ∑ i, x i ≤ B.

    Symmetrically, consider the case D ≤ b. For each coordinate i, D * v i ≤ b * v i by `mul_le_mul_of_nonneg_right`, and a * u i ≥ 0 by `mul_nonneg` and `Nat.cast_nonneg`. Along with D * x i = a * u i + b * v i, `nlinarith` shows v i ≤ x i for all i. Minimality of the atom x together with v ≠ 0 forces v = x via `resolve_left`, so the sum bound on v yields ∑ i, x i ≤ B.

    lines 27–36

    uses mul_le_mul_of_nonneg_right, mul_nonneg, Nat.cast_nonneg, resolve_left

      by_cases hb : D ≤ b
      · have hav : ∀ i, v i ≤ x i := by
          intro i
          have hbi : (D : ℤ) ≤ b := by exact_mod_cast hb
          have hh := mul_le_mul_of_nonneg_right hbi (hv0 i)
          have hau : 0 ≤ (a : ℤ) * u i := mul_nonneg (Nat.cast_nonneg _) (hu0 i)
          have hr := hrel i
          nlinarith
        have hx := (hmin v hvM hv0 hav).resolve_left hv
        simpa only [← hx] using hvb
  4. When a < D and b < D, the coefficients satisfy a + b ≤ D.

    In the remaining case where D ≰ a and D ≰ b, linear integer arithmetic (`omega`) deduces a < D and b < D. Because x is an atom and u, v are primitive vectors spanning the cone containing x, the lemma `two_ray_integer_atom_coeff_sum_le_primitive` applies to show that the sum of the numerators cannot exceed the common denominator, yielding a + b ≤ D.

    lines 37–38

    uses two_ray_integer_atom_coeff_sum_le_primitive

      have hc := two_ray_integer_atom_coeff_sum_le_primitive M u v x huM hvM hxM hu0 hv0 hu
        hmin hprimu hprimv D a b hD (by omega) (by omega) hrel
  5. ∑ i, x i ≤ B.

    With the coefficient bound a + b ≤ D established, the lemma `two_ray_nonnegative_sum_bound` deduces that the coordinate sum ∑ i, x i is at most B, completing the proof.

    line 39

    uses two_ray_nonnegative_sum_bound

      exact two_ray_nonnegative_sum_bound u v x D a b hD hc B hB hub hvb hrel
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality by a nonnegative element on the right preserves the inequality.
mul_nonneg
The product of two nonnegative elements is nonnegative.
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is nonnegative.
resolve_left
Given a disjunction P ∨ Q and a proof of ¬P, concludes Q.
two_ray_integer_atom_coeff_sum_le_primitive
If an atom x in an additive subgroup M satisfies D * x = a * u + b * v with u, v ∈ M nonzero, nonnegative, and primitive, and a, b < D, then a + b ≤ D.
two_ray_nonnegative_sum_bound
If D * x = a * u + b * v with a + b ≤ D, D > 0, and nonnegativity conditions, and the coordinate sums of u and v are at most B ≥ 0, then the coordinate sum of x is at most 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 1000000set_option maxRecDepth 4000theorem integer_atom_sum_bound_of_two_primitive_rays {ι : Type*} [Fintype ι]    (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) (hv : v ≠ 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)    (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i)    (B : ℤ) (hB : 0 ≤ B) (hub : (∑ i, u i) ≤ B) (hvb : (∑ i, v i) ≤ B) :    (∑ i, x i) ≤ B := by  have hDz : (0 : ℤ) < D := by exact_mod_cast hD  by_cases ha : D ≤ a  · have hau : ∀ i, u i ≤ x i := by      intro i      have hai : (D : ℤ) ≤ a := by exact_mod_cast ha      have hh := mul_le_mul_of_nonneg_right hai (hu0 i)      have hbv : 0 ≤ (b : ℤ) * v i := mul_nonneg (Nat.cast_nonneg _) (hv0 i)      have hr := hrel i      nlinarith    have hx := (hmin u huM hu0 hau).resolve_left hu    simpa only [← hx] using hub  by_cases hb : D ≤ b  · have hav : ∀ i, v i ≤ x i := by      intro i      have hbi : (D : ℤ) ≤ b := by exact_mod_cast hb      have hh := mul_le_mul_of_nonneg_right hbi (hv0 i)      have hau : 0 ≤ (a : ℤ) * u i := mul_nonneg (Nat.cast_nonneg _) (hu0 i)      have hr := hrel i      nlinarith    have hx := (hmin v hvM hv0 hav).resolve_left hv    simpa only [← hx] using hvb  have hc := two_ray_integer_atom_coeff_sum_le_primitive M u v x huM hvM hxM hu0 hv0 hu    hmin hprimu hprimv D a b hD (by omega) (by omega) hrel  exact two_ray_nonnegative_sum_bound u v x D a b hD hc B hB hub hvb hrel
See it in the graphDiscuss this resultChallenge it