css_z_distance_ge_three_iff_cols
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`.
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.
uses
css_z_distance_ge_three_iff_multiplicity_freeunfold 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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