AFTD Auto-Formalizing Theoretical Domains

graph_idle_plan_cost_lt_one

theoremverified

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

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.

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

    lines 6–10

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

    lines 11–13

      have hdy : (0:ℝ) < (dy:ℝ) := by linarith
      have hdxpos : (0:ℝ) < (dx:ℝ) := by linarith
      have hdypos : (0:ℝ) < (dy:ℝ) := by linarith
  3. 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).

    lines 14–15

      rw [hx', hy']
      field_simp
  4. 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.

    line 16

    uses mul_le_mul_of_nonneg_left

      nlinarith [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.

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 ≤ 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:ℝ))]
See it in the graphDiscuss this resultChallenge it