is_parity_repr
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)