AFTD Auto-Formalizing Theoretical Domains

css_z_distance_ge_three_iff_cols

theoremverified

A CSS quantum code specified by a k by n logical X-operator matrix K and an s by n X-stabilizer matrix S over ZMod 2 has Z-distance at least 3 if and only if its columns are multiplicity-free: no column has zero syndrome with nonzero logical label, and no two distinct columns have equal syndrome but different logical labels.

Statement

theorem css_z_distance_ge_three_iff_cols {k s n : ℕ}
    (K : Matrix (Fin k) (Fin n) (ZMod 2)) (S : Matrix (Fin s) (Fin n) (ZMod 2)) :
    css_z_distance_ge_three K S ↔
      ((∀ j, S.transpose j = 0 → K.transpose j = 0) ∧
        (∀ i j, i ≠ j → S.transpose i = S.transpose j → K.transpose i = K.transpose j))
Source
arXiv:2610.09341 Lemma 2.1
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • css_z_distance_ge_threeA CSS quantum code specified by a k by n logical X-operator matrix K and an s by n X-stabilizer matrix S over ZMod 2 has Z-distance at…
  • css_z_distance_ge_three_iff_multiplicity_freeFor binary matrices K (k × n) and S (s × n), the CSS code with generator matrix [K; S] has Z-distance at least 3 (every v ∈ F_2^n with Sv…
Used by 2
  • 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 any natural numbers $k$, $s$, and $n$, and any matrices $K \in \mathrm{Matrix}(\mathrm{Fin}\ k, \mathrm{Fin}\ n, \mathbb{Z}/2\mathbb{Z})$ and $S \in \mathrm{Matrix}(\mathrm{Fin}\ s, \mathrm{Fin}\ n, \mathbb{Z}/2\mathbb{Z})$, the property css_z_distance_ge_three K S holds if and only if both: 1. For every column index $j \in \mathrm{Fin}\ n$, if the $j$-th column of $S$ is the zero vector, then the $j$-th column of $K$ is the zero vector; and 2. For all pairs of distinct column indices $i, j \in \mathrm{Fin}\ n$ ($i \ne j$), if the $i$-th column of $S$ equals the $j$-th column of $S$, then the $i$-th column of $K$ equals the $j$-th column of $K$.

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 characterizes when a CSS code has $Z$-distance at least 3 in terms of its column syndromes and logical labels. The proof unfolds the definition of `css_z_distance_ge_three` into the requirement that no non-trivial logical $X$-error has Hamming weight 1 or 2, and then immediately concludes by invoking the lemma `css_z_distance_ge_three_iff_multiplicity_free`.

  1. The condition that the CSS code has $Z$-distance at least $3$ is equivalent to the columns of $S$ and $K$ being multiplicity-free.

    Unfolding the definition of `css_z_distance_ge_three` expresses the left-hand side as the statement that every error vector $v$ with stabilizer syndrome $S v = 0$ and non-trivial logical effect $K v \neq 0$ has Hamming weight at least $3$. Applying `css_z_distance_ge_three_iff_multiplicity_free` then concludes that this minimum-weight condition is equivalent to the two column conditions: zero-syndrome columns must have zero logical label, and distinct columns with the same syndrome must share the same logical label.

    lines 7–8

    uses css_z_distance_ge_three_iff_multiplicity_free

      unfold css_z_distance_ge_three
      exact css_z_distance_ge_three_iff_multiplicity_free K S
css_z_distance_ge_three_iff_multiplicity_free
A vector $v$ satisfying $S v = 0$ and $K v \neq 0$ has Hamming weight at least $3$ if and only if every column with syndrome zero has logical label zero, and any two distinct columns with identical syndromes also have identical logical labels.

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

/-- Z-distance at least 3 is equivalent to multiplicity-free columns. -/theorem css_z_distance_ge_three_iff_cols {k s n : ℕ}    (K : Matrix (Fin k) (Fin n) (ZMod 2)) (S : Matrix (Fin s) (Fin n) (ZMod 2)) :    css_z_distance_ge_three K S ↔      ((∀ j, S.transpose j = 0 → K.transpose j = 0) ∧        (∀ i j, i ≠ j → S.transpose i = S.transpose j → K.transpose i = K.transpose j)) := by  unfold css_z_distance_ge_three  exact css_z_distance_ge_three_iff_multiplicity_free K S
See it in the graphDiscuss this resultChallenge it