two_ray_nonnegative_sum_bound
For finite integer-valued functions u,v,x and natural D,a,b with D positive and a+b at most D, if D*x=a*u+b*v coordinatewise and both u and v have coordinate sum at most B, where B is a nonnegative integer, then x has coordinate sum at most B.
Statement
theorem two_ray_nonnegative_sum_bound {ι : Type*} [Fintype ι] (u v x : ι → ℤ) (D a b : ℕ) (hD : 0 < D) (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
- Used by 1
- integer_atom_sum_bound_of_two_primitive_raysIn an additive subgroup of finite integer vectors, an element with no proper nonzero nonnegative subgroup subvector has coordinate sum at…
The proof, explained
Summing the coordinatewise identity $D x_i = a u_i + b v_i$ over all indices yields $D \sum_i x_i = a \sum_i u_i + b \sum_i v_i$. Since $a, b \ge 0$ and both coordinate sums are bounded by $B$, this sum is bounded above by $(a + b) B$. Finally, because $a + b \le D$ and $B \ge 0$, we have $(a + b) B \le D B$, and dividing through by $D > 0$ yields the desired bound $\sum_i x_i \le B$.
$D \sum_{i} x_i = a \sum_{i} u_i + b \sum_{i} v_i$
Distribute multiplication inside each sum using `mul_sum` and combine the two sums on the right into a single sum using `sum_add_distrib`. The resulting sums $\sum_i D x_i$ and $\sum_i (a u_i + b v_i)$ are equal by `sum_congr` because their terms agree coordinatewise by hypothesis `hrel`.
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 inequalities $0 < D$ and $a + b \le D$ hold in $\mathbb{Z}$.
Cast the given natural number inequalities $0 < D$ and $a + b \le D$ to integers via `exact_mod_cast`.
have hDz : (0 : ℤ) < D := by exact_mod_cast hD have hc : (a : ℤ)+(b : ℤ) ≤ D := by exact_mod_cast hcoeff
$a \sum_i u_i \le a B$, $b \sum_i v_i \le b B$, and $(a + b) B \le D B$
Because $a$ and $b$ are nonnegative integers (by `Nat.cast_nonneg`), multiplying the coordinate sum bounds $\sum_i u_i \le B$ and $\sum_i v_i \le B$ by $a$ and $b$ respectively gives $a \sum_i u_i \le a B$ and $b \sum_i v_i \le b B$ by `mul_le_mul_of_nonneg_left`. Multiplying the inequality $a + b \le D$ on the right by $B \ge 0$ gives $(a + b) B \le D B$ by `mul_le_mul_of_nonneg_right`.
uses
mul_le_mul_of_nonneg_left,Nat.cast_nonneg,mul_le_mul_of_nonneg_righthave hu' := mul_le_mul_of_nonneg_left hu (Nat.cast_nonneg a : (0 : ℤ) ≤ a) 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
$\sum_{i} x_i \le B$
Chaining the relations gives $D \sum_i x_i = a \sum_i u_i + b \sum_i v_i \le a B + b B = (a + b) B \le D B$. Since $D > 0$, dividing by $D$ yields $\sum_i x_i \le B$. The tactic `nlinarith` discharges this nonlinear integer arithmetic deduction directly.
nlinarith
mul_sum- Multiplication distributes over a finite sum: $c \sum_{i \in s} f(i) = \sum_{i \in s} c f(i)$.
sum_add_distrib- The sum of two functions over a finite set equals the sum of the two sums: $\sum_{i \in s} (f(i) + g(i)) = \sum_{i \in s} f(i) + \sum_{i \in s} g(i)$.
sum_congr- Two sums over identical finite sets are equal if their summands agree at every element.
mul_le_mul_of_nonneg_left- Multiplying an inequality $b \le c$ on the left by a nonnegative element $a \ge 0$ preserves the inequality: $a b \le a c$.
Nat.cast_nonneg- The coercion of any natural number into an ordered ring is nonnegative ($0 \le n$).
mul_le_mul_of_nonneg_right- Multiplying an inequality $b \le c$ on the right by a nonnegative element $a \ge 0$ preserves the inequality: $b a \le c a$.
- The natural number hypotheses $0 < D$ and $a + b \le D$ are coerced to integers using `exact_mod_cast` before being combined algebraically.
- The final deduction is performed by `nlinarith`, which automates the linear and nonlinear integer arithmetic combining the bounds and dividing 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_bound {ι : Type*} [Fintype ι] (u v x : ι → ℤ) (D a b : ℕ) (hD : 0 < D) (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 hc : (a : ℤ)+(b : ℤ) ≤ D := by exact_mod_cast hcoeff have hu' := mul_le_mul_of_nonneg_left hu (Nat.cast_nonneg a : (0 : ℤ) ≤ a) 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