AFTD Auto-Formalizing Theoretical Domains

graph_idle_plan_cost_lt_one_boundary

theoremverified

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

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.

  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`.

    lines 6–11

    uses Nat.zero_lt_one, lt_of_lt_of_le, lt_trans

      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
  2. 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.

    lines 12–15

      have key : 2*(b:ℝ)*((1/2)/(dy:ℝ)) = (1:ℝ)/2 + (1:ℝ)/(2*(dy:ℝ)) := by
        field_simp
        nlinarith
      rw [key]
  3. 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.

    lines 16–17

      have h3 : (1:ℝ)/2/(dx:ℝ) = 1/(2*(dx:ℝ)) := by ring
      rw [h3]
  4. 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).

    lines 18–21

    uses one_div_lt_one_div_of_lt

      have h2 : (1:ℝ)/(2*(dy:ℝ)) < 1/(2*(dx:ℝ)) := by
        apply one_div_lt_one_div_of_lt
        · positivity
        · linarith
  5. 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.

    line 22

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it