gf8_oracle_t_count_ge_20
The slice-rank floor of arXiv:2610.01024 Proposition 59 at k = 3: every parity representation of the GF(8) multiplication oracle's syndrome has at least G(3) = 20 parities (every nonzero slice of the multiplication tensor has rank 6, so the column code is an even self-orthogonal [t, 9, 8] code, and the Griesmer bound gives t >= 20).
Statement
theorem gf8_oracle_t_count_ge_20 (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) : 20 ≤ S.card- Formalizes
- arXiv:2610.01024, Proposition 59 (slice-rank floor), special case k = 3
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_parity_reprA finite set S of nonempty parities on n qubits is a parity representation of a syndrome s if the moment of S at every non-empty subset A…
- gf8_oracle_syndromeThe syndrome s_A of the GF(8) multiplication phase oracle U_3 |x, y, z> = (-1)^{z . (x * y)} |x, y, z> on nine qubits: s_A = 1 iff A =…
- gf8_mult_coeffThe structure constants for multiplication in GF(8) with respect to the basis {1, alpha, alpha^2} with irreducible polynomial alpha^3 +…
- gf8_oracle_syndrome_singletonSanity check: the GF(8) oracle has no order-one syndrome.
- Used by 2
- monomial_mulFor any natural number s and any two finite subsets I and J of Fin s, the pointwise product of the coordinate monomials monomial I and…
- gf8_oracle_min_t_count_ge_20The slice-rank lower bound: the minimal T-count of the GF(8) multiplication oracle is at least 20.
The proof, explained
The theorem proves that every parity representation S of the GF(8) multiplication oracle syndrome has cardinality at least 20. Representing parities injectively as indicator vectors in 𝔽₂⁹, every nonzero linear functional has weight at least 8 on the resulting point set because every nonzero slice of the multiplication tensor has rank 6 (giving weight ≥ 7) and singleton syndromes vanish (forcing the weight to be even). Applying the Griesmer bound for binary linear codes to this 9-dimensional point set with minimum distance 8 yields |S| ≥ G(3) = 20.
Define the ordered and symmetrized GF(8) oracle syndrome on triples of qubits.
`gf8_syn_ord` defines the syndrome for qubits ordered across the three registers, using `Nat.mod_lt` (verified by `norm_num`) to ensure coordinate indices modulo 3 are strictly less than 3. `gf8_syn_sym` then sums over all six permutations of the three qubits.
uses
Nat.mod_lt/-- One ordered term of the GF(8) oracle syndrome on triples: `T(q, r, l)` when the three qubits lie in registers x, y, z in this order. -/ def gf8_syn_ord (a b c : Fin 9) : ZMod 2 := if a.val / 3 = 0 ∧ b.val / 3 = 1 ∧ c.val / 3 = 2 then gf8_mult_coeff ⟨a.val % 3, Nat.mod_lt _ (by norm_num)⟩ ⟨b.val % 3, Nat.mod_lt _ (by norm_num)⟩ ⟨c.val % 3, Nat.mod_lt _ (by norm_num)⟩ else 0 /-- The GF(8) oracle syndrome on triples, symmetrized over the six orders. -/ def gf8_syn_sym (i j k : Fin 9) : ZMod 2 := gf8_syn_ord i j k + gf8_syn_ord i k j + gf8_syn_ord j i k + gf8_syn_ord j k i + gf8_syn_ord k i j + gf8_syn_ord k j i
Basic evaluation of the syndrome on pairs, triples, and register indexing. automation
By exhaustive check (`decide`), the syndrome vanishes on every pair of qubits (`gf8_syndrome_pair`), agrees with the symmetrized syndrome on triples (`gf8_syndrome_triple`), and elements of 𝔽₂ are 0 or 1 (`gf8_zmod2_cases`). The qubit indexing `gf8_row b t = 3 * b + t` is shown to stay strictly below 9 using integer arithmetic (`omega`).
theorem gf8_syndrome_pair (i j : Fin 9) : gf8_oracle_syndrome {i, j} = 0 := by revert i j; decide theorem gf8_syndrome_triple (i j k : Fin 9) : gf8_oracle_syndrome {i, j, k} = gf8_syn_sym i j k := by revert i j k; decide theorem gf8_zmod2_cases (a : ZMod 2) : a = 0 ∨ a = 1 := by revert a; decide /-- Qubit `t` of register `b` (x = 0, y = 1, z = 2). -/ def gf8_row (b t : Fin 3) : Fin 9 := ⟨3 * b.val + t.val, by omega⟩ /-- The first register other than `β`. -/ def gf8_other1 (β : Fin 3) : Fin 3 := ![1, 0, 0] β /-- The second register other than `β`. -/ def gf8_other2 (β : Fin 3) : Fin 3 := ![2, 2, 1] β /-- The 3 × 3 block of a slice of the GF(8) syndrome tensor, contracted with `c` on register `β`, between the two other registers. -/ def gf8_amat (β : Fin 3) (c : Fin 3 → ZMod 2) : Matrix (Fin 3) (Fin 3) (ZMod 2) := Matrix.of fun q r => ∑ t, c t * gf8_syn_sym (gf8_row β t) (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r)
Symmetry and vanishing of off-register syndrome values.
The symmetrized syndrome `gf8_syn_sym` evaluates to 0 if one qubit lies outside the designated register β (`gf8_syn_sym_off`, by `decide`), or if two qubits lie in the same register (`gf8_syn_sym_same`, by `decide`). Swapping the last two qubit arguments is an invariance by ring symmetry (`gf8_syn_sym_swap`).
uses
gf8_syn_symtheorem gf8_syn_sym_off (β : Fin 3) (i : Fin 9) (q r : Fin 3) (hi : i.val / 3 ≠ β.val) : gf8_syn_sym i (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r) = 0 := by revert β i q r; decide theorem gf8_syn_sym_same (i j k : Fin 9) (h : j.val / 3 = k.val / 3) : gf8_syn_sym i j k = 0 := by revert i j k; decide theorem gf8_syn_sym_swap (i j k : Fin 9) : gf8_syn_sym i j k = gf8_syn_sym i k j := by unfold gf8_syn_sym; ring
Every nonzero 3 × 3 slice of the syndrome tensor is invertible.
Expanding the 3 × 3 determinant via `Matrix.det_fin_three`, finite exhaustion (`decide`) over all 3 × (2³ - 1) = 21 nonzero triples confirms that the determinant polynomial never vanishes on 𝔽₂. Therefore, whenever `c ≠ 0`, `det(gf8_amat β c) ≠ 0`.
uses
Matrix.det_fin_threetheorem gf8_amat_det (β : Fin 3) (c : Fin 3 → ZMod 2) (hc : c ≠ 0) : (gf8_amat β c).det ≠ 0 := by have key : ∀ (β : Fin 3) (c0 c1 c2 : ZMod 2), ¬(c0 = 0 ∧ c1 = 0 ∧ c2 = 0) → gf8_amat β ![c0, c1, c2] 0 0 * gf8_amat β ![c0, c1, c2] 1 1 * gf8_amat β ![c0, c1, c2] 2 2 - gf8_amat β ![c0, c1, c2] 0 0 * gf8_amat β ![c0, c1, c2] 1 2 * gf8_amat β ![c0, c1, c2] 2 1 - gf8_amat β ![c0, c1, c2] 0 1 * gf8_amat β ![c0, c1, c2] 1 0 * gf8_amat β ![c0, c1, c2] 2 2 + gf8_amat β ![c0, c1, c2] 0 1 * gf8_amat β ![c0, c1, c2] 1 2 * gf8_amat β ![c0, c1, c2] 2 0 + gf8_amat β ![c0, c1, c2] 0 2 * gf8_amat β ![c0, c1, c2] 1 0 * gf8_amat β ![c0, c1, c2] 2 1 - gf8_amat β ![c0, c1, c2] 0 2 * gf8_amat β ![c0, c1, c2] 1 1 * gf8_amat β ![c0, c1, c2] 2 0 ≠ 0 := by decide have hc' : c = ![c 0, c 1, c 2] := by ext t; fin_cases t <;> rfl rw [Matrix.det_fin_three, hc'] apply key rintro ⟨h0, h1, h2⟩ apply hc rw [hc'] ext t fin_cases t <;> simp [h0, h1, h2]
Contracting the syndrome on register β recovers the block matrix gf8_amat.
Using injectivity of `gf8_row β` (`Fin.ext`), the contraction over all 9 qubits is rewritten via `Finset.sum_image` and `Finset.sum_subset` as a sum over register β: all off-register terms vanish by `gf8_syn_sym_off`, matching the definition of `gf8_amat β c`.
uses
Fin.ext,Finset.sum_image,Finset.sum_subset,gf8_syn_sym_offtheorem gf8_block_sum (β : Fin 3) (lam : Fin 9 → ZMod 2) (q r : Fin 3) : ∑ i, lam i * gf8_syn_sym i (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r) = gf8_amat β (fun t => lam (gf8_row β t)) q r := by classical have hinj : ∀ x ∈ (Finset.univ : Finset (Fin 3)), ∀ y ∈ (Finset.univ : Finset (Fin 3)), gf8_row β x = gf8_row β y → x = y := by intro x _ y _ h simp only [gf8_row, Fin.mk.injEq] at h exact Fin.ext (by omega) simp only [gf8_amat, Matrix.of_apply] rw [← Finset.sum_image (f := fun i => lam i * gf8_syn_sym i (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r)) hinj] symm apply Finset.sum_subset (Finset.subset_univ _) intro i _ hi have hne : i.val / 3 ≠ β.val := by intro h apply hi refine Finset.mem_image.2 ⟨⟨i.val % 3, by omega⟩, Finset.mem_univ _, ?_⟩ ext simp only [gf8_row] omega rw [gf8_syn_sym_off β i q r hne, mul_zero]
The parity representation sum over odd parities expresses the contracted syndrome.
Using `Finset.sum_filter` and `Finset.sum_subset_zero_on_sdiff`, we split whether `i ∈ y`. Exchanging summations with `Finset.sum_comm`, each inner sum counts parities containing `insert i A`. By the defining property of a parity representation `hS`, this equals the syndrome value `gf8_oracle_syndrome (insert i A)`.
uses
Finset.sum_filter,Finset.sum_mul,Finset.sum_subset_zero_on_sdiff,gf8_zmod2_cases,Finset.sum_boole/-- Counting the parities of a representation that a functional `lam` sees as odd, weighted by `A ⊆ y`, gives a contraction of the syndrome. -/ theorem gf8_W_sum (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) (lam : Fin 9 → ZMod 2) (A : Finset (Fin 9)) (hA : A.card ≤ 2) : ∑ y ∈ S.filter (fun y => ∑ i ∈ y, lam i = 1), (if A ⊆ y then (1 : ZMod 2) else 0) = ∑ i, lam i * gf8_oracle_syndrome (insert i A) := by classical rw [Finset.sum_filter] have h1 : ∀ y : Finset (Fin 9), (if ∑ i ∈ y, lam i = 1 then (if A ⊆ y then (1 : ZMod 2) else 0) else 0) = ∑ i, lam i * (if insert i A ⊆ y then 1 else 0) := by intro y have h2 : ∑ i, lam i * (if insert i A ⊆ y then (1 : ZMod 2) else 0) = (∑ i ∈ y, lam i) * (if A ⊆ y then 1 else 0) := by rw [Finset.sum_mul] symm apply Finset.sum_subset_zero_on_sdiff (Finset.subset_univ y) · intro i hi have : i ∉ y := (Finset.mem_sdiff.1 hi).2 simp [Finset.insert_subset_iff, this] · intro i hi simp [Finset.insert_subset_iff, hi] rw [h2] rcases gf8_zmod2_cases (∑ i ∈ y, lam i) with h | h <;> simp [h] rw [Finset.sum_congr rfl fun y _ => h1 y, Finset.sum_comm] refine Finset.sum_congr rfl fun i _ => ?_ rw [← Finset.mul_sum, Finset.sum_boole] congr 1 apply hS.2 exact ⟨Finset.card_pos.2 (Finset.insert_nonempty _ _), (Finset.card_insert_le _ _).trans (by omega)⟩
The 6 × 6 incidence Gram matrix Z * Zᵀ has rank 6.
Choosing a register β where `lam` is non-trivial, we construct a 6 × |W| incidence matrix Z indexed by the other two registers. Evaluating entries using `gf8_W_sum` and `gf8_syndrome_triple` shows Z * Zᵀ is a 2 × 2 block matrix with anti-diagonal blocks A and Aᵀ (where A = `gf8_amat β c`). Since A is invertible by `gf8_amat_det`, the block matrix is invertible, so its rank is at least 6 by `Matrix.rank_mul_le_left`.
uses
gf8_W_sum,gf8_syndrome_triple,gf8_amat_det,gf8_block_sum,gf8_syn_sym_swap,Matrix.rank_mul_le_leftopen Matrix in theorem gf8_weight_ge_seven (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) (lam : Fin 9 → ZMod 2) (hlam : lam ≠ 0) : 7 ≤ (S.filter fun y => ∑ i ∈ y, lam i = 1).card := by classical set W := S.filter fun y => ∑ i ∈ y, lam i = 1 with hW have hsum := gf8_W_sum S hS lam obtain ⟨i0, hi0⟩ := Function.ne_iff.1 hlam let β : Fin 3 := ⟨i0.val / 3, by omega⟩ let c : Fin 3 → ZMod 2 := fun t => lam (gf8_row β t) have hc : c ≠ 0 := by intro h apply hi0 have h' : gf8_row β ⟨i0.val % 3, by omega⟩ = i0 := by ext simp only [gf8_row, β] omega rw [← h'] exact congrFun h _ let rowof : Fin 3 ⊕ Fin 3 → Fin 9 := Sum.elim (gf8_row (gf8_other1 β)) (gf8_row (gf8_other2 β)) let Z : Matrix (Fin 3 ⊕ Fin 3) W (ZMod 2) := fun a y => if rowof a ∈ y.1 then 1 else 0 let A := gf8_amat β c have hentry : ∀ a b, (Z * Zᵀ) a b = ∑ i, lam i * gf8_syn_sym i (rowof a) (rowof b) := by intro a b rw [Matrix.mul_apply] have : ∀ y : W, Z a y * Zᵀ y b = if ({rowof a, rowof b} : Finset (Fin 9)) ⊆ y.1 then 1 else 0 := by intro y show (if rowof a ∈ y.1 then (1 : ZMod 2) else 0) * (if rowof b ∈ y.1 then 1 else 0) = _ simp only [Finset.insert_subset_iff, Finset.singleton_subset_iff] split_ifs <;> simp_all rw [Finset.sum_congr rfl fun y _ => this y] rw [Finset.sum_coe_sort W (fun y => if ({rowof a, rowof b} : Finset (Fin 9)) ⊆ y then (1 : ZMod 2) else 0)] rw [hsum _ Finset.card_le_two] refine Finset.sum_congr rfl fun i _ => ?_ rw [gf8_syndrome_triple] have hblk1 : ∀ q, (rowof (Sum.inl q)).val / 3 = (gf8_other1 β).val := by intro q; simp only [rowof, Sum.elim_inl, gf8_row]; omega have hblk2 : ∀ q, (rowof (Sum.inr q)).val / 3 = (gf8_other2 β).val := by intro q; simp only [rowof, Sum.elim_inr, gf8_row]; omega have hZZ : Z * Zᵀ = Matrix.fromBlocks 0 A Aᵀ 0 := by ext a b rw [hentry] rcases a with q | q <;> rcases b with r | r · rw [Matrix.fromBlocks_apply₁₁, Matrix.zero_apply] exact Finset.sum_eq_zero fun i _ => by rw [gf8_syn_sym_same _ _ _ (by rw [hblk1, hblk1]), mul_zero] · rw [Matrix.fromBlocks_apply₁₂] exact gf8_block_sum β lam q r · rw [Matrix.fromBlocks_apply₂₁, Matrix.transpose_apply] show _ = gf8_amat β c r q rw [← gf8_block_sum β lam r q] exact Finset.sum_congr rfl fun i _ => by rw [gf8_syn_sym_swap]; rfl · rw [Matrix.fromBlocks_apply₂₂, Matrix.zero_apply] exact Finset.sum_eq_zero fun i _ => by rw [gf8_syn_sym_same _ _ _ (by rw [hblk2, hblk2]), mul_zero] have hA : IsUnit A.det := isUnit_iff_ne_zero.2 (gf8_amat_det β c hc) have hmul : Matrix.fromBlocks 0 A Aᵀ 0 * Matrix.fromBlocks 0 A⁻¹ᵀ A⁻¹ 0 = 1 := by rw [Matrix.fromBlocks_multiply, ← Matrix.fromBlocks_one] simp only [Matrix.zero_mul, Matrix.mul_zero, zero_add, add_zero, Matrix.mul_nonsing_inv _ hA, ← Matrix.transpose_mul, Matrix.nonsing_inv_mul _ hA, Matrix.transpose_one] have hN : 6 ≤ (Matrix.fromBlocks 0 A Aᵀ 0).rank := by have := Matrix.rank_mul_le_left (Matrix.fromBlocks 0 A Aᵀ 0) (Matrix.fromBlocks 0 A⁻¹ᵀ A⁻¹ 0) rw [hmul, Matrix.rank_one] at this simpa using this
Any nonzero functional takes value 1 on at least 7 parities.
The all-ones vector lies in the kernel of Z because contracting on singletons produces zero syndrome on pairs (`gf8_syndrome_pair`). By rank-nullity (`LinearMap.finrank_range_add_finrank_ker`), dim(ker Z) ≥ 1, so rank(Z) ≤ |W| - 1. Combining this with 6 ≤ rank(Z * Zᵀ) ≤ rank(Z) yields |W| ≥ 7.
uses
gf8_syndrome_pair,LinearMap.finrank_range_add_finrank_ker,Matrix.rank_mul_le_lefthave hcol : Z *ᵥ (fun _ => 1) = 0 := by funext a simp only [Matrix.mulVec, dotProduct, mul_one, Pi.zero_apply, Z] rw [Finset.sum_coe_sort W (fun y => if rowof a ∈ y then (1 : ZMod 2) else 0)] have := hsum {rowof a} (by simp) simp only [Finset.singleton_subset_iff] at this rw [this] exact Finset.sum_eq_zero fun i _ => by rw [gf8_syndrome_pair, mul_zero] have hrn := LinearMap.finrank_range_add_finrank_ker Z.mulVecLin rw [Module.finrank_fintype_fun_eq_card, Fintype.card_coe] at hrn have hker : 0 < W.card → 1 ≤ Module.finrank (ZMod 2) (LinearMap.ker Z.mulVecLin) := by intro hpos rw [Nat.one_le_iff_ne_zero] intro h0 rw [Submodule.finrank_eq_zero] at h0 have hmem : (fun _ => (1 : ZMod 2)) ∈ LinearMap.ker Z.mulVecLin := by rw [LinearMap.mem_ker, Matrix.mulVecLin_apply, hcol] rw [h0, Submodule.mem_bot] at hmem obtain ⟨y, hy⟩ := Finset.card_pos.1 hpos have := congrFun hmem ⟨y, hy⟩ simp at this have hle : (Z * Zᵀ).rank ≤ Z.rank := Matrix.rank_mul_le_left _ _ rw [hZZ] at hle unfold Matrix.rank at hle by_contra hlt push Not at hlt rcases Nat.eq_zero_or_pos W.card with h0 | hpos · have : Module.finrank (ZMod 2) (LinearMap.range Z.mulVecLin) ≤ 0 := by omega unfold Matrix.rank at hN omega · have := hker hpos unfold Matrix.rank at hN omega
Any nonzero functional takes value 1 on at least 8 parities.
Applying `gf8_W_sum` with A = ∅ shows |W| mod 2 = ∑ i, lam i * syndrome({i}) = 0, because singletons have zero syndrome (`gf8_oracle_syndrome_singleton`). By `ZMod.natCast_eq_zero_iff_even`, |W| is even. Since |W| ≥ 7 by `gf8_weight_ge_seven`, it follows that |W| ≥ 8.
uses
gf8_weight_ge_seven,gf8_W_sum,gf8_oracle_syndrome_singleton,ZMod.natCast_eq_zero_iff_eventheorem gf8_weight_ge_eight (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) (lam : Fin 9 → ZMod 2) (hlam : lam ≠ 0) : 8 ≤ (S.filter fun y => ∑ i ∈ y, lam i = 1).card := by classical have h7 := gf8_weight_ge_seven S hS lam hlam have heven : ((S.filter fun y => ∑ i ∈ y, lam i = 1).card : ZMod 2) = 0 := by have := gf8_W_sum S hS lam ∅ (by simp) simp only [Finset.empty_subset, ite_true, Finset.sum_const, nsmul_eq_mul, mul_one] at this rw [this] exact Finset.sum_eq_zero fun i _ => by rw [Finset.insert_empty, gf8_oracle_syndrome_singleton, mul_zero] obtain ⟨m, hm⟩ := (ZMod.natCast_eq_zero_iff_even).1 heven omega /-- The length bound `∑_{i<k} ⌈d / 2^i⌉` for binary linear codes, written recursively. -/ def binary_code_len_bound : ℕ → ℕ → ℕ | 0, _ => 0 | k + 1, d => d + binary_code_len_bound k ((d + 1) / 2) /-- Length bound for binary linear codes (by residual codes), in the language of point sets: if every nonzero linear functional on a `k`-dimensional `𝔽₂`-space takes the value `1` on at least `d` points of `P`, then `P` has at least `∑_{i<k} ⌈d / 2^i⌉` points. -/
Griesmer bound induction: codimension-1 projection and minimal functional.
By induction on k, we select a nonzero functional φ0 minimizing |{y ∈ P | φ0 y = 1}|. By duality (`Module.forall_dual_apply_eq_zero_iff`), such functionals exist. The hyperplane H = ker φ0 has dimension k by rank-nullity (`LinearMap.finrank_range_add_finrank_ker`), and P decomposes into P' = P ∩ H and points outside H.
uses
Module.forall_dual_apply_eq_zero_iff,Nat.find_spec,LinearMap.finrank_range_add_finrank_kertheorem binary_points_len_bound : ∀ (k : ℕ) (V : Type) [AddCommGroup V] [Module (ZMod 2) V] [FiniteDimensional (ZMod 2) V], Module.finrank (ZMod 2) V = k → ∀ (P : Finset V) (d : ℕ), (∀ φ : Module.Dual (ZMod 2) V, φ ≠ 0 → d ≤ (P.filter fun y => φ y = 1).card) → binary_code_len_bound k d ≤ P.card := by intro k induction k with | zero => intros; simp [binary_code_len_bound] | succ k ih => intro V _ _ _ hk P d hP classical have hnt : Nontrivial V := Module.nontrivial_of_finrank_pos (R := ZMod 2) (by omega) have hex : ∃ m, ∃ φ : Module.Dual (ZMod 2) V, φ ≠ 0 ∧ (P.filter fun y => φ y = 1).card = m := by obtain ⟨v, hv⟩ := exists_ne (0 : V) obtain ⟨φ, hφ⟩ : ∃ φ : Module.Dual (ZMod 2) V, φ v ≠ 0 := by by_contra h push Not at h exact hv ((Module.forall_dual_apply_eq_zero_iff (ZMod 2) v).1 h) exact ⟨_, φ, fun h => hφ (by simp [h]), rfl⟩ obtain ⟨φ0, hφ0, hw0⟩ := Nat.find_spec hex have hmin : ∀ φ : Module.Dual (ZMod 2) V, φ ≠ 0 → Nat.find hex ≤ (P.filter fun y => φ y = 1).card := fun φ hφ => Nat.find_min' hex ⟨φ, hφ, rfl⟩ have hdw : d ≤ Nat.find hex := hw0 ▸ hP φ0 hφ0 obtain ⟨v0, hv0⟩ : ∃ v, φ0 v ≠ 0 := by by_contra h push Not at h exact hφ0 (LinearMap.ext h) have hv01 : φ0 v0 = 1 := (gf8_zmod2_cases _).resolve_left hv0 let H := LinearMap.ker φ0 have hH : Module.finrank (ZMod 2) H = k := by have h1 := LinearMap.finrank_range_add_finrank_ker φ0 have h2 : LinearMap.range φ0 = ⊤ := by rw [LinearMap.range_eq_top] intro b rcases gf8_zmod2_cases b with rfl | rfl · exact ⟨0, map_zero _⟩ · exact ⟨v0, hv01⟩ rw [h2, finrank_top, Module.finrank_self] at h1 show Module.finrank (ZMod 2) (LinearMap.ker φ0) = k omega let P' : Finset H := P.subtype (· ∈ H) have hcount : ∀ (p q : V → Prop) [DecidablePred p] [DecidablePred q], (∀ y, (if p y then 1 else 0) + (if q y then 1 else 0) = 1) → (P.filter p).card + (P.filter q).card = P.card := by intro p q _ _ h rw [Finset.card_filter, Finset.card_filter, ← Finset.sum_add_distrib] rw [Finset.card_eq_sum_ones] exact Finset.sum_congr rfl fun y _ => h y have hP' : P'.card = (P.filter fun y => φ0 y = 0).card := by rw [Finset.card_subtype] exact congrArg Finset.card (Finset.filter_congr fun y _ => LinearMap.mem_ker) have hsplit : (P.filter fun y => φ0 y = 0).card + (P.filter fun y => φ0 y = 1).card = P.card := by apply hcount intro y rcases gf8_zmod2_cases (φ0 y) with h | h <;> simp [h]
Griesmer bound induction: inductive step via functional extension.
Every nonzero functional ψ on H extends via `LinearMap.exists_extend` to two distinct functionals φ and φ + φ0 on V. Summing their weights on P shows 2 * |{y ∈ P' | ψ y = 1}| + |{y ∈ P | φ0 y = 1}| ≥ 2 * d, so ψ takes value 1 on at least ⌈d / 2⌉ points of P'. Applying the inductive hypothesis on H yields the bound.
uses
LinearMap.exists_extend,LinearMap.add_apply,gf8_zmod2_caseshave hrec : ∀ ψ : Module.Dual (ZMod 2) H, ψ ≠ 0 → (d + 1) / 2 ≤ (P'.filter fun y => ψ y = 1).card := by intro ψ hψ obtain ⟨φ, hφ⟩ := LinearMap.exists_extend ψ have hφH : ∀ y : H, φ y = ψ y := fun y => by rw [← hφ] rfl have hne1 : φ ≠ 0 := by rintro rfl apply hψ ext y rw [← hφH] rfl have hne2 : φ + φ0 ≠ 0 := by intro h0 apply hψ ext y have : (φ + φ0) y = 0 := by rw [h0]; rfl rw [LinearMap.add_apply, LinearMap.mem_ker.1 y.2, add_zero] at this rw [← hφH, this] rfl have c1 := hmin φ hne1 have c2 := hmin (φ + φ0) hne2 have hmap : (P'.filter fun y => ψ y = 1).map (Function.Embedding.subtype _) = P.filter fun y => φ0 y = 0 ∧ φ y = 1 := by ext y constructor · intro hy obtain ⟨y', hy', rfl⟩ := Finset.mem_map.1 hy rw [Finset.mem_filter, Finset.mem_subtype] at hy' refine Finset.mem_filter.2 ⟨hy'.1, LinearMap.mem_ker.1 y'.2, ?_⟩ show φ (y' : V) = 1 rw [hφH] exact hy'.2 · intro hy rw [Finset.mem_filter] at hy refine Finset.mem_map.2 ⟨⟨y, LinearMap.mem_ker.2 hy.2.1⟩, Finset.mem_filter.2 ⟨Finset.mem_subtype.2 hy.1, ?_⟩, rfl⟩ rw [← hφH] exact hy.2.2 have hr : (P'.filter fun y => ψ y = 1).card = (P.filter fun y => φ0 y = 0 ∧ φ y = 1).card := by rw [← hmap, Finset.card_map] have hsum : (P.filter fun y => φ y = 1).card + (P.filter fun y => (φ + φ0) y = 1).card = 2 * (P.filter fun y => φ0 y = 0 ∧ φ y = 1).card + (P.filter fun y => φ0 y = 1).card := by simp only [Finset.card_filter, ← Finset.sum_add_distrib, Finset.mul_sum] refine Finset.sum_congr rfl fun y _ => ?_ rw [LinearMap.add_apply] rcases gf8_zmod2_cases (φ y) with h1 | h1 <;> rcases gf8_zmod2_cases (φ0 y) with h2 | h2 <;> simp [h1, h2] rw [hr] omega have := ih H hH P' ((d + 1) / 2) hrec show d + binary_code_len_bound k ((d + 1) / 2) ≤ P.card omega
Embedding parities into 𝔽₂⁹ reduces the bound to the Griesmer point bound.
Parity subsets are mapped to indicator vectors in 𝔽₂⁹ via `ind`. Injectivity of `ind` ensures |image ind S| = |S| (`Finset.card_image_of_injective`). Applying `binary_points_len_bound` with k = 9 and d = 8, and computing `binary_code_len_bound 9 8 = 20` by decision procedure, reduces the theorem to showing that every nonzero functional has weight at least 8.
uses
congrFun,binary_points_len_bound,Module.finrank_fin_fun,Finset.card_image_of_injective,binary_code_len_boundtheorem gf8_oracle_t_count_ge_20 (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) : 20 ≤ S.card := by classical let ind : Finset (Fin 9) → (Fin 9 → ZMod 2) := fun y i => if i ∈ y then 1 else 0 have hinj : Function.Injective ind := by intro y y' h ext i have := congrFun h i simp only [ind] at this by_cases h1 : i ∈ y <;> by_cases h2 : i ∈ y' <;> simp_all have hG := binary_points_len_bound 9 (Fin 9 → ZMod 2) (Module.finrank_fin_fun (ZMod 2)) (S.image ind) 8 ?_ · rw [Finset.card_image_of_injective _ hinj] at hG have h20 : binary_code_len_bound 9 8 = 20 := by decide
Every nonzero functional has weight at least 8 on the embedded representation, concluding |S| ≥ 20.
Every nonzero functional φ on 𝔽₂⁹ corresponds via `LinearMap.pi_apply_eq_sum_univ` to a nonzero vector `lam`. Under this correspondence, evaluating φ on the indicator of y gives the sum of `lam` over y. By `gf8_weight_ge_eight`, at least 8 parities in S have this sum equal to 1, completing the hypothesis of the Griesmer bound.
uses
LinearMap.pi_apply_eq_sum_univ,LinearMap.ext,Finset.filter_image,Finset.card_image_of_injective,gf8_weight_ge_eightomega · intro φ hφ let lam : Fin 9 → ZMod 2 := fun i => φ (fun j => if i = j then 1 else 0) have hφv : ∀ x, φ x = ∑ i, x i * lam i := fun x => by rw [LinearMap.pi_apply_eq_sum_univ] rfl have hlam : lam ≠ 0 := by intro h apply hφ refine LinearMap.ext fun x => ?_ rw [hφv] simp [h] have hind : ∀ y, φ (ind y) = ∑ i ∈ y, lam i := by intro y rw [hφv] simp only [ind, ite_mul, one_mul, zero_mul] rw [Finset.sum_ite_mem, Finset.univ_inter] rw [Finset.filter_image, Finset.card_image_of_injective _ hinj] simp only [hind] exact gf8_weight_ge_eight S hS lam hlam
binary_code_len_bound- The recursive binary Griesmer length bound: bound 0 d = 0, and bound (k + 1) d = d + bound k ⌈d / 2⌉.
binary_points_len_bound- For any point set P in a k-dimensional vector space over 𝔽₂, if every nonzero dual functional takes value 1 on at least d points of P, then P has at least binary_code_len_bound k d points.
congrFun- Two functions are equal implies they take equal values on any input.
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Finset.card_image_of_injective- The cardinality of the image of a finite set under an injective map equals the cardinality of the original set.
Finset.filter_image- Filtering an image by a predicate equals the image of the set filtered by the precomposed predicate.
Finset.sum_boole- The sum of boolean indicators over a finite set equals the cardinality of the filtered set.
Finset.sum_filter- Summing over a filtered set equals summing over the whole set with an indicator conditional.
Finset.sum_image- The sum of a function over the image of an injective map equals the sum over the domain.
Finset.sum_mul- Right-distributivity of multiplication over a finite sum.
Finset.sum_subset- If s₁ ⊆ s₂ and the summand vanishes on s₂ \ s₁, the sum over s₁ equals the sum over s₂.
Finset.sum_subset_zero_on_sdiff- Two finite sums agree if the terms agree on the subset and vanish on the set difference.
gf8_amat_det- For any nonzero vector c in 𝔽₂³, the 3 × 3 slice matrix gf8_amat β c has nonzero determinant.
gf8_block_sum- Contracting the symmetrized syndrome with lam on one register recovers the matrix entry of gf8_amat β c.
gf8_oracle_syndrome_singleton- The GF(8) oracle syndrome evaluates to 0 on any single qubit.
gf8_syn_sym- The symmetrized GF(8) multiplication syndrome on three qubits, summed over all six permutations of the triple.
gf8_syn_sym_off- The symmetrized syndrome vanishes when one qubit does not lie in the expected register β for that slice.
gf8_syn_sym_swap- The symmetrized syndrome is symmetric under swapping its second and third qubit arguments.
gf8_syndrome_pair- The GF(8) oracle syndrome evaluates to 0 on any pair of qubits.
gf8_syndrome_triple- The syndrome on any triple of qubits equals the symmetrized syndrome gf8_syn_sym.
gf8_W_sum- Summing the indicator of A ⊆ y over odd parities of a functional lam computes the contracted syndrome ∑ i, lam i * syndrome(insert i A).
gf8_weight_ge_eight- Every nonzero functional on 𝔽₂⁹ takes value 1 on at least 8 parities in any parity representation of the syndrome.
gf8_weight_ge_seven- Every nonzero functional on 𝔽₂⁹ takes value 1 on at least 7 parities in any parity representation of the syndrome.
gf8_zmod2_cases- Every element of ZMod 2 (𝔽₂) is either 0 or 1.
LinearMap.add_apply- The evaluation of the sum of two linear maps on a vector is the sum of their individual evaluations.
LinearMap.exists_extend- Any linear functional on a subspace can be extended to a linear functional on the whole ambient space.
LinearMap.ext- Two linear maps are equal if they agree on all inputs.
LinearMap.finrank_range_add_finrank_ker- The rank-nullity theorem: the dimension of the range plus the dimension of the kernel equals the dimension of the domain.
LinearMap.pi_apply_eq_sum_univ- Any linear functional on a finite-dimensional coordinate space is given by the standard dot product with its basis values.
Matrix.det_fin_three- The Leibniz determinant formula for a 3 × 3 matrix over a commutative ring.
Matrix.rank_mul_le_left- The rank of a matrix product A * B is at most the rank of A.
Module.finrank_fin_fun- The dimension of the function space Fin n → R over a field R is n.
Module.forall_dual_apply_eq_zero_iff- A vector in a module is zero if and only if every linear functional evaluates to zero on it.
Nat.find_spec- The least natural number satisfying an existential predicate satisfies that predicate.
Nat.mod_lt- If 0 < y, then x % y < y for natural numbers.
ZMod.natCast_eq_zero_iff_even- An integer cast to ZMod 2 is zero if and only if the integer is even.
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.
/-- One ordered term of the GF(8) oracle syndrome on triples: `T(q, r, l)` when the threequbits lie in registers x, y, z in this order. -/def gf8_syn_ord (a b c : Fin 9) : ZMod 2 := if a.val / 3 = 0 ∧ b.val / 3 = 1 ∧ c.val / 3 = 2 then gf8_mult_coeff ⟨a.val % 3, Nat.mod_lt _ (by norm_num)⟩ ⟨b.val % 3, Nat.mod_lt _ (by norm_num)⟩ ⟨c.val % 3, Nat.mod_lt _ (by norm_num)⟩ else 0/-- The GF(8) oracle syndrome on triples, symmetrized over the six orders. -/def gf8_syn_sym (i j k : Fin 9) : ZMod 2 := gf8_syn_ord i j k + gf8_syn_ord i k j + gf8_syn_ord j i k + gf8_syn_ord j k i + gf8_syn_ord k i j + gf8_syn_ord k j itheorem gf8_syndrome_pair (i j : Fin 9) : gf8_oracle_syndrome {i, j} = 0 := by revert i j; decidetheorem gf8_syndrome_triple (i j k : Fin 9) : gf8_oracle_syndrome {i, j, k} = gf8_syn_sym i j k := by revert i j k; decidetheorem gf8_zmod2_cases (a : ZMod 2) : a = 0 ∨ a = 1 := by revert a; decide/-- Qubit `t` of register `b` (x = 0, y = 1, z = 2). -/def gf8_row (b t : Fin 3) : Fin 9 := ⟨3 * b.val + t.val, by omega⟩/-- The first register other than `β`. -/def gf8_other1 (β : Fin 3) : Fin 3 := ![1, 0, 0] β/-- The second register other than `β`. -/def gf8_other2 (β : Fin 3) : Fin 3 := ![2, 2, 1] β/-- The 3 × 3 block of a slice of the GF(8) syndrome tensor, contracted with `c` on register `β`,between the two other registers. -/def gf8_amat (β : Fin 3) (c : Fin 3 → ZMod 2) : Matrix (Fin 3) (Fin 3) (ZMod 2) := Matrix.of fun q r => ∑ t, c t * gf8_syn_sym (gf8_row β t) (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r)theorem gf8_syn_sym_off (β : Fin 3) (i : Fin 9) (q r : Fin 3) (hi : i.val / 3 ≠ β.val) : gf8_syn_sym i (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r) = 0 := by revert β i q r; decidetheorem gf8_syn_sym_same (i j k : Fin 9) (h : j.val / 3 = k.val / 3) : gf8_syn_sym i j k = 0 := by revert i j k; decidetheorem gf8_syn_sym_swap (i j k : Fin 9) : gf8_syn_sym i j k = gf8_syn_sym i k j := by unfold gf8_syn_sym; ringtheorem gf8_amat_det (β : Fin 3) (c : Fin 3 → ZMod 2) (hc : c ≠ 0) : (gf8_amat β c).det ≠ 0 := by have key : ∀ (β : Fin 3) (c0 c1 c2 : ZMod 2), ¬(c0 = 0 ∧ c1 = 0 ∧ c2 = 0) → gf8_amat β ![c0, c1, c2] 0 0 * gf8_amat β ![c0, c1, c2] 1 1 * gf8_amat β ![c0, c1, c2] 2 2 - gf8_amat β ![c0, c1, c2] 0 0 * gf8_amat β ![c0, c1, c2] 1 2 * gf8_amat β ![c0, c1, c2] 2 1 - gf8_amat β ![c0, c1, c2] 0 1 * gf8_amat β ![c0, c1, c2] 1 0 * gf8_amat β ![c0, c1, c2] 2 2 + gf8_amat β ![c0, c1, c2] 0 1 * gf8_amat β ![c0, c1, c2] 1 2 * gf8_amat β ![c0, c1, c2] 2 0 + gf8_amat β ![c0, c1, c2] 0 2 * gf8_amat β ![c0, c1, c2] 1 0 * gf8_amat β ![c0, c1, c2] 2 1 - gf8_amat β ![c0, c1, c2] 0 2 * gf8_amat β ![c0, c1, c2] 1 1 * gf8_amat β ![c0, c1, c2] 2 0 ≠ 0 := by decide have hc' : c = ![c 0, c 1, c 2] := by ext t; fin_cases t <;> rfl rw [Matrix.det_fin_three, hc'] apply key rintro ⟨h0, h1, h2⟩ apply hc rw [hc'] ext t fin_cases t <;> simp [h0, h1, h2]theorem gf8_block_sum (β : Fin 3) (lam : Fin 9 → ZMod 2) (q r : Fin 3) : ∑ i, lam i * gf8_syn_sym i (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r) = gf8_amat β (fun t => lam (gf8_row β t)) q r := by classical have hinj : ∀ x ∈ (Finset.univ : Finset (Fin 3)), ∀ y ∈ (Finset.univ : Finset (Fin 3)), gf8_row β x = gf8_row β y → x = y := by intro x _ y _ h simp only [gf8_row, Fin.mk.injEq] at h exact Fin.ext (by omega) simp only [gf8_amat, Matrix.of_apply] rw [← Finset.sum_image (f := fun i => lam i * gf8_syn_sym i (gf8_row (gf8_other1 β) q) (gf8_row (gf8_other2 β) r)) hinj] symm apply Finset.sum_subset (Finset.subset_univ _) intro i _ hi have hne : i.val / 3 ≠ β.val := by intro h apply hi refine Finset.mem_image.2 ⟨⟨i.val % 3, by omega⟩, Finset.mem_univ _, ?_⟩ ext simp only [gf8_row] omega rw [gf8_syn_sym_off β i q r hne, mul_zero]/-- Counting the parities of a representation that a functional `lam` sees as odd, weighted by`A ⊆ y`, gives a contraction of the syndrome. -/theorem gf8_W_sum (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) (lam : Fin 9 → ZMod 2) (A : Finset (Fin 9)) (hA : A.card ≤ 2) : ∑ y ∈ S.filter (fun y => ∑ i ∈ y, lam i = 1), (if A ⊆ y then (1 : ZMod 2) else 0) = ∑ i, lam i * gf8_oracle_syndrome (insert i A) := by classical rw [Finset.sum_filter] have h1 : ∀ y : Finset (Fin 9), (if ∑ i ∈ y, lam i = 1 then (if A ⊆ y then (1 : ZMod 2) else 0) else 0) = ∑ i, lam i * (if insert i A ⊆ y then 1 else 0) := by intro y have h2 : ∑ i, lam i * (if insert i A ⊆ y then (1 : ZMod 2) else 0) = (∑ i ∈ y, lam i) * (if A ⊆ y then 1 else 0) := by rw [Finset.sum_mul] symm apply Finset.sum_subset_zero_on_sdiff (Finset.subset_univ y) · intro i hi have : i ∉ y := (Finset.mem_sdiff.1 hi).2 simp [Finset.insert_subset_iff, this] · intro i hi simp [Finset.insert_subset_iff, hi] rw [h2] rcases gf8_zmod2_cases (∑ i ∈ y, lam i) with h | h <;> simp [h] rw [Finset.sum_congr rfl fun y _ => h1 y, Finset.sum_comm] refine Finset.sum_congr rfl fun i _ => ?_ rw [← Finset.mul_sum, Finset.sum_boole] congr 1 apply hS.2 exact ⟨Finset.card_pos.2 (Finset.insert_nonempty _ _), (Finset.card_insert_le _ _).trans (by omega)⟩open Matrix intheorem gf8_weight_ge_seven (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) (lam : Fin 9 → ZMod 2) (hlam : lam ≠ 0) : 7 ≤ (S.filter fun y => ∑ i ∈ y, lam i = 1).card := by classical set W := S.filter fun y => ∑ i ∈ y, lam i = 1 with hW have hsum := gf8_W_sum S hS lam obtain ⟨i0, hi0⟩ := Function.ne_iff.1 hlam let β : Fin 3 := ⟨i0.val / 3, by omega⟩ let c : Fin 3 → ZMod 2 := fun t => lam (gf8_row β t) have hc : c ≠ 0 := by intro h apply hi0 have h' : gf8_row β ⟨i0.val % 3, by omega⟩ = i0 := by ext simp only [gf8_row, β] omega rw [← h'] exact congrFun h _ let rowof : Fin 3 ⊕ Fin 3 → Fin 9 := Sum.elim (gf8_row (gf8_other1 β)) (gf8_row (gf8_other2 β)) let Z : Matrix (Fin 3 ⊕ Fin 3) W (ZMod 2) := fun a y => if rowof a ∈ y.1 then 1 else 0 let A := gf8_amat β c have hentry : ∀ a b, (Z * Zᵀ) a b = ∑ i, lam i * gf8_syn_sym i (rowof a) (rowof b) := by intro a b rw [Matrix.mul_apply] have : ∀ y : W, Z a y * Zᵀ y b = if ({rowof a, rowof b} : Finset (Fin 9)) ⊆ y.1 then 1 else 0 := by intro y show (if rowof a ∈ y.1 then (1 : ZMod 2) else 0) * (if rowof b ∈ y.1 then 1 else 0) = _ simp only [Finset.insert_subset_iff, Finset.singleton_subset_iff] split_ifs <;> simp_all rw [Finset.sum_congr rfl fun y _ => this y] rw [Finset.sum_coe_sort W (fun y => if ({rowof a, rowof b} : Finset (Fin 9)) ⊆ y then (1 : ZMod 2) else 0)] rw [hsum _ Finset.card_le_two] refine Finset.sum_congr rfl fun i _ => ?_ rw [gf8_syndrome_triple] have hblk1 : ∀ q, (rowof (Sum.inl q)).val / 3 = (gf8_other1 β).val := by intro q; simp only [rowof, Sum.elim_inl, gf8_row]; omega have hblk2 : ∀ q, (rowof (Sum.inr q)).val / 3 = (gf8_other2 β).val := by intro q; simp only [rowof, Sum.elim_inr, gf8_row]; omega have hZZ : Z * Zᵀ = Matrix.fromBlocks 0 A Aᵀ 0 := by ext a b rw [hentry] rcases a with q | q <;> rcases b with r | r · rw [Matrix.fromBlocks_apply₁₁, Matrix.zero_apply] exact Finset.sum_eq_zero fun i _ => by rw [gf8_syn_sym_same _ _ _ (by rw [hblk1, hblk1]), mul_zero] · rw [Matrix.fromBlocks_apply₁₂] exact gf8_block_sum β lam q r · rw [Matrix.fromBlocks_apply₂₁, Matrix.transpose_apply] show _ = gf8_amat β c r q rw [← gf8_block_sum β lam r q] exact Finset.sum_congr rfl fun i _ => by rw [gf8_syn_sym_swap]; rfl · rw [Matrix.fromBlocks_apply₂₂, Matrix.zero_apply] exact Finset.sum_eq_zero fun i _ => by rw [gf8_syn_sym_same _ _ _ (by rw [hblk2, hblk2]), mul_zero] have hA : IsUnit A.det := isUnit_iff_ne_zero.2 (gf8_amat_det β c hc) have hmul : Matrix.fromBlocks 0 A Aᵀ 0 * Matrix.fromBlocks 0 A⁻¹ᵀ A⁻¹ 0 = 1 := by rw [Matrix.fromBlocks_multiply, ← Matrix.fromBlocks_one] simp only [Matrix.zero_mul, Matrix.mul_zero, zero_add, add_zero, Matrix.mul_nonsing_inv _ hA, ← Matrix.transpose_mul, Matrix.nonsing_inv_mul _ hA, Matrix.transpose_one] have hN : 6 ≤ (Matrix.fromBlocks 0 A Aᵀ 0).rank := by have := Matrix.rank_mul_le_left (Matrix.fromBlocks 0 A Aᵀ 0) (Matrix.fromBlocks 0 A⁻¹ᵀ A⁻¹ 0) rw [hmul, Matrix.rank_one] at this simpa using this have hcol : Z *ᵥ (fun _ => 1) = 0 := by funext a simp only [Matrix.mulVec, dotProduct, mul_one, Pi.zero_apply, Z] rw [Finset.sum_coe_sort W (fun y => if rowof a ∈ y then (1 : ZMod 2) else 0)] have := hsum {rowof a} (by simp) simp only [Finset.singleton_subset_iff] at this rw [this] exact Finset.sum_eq_zero fun i _ => by rw [gf8_syndrome_pair, mul_zero] have hrn := LinearMap.finrank_range_add_finrank_ker Z.mulVecLin rw [Module.finrank_fintype_fun_eq_card, Fintype.card_coe] at hrn have hker : 0 < W.card → 1 ≤ Module.finrank (ZMod 2) (LinearMap.ker Z.mulVecLin) := by intro hpos rw [Nat.one_le_iff_ne_zero] intro h0 rw [Submodule.finrank_eq_zero] at h0 have hmem : (fun _ => (1 : ZMod 2)) ∈ LinearMap.ker Z.mulVecLin := by rw [LinearMap.mem_ker, Matrix.mulVecLin_apply, hcol] rw [h0, Submodule.mem_bot] at hmem obtain ⟨y, hy⟩ := Finset.card_pos.1 hpos have := congrFun hmem ⟨y, hy⟩ simp at this have hle : (Z * Zᵀ).rank ≤ Z.rank := Matrix.rank_mul_le_left _ _ rw [hZZ] at hle unfold Matrix.rank at hle by_contra hlt push Not at hlt rcases Nat.eq_zero_or_pos W.card with h0 | hpos · have : Module.finrank (ZMod 2) (LinearMap.range Z.mulVecLin) ≤ 0 := by omega unfold Matrix.rank at hN omega · have := hker hpos unfold Matrix.rank at hN omegatheorem gf8_weight_ge_eight (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) (lam : Fin 9 → ZMod 2) (hlam : lam ≠ 0) : 8 ≤ (S.filter fun y => ∑ i ∈ y, lam i = 1).card := by classical have h7 := gf8_weight_ge_seven S hS lam hlam have heven : ((S.filter fun y => ∑ i ∈ y, lam i = 1).card : ZMod 2) = 0 := by have := gf8_W_sum S hS lam ∅ (by simp) simp only [Finset.empty_subset, ite_true, Finset.sum_const, nsmul_eq_mul, mul_one] at this rw [this] exact Finset.sum_eq_zero fun i _ => by rw [Finset.insert_empty, gf8_oracle_syndrome_singleton, mul_zero] obtain ⟨m, hm⟩ := (ZMod.natCast_eq_zero_iff_even).1 heven omega/-- The length bound `∑_{i<k} ⌈d / 2^i⌉` for binary linear codes, written recursively. -/def binary_code_len_bound : ℕ → ℕ → ℕ | 0, _ => 0 | k + 1, d => d + binary_code_len_bound k ((d + 1) / 2)/-- Length bound for binary linear codes (by residual codes), in the language of point sets: if every nonzero linear functional on a`k`-dimensional `𝔽₂`-space takes the value `1` on at least `d` points of `P`, then`P` has at least `∑_{i<k} ⌈d / 2^i⌉` points. -/theorem binary_points_len_bound : ∀ (k : ℕ) (V : Type) [AddCommGroup V] [Module (ZMod 2) V] [FiniteDimensional (ZMod 2) V], Module.finrank (ZMod 2) V = k → ∀ (P : Finset V) (d : ℕ), (∀ φ : Module.Dual (ZMod 2) V, φ ≠ 0 → d ≤ (P.filter fun y => φ y = 1).card) → binary_code_len_bound k d ≤ P.card := by intro k induction k with | zero => intros; simp [binary_code_len_bound] | succ k ih => intro V _ _ _ hk P d hP classical have hnt : Nontrivial V := Module.nontrivial_of_finrank_pos (R := ZMod 2) (by omega) have hex : ∃ m, ∃ φ : Module.Dual (ZMod 2) V, φ ≠ 0 ∧ (P.filter fun y => φ y = 1).card = m := by obtain ⟨v, hv⟩ := exists_ne (0 : V) obtain ⟨φ, hφ⟩ : ∃ φ : Module.Dual (ZMod 2) V, φ v ≠ 0 := by by_contra h push Not at h exact hv ((Module.forall_dual_apply_eq_zero_iff (ZMod 2) v).1 h) exact ⟨_, φ, fun h => hφ (by simp [h]), rfl⟩ obtain ⟨φ0, hφ0, hw0⟩ := Nat.find_spec hex have hmin : ∀ φ : Module.Dual (ZMod 2) V, φ ≠ 0 → Nat.find hex ≤ (P.filter fun y => φ y = 1).card := fun φ hφ => Nat.find_min' hex ⟨φ, hφ, rfl⟩ have hdw : d ≤ Nat.find hex := hw0 ▸ hP φ0 hφ0 obtain ⟨v0, hv0⟩ : ∃ v, φ0 v ≠ 0 := by by_contra h push Not at h exact hφ0 (LinearMap.ext h) have hv01 : φ0 v0 = 1 := (gf8_zmod2_cases _).resolve_left hv0 let H := LinearMap.ker φ0 have hH : Module.finrank (ZMod 2) H = k := by have h1 := LinearMap.finrank_range_add_finrank_ker φ0 have h2 : LinearMap.range φ0 = ⊤ := by rw [LinearMap.range_eq_top] intro b rcases gf8_zmod2_cases b with rfl | rfl · exact ⟨0, map_zero _⟩ · exact ⟨v0, hv01⟩ rw [h2, finrank_top, Module.finrank_self] at h1 show Module.finrank (ZMod 2) (LinearMap.ker φ0) = k omega let P' : Finset H := P.subtype (· ∈ H) have hcount : ∀ (p q : V → Prop) [DecidablePred p] [DecidablePred q], (∀ y, (if p y then 1 else 0) + (if q y then 1 else 0) = 1) → (P.filter p).card + (P.filter q).card = P.card := by intro p q _ _ h rw [Finset.card_filter, Finset.card_filter, ← Finset.sum_add_distrib] rw [Finset.card_eq_sum_ones] exact Finset.sum_congr rfl fun y _ => h y have hP' : P'.card = (P.filter fun y => φ0 y = 0).card := by rw [Finset.card_subtype] exact congrArg Finset.card (Finset.filter_congr fun y _ => LinearMap.mem_ker) have hsplit : (P.filter fun y => φ0 y = 0).card + (P.filter fun y => φ0 y = 1).card = P.card := by apply hcount intro y rcases gf8_zmod2_cases (φ0 y) with h | h <;> simp [h] have hrec : ∀ ψ : Module.Dual (ZMod 2) H, ψ ≠ 0 → (d + 1) / 2 ≤ (P'.filter fun y => ψ y = 1).card := by intro ψ hψ obtain ⟨φ, hφ⟩ := LinearMap.exists_extend ψ have hφH : ∀ y : H, φ y = ψ y := fun y => by rw [← hφ] rfl have hne1 : φ ≠ 0 := by rintro rfl apply hψ ext y rw [← hφH] rfl have hne2 : φ + φ0 ≠ 0 := by intro h0 apply hψ ext y have : (φ + φ0) y = 0 := by rw [h0]; rfl rw [LinearMap.add_apply, LinearMap.mem_ker.1 y.2, add_zero] at this rw [← hφH, this] rfl have c1 := hmin φ hne1 have c2 := hmin (φ + φ0) hne2 have hmap : (P'.filter fun y => ψ y = 1).map (Function.Embedding.subtype _) = P.filter fun y => φ0 y = 0 ∧ φ y = 1 := by ext y constructor · intro hy obtain ⟨y', hy', rfl⟩ := Finset.mem_map.1 hy rw [Finset.mem_filter, Finset.mem_subtype] at hy' refine Finset.mem_filter.2 ⟨hy'.1, LinearMap.mem_ker.1 y'.2, ?_⟩ show φ (y' : V) = 1 rw [hφH] exact hy'.2 · intro hy rw [Finset.mem_filter] at hy refine Finset.mem_map.2 ⟨⟨y, LinearMap.mem_ker.2 hy.2.1⟩, Finset.mem_filter.2 ⟨Finset.mem_subtype.2 hy.1, ?_⟩, rfl⟩ rw [← hφH] exact hy.2.2 have hr : (P'.filter fun y => ψ y = 1).card = (P.filter fun y => φ0 y = 0 ∧ φ y = 1).card := by rw [← hmap, Finset.card_map] have hsum : (P.filter fun y => φ y = 1).card + (P.filter fun y => (φ + φ0) y = 1).card = 2 * (P.filter fun y => φ0 y = 0 ∧ φ y = 1).card + (P.filter fun y => φ0 y = 1).card := by simp only [Finset.card_filter, ← Finset.sum_add_distrib, Finset.mul_sum] refine Finset.sum_congr rfl fun y _ => ?_ rw [LinearMap.add_apply] rcases gf8_zmod2_cases (φ y) with h1 | h1 <;> rcases gf8_zmod2_cases (φ0 y) with h2 | h2 <;> simp [h1, h2] rw [hr] omega have := ih H hH P' ((d + 1) / 2) hrec show d + binary_code_len_bound k ((d + 1) / 2) ≤ P.card omegatheorem gf8_oracle_t_count_ge_20 (S : Finset (Finset (Fin 9))) (hS : is_parity_repr S gf8_oracle_syndrome) : 20 ≤ S.card := by classical let ind : Finset (Fin 9) → (Fin 9 → ZMod 2) := fun y i => if i ∈ y then 1 else 0 have hinj : Function.Injective ind := by intro y y' h ext i have := congrFun h i simp only [ind] at this by_cases h1 : i ∈ y <;> by_cases h2 : i ∈ y' <;> simp_all have hG := binary_points_len_bound 9 (Fin 9 → ZMod 2) (Module.finrank_fin_fun (ZMod 2)) (S.image ind) 8 ?_ · rw [Finset.card_image_of_injective _ hinj] at hG have h20 : binary_code_len_bound 9 8 = 20 := by decide omega · intro φ hφ let lam : Fin 9 → ZMod 2 := fun i => φ (fun j => if i = j then 1 else 0) have hφv : ∀ x, φ x = ∑ i, x i * lam i := fun x => by rw [LinearMap.pi_apply_eq_sum_univ] rfl have hlam : lam ≠ 0 := by intro h apply hφ refine LinearMap.ext fun x => ?_ rw [hφv] simp [h] have hind : ∀ y, φ (ind y) = ∑ i ∈ y, lam i := by intro y rw [hφv] simp only [ind, ite_mul, one_mul, zero_mul] rw [Finset.sum_ite_mem, Finset.univ_inter] rw [Finset.filter_image, Finset.card_image_of_injective _ hinj] simp only [hind] exact gf8_weight_ge_eight S hS lam hlam