k22_code_max_density_le
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
- four_cycle_graph_code_density_tendsto_one_along_powers_of_twoAs the natural number r tends to infinity, the sequence ((2 : ℝ) ^ r) * kst_code_max_density 2 2 (2 ^ r) tends to 1.
- four_cycle_graph_code_asymptotic_density_eventually_leFor every real number ε > 0, for eventually all natural numbers n in Filter.atTop, (n : ℝ) * kst_code_max_density 2 2 n ≤ 1 + ε.
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).
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).
classical dsimp [kst_code_max_density]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.
have hpos_n : (0 : ℝ) < (n : ℝ) - 2 := by have : (4 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hn linarith
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).
uses
ciSup_pos,k22_code_card_le,div_le_iff₀,div_mul_eq_mul_div,one_mul,le_div_iff₀,ciSup_neg,Real.sSup_emptyhave 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
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.
uses
ciSup_lehave : 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.
- In Lean, `kst_code_max_density` is formalized as an outer supremum over all sets of graphs C and an inner supremum over proofs that C is a code. When C is not a code, the inner supremum is over an empty proposition, which Mathlib evaluates to `sSup ∅ = 0`. On paper, one simply defines the maximum density by taking the supremum directly over valid codes.
- Casting the natural number subtraction `n - 2` to the real numbers requires establishing `2 ≤ n` (here derived from `4 ≤ n`) so that natural number truncation does not occur.
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 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