chain_trees_claw_packing_gap_rate
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
- chain_trees_floor_claw_packing_gap_geFor every integer k ≥ 1, the normalized gap (3k - ⌊5k/2⌋) / (16k) between the integer tripartite information bounds on the 16k-vertex…
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.
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.
uses
Nat.cast_pos.mpr,ne_of_gthave hk_pos : (0 : ℝ) < (k : ℝ) := Nat.cast_pos.mpr (by omega) have hk_ne : (k : ℝ) ≠ 0 := ne_of_gt hk_pos
((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.
have h_eq : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) = 1 / 32 := by field_simp ring
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.
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.
- On line 9, `rw [h_eq]` replaces the right-hand side with `1 / 32`, leaving the trivial inequality `1 / 32 ≤ 1 / 32`, which the `rw` tactic closes automatically by reflexivity.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]