AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_t_count_six

theoremverifiedoriginal

There exists a finite set S : Finset (Finset (Fin 6)) such that is_parity_repr S (cyclic_cubic_syndrome 6) and S.card = 17.

Statement

theorem cyclic_cubic_t_count_six : ∃ S : Finset (Finset (Fin 6)), is_parity_repr S (cyclic_cubic_syndrome 6) ∧ S.card = 17
Related work
arXiv:2610.01024
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • cyclic_cubic_syndromeFor a natural number n and a finite subset A of Fin n, cyclic_cubic_syndrome n A returns 1 in ZMod 2 if there exists j : Fin n such that A…
  • 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…

Read back from the Lean

There exists a collection $S$ of subsets of $\text{Fin } 6$ such that: 1. Every subset $y \in S$ is nonempty. 2. For every subset $A \subseteq \text{Fin } 6$ with $1 \le |A| \le 3$, the number of sets $y \in S$ containing $A$ is odd if $A = \{j, (j+1)\%6, (j+2)\%6\}$ for some $j \in \text{Fin } 6$, and even otherwise. 3. The cardinality of $S$ is 17.

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 proof establishes the existence of a 17-element parity representation for the cyclic cubic syndrome on Fin 6 by exhibiting an explicit family S of 17 subsets. Both the cardinality |S| = 17 and the condition that S parity-represents the cyclic cubic syndrome are verified by exhaustive computation in the Lean kernel (`decide +kernel`).

  1. There exists a candidate family S of 17 subsets of Fin 6 whose cardinality is 17.

    We instantiate the existential quantifier with an explicit family S consisting of 17 subsets of Fin 6: {0, 1}, {0, 1, 2}, {0, 3}, {0, 1, 3}, {0, 1, 2, 3}, {2, 4}, {1, 3, 4}, {0, 1, 3, 4}, {2, 3, 4}, {5}, {0, 3, 5}, {0, 4, 5}, {2, 4, 5}, {0, 2, 4, 5}, {3, 4, 5}, {1, 2, 3, 4, 5}, and {0, 1, 2, 3, 4, 5}. The cardinality goal |S| = 17 is verified immediately by kernel evaluation (`decide +kernel`), leaving the parity representation condition to be verified.

    lines 3–5

      refine ⟨{{0, 1}, {0, 1, 2}, {0, 3}, {0, 1, 3}, {0, 1, 2, 3}, {2, 4}, {1, 3, 4}, {0, 1, 3, 4},
        {2, 3, 4}, {5}, {0, 3, 5}, {0, 4, 5}, {2, 4, 5}, {0, 2, 4, 5}, {3, 4, 5},
        {1, 2, 3, 4, 5}, {0, 1, 2, 3, 4, 5}}, ?_, by decide +kernel⟩
  2. The family S is a parity representation of the cyclic cubic syndrome on Fin 6. automation

    Unfolding the definitions of is_parity_repr and cyclic_cubic_syndrome reduces the parity condition to an explicit check over all subsets A ⊆ Fin 6 with 1 ≤ |A| ≤ 3: every set in S must be nonempty, and the number of sets in S containing A must be odd if A is a cyclic triple {j, (j+1) % 6, (j+2) % 6} and even otherwise. Because Fin 6 is finite (with only 41 subsets of size 1, 2, or 3), this entire finite combinatorial condition is decided by exhaustive kernel evaluation (`decide +kernel`).

    lines 6–7

    uses is_parity_repr, cyclic_cubic_syndrome

      unfold is_parity_repr cyclic_cubic_syndrome
      decide +kernel
is_parity_repr
A family S of nonempty subsets of Fin n is a parity representation of syndrome s if for all subsets A of size between 1 and 3, the number of sets in S covering A has the same parity as s(A).
cyclic_cubic_syndrome
The syndrome on subsets of Fin n taking value 1 on contiguous cyclic triples {j, (j+1) % n, (j+2) % n} and 0 on all other subsets.

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

/-- For n = 6, there exists a parity representation of the cyclic cubic syndrome of cardinality 17. -/theorem cyclic_cubic_t_count_six : ∃ S : Finset (Finset (Fin 6)), is_parity_repr S (cyclic_cubic_syndrome 6) ∧ S.card = 17 := by  refine ⟨{{0, 1}, {0, 1, 2}, {0, 3}, {0, 1, 3}, {0, 1, 2, 3}, {2, 4}, {1, 3, 4}, {0, 1, 3, 4},    {2, 3, 4}, {5}, {0, 3, 5}, {0, 4, 5}, {2, 4, 5}, {0, 2, 4, 5}, {3, 4, 5},    {1, 2, 3, 4, 5}, {0, 1, 2, 3, 4, 5}}, ?_, by decide +kernel⟩  unfold is_parity_repr cyclic_cubic_syndrome  decide +kernel
See it in the graphDiscuss this resultChallenge it