chain_trees_floor_claw_packing_gap_ge
For every integer k ≥ 1, the normalized gap (3k - ⌊5k/2⌋) / (16k) between the integer tripartite information bounds on the 16k-vertex chain trees is at least 1/32.
Statement
theorem chain_trees_floor_claw_packing_gap_ge (k : ℕ) (hk : 1 ≤ k) :
(1 : ℝ) / 32 ≤ (((3 * k : ℕ) : ℝ) - ((5 * k / 2 : ℕ) : ℝ)) / (16 * k : ℝ)- Source
- arXiv:2511.19585
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- chain_trees_claw_packing_gap_rateFor every integer k ≥ 1, the gap (3k - 5k/2) / (16k) between the tripartite information bounds on the 16k-vertex chain trees is at least…
- Used by 1
- chain_trees_extensive_mmi_gap_of_exact_claw_packingsFor any integer k ≥ 1, if max_claw_packing (chain_tree_1 k) = 5 * k / 2 in ℕ (using integer division) and max_claw_packing (chain_tree_2…
Read back from the Lean
For every natural number $k$ satisfying $1 \le k$, $\frac{1}{32} \le \frac{3k - \lfloor 5k / 2 \rfloor}{16k}$, where $5k / 2$ is integer (truncated) division in $\mathbb{N}$, and the subtraction and outer divisions are performed in $\mathbb{R}$.
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 proof bounds the discrete normalized gap from below by comparing it to the continuous rate. First, the continuous gap (3k - 5k/2) / (16k) is bounded below by 1/32 using the theorem `chain_trees_claw_packing_gap_rate`. Because integer division truncates, ⌊5k/2⌋ ≤ 5k/2, which makes the numerator 3k - ⌊5k/2⌋ at least as large as 3k - 5k/2. Since the denominator 16k is non-negative, dividing preserves the inequality, and transitivity yields the desired lower bound of 1/32.
The continuous normalized gap (3k - 5k/2) / (16k) is at least 1/32.
Applying the known bound `chain_trees_claw_packing_gap_rate` to the assumption k ≥ 1 establishes that 1/32 ≤ (3k - 5k/2) / (16k).
uses
chain_trees_claw_packing_gap_ratehave h1 : (1 : ℝ) / 32 ≤ ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) := chain_trees_claw_packing_gap_rate k hkThe continuous numerator 3k - 5k/2 is at most the integer-truncated numerator 3k - ⌊5k/2⌋.
Integer division truncates, so ⌊5k/2⌋ ≤ 5k/2 by `Nat.cast_div_le`. Subtracting this smaller or equal term from 3k increases the value; after normalizing coercions (`push_cast`), linear arithmetic (`linarith`) verifies that 3k - 5k/2 ≤ 3k - ⌊5k/2⌋.
uses
Nat.cast_div_lehave h_div : ((5 * k / 2 : ℕ) : ℝ) ≤ ((5 * k : ℕ) : ℝ) / 2 := Nat.cast_div_le have h_num : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) ≤ (((3 * k : ℕ) : ℝ) - ((5 * k / 2 : ℕ) : ℝ)) := by push_cast at h_div ⊢ linarith
The continuous normalized gap is at most the integer-truncated normalized gap.
The denominator 16k is non-negative for natural k (verified by `positivity`). Dividing both sides of the numerator inequality by this non-negative denominator preserves the inequality via `div_le_div_of_nonneg_right`.
uses
div_le_div_of_nonneg_righthave h_denom : 0 ≤ (16 * k : ℝ) := by positivity have h2 : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) ≤ (((3 * k : ℕ) : ℝ) - ((5 * k / 2 : ℕ) : ℝ)) / (16 * k : ℝ) := div_le_div_of_nonneg_right h_num h_denom
The integer-truncated normalized gap (3k - ⌊5k/2⌋) / (16k) is at least 1/32.
Chaining the continuous lower bound 1/32 ≤ (3k - 5k/2) / (16k) and the comparison (3k - 5k/2) / (16k) ≤ (3k - ⌊5k/2⌋) / (16k) using transitivity (`le_trans`) completes the proof.
uses
le_transexact le_trans h1 h2
chain_trees_claw_packing_gap_rate- For any integer k ≥ 1, the continuous normalized gap (3k - 5k/2) / (16k) is at least 1/32.
Nat.cast_div_le- For natural numbers m and n, the cast of the integer quotient ⌊m / n⌋ to an ordered semifield is at most the quotient of the casts m / n.
div_le_div_of_nonneg_right- Dividing both sides of an inequality by a non-negative quantity preserves the inequality: if a ≤ b and 0 ≤ c, then a / c ≤ b / c.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
- In Lean, integer division is represented by natural number division (5 * k / 2 : ℕ) cast to ℝ; the tactic `push_cast` distributes the coercion across arithmetic operations before `linarith` handles the real inequality.
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 normalized difference between 3k and the integer floor 5k/2 is at least 1/32. -/theorem chain_trees_floor_claw_packing_gap_ge (k : ℕ) (hk : 1 ≤ k) : (1 : ℝ) / 32 ≤ (((3 * k : ℕ) : ℝ) - ((5 * k / 2 : ℕ) : ℝ)) / (16 * k : ℝ) := by have h1 : (1 : ℝ) / 32 ≤ ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) := chain_trees_claw_packing_gap_rate k hk have h_div : ((5 * k / 2 : ℕ) : ℝ) ≤ ((5 * k : ℕ) : ℝ) / 2 := Nat.cast_div_le have h_num : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) ≤ (((3 * k : ℕ) : ℝ) - ((5 * k / 2 : ℕ) : ℝ)) := by push_cast at h_div ⊢ linarith have h_denom : 0 ≤ (16 * k : ℝ) := by positivity have h2 : ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) ≤ (((3 * k : ℕ) : ℝ) - ((5 * k / 2 : ℕ) : ℝ)) / (16 * k : ℝ) := div_le_div_of_nonneg_right h_num h_denom exact le_trans h1 h2