graph_idle_plan_cost_lt_one
If d_x = a + c + 1, d_y = b + c + 1, 1 ≤ d_x ≤ d_y and b ≤ c + 1, then 1/2 − (1/2)/d_x + 2b·(1/2)/d_y < 1.
Statement
theorem graph_idle_plan_cost_lt_one
(dx dy a b c : ℕ) (hdx : 1 ≤ dx) (hle : dx ≤ dy)
(hx : dx = a + c + 1) (hy : dy = b + c + 1) (hb : b ≤ c + 1) :
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 expression 1/2 − 1/(2 dx) + 2b·(1/2)/dy simplifies to 1/2 − 1/(2 dx) + b/dy. Since b ≤ c + 1, we have 2b ≤ b + c + 1 = dy, meaning b/dy ≤ 1/2. Subtracting the strictly positive quantity 1/(2 dx) (as dx ≥ 1) guarantees the overall sum is strictly less than 1/2 + 1/2 = 1. The formal proof casts all natural-number assumptions to ℝ, clears denominators using field_simp, and verifies the resulting polynomial inequality with nlinarith.
The hypotheses 1 ≤ dx, dx ≤ dy, dx = a + c + 1, dy = b + c + 1, and b ≤ c + 1 are transferred from ℕ to ℝ.
The tactic exact_mod_cast casts each natural-number equality and inequality to its corresponding statement over the real numbers.
have hdx' : (1:ℝ) ≤ (dx:ℝ) := by exact_mod_cast hdx have hle' : (dx:ℝ) ≤ (dy:ℝ) := by exact_mod_cast hle have hx' : (dx:ℝ) = (a:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hx have hy' : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hy have hb' : (b:ℝ) ≤ (c:ℝ) + 1 := by exact_mod_cast hb
0 < dx and 0 < dy hold in ℝ.
Linear arithmetic (linarith) derives that dx and dy are strictly positive from 1 ≤ dx and dx ≤ dy. (The strict positivity of dy is proved twice, on lines 11 and 13).
have hdy : (0:ℝ) < (dy:ℝ) := by linarith have hdxpos : (0:ℝ) < (dx:ℝ) := by linarith have hdypos : (0:ℝ) < (dy:ℝ) := by linarith
The goal is expressed purely in terms of a, b, and c, and denominators are cleared to yield a polynomial inequality.
Rewriting replaces dx with a + c + 1 and dy with b + c + 1. The tactic field_simp then clears the denominators 2, a + c + 1, and b + c + 1 (all of which are non-zero since dx > 0 and dy > 0), transforming the fractional inequality into (a + c)(b + c + 1) + 2b(a + c + 1) < 2(a + c + 1)(b + c + 1).
rw [hx', hy'] field_simp
The polynomial inequality holds, completing the theorem.
The tactic nlinarith closes the goal. It is provided with the supplementary inequality b² ≤ b(c + 1), derived by multiplying b ≤ c + 1 on the left by b ≥ 0 (checked by positivity) via mul_le_mul_of_nonneg_left. Expanding both sides shows the difference between the right- and left-hand sides is (a + c + 1)(c + 1 - b) + (b + c + 1), which is strictly positive because b ≤ c + 1, dx > 0, and dy > 0.
uses
mul_le_mul_of_nonneg_leftnlinarith [mul_le_mul_of_nonneg_left hb' (by positivity : (0:ℝ) ≤ (b:ℝ))]
mul_le_mul_of_nonneg_left- If b ≤ c and 0 ≤ a, then a * b ≤ a * c.
- Line 13 redundantly re-proves 0 < (dy : ℝ) under the name hdypos, which was already established on line 11 as hdy.
- The non-linear arithmetic step on line 16 automatically expands and compares polynomials, combining the cleared-denominator goal with the supplied quadratic inequality b² ≤ b(c + 1).
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 ≤ c+1 the main-plan cost bound is strictly below 1. -/theorem graph_idle_plan_cost_lt_one (dx dy a b c : ℕ) (hdx : 1 ≤ dx) (hle : dx ≤ dy) (hx : dx = a + c + 1) (hy : dy = b + c + 1) (hb : b ≤ c + 1) : 1/2 - (1/2)/(dx:ℝ) + 2*(b:ℝ)*((1/2)/(dy:ℝ)) < 1 := by have hdx' : (1:ℝ) ≤ (dx:ℝ) := by exact_mod_cast hdx have hle' : (dx:ℝ) ≤ (dy:ℝ) := by exact_mod_cast hle have hx' : (dx:ℝ) = (a:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hx have hy' : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hy have hb' : (b:ℝ) ≤ (c:ℝ) + 1 := by exact_mod_cast hb have hdy : (0:ℝ) < (dy:ℝ) := by linarith have hdxpos : (0:ℝ) < (dx:ℝ) := by linarith have hdypos : (0:ℝ) < (dy:ℝ) := by linarith rw [hx', hy'] field_simp nlinarith [mul_le_mul_of_nonneg_left hb' (by positivity : (0:ℝ) ≤ (b:ℝ))]