two_ray_nonnegative_sum_strict_bound
Under the same weighted two-ray relation, with D and a positive, a+b at most D, B nonnegative, the coordinate sum of u strictly less than B and the coordinate sum of v at most B, the coordinate sum of x is strictly less than B.
Statement
theorem two_ray_nonnegative_sum_strict_bound {ι : Type*} [Fintype ι] (u v x : ι → ℤ) (D a b : ℕ) (hD : 0 < D) (ha : 0 < a) (hcoeff : a+b ≤ D) (B : ℤ) (hB : 0 ≤ B) (hu : (∑ i, u i) < B) (hv : (∑ i, v i) ≤ B) (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) : (∑ i, x i) < B
- Source
- Helper for OP-197 / arXiv:2610.16562 Conjecture1, continuing the already verified two_ray_integer_atom_coeff_sum_le from deep session1. This closes primitive-ray denominator normalization and weighted length bookkeeping, not extraction of the two circuit rays or the box conjecture. No research advance claimed.
- 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
The proof, explained
Summing the coordinate-wise relation D * x i = a * u i + b * v i over all indices expresses D * ∑ x i as a positive linear combination a * ∑ u i + b * ∑ v i. Weighting the bounds ∑ u i < B and ∑ v i ≤ B by a > 0 and b ≥ 0 shows D * ∑ x i < (a + b) * B. Since a + b ≤ D and B ≥ 0, this is bounded by D * B, from which dividing by D > 0 yields the strict bound ∑ x i < B.
D * (∑ i, x i) = a * (∑ i, u i) + b * (∑ i, v i)
Summing the coordinate-wise relation D * x i = a * u i + b * v i over all indices gives ∑ i, D * x i = ∑ i, (a * u i + b * v i) by sum_congr. Distributing the sum over addition with sum_add_distrib and factoring out the scalars D, a, and b using mul_sum yields the identity relating the total coordinate sums.
uses
mul_sum,sum_add_distrib,sum_congrhave hsum : (D : ℤ) * (∑ i, x i) = (a : ℤ) * (∑ i, u i) + (b : ℤ) * (∑ i, v i) := by simp only [mul_sum, ← sum_add_distrib] exact sum_congr rfl (fun i _ => hrel i)
The bounds 0 < D, 0 < a, and a + b ≤ D hold for the integer casts of D, a, and b.
The hypotheses hD (0 < D), ha (0 < a), and hcoeff (a + b ≤ D) on natural numbers are cast into the integers using exact_mod_cast to prepare for integer arithmetic.
have hDz : (0 : ℤ) < D := by exact_mod_cast hD have haz : (0 : ℤ) < a := by exact_mod_cast ha have hc : (a : ℤ)+(b : ℤ) ≤ D := by exact_mod_cast hcoeff
a * (∑ i, u i) < a * B, b * (∑ i, v i) ≤ b * B, and (a + b) * B ≤ D * B
Multiplying the strict bound ∑ i, u i < B on the left by a > 0 yields a * (∑ i, u i) < a * B via mul_lt_mul_of_pos_left. Since b ≥ 0 in ℤ (by Nat.cast_nonneg), multiplying ∑ i, v i ≤ B on the left by b preserves the weak inequality to give b * (∑ i, v i) ≤ b * B via mul_le_mul_of_nonneg_left. Finally, multiplying a + b ≤ D on the right by B ≥ 0 yields (a + b) * B ≤ D * B via mul_le_mul_of_nonneg_right.
uses
mul_lt_mul_of_pos_left,mul_le_mul_of_nonneg_left,Nat.cast_nonneg,mul_le_mul_of_nonneg_righthave hu' := mul_lt_mul_of_pos_left hu haz have hv' := mul_le_mul_of_nonneg_left hv (Nat.cast_nonneg b : (0 : ℤ) ≤ b) have hm := mul_le_mul_of_nonneg_right hc hB
∑ i, x i < B automation
Combining the sum identity with the scaled inequalities yields D * (∑ i, x i) = a * (∑ i, u i) + b * (∑ i, v i) < a * B + b * B = (a + b) * B ≤ D * B. Dividing through by D > 0 gives ∑ i, x i < B; the nlinarith tactic completes this nonlinear integer arithmetic deduction automatically.
nlinarith
mul_sum- Multiplication distributes over a finite sum from the left: a ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
sum_add_distrib- A finite sum of two functions splits into the sum of the individual sums: ∑ i ∈ s, (f i + g i) = ∑ i ∈ s, f i + ∑ i ∈ s, g i.
sum_congr- If two index sets are equal and the summands agree pointwise on the set, then the finite sums are equal.
mul_lt_mul_of_pos_left- Multiplying a strict inequality b < c on the left by a strictly positive element a > 0 preserves the strict inequality: a * b < a * c.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative element a ≥ 0 preserves the inequality: a * b ≤ a * c.
Nat.cast_nonneg- The canonical injection of any natural number into an ordered ring is non-negative: 0 ≤ (n : ℤ).
mul_le_mul_of_nonneg_right- Multiplying an inequality b ≤ c on the right by a non-negative element a ≥ 0 preserves the inequality: b * a ≤ c * a.
- Casting hypotheses from ℕ to ℤ via `exact_mod_cast` is formal bookkeeping required because Lean distinguishes between natural numbers and integers.
- The final deduction is handled by `nlinarith`, which automates nonlinear integer arithmetic to combine the inequalities and divide by D > 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 two_ray_nonnegative_sum_strict_bound {ι : Type*} [Fintype ι] (u v x : ι → ℤ) (D a b : ℕ) (hD : 0 < D) (ha : 0 < a) (hcoeff : a+b ≤ D) (B : ℤ) (hB : 0 ≤ B) (hu : (∑ i, u i) < B) (hv : (∑ i, v i) ≤ B) (hrel : ∀ i, (D : ℤ) * x i = (a : ℤ) * u i + (b : ℤ) * v i) : (∑ i, x i) < B := by have hsum : (D : ℤ) * (∑ i, x i) = (a : ℤ) * (∑ i, u i) + (b : ℤ) * (∑ i, v i) := by simp only [mul_sum, ← sum_add_distrib] exact sum_congr rfl (fun i _ => hrel i) have hDz : (0 : ℤ) < D := by exact_mod_cast hD have haz : (0 : ℤ) < a := by exact_mod_cast ha have hc : (a : ℤ)+(b : ℤ) ≤ D := by exact_mod_cast hcoeff have hu' := mul_lt_mul_of_pos_left hu haz have hv' := mul_le_mul_of_nonneg_left hv (Nat.cast_nonneg b : (0 : ℤ) ≤ b) have hm := mul_le_mul_of_nonneg_right hc hB nlinarith