gf8_oracle_syndrome_zero_zero_zero
Sanity check: the syndrome of the GF(8) oracle is 1 on {x_0, y_0, z_0}, since 1 * 1 = 1 has bit 0 set.
Statement
theorem gf8_oracle_syndrome_zero_zero_zero : gf8_oracle_syndrome {0, 3, 6} = 1- Source
- sanity check of the definition gf8_oracle_syndrome (arXiv:2610.01024 Prop. 55 and Fact 21)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 =…
- Used by 1
- gf8_oracle_parity_repr_nonemptyEvery parity representation S of the GF(8) multiplication oracle syndrome is nonempty because the syndrome at {0, 3, 6} is 1 mod 2,…
The proof, explained
The theorem verifies that the oracle syndrome evaluates to $1$ on the set $\{0, 3, 6\}$. Unfolding the definition reduces this to an existential search over indices $q, r, l \in \{0, 1, 2\}$, which is satisfied by the choice $q = r = l = 0$. Since all types and predicates involved are finite and decidable, the proof is closed by direct computation.
The oracle syndrome on the subset $\{0, 3, 6\}$ evaluates to $1$. automation
By definition, $\text{gf8\_oracle\_syndrome}(\{0, 3, 6\}) = 1$ if there exist indices $q, r, l \in \text{Fin } 3$ such that $\{q, 3 + r, 6 + l\} = \{0, 3, 6\}$ and $\text{gf8\_mult\_coeff}(q, r, l) = 1$. The witness $q = 0, r = 0, l = 0$ satisfies both conditions, since $\{0, 3, 6\} = \{0, 3, 6\}$ and $\text{gf8\_mult\_coeff}(0, 0, 0) = 1$ (the $(0+0, 0) = (0, 0)$ branch of the definition). Because this search is over finite types, the `decide` tactic completes the proof by direct evaluation.
theorem gf8_oracle_syndrome_zero_zero_zero : gf8_oracle_syndrome {0, 3, 6} = 1 := by decide
- The proof is executed entirely by computational reflection (`decide`), which evaluates the finite existential search and definitions in the kernel.
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
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.
theorem gf8_oracle_syndrome_zero_zero_zero : gf8_oracle_syndrome {0, 3, 6} = 1 := by decide