AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_t_count_five

theoremverifiedoriginal

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

Statement

theorem cyclic_cubic_t_count_five : ∃ S : Finset (Finset (Fin 5)), is_parity_repr S (cyclic_cubic_syndrome 5) ∧ S.card = 11
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 family $S$ of subsets of $\text{Fin } 5$ such that: 1. Every set $y \in S$ is nonempty; 2. For every subset $A \subseteq \text{Fin } 5$ with $1 \le |A| \le 3$, the number of elements $y \in S$ with $A \subseteq y$ is odd if $A = \{j, (j+1) \bmod 5, (j+2) \bmod 5\}$ for some $j \in \text{Fin } 5$, and even otherwise; and 3. The cardinality of $S$ is 11.

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 theorem is proved by exhibiting an explicit family S of 11 subsets of {0, 1, 2, 3, 4}. Lean's trusted kernel checks by finite exhaustive computation that S has cardinality 11, that every member of S is nonempty, and that the parity of the number of sets containing any subset A of size at most 3 matches the cyclic cubic syndrome.

  1. The candidate family S of 11 subsets of {0, 1, 2, 3, 4} has cardinality 11, reducing the theorem to showing that S is a parity representation of the cyclic cubic syndrome.

    We supply the explicit family S = {{1}, {0, 1}, {2}, {0, 3}, {2, 3}, {0, 1, 4}, {1, 2, 4}, {0, 1, 3, 4}, {2, 3, 4}, {0, 2, 3, 4}, {0, 1, 2, 3, 4}} as a witness for the existential quantifier. Lean verifies that S contains exactly 11 elements by kernel computation via `decide +kernel`.

    line 3

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

    Unfolding the definitions of `is_parity_repr` and `cyclic_cubic_syndrome`, the remaining requirement is that every element of S is non-empty, and that for every subset A ⊆ {0, 1, 2, 3, 4} of size 1, 2, or 3, the number of sets in S containing A is odd if and only if A consists of three cyclically consecutive elements modulo 5. Because the domain {0, 1, 2, 3, 4} is finite, this is a bounded decidable proposition, which the kernel evaluates to true by exhaustive case checking via `decide +kernel`.

    lines 4–5

      unfold is_parity_repr cyclic_cubic_syndrome
      decide +kernel

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 = 5, there exists a parity representation of the cyclic cubic syndrome of cardinality 11. -/theorem cyclic_cubic_t_count_five : ∃ S : Finset (Finset (Fin 5)), is_parity_repr S (cyclic_cubic_syndrome 5) ∧ S.card = 11 := by  refine ⟨{{1}, {0, 1}, {2}, {0, 3}, {2, 3}, {0, 1, 4}, {1, 2, 4}, {0, 1, 3, 4}, {2, 3, 4}, {0, 2, 3, 4}, {0, 1, 2, 3, 4}}, ?_, by decide +kernel⟩  unfold is_parity_repr cyclic_cubic_syndrome  decide +kernel
See it in the graphDiscuss this resultChallenge it