AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_parity_repr_eval_zero

theoremverified

For 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 c = 0.

Statement

theorem cyclic_cubic_parity_repr_eval_zero (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) (c : Fin n → ZMod 2) (b : ZMod 2) (h : ∀ y ∈ S, (∑ j ∈ y, c j) = b) : c = 0
Source
step towards cyclic_cubic_t_count_isotropy_lower_bound
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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_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…
  • cyclic_cubic_distinct_neighborsFor n ≥ 6 and any x : Fin n, the cyclic neighbors (x - 1) % n and (x + 1) % n are distinct.
  • cyclic_cubic_parity_repr_pair_sumFor n ≥ 6 and any distinct pair p ≠ q, the sum ∑_j c_j * s({j, p, q}) vanishes for any affine evaluation on a parity representation.
  • cyclic_cubic_syndrome_isolatedFor n ≥ 6 and any x : Fin n, the cyclic cubic syndrome of {j, (x-1)%n, (x+1)%n} is 0 for all j ≠ x.
Used by 1

The proof, explained

To show that c = 0, we prove that c(x) = 0 for an arbitrary x ∈ Fin n. We consider the cyclic neighbors p = x - 1 and q = x + 1 (mod n), which are distinct because n ≥ 6. An orthogonality relation for parity representations ensures that the sum ∑_j c_j * syndrome({j, p, q}) vanishes. Because no other index j ≠ x can form a consecutive cyclic triple with p and q, the sum collapses to the single term c(x) * syndrome({x, p, q}) = c(x) * 1 = 0, forcing c(x) = 0.

  1. To evaluate the syndrome of {x, x - 1, x + 1} as 1, it suffices to show it equals a consecutive cyclic triple {j, j + 1, j + 2} with j = x - 1 (mod n).

    By definition, cyclic_cubic_syndrome n A is 1 when A is of the form {j, j + 1, j + 2} mod n for some index j, and 0 otherwise. Unfolding the definition and rewriting with if_pos reduces the goal to providing a witness j; choosing j = (x - 1) % n leaves the equality of sets {x, x - 1, x + 1} = {j, j + 1, j + 2} to be verified.

    lines 1–5

    uses if_pos

    private theorem cyclic_cubic_parity_repr_eval_zero_syndrome_one (n : ℕ) (hn : 6 ≤ n) (x : Fin n) :
        cyclic_cubic_syndrome n {x, (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n), (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)} = 1 := by
      unfold cyclic_cubic_syndrome
      rw [if_pos]
      refine ⟨⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩, ?_⟩
  2. The index (j + 1) mod n equals x.

    By extensionality on Fin n, we compare the underlying natural numbers. Using Nat.mod_add_mod, ((x + n - 1) % n + 1) % n rewrites to (x + n - 1 + 1) % n = (x + n) % n. Dropping the multiple of n with Nat.add_mod_right leaves x % n, which equals x since x < n.

    lines 6–12

    uses Fin.ext, Nat.mod_add_mod, Nat.add_mod_right, Nat.mod_eq_of_lt

      have hA : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = x := by
        apply Fin.ext
        simp only
        have h1 : ((x.val + n - 1) % n + 1) % n = (x.val + n - 1 + 1) % n := Nat.mod_add_mod _ _ _
        rw [h1]
        have h2 : x.val + n - 1 + 1 = x.val + n := by omega
        rw [h2, Nat.add_mod_right, Nat.mod_eq_of_lt x.isLt]
  3. The index (j + 2) mod n equals (x + 1) mod n.

    Similarly, comparing values via Fin.ext, ((x + n - 1) % n + 2) % n rewrites by Nat.mod_add_mod to (x + n - 1 + 2) % n = ((x + 1) + n) % n, which simplifies to (x + 1) % n by Nat.add_mod_right.

    lines 13–19

    uses Fin.ext, Nat.mod_add_mod, Nat.add_mod_right

      have hB : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 2) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) := by
        apply Fin.ext
        simp only
        have h1 : ((x.val + n - 1) % n + 2) % n = (x.val + n - 1 + 2) % n := Nat.mod_add_mod _ _ _
        rw [h1]
        have h2 : x.val + n - 1 + 2 = (x.val + 1) + n := by omega
        rw [h2, Nat.add_mod_right]
  4. The syndrome of {x, x - 1, x + 1} is 1.

    Substituting the verified identities j + 1 = x and j + 2 = x + 1 turns {j, j + 1, j + 2} into {x - 1, x, x + 1}. Commuting the insertion of elements via Finset.insert_comm shows this equals {x, x - 1, x + 1}, completing the helper lemma.

    lines 20–21

    uses Finset.insert_comm

      simp only [hA, hB]
      exact Finset.insert_comm _ _ _
  5. To prove c = 0, let x ∈ Fin n be arbitrary and let p = x - 1 and q = x + 1 be its cyclic neighbors; then p ≠ q.

    By function extensionality, it suffices to prove c x = 0 for an arbitrary x. We set p = (x - 1) % n and q = (x + 1) % n. Because n ≥ 6, these two cyclic neighbors are distinct by cyclic_cubic_distinct_neighbors.

    lines 22–28

    uses cyclic_cubic_distinct_neighbors

    /-- For 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 c = 0. -/
    theorem cyclic_cubic_parity_repr_eval_zero (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) (c : Fin n → ZMod 2) (b : ZMod 2) (h : ∀ y ∈ S, (∑ j ∈ y, c j) = b) : c = 0 := by
      funext x
      set p : Fin n := ⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ with hp
      set q : Fin n := ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ with hq
      have hpq : p ≠ q := by simpa only [hp, hq] using cyclic_cubic_distinct_neighbors n hn x
  6. The sum ∑_j c_j * syndrome({j, p, q}) reduces to the single term c_x * syndrome({x, p, q}).

    We apply Fintype.sum_eq_single to isolate the index x. For any j ≠ x, the set {j, p, q} cannot form three consecutive cyclic elements when n ≥ 6, so its syndrome is 0 by cyclic_cubic_syndrome_isolated. Each term for j ≠ x thus vanishes by mul_zero.

    lines 29–34

    uses Fintype.sum_eq_single, cyclic_cubic_syndrome_isolated, mul_zero

      have hsingle : ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} = c x * cyclic_cubic_syndrome n {x, p, q} := by
        apply Fintype.sum_eq_single x
        intro j hjx
        rw [show cyclic_cubic_syndrome n {j, p, q} = 0 from by
          simpa only [hp, hq] using cyclic_cubic_syndrome_isolated n hn x j hjx]
        rw [mul_zero]
  7. c x = 0, completing the proof that c = 0.

    By cyclic_cubic_parity_repr_pair_sum, the sum ∑_j c_j * syndrome({j, p, q}) equals 0. Replacing the sum with its isolated term gives c_x * syndrome({x, p, q}) = 0. The helper lemma shows syndrome({x, p, q}) = 1, so this simplifies via mul_one to c_x = 0. Since x was arbitrary, c = 0.

    lines 35–40

    uses cyclic_cubic_parity_repr_pair_sum, cyclic_cubic_parity_repr_eval_zero_syndrome_one, mul_one

      have hsum := cyclic_cubic_parity_repr_pair_sum n hn S hS c b h p q hpq
      rw [hsingle] at hsum
      have hsy : cyclic_cubic_syndrome n {x, p, q} = 1 := by
        simpa only [hp, hq] using cyclic_cubic_parity_repr_eval_zero_syndrome_one n hn x
      rw [hsy, mul_one] at hsum
      exact hsum
if_pos
If a condition c holds, then the conditional if c then t else e evaluates to t.
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
Nat.mod_add_mod
For natural numbers, ((m % n) + k) % n = (m + k) % n.
Nat.add_mod_right
Adding a multiple of the modulus does not change the remainder: (x + z) % z = x % z.
Nat.mod_eq_of_lt
If a < b, then a % b = a.
Finset.insert_comm
Inserting two elements into a finite set is commutative: {a, b} ∪ s = {b, a} ∪ s.
cyclic_cubic_distinct_neighbors
For n ≥ 6, the cyclic neighbors (x - 1) % n and (x + 1) % n of any x are distinct.
Fintype.sum_eq_single
A sum over a finite type reduces to the single term at a if all other terms vanish.
cyclic_cubic_syndrome_isolated
For n ≥ 6 and j ≠ x, the cyclic cubic syndrome of {j, (x - 1) % n, (x + 1) % n} is zero.
mul_zero
Multiplying any element by zero yields zero.
cyclic_cubic_parity_repr_pair_sum
For any parity representation S of cyclic_cubic_syndrome n and any pair p ≠ q, the weighted sum ∑_j c_j * syndrome({j, p, q}) is zero.
cyclic_cubic_parity_repr_eval_zero_syndrome_one
For n ≥ 6, the cyclic cubic syndrome on {x, (x - 1) % n, (x + 1) % n} is 1.
mul_one
Multiplying any element by one yields that element.

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

private theorem cyclic_cubic_parity_repr_eval_zero_syndrome_one (n : ℕ) (hn : 6 ≤ n) (x : Fin n) :    cyclic_cubic_syndrome n {x, (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n), (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)} = 1 := by  unfold cyclic_cubic_syndrome  rw [if_pos]  refine ⟨⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩, ?_⟩  have hA : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = x := by    apply Fin.ext    simp only    have h1 : ((x.val + n - 1) % n + 1) % n = (x.val + n - 1 + 1) % n := Nat.mod_add_mod _ _ _    rw [h1]    have h2 : x.val + n - 1 + 1 = x.val + n := by omega    rw [h2, Nat.add_mod_right, Nat.mod_eq_of_lt x.isLt]  have hB : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 2) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) := by    apply Fin.ext    simp only    have h1 : ((x.val + n - 1) % n + 2) % n = (x.val + n - 1 + 2) % n := Nat.mod_add_mod _ _ _    rw [h1]    have h2 : x.val + n - 1 + 2 = (x.val + 1) + n := by omega    rw [h2, Nat.add_mod_right]  simp only [hA, hB]  exact Finset.insert_comm _ _ _/-- For 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 c = 0. -/theorem cyclic_cubic_parity_repr_eval_zero (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) (c : Fin n → ZMod 2) (b : ZMod 2) (h : ∀ y ∈ S, (∑ j ∈ y, c j) = b) : c = 0 := by  funext x  set p : Fin n := ⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ with hp  set q : Fin n := ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ with hq  have hpq : p ≠ q := by simpa only [hp, hq] using cyclic_cubic_distinct_neighbors n hn x  have hsingle : ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} = c x * cyclic_cubic_syndrome n {x, p, q} := by    apply Fintype.sum_eq_single x    intro j hjx    rw [show cyclic_cubic_syndrome n {j, p, q} = 0 from by      simpa only [hp, hq] using cyclic_cubic_syndrome_isolated n hn x j hjx]    rw [mul_zero]  have hsum := cyclic_cubic_parity_repr_pair_sum n hn S hS c b h p q hpq  rw [hsingle] at hsum  have hsy : cyclic_cubic_syndrome n {x, p, q} = 1 := by    simpa only [hp, hq] using cyclic_cubic_parity_repr_eval_zero_syndrome_one n hn x  rw [hsy, mul_one] at hsum  exact hsum
See it in the graphDiscuss this resultChallenge it