graph_idle_plan_cost_lt_one_of_b_eq_zero
If b = 0 and 1 ≤ d_x, then 1/2 − (1/2)/d_x + 0 < 1.
Statement
theorem graph_idle_plan_cost_lt_one_of_b_eq_zero
(dx dy a b c : ℕ) (hdx : 1 ≤ dx) (hx : dx = a + c + 1) (hy : dy = b + c + 1) (hb : b = 0) :
1/2 - (1/2)/(dx:ℝ) + 2*(b:ℝ)*((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- 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 claim establishes that the cost expression $1/2 - (1/2)/d_x + 2b((1/2)/d_y)$ is strictly less than $1$ when $b = 0$. Substituting $b = 0$ eliminates the third term, leaving $1/2 - (1/2)/d_x$. Because $d_x \ge 1$, the term $(1/2)/d_x$ is non-negative, so the remaining quantity is at most $1/2 < 1$.
Substitute $b = 0$ into the cost expression.
Substituting the hypothesis $b = 0$ into the goal replaces the variable $b$ by $0$, turning the third term $2b((1/2)/d_y)$ into $2 \cdot 0 \cdot ((1/2)/d_y)$.
subst hbThe term $(1/2)/d_x$ is non-negative.
From $1 \le d_x$, casting to the real numbers yields $d_x > 0$. Because both $1/2$ and $d_x$ are strictly positive real numbers, their quotient $(1/2)/d_x$ is non-negative.
have hdx' : (0:ℝ) < dx := by exact_mod_cast hdx have hnn : (0:ℝ) ≤ (1/2)/(dx:ℝ) := by positivity
The cost bound $1/2 - (1/2)/d_x < 1$ holds.
Simplification eliminates the product with zero, reducing the goal to $1/2 - (1/2)/d_x < 1$. Since $(1/2)/d_x \ge 0$, the left-hand side is at most $1/2$, and linear arithmetic concludes that this is strictly less than $1$.
simp linarith
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: with b = 0 the main-plan cost bound is strictly below 1. -/theorem graph_idle_plan_cost_lt_one_of_b_eq_zero (dx dy a b c : ℕ) (hdx : 1 ≤ dx) (hx : dx = a + c + 1) (hy : dy = b + c + 1) (hb : b = 0) : 1/2 - (1/2)/(dx:ℝ) + 2*(b:ℝ)*((1/2)/(dy:ℝ)) < 1 := by subst hb have hdx' : (0:ℝ) < dx := by exact_mod_cast hdx have hnn : (0:ℝ) ≤ (1/2)/(dx:ℝ) := by positivity simp linarith