AFTD Auto-Formalizing Theoretical Domains

op_159_css_ccz_stabilizer_rank_ge_two

theoremverifiedoriginal

For any block length n, if a 3 by n logical matrix K and an s by n stabilizer matrix S over ZMod 2 form a CSS quasi-transversal CCZ code, then the stabilizer rank s is at least 2.

Statement

theorem op_159_css_ccz_stabilizer_rank_ge_two (n s : ℕ)
    (K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin s) (Fin n) (ZMod 2))
    (h : css_quasi_transversal_ccz_code n s K S) : 2 ≤ s
Related work
arXiv:2610.09341 Prop. 4.3
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • css_quasi_transversal_ccz_codeA CSS quantum code of block length n specified by a 3 by n logical X-operator matrix K and an s by n X-stabilizer matrix S over ZMod 2 has…
  • op_159_css_ccz_no_code_s_zeroFor any block length n, no 3 by n logical X-operator matrix K and 0 by n X-stabilizer matrix S over ZMod 2 form a CSS quasi-transversal…
  • op_159_css_ccz_no_code_s_oneFor any block length n, no 3 by n logical X-operator matrix K and 1 by n X-stabilizer matrix S over ZMod 2 form a CSS quasi-transversal…

Read back from the Lean

For all natural numbers $n$ and $s$, and for all matrices $K \in \mathrm{Mat}_{3 \times n}(\mathbb{Z}/2\mathbb{Z})$ and $S \in \mathrm{Mat}_{s \times n}(\mathbb{Z}/2\mathbb{Z})$, if the pair $(K, S)$ forms a CSS quasi-transversal CCZ code (satisfying the CSS $Z$-distance at least 3 condition and the Campbell-Howard conditions), then $s \ge 2$ (the matrix $S$ has at least 2 rows).

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 contradiction. If the stabilizer rank s were strictly less than 2, then s would have to be 0 or 1. Both possibilities are ruled out by prior non-existence results, which show that no CSS quasi-transversal CCZ code can have stabilizer rank 0 or 1.

  1. Assume for contradiction that s < 2, reducing the problem to the cases s = 0 and s = 1.

    We proceed by contradiction, assuming ¬(2 ≤ s). By linear arithmetic over ℕ, this implies s < 2. Because s is a natural number, an exhaustive case analysis on the interval [0, 2) leaves only two cases: s = 0 and s = 1.

    lines 5–7

      by_contra hlt
      have hs : s < 2 := by omega
      interval_cases s
  2. The case s = 0 is impossible.

    The auxiliary theorem op_159_css_ccz_no_code_s_zero establishes that no CSS quasi-transversal CCZ code can have stabilizer rank 0, contradicting the hypothesis h.

    line 8

    uses op_159_css_ccz_no_code_s_zero

      · exact op_159_css_ccz_no_code_s_zero n K S h
  3. The case s = 1 is impossible, completing the proof.

    Similarly, op_159_css_ccz_no_code_s_one proves that no CSS quasi-transversal CCZ code can have stabilizer rank 1, which again contradicts h and closes the final branch.

    line 9

    uses op_159_css_ccz_no_code_s_one

      · exact op_159_css_ccz_no_code_s_one n K S h
op_159_css_ccz_no_code_s_zero
There is no CSS quasi-transversal CCZ code with stabilizer rank 0.
op_159_css_ccz_no_code_s_one
There is no CSS quasi-transversal CCZ code with stabilizer rank 1.

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

/-- Any CSS code of block length n with 3 logical qubits, Z-distance at least 3, and quasi-transversal CCZ must have stabilizer rank s at least 2. -/theorem op_159_css_ccz_stabilizer_rank_ge_two (n s : ℕ)    (K : Matrix (Fin 3) (Fin n) (ZMod 2)) (S : Matrix (Fin s) (Fin n) (ZMod 2))    (h : css_quasi_transversal_ccz_code n s K S) : 2 ≤ s := by  by_contra hlt  have hs : s < 2 := by omega  interval_cases s  · exact op_159_css_ccz_no_code_s_zero n K S h  · exact op_159_css_ccz_no_code_s_one n K S h
See it in the graphDiscuss this resultChallenge it