carpool_delta_sum
For any integer threshold D : ℤ, integer discrepancies da db : ℤ satisfying da - db ≤ 29, and natural number k ≥ 1, the sum of delta_plus = db - (carpool_threshold_A D (k + 1) - carpool_threshold_A D k) and delta_minus = -da + (carpool_threshold_A D k - carpool_threshold_A D (k - 1)) is at least 1.
Statement
theorem carpool_delta_sum (D : ℤ) (da db : ℤ) (k : ℕ) (hk : 1 ≤ k) (hgap : da - db ≤ 29) : let delta_plus := db - (carpool_threshold_A D (k + 1) - carpool_threshold_A D k) let delta_minus := -da + (carpool_threshold_A D k - carpool_threshold_A D (k - 1)) delta_plus + delta_minus ≥ 1
- Source
- arXiv:2611.00388 Eq. (4.4)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- carpool_threshold_AThe quadratic threshold function carpool_threshold_A taking an integer parameter D : ℤ and a natural number k : ℕ, defined as the integer…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- carpool_backward_step_slack_increaseFor natural numbers n and T, an integer D, trajectory d : ℕ → Fin n → ℤ, and receiver/sender functions a, b : ℕ → Fin n satisfying for all…
Read back from the Lean
For any integers $D$, $da$, and $db$, and any natural number $k$ such that $1 \le k$ and $da - db \le 29$, defining $$\delta_{\text{plus}} = db - (\text{carpool\_threshold\_A}(D, k + 1) - \text{carpool\_threshold\_A}(D, k))$$ and $$\delta_{\text{minus}} = -da + (\text{carpool\_threshold\_A}(D, k) - \text{carpool\_threshold\_A}(D, k - 1)),$$ the inequality $\delta_{\text{plus}} + \delta_{\text{minus}} \ge 1$ holds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof computes the sum delta_plus + delta_minus by directly expanding the quadratic threshold formula carpool_threshold_A(D, k) = k * D - 15 * k * (k - 1). Because the second finite difference of this quadratic function is constant, both the threshold parameter D and the index k cancel out completely, reducing delta_plus + delta_minus to 30 + db - da. The receiving gap hypothesis da - db ≤ 29 then immediately implies that this sum is at least 1.
Express k as m + 1 for some natural number m.
Since k ≥ 1 (hk), we write k = m + 1 where m = k - 1 using Nat.sub_add_cancel. This re-indexes k to avoid truncated natural number subtraction when evaluating k - 1.
uses
Nat.sub_add_cancelobtain ⟨m, rfl⟩ : ∃ m : ℕ, k = m + 1 := ⟨k - 1, (Nat.sub_add_cancel hk).symm⟩
The expression delta_plus + delta_minus simplifies to 30 + db - da.
Unfolding the definition of carpool_threshold_A replaces each term with (n : ℤ) * D - 15 * (n : ℤ) * (n - 1). Ring normalization (`ring_nf`) expands and simplifies the resulting polynomial: the parameter D and the step index m cancel out completely because the second discrete difference of the quadratic sequence is the constant -30, reducing the goal to 30 + db - da ≥ 1.
dsimp [carpool_threshold_A] ring_nf
The inequality 30 + db - da ≥ 1 holds.
The assumption da - db ≤ 29 (hgap) rearranges to db - da ≥ -29, which means 30 + db - da ≥ 30 - 29 = 1. Linear arithmetic (`linarith`) closes the goal.
linarith
Nat.sub_add_cancel- For natural numbers m ≤ n, (n - m) + m = n.
- The cancellation of the threshold parameter D and index m is carried out algebraically by `ring_nf`, which evaluates the constant second difference of the quadratic threshold sequence.
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.
/-- The sum of gains Delta_+ and Delta_- along a crossing edge is at least 1 when the receiving gap is at most 29. -/theorem carpool_delta_sum (D : ℤ) (da db : ℤ) (k : ℕ) (hk : 1 ≤ k) (hgap : da - db ≤ 29) : let delta_plus := db - (carpool_threshold_A D (k + 1) - carpool_threshold_A D k) let delta_minus := -da + (carpool_threshold_A D k - carpool_threshold_A D (k - 1)) delta_plus + delta_minus ≥ 1 := by obtain ⟨m, rfl⟩ : ∃ m : ℕ, k = m + 1 := ⟨k - 1, (Nat.sub_add_cancel hk).symm⟩ dsimp [carpool_threshold_A] ring_nf linarith