AFTD Auto-Formalizing Theoretical Domains

is_parity_repr

def

A 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 of qubits of cardinality at most 3 matches s(A) modulo 2.

Statement

def is_parity_repr {n : ℕ} (S : Finset (Finset (Fin n))) (s : Finset (Fin n) → ZMod 2) : Prop
Defined in
arXiv:2610.01024, Definition 20 and Fact 21
Verified
04 Oct 2026
Axioms
none listed
Used by 24
  • ccz_layer_parity_repr_card_geThe Hadamard-free floor of arXiv:2610.01024 (Corollary 83): every set of nonzero parities on 3m qubits whose order-1, 2, 3 moments equal…
  • line_cubic_t_count_fiveFor n = 5, there exists a parity representation of the line cubic syndrome of cardinality 11.
  • gf8_oracle_parity_repr_nonemptyEvery parity representation S of the GF(8) multiplication oracle syndrome is nonempty because the syndrome at {0, 3, 6} is 1 mod 2,…
  • gf8_oracle_min_t_count_le_29The minimal T-count of the GF(8) multiplication oracle is at most 29, certified by an explicit 29-parity representation.
  • 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.
  • ccz_layer_parity_repr_twoTwo disjoint CCZ gates have a parity representation with 13 = 6 * 2 + 1 parities, so the Hadamard-free T-count of the layer with m = 2 is…
  • gf8_oracle_t_count_le_29The GF(8) multiplication oracle has a parity representation with 29 parities, so its T-count delta(U_3) in Hadamard-free {CNOT, T}…
  • 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.
  • line_cubic_t_count_sixFor n = 6, there exists a parity representation of the line cubic syndrome of cardinality 13.
  • 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.
  • gf8_oracle_min_t_countThe minimal T-count of the GF(8) multiplication phase oracle on nine qubits in the Hadamard-free {CNOT, T} model, defined via the…
  • cyclic_cubic_min_t_count_eq_of_boundsIf there exists a parity representation of cardinality k, and all parity representations have cardinality at least k, then…
  • 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_t_count_fiveThere exists a finite set S : Finset (Finset (Fin 5)) such that is_parity_repr S (cyclic_cubic_syndrome 5) and S.card = 11.
  • line_cubic_t_count_lower_boundFor any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.
  • gf8_oracle_min_t_count_ge_20The slice-rank lower bound: the minimal T-count of the GF(8) multiplication oracle is at least 20.
  • gf8_oracle_t_count_ge_20The slice-rank floor of arXiv:2610.01024 Proposition 59 at k = 3: every parity representation of the GF(8) multiplication oracle's…
  • 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,…
  • cyclic_cubic_min_t_countFor a natural number n, cyclic_cubic_min_t_count n is the infimum in ℕ of the cardinalities of all parity representations S : Finset…
  • cyclic_cubic_t_count_isotropy_lower_boundFor 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…
  • 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…
  • 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.
  • open_problem_line_cubic_t_countFor every integer n ≥ 5, there exists a parity representation of the line cubic syndrome of cardinality 2n + 1.
  • cyclic_cubic_t_count_sixThere exists a finite set S : Finset (Finset (Fin 6)) such that is_parity_repr S (cyclic_cubic_syndrome 6) and S.card = 17.

Read back from the Lean

Given a natural number $n$, a family of subsets $S$ of $\mathrm{Fin}(n)$ (i.e., a Finset (Finset (Fin n))), and a function $s : \mathrm{Finset}(\mathrm{Fin}(n)) \to \mathbb{Z}/2\mathbb{Z}$, the definition is_parity_repr S s asserts that: 1. Every element $y \in S$ is non-empty (y.Nonempty). 2. For every subset $A \subseteq \mathrm{Fin}(n)$ whose cardinality satisfies $1 \le |A| \le 3$, the number of sets $y \in S$ that contain $A$ ($A \subseteq y$), reduced modulo 2 (as an element of $\mathbb{Z}/2\mathbb{Z}$), equals $s(A)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A set S of nonempty parities on n qubits represents a syndrome s if for all subsets A of size 1, 2, or 3, the number of parities containing A has parity matching s A. -/
def is_parity_repr {n : ℕ} (S : Finset (Finset (Fin n))) (s : Finset (Fin n) → ZMod 2) : Prop := (∀ y ∈ S, y.Nonempty) ∧
  (∀ A : Finset (Fin n), 1 ≤ A.card ∧ A.card ≤ 3 →
    ((S.filter (fun y => A ⊆ y)).card : ZMod 2) = s A)
See it in the graphDiscuss this resultChallenge it