AFTD Auto-Formalizing Theoretical Domains

graph_idle_plan_cost_lt_one_of_b_eq_zero

theoremverified

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

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

  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)$.

    line 5

      subst hb
  2. The 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.

    lines 6–7

      have hdx' : (0:ℝ) < dx := by exact_mod_cast hdx
      have hnn : (0:ℝ) ≤ (1/2)/(dx:ℝ) := by positivity
  3. 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$.

    lines 8–9

      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

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