gf8_oracle_min_t_count_le_29
The minimal T-count of the GF(8) multiplication oracle is at most 29, certified by an explicit 29-parity representation.
Statement
theorem gf8_oracle_min_t_count_le_29 : gf8_oracle_min_t_count ≤ 29- Formalizes
- arXiv:2610.01024, Remark 83 and Table 6
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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}…
- 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 =…
Read back from the Lean
The minimum (infimum in ℕ) size of a family S of nonempty subsets of Fin 9 that forms a parity representation of the syndrome function gf8_oracle_syndrome on subsets of size 1, 2, and 3 is at most 29.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The minimal T-count `gf8_oracle_min_t_count` is defined as the infimum of the cardinalities of all valid parity representations for the GF(8) multiplication oracle. The companion theorem `gf8_oracle_t_count_le_29` proves that 29 is achievable by exhibiting an explicit parity representation of size 29. By `Nat.sInf_le`, the infimum of any set of natural numbers is at most any element in that set, yielding the upper bound 29.
The minimal T-count of the GF(8) multiplication oracle is at most 29.
By definition, `gf8_oracle_min_t_count` is the infimum of the set of sizes of all parity representations for the GF(8) multiplication oracle. The theorem `gf8_oracle_t_count_le_29` exhibits a 29-element parity representation, establishing that 29 belongs to this set. Applying `Nat.sInf_le` to this membership witness directly yields that the infimum is at most 29.
uses
Nat.sInf_le,gf8_oracle_t_count_le_29theorem gf8_oracle_min_t_count_le_29 : gf8_oracle_min_t_count ≤ 29 := Nat.sInf_le gf8_oracle_t_count_le_29
Nat.sInf_le- For any set of natural numbers s and any natural number m, if m ∈ s, then the infimum of s is at most m.
gf8_oracle_t_count_le_29- There exists an explicit parity representation for the GF(8) multiplication oracle consisting of 29 sets.
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
/-- The upper bound: the minimal T-count of the GF(8) multiplication oracle is at most 29. -/theorem gf8_oracle_min_t_count_le_29 : gf8_oracle_min_t_count ≤ 29 := Nat.sInf_le gf8_oracle_t_count_le_29