k22_code_exists_dense_family_of_power_of_two
For every natural number r ≥ 2, there exists a K_{2,2}-code on Fin (2^r) with density at least 1 / 2^r.
Statement
theorem k22_code_exists_dense_family_of_power_of_two (r : ℕ) (hr : 2 ≤ r) :
∃ C : Set (SimpleGraph (Fin (2 ^ r))),
is_kst_code 2 2 (2 ^ r) C ∧
1 / ((2 : ℝ) ^ r) ≤ (C.ncard : ℝ) / (2 ^ ((2 ^ r).choose 2) : ℝ)- Source
- step towards k22_code_exists_dense_family
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- card_simpleGraphThe number of simple graphs on a finite vertex set V is 2^{C(|V|,2)}, where C(|V|,2) = |V|(|V|-1)/2 is the number of unordered pairs of…
- k22_code_max_density_two_pow_geFor every natural number r ≥ 2, the maximum density of a K_{2,2}-code on Fin (2^r) is at least 1 / 2^r.
- 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…
The proof, explained
The theorem is proved by a pigeonhole argument applied to an algebraic signature map on graphs. The vertex set Fin (2^r) is identified with the finite field GF(2^r), and graphs are mapped to signatures in GF(2^r) such that every fiber forms a valid K_{2,2}-code. Since there are 2^(choose (2^r) 2) graphs on 2^r vertices and only 2^r possible signatures, the pigeonhole principle guarantees a fiber containing at least 2^(choose (2^r) 2 - r) graphs. Taking this fiber as the code yields the required density of at least 1 / 2^r.
The vertex set Fin (2^r) is placed in bijection with the finite field GF(2^r).
Using classical logic, we register a finite type instance for the Galois field $GF(2^r) = \mathrm{GaloisField}(2, r)$ using `Fintype.ofFinite`. Since $r \ge 2 > 0$, `GaloisField.card` and `Nat.card_eq_fintype_card` show that $|GF(2^r)| = 2^r$. Because $\mathrm{Fin}(2^r)$ also has cardinality $2^r$ by `Fintype.card_fin`, we construct an explicit bijection $e : \mathrm{Fin}(2^r) \simeq GF(2^r)$ via `Fintype.equivFinOfCardEq`.
uses
Fintype.ofFinite,Nat.card_eq_fintype_card,GaloisField.card,Fintype.card_fin,Fintype.equivFinOfCardEqclassical letI : Fintype (GaloisField 2 r) := Fintype.ofFinite _ have hcard : Fintype.card (GaloisField 2 r) = 2 ^ r := by rw [← Nat.card_eq_fintype_card]; exact GaloisField.card 2 r (by omega) have hcardV : Fintype.card (Fin (2 ^ r)) = 2 ^ r := Fintype.card_fin _ let e : Fin (2 ^ r) ≃ GaloisField 2 r := (Fintype.equivFinOfCardEq hcard).symm
There exists an element s in GF(2^r) whose fiber under the graph signature map contains at least 2^(N - r) graphs, where N = choose (2^r) 2.
Let $N = \binom{2^r}{2}$ be the number of possible edges on $2^r$ vertices. Since $r \ge 2$, we have $r \le N$ by `k22_code_max_density_two_pow_ge_r_le_choose`. The total number of graphs on $\mathrm{Fin}(2^r)$ is $2^N$ by `card_simpleGraph`. Because $2^r \cdot 2^{N - r} = 2^N$ using `pow_add` and `Nat.add_sub_cancel'`, the pigeonhole principle (`Fintype.exists_le_card_fiber_of_mul_le_card`) guarantees the existence of a signature value $s \in GF(2^r)$ whose fiber under `k22_code_max_density_two_pow_ge_sig` contains at least $2^{N - r}$ graphs.
uses
k22_code_max_density_two_pow_ge_r_le_choose,Fintype.exists_le_card_fiber_of_mul_le_card,card_simpleGraph,pow_add,Nat.add_sub_cancel'set N := (2 ^ r).choose 2 with hN have hrN := k22_code_max_density_two_pow_ge_r_le_choose r hr obtain ⟨s, hs⟩ := Fintype.exists_le_card_fiber_of_mul_le_card (f := k22_code_max_density_two_pow_ge_sig (fun v => e v)) (n := 2 ^ (N - r)) (by rw [hcard, card_simpleGraph, hcardV, ← pow_add, Nat.add_sub_cancel' hrN])
The chosen fiber is a K_{2,2}-code.
We define the candidate code $C$ to be the fiber $\{G \mid \mathrm{sig}(e, G) = s\}$. Since $GF(2^r)$ is a field of characteristic 2 and $e$ is injective, lemma `k22_code_max_density_two_pow_ge_fiber_code` directly implies that this fiber forms a $K_{2,2}$-code.
uses
k22_code_max_density_two_pow_ge_fiber_coderefine ⟨{G | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s}, ?_, ?_⟩ · exact k22_code_max_density_two_pow_ge_fiber_code _ e.injective s
The cardinality of C as a set is at least 2^(N - r).
The set $C$ is rewritten as the coercion of a filtered finset of graphs. By `Set.ncard_coe_finset`, its set cardinality `ncard` equals its finset cardinality, which is at least $2^{N - r}$ from the pigeonhole bound $hs$.
uses
Set.ncard_coe_finset· have hncard : 2 ^ (N - r) ≤ ({G : SimpleGraph (Fin (2 ^ r)) | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s} : Set _).ncard := by have : {G : SimpleGraph (Fin (2 ^ r)) | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s} = ↑(Finset.univ.filter fun G => k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s) := by ext G; simp rw [this, Set.ncard_coe_finset] exact hs
The density of C is at least 1 / 2^r.
To prove $1 / 2^r \le |C| / 2^N$, we clear denominators using `div_le_div_iff₀` and `one_mul`, reducing the claim to $2^N \le |C| \cdot 2^r$. Rewriting $2^N = 2^{N - r} \cdot 2^r$ via `pow_add` and `Nat.sub_add_cancel`, the inequality follows from $2^{N - r} \le |C|$ by multiplying both sides by $2^r > 0$ using `mul_le_mul_of_nonneg_right`.
uses
div_le_div_iff₀,one_mul,pow_add,Nat.sub_add_cancel,mul_le_mul_of_nonneg_righthave hpos : (0 : ℝ) < 2 ^ N := by positivity rw [div_le_div_iff₀ (by positivity) hpos, one_mul] calc (2 : ℝ) ^ N = (2 : ℝ) ^ (N - r) * 2 ^ r := by rw [← pow_add, Nat.sub_add_cancel hrN] _ ≤ (({G : SimpleGraph (Fin (2 ^ r)) | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s} : Set _).ncard : ℝ) * 2 ^ r := by apply mul_le_mul_of_nonneg_right _ (by positivity) exact_mod_cast hncard
Fintype.ofFinite- Constructs a `Fintype` instance from a `Finite` instance.
Nat.card_eq_fintype_card- The general cardinality `Nat.card α` of a finite type equals its `Fintype.card α`.
GaloisField.card- The cardinality of the Galois field of characteristic $p$ and degree $n$ is $p^n$, provided $n ≠ 0$.
Fintype.card_fin- The cardinality of `Fin n` is $n$.
Fintype.equivFinOfCardEq- Any finite type with cardinality $n$ is in bijection with `Fin n`.
k22_code_max_density_two_pow_ge_r_le_choose- For any natural number $r ≥ 2$, $r ≤ \binom{2^r}{2}$.
Fintype.exists_le_card_fiber_of_mul_le_card- If $f : α → β$ is a map between finite types with $|\beta| \cdot n ≤ |α|$, then some fiber of $f$ has size at least $n$.
card_simpleGraph- The number of simple graphs on a finite vertex set $V$ is $2^{\binom{|V|}{2}}$.
pow_add- In a monoid, $a^{m + n} = a^m \cdot a^n$.
Nat.add_sub_cancel'- For natural numbers with $m ≤ n$, $m + (n - m) = n$.
k22_code_max_density_two_pow_ge_fiber_code- For an injective labeling of vertices into a field of characteristic 2, every fiber of the signature map is a $K_{2,2}$-code.
Set.ncard_coe_finset- The set cardinality `ncard` of a coerced finset equals its finset cardinality `card`.
div_le_div_iff₀- For positive denominators $b, d > 0$, $a / b ≤ c / d$ if and only if $a \cdot d ≤ c \cdot b$.
one_mul- Multiplying an element by 1 on the left leaves it unchanged ($1 \cdot a = a$).
Nat.sub_add_cancel- For natural numbers with $m ≤ n$, $(n - m) + m = n$.
mul_le_mul_of_nonneg_right- Multiplying an inequality $b ≤ c$ on the right by a nonnegative element preserves the inequality.
- The signature map `k22_code_max_density_two_pow_ge_sig` and the lemma `k22_code_max_density_two_pow_ge_fiber_code` asserting that its fibers form $K_{2,2}$-codes are established earlier in the knowledge base and treated as black boxes here.
- The argument transitions between finset cardinalities (`Finset.card`), required by the library pigeonhole lemma, and set cardinalities (`Set.ncard`), used in the theorem statement.
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.
/-- There exists a K_{2,2}-code on Fin (2^r) with density at least 1 / 2^r for all r ≥ 2. -/theorem k22_code_exists_dense_family_of_power_of_two (r : ℕ) (hr : 2 ≤ r) : ∃ C : Set (SimpleGraph (Fin (2 ^ r))), is_kst_code 2 2 (2 ^ r) C ∧ 1 / ((2 : ℝ) ^ r) ≤ (C.ncard : ℝ) / (2 ^ ((2 ^ r).choose 2) : ℝ) := by classical letI : Fintype (GaloisField 2 r) := Fintype.ofFinite _ have hcard : Fintype.card (GaloisField 2 r) = 2 ^ r := by rw [← Nat.card_eq_fintype_card]; exact GaloisField.card 2 r (by omega) have hcardV : Fintype.card (Fin (2 ^ r)) = 2 ^ r := Fintype.card_fin _ let e : Fin (2 ^ r) ≃ GaloisField 2 r := (Fintype.equivFinOfCardEq hcard).symm set N := (2 ^ r).choose 2 with hN have hrN := k22_code_max_density_two_pow_ge_r_le_choose r hr obtain ⟨s, hs⟩ := Fintype.exists_le_card_fiber_of_mul_le_card (f := k22_code_max_density_two_pow_ge_sig (fun v => e v)) (n := 2 ^ (N - r)) (by rw [hcard, card_simpleGraph, hcardV, ← pow_add, Nat.add_sub_cancel' hrN]) refine ⟨{G | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s}, ?_, ?_⟩ · exact k22_code_max_density_two_pow_ge_fiber_code _ e.injective s · have hncard : 2 ^ (N - r) ≤ ({G : SimpleGraph (Fin (2 ^ r)) | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s} : Set _).ncard := by have : {G : SimpleGraph (Fin (2 ^ r)) | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s} = ↑(Finset.univ.filter fun G => k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s) := by ext G; simp rw [this, Set.ncard_coe_finset] exact hs have hpos : (0 : ℝ) < 2 ^ N := by positivity rw [div_le_div_iff₀ (by positivity) hpos, one_mul] calc (2 : ℝ) ^ N = (2 : ℝ) ^ (N - r) * 2 ^ r := by rw [← pow_add, Nat.sub_add_cancel hrN] _ ≤ (({G : SimpleGraph (Fin (2 ^ r)) | k22_code_max_density_two_pow_ge_sig (fun v => e v) G = s} : Set _).ncard : ℝ) * 2 ^ r := by apply mul_le_mul_of_nonneg_right _ (by positivity) exact_mod_cast hncard