AFTD Auto-Formalizing Theoretical Domains

gf8_oracle_parity_repr_nonempty

theoremverified

Every parity representation S of the GF(8) multiplication oracle syndrome is nonempty because the syndrome at {0, 3, 6} is 1 mod 2, whereas an empty representation would yield moment 0.

Statement

theorem gf8_oracle_parity_repr_nonempty (S : Finset (Finset (Fin 9)))
    (hS : is_parity_repr S gf8_oracle_syndrome) : S.Nonempty
Source
step towards gf8_oracle_t_count_le_23
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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 =…
  • gf8_oracle_syndrome_zero_zero_zeroSanity 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.

The proof, explained

We argue by contradiction, assuming that the parity representation S is empty. By the definition of a parity representation, the number of sets in S containing any subset of size between 1 and 3 (mod 2) must equal the syndrome on that subset. Evaluating this condition at {0, 3, 6} requires the moment to be 1, but an empty collection S = ∅ contains no supersets and therefore has moment 0, a contradiction.

  1. The moment condition holds for the parity representation S.

    Unpack the definition of `is_parity_repr` to extract `hmom`, which asserts that for any subset A of {0, ..., 8} with 1 ≤ |A| ≤ 3, the number of sets in S containing A modulo 2 equals `gf8_oracle_syndrome A`.

    line 4

      rcases hS with ⟨-, hmom⟩
  2. Assume for contradiction that S = ∅.

    Assume for contradiction that S is not nonempty (`by_contra`). By `Finset.not_nonempty_iff_eq_empty`, this is equivalent to S = ∅, which we substitute into the hypotheses.

    lines 5–7

    uses Finset.not_nonempty_iff_eq_empty

      by_contra h
      rw [Finset.not_nonempty_iff_eq_empty] at h
      subst h
  3. The moment condition applies to the set {0, 3, 6}.

    Specialize the moment condition `hmom` to the set A = {0, 3, 6}. Both bounds 1 ≤ |A| and |A| ≤ 3 are verified by decidable computation (`decide`), yielding that the count modulo 2 of supersets of {0, 3, 6} in the empty set equals `gf8_oracle_syndrome {0, 3, 6}`.

    line 8

      have hm := hmom ({0, 3, 6} : Finset (Fin 9)) ⟨by decide, by decide⟩
  4. Contradiction: 0 = 1 in ZMod 2.

    Rewrite the right-hand syndrome value to 1 using `gf8_oracle_syndrome_zero_zero_zero`. Since S is empty, no element contains {0, 3, 6}, so the left-hand side counts an empty set and evaluates to 0. Simplifying this equality produces 0 = 1 in ZMod 2, which is false and closes the proof.

    lines 9–10

    uses gf8_oracle_syndrome_zero_zero_zero

      rw [gf8_oracle_syndrome_zero_zero_zero] at hm
      simp at hm
Finset.not_nonempty_iff_eq_empty
A finite set is not nonempty if and only if it is empty.
gf8_oracle_syndrome_zero_zero_zero
The GF(8) multiplication oracle syndrome evaluates to 1 on the set {0, 3, 6}.

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

/-- Every parity representation of the GF(8) multiplication oracle syndrome is nonempty. -/theorem gf8_oracle_parity_repr_nonempty (S : Finset (Finset (Fin 9)))    (hS : is_parity_repr S gf8_oracle_syndrome) : S.Nonempty := by  rcases hS with ⟨-, hmom⟩  by_contra h  rw [Finset.not_nonempty_iff_eq_empty] at h  subst h  have hm := hmom ({0, 3, 6} : Finset (Fin 9)) ⟨by decide, by decide⟩  rw [gf8_oracle_syndrome_zero_zero_zero] at hm  simp at hm
See it in the graphDiscuss this resultChallenge it