AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_t_count_isotropy_lower_bound

theoremverifiedoriginal

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.

  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.

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

    lines 17–23

    uses Finset.sum_coe_sort, cyclic_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 (cyclic_cubic_parity_repr_ortho n hn S hS c d).1
  3. 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.

    lines 24–29

    uses Finset.sum_coe_sort, cyclic_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 (cyclic_cubic_parity_repr_ortho n hn S hS c 0).2
  4. 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).

    lines 30–41

    uses congr_fun, cyclic_cubic_parity_repr_eval_zero, cyclic_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 := 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
  5. 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.

    lines 42–48

    uses LinearMap.ker_eq_bot, LinearMap.ker_eq_bot', congr_fun, cyclic_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 cyclic_cubic_parity_repr_eval_zero n hn S hS c 0 h1
  6. 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.

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

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

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

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