line_cubic_t_count_lower_bound
For any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.
Statement
theorem line_cubic_t_count_lower_bound (n : ℕ) (hn : 5 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n)) : 2 * n + 1 ≤ S.card- Formalizes
- arXiv:2610.01024, Proposition 65
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- line_syndromeThe syndrome of the line cubic form assigns 1 to adjacent triples {i, i+1, i+2} and 0 to all other subsets of Fin n.
- 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…
- line_cubic_parity_repr_nonemptyEvery parity representation of the line cubic syndrome for n ≥ 5 is nonempty, because line_syndrome n {0, 1, 2} = 1.
- line_cubic_parity_repr_orthoEvery parity representation S of line_syndrome n satisfies ∑_{y ∈ S} (∑_{j ∈ y} c_j)(∑_{k ∈ y} d_k) = 0 and ∑_{y ∈ S} ∑_{j ∈ y} c_j = 0,…
- line_cubic_parity_repr_eval_zeroFor n ≥ 5, any affine evaluation (∑_{j ∈ y} c_j = b) on all parities y ∈ S of a parity representation S of line_syndrome n forces c = 0.
- 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…
Read back from the Lean
For any natural number $n \ge 5$ and any finite set $S$ of subsets of $\{0, \dots, n-1\}$, if $S$ is a parity representation of the line syndrome of length $n$ (meaning that every set in $S$ is nonempty, and for every subset $A \subseteq \{0, \dots, n-1\}$ of size between 1 and 3, the number of sets in $S$ containing $A$ is odd if $A$ is a contiguous triple $\{i, i+1, i+2\}$ for some $0 \le i < n-2$, and even otherwise), then $S$ contains at least $2n + 1$ sets.
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 lower bound is established by embedding 𝔽₂ⁿ into 𝔽₂^S via a linear evaluation map sending each vector c to its parity sums over the sets in S. Using the orthogonality relations of parity representations of the line cubic syndrome, the image subspace V is shown to be self-orthogonal and orthogonal to the all-ones vector. Since the evaluation map is injective and non-degenerate, V has dimension n and does not contain the all-ones vector, so an isotropic subspace dimension bound implies |S| ≥ 2n + 1.
The evaluation mapping evalMap : 𝔽₂ⁿ → 𝔽₂^S sending c to (y ↦ ∑_{j ∈ y} c j) is a linear map, and V = range(evalMap) is a linear subspace of 𝔽₂^S.
Evaluating a vector on a parity set y is linear in c: additivity follows from distributing sums over addition (Finset.sum_add_distrib), and compatibility with scalar multiplication follows from distributing multiplication over sums (Finset.mul_sum). Its image V is then defined as the range subspace in 𝔽₂^S.
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 isotropic (self-orthogonal): for all u, v ∈ V, ∑_{y ∈ S} u(y) v(y) = 0.
Any u, v ∈ V are the images of vectors c, d ∈ 𝔽₂ⁿ under evalMap. Converting the sum over the subtype S to a sum over the finset S using Finset.sum_coe_sort, the inner product is ∑_{y ∈ S} (∑_{j ∈ y} c j) * (∑_{k ∈ y} d k), which vanishes by the first part of line_cubic_parity_repr_ortho.
uses
Finset.sum_coe_sort,line_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 (line_cubic_parity_repr_ortho n S hS c d).1
Every vector v ∈ V is orthogonal to the all-ones vector, meaning ∑_{y ∈ S} v(y) = 0.
Any vector v ∈ V is the evaluation of some c ∈ 𝔽₂ⁿ. Rewriting the sum over the finset S via Finset.sum_coe_sort gives ∑_{y ∈ S} ∑_{j ∈ y} c j, which is zero by the second part of line_cubic_parity_repr_ortho (evaluating at c and the zero vector).
uses
Finset.sum_coe_sort,line_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 (line_cubic_parity_repr_ortho n S hS c 0).2
The all-ones vector 1 ∈ 𝔽₂^S is not in V.
Suppose for contradiction that the all-ones vector is in V, so evalMap(c) = 1 for some c. Then ∑_{j ∈ y} c j = 1 for all y ∈ S by congr_fun. By line_cubic_parity_repr_eval_zero, this forces c = 0. But S is nonempty by line_cubic_parity_repr_nonempty, so picking any y ∈ S and evaluating evalMap(0) yields 0 = 1 using Pi.zero_apply and Finset.sum_const_zero, contradicting zero_ne_one.
uses
congr_fun,line_cubic_parity_repr_eval_zero,line_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 := line_cubic_parity_repr_eval_zero n hn S hS c 1 h_eval obtain ⟨y, hy⟩ := line_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 evaluation map evalMap is injective.
By LinearMap.ker_eq_bot and LinearMap.ker_eq_bot', injectivity is equivalent to having a trivial kernel. If evalMap(c) = 0, then evaluating at each y ∈ S via congr_fun shows that ∑_{j ∈ y} c j = 0 for all y ∈ S. Since n ≥ 5, line_cubic_parity_repr_eval_zero with constant 0 implies c = 0.
uses
LinearMap.ker_eq_bot,LinearMap.ker_eq_bot',congr_fun,line_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 line_cubic_parity_repr_eval_zero n hn S hS c 0 h1
The dimension (finite rank) of V over 𝔽₂ is n.
Because evalMap is injective, LinearMap.finrank_range_of_inj shows that the dimension of its image V equals the dimension of its domain 𝔽₂ⁿ, which is 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 2n + 1.
Applying the general bound isotropic_subspace_lower_bound to the subspace V (which is isotropic, orthogonal to the all-ones vector, and does not contain the all-ones vector) yields 2 * dim(V) + 1 ≤ |S|. Substituting dim(V) = n gives 2n + 1 ≤ |S|.
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- The sum of a sum of functions over a finite set equals the sum of their individual sums.
Finset.mul_sum- Multiplication distributes over finite sums from the left.
Finset.sum_coe_sort- A sum over the elements of a subtype coerced from a finite set s equals the sum directly over s.
line_cubic_parity_repr_ortho- For any parity representation S of the line cubic syndrome and any vectors c and d, the sum over S of the product of evaluations of c and d is 0, and the sum over S of evaluations of c is 0.
congr_fun- Equal functions take equal values on equal inputs.
line_cubic_parity_repr_eval_zero- If a vector c has a constant evaluation b across all parity sets y ∈ S for a parity representation of the line cubic syndrome (with n ≥ 5), then c = 0.
line_cubic_parity_repr_nonempty- A parity representation of the line cubic syndrome is nonempty when n ≥ 5.
Pi.zero_apply- The zero function evaluated at any input returns zero.
Finset.sum_const_zero- The sum of zero over any finite set is zero.
zero_ne_one- Zero is not equal to one.
LinearMap.ker_eq_bot- A linear map is injective if and only if its kernel is trivial.
LinearMap.ker_eq_bot'- The kernel of a linear map is trivial if and only if every element mapped to zero is zero.
LinearMap.finrank_range_of_inj- An injective linear map preserves the finite rank (dimension) of its domain.
isotropic_subspace_lower_bound- Any subspace V ⊆ 𝔽₂^M that is self-orthogonal, orthogonal to the all-ones vector, and does not contain the all-ones vector satisfies 2 * dim(V) + 1 ≤ |M|.
- In Lean, the finite set S is distinguished from the coerced subtype ↥S. Bridging sums and cardinalities defined on the subtype to those on the finset requires formal conversion steps using Finset.sum_coe_sort and Fintype.card S = S.card.
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.
/-- Proposition 65 floor: every parity representation of the line cubic syndrome has at least 2n + 1 parities for n ≥ 5. -/theorem line_cubic_t_count_lower_bound (n : ℕ) (hn : 5 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_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 (line_cubic_parity_repr_ortho n 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 (line_cubic_parity_repr_ortho n 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 := line_cubic_parity_repr_eval_zero n hn S hS c 1 h_eval obtain ⟨y, hy⟩ := line_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 line_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