graph_idle_plan_cost_lt_one_boundary
If d_x = a + c + 1 < d_y = b + c + 1 and b = c + 2, then 1/2 − (1/2)/d_x + 2b·(1/2)/d_y < 1.
Statement
theorem graph_idle_plan_cost_lt_one_boundary
(dx dy a b c : ℕ) (hdx : 1 ≤ dx) (hlt : dx < dy)
(hx : dx = a + c + 1) (hy : dy = b + c + 1) (hb : b = c + 2) :
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 proof rewrites the boundary term 2b · ((1/2) / d_y) using the relation 2b = d_y + 1 (derived from b = c + 2 and d_y = b + c + 1) into 1/2 + 1 / (2 d_y). Substituting this into the cost expression turns it into 1 − 1 / (2 d_x) + 1 / (2 d_y). Since d_x < d_y, the reciprocal inequality 1 / (2 d_y) < 1 / (2 d_x) holds, ensuring that the total cost is strictly less than 1.
0 < d_x < d_y in ℝ, along with real-number versions of the given equalities on d_x, d_y, a, b, c.
From 1 ≤ d_x and 0 < 1 (`Nat.zero_lt_one`), `lt_of_lt_of_le` yields 0 < d_x. Casting d_x < d_y to ℝ and applying transitivity (`lt_trans`) gives 0 < d_y. The hypotheses b = c + 2, d_y = b + c + 1, and d_x = a + c + 1 are likewise cast from ℕ to ℝ using `exact_mod_cast`.
uses
Nat.zero_lt_one,lt_of_lt_of_le,lt_transhave hdxpos : (0:ℝ) < dx := by exact_mod_cast (lt_of_lt_of_le Nat.zero_lt_one hdx) have hltR : (dx:ℝ) < (dy:ℝ) := by exact_mod_cast hlt have hdypos : (0:ℝ) < (dy:ℝ) := lt_trans hdxpos hltR have hbR : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb have hyR : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hy have hdxR : (dx:ℝ) = (a:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hx
The term 2b · ((1/2) / d_y) is rewritten as 1/2 + 1 / (2 d_y) in the goal.
The conditions d_y = b + c + 1 and b = c + 2 imply 2b = d_y + 1. Clearing denominators with `field_simp` reduces 2b · ((1/2) / d_y) = 1/2 + 1 / (2 d_y) to 2b = d_y + 1, which `nlinarith` verifies. Rewriting with this identity transforms the goal into 1/2 − (1/2) / d_x + (1/2 + 1 / (2 d_y)) < 1.
have key : 2*(b:ℝ)*((1/2)/(dy:ℝ)) = (1:ℝ)/2 + (1:ℝ)/(2*(dy:ℝ)) := by field_simp nlinarith rw [key]
The term (1/2) / d_x is simplified to 1 / (2 d_x).
Ring arithmetic confirms that (1/2) / d_x = 1 / (2 d_x). Rewriting with this identity puts the inequality into the form 1/2 − 1 / (2 d_x) + (1/2 + 1 / (2 d_y)) < 1.
have h3 : (1:ℝ)/2/(dx:ℝ) = 1/(2*(dx:ℝ)) := by ring rw [h3]
1 / (2 d_y) < 1 / (2 d_x).
Since 0 < 2 d_x (established by `positivity` from 0 < d_x) and 2 d_x < 2 d_y (by linear arithmetic from d_x < d_y), `one_div_lt_one_div_of_lt` yields 1 / (2 d_y) < 1 / (2 d_x).
uses
one_div_lt_one_div_of_lthave h2 : (1:ℝ)/(2*(dy:ℝ)) < 1/(2*(dx:ℝ)) := by apply one_div_lt_one_div_of_lt · positivity · linarith
The total cost 1/2 − (1/2) / d_x + 2b · ((1/2) / d_y) is strictly less than 1.
Linear arithmetic (`linarith`) combines 1 / (2 d_y) < 1 / (2 d_x) with 1/2 − 1 / (2 d_x) + 1/2 + 1 / (2 d_y) = 1 + (1 / (2 d_y) − 1 / (2 d_x)) to conclude that the cost is strictly less than 1.
linarith
Nat.zero_lt_one- Zero is strictly less than one for natural numbers.
lt_of_lt_of_le- In a preorder, if a < b and b ≤ c, then a < c.
lt_trans- Strict inequality is transitive: if a < b and b < c, then a < c.
one_div_lt_one_div_of_lt- For positive elements in an ordered semifield, if a < b then 1 / b < 1 / a.
- The natural number variables and hypotheses are explicitly cast to the real numbers before performing arithmetic, which is a formal requirement in Lean with no counterpart on paper.
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.
/-- Boundary arithmetic: with b = c+2 but d_x < d_y the main-plan cost bound is still below 1. -/theorem graph_idle_plan_cost_lt_one_boundary (dx dy a b c : ℕ) (hdx : 1 ≤ dx) (hlt : dx < dy) (hx : dx = a + c + 1) (hy : dy = b + c + 1) (hb : b = c + 2) : 1/2 - (1/2)/(dx:ℝ) + 2*(b:ℝ)*((1/2)/(dy:ℝ)) < 1 := by have hdxpos : (0:ℝ) < dx := by exact_mod_cast (lt_of_lt_of_le Nat.zero_lt_one hdx) have hltR : (dx:ℝ) < (dy:ℝ) := by exact_mod_cast hlt have hdypos : (0:ℝ) < (dy:ℝ) := lt_trans hdxpos hltR have hbR : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb have hyR : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hy have hdxR : (dx:ℝ) = (a:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hx have key : 2*(b:ℝ)*((1/2)/(dy:ℝ)) = (1:ℝ)/2 + (1:ℝ)/(2*(dy:ℝ)) := by field_simp nlinarith rw [key] have h3 : (1:ℝ)/2/(dx:ℝ) = 1/(2*(dx:ℝ)) := by ring rw [h3] have h2 : (1:ℝ)/(2*(dy:ℝ)) < 1/(2*(dx:ℝ)) := by apply one_div_lt_one_div_of_lt · positivity · linarith linarith