Dual Distance Gives Generator Puncture Rank

Claim/Theorem

Let \(G\) be a full-row-rank binary matrix whose row space is a linear code \(L\subseteq \mathbf F_2^m\). Let

\[ d_\perp := d(L^\perp). \]

Then for every coordinate subset \(U\subseteq [m]\) with

\[ |U|<d_\perp, \]

the restricted column set of \(G\) on \(U\) is linearly independent:

\[ \operatorname{rank}(G_U)=|U|. \]

Equivalently, any linear dependence among columns of a generator matrix for \(L\) must involve at least \(d(L^\perp)\) coordinates.

Proof sketch:

1. If the columns of \(G_U\) were dependent, there would exist a nonzero vector \(y\in \mathbf F_2^{U}\) such that

\[ G_U y^\top = 0. \]

1. Extending \(y\) by zeros outside \(U\) gives a nonzero vector \(\tilde y\in \mathbf F_2^m\) with

\[ G \tilde y^\top = 0, \]

so \(\tilde y\in L^\perp\). 3. But

\[ 0<|\tilde y| \le |U| < d(L^\perp), \]

contradicting the definition of the dual distance.

Quantum-Tanner corollary for the chosen local-generator presentation:

• for parity 0, the local row space is

\[ L_0=C_A\otimes C_B, \]

whose dual is the dual tensor code

\[ L_0^\perp=C_A^\perp\otimes \mathbf F_2^B + \mathbf F_2^A\otimes C_B^\perp, \]

with distance

\[ d(L_0^\perp)=\min\{d(C_A^\perp),d(C_B^\perp)\}; \]

• for parity 1, the local row space is

\[ L_1=C_A^\perp\otimes C_B^\perp, \]

with

\[ d(L_1^\perp)=\min\{d(C_A),d(C_B)\}. \]

Under the Theorem 17 hypotheses of [[quantum-tanner-theorem17-parity-expander.md]], all four distances are at least \(\delta\Delta\), so every local generator block in the chosen presentation has full column rank on any local coordinate subset of size strictly less than \(\delta\Delta\).

This gives a new exact local-rank tool on the explicit-family route: although the global intrinsic rank problem remains open, each root neighborhood already behaves like a full-rank local measurement block up to O(\Delta) punctures.

Dependencies

• [[quantum-tanner-theorem17-parity-expander.md]]

Conflicts/Gaps

• This is only a local block statement. A global balanced cut may intersect many root neighborhoods in far more than \delta\Delta coordinates, so the theorem does not by itself imply linear global cut rank.
• The result is about the chosen local-generator presentation. It does not automatically transfer to arbitrary stabilizer bases of the same code.
• The current open step is now more concrete on the explicit-family side: globalize these exact local rank contributions across many roots without losing too much to overlaps between neighborhoods.

Sources

• 10.48550/arXiv.2202.13641