AFTD Auto-Formalizing Theoretical Domains

two_ray_nonnegative_sum_strict_bound

theoremverified

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

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.

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

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

    lines 14–16

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

    lines 17–19

    uses mul_lt_mul_of_pos_left, mul_le_mul_of_nonneg_left, Nat.cast_nonneg, mul_le_mul_of_nonneg_right

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

    line 20

      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.

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