AFTD Auto-Formalizing Theoretical Domains

chain_trees_claw_packing_gap_rate

theoremverified

For every integer k ≥ 1, the gap (3k - 5k/2) / (16k) between the tripartite information bounds on the 16k-vertex chain trees is at least 1/32.

Statement

theorem chain_trees_claw_packing_gap_rate (k : ℕ) (hk : 1 ≤ k) :
    (1 : ℝ) / 32 ≤ ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ)
Source
knowledgebase: OP-828
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For every natural number $k$ satisfying $1 \le k$, $1/32 \le ((3k) - (5k / 2)) / (16k)$, where $k$ is coerced to $\mathbb{R}$ and all arithmetic operations are real operations.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The inequality holds because the expression ((3k - 5k/2) / (16k)) is identically equal to 1/32 for every k ≥ 1. The proof first shows that k ≠ 0 in ℝ, simplifies the rational expression to 1/32 using field and ring operations, and substitutes this equality to conclude by reflexivity.

  1. k > 0 and k ≠ 0 as real numbers

    From the hypothesis k ≥ 1, linear integer arithmetic (`omega`) gives k > 0. Casting to the real numbers via `Nat.cast_pos.mpr` shows that k is strictly positive in ℝ, and `ne_of_gt` converts this strict inequality to k ≠ 0.

    lines 4–5

    uses Nat.cast_pos.mpr, ne_of_gt

      have hk_pos : (0 : ℝ) < (k : ℝ) := Nat.cast_pos.mpr (by omega)
      have hk_ne : (k : ℝ) ≠ 0 := ne_of_gt hk_pos
  2. ((3k - 5k / 2) / (16k) : ℝ) = 1 / 32

    Since k ≠ 0, `field_simp` clears the denominators and cancels k, reducing the identity to (3 · 2 - 5) · 32 = 2 · 16. Then `ring` evaluates both sides to 32, establishing equality.

    lines 6–8

      have h_eq : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) = 1 / 32 := by
        field_simp
        ring
  3. 1 / 32 ≤ (3k - 5k / 2) / (16k)

    Rewriting the right-hand side using the equality `h_eq` turns the goal into 1 / 32 ≤ 1 / 32, which holds by reflexivity.

    line 9

      rw [h_eq]
Nat.cast_pos.mpr
A natural number cast into a linearly ordered semiring is strictly positive if the original natural number is strictly positive (0 < n → 0 < ↑n).
ne_of_gt
If b < a in a preorder, then a ≠ b.

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

/-- The asymptotic claw packing gap rate between 3k and 5k/2 on 16k vertices is at least 1/32. -/theorem chain_trees_claw_packing_gap_rate (k : ℕ) (hk : 1 ≤ k) :    (1 : ℝ) / 32 ≤ ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) := by  have hk_pos : (0 : ℝ) < (k : ℝ) := Nat.cast_pos.mpr (by omega)  have hk_ne : (k : ℝ) ≠ 0 := ne_of_gt hk_pos  have h_eq : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) = 1 / 32 := by    field_simp    ring  rw [h_eq]
See it in the graphDiscuss this resultChallenge it