AFTD Auto-Formalizing Theoretical Domains

gf8_oracle_syndrome_eq_zero_of_card_ne_three

theoremverified

The syndrome of the GF(8) multiplication oracle vanishes on any subset A ⊆ Fin 9 whose cardinality is not 3, because non-zero syndrome terms arise only from triples connecting the three 3-qubit registers.

Statement

theorem gf8_oracle_syndrome_eq_zero_of_card_ne_three (A : Finset (Fin 9)) (h : A.card ≠ 3) :
    gf8_oracle_syndrome A = 0
Source
step towards gf8_oracle_t_count_le_23
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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 =…
  • gf8_mult_coeffThe structure constants for multiplication in GF(8) with respect to the basis {1, alpha, alpha^2} with irreducible polynomial alpha^3 +…

The proof, explained

The proof unfolds the definition of `gf8_oracle_syndrome A` and splits on whether A arises from a valid multiplication triple. If no such triple exists, the syndrome is 0 by definition. If such a triple does exist, A = {q, 3 + r, 6 + l} for some q, r, l ∈ Fin 3; an exhaustive check of all 27 cases shows that such a set always has cardinality 3, contradicting the hypothesis |A| ≠ 3.

  1. Evaluating the syndrome reduces to distinguishing whether A is an oracle triple or not.

    Unfolding the definition of `gf8_oracle_syndrome A` reveals an `if-then-else` expression: the syndrome is 1 if there exist q, r, l ∈ Fin 3 such that `gf8_mult_coeff q r l = 1` and A = {q, 3 + r, 6 + l}, and 0 otherwise. We split into cases on whether this existential condition holds (`split_ifs with hex`).

    lines 4–5

      unfold gf8_oracle_syndrome
      split_ifs with hex
  2. In the case where A arises from an oracle triple, it suffices to show that {q, 3 + r, 6 + l} has cardinality 3.

    When the existential condition holds, the definition evaluates to 1, leaving the false equation 1 = 0. By `exfalso` and applying the hypothesis h (which states |A| ≠ 3), the goal reduces to showing |A| = 3. Deconstructing the existential witness `hex` extracts the indices q, r, l ∈ Fin 3 and substitutes A = {q, 3 + r, 6 + l}.

    lines 6–8

      · exfalso
        apply h
        rcases hex with ⟨q, r, l, -, rfl⟩
  3. For all q, r, l ∈ Fin 3, the set {q, 3 + r, 6 + l} has cardinality 3.

    Because q, r, and l each belong to the three-element type Fin 3, there are only 3 × 3 × 3 = 27 possible triples. Exhausting all possibilities with `fin_cases` leaves 27 concrete goals, in each of which the three elements fall into the disjoint ranges {0, 1, 2}, {3, 4, 5}, and {6, 7, 8}. Lean's `decide` tactic evaluates the cardinality of each explicit set by direct computation, confirming it is 3 in every case and thereby closing the contradiction.

    line 9

        fin_cases q <;> fin_cases r <;> fin_cases l <;> decide
  4. When no such triple exists, the syndrome is 0.

    In the negative branch of the `if-then-else`, the definition directly evaluates to 0, leaving the goal 0 = 0, which holds by reflexivity (`rfl`).

    line 10

      · rfl

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 syndrome of the GF(8) multiplication oracle vanishes on any subset whose cardinality is not 3. -/theorem gf8_oracle_syndrome_eq_zero_of_card_ne_three (A : Finset (Fin 9)) (h : A.card ≠ 3) :    gf8_oracle_syndrome A = 0 := by  unfold gf8_oracle_syndrome  split_ifs with hex  · exfalso    apply h    rcases hex with ⟨q, r, l, -, rfl⟩    fin_cases q <;> fin_cases r <;> fin_cases l <;> decide  · rfl
See it in the graphDiscuss this resultChallenge it