graph_idle_special_cost_lt_one
If a = b, b = c + 2 and d_y = b + c + 1, then 1/2 + 2(a−1)·(1/2)/d_y < 1.
Statement
theorem graph_idle_special_cost_lt_one
(a b c dy : ℕ) (ha : a = b) (hb : b = c + 2) (hdy : dy = b + c + 1) :
(1:ℝ)/2 + 2*((a:ℝ) - 1)*((1/2)/(dy:ℝ)) < 1- Source
- step towards exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_edge_partition_cardWith the four-part partition of V induced by an edge xy: deg x = |A| + |C| + 1, deg y = |B| + |C| + 1, and |V| = 2 + |A| + |B| + |C| + |P|.
- Used by 2
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- graph_idle_wasserstein_lt_one_of_edge_partitionGiven the edge partition of a graph of diameter at most 2 whose minimum degree is at least 2n/3 − 1, the idleness-1/2 measures at the…
The proof, explained
The proof reduces the inequality to a single variable $c$ by substituting the relations $a = b = c + 2$ and $d_y = b + c + 1 = 2c + 3$. This substitution simplifies the expression to $\frac{1}{2} + \frac{c+1}{2c+3} < 1$. Clearing the strictly positive denominator $2c + 3$ yields $4c + 5 < 4c + 6$, which holds trivially because $5 < 6$.
$d_y > 0$ as a real number
Since $d_y = b + c + 1$ with $b, c \in \mathbb{N}$, Presburger arithmetic over the natural numbers shows $d_y > 0$, which is then cast into the real numbers.
have hdypos : (0:ℝ) < dy := by have : 0 < dy := by omega exact_mod_cast this
$d_y = 2c + 3$ in $\mathbb{R}$
Casting the hypotheses $d_y = b + c + 1$ and $b = c + 2$ to $\mathbb{R}$, linear arithmetic combines them to express $d_y$ as $(c + 2) + c + 1 = 2c + 3$.
have hdy' : (dy:ℝ) = 2*(c:ℝ) + 3 := by have : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hdy have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb nlinarith
$a = c + 2$ in $\mathbb{R}$
Casting the hypotheses $a = b$ and $b = c + 2$ to $\mathbb{R}$, linear arithmetic equates them to get $a = c + 2$.
have ha' : (a:ℝ) = (c:ℝ) + 2 := by have : (a:ℝ) = (b:ℝ) := by exact_mod_cast ha have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb nlinarith
The inequality is expressed solely in terms of $c$: $\frac{1}{2} + 2(c + 2 - 1) \cdot \frac{1/2}{2c + 3} < 1$
Substitute the derived equations $d_y = 2c + 3$ and $a = c + 2$ into the target inequality.
rw [hdy', ha']Clearing denominators and expanding reduces the inequality to $4c + 5 < 4c + 6$
Because $c \ge 0$, the denominator $2c + 3$ is strictly positive and therefore nonzero. Clearing fractions by multiplying by $2(2c + 3)$ and normalizing the resulting polynomials on both sides simplifies the goal to $4c + 5 < 4c + 6$.
have hden : (2*(c:ℝ) + 3) ≠ (0:ℝ) := by positivity field_simp [hden] ring_nf
The inequality holds, completing the proof
Since $c$ is a natural number, $c \ge 0$ in $\mathbb{R}$ by Nat.cast_nonneg. Linear arithmetic closes the goal immediately, since $4c + 5 < 4c + 6$ is equivalent to $5 < 6$.
uses
Nat.cast_nonneghave hc : (0:ℝ) ≤ (c:ℝ) := Nat.cast_nonneg c nlinarith [hc]
Nat.cast_nonneg- The coercion of any natural number into an ordered semiring is non-negative ($0 \le n$).
- The hypothesis `hdypos` (establishing $0 < d_y$ in $\mathbb{R}$ on lines 5–7) is never actually referenced in the rest of the proof.
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.
/-- Arithmetic: in the boundary configuration 1/2 + 2(|A|-1)(1/2)/d_y < 1. -/theorem graph_idle_special_cost_lt_one (a b c dy : ℕ) (ha : a = b) (hb : b = c + 2) (hdy : dy = b + c + 1) : (1:ℝ)/2 + 2*((a:ℝ) - 1)*((1/2)/(dy:ℝ)) < 1 := by have hdypos : (0:ℝ) < dy := by have : 0 < dy := by omega exact_mod_cast this have hdy' : (dy:ℝ) = 2*(c:ℝ) + 3 := by have : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hdy have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb nlinarith have ha' : (a:ℝ) = (c:ℝ) + 2 := by have : (a:ℝ) = (b:ℝ) := by exact_mod_cast ha have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb nlinarith rw [hdy', ha'] have hden : (2*(c:ℝ) + 3) ≠ (0:ℝ) := by positivity field_simp [hden] ring_nf have hc : (0:ℝ) ≤ (c:ℝ) := Nat.cast_nonneg c nlinarith [hc]