AFTD Auto-Formalizing Theoretical Domains

two_ray_nonnegative_sum_bound

theoremverified

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

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

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

    lines 10–13

    uses mul_sum, sum_add_distrib, sum_congr

      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)
  2. 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`.

    lines 14–15

      have hDz : (0 : ℤ) < D := by exact_mod_cast hD
      have hc : (a : ℤ)+(b : ℤ) ≤ D := by exact_mod_cast hcoeff
  3. $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`.

    lines 16–18

    uses mul_le_mul_of_nonneg_left, Nat.cast_nonneg, mul_le_mul_of_nonneg_right

      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
  4. $\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.

    line 19

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

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