AFTD Auto-Formalizing Theoretical Domains

gf8_oracle_min_t_count_le_29

theoremverifiedformalization

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.

  1. 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.

    line 2

    uses Nat.sInf_le, gf8_oracle_t_count_le_29

    theorem 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
See it in the graphDiscuss this resultChallenge it