integer_atom_sum_bound_of_two_primitive_rays
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
- 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…
- two_ray_nonnegative_sum_boundFor finite integer-valued functions u,v,x and natural D,a,b with D positive and a+b at most D, if D*x=a*u+b*v coordinatewise and both u…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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.
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.
have hDz : (0 : ℤ) < D := by exact_mod_cast hD
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.
uses
mul_le_mul_of_nonneg_right,mul_nonneg,Nat.cast_nonneg,resolve_leftby_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
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.
uses
mul_le_mul_of_nonneg_right,mul_nonneg,Nat.cast_nonneg,resolve_leftby_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
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.
uses
two_ray_integer_atom_coeff_sum_le_primitivehave 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
∑ 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.
uses
two_ray_nonnegative_sum_boundexact 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
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 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