AFTD Auto-Formalizing Theoretical Domains

chain_trees_floor_claw_packing_gap_ge

theoremverified

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

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.

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

    lines 4–5

    uses chain_trees_claw_packing_gap_rate

      have h1 : (1 : ℝ) / 32 ≤ ((3 * k : ℝ) - (5 * k / 2 : ℝ)) / (16 * k : ℝ) :=
        chain_trees_claw_packing_gap_rate k hk
  2. The 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⌋.

    lines 6–9

    uses Nat.cast_div_le

      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
  3. 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`.

    lines 10–13

    uses div_le_div_of_nonneg_right

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

    line 14

    uses le_trans

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

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 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
See it in the graphDiscuss this resultChallenge it