AFTD Auto-Formalizing Theoretical Domains

integer_positive_line_boundary_decomposition

theoremverified

For a strictly positive finite integer vector x and a mixed-sign integer direction w, explicit integer vectors u=w(i)x-x(i)w and v=x(j)w-w(j)x are nonnegative and nonzero, with u(i)=0,v(j)=0, and positive integers D,a,b (represented in Z) satisfy D*x=a*u+b*v. The displayed formulas are included in the conclusion.

Statement

theorem integer_positive_line_boundary_decomposition {ι : Type*} [Fintype ι]
    (x w : ι → ℤ) (hx : ∀ k, 0 < x k)
    (hp : ∃ i, 0 < w i) (hn : ∃ j, w j < 0) :
    ∃ (u v : ι → ℤ) (i j : ι) (D a b : ℤ),
      (∀ k, 0 ≤ u k) ∧ (∀ k, 0 ≤ v k) ∧ u ≠ 0 ∧ v ≠ 0 ∧
      u i = 0 ∧ v j = 0 ∧ 0 < D ∧ 0 < a ∧ 0 < b ∧
      (∀ k, D*x k = a*u k + b*v k) ∧
      u = (fun k => w i*x k - x i*w k) ∧
      v = (fun k => x j*w k - w j*x k)
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 3
  • integer_positive_line_boundary_indicesFor finite integer functions x,w with x strictly positive coordinatewise and w taking both positive and negative values, there are indices…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The theorem decomposes a strictly positive integer vector x along a mixed-sign direction w into a positive linear combination D * x = a * u + b * v of two nonzero nonnegative integer vectors u and v on the coordinate boundary. The proof first finds indices i and j where the ratio w / x attains its maximum and minimum values (with w i > 0 and w j < 0) via integer_positive_line_boundary_indices, and defines u k = w i * x k - x i * w k and v k = x j * w k - w j * x k. These vectors are nonnegative, vanish at i and j respectively, and are nonzero because their cross-components equal the positive determinant D = x j * w i - x i * w j. Finally, setting a = x j > 0 and b = x i > 0, the decomposition identity holds identically by polynomial cancellation of the w terms.

  1. Boundary indices i and j exist, and candidate vectors u and v are defined.

    Applying integer_positive_line_boundary_indices yields indices i, j with w i > 0 and w j < 0 such that x i * w k ≤ x k * w i and x k * w j ≤ x j * w k for all k. The candidate boundary vectors u and v are then defined pointwise as u k = w i * x k - x i * w k and v k = x j * w k - w j * x k.

    lines 14–16

    uses integer_positive_line_boundary_indices

      obtain ⟨i,j,hwi,hwj,hui,hvj⟩ := integer_positive_line_boundary_indices x w hx hp hn
      let u := fun k => w i*x k - x i*w k
      let v := fun k => x j*w k - w j*x k
  2. The integer determinant D = x j * w i - x i * w j is strictly positive.

    Since x j > 0 and w i > 0, their product x j * w i is positive by mul_pos. Since x i > 0 and w j < 0, their product x i * w j is negative by mul_neg_of_pos_of_neg. Subtracting a strictly negative integer from a strictly positive integer gives a strictly positive integer, which omega verifies.

    lines 17–20

    uses mul_pos, mul_neg_of_pos_of_neg

      have hD : 0 < x j*w i - x i*w j := by
        have hh1 := mul_pos (hx j) hwi
        have hh2 := mul_neg_of_pos_of_neg (hx i) hwj
        omega
  3. The vectors satisfy u i = 0, v j = 0, and cross-evaluate to u j = v i = x j * w i - x i * w j.

    Directly evaluating u at i yields w i * x i - x i * w i = 0, and evaluating v at j yields x j * w j - w j * x j = 0. Similarly, evaluating u at j gives w i * x j - x i * w j = x j * w i - x i * w j, and evaluating v at i gives x j * w i - w j * x i = x j * w i - x i * w j. Each equality simplifies by ring arithmetic.

    lines 21–24

      have hui0 : u i = 0 := by dsimp [u]; ring
      have hvj0 : v j = 0 := by dsimp [v]; ring
      have huj : u j = x j*w i - x i*w j := by dsimp [u]; ring
      have hvi : v i = x j*w i - x i*w j := by dsimp [v]; ring
  4. The vectors u and v are nonzero.

    If u = 0, evaluating at j using congrFun and Pi.zero_apply gives u j = 0, which means x j * w i - x i * w j = 0, contradicting D > 0. Similarly, if v = 0, evaluating at i yields v i = 0, which again contradicts D > 0.

    lines 25–26

    uses congrFun, Pi.zero_apply

      have hun : u ≠ 0 := by intro hh; have hh' := congrFun hh j; simp only [Pi.zero_apply] at hh'; rw [huj] at hh'; omega
      have hvn : v ≠ 0 := by intro hh; have hh' := congrFun hh i; simp only [Pi.zero_apply] at hh'; rw [hvi] at hh'; omega
  5. The witnesses u, v, i, j, D = x j * w i - x i * w j, a = x j, and b = x i satisfy the existential claim up to three remaining checks.

    We supply u, v, i, j, D = x j * w i - x i * w j, a = x j, and b = x i as witnesses. The conditions u ≠ 0, v ≠ 0, u i = 0, v j = 0, D > 0, a > 0 (since x j > 0), and b > 0 (since x i > 0) were proved above, while the equality of functions holds by reflexivity. This leaves three subgoals: nonnegativity of u, nonnegativity of v, and the linear decomposition formula.

    line 27

      refine ⟨u,v,i,j,x j*w i - x i*w j,x j,x i,?_,?_,hun,hvn,hui0,hvj0,hD,hx j,hx i,?_,rfl,rfl⟩
  6. The vector u is entrywise nonnegative: for all k, 0 ≤ u k.

    By definition, u k = w i * x k - x i * w k. The choice of index i ensures x i * w k ≤ x k * w i for all k, so subtracting x i * w k yields 0 ≤ w i * x k - x i * w k.

    line 28

      · intro k; dsimp [u]; have := hui k; nlinarith
  7. The vector v is entrywise nonnegative: for all k, 0 ≤ v k.

    By definition, v k = x j * w k - w j * x k. The choice of index j ensures x k * w j ≤ x j * w k for all k, so subtracting x k * w j yields 0 ≤ x j * w k - w j * x k.

    line 29

      · intro k; dsimp [v]; have := hvj k; nlinarith
  8. The linear decomposition D * x k = a * u k + b * v k holds for all k.

    Expanding the right-hand side with a = x j and b = x i gives x j * (w i * x k - x i * w k) + x i * (x j * w k - w j * x k) = (x j * w i - x i * w j) * x k + (x i * x j - x j * x i) * w k = (x j * w i - x i * w j) * x k = D * x k. The ring tactic confirms this polynomial identity.

    line 30

      · intro k; dsimp [u,v]; ring
integer_positive_line_boundary_indices
Given a strictly positive integer vector x and an integer vector w with both positive and negative entries, there exist indices i and j with w i > 0 and w j < 0 such that x i * w k ≤ x k * w i and x k * w j ≤ x j * w k for all k.
mul_pos
The product of two strictly positive elements in a strictly ordered semiring is strictly positive.
mul_neg_of_pos_of_neg
The product of a strictly positive element and a strictly negative element is strictly negative.
congrFun
If two functions are equal, then their values at any input are equal: f = g implies f a = g a.
Pi.zero_apply
Evaluating the zero function at any point gives zero: (0 : ι → M) i = 0.

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_positive_line_boundary_decomposition {ι : Type*} [Fintype ι]    (x w : ι → ℤ) (hx : ∀ k, 0 < x k)    (hp : ∃ i, 0 < w i) (hn : ∃ j, w j < 0) :    ∃ (u v : ι → ℤ) (i j : ι) (D a b : ℤ),      (∀ k, 0 ≤ u k) ∧ (∀ k, 0 ≤ v k) ∧ u ≠ 0 ∧ v ≠ 0 ∧      u i = 0 ∧ v j = 0 ∧ 0 < D ∧ 0 < a ∧ 0 < b ∧      (∀ k, D*x k = a*u k + b*v k) ∧      u = (fun k => w i*x k - x i*w k) ∧      v = (fun k => x j*w k - w j*x k) := by  obtain ⟨i,j,hwi,hwj,hui,hvj⟩ := integer_positive_line_boundary_indices x w hx hp hn  let u := fun k => w i*x k - x i*w k  let v := fun k => x j*w k - w j*x k  have hD : 0 < x j*w i - x i*w j := by    have hh1 := mul_pos (hx j) hwi    have hh2 := mul_neg_of_pos_of_neg (hx i) hwj    omega  have hui0 : u i = 0 := by dsimp [u]; ring  have hvj0 : v j = 0 := by dsimp [v]; ring  have huj : u j = x j*w i - x i*w j := by dsimp [u]; ring  have hvi : v i = x j*w i - x i*w j := by dsimp [v]; ring  have hun : u ≠ 0 := by intro hh; have hh' := congrFun hh j; simp only [Pi.zero_apply] at hh'; rw [huj] at hh'; omega  have hvn : v ≠ 0 := by intro hh; have hh' := congrFun hh i; simp only [Pi.zero_apply] at hh'; rw [hvi] at hh'; omega  refine ⟨u,v,i,j,x j*w i - x i*w j,x j,x i,?_,?_,hun,hvn,hui0,hvj0,hD,hx j,hx i,?_,rfl,rfl⟩  · intro k; dsimp [u]; have := hui k; nlinarith  · intro k; dsimp [v]; have := hvj k; nlinarith  · intro k; dsimp [u,v]; ring
See it in the graphDiscuss this resultChallenge it