gf8_oracle_t_count_le_29
The GF(8) multiplication oracle has a parity representation with 29 parities, so its T-count delta(U_3) in Hadamard-free {CNOT, T} circuits is at most 29 (an explicit certificate found by SAT search; the merged schoolbook expansion has 36).
Statement
theorem gf8_oracle_t_count_le_29 : ∃ S : Finset (Finset (Fin 9)), is_parity_repr S gf8_oracle_syndrome ∧ S.card = 29- Formalizes
- Exact T-counts of Toffoli Layers from an Isotropy Bound, arXiv:2610.01024, Open Problem 10: the best published circuit for the GF(8) oracle already has T-count 23, so this bound 29 is weaker than the published one; the 29-parity certificate itself was found here by SAT search
- Verified
- 06 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…
- gf8_oracle_syndromeThe syndrome s_A of the GF(8) multiplication phase oracle U_3 |x, y, z> = (-1)^{z . (x * y)} |x, y, z> on nine qubits: s_A = 1 iff A =…
- Used by 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.
- 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.
The proof, explained
The theorem is proved by providing an explicit witness: a family S of 29 subsets of {0, ..., 8} discovered via SAT search. The claim that S has size 29 and satisfies the parity representation condition for the GF(8) multiplication oracle is then verified by direct exhaustive computation in the Lean kernel (`decide +kernel`).
It suffices to verify that the explicit 29-element family of subsets S is a parity representation of the GF(8) oracle syndrome.
To prove the existential statement, we instantiate S with an explicit family of 29 concrete subsets of {0, ..., 8} found by SAT search. The conjunct S.card = 29 is proved immediately by kernel computation (`decide +kernel`), which verifies that the 29 listed subsets are all distinct. This leaves only the goal of showing that S satisfies `is_parity_repr S gf8_oracle_syndrome`.
refine ⟨{{0, 1, 2, 3, 5, 6, 7}, {0, 1, 2, 3, 5, 7}, {0, 1, 2, 4, 6, 7}, {0, 1, 2, 4, 8}, {0, 1, 2, 7}, {0, 1, 2, 8}, {0, 2, 4, 5, 6, 7, 8}, {0, 2, 4, 5, 7}, {0, 2, 6, 7, 8}, {0, 2, 7}, {1, 2, 3, 5, 6, 7, 8}, {1, 2, 3, 5, 8}, {1, 2, 4, 5, 6, 8}, {1, 2, 4, 5, 7, 8}, {1, 3, 5, 6, 7, 8}, {1, 3, 5, 6, 8}, {1, 3, 7, 8}, {1, 3, 8}, {2, 3, 4, 5, 7, 8}, {2, 3, 4, 5, 7}, {2, 3, 6, 7}, {2, 3, 6}, {2, 4, 5, 7, 8}, {2, 4, 5}, {3, 4, 5, 6, 8}, {3, 4, 5, 6}, {4, 6, 8}, {4, 7}, {6, 7}}, ?_, by decide +kernel⟩
The candidate family S satisfies the parity representation condition for the GF(8) multiplication oracle syndrome. automation
Unfolding the definition of `is_parity_repr` expresses the goal as two conditions: every subset in S must be nonempty, and for every subset A ⊆ {0, ..., 8} with 1 ≤ |A| ≤ 3, the number of elements of S containing A must match `gf8_oracle_syndrome A` modulo 2. Because the domain {0, ..., 8} is finite, there are only 9 + 36 + 84 = 129 such subsets A, making this an entirely decidable finite check. The tactic `decide +kernel` performs this exhaustive evaluation in the Lean kernel, closing the goal.
unfold is_parity_repr decide +kernel
- Both the cardinality check |S| = 29 and the verification that S is a parity representation for the GF(8) multiplication oracle syndrome are carried out by exhaustive computation in the Lean kernel (`decide +kernel`), relying on the decidability of finite set operations.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem gf8_oracle_t_count_le_29 : ∃ S : Finset (Finset (Fin 9)), is_parity_repr S gf8_oracle_syndrome ∧ S.card = 29 := by refine ⟨{{0, 1, 2, 3, 5, 6, 7}, {0, 1, 2, 3, 5, 7}, {0, 1, 2, 4, 6, 7}, {0, 1, 2, 4, 8}, {0, 1, 2, 7}, {0, 1, 2, 8}, {0, 2, 4, 5, 6, 7, 8}, {0, 2, 4, 5, 7}, {0, 2, 6, 7, 8}, {0, 2, 7}, {1, 2, 3, 5, 6, 7, 8}, {1, 2, 3, 5, 8}, {1, 2, 4, 5, 6, 8}, {1, 2, 4, 5, 7, 8}, {1, 3, 5, 6, 7, 8}, {1, 3, 5, 6, 8}, {1, 3, 7, 8}, {1, 3, 8}, {2, 3, 4, 5, 7, 8}, {2, 3, 4, 5, 7}, {2, 3, 6, 7}, {2, 3, 6}, {2, 4, 5, 7, 8}, {2, 4, 5}, {3, 4, 5, 6, 8}, {3, 4, 5, 6}, {4, 6, 8}, {4, 7}, {6, 7}}, ?_, by decide +kernel⟩ unfold is_parity_repr decide +kernel