integer_positive_line_boundary_decomposition
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- four_point_positive_kernel_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
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.
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.
uses
integer_positive_line_boundary_indicesobtain ⟨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
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.
uses
mul_pos,mul_neg_of_pos_of_neghave 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
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.
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
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.
uses
congrFun,Pi.zero_applyhave 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
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.
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⟩
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.
· intro k; dsimp [u]; have := hui k; nlinarith
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.
· intro k; dsimp [v]; have := hvj k; nlinarith
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.
· 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
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_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