AFTD Auto-Formalizing Theoretical Domains

chain_trees_extensive_mmi_gap_of_exact_claw_packings

theoremverified

For 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 k) = 3 * k in ℕ, then ((max_claw_packing (chain_tree_2 k) : ℝ) - (max_claw_packing (chain_tree_1 k) : ℝ)) / (16 * k : ℝ) ≥ 1 / 32.

Statement

theorem chain_trees_extensive_mmi_gap_of_exact_claw_packings (k : ℕ) (hk : 1 ≤ k)
    (h1 : max_claw_packing (chain_tree_1 k) = 5 * k / 2)
    (h2 : max_claw_packing (chain_tree_2 k) = 3 * k) :
    (1 : ℝ) / 32 ≤ ((max_claw_packing (chain_tree_2 k) : ℝ) - (max_claw_packing (chain_tree_1 k) : ℝ)) / (16 * k : ℝ)
Source
arXiv:2511.19585
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • max_claw_packingFor a simple graph G on a finite type V, max_claw_packing G is defined as the supremum of Finset.card P over all P : Finset (Finset V) in…
  • chain_tree_1For any k, chain_tree_1 k is the graph formed by joining k copies of seed_tree_1 in a chain at vertex 9.
  • chain_tree_2For any k, chain_tree_2 k is the graph formed by joining k copies of seed_tree_2 in a chain at vertex 1.

Read back from the Lean

For every natural number $k$, if: 1. $1 \le k$, 2. the maximum claw packing size of chain_tree_1 k equals $5k / 2$ (evaluated via integer division in $\mathbb{N}$), and 3. the maximum claw packing size of chain_tree_2 k equals $3k$, then the normalized difference in maximum claw packing sizes satisfies: $$\frac{1}{32} \le \frac{(\operatorname{max\_claw\_packing}(\operatorname{chain\_tree\_2}(k)) : \mathbb{R}) - (\operatorname{max\_claw\_packing}(\operatorname{chain\_tree\_1}(k)) : \mathbb{R})}{16k}$$ (where the right-hand side is evaluated 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 theorem asserts that if the maximum claw packings of two chain tree graphs on 16k vertices are 5k/2 (integer division) and 3k, their normalized gap is at least 1/32. The proof substitutes these assumed values into the normalized difference expression, reducing the claim to the arithmetic inequality (3k - ⌊5k/2⌋) / (16k) ≥ 1/32. This inequality is then closed immediately by the lemma chain_trees_floor_claw_packing_gap_ge.

  1. It suffices to show that 1/32 ≤ (3k - ⌊5k/2⌋) / (16k) in the real numbers.

    Rewriting with the hypotheses h1 and h2 substitutes 5 * k / 2 for max_claw_packing (chain_tree_1 k) and 3 * k for max_claw_packing (chain_tree_2 k) in the goal.

    line 6

      rw [h1, h2]
  2. The normalized difference is at least 1/32.

    This is established directly by chain_trees_floor_claw_packing_gap_ge applied to k and the assumption 1 ≤ k (hk).

    line 7

    uses chain_trees_floor_claw_packing_gap_ge

      exact chain_trees_floor_claw_packing_gap_ge k hk
chain_trees_floor_claw_packing_gap_ge
For any natural number k ≥ 1, the normalized difference (3k - ⌊5k/2⌋) / (16k) in ℝ is at least 1/32.

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

/-- If the chain trees achieve claw packings 5k/2 and 3k in Nat, their normalized gap is at least 1/32. -/theorem chain_trees_extensive_mmi_gap_of_exact_claw_packings (k : ℕ) (hk : 1 ≤ k)    (h1 : max_claw_packing (chain_tree_1 k) = 5 * k / 2)    (h2 : max_claw_packing (chain_tree_2 k) = 3 * k) :    (1 : ℝ) / 32 ≤ ((max_claw_packing (chain_tree_2 k) : ℝ) - (max_claw_packing (chain_tree_1 k) : ℝ)) / (16 * k : ℝ) := by  rw [h1, h2]  exact chain_trees_floor_claw_packing_gap_ge k hk
See it in the graphDiscuss this resultChallenge it