AFTD Auto-Formalizing Theoretical Domains

nonnegative_integer_vector_primitive_factorization

theoremverified

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

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.

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

    lines 10–14

      classical
      have hex : ∃ i, u i ≠ 0 := by
        by_contra hh; push_neg at hh
        exact hne (funext hh)
      obtain ⟨i,hi⟩ := hex
  2. 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.

    lines 15–17

    uses Int.toNat_of_nonneg, Nat.cast_zero

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

    lines 18–19

    uses Finset.extract_gcd, Finset.mem_univ

      obtain ⟨v,hfac,hgcd⟩ := Finset.extract_gcd (s:=Finset.univ) f ⟨i,Finset.mem_univ i⟩
      let d := Finset.univ.gcd f
  4. 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.

    lines 20–26

    uses Finset.mem_univ, zero_mul

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

    lines 27–35

    uses Finset.mem_univ

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

    lines 36–43

    uses congrFun, Pi.zero_apply

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

    lines 44–45

    uses Nat.cast_nonneg

      refine ⟨d,z,hd,?_,hzne,hfacz,?_⟩
      · intro k; exact Nat.cast_nonneg _
  8. 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.

    lines 46–53

    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.

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