AFTD Auto-Formalizing Theoretical Domains

k22_code_exists_dense_family_of_power_of_two

theoremverified

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.

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

    lines 6–11

    uses Fintype.ofFinite, Nat.card_eq_fintype_card, GaloisField.card, Fintype.card_fin, Fintype.equivFinOfCardEq

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

    lines 12–16

    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])
  3. 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.

    lines 17–18

    uses k22_code_max_density_two_pow_ge_fiber_code

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

    lines 19–25

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

    lines 26–32

    uses div_le_div_iff₀, one_mul, pow_add, Nat.sub_add_cancel, mul_le_mul_of_nonneg_right

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

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

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