AFTD Auto-Formalizing Theoretical Domains

gf8_oracle_min_t_count_ge_20

theoremverifiedformalization

The slice-rank lower bound: the minimal T-count of the GF(8) multiplication oracle is at least 20.

Statement

theorem gf8_oracle_min_t_count_ge_20 : 20 ≤ gf8_oracle_min_t_count
Formalizes
arXiv:2610.01024, Proposition 84
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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_ge_20The slice-rank floor of arXiv:2610.01024 Proposition 59 at k = 3: every parity representation of the GF(8) multiplication oracle's…
  • 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 theorem asserts that $20 \le \text{gf8\_oracle\_min\_t\_count}$, where $\text{gf8\_oracle\_min\_t\_count}$ is the infimum in $\mathbb{N}$ of all $k \in \mathbb{N}$ for which there exists a family $S$ of $k$ non-empty subsets of $\text{Fin } 9$ that is a parity representation of the syndrome function $\text{gf8\_oracle\_syndrome}$ on all subsets of $\text{Fin } 9$ of size between 1 and 3.

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 of the GF(8) multiplication oracle is defined as the infimum of the cardinalities of all its parity representations. Applying the infimum lower-bound lemma le_csInf reduces the goal to showing that the set of valid representation sizes is nonempty and that every member is at least 20. Nonemptiness is witnessed by an explicit construction of size 29 (gf8_oracle_t_count_le_29), and the lower bound is provided by the slice-rank theorem gf8_oracle_t_count_ge_20.

  1. To establish that 20 ≤ gf8_oracle_min_t_count, it suffices to show that the set of sizes of parity representations of the GF(8) oracle syndrome is nonempty and that every element of that set is at least 20.

    Unfolding the definition shows that gf8_oracle_min_t_count is the infimum of the set of cardinalities of all parity representations S of the GF(8) multiplication oracle syndrome. Applying le_csInf reduces a lower bound on an infimum in ℕ to two subgoals: proving that the set is nonempty, and showing that 20 is a lower bound for every element in the set.

    lines 3–4

    uses le_csInf

      unfold gf8_oracle_min_t_count
      apply le_csInf
  2. The set of sizes of parity representations of the GF(8) oracle syndrome is nonempty.

    Lemma gf8_oracle_t_count_le_29 provides an explicit parity representation S with cardinality 29. Providing 29 along with S, its representation proof, and its cardinality witnesses that 29 belongs to the set.

    lines 5–6

    uses gf8_oracle_t_count_le_29

      · obtain ⟨S, hS, hc⟩ := gf8_oracle_t_count_le_29
        exact ⟨29, S, hS, hc⟩
  3. Every element of the set of representation sizes is at least 20.

    Let b be any element in the set. By definition, b = S.card for some parity representation S of the oracle syndrome. The slice-rank lower bound theorem gf8_oracle_t_count_ge_20 directly proves that any such parity representation satisfies 20 ≤ S.card.

    lines 7–9

    uses gf8_oracle_t_count_ge_20

      · intro b hb
        obtain ⟨S, hS, rfl⟩ := hb
        exact gf8_oracle_t_count_ge_20 S hS
le_csInf
In a conditionally complete lattice, a ≤ sInf s holds provided s is nonempty and a ≤ b for all b ∈ s.
gf8_oracle_t_count_le_29
There exists a parity representation of the GF(8) oracle syndrome with cardinality 29.
gf8_oracle_t_count_ge_20
Every parity representation of the GF(8) oracle syndrome has cardinality at least 20.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The slice-rank lower bound: the minimal T-count of the GF(8) multiplication oracle is at least 20. -/theorem gf8_oracle_min_t_count_ge_20 : 20 ≤ gf8_oracle_min_t_count := by  unfold gf8_oracle_min_t_count  apply le_csInf  · obtain ⟨S, hS, hc⟩ := gf8_oracle_t_count_le_29    exact ⟨29, S, hS, hc⟩  · intro b hb    obtain ⟨S, hS, rfl⟩ := hb    exact gf8_oracle_t_count_ge_20 S hS
See it in the graphDiscuss this resultChallenge it