AFTD Auto-Formalizing Theoretical Domains

line_cubic_t_count_lower_bound

theoremverifiedformalization

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.

  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.

    lines 3–16

    uses Finset.sum_add_distrib, Finset.mul_sum

      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
  2. 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.

    lines 17–23

    uses Finset.sum_coe_sort, line_cubic_parity_repr_ortho

      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
  3. 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).

    lines 24–29

    uses Finset.sum_coe_sort, line_cubic_parity_repr_ortho

      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
  4. 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.

    lines 30–41

    uses congr_fun, line_cubic_parity_repr_eval_zero, line_cubic_parity_repr_nonempty, Pi.zero_apply, Finset.sum_const_zero, zero_ne_one

      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
  5. 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.

    lines 42–48

    uses LinearMap.ker_eq_bot, LinearMap.ker_eq_bot', congr_fun, line_cubic_parity_repr_eval_zero

      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
  6. 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.

    lines 49–51

    uses LinearMap.finrank_range_of_inj

      have h_rank : Module.finrank (ZMod 2) V = n := by
        rw [LinearMap.finrank_range_of_inj h_inj]
        simp
  7. 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|.

    lines 52–55

    uses isotropic_subspace_lower_bound

      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
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|.

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

/-- 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
See it in the graphDiscuss this resultChallenge it