AFTD Auto-Formalizing Theoretical Domains

integer_positive_line_boundary_indices

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 11–19

      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]⟩
  2. 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.

    lines 20–24

    uses Finset.mem_filter.mp

      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, ?_, ?_⟩
  3. 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.

    lines 25–31

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

    lines 32–34

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

    lines 35–42

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

    lines 43–45

    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.

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