AFTD Auto-Formalizing Theoretical Domains

kst_code_linear_construction_finite_field

theoremverifiedformalization

Let n, s, t, r ≥ 1 be integers, and let w_1, ..., w_n in (ZMod 2)^r be vectors such that the sum of w_i over S is nonzero for every subset S of [n] with |S| in {s, t}. Then there exists a binary linear K_{s,t}-code C in the set of simple graphs on Fin n of codimension at most r (n.choose 2 - Nat.log 2 (Set.ncard C) ≤ r) and density at least (1/2)^r.

Statement

theorem kst_code_linear_construction_finite_field
    (n s t r : ℕ) (hn : 1 ≤ n) (hs : 1 ≤ s) (ht : 1 ≤ t) (hr : 1 ≤ r)
    (w : Fin n → Fin r → ZMod 2)
    (hw : ∀ S : Finset (Fin n), (S.card = s ∨ S.card = t) → ∑ i ∈ S, w i ≠ 0) :
    ∃ C : Set (SimpleGraph (Fin n)),
      is_kst_code s t n C ∧
      is_binary_linear_graph_code n C ∧
      n.choose 2 - Nat.log 2 (Set.ncard C) ≤ r ∧
      (1 / 2 : ℝ) ^ r ≤ (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ)
Formalizes
arXiv:2610.35136 Lemma 4.2
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • is_binary_linear_graph_codeA family C of simple graphs on vertex set [n] is a binary linear graph-code if it contains the empty graph and is closed under symmetric…
  • 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…
  • weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…

Read back from the Lean

Let $n, s, t, r$ be natural numbers such that $1 \le n$, $1 \le s$, $1 \le t$, and $1 \le r$. Let $w : \mathrm{Fin}\ n \to \mathrm{Fin}\ r \to \mathbb{Z}/2\mathbb{Z}$ be a function assigning to each vertex in $\mathrm{Fin}\ n$ a vector in $(\mathbb{Z}/2\mathbb{Z})^r$. Assume that for every subset $S \subseteq \mathrm{Fin}\ n$, if $|S| = s$ or $|S| = t$, then the coordinatewise sum $\sum_{i \in S} w(i)$ is non-zero in $(\mathbb{Z}/2\mathbb{Z})^r$. Then there exists a set $C$ of simple graphs on vertex set $\mathrm{Fin}\ n$ satisfying: 1. $C$ is a $K_{s,t}$-code: for all distinct graphs $G, G' \in C$ and all disjoint subsets $A, B \subseteq \mathrm{Fin}\ n$ with $|A| = s$ and $|B| = t$, the symmetric difference graph $G \mathbin{\Delta} G'$ is not equal to the complete bipartite graph between $A$ and $B$. 2. $C$ is a binary linear graph code: the empty graph $\bot$ is in $C$, and for all $G, G' \in C$, their symmetric difference $G \mathbin{\Delta} G'$ is also in $C$. 3. $\binom{n}{2} - \lfloor \log_2(|C|) \rfloor \le r$ (using natural number subtraction and $\lfloor \log_2 \cdot \rfloor$). 4. $(1/2)^r \le |C| / 2^{\binom{n}{2}}$ in the real numbers, where $|C| = \mathrm{Set.ncard}(C)$.

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 constructs the code C as the kernel of a syndrome map from simple graphs on Fin n to the Galois field GF(2^r), by linearly identifying (ZMod 2)^r with GF(2^r) and assigning to each graph G the edge-weight sum ∑_{e={i,j} ∈ E(G)} z_i z_j. Because the syndrome of a complete bipartite graph K_{A,B} factors as (∑_{a ∈ A} z_a)(∑_{b ∈ B} z_b), which cannot vanish when |A| = s and |B| = t, no two codewords differ by K_{s,t}, making C a K_{s,t}-code. Finally, the syndrome map partitions the 2^(n.choose 2) graphs into at most 2^r cosets of C via an explicit injection into GF(2^r) × C, giving 2^(n.choose 2) ≤ 2^r * |C|, which yields both the codimension bound and the density bound.

  1. Define the syndrome of a simple graph as the sum over all pairs of the edge weight z(i) * z(j) conditioned on membership in the edge set.

    For each unordered pair e = s(i, j), the edge weight is z(i) * z(j). The syndrome of G is defined by summing this weight over all e ∈ Sym2 (Fin n) when e ∈ G.edgeSet, and 0 otherwise.

    lines 11–16

    noncomputable def kst_code_linear_construction_finite_field_syndrome {n : ℕ} {F : Type*}
        [CommSemiring F] (z : Fin n → F) (G : SimpleGraph (Fin n)) : F := by
      classical
      exact ∑ e : Sym2 (Fin n),
        if e ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z e else 0
    
  2. The syndrome of a graph G equals the sum of edge weights over any finite set T whose elements are precisely the edges of G.

    Because pairs outside T do not belong to G.edgeSet, their terms in the sum are 0 (hg). Rewriting the sum over all pairs to a sum over T (Finset.sum_subset, kst_code_linear_construction_finite_field_syndrome) and simplifying the conditional (Finset.sum_congr) yields the restricted sum.

    lines 18–40

    uses Finset.sum_subset, kst_code_linear_construction_finite_field_syndrome, Finset.sum_congr

    lemma kst_code_linear_construction_finite_field_syndrome_eq_sum {n : ℕ} {F : Type*}
        [CommSemiring F] (z : Fin n → F) (G : SimpleGraph (Fin n)) (T : Finset (Sym2 (Fin n)))
        (hT : ∀ e, e ∈ T ↔ e ∈ G.edgeSet) :
        kst_code_linear_construction_finite_field_syndrome z G
          = ∑ e ∈ T, kst_code_linear_construction_finite_field_edge_weight z e := by
      classical
      have hg : ∀ x : Sym2 (Fin n), x ∉ T →
          (if x ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z x else 0) = 0 := by
        intro x hx
        split_ifs with h
        · exact absurd ((hT x).mpr h) hx
        · rfl
      have h1 : (∑ e : Sym2 (Fin n),
            (if e ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z e else 0))
          = ∑ e ∈ T,
            (if e ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z e else 0) :=
        (Finset.sum_subset (Finset.subset_univ T) (fun x _ hx => hg x hx)).symm
      rw [kst_code_linear_construction_finite_field_syndrome, h1]
      refine Finset.sum_congr rfl (fun e he => ?_)
      split_ifs with h
      · rfl
      · exact absurd ((hT e).mp he) h
    
  3. The empty graph ⊥ has syndrome 0.

    Since the empty graph has no edges, every term in the syndrome definition vanishes, so the sum evaluates to 0.

    lines 41–46

    uses kst_code_linear_construction_finite_field_syndrome

    @[simp] lemma kst_code_linear_construction_finite_field_syndrome_bot {n : ℕ} {F : Type*}
        [CommSemiring F] (z : Fin n → F) :
        kst_code_linear_construction_finite_field_syndrome z (⊥ : SimpleGraph (Fin n)) = 0 := by
      classical
      simp [kst_code_linear_construction_finite_field_syndrome]
    
  4. Over any commutative semiring of characteristic 2, the syndrome of the symmetric difference of two graphs is the sum of their individual syndromes.

    By definition of symmetric difference (symmDiff_def), an edge belongs to G Δ G' if and only if it belongs to exactly one of G or G'. Distributing the sum (Finset.sum_add_distrib), an edge present in both graphs contributes 0 to G Δ G' and weight + weight = 0 (CharTwo.add_self_eq_zero) to the sum of syndromes, so each summand agrees on both sides.

    lines 47–63

    uses kst_code_linear_construction_finite_field_syndrome, Finset.sum_add_distrib, symmDiff_def, CharTwo.add_self_eq_zero

    lemma kst_code_linear_construction_finite_field_syndrome_symmDiff {n : ℕ} {F : Type*}
        [CommSemiring F] [CharP F 2] (z : Fin n → F) (G G' : SimpleGraph (Fin n)) :
        kst_code_linear_construction_finite_field_syndrome z (symmDiff G G')
          = kst_code_linear_construction_finite_field_syndrome z G
            + kst_code_linear_construction_finite_field_syndrome z G' := by
      classical
      simp only [kst_code_linear_construction_finite_field_syndrome]
      rw [← Finset.sum_add_distrib]
      refine Finset.sum_congr rfl fun e _ => ?_
      have hmem : e ∈ (symmDiff G G').edgeSet ↔
          (e ∈ G.edgeSet ∧ e ∉ G'.edgeSet) ∨ (e ∉ G.edgeSet ∧ e ∈ G'.edgeSet) := by
        rw [symmDiff_def, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_sdiff, SimpleGraph.edgeSet_sdiff,
          Set.mem_union, Set.mem_sdiff, Set.mem_sdiff]
        tauto
      by_cases h1 : e ∈ G.edgeSet <;> by_cases h2 : e ∈ G'.edgeSet <;>
        simp [hmem, h1, h2, CharTwo.add_self_eq_zero]
    
  5. For disjoint sets A and B, the syndrome of the complete bipartite graph between A and B is (∑_{a ∈ A} z_a) * (∑_{b ∈ B} z_b).

    Because A and B are disjoint, the edges between A and B bijectively correspond to the product A × B. Using the restricted sum lemma (kst_code_linear_construction_finite_field_syndrome_eq_sum), the syndrome becomes a sum over A × B of edge weights z_a * z_b (Finset.sum_image, Finset.sum_product, kst_code_linear_construction_finite_field_edge_weight_mk), which factors into the product of the two vertex sums (Finset.sum_mul_sum).

    lines 64–104

    uses kst_code_linear_construction_finite_field_syndrome_eq_sum, Finset.sum_image, Finset.sum_product, kst_code_linear_construction_finite_field_edge_weight_mk, Finset.sum_mul_sum

    lemma kst_code_linear_construction_finite_field_syndrome_between {n : ℕ} {F : Type*}
        [CommSemiring F] (z : Fin n → F) (A B : Finset (Fin n)) (hAB : Disjoint A B) :
        kst_code_linear_construction_finite_field_syndrome z
            (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) (⊤ : SimpleGraph (Fin n)))
          = (∑ a ∈ A, z a) * (∑ b ∈ B, z b) := by
      classical
      have hset : (Finset.univ.filter (fun e : Sym2 (Fin n) =>
            e ∈ (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) (⊤ : SimpleGraph (Fin n))).edgeSet))
          = (A ×ˢ B).image (fun p : Fin n × Fin n => s(p.1, p.2)) := by
        ext e
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_product]
        constructor
        · intro he
          induction e using Sym2.ind with
          | _ v w =>
            rw [SimpleGraph.mem_edgeSet, SimpleGraph.between_adj, SimpleGraph.top_adj] at he
            obtain ⟨-, hv | hv⟩ := he
            · exact ⟨(v, w), ⟨hv.1, hv.2⟩, rfl⟩
            · exact ⟨(w, v), ⟨hv.2, hv.1⟩, (Sym2.eq_iff.mpr (Or.inr ⟨rfl, rfl⟩)).symm⟩
        · rintro ⟨p, ⟨hpa, hpb⟩, rfl⟩
          rw [SimpleGraph.mem_edgeSet, SimpleGraph.between_adj, SimpleGraph.top_adj]
          refine ⟨?_, Or.inl ⟨hpa, hpb⟩⟩
          intro h
          exact (Finset.disjoint_left.mp hAB hpa) (h ▸ hpb)
      have hT : ∀ e : Sym2 (Fin n), e ∈ (A ×ˢ B).image (fun p : Fin n × Fin n => s(p.1, p.2)) ↔
          e ∈ (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) (⊤ : SimpleGraph (Fin n))).edgeSet := by
        intro e
        rw [← hset, Finset.mem_filter]
        exact ⟨fun h => h.2, fun h => ⟨Finset.mem_univ _, h⟩⟩
      rw [kst_code_linear_construction_finite_field_syndrome_eq_sum z _ _ hT]
      rw [Finset.sum_image]
      · rw [Finset.sum_product]
        simp only [kst_code_linear_construction_finite_field_edge_weight_mk]
        rw [Finset.sum_mul_sum]
      · intro p hp q hq hpq
        simp only [Finset.mem_coe, Finset.mem_product] at hp hq
        rw [Sym2.eq_iff] at hpq
        rcases hpq with ⟨h1, h2⟩ | ⟨h1, h2⟩
        · exact Prod.ext h1 h2
        · exact absurd (h1 ▸ hq.2) (Finset.disjoint_left.mp hAB hp.1)
    
  6. Identify the vector space (ZMod 2)^r with the Galois field GF(2^r) and map each vector w_i to an element z_i in GF(2^r).

    Because 2 is prime (Nat.prime_two) and r ≥ 1, the Galois field GF(2^r) is an r-dimensional vector space over ZMod 2 (GaloisField.finrank). The coordinate space Fin r → ZMod 2 also has dimension r (Module.finrank_fintype_fun_eq_card, Fintype.card_fin). Equating their dimensions yields a linear equivalence φ between them (LinearEquiv.ofFinrankEq), through which we define z i = φ (w i) in GF(2^r).

    lines 115–123

    uses Nat.prime_two, Fintype.ofFinite, LinearEquiv.ofFinrankEq, Module.finrank_fintype_fun_eq_card, Fintype.card_fin, GaloisField.finrank

      classical
      haveI : Fact (Nat.Prime 2) := ⟨Nat.prime_two⟩
      haveI : Fintype (GaloisField 2 r) := Fintype.ofFinite _
      have hr0 : r ≠ 0 := by omega
      let φ : (Fin r → ZMod 2) ≃ₗ[ZMod 2] GaloisField 2 r :=
        LinearEquiv.ofFinrankEq _ _ (by
          rw [Module.finrank_fintype_fun_eq_card, Fintype.card_fin]
          exact (GaloisField.finrank 2 hr0).symm)
      let z : Fin n → GaloisField 2 r := fun i => φ (w i)
  7. For any subset S of [n] with |S| ∈ {s, t}, the sum of z_i over S is nonzero in GF(2^r).

    By linearity, the isomorphism φ commutes with finite sums (map_sum). If the sum of z_i over S were 0, applying the injectivity of φ (map_zero) would force the sum of w_i over S to be 0, directly contradicting the theorem's hypothesis hw.

    lines 124–131

    uses map_sum, map_zero

      have hz : ∀ S : Finset (Fin n), (S.card = s ∨ S.card = t) → ∑ i ∈ S, z i ≠ 0 := by
        intro S hS hsum0
        apply hw S hS
        have hmap : φ (∑ i ∈ S, w i) = ∑ i ∈ S, z i := by
          simp only [z]
          exact map_sum φ w S
        have h0 : φ (∑ i ∈ S, w i) = 0 := by rw [hmap]; exact hsum0
        exact φ.injective (by rw [h0, map_zero])
  8. The kernel C of the syndrome map contains the empty graph and is closed under symmetric difference, making it a binary linear graph code.

    The empty graph ⊥ has syndrome 0 by definition, so ⊥ ∈ C. By additivity of the syndrome under symmetric difference in characteristic 2 (kst_code_linear_construction_finite_field_syndrome_symmDiff), if G and G' have syndrome 0, then their symmetric difference has syndrome 0 + 0 = 0 (add_zero), so G Δ G' ∈ C.

    lines 132–138

    uses Set.mem_ofPred_eq, kst_code_linear_construction_finite_field_syndrome_symmDiff, add_zero

      let C : Set (SimpleGraph (Fin n)) := {G | kst_code_linear_construction_finite_field_syndrome z G = 0}
      have hCbot : (⊥ : SimpleGraph (Fin n)) ∈ C := by
        simp [C]
      have hCclos : ∀ G G' : SimpleGraph (Fin n), G ∈ C → G' ∈ C → symmDiff G G' ∈ C := by
        intro G G' hG hG'
        simp only [C, Set.mem_ofPred_eq] at hG hG' ⊢
        rw [kst_code_linear_construction_finite_field_syndrome_symmDiff, hG, hG', add_zero]
  9. Each achievable syndrome y has a representative graph rep(y), and for every graph G, G Δ rep(syndrome(G)) belongs to C.

    Using classical choice (dif_pos), rep(y) selects a graph with syndrome y whenever one exists. By linearity (kst_code_linear_construction_finite_field_syndrome_symmDiff), the syndrome of G Δ rep(syndrome(G)) is syndrome(G) + syndrome(G), which vanishes in characteristic 2 (CharTwo.add_self_eq_zero), placing G Δ rep(syndrome(G)) in C.

    lines 139–156

    uses dif_pos, Set.mem_ofPred_eq, kst_code_linear_construction_finite_field_syndrome_symmDiff, CharTwo.add_self_eq_zero

      let rep : GaloisField 2 r → SimpleGraph (Fin n) :=
        fun y => if h : ∃ G : SimpleGraph (Fin n),
          kst_code_linear_construction_finite_field_syndrome z G = y then h.choose else ⊥
      have hrep : ∀ (y : GaloisField 2 r)
          (hy : ∃ G : SimpleGraph (Fin n),
            kst_code_linear_construction_finite_field_syndrome z G = y),
          kst_code_linear_construction_finite_field_syndrome z (rep y) = y := by
        intro y hy
        simp only [rep]
        rw [dif_pos hy]
        exact hy.choose_spec
      have hmemC : ∀ G : SimpleGraph (Fin n),
          symmDiff G (rep (kst_code_linear_construction_finite_field_syndrome z G)) ∈ C := by
        intro G
        simp only [C, Set.mem_ofPred_eq]
        rw [kst_code_linear_construction_finite_field_syndrome_symmDiff,
          hrep (kst_code_linear_construction_finite_field_syndrome z G) ⟨G, rfl⟩]
        exact CharTwo.add_self_eq_zero _
  10. The map sending each graph G to the pair (syndrome(G), G Δ rep(syndrome(G))) in GF(2^r) × C is injective.

    Because symmetric difference cancels itself ((X Δ R) Δ R = X by symmDiff_assoc, symmDiff_self, symmDiff_bot), a graph G is uniquely recovered from its syndrome y and its coset component G Δ rep(y). Thus, if two graphs produce the same syndrome and the same element of C, they must be equal.

    lines 157–175

    uses symmDiff_assoc, symmDiff_self, symmDiff_bot, Prod.fst

      have hcancel : ∀ (X R : SimpleGraph (Fin n)), symmDiff (symmDiff X R) R = X := by
        intro X R
        rw [symmDiff_assoc, symmDiff_self, symmDiff_bot]
      have hinj : Function.Injective (fun G : SimpleGraph (Fin n) =>
          (kst_code_linear_construction_finite_field_syndrome z G,
            (⟨symmDiff G (rep (kst_code_linear_construction_finite_field_syndrome z G)),
              hmemC G⟩ : ↥C))) := by
        intro G1 G2 h
        have h1 : kst_code_linear_construction_finite_field_syndrome z G1
            = kst_code_linear_construction_finite_field_syndrome z G2 := congrArg Prod.fst h
        have h2 : symmDiff G1 (rep (kst_code_linear_construction_finite_field_syndrome z G1))
            = symmDiff G2 (rep (kst_code_linear_construction_finite_field_syndrome z G2)) :=
          congrArg (fun p : GaloisField 2 r × ↥C => ((p.2 : ↥C) : SimpleGraph (Fin n))) h
        rw [h1] at h2
        calc G1 = symmDiff (symmDiff G1 (rep (kst_code_linear_construction_finite_field_syndrome z G2)))
              (rep (kst_code_linear_construction_finite_field_syndrome z G2)) := (hcancel _ _).symm
          _ = symmDiff (symmDiff G2 (rep (kst_code_linear_construction_finite_field_syndrome z G2)))
              (rep (kst_code_linear_construction_finite_field_syndrome z G2)) := by rw [h2]
          _ = G2 := hcancel _ _
  11. The total number of graphs 2^(n.choose 2) is at most 2^r * |C|, and C is nonempty.

    The number of simple graphs on n vertices is 2^(n.choose 2) (card_simpleGraph, Fintype.card_fin), the Galois field has cardinality 2^r (GaloisField.card, Nat.card_eq_fintype_card), and |C| is its cardinality (Set.ncard_eq_toFinset_card', Set.toFinset_card). The injection into GF(2^r) × C implies the domain size cannot exceed the codomain size (Fintype.card_le_of_injective, Fintype.card_prod), giving 2^(n.choose 2) ≤ 2^r * |C|. Furthermore, |C| > 0 because ⊥ ∈ C (Set.ncard_pos).

    lines 176–187

    uses card_simpleGraph, Fintype.card_fin, Nat.card_eq_fintype_card, GaloisField.card, Set.ncard_eq_toFinset_card', Set.toFinset_card, Fintype.card_le_of_injective, Fintype.card_prod, Set.ncard_pos

      have hcardG : Fintype.card (SimpleGraph (Fin n)) = 2 ^ (n.choose 2) := by
        rw [card_simpleGraph, Fintype.card_fin]
      have hcardF : Fintype.card (GaloisField 2 r) = 2 ^ r := by
        rw [← Nat.card_eq_fintype_card, GaloisField.card 2 r hr0]
      have hcardC : Fintype.card ↥C = Set.ncard C := by
        rw [Set.ncard_eq_toFinset_card', Set.toFinset_card]
      have hmain : 2 ^ (n.choose 2) ≤ 2 ^ r * Set.ncard C := by
        have hle := Fintype.card_le_of_injective _ hinj
        rwa [Fintype.card_prod, hcardF, hcardC, hcardG] at hle
      have hCpos : 0 < Set.ncard C := by
        rw [Set.ncard_pos]
        exact ⟨⊥, hCbot⟩
  12. C is a K_{s,t}-code: no two distinct graphs in C have symmetric difference equal to a complete bipartite graph between sets of sizes s and t.

    For distinct G, G' ∈ C, linearity implies syndrome(G Δ G') = syndrome(G) + syndrome(G') = 0 (kst_code_linear_construction_finite_field_syndrome_symmDiff, add_zero). If G Δ G' were a complete bipartite graph between disjoint sets A and B with |A| = s and |B| = t, its syndrome would equal (∑_{a ∈ A} z_a) * (∑_{b ∈ B} z_b) (kst_code_linear_construction_finite_field_syndrome_between). But both vertex sums are nonzero in GF(2^r) (hz, Or.inl, Or.inr), and their product cannot be zero in a field (mul_ne_zero), giving a contradiction.

    lines 188–194

    uses Set.mem_ofPred_eq, kst_code_linear_construction_finite_field_syndrome_symmDiff, add_zero, kst_code_linear_construction_finite_field_syndrome_between, mul_ne_zero, Or.inl, Or.inr

      refine ⟨C, ?_, ⟨hCbot, hCclos⟩, ?_, ?_⟩
      · intro G G' hG hG' hne A B hAB hA hB hcontra
        simp only [C, Set.mem_ofPred_eq] at hG hG'
        have hzero : kst_code_linear_construction_finite_field_syndrome z (symmDiff G G') = 0 := by
          rw [kst_code_linear_construction_finite_field_syndrome_symmDiff, hG, hG', add_zero]
        rw [hcontra, kst_code_linear_construction_finite_field_syndrome_between z A B hAB] at hzero
        exact mul_ne_zero (hz A (Or.inl hA)) (hz B (Or.inr hB)) hzero
  13. The codimension of C is at most r: n.choose 2 - Nat.log 2 |C| ≤ r.

    From 2^(n.choose 2) ≤ 2^r * |C|, dividing by 2^r shows 2^(n.choose 2 - r) ≤ |C| (pow_add, Nat.add_sub_cancel', Nat.le_of_mul_le_mul_left, Nat.sub_eq_zero_of_le, pow_zero). Taking base-2 logarithms yields n.choose 2 - r ≤ Nat.log 2 |C| (Nat.le_log_iff_pow_le), from which linear integer arithmetic (omega) derives the desired codimension bound n.choose 2 - Nat.log 2 |C| ≤ r.

    lines 195–206

    uses pow_add, Nat.add_sub_cancel', Nat.le_of_mul_le_mul_left, Nat.sub_eq_zero_of_le, pow_zero, Nat.le_log_iff_pow_le

      · have hpow : 2 ^ (n.choose 2 - r) ≤ Set.ncard C := by
          by_cases h : r ≤ n.choose 2
          · have h2 : 2 ^ r * 2 ^ (n.choose 2 - r) ≤ 2 ^ r * Set.ncard C := by
              rw [← pow_add, Nat.add_sub_cancel' h]
              exact hmain
            exact Nat.le_of_mul_le_mul_left h2 (by positivity)
          · rw [Nat.sub_eq_zero_of_le (by omega : n.choose 2 ≤ r), pow_zero]
            omega
        have hlog : n.choose 2 - r ≤ Nat.log 2 (Set.ncard C) := by
          rw [Nat.le_log_iff_pow_le (by norm_num : 1 < 2) (by omega : Set.ncard C ≠ 0)]
          exact hpow
        omega
  14. The density of C is at least (1/2)^r: (1/2)^r ≤ |C| / 2^(n.choose 2).

    Casting the inequality 2^(n.choose 2) ≤ 2^r * |C| to real numbers and clearing denominators (div_pow, one_pow, div_le_div_iff₀, one_mul, mul_comm) transforms (1/2)^r ≤ |C| / 2^(n.choose 2) into 2^(n.choose 2) ≤ 2^r * |C|, which is precisely the cardinality bound established earlier.

    lines 207–211

    uses div_pow, one_pow, div_le_div_iff₀, one_mul, mul_comm

      · have hmainR : (2 : ℝ) ^ (n.choose 2) ≤ (2 : ℝ) ^ r * (Set.ncard C : ℝ) := by
          exact_mod_cast hmain
        rw [div_pow, one_pow, div_le_div_iff₀ (by positivity) (by positivity), one_mul,
          mul_comm (Set.ncard C : ℝ) ((2 : ℝ) ^ r)]
        exact hmainR
kst_code_linear_construction_finite_field_syndrome
The syndrome of a graph G with vertex weights z is the sum of z_i * z_j over edges {i,j} in G.
Finset.sum_subset
If s₁ ⊆ s₂ and the summand f vanishes on s₂ \ s₁, then the sum of f over s₁ equals the sum of f over s₂.
Finset.sum_congr
If two index sets are equal and the summands agree on all elements of the set, the sums are equal.
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of their individual sums.
symmDiff_def
The symmetric difference a Δ b is defined as (a \ b) ⊔ (b \ a).
kst_code_linear_construction_finite_field_syndrome_eq_sum
The syndrome of G equals the sum of edge weights over any finite set whose elements are precisely the edges of G.
Finset.sum_image
The sum of f over the image of an injective map g equals the sum of f ∘ g over the domain.
Finset.sum_product
A sum over a Cartesian product s ×ˢ t equals the iterated sum over s and t.
kst_code_linear_construction_finite_field_edge_weight_mk
The weight of an edge between vertices i and j is the product z i * z j.
Finset.sum_mul_sum
The product of two finite sums equals the double sum of the pairwise products of their terms.
Nat.prime_two
Two is a prime natural number.
Fintype.ofFinite
A finite type can be equipped with a Fintype instance.
LinearEquiv.ofFinrankEq
Two free modules of the same finite rank over a commutative ring are linearly equivalent.
Module.finrank_fintype_fun_eq_card
The rank of the module of functions from a finite type to the base ring equals the cardinality of the index type.
Fintype.card_fin
The cardinality of the standard finite set Fin n is n.
GaloisField.finrank
The dimension of the Galois field GF(p^n) as a vector space over ZMod p is n.
map_sum
A linear map or homomorphism distributes over finite sums.
map_zero
A zero-preserving map maps zero to zero.
Set.mem_ofPred_eq
Membership in a set comprehension {x | P x} is equivalent to P x.
kst_code_linear_construction_finite_field_syndrome_symmDiff
In characteristic 2, the syndrome of the symmetric difference of two graphs is the sum of their individual syndromes.
add_zero
Adding zero to an element leaves it unchanged.
dif_pos
A dependent conditional dite evaluates to its first branch when the condition is true.
CharTwo.add_self_eq_zero
In characteristic 2, adding any element to itself yields zero (x + x = 0).
symmDiff_assoc
Symmetric difference is associative: (a Δ b) Δ c = a Δ (b Δ c).
symmDiff_self
The symmetric difference of an element with itself is the empty element: a Δ a = ⊥.
symmDiff_bot
The symmetric difference of an element with the empty element is itself: a Δ ⊥ = a.
Prod.fst
The first projection of a pair (a, b) is a.
card_simpleGraph
The number of simple graphs on a finite vertex set V is 2^(|V|.choose 2).
Nat.card_eq_fintype_card
The Nat.card of a finite type equals its Fintype cardinality.
GaloisField.card
The cardinality of the Galois field GF(p, n) is p^n.
Set.ncard_eq_toFinset_card'
The cardinality of a finite set equals the cardinality of its coerced finset.
Set.toFinset_card
The cardinality of the finset coerced from a set equals the type-theoretic cardinality of the subtype.
Fintype.card_le_of_injective
An injective map between finite types implies the domain cardinality is at most the codomain cardinality.
Fintype.card_prod
The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Set.ncard_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
kst_code_linear_construction_finite_field_syndrome_between
The syndrome of the complete bipartite graph between disjoint sets A and B is the product of the vertex sums over A and B.
mul_ne_zero
In an integral domain, the product of two nonzero elements is nonzero.
Or.inl
Introduces a disjunction a ∨ b from a proof of a.
Or.inr
Introduces a disjunction a ∨ b from a proof of b.
pow_add
Powers with the same base satisfy a^(m + n) = a^m * a^n.
Nat.add_sub_cancel'
For natural numbers with m ≤ n, m + (n - m) = n.
Nat.le_of_mul_le_mul_left
If c * a ≤ c * b and c > 0 for natural numbers, then a ≤ b.
Nat.sub_eq_zero_of_le
If n ≤ m for natural numbers, then n - m = 0.
pow_zero
Any base raised to the power 0 equals 1.
Nat.le_log_iff_pow_le
For base b > 1 and y ≠ 0, x ≤ log_b y if and only if b^x ≤ y.
div_pow
Powers distribute over division: (a / b)^n = a^n / b^n.
one_pow
1 raised to any power is 1.
div_le_div_iff₀
For positive denominators, a / b ≤ c / d is equivalent to a * d ≤ c * b.
one_mul
Multiplying 1 by an element yields the element: 1 * a = a.
mul_comm
Multiplication is commutative: a * b = b * a.

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 weight `z i * z j` attached to an unordered pair of vertices. -/noncomputable def kst_code_linear_construction_finite_field_edge_weight {n : ℕ} {F : Type*}    [CommMonoid F] (z : Fin n → F) : Sym2 (Fin n) → F :=  Sym2.lift ⟨fun i j => z i * z j, fun i j => mul_comm (z i) (z j)⟩@[simp] lemma kst_code_linear_construction_finite_field_edge_weight_mk {n : ℕ} {F : Type*}    [CommMonoid F] (z : Fin n → F) (i j : Fin n) :    kst_code_linear_construction_finite_field_edge_weight z s(i, j) = z i * z j := rfl/-- The syndrome of a graph: the sum of `z i * z j` over its edges. -/noncomputable def kst_code_linear_construction_finite_field_syndrome {n : ℕ} {F : Type*}    [CommSemiring F] (z : Fin n → F) (G : SimpleGraph (Fin n)) : F := by  classical  exact ∑ e : Sym2 (Fin n),    if e ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z e else 0/-- The syndrome only depends on the set of edges. -/lemma kst_code_linear_construction_finite_field_syndrome_eq_sum {n : ℕ} {F : Type*}    [CommSemiring F] (z : Fin n → F) (G : SimpleGraph (Fin n)) (T : Finset (Sym2 (Fin n)))    (hT : ∀ e, e ∈ T ↔ e ∈ G.edgeSet) :    kst_code_linear_construction_finite_field_syndrome z G      = ∑ e ∈ T, kst_code_linear_construction_finite_field_edge_weight z e := by  classical  have hg : ∀ x : Sym2 (Fin n), x ∉ T →      (if x ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z x else 0) = 0 := by    intro x hx    split_ifs with h    · exact absurd ((hT x).mpr h) hx    · rfl  have h1 : (∑ e : Sym2 (Fin n),        (if e ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z e else 0))      = ∑ e ∈ T,        (if e ∈ G.edgeSet then kst_code_linear_construction_finite_field_edge_weight z e else 0) :=    (Finset.sum_subset (Finset.subset_univ T) (fun x _ hx => hg x hx)).symm  rw [kst_code_linear_construction_finite_field_syndrome, h1]  refine Finset.sum_congr rfl (fun e he => ?_)  split_ifs with h  · rfl  · exact absurd ((hT e).mp he) h@[simp] lemma kst_code_linear_construction_finite_field_syndrome_bot {n : ℕ} {F : Type*}    [CommSemiring F] (z : Fin n → F) :    kst_code_linear_construction_finite_field_syndrome z (⊥ : SimpleGraph (Fin n)) = 0 := by  classical  simp [kst_code_linear_construction_finite_field_syndrome]lemma kst_code_linear_construction_finite_field_syndrome_symmDiff {n : ℕ} {F : Type*}    [CommSemiring F] [CharP F 2] (z : Fin n → F) (G G' : SimpleGraph (Fin n)) :    kst_code_linear_construction_finite_field_syndrome z (symmDiff G G')      = kst_code_linear_construction_finite_field_syndrome z G        + kst_code_linear_construction_finite_field_syndrome z G' := by  classical  simp only [kst_code_linear_construction_finite_field_syndrome]  rw [← Finset.sum_add_distrib]  refine Finset.sum_congr rfl fun e _ => ?_  have hmem : e ∈ (symmDiff G G').edgeSet ↔      (e ∈ G.edgeSet ∧ e ∉ G'.edgeSet) ∨ (e ∉ G.edgeSet ∧ e ∈ G'.edgeSet) := by    rw [symmDiff_def, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_sdiff, SimpleGraph.edgeSet_sdiff,      Set.mem_union, Set.mem_sdiff, Set.mem_sdiff]    tauto  by_cases h1 : e ∈ G.edgeSet <;> by_cases h2 : e ∈ G'.edgeSet <;>    simp [hmem, h1, h2, CharTwo.add_self_eq_zero]lemma kst_code_linear_construction_finite_field_syndrome_between {n : ℕ} {F : Type*}    [CommSemiring F] (z : Fin n → F) (A B : Finset (Fin n)) (hAB : Disjoint A B) :    kst_code_linear_construction_finite_field_syndrome z        (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) (⊤ : SimpleGraph (Fin n)))      = (∑ a ∈ A, z a) * (∑ b ∈ B, z b) := by  classical  have hset : (Finset.univ.filter (fun e : Sym2 (Fin n) =>        e ∈ (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) (⊤ : SimpleGraph (Fin n))).edgeSet))      = (A ×ˢ B).image (fun p : Fin n × Fin n => s(p.1, p.2)) := by    ext e    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image, Finset.mem_product]    constructor    · intro he      induction e using Sym2.ind with      | _ v w =>        rw [SimpleGraph.mem_edgeSet, SimpleGraph.between_adj, SimpleGraph.top_adj] at he        obtain ⟨-, hv | hv⟩ := he        · exact ⟨(v, w), ⟨hv.1, hv.2⟩, rfl⟩        · exact ⟨(w, v), ⟨hv.2, hv.1⟩, (Sym2.eq_iff.mpr (Or.inr ⟨rfl, rfl⟩)).symm⟩    · rintro ⟨p, ⟨hpa, hpb⟩, rfl⟩      rw [SimpleGraph.mem_edgeSet, SimpleGraph.between_adj, SimpleGraph.top_adj]      refine ⟨?_, Or.inl ⟨hpa, hpb⟩⟩      intro h      exact (Finset.disjoint_left.mp hAB hpa) (h ▸ hpb)  have hT : ∀ e : Sym2 (Fin n), e ∈ (A ×ˢ B).image (fun p : Fin n × Fin n => s(p.1, p.2)) ↔      e ∈ (SimpleGraph.between (A : Set (Fin n)) (B : Set (Fin n)) (⊤ : SimpleGraph (Fin n))).edgeSet := by    intro e    rw [← hset, Finset.mem_filter]    exact ⟨fun h => h.2, fun h => ⟨Finset.mem_univ _, h⟩⟩  rw [kst_code_linear_construction_finite_field_syndrome_eq_sum z _ _ hT]  rw [Finset.sum_image]  · rw [Finset.sum_product]    simp only [kst_code_linear_construction_finite_field_edge_weight_mk]    rw [Finset.sum_mul_sum]  · intro p hp q hq hpq    simp only [Finset.mem_coe, Finset.mem_product] at hp hq    rw [Sym2.eq_iff] at hpq    rcases hpq with ⟨h1, h2⟩ | ⟨h1, h2⟩    · exact Prod.ext h1 h2    · exact absurd (h1 ▸ hq.2) (Finset.disjoint_left.mp hAB hp.1)/-- Linear graph-code construction via finite field multiplication (Lemma 4.2, arXiv:2610.35136). -/theorem kst_code_linear_construction_finite_field    (n s t r : ℕ) (hn : 1 ≤ n) (hs : 1 ≤ s) (ht : 1 ≤ t) (hr : 1 ≤ r)    (w : Fin n → Fin r → ZMod 2)    (hw : ∀ S : Finset (Fin n), (S.card = s ∨ S.card = t) → ∑ i ∈ S, w i ≠ 0) :    ∃ C : Set (SimpleGraph (Fin n)),      is_kst_code s t n C ∧      is_binary_linear_graph_code n C ∧      n.choose 2 - Nat.log 2 (Set.ncard C) ≤ r ∧      (1 / 2 : ℝ) ^ r ≤ (Set.ncard C : ℝ) / (2 ^ (n.choose 2) : ℝ) := by  classical  haveI : Fact (Nat.Prime 2) := ⟨Nat.prime_two⟩  haveI : Fintype (GaloisField 2 r) := Fintype.ofFinite _  have hr0 : r ≠ 0 := by omega  let φ : (Fin r → ZMod 2) ≃ₗ[ZMod 2] GaloisField 2 r :=    LinearEquiv.ofFinrankEq _ _ (by      rw [Module.finrank_fintype_fun_eq_card, Fintype.card_fin]      exact (GaloisField.finrank 2 hr0).symm)  let z : Fin n → GaloisField 2 r := fun i => φ (w i)  have hz : ∀ S : Finset (Fin n), (S.card = s ∨ S.card = t) → ∑ i ∈ S, z i ≠ 0 := by    intro S hS hsum0    apply hw S hS    have hmap : φ (∑ i ∈ S, w i) = ∑ i ∈ S, z i := by      simp only [z]      exact map_sum φ w S    have h0 : φ (∑ i ∈ S, w i) = 0 := by rw [hmap]; exact hsum0    exact φ.injective (by rw [h0, map_zero])  let C : Set (SimpleGraph (Fin n)) := {G | kst_code_linear_construction_finite_field_syndrome z G = 0}  have hCbot : (⊥ : SimpleGraph (Fin n)) ∈ C := by    simp [C]  have hCclos : ∀ G G' : SimpleGraph (Fin n), G ∈ C → G' ∈ C → symmDiff G G' ∈ C := by    intro G G' hG hG'    simp only [C, Set.mem_ofPred_eq] at hG hG' ⊢    rw [kst_code_linear_construction_finite_field_syndrome_symmDiff, hG, hG', add_zero]  let rep : GaloisField 2 r → SimpleGraph (Fin n) :=    fun y => if h : ∃ G : SimpleGraph (Fin n),      kst_code_linear_construction_finite_field_syndrome z G = y then h.choose else ⊥  have hrep : ∀ (y : GaloisField 2 r)      (hy : ∃ G : SimpleGraph (Fin n),        kst_code_linear_construction_finite_field_syndrome z G = y),      kst_code_linear_construction_finite_field_syndrome z (rep y) = y := by    intro y hy    simp only [rep]    rw [dif_pos hy]    exact hy.choose_spec  have hmemC : ∀ G : SimpleGraph (Fin n),      symmDiff G (rep (kst_code_linear_construction_finite_field_syndrome z G)) ∈ C := by    intro G    simp only [C, Set.mem_ofPred_eq]    rw [kst_code_linear_construction_finite_field_syndrome_symmDiff,      hrep (kst_code_linear_construction_finite_field_syndrome z G) ⟨G, rfl⟩]    exact CharTwo.add_self_eq_zero _  have hcancel : ∀ (X R : SimpleGraph (Fin n)), symmDiff (symmDiff X R) R = X := by    intro X R    rw [symmDiff_assoc, symmDiff_self, symmDiff_bot]  have hinj : Function.Injective (fun G : SimpleGraph (Fin n) =>      (kst_code_linear_construction_finite_field_syndrome z G,        (⟨symmDiff G (rep (kst_code_linear_construction_finite_field_syndrome z G)),          hmemC G⟩ : ↥C))) := by    intro G1 G2 h    have h1 : kst_code_linear_construction_finite_field_syndrome z G1        = kst_code_linear_construction_finite_field_syndrome z G2 := congrArg Prod.fst h    have h2 : symmDiff G1 (rep (kst_code_linear_construction_finite_field_syndrome z G1))        = symmDiff G2 (rep (kst_code_linear_construction_finite_field_syndrome z G2)) :=      congrArg (fun p : GaloisField 2 r × ↥C => ((p.2 : ↥C) : SimpleGraph (Fin n))) h    rw [h1] at h2    calc G1 = symmDiff (symmDiff G1 (rep (kst_code_linear_construction_finite_field_syndrome z G2)))          (rep (kst_code_linear_construction_finite_field_syndrome z G2)) := (hcancel _ _).symm      _ = symmDiff (symmDiff G2 (rep (kst_code_linear_construction_finite_field_syndrome z G2)))          (rep (kst_code_linear_construction_finite_field_syndrome z G2)) := by rw [h2]      _ = G2 := hcancel _ _  have hcardG : Fintype.card (SimpleGraph (Fin n)) = 2 ^ (n.choose 2) := by    rw [card_simpleGraph, Fintype.card_fin]  have hcardF : Fintype.card (GaloisField 2 r) = 2 ^ r := by    rw [← Nat.card_eq_fintype_card, GaloisField.card 2 r hr0]  have hcardC : Fintype.card ↥C = Set.ncard C := by    rw [Set.ncard_eq_toFinset_card', Set.toFinset_card]  have hmain : 2 ^ (n.choose 2) ≤ 2 ^ r * Set.ncard C := by    have hle := Fintype.card_le_of_injective _ hinj    rwa [Fintype.card_prod, hcardF, hcardC, hcardG] at hle  have hCpos : 0 < Set.ncard C := by    rw [Set.ncard_pos]    exact ⟨⊥, hCbot⟩  refine ⟨C, ?_, ⟨hCbot, hCclos⟩, ?_, ?_⟩  · intro G G' hG hG' hne A B hAB hA hB hcontra    simp only [C, Set.mem_ofPred_eq] at hG hG'    have hzero : kst_code_linear_construction_finite_field_syndrome z (symmDiff G G') = 0 := by      rw [kst_code_linear_construction_finite_field_syndrome_symmDiff, hG, hG', add_zero]    rw [hcontra, kst_code_linear_construction_finite_field_syndrome_between z A B hAB] at hzero    exact mul_ne_zero (hz A (Or.inl hA)) (hz B (Or.inr hB)) hzero  · have hpow : 2 ^ (n.choose 2 - r) ≤ Set.ncard C := by      by_cases h : r ≤ n.choose 2      · have h2 : 2 ^ r * 2 ^ (n.choose 2 - r) ≤ 2 ^ r * Set.ncard C := by          rw [← pow_add, Nat.add_sub_cancel' h]          exact hmain        exact Nat.le_of_mul_le_mul_left h2 (by positivity)      · rw [Nat.sub_eq_zero_of_le (by omega : n.choose 2 ≤ r), pow_zero]        omega    have hlog : n.choose 2 - r ≤ Nat.log 2 (Set.ncard C) := by      rw [Nat.le_log_iff_pow_le (by norm_num : 1 < 2) (by omega : Set.ncard C ≠ 0)]      exact hpow    omega  · have hmainR : (2 : ℝ) ^ (n.choose 2) ≤ (2 : ℝ) ^ r * (Set.ncard C : ℝ) := by      exact_mod_cast hmain    rw [div_pow, one_pow, div_le_div_iff₀ (by positivity) (by positivity), one_mul,      mul_comm (Set.ncard C : ℝ) ((2 : ℝ) ^ r)]    exact hmainR
See it in the graphDiscuss this resultChallenge it