nonnegative_integer_vector_primitive_factorization
Every nonzero nonnegative finite integer vector u equals d*v coordinatewise for a positive natural d and a nonzero nonnegative integer vector v whose only common natural coordinate divisors divide one.
Statement
theorem nonnegative_integer_vector_primitive_factorization {ι : Type*} [Fintype ι] (u : ι → ℤ) (hu : ∀ i, 0 ≤ u i) (hne : u ≠ 0) : ∃ (d : ℕ) (v : ι → ℤ), 0 < d ∧ (∀ i, 0 ≤ v i) ∧ v ≠ 0 ∧ (∀ i, u i = (d : ℤ)*v i) ∧ (∀ e : ℕ, (∀ i, (e : ℤ) ∣ v i) → e ∣ 1)
- 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- Used by 1
- four_point_positive_kernel_primitive_boundary_decompositionFor two integer rows on four coordinates with independent first two columns and a strictly positive integer common kernel vector x, there…
The proof, explained
Since u is a nonzero nonnegative integer vector over a finite index type, it can be viewed as a nonzero vector of natural numbers. Applying `Finset.extract_gcd` extracts the greatest common divisor d = gcd(u), which is strictly positive, and yields a natural vector v with gcd(v) = 1 such that u = d * v. Casting v back to an integer vector provides the desired primitive, nonzero, nonnegative vector factorisation.
There exists an index i where u i ≠ 0.
Since u is nonzero by hypothesis, its coordinates cannot all be zero; if they were, function extensionality would imply u = 0, a contradiction.
classical have hex : ∃ i, u i ≠ 0 := by by_contra hh; push_neg at hh exact hne (funext hh) obtain ⟨i,hi⟩ := hex
The vector u corresponds coordinatewise to a natural vector f, with f i ≠ 0 at the nonzero coordinate.
Defining f by f(k) = (u(k)).toNat, the nonnegativity hypothesis 0 ≤ u(k) ensures that casting f(k) to an integer recovers u(k) (Int.toNat_of_nonneg). If f(i) were zero, its cast would be zero (Nat.cast_zero), contradicting u(i) ≠ 0.
uses
Int.toNat_of_nonneg,Nat.cast_zerolet f := fun i => (u i).toNat have hfu : ∀ i, (f i : ℤ) = u i := by intro i; exact Int.toNat_of_nonneg (hu i) have hfi : f i ≠ 0 := by intro hh; have hh' := hfu i; rw [hh] at hh'; simp only [Nat.cast_zero] at hh'; exact hi hh'.symm
The natural vector f factors as f(k) = d * v(k) with d = gcd(f) and gcd(v) = 1.
Because the index type is finite and nonempty (witnessed by the index i in Finset.mem_univ), Finset.extract_gcd factors f into its greatest common divisor d = gcd(f) and a natural vector v whose coordinates have greatest common divisor 1.
uses
Finset.extract_gcd,Finset.mem_univobtain ⟨v,hfac,hgcd⟩ := Finset.extract_gcd (s:=Finset.univ) f ⟨i,Finset.mem_univ i⟩ let d := Finset.univ.gcd f
The greatest common divisor d is strictly positive (0 < d).
If d were zero, then at coordinate i we would have f(i) = d * v(i) = 0 * v(i) = 0 by zero_mul, contradicting f(i) ≠ 0.
uses
Finset.mem_univ,zero_mulhave hd : 0 < d := by have hh := hfac i (Finset.mem_univ i) by_contra hn have hz : d=0 := by omega change f i=d*v i at hh rw [hz,zero_mul] at hh exact hfi hh
Casting v to an integer vector z factors u coordinatewise as u(k) = d * z(k).
Setting z(k) = (v(k) : ℤ), the equality f(k) = d * v(k) in ℕ casts to (f(k) : ℤ) = d * z(k) in ℤ. Since (f(k) : ℤ) = u(k), this gives u(k) = d * z(k) for all coordinates.
uses
Finset.mem_univlet z := fun i => (v i : ℤ) have hfacz : ∀ i, u i=(d : ℤ)*z i := by intro k have hh := hfac k (Finset.mem_univ k) have hh' : (f k : ℤ)=(d : ℤ)*z k := by change (f k : ℤ)=(d : ℤ)*(v k : ℤ) change f k=d*v k at hh exact_mod_cast hh rwa [hfu k] at hh'
The integer vector z is nonzero.
If z were zero, evaluating at each coordinate k would give z(k) = 0 (congrFun, Pi.zero_apply), so u(k) = d * 0 = 0 for all k. Hence u = 0, contradicting the assumption u ≠ 0.
uses
congrFun,Pi.zero_applyhave hzne : z ≠ 0 := by intro hh apply hne funext k have hk := hfacz k have hzk := congrFun hh k simp only [Pi.zero_apply] at hzk simpa [hzk] using hk
The witnesses d and z satisfy nonnegativity: 0 ≤ z(k) for all coordinates k.
We instantiate the existential goal with d and z, providing the already established facts 0 < d, z ≠ 0, and u = d * z. Nonnegativity holds because each z(k) is the cast of a natural number v(k) (Nat.cast_nonneg).
uses
Nat.cast_nonnegrefine ⟨d,z,hd,?_,hzne,hfacz,?_⟩ · intro k; exact Nat.cast_nonneg _
Every common natural divisor of the coordinates of z divides 1.
If a natural number e divides each z(k) as an integer, then e divides v(k) in ℕ. By Finset.dvd_gcd, e divides the GCD of v over the universe. Since gcd(v) = 1 by construction, e divides 1.
uses
Finset.dvd_gcd· intro e he have hdiv : e ∣ Finset.univ.gcd v := by apply Finset.dvd_gcd intro k hk have hh := he k change (e : ℤ) ∣ (v k : ℤ) at hh exact_mod_cast hh simpa only [hgcd] using hdiv
Int.toNat_of_nonneg- For any integer a ≥ 0, casting its conversion to a natural number back to ℤ yields a.
Nat.cast_zero- The cast of 0 ∈ ℕ into an additive monoid with one is 0.
Finset.extract_gcd- For a function from a nonempty finite set into a GCD monoid, one can extract the overall GCD, factoring the function into this GCD times a function whose values have GCD 1.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
zero_mul- Multiplying zero by any element on the left yields zero (0 * a = 0).
congrFun- Equal functions produce equal values on the same argument (f = g implies f(a) = g(a)).
Pi.zero_apply- Evaluating the zero function at any point yields zero (0(i) = 0).
Nat.cast_nonneg- The cast of any natural number into an ordered semiring is nonnegative.
Finset.dvd_gcd- If an element divides the value of a function at every point of a finite set, it divides the GCD of those values.
- The proof works primarily in `ℕ` to take advantage of GCD monoid results on finite sets, relying on `exact_mod_cast` to translate divisibility and factorisation between `ℕ` and `ℤ`.
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 nonnegative_integer_vector_primitive_factorization {ι : Type*} [Fintype ι] (u : ι → ℤ) (hu : ∀ i, 0 ≤ u i) (hne : u ≠ 0) : ∃ (d : ℕ) (v : ι → ℤ), 0 < d ∧ (∀ i, 0 ≤ v i) ∧ v ≠ 0 ∧ (∀ i, u i = (d : ℤ)*v i) ∧ (∀ e : ℕ, (∀ i, (e : ℤ) ∣ v i) → e ∣ 1) := by classical have hex : ∃ i, u i ≠ 0 := by by_contra hh; push_neg at hh exact hne (funext hh) obtain ⟨i,hi⟩ := hex let f := fun i => (u i).toNat have hfu : ∀ i, (f i : ℤ) = u i := by intro i; exact Int.toNat_of_nonneg (hu i) have hfi : f i ≠ 0 := by intro hh; have hh' := hfu i; rw [hh] at hh'; simp only [Nat.cast_zero] at hh'; exact hi hh'.symm obtain ⟨v,hfac,hgcd⟩ := Finset.extract_gcd (s:=Finset.univ) f ⟨i,Finset.mem_univ i⟩ let d := Finset.univ.gcd f have hd : 0 < d := by have hh := hfac i (Finset.mem_univ i) by_contra hn have hz : d=0 := by omega change f i=d*v i at hh rw [hz,zero_mul] at hh exact hfi hh let z := fun i => (v i : ℤ) have hfacz : ∀ i, u i=(d : ℤ)*z i := by intro k have hh := hfac k (Finset.mem_univ k) have hh' : (f k : ℤ)=(d : ℤ)*z k := by change (f k : ℤ)=(d : ℤ)*(v k : ℤ) change f k=d*v k at hh exact_mod_cast hh rwa [hfu k] at hh' have hzne : z ≠ 0 := by intro hh apply hne funext k have hk := hfacz k have hzk := congrFun hh k simp only [Pi.zero_apply] at hzk simpa [hzk] using hk refine ⟨d,z,hd,?_,hzne,hfacz,?_⟩ · intro k; exact Nat.cast_nonneg _ · intro e he have hdiv : e ∣ Finset.univ.gcd v := by apply Finset.dvd_gcd intro k hk have hh := he k change (e : ℤ) ∣ (v k : ℤ) at hh exact_mod_cast hh simpa only [hgcd] using hdiv