Skip to content

Connected Basis For Nonzero-Coordinate Code

Claim/Theorem

This node is a graph-internal linear-algebra lemma used to attack the explicit quantum Tanner gap. Let \(C\subseteq \mathbf F_2^N\) be a binary linear code with no zero coordinate, meaning that for every coordinate position \(u\) there exists a codeword \(c\in C\) with \(c_u=1\). Then there exists a basis \(\beta\) of \(C\) such that the coordinate-basis incidence graph

\[ G(C,\beta) \]

with left vertices the coordinates \(\{1,\dots,N\}\), right vertices the basis elements of \(\beta\), and edges \((u,b)\) whenever \(b_u=1\), is connected.

Consequently, for such a connected basis:

  • every coordinate has degree at least 1 in \(G(C,\beta)\),
  • every proper nonempty subset whose basis-vertex part is neither empty nor all of \(\beta\) has boundary at least 1.

So the finite gadget constant \(\beta_H\) from [[incidence-expansion-to-parity-tanner-expansion.md]] is automatically positive once one chooses a connected basis.

Dependencies

  • [[incidence-expansion-to-parity-tanner-expansion.md]]

Conflicts/Gaps

  • The lemma requires that the code have no zero coordinates. Positive distance alone does not imply this.
  • Connectedness only guarantees a positive boundary constant, not an optimized one. A stronger connected basis could still give a better expansion constant than the bare lower bound 1.
  • This node is a basis-existence statement for a constant-size local code. It does not by itself prove anything about the family-size dependence of the global Tanner graph.

Sources

  • 10.48550/arXiv.2202.13641