cyclic_cubic_t_count_isotropy_lower_bound
For every natural number n ≥ 6 and every finite set S : Finset (Finset (Fin n)), if is_parity_repr S (cyclic_cubic_syndrome n), then 2 * n + 1 ≤ S.card.
Statement
theorem cyclic_cubic_t_count_isotropy_lower_bound (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) : 2 * n + 1 ≤ S.card- Related work
- arXiv:2610.01024
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- cyclic_cubic_syndromeFor a natural number n and a finite subset A of Fin n, cyclic_cubic_syndrome n A returns 1 in ZMod 2 if there exists j : Fin n such that A…
- 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…
- cyclic_cubic_parity_repr_nonemptyEvery parity representation S of cyclic_cubic_syndrome n for n ≥ 6 is nonempty, because cyclic_cubic_syndrome n {0, 1, 2} = 1.
- cyclic_cubic_parity_repr_orthoEvery parity representation S of cyclic_cubic_syndrome n satisfies ∑_{y ∈ S} (∑_{j ∈ y} c_j)(∑_{k ∈ y} d_k) = 0 and ∑_{y ∈ S} ∑_{j ∈ y}…
- cyclic_cubic_parity_repr_eval_zeroFor n ≥ 6, any affine evaluation (∑_{j ∈ y} c_j = b) on all parities y ∈ S of a parity representation S of cyclic_cubic_syndrome n forces…
- isotropic_subspace_lower_boundIf V is an isotropic subspace of (M → ZMod 2) under the standard dot product, the all-ones vector is orthogonal to V, and the all-ones…
Read back from the Lean
For any natural number $n \ge 6$ and any finite set $S$ of subsets of $\mathrm{Fin}(n)$, if $S$ is a parity representation of the cyclic cubic syndrome of length $n$—that is, every element of $S$ is non-empty, and for every subset $A \subseteq \mathrm{Fin}(n)$ with $1 \le |A| \le 3$, the number of elements of $S$ that contain $A$ is odd if and only if $A = \{j, (j + 1) \bmod n, (j + 2) \bmod n\}$ for some $j \in \mathrm{Fin}(n)$, and even otherwise—then the cardinality of $S$ is at least $2n + 1$.
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 establishes the lower bound |S| ≥ 2n + 1 through a linear-algebraic isotropy argument over ℤ/2ℤ. It defines an evaluation map from (ℤ/2ℤ)^n into (ℤ/2ℤ)^S and shows that its image V is an n-dimensional totally isotropic subspace that is orthogonal to the all-ones vector 1 but does not contain 1. Applying a general lower bound for such isotropic subspaces (isotropic_subspace_lower_bound), which requires |S| ≥ 2 * dim(V) + 1, immediately yields |S| ≥ 2n + 1.
The evaluation map evalMap : (Fin n → ℤ/2ℤ) →ₗ[ℤ/2ℤ] (S → ℤ/2ℤ), defined by c ↦ (y ↦ ∑_{j ∈ y} c j), is linear, and V is defined as its range.
We define the map evaluating each vector c ∈ (ℤ/2ℤ)^n on subsets y ∈ S by summing the coordinates of c over y. Linearity under addition is verified by distributing the sum over addition using Finset.sum_add_distrib, and linearity under scalar multiplication is verified using Finset.mul_sum. We then define the subspace V ≤ (ℤ/2ℤ)^S as the range of evalMap.
uses
Finset.sum_add_distrib,Finset.mul_sumlet evalMap : (Fin n → ZMod 2) →ₗ[ZMod 2] (S → ZMod 2) := { toFun := fun c y => ∑ j ∈ (y : Finset (Fin n)), c j map_add' := by intro c d ext ⟨y, hy⟩ dsimp rw [← Finset.sum_add_distrib] map_smul' := by intro a c ext ⟨y, hy⟩ dsimp exact (Finset.mul_sum _ _ _).symm } let V : Submodule (ZMod 2) (S → ZMod 2) := LinearMap.range evalMap
The subspace V is totally isotropic under the standard inner product on (ℤ/2ℤ)^S.
For any u, v ∈ V with witnesses c, d ∈ (ℤ/2ℤ)^n, rewriting the inner product from a sum over the subtype S to a sum over the finset S via Finset.sum_coe_sort yields ∑_{y ∈ S} (∑_{j ∈ y} c j) * (∑_{k ∈ y} d k). This vanishes by the first component of cyclic_cubic_parity_repr_ortho.
uses
Finset.sum_coe_sort,cyclic_cubic_parity_repr_orthohave h_iso : ∀ u ∈ V, ∀ v ∈ V, (∑ m, u m * v m) = 0 := by rintro u ⟨c, rfl⟩ v ⟨d, rfl⟩ have h1 : (∑ m : S, evalMap c m * evalMap d m) = ∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k) := Finset.sum_coe_sort S (fun y => (∑ j ∈ y, c j) * (∑ k ∈ y, d k)) rw [h1] exact (cyclic_cubic_parity_repr_ortho n hn S hS c d).1
Every vector in V is orthogonal to the all-ones vector 1 ∈ (ℤ/2ℤ)^S.
For any v ∈ V with v = evalMap c, the coordinate sum ∑_{m ∈ S} v m converts via Finset.sum_coe_sort to ∑_{y ∈ S} ∑_{j ∈ y} c j, which vanishes by the second component of cyclic_cubic_parity_repr_ortho applied with d = 0.
uses
Finset.sum_coe_sort,cyclic_cubic_parity_repr_orthohave h_ones_ortho : ∀ v ∈ V, ∑ m, v m = 0 := by rintro v ⟨c, rfl⟩ have h1 : (∑ m : S, evalMap c m) = ∑ y ∈ S, ∑ j ∈ y, c j := Finset.sum_coe_sort S (fun y => ∑ j ∈ y, c j) rw [h1] exact (cyclic_cubic_parity_repr_ortho n hn S hS c 0).2
The all-ones vector 1 ∈ (ℤ/2ℤ)^S is not in V.
Suppose 1 ∈ V, so 1 = evalMap c for some c. Applying congr_fun shows that ∑_{j ∈ y} c j = 1 for every y ∈ S. By cyclic_cubic_parity_repr_eval_zero with b = 1, any vector with constant evaluation 1 must be zero, so c = 0. But S is nonempty by cyclic_cubic_parity_repr_nonempty; evaluating evalMap 0 at an element y ∈ S yields 0 (using Pi.zero_apply and Finset.sum_const_zero), which contradicts 0 ≠ 1 (zero_ne_one).
uses
congr_fun,cyclic_cubic_parity_repr_eval_zero,cyclic_cubic_parity_repr_nonempty,Pi.zero_apply,Finset.sum_const_zero,zero_ne_onehave h_ones_notin : (fun _ : S => (1 : ZMod 2)) ∉ V := by intro ⟨c, hc⟩ have h_eval : ∀ y ∈ S, ∑ j ∈ y, c j = 1 := by intro y hy exact congr_fun hc ⟨y, hy⟩ have hc0 : c = 0 := cyclic_cubic_parity_repr_eval_zero n hn S hS c 1 h_eval obtain ⟨y, hy⟩ := cyclic_cubic_parity_repr_nonempty n hn S hS have h1 := congr_fun hc ⟨y, hy⟩ dsimp [evalMap] at h1 rw [hc0] at h1 simp only [Pi.zero_apply, Finset.sum_const_zero] at h1 exact zero_ne_one h1
The linear map evalMap is injective.
A linear map is injective if and only if its kernel is trivial, which holds if and only if evalMap c = 0 implies c = 0 (LinearMap.ker_eq_bot, LinearMap.ker_eq_bot'). If evalMap c = 0, evaluating at each y ∈ S via congr_fun shows that ∑_{j ∈ y} c j = 0 for all y ∈ S, which implies c = 0 by cyclic_cubic_parity_repr_eval_zero with b = 0.
uses
LinearMap.ker_eq_bot,LinearMap.ker_eq_bot',congr_fun,cyclic_cubic_parity_repr_eval_zerohave h_inj : Function.Injective evalMap := by rw [← LinearMap.ker_eq_bot, LinearMap.ker_eq_bot'] intro c hc have h1 : ∀ y ∈ S, ∑ j ∈ y, c j = 0 := by intro y hy exact congr_fun hc ⟨y, hy⟩ exact cyclic_cubic_parity_repr_eval_zero n hn S hS c 0 h1
The dimension of V over ℤ/2ℤ is n.
Because evalMap is injective, the dimension of its image V equals the dimension of its domain (ℤ/2ℤ)^n by LinearMap.finrank_range_of_inj, and simplifying this dimension gives n.
uses
LinearMap.finrank_range_of_injhave h_rank : Module.finrank (ZMod 2) V = n := by rw [LinearMap.finrank_range_of_inj h_inj] simp
The cardinality of S is at least 2 * n + 1.
Applying isotropic_subspace_lower_bound to V using the three established conditions (isotropy, orthogonality to 1, and 1 ∉ V) gives 2 * dim(V) + 1 ≤ |S|. Substituting dim(V) = n and identifying Fintype.card S with S.card completes the proof.
uses
isotropic_subspace_lower_boundhave h_bound := isotropic_subspace_lower_bound V h_iso h_ones_ortho h_ones_notin rw [h_rank] at h_bound have h_card : Fintype.card S = S.card := by simp rwa [h_card] at h_bound
Finset.sum_add_distrib- Summation over a finite set distributes over addition: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_coe_sort- Summing over the subtype coerced from a finset s is equal to summing over s itself: ∑ i, f ↑i = ∑ i ∈ s, f i.
cyclic_cubic_parity_repr_ortho- For any parity representation S of the cyclic cubic syndrome and any vectors c and d, the evaluations of c and d on S are orthogonal, and every evaluation is orthogonal to the all-ones vector.
congr_fun- If two functions are equal, then their evaluations at any argument are equal: f = g → f a = g a.
cyclic_cubic_parity_repr_eval_zero- For a parity representation S of the cyclic cubic syndrome, if a vector c has constant evaluation b across all subsets y ∈ S, then c must be 0.
cyclic_cubic_parity_repr_nonempty- Any parity representation of the cyclic cubic syndrome on n ≥ 6 variables is nonempty.
Pi.zero_apply- The zero function evaluated at any input is zero: 0 i = 0.
Finset.sum_const_zero- The sum of the constant zero function over any finite set is zero.
zero_ne_one- In any nontrivial ring, 0 ≠ 1.
LinearMap.ker_eq_bot- A linear map is injective if and only if its kernel is trivial (the bottom submodule).
LinearMap.ker_eq_bot'- The kernel of a linear map is trivial if and only if every vector mapped to zero is itself zero.
LinearMap.finrank_range_of_inj- An injective linear map between vector spaces preserves dimension: dim(range f) = dim(domain).
isotropic_subspace_lower_bound- If V ⊆ (ℤ/2ℤ)^M is a totally isotropic subspace orthogonal to the all-ones vector and not containing the all-ones vector, then |M| ≥ 2 dim(V) + 1.
- The proof identifies the cardinality of the finset `S.card` with the cardinality of the induced subtype `Fintype.card S`, which Lean handles automatically via `simp`.
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.
/-- For any n ≥ 6, every parity representation of the cyclic cubic syndrome has cardinality at least 2n + 1. -/theorem cyclic_cubic_t_count_isotropy_lower_bound (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) : 2 * n + 1 ≤ S.card := by let evalMap : (Fin n → ZMod 2) →ₗ[ZMod 2] (S → ZMod 2) := { toFun := fun c y => ∑ j ∈ (y : Finset (Fin n)), c j map_add' := by intro c d ext ⟨y, hy⟩ dsimp rw [← Finset.sum_add_distrib] map_smul' := by intro a c ext ⟨y, hy⟩ dsimp exact (Finset.mul_sum _ _ _).symm } let V : Submodule (ZMod 2) (S → ZMod 2) := LinearMap.range evalMap have h_iso : ∀ u ∈ V, ∀ v ∈ V, (∑ m, u m * v m) = 0 := by rintro u ⟨c, rfl⟩ v ⟨d, rfl⟩ have h1 : (∑ m : S, evalMap c m * evalMap d m) = ∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k) := Finset.sum_coe_sort S (fun y => (∑ j ∈ y, c j) * (∑ k ∈ y, d k)) rw [h1] exact (cyclic_cubic_parity_repr_ortho n hn S hS c d).1 have h_ones_ortho : ∀ v ∈ V, ∑ m, v m = 0 := by rintro v ⟨c, rfl⟩ have h1 : (∑ m : S, evalMap c m) = ∑ y ∈ S, ∑ j ∈ y, c j := Finset.sum_coe_sort S (fun y => ∑ j ∈ y, c j) rw [h1] exact (cyclic_cubic_parity_repr_ortho n hn S hS c 0).2 have h_ones_notin : (fun _ : S => (1 : ZMod 2)) ∉ V := by intro ⟨c, hc⟩ have h_eval : ∀ y ∈ S, ∑ j ∈ y, c j = 1 := by intro y hy exact congr_fun hc ⟨y, hy⟩ have hc0 : c = 0 := cyclic_cubic_parity_repr_eval_zero n hn S hS c 1 h_eval obtain ⟨y, hy⟩ := cyclic_cubic_parity_repr_nonempty n hn S hS have h1 := congr_fun hc ⟨y, hy⟩ dsimp [evalMap] at h1 rw [hc0] at h1 simp only [Pi.zero_apply, Finset.sum_const_zero] at h1 exact zero_ne_one h1 have h_inj : Function.Injective evalMap := by rw [← LinearMap.ker_eq_bot, LinearMap.ker_eq_bot'] intro c hc have h1 : ∀ y ∈ S, ∑ j ∈ y, c j = 0 := by intro y hy exact congr_fun hc ⟨y, hy⟩ exact cyclic_cubic_parity_repr_eval_zero n hn S hS c 0 h1 have h_rank : Module.finrank (ZMod 2) V = n := by rw [LinearMap.finrank_range_of_inj h_inj] simp have h_bound := isotropic_subspace_lower_bound V h_iso h_ones_ortho h_ones_notin rw [h_rank] at h_bound have h_card : Fintype.card S = S.card := by simp rwa [h_card] at h_bound