integer_positive_line_boundary_indices
For finite integer functions x,w with x strictly positive coordinatewise and w taking both positive and negative values, there are indices i,j with w(i)>0,w(j)<0 such that x(i)w(k)<=x(k)w(i) and x(k)w(j)<=x(j)w(k) for every k. These are the two first boundary positions along the line through x in direction w.
Statement
theorem integer_positive_line_boundary_indices {ι : Type*} [Fintype ι] (x w : ι → ℤ) (hx : ∀ k, 0 < x k) (hp : ∃ i, 0 < w i) (hn : ∃ j, w j < 0) : ∃ i j, 0 < w i ∧ w j < 0 ∧ (∀ k, x i * w k ≤ x k * w i) ∧ (∀ k, x k * w j ≤ x j * w 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 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- integer_positive_line_boundary_decompositionFor 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…
The proof, explained
The proof constructs the indices i and j by minimizing ratios over finite nonempty sets. We partition the indices into P where w is positive and N where w is negative; each set is nonempty by assumption. Over the rationals, we select i ∈ P to minimize x(k)/w(k) and j ∈ N to minimize x(k)/(-w(k)). For any coordinate k, the required cross-multiplication inequalities follow by clearing denominators when w(k) shares the sign, and by transitivity through 0 when w(k) has the opposite sign or vanishes.
The index sets P = {k | w(k) > 0} and N = {k | w(k) < 0} are nonempty finite sets.
We define P as the finite set of indices where w is strictly positive, and N as the finite set where w is strictly negative. The hypotheses that w takes at least one positive value and at least one negative value immediately provide witnesses showing that P and N are nonempty.
classical let P := Finset.univ.filter (fun i => 0 < w i) let N := Finset.univ.filter (fun j => w j < 0) have hP : P.Nonempty := by rcases hp with ⟨i, hi⟩ exact ⟨i, by simp [P, hi]⟩ have hN : N.Nonempty := by rcases hn with ⟨j, hj⟩ exact ⟨j, by simp [N, hj]⟩
There exist indices i ∈ P and j ∈ N minimizing the rational ratios x(k)/w(k) and x(k)/(-w(k)), respectively.
Since P and N are finite and nonempty, the rational functions k ↦ x(k)/w(k) on P and k ↦ x(k)/(-w(k)) on N attain their minimum values at some indices i ∈ P and j ∈ N. By definition of P and N, w(i) > 0 and w(j) < 0. Providing i and j as the required witnesses reduces the goal to verifying the two cross-multiplication inequalities for an arbitrary index k.
uses
Finset.mem_filter.mpobtain ⟨i, hi, hmini⟩ := P.exists_min_image (fun k => (x k : ℚ) / (w k : ℚ)) hP obtain ⟨j, hj, hminj⟩ := N.exists_min_image (fun k => (x k : ℚ) / (-(w k : ℚ))) hN have hwi : 0 < w i := (Finset.mem_filter.mp hi).2 have hwj : w j < 0 := (Finset.mem_filter.mp hj).2 refine ⟨i, j, hwi, hwj, ?_, ?_⟩
For any index k with w(k) > 0, the inequality x(i) * w(k) ≤ x(k) * w(i) holds.
When w(k) > 0, k belongs to P, so by the minimality of i we have x(i)/w(i) ≤ x(k)/w(k) in ℚ. Since both denominators w(i) and w(k) are strictly positive rationals, div_le_div_iff₀ allows clearing denominators to obtain x(i) * w(k) ≤ x(k) * w(i) in ℚ, which casts back to the integers.
uses
div_le_div_iff₀· intro k by_cases hk : 0 < w k · have hm := hmini k (by simp [P, hk]) have hwiq : (0 : ℚ) < w i := by exact_mod_cast hwi have hwkq : (0 : ℚ) < w k := by exact_mod_cast hk have hh := (div_le_div_iff₀ hwiq hwkq).mp hm exact_mod_cast hh
For any index k with w(k) ≤ 0, the inequality x(i) * w(k) ≤ x(k) * w(i) holds.
When w(k) ≤ 0, the product x(i) * w(k) is nonpositive because x(i) > 0 and w(k) ≤ 0 (using mul_nonpos_of_nonneg_of_nonpos and le_of_lt). Meanwhile, x(k) * w(i) is nonnegative because x(k) > 0 and w(i) > 0 (using mul_nonneg and le_of_lt). Linear integer arithmetic (omega) closes the goal by transitivity through 0: x(i) * w(k) ≤ 0 ≤ x(k) * w(i).
uses
mul_nonpos_of_nonneg_of_nonpos,le_of_lt,mul_nonneg· have hm : x i * w k ≤ 0 := mul_nonpos_of_nonneg_of_nonpos (le_of_lt (hx i)) (by omega) have hm2 : 0 ≤ x k * w i := mul_nonneg (le_of_lt (hx k)) (le_of_lt hwi) omega
For any index k with w(k) < 0, the inequality x(k) * w(j) ≤ x(j) * w(k) holds.
When w(k) < 0, k belongs to N, so by the minimality of j we have x(j)/(-w(j)) ≤ x(k)/(-w(k)) in ℚ. Since w(j) < 0 and w(k) < 0, their negations -w(j) and -w(k) are strictly positive (by neg_pos.mpr). Clearing denominators with div_le_div_iff₀ yields x(j) * (-w(k)) ≤ x(k) * (-w(j)), which rearranges by linear arithmetic (nlinarith) to x(k) * w(j) ≤ x(j) * w(k) in ℚ and casts to the integers.
uses
neg_pos.mpr,div_le_div_iff₀· intro k by_cases hk : w k < 0 · have hm := hminj k (by simp [N, hk]) have hwjq : (0 : ℚ) < -(w j : ℚ) := by exact_mod_cast (neg_pos.mpr hwj) have hwkq : (0 : ℚ) < -(w k : ℚ) := by exact_mod_cast (neg_pos.mpr hk) have hh := (div_le_div_iff₀ hwjq hwkq).mp hm have hh' : (x k : ℚ) * w j ≤ (x j : ℚ) * w k := by nlinarith exact_mod_cast hh'
For any index k with w(k) ≥ 0, the inequality x(k) * w(j) ≤ x(j) * w(k) holds.
When w(k) ≥ 0, the product x(k) * w(j) is nonpositive because x(k) > 0 and w(j) < 0 (using mul_nonpos_of_nonneg_of_nonpos and le_of_lt). Meanwhile, x(j) * w(k) is nonnegative because x(j) > 0 and w(k) ≥ 0 (using mul_nonneg and le_of_lt). Linear integer arithmetic (omega) closes the goal by transitivity through 0: x(k) * w(j) ≤ 0 ≤ x(j) * w(k).
uses
mul_nonpos_of_nonneg_of_nonpos,le_of_lt,mul_nonneg· have hm : x k * w j ≤ 0 := mul_nonpos_of_nonneg_of_nonpos (le_of_lt (hx k)) (le_of_lt hwj) have hm2 : 0 ≤ x j * w k := mul_nonneg (le_of_lt (hx j)) (by omega) omega
Finset.mem_filter.mp- An element belongs to a filtered finite set only if it belongs to the original set and satisfies the filtering predicate.
div_le_div_iff₀- For fractions with strictly positive denominators in a linearly ordered field, a / b ≤ c / d holds if and only if a * d ≤ c * b.
mul_nonpos_of_nonneg_of_nonpos- The product of a nonnegative element and a nonpositive element is nonpositive.
le_of_lt- Strict inequality implies non-strict inequality.
mul_nonneg- The product of two nonnegative elements is nonnegative.
neg_pos.mpr- If an element is strictly negative, its negation is strictly positive.
- Because division is not defined over the integers ℤ, the ratios x(k)/w(k) and x(k)/(-w(k)) are computed in the rational numbers ℚ, and the results are cast between ℤ and ℚ via exact_mod_cast.
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_indices {ι : Type*} [Fintype ι] (x w : ι → ℤ) (hx : ∀ k, 0 < x k) (hp : ∃ i, 0 < w i) (hn : ∃ j, w j < 0) : ∃ i j, 0 < w i ∧ w j < 0 ∧ (∀ k, x i * w k ≤ x k * w i) ∧ (∀ k, x k * w j ≤ x j * w k) := by classical let P := Finset.univ.filter (fun i => 0 < w i) let N := Finset.univ.filter (fun j => w j < 0) have hP : P.Nonempty := by rcases hp with ⟨i, hi⟩ exact ⟨i, by simp [P, hi]⟩ have hN : N.Nonempty := by rcases hn with ⟨j, hj⟩ exact ⟨j, by simp [N, hj]⟩ obtain ⟨i, hi, hmini⟩ := P.exists_min_image (fun k => (x k : ℚ) / (w k : ℚ)) hP obtain ⟨j, hj, hminj⟩ := N.exists_min_image (fun k => (x k : ℚ) / (-(w k : ℚ))) hN have hwi : 0 < w i := (Finset.mem_filter.mp hi).2 have hwj : w j < 0 := (Finset.mem_filter.mp hj).2 refine ⟨i, j, hwi, hwj, ?_, ?_⟩ · intro k by_cases hk : 0 < w k · have hm := hmini k (by simp [P, hk]) have hwiq : (0 : ℚ) < w i := by exact_mod_cast hwi have hwkq : (0 : ℚ) < w k := by exact_mod_cast hk have hh := (div_le_div_iff₀ hwiq hwkq).mp hm exact_mod_cast hh · have hm : x i * w k ≤ 0 := mul_nonpos_of_nonneg_of_nonpos (le_of_lt (hx i)) (by omega) have hm2 : 0 ≤ x k * w i := mul_nonneg (le_of_lt (hx k)) (le_of_lt hwi) omega · intro k by_cases hk : w k < 0 · have hm := hminj k (by simp [N, hk]) have hwjq : (0 : ℚ) < -(w j : ℚ) := by exact_mod_cast (neg_pos.mpr hwj) have hwkq : (0 : ℚ) < -(w k : ℚ) := by exact_mod_cast (neg_pos.mpr hk) have hh := (div_le_div_iff₀ hwjq hwkq).mp hm have hh' : (x k : ℚ) * w j ≤ (x j : ℚ) * w k := by nlinarith exact_mod_cast hh' · have hm : x k * w j ≤ 0 := mul_nonpos_of_nonneg_of_nonpos (le_of_lt (hx k)) (le_of_lt hwj) have hm2 : 0 ≤ x j * w k := mul_nonneg (le_of_lt (hx j)) (by omega) omega