AFTD Auto-Formalizing Theoretical Domains

line_cubic_parity_repr_ortho

theoremverified

Every 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, because singletons and pairs have syndrome 0.

Statement

theorem line_cubic_parity_repr_ortho (n : ℕ)
    (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n))
    (c d : Fin n → ZMod 2) :
    (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k) = 0) ∧
    (∑ y ∈ S, (∑ j ∈ y, c j) = 0)
Source
step towards line_cubic_t_count_lower_bound
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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.
Used by 1

The proof, explained

The theorem proves that any parity representation S of line_syndrome n satisfies bilinear orthogonality ∑_{y ∈ S} (∑_{j ∈ y} c_j)(∑_{k ∈ y} d_k) = 0 and linear orthogonality ∑_{y ∈ S} ∑_{j ∈ y} c_j = 0 over ZMod 2. The argument first establishes a lemma: singletons and pairs have count 0 modulo 2 because line_syndrome is supported only on 3-element line segments {i, i+1, i+2}. For the main theorem, exchanging summation orders rewrites the bilinear sum as a linear combination of parity counts of supersets of pairs {j, k}, and rewrites the linear sum as a combination of parity counts of supersets of singletons {j}. Since {j, k} and {j} have cardinality at most 2, every term vanishes by the lemma.

  1. For any subset A with 1 ≤ |A| ≤ 2, the count modulo 2 of sets in S containing A reduces to showing that A cannot be a 3-element line segment {i, i+1, i+2}.

    Since |A| ≤ 2, we have |A| ≤ 3, so the parity representation hypothesis equates the count modulo 2 of supersets of A to line_syndrome n A. By definition, line_syndrome n A is 1 if A = {i, i+1, i+2} for some index i, and 0 otherwise. In the latter case the count is immediately 0; in the former case, we obtain such an index i and must derive a contradiction to rule it out.

    lines 5–10

      have hA3 : A.card ≤ 3 := by omega
      have hrepr := hS.2 A ⟨hA1, hA3⟩
      rw [hrepr]
      unfold line_syndrome
      split_ifs with h
      · rcases h with ⟨i, hi⟩
  2. A subset A with |A| ≤ 2 cannot be a 3-element line segment, so its count modulo 2 of supersets in S is zero.

    The three elements i, i+1, and i+2 in Fin n are strictly increasing and therefore pairwise distinct. By inserting elements one by one (`Finset.card_insert_of_notMem`, `Finset.card_singleton`, `Finset.mem_singleton`, `Finset.mem_insert`), the cardinality of {i, i+1, i+2} is 3. By `congr_arg`, A = {i, i+1, i+2} implies |A| = 3, which contradicts the assumption |A| ≤ 2. The remaining case where A is not a 3-element segment evaluates to 0 directly by reflexivity (`rfl`).

    lines 11–26

    uses Finset.card_insert_of_notMem, Finset.card_singleton, Finset.mem_singleton, Finset.mem_insert, congr_arg

        have hc : ({⟨i.val, by omega⟩, ⟨i.val + 1, by omega⟩, ⟨i.val + 2, by omega⟩} : Finset (Fin n)).card = 3 := by
          let a : Fin n := ⟨i.val, by omega⟩
          let b : Fin n := ⟨i.val + 1, by omega⟩
          let c : Fin n := ⟨i.val + 2, by omega⟩
          change ({a, b, c} : Finset (Fin n)).card = 3
          have hab : a ≠ b := by intro h; injection h with h; omega
          have hac : a ≠ c := by intro h; injection h with h; omega
          have hbc : b ≠ c := by intro h; injection h with h; omega
          rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton]
          · intro h; simp only [Finset.mem_singleton] at h; exact hbc h
          · simp only [Finset.mem_insert, Finset.mem_singleton]; rintro (h | h)
            · exact hab h
            · exact hac h
        have h_card_eq := congr_arg Finset.card hi
        omega
      · rfl
  3. It suffices to prove that for each pair of indices j and k, the sum ∑_{y ∈ S} (if j ∈ y then c_j else 0) * (if k ∈ y then d_k else 0) is zero.

    We split the conjunction with `constructor`. For the bilinear sum, we rewrite the restricted sums over y as unrestricted sums over all elements of Fin n using indicator functions (`Finset.sum_ite_mem_eq`) and expand their product into a double sum over j and k via `Finset.sum_mul_sum`. Exchanging the order of summation (`Finset.sum_comm`), it suffices by `Finset.sum_eq_zero` to show that the inner sum over y vanishes for each fixed j and k.

    lines 34–43

    uses Finset.sum_congr, Finset.sum_ite_mem_eq, Finset.sum_mul_sum, Finset.sum_comm, Finset.sum_eq_zero

      constructor
      · have h1 : (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k)) =
            ∑ y ∈ S, ∑ j : Fin n, ∑ k : Fin n, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0) := by
          refine Finset.sum_congr rfl (fun y _ => ?_)
          rw [← Finset.sum_ite_mem_eq y c, ← Finset.sum_ite_mem_eq y d]
          rw [Finset.sum_mul_sum]
        rw [h1, Finset.sum_comm]
        refine Finset.sum_eq_zero (fun j _ => ?_)
        rw [Finset.sum_comm]
        refine Finset.sum_eq_zero (fun k _ => ?_)
  4. For fixed j and k, the sum over y ∈ S equals (c_j * d_k) times the cardinality modulo 2 of the sets y ∈ S containing {j, k}.

    The product of indicators (if j ∈ y then c_j else 0) * (if k ∈ y then d_k else 0) is c_j * d_k when both j ∈ y and k ∈ y, and 0 otherwise. Factoring out c_j * d_k (`Finset.mul_sum`), the remaining sum of booleans equals the cardinality modulo 2 of {x ∈ S | j ∈ x ∧ k ∈ x} by `Finset.sum_boole`. We rewrite this set as the filter of sets y ∈ S such that {j, k} ⊆ y (`Finset.mem_filter`, `Finset.insert_subset_iff`, `Finset.singleton_subset_iff`).

    lines 44–53

    uses Finset.mul_sum, Finset.sum_congr, Finset.sum_boole, Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff

        have h_split : (∑ y ∈ S, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0)) =
            (c j * d k) * ∑ y ∈ S, (if j ∈ y ∧ k ∈ y then (1 : ZMod 2) else 0) := by
          rw [Finset.mul_sum]
          refine Finset.sum_congr rfl (fun y _ => ?_)
          by_cases hj : j ∈ y <;> by_cases hk : k ∈ y <;> simp [hj, hk]
        rw [h_split, Finset.sum_boole]
        have h_filt : {x ∈ S | j ∈ x ∧ k ∈ x} = S.filter (fun y => {j, k} ⊆ y) := by
          ext y
          simp only [Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff]
        rw [h_filt]
  5. Each (j, k) term vanishes, completing the proof of the bilinear identity.

    The set {j, k} is nonempty (`Finset.mem_insert_self`), so its cardinality is at least 1 (`Finset.Nonempty.card_pos`). Furthermore, |{j, k}| ≤ |{k}| + 1 = 2 by `Finset.card_insert_le` and `Finset.card_singleton`. By `line_cubic_parity_repr_ortho_card_le_two`, the number of elements of S containing {j, k} is 0 in ZMod 2. Multiplying by c_j * d_k yields 0 (`mul_zero`).

    lines 54–61

    uses Finset.mem_insert_self, Finset.Nonempty.card_pos, Finset.card_insert_le, Finset.card_singleton, line_cubic_parity_repr_ortho_card_le_two, mul_zero

        have hne : ({j, k} : Finset (Fin n)).Nonempty := ⟨j, Finset.mem_insert_self j _⟩
        have hcard1 : 1 ≤ ({j, k} : Finset (Fin n)).card := Finset.Nonempty.card_pos hne
        have hcard2 : ({j, k} : Finset (Fin n)).card ≤ 2 := by
          have := Finset.card_insert_le j {k}
          rw [Finset.card_singleton] at this
          omega
        have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j, k} hcard1 hcard2
        rw [h_zero, mul_zero]
  6. It suffices to show that for each index j, the sum ∑_{y ∈ S} (if j ∈ y then c_j else 0) is zero.

    For the second conjunct, we rewrite ∑_{j ∈ y} c_j as the unrestricted sum ∑_{j} (if j ∈ y then c_j else 0) using `Finset.sum_ite_mem_eq`. Exchanging the summation order (`Finset.sum_comm`), it suffices by `Finset.sum_eq_zero` to show that the sum over y ∈ S vanishes for each fixed index j.

    lines 62–66

    uses Finset.sum_congr, Finset.sum_ite_mem_eq, Finset.sum_comm, Finset.sum_eq_zero

      · have h1 : (∑ y ∈ S, ∑ j ∈ y, c j) = ∑ y ∈ S, ∑ j : Fin n, if j ∈ y then c j else 0 := by
          refine Finset.sum_congr rfl (fun y _ => ?_)
          exact (Finset.sum_ite_mem_eq y c).symm
        rw [h1, Finset.sum_comm]
        refine Finset.sum_eq_zero (fun j _ => ?_)
  7. For fixed j, the sum over y ∈ S equals c_j times the cardinality modulo 2 of the sets y ∈ S containing {j}.

    Factoring c_j out of the sum (`Finset.mul_sum`), the remaining sum over y ∈ S of the indicator for j ∈ y evaluates to the cardinality of {x ∈ S | j ∈ x} modulo 2 by `Finset.sum_boole`. The membership condition j ∈ y is equivalent to {j} ⊆ y (`Finset.mem_filter`, `Finset.singleton_subset_iff`).

    lines 67–76

    uses Finset.mul_sum, Finset.sum_congr, Finset.sum_boole, Finset.mem_filter, Finset.singleton_subset_iff

        have h_split : (∑ y ∈ S, if j ∈ y then c j else 0) =
            c j * ∑ y ∈ S, (if j ∈ y then (1 : ZMod 2) else 0) := by
          rw [Finset.mul_sum]
          refine Finset.sum_congr rfl (fun y _ => ?_)
          split_ifs <;> ring
        rw [h_split, Finset.sum_boole]
        have h_filt : {x ∈ S | j ∈ x} = S.filter (fun y => {j} ⊆ y) := by
          ext y
          simp only [Finset.mem_filter, Finset.singleton_subset_iff]
        rw [h_filt]
  8. Each j term vanishes, completing the proof of linear orthogonality.

    The singleton {j} has cardinality 1 (`Finset.card_singleton`), which satisfies 1 ≤ |{j}| ≤ 2. Applying `line_cubic_parity_repr_ortho_card_le_two` gives that the number of elements in S containing {j} is 0 in ZMod 2. Multiplying by c_j gives 0 (`mul_zero`).

    lines 77–80

    uses Finset.card_singleton, line_cubic_parity_repr_ortho_card_le_two, mul_zero

        have hcard1 : 1 ≤ ({j} : Finset (Fin n)).card := by rw [Finset.card_singleton]
        have hcard2 : ({j} : Finset (Fin n)).card ≤ 2 := by rw [Finset.card_singleton]; omega
        have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j} hcard1 hcard2
        rw [h_zero, mul_zero]
congr_arg
Applying a function to equal arguments yields equal results.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Finset.card_singleton
The cardinality of any singleton set {a} is 1.
Finset.insert_subset_iff
The set insert a s is a subset of t if and only if a ∈ t and s ⊆ t.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_insert
An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_insert_self
An element a belongs to insert a s.
Finset.mem_singleton
An element b belongs to {a} if and only if b = a.
Finset.mul_sum
A factor distributes into a finite sum: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
Finset.Nonempty.card_pos
A nonempty finite set has strictly positive cardinality.
Finset.singleton_subset_iff
The singleton {a} is a subset of s if and only if a ∈ s.
Finset.sum_boole
The sum of a boolean indicator over a finite set equals the cardinality of the subset satisfying the predicate, cast into the ring.
Finset.sum_comm
The order of summation in a double finite sum can be exchanged.
Finset.sum_congr
Two sums over equal sets are equal if their terms agree on that set.
Finset.sum_eq_zero
A finite sum is zero if every summand is zero.
Finset.sum_ite_mem_eq
Summing an indicator-weighted term over all elements is equal to summing the term over the subset where the indicator holds.
Finset.sum_mul_sum
The product of two sums equals the double sum of the pairwise products of their terms.
line_cubic_parity_repr_ortho_card_le_two
For any parity representation S of line_syndrome n and any subset A with 1 ≤ |A| ≤ 2, the number of sets in S containing A is 0 modulo 2.
mul_zero
Multiplying any element by zero yields zero.

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

lemma line_cubic_parity_repr_ortho_card_le_two (n : ℕ)    (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n))    (A : Finset (Fin n)) (hA1 : 1 ≤ A.card) (hA2 : A.card ≤ 2) :    ((S.filter (fun y => A ⊆ y)).card : ZMod 2) = 0 := by  have hA3 : A.card ≤ 3 := by omega  have hrepr := hS.2 A ⟨hA1, hA3⟩  rw [hrepr]  unfold line_syndrome  split_ifs with h  · rcases h with ⟨i, hi⟩    have hc : ({⟨i.val, by omega⟩, ⟨i.val + 1, by omega⟩, ⟨i.val + 2, by omega⟩} : Finset (Fin n)).card = 3 := by      let a : Fin n := ⟨i.val, by omega⟩      let b : Fin n := ⟨i.val + 1, by omega⟩      let c : Fin n := ⟨i.val + 2, by omega⟩      change ({a, b, c} : Finset (Fin n)).card = 3      have hab : a ≠ b := by intro h; injection h with h; omega      have hac : a ≠ c := by intro h; injection h with h; omega      have hbc : b ≠ c := by intro h; injection h with h; omega      rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton]      · intro h; simp only [Finset.mem_singleton] at h; exact hbc h      · simp only [Finset.mem_insert, Finset.mem_singleton]; rintro (h | h)        · exact hab h        · exact hac h    have h_card_eq := congr_arg Finset.card hi    omega  · rfl/-- Every parity representation of the line cubic syndrome satisfies bilinear self-orthogonality and linear orthogonality to the all-ones vector. -/theorem line_cubic_parity_repr_ortho (n : ℕ)    (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n))    (c d : Fin n → ZMod 2) :    (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k) = 0) ∧    (∑ y ∈ S, (∑ j ∈ y, c j) = 0) := by  constructor  · have h1 : (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k)) =        ∑ y ∈ S, ∑ j : Fin n, ∑ k : Fin n, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0) := by      refine Finset.sum_congr rfl (fun y _ => ?_)      rw [← Finset.sum_ite_mem_eq y c, ← Finset.sum_ite_mem_eq y d]      rw [Finset.sum_mul_sum]    rw [h1, Finset.sum_comm]    refine Finset.sum_eq_zero (fun j _ => ?_)    rw [Finset.sum_comm]    refine Finset.sum_eq_zero (fun k _ => ?_)    have h_split : (∑ y ∈ S, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0)) =        (c j * d k) * ∑ y ∈ S, (if j ∈ y ∧ k ∈ y then (1 : ZMod 2) else 0) := by      rw [Finset.mul_sum]      refine Finset.sum_congr rfl (fun y _ => ?_)      by_cases hj : j ∈ y <;> by_cases hk : k ∈ y <;> simp [hj, hk]    rw [h_split, Finset.sum_boole]    have h_filt : {x ∈ S | j ∈ x ∧ k ∈ x} = S.filter (fun y => {j, k} ⊆ y) := by      ext y      simp only [Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff]    rw [h_filt]    have hne : ({j, k} : Finset (Fin n)).Nonempty := ⟨j, Finset.mem_insert_self j _⟩    have hcard1 : 1 ≤ ({j, k} : Finset (Fin n)).card := Finset.Nonempty.card_pos hne    have hcard2 : ({j, k} : Finset (Fin n)).card ≤ 2 := by      have := Finset.card_insert_le j {k}      rw [Finset.card_singleton] at this      omega    have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j, k} hcard1 hcard2    rw [h_zero, mul_zero]  · have h1 : (∑ y ∈ S, ∑ j ∈ y, c j) = ∑ y ∈ S, ∑ j : Fin n, if j ∈ y then c j else 0 := by      refine Finset.sum_congr rfl (fun y _ => ?_)      exact (Finset.sum_ite_mem_eq y c).symm    rw [h1, Finset.sum_comm]    refine Finset.sum_eq_zero (fun j _ => ?_)    have h_split : (∑ y ∈ S, if j ∈ y then c j else 0) =        c j * ∑ y ∈ S, (if j ∈ y then (1 : ZMod 2) else 0) := by      rw [Finset.mul_sum]      refine Finset.sum_congr rfl (fun y _ => ?_)      split_ifs <;> ring    rw [h_split, Finset.sum_boole]    have h_filt : {x ∈ S | j ∈ x} = S.filter (fun y => {j} ⊆ y) := by      ext y      simp only [Finset.mem_filter, Finset.singleton_subset_iff]    rw [h_filt]    have hcard1 : 1 ≤ ({j} : Finset (Fin n)).card := by rw [Finset.card_singleton]    have hcard2 : ({j} : Finset (Fin n)).card ≤ 2 := by rw [Finset.card_singleton]; omega    have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j} hcard1 hcard2    rw [h_zero, mul_zero]
See it in the graphDiscuss this resultChallenge it