Good Codes Have Some Linear Cut Rank¶
Claim/Theorem¶
Every good linear code has at least one coordinate partition with large rank-connectivity.
Let \(C\) be an [n,k,d] linear code. Then there exists a subset \(L\) of coordinates such that
\[
\lambda_C(L)
\;:=\;
\dim(C|_L)+\dim(C|_{L^c})-\dim(C)
\;\in\;
\Omega\!\left(\frac{k(d-1)}{n}\right).
\]
Equivalently, for any stabilizer space \(\mathcal S\) represented by a full-row-rank matrix \(H\) with kernel \(C=\ker H\), there exists a cut \(L\) with
\[
\chi_L(\mathcal S)\;\in\;\Omega\!\left(\frac{k(d-1)}{n}\right).
\]
Proof sketch:
- In a minimal tree realization on a path (a conventional trellis), the state dimension on an edge cutting the path into a prefix \(J\) and suffix \(J^c\) is
\[
\dim(C)-\dim(C_J)-\dim(C_{J^c}),
\]
by Kashyap's equation (5). 2. Since the cross-section dimensions satisfy
\[
\dim(C_J)=\dim(C)-\dim(C|_{J^c}),
\qquad
\dim(C_{J^c})=\dim(C)-\dim(C|_J),
\]
that edge-state dimension is exactly \(\lambda_C(J)\). 3. Kashyap records that the state max-complexity of any conventional trellis realization is at least
\[
\frac{k(d-1)}{n}.
\]
Therefore some cut \(J\) along the trellis satisfies \(\lambda_C(J)\ge k(d-1)/n\).
Hence any asymptotically good family has at least one partition with linear cut-rank.
Dependencies¶
- [[cross-cut-stabilizer-rank-rank-formula.md]]
Conflicts/Gaps¶
- This theorem only gives existence of some high-connectivity cut. It does not say that balanced cuts, separator-induced cuts, or hardware-relevant cuts have large rank-connectivity.
- Therefore it is still far weaker than what Conjecture 3 needs: a hardware-constrained lower bound requires a cut with both large intrinsic demand and small hardware capacity.
- The statement is compatible with the direct-sum obstruction in [[good-code-parameters-do-not-imply-cut-rank.md]], because the high-connectivity cut produced here need not be balanced.
Sources¶
10.48550/arXiv.0805.219910.48550/arXiv.0711.1383