AFTD Auto-Formalizing Theoretical Domains

k22_code_max_density_le

theoremverifiedformalization

For every natural number n with 4 ≤ n, the maximum density of a K_{2,2}-code on Fin n, kst_code_max_density 2 2 n, is at most 1 / ((n : ℝ) - 2).

Statement

theorem k22_code_max_density_le (n : ℕ) (hn : 4 ≤ n) :
    kst_code_max_density 2 2 n ≤ 1 / ((n : ℝ) - 2)
Formalizes
arXiv:2301.13305, Proposition 1.5; arXiv:2610.35136, Proposition 3.1
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • kst_code_max_densityThe maximum density of a K_{s,t}-code in simple graphs on vertex set [n] is the supremum over all K_{s,t}-codes C of |C| / 2^{n choose 2}.
  • k22_code_card_leLet n be a natural number with 4 ≤ n. For every K_{2,2}-code C of simple graphs on Fin n, (n - 2) * Set.ncard C ≤ 2 ^ (n.choose 2).
  • is_kst_codeA family C of simple graphs on vertex set [n] is a K_{s,t}-code if for every two distinct graphs G, G' in C and every pair of disjoint…
Used by 2

Read back from the Lean

For every natural number $n \ge 4$, the maximum density of a $(2, 2)$-code on simple graphs with vertex set $\operatorname{Fin} n$ is at most $\frac{1}{n - 2}$.

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 unfolds the definition of `kst_code_max_density` as a double supremum over graph families C and proofs that C is a K_{2,2}-code. For each candidate family C, if C is a code, the cardinality bound (n - 2) * |C| ≤ 2^(n choose 2) from `k22_code_card_le` rearranges to show its density is at most 1 / (n - 2); if C is not a code, the supremum is empty and evaluates to 0. Since every term is bounded by 1 / (n - 2) and the index type is nonempty, the outer supremum is bounded by 1 / (n - 2).

  1. Unfolding the definition reduces the goal to bounding a double supremum over graph families and code proofs by 1 / (n - 2).

    We work under classical logic and simplify by unfolding the definition of `kst_code_max_density`, which defines the maximum density as the supremum over all sets C of graphs on Fin n and proofs that C is a K_{2,2}-code of the density |C| / 2^(n choose 2).

    lines 4–5

      classical
      dsimp [kst_code_max_density]
  2. The real denominator (n : ℝ) - 2 is strictly positive.

    From the hypothesis 4 ≤ n (hn), casting from ℕ to ℝ gives 4 ≤ (n : ℝ), and linear arithmetic yields 0 < (n : ℝ) - 2.

    lines 6–8

      have hpos_n : (0 : ℝ) < (n : ℝ) - 2 := by
        have : (4 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn
        linarith
  3. For every set of graphs C, the inner supremum over proofs that C is a K_{2,2}-code is at most 1 / (n - 2).

    We introduce an arbitrary graph family C and perform a case split on whether C is a K_{2,2}-code: 1. If C is a K_{2,2}-code (witnessed by h), the inner supremum simplifies to |C| / 2^(n choose 2) via `ciSup_pos`. Applying `k22_code_card_le` gives (n - 2) * |C| ≤ 2^(n choose 2). We cast this bound to ℝ, rewrite (n - 2 : ℕ) as (n : ℝ) - 2 (since 2 ≤ n), and clear denominators using `div_le_iff₀`, `div_mul_eq_mul_div`, `one_mul`, and `le_div_iff₀` with 0 < 2^(n choose 2) and 0 < n - 2. Linear arithmetic then confirms |C| / 2^(n choose 2) ≤ 1 / (n - 2). 2. If C is not a K_{2,2}-code, the index condition is false, so the supremum simplifies to sSup ∅ = 0 by `ciSup_neg` and `Real.sSup_empty`. Since 0 < n - 2, positivity immediately yields 0 ≤ 1 / (n - 2).

    lines 9–27

    uses ciSup_pos, k22_code_card_le, div_le_iff₀, div_mul_eq_mul_div, one_mul, le_div_iff₀, ciSup_neg, Real.sSup_empty

      have h_le : ∀ C : Set (SimpleGraph (Fin n)),
          (⨆ (_hC : is_kst_code 2 2 n C), (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ)) ≤ 1 / ((n : ℝ) - 2) := by
        intro C
        by_cases h : is_kst_code 2 2 n C
        · rw [ciSup_pos h]
          have hcard := k22_code_card_le n hn C h
          have hpos_pow : (0 : ℝ) < 2 ^ n.choose 2 := by positivity
          have hcast : ((n - 2 : ℕ) : ℝ) * (Set.ncard C : ℝ) ≤ (2 ^ n.choose 2 : ℝ) := by
            exact_mod_cast hcard
          have h_sub : ((n - 2 : ℕ) : ℝ) = (n : ℝ) - 2 := by
            push_cast [show 2 ≤ n by omega]
            rfl
          rw [h_sub] at hcast
          rw [div_le_iff₀ hpos_pow]
          rw [div_mul_eq_mul_div, one_mul]
          rw [le_div_iff₀ hpos_n]
          linarith
        · rw [ciSup_neg h, Real.sSup_empty]
          positivity
  4. The overall maximum density is at most 1 / (n - 2).

    The space of sets of graphs on Fin n is nonempty (witnessed by the empty set ∅). Since each term of the outer supremum is bounded above by 1 / (n - 2) by the previous step, `ciSup_le` completes the proof.

    lines 28–29

    uses ciSup_le

      have : Nonempty (Set (SimpleGraph (Fin n))) := ⟨∅⟩
      exact ciSup_le h_le
ciSup_pos
If a proposition p is true (witnessed by hp), the indexed supremum over p simplifies to the value at hp: ⨆ (h : p), f h = f hp.
k22_code_card_le
For n ≥ 4, every K_{2,2}-code C on Fin n satisfies (n - 2) * |C| ≤ 2^(n choose 2).
div_le_iff₀
For a positive divisor c, b / c ≤ a if and only if b ≤ a * c.
div_mul_eq_mul_div
For elements in a division monoid, (a / b) * c = (a * c) / b.
one_mul
1 * a = a for any element a in a multiplicative structure with 1.
le_div_iff₀
For a positive divisor c, a ≤ b / c if and only if a * c ≤ b.
ciSup_neg
If a proposition p is false, the indexed supremum over p is the supremum of the empty set: ⨆ (h : p), f h = sSup ∅.
Real.sSup_empty
The supremum of the empty set of real numbers is 0.
ciSup_le
If an index set is nonempty and every term in an indexed family is bounded above by c, then the supremum of the family is at most 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 maximum density of a K_{2,2}-code on Fin n for n ≥ 4 is at most 1 / (n - 2). -/theorem k22_code_max_density_le (n : ℕ) (hn : 4 ≤ n) :    kst_code_max_density 2 2 n ≤ 1 / ((n : ℝ) - 2) := by  classical  dsimp [kst_code_max_density]  have hpos_n : (0 : ℝ) < (n : ℝ) - 2 := by    have : (4 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn    linarith  have h_le : ∀ C : Set (SimpleGraph (Fin n)),      (⨆ (_hC : is_kst_code 2 2 n C), (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ)) ≤ 1 / ((n : ℝ) - 2) := by    intro C    by_cases h : is_kst_code 2 2 n C    · rw [ciSup_pos h]      have hcard := k22_code_card_le n hn C h      have hpos_pow : (0 : ℝ) < 2 ^ n.choose 2 := by positivity      have hcast : ((n - 2 : ℕ) : ℝ) * (Set.ncard C : ℝ) ≤ (2 ^ n.choose 2 : ℝ) := by        exact_mod_cast hcard      have h_sub : ((n - 2 : ℕ) : ℝ) = (n : ℝ) - 2 := by        push_cast [show 2 ≤ n by omega]        rfl      rw [h_sub] at hcast      rw [div_le_iff₀ hpos_pow]      rw [div_mul_eq_mul_div, one_mul]      rw [le_div_iff₀ hpos_n]      linarith    · rw [ciSup_neg h, Real.sSup_empty]      positivity  have : Nonempty (Set (SimpleGraph (Fin n))) := ⟨∅⟩  exact ciSup_le h_le
See it in the graphDiscuss this resultChallenge it