kst_code_linear_construction_finite_field
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.
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.
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 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.
uses
Finset.sum_subset,kst_code_linear_construction_finite_field_syndrome,Finset.sum_congrlemma 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
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.
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]
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.
uses
kst_code_linear_construction_finite_field_syndrome,Finset.sum_add_distrib,symmDiff_def,CharTwo.add_self_eq_zerolemma 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]
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).
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_sumlemma 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)
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).
uses
Nat.prime_two,Fintype.ofFinite,LinearEquiv.ofFinrankEq,Module.finrank_fintype_fun_eq_card,Fintype.card_fin,GaloisField.finrankclassical 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)
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.
uses
map_sum,map_zerohave 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])
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.
uses
Set.mem_ofPred_eq,kst_code_linear_construction_finite_field_syndrome_symmDiff,add_zerolet 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]
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.
uses
dif_pos,Set.mem_ofPred_eq,kst_code_linear_construction_finite_field_syndrome_symmDiff,CharTwo.add_self_eq_zerolet 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 _
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.
uses
symmDiff_assoc,symmDiff_self,symmDiff_bot,Prod.fsthave 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 _ _
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).
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_poshave 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⟩
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.
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.inrrefine ⟨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
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.
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
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.
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.
- The codimension and density bounds are deduced by constructing an explicit injection from the space of all simple graphs into the Cartesian product of the syndrome field and the code C, rather than invoking abstract quotient module dimensions.
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 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