AFTD Auto-Formalizing Theoretical Domains

graph_idle_special_cost_lt_one

theoremverified

If a = b, b = c + 2 and d_y = b + c + 1, then 1/2 + 2(a−1)·(1/2)/d_y < 1.

Statement

theorem graph_idle_special_cost_lt_one
    (a b c dy : ℕ) (ha : a = b) (hb : b = c + 2) (hdy : dy = b + c + 1) :
    (1:ℝ)/2 + 2*((a:ℝ) - 1)*((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
Built on 1
  • graph_edge_partition_cardWith the four-part partition of V induced by an edge xy: deg x = |A| + |C| + 1, deg y = |B| + |C| + 1, and |V| = 2 + |A| + |B| + |C| + |P|.
Used by 2

The proof, explained

The proof reduces the inequality to a single variable $c$ by substituting the relations $a = b = c + 2$ and $d_y = b + c + 1 = 2c + 3$. This substitution simplifies the expression to $\frac{1}{2} + \frac{c+1}{2c+3} < 1$. Clearing the strictly positive denominator $2c + 3$ yields $4c + 5 < 4c + 6$, which holds trivially because $5 < 6$.

  1. $d_y > 0$ as a real number

    Since $d_y = b + c + 1$ with $b, c \in \mathbb{N}$, Presburger arithmetic over the natural numbers shows $d_y > 0$, which is then cast into the real numbers.

    lines 5–7

      have hdypos : (0:ℝ) < dy := by
        have : 0 < dy := by omega
        exact_mod_cast this
  2. $d_y = 2c + 3$ in $\mathbb{R}$

    Casting the hypotheses $d_y = b + c + 1$ and $b = c + 2$ to $\mathbb{R}$, linear arithmetic combines them to express $d_y$ as $(c + 2) + c + 1 = 2c + 3$.

    lines 8–11

      have hdy' : (dy:ℝ) = 2*(c:ℝ) + 3 := by
        have : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hdy
        have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb
        nlinarith
  3. $a = c + 2$ in $\mathbb{R}$

    Casting the hypotheses $a = b$ and $b = c + 2$ to $\mathbb{R}$, linear arithmetic equates them to get $a = c + 2$.

    lines 12–15

      have ha' : (a:ℝ) = (c:ℝ) + 2 := by
        have : (a:ℝ) = (b:ℝ) := by exact_mod_cast ha
        have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb
        nlinarith
  4. The inequality is expressed solely in terms of $c$: $\frac{1}{2} + 2(c + 2 - 1) \cdot \frac{1/2}{2c + 3} < 1$

    Substitute the derived equations $d_y = 2c + 3$ and $a = c + 2$ into the target inequality.

    line 16

      rw [hdy', ha']
  5. Clearing denominators and expanding reduces the inequality to $4c + 5 < 4c + 6$

    Because $c \ge 0$, the denominator $2c + 3$ is strictly positive and therefore nonzero. Clearing fractions by multiplying by $2(2c + 3)$ and normalizing the resulting polynomials on both sides simplifies the goal to $4c + 5 < 4c + 6$.

    lines 17–19

      have hden : (2*(c:ℝ) + 3) ≠ (0:ℝ) := by positivity
      field_simp [hden]
      ring_nf
  6. The inequality holds, completing the proof

    Since $c$ is a natural number, $c \ge 0$ in $\mathbb{R}$ by Nat.cast_nonneg. Linear arithmetic closes the goal immediately, since $4c + 5 < 4c + 6$ is equivalent to $5 < 6$.

    lines 20–21

    uses Nat.cast_nonneg

      have hc : (0:ℝ) ≤ (c:ℝ) := Nat.cast_nonneg c
      nlinarith [hc]
Nat.cast_nonneg
The coercion of any natural number into an ordered semiring is non-negative ($0 \le n$).

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: in the boundary configuration 1/2 + 2(|A|-1)(1/2)/d_y < 1. -/theorem graph_idle_special_cost_lt_one    (a b c dy : ℕ) (ha : a = b) (hb : b = c + 2) (hdy : dy = b + c + 1) :    (1:ℝ)/2 + 2*((a:ℝ) - 1)*((1/2)/(dy:ℝ)) < 1 := by  have hdypos : (0:ℝ) < dy := by    have : 0 < dy := by omega    exact_mod_cast this  have hdy' : (dy:ℝ) = 2*(c:ℝ) + 3 := by    have : (dy:ℝ) = (b:ℝ) + (c:ℝ) + 1 := by exact_mod_cast hdy    have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb    nlinarith  have ha' : (a:ℝ) = (c:ℝ) + 2 := by    have : (a:ℝ) = (b:ℝ) := by exact_mod_cast ha    have : (b:ℝ) = (c:ℝ) + 2 := by exact_mod_cast hb    nlinarith  rw [hdy', ha']  have hden : (2*(c:ℝ) + 3) ≠ (0:ℝ) := by positivity  field_simp [hden]  ring_nf  have hc : (0:ℝ) ≤ (c:ℝ) := Nat.cast_nonneg c  nlinarith [hc]
See it in the graphDiscuss this resultChallenge it