gf8_oracle_syndrome_eq_zero_of_card_ne_three
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.
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`).
unfold gf8_oracle_syndrome split_ifs with hex
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}.
· exfalso apply h rcases hex with ⟨q, r, l, -, rfl⟩
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.
fin_cases q <;> fin_cases r <;> fin_cases l <;> decideWhen 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`).
· rfl
- The proof establishes that {q, 3 + r, 6 + l} has cardinality 3 by exhaustive enumeration (using `fin_cases` on q, r, and l, followed by `decide` on all 27 cases) rather than by proving algebraically that the three indices lie in pairwise disjoint intervals [0, 2], [3, 5], and [6, 8].
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
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.
/-- 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