Skip to content

Good LTC Does Not Imply Balanced Cut Rank

Claim/Theorem

Even asymptotically good locally testable codes do not, by themselves, force linear balanced-cut rank-connectivity.

Let \(A_N\) and \(B_N\) be two families of linear codes of equal blocklength \(N\) such that each family is:

  • asymptotically good, and
  • locally testable with constant query complexity and constant soundness.

Form the direct-sum family

\[ C_n \;=\; A_N \oplus B_N \]

on disjoint coordinate sets, with total length \(n=2N\).

Then:

  1. \(C_n\) remains asymptotically good, because
\[ k(C_n)=k(A_N)+k(B_N)=\Theta(n), \qquad d(C_n)=\min(d(A_N),d(B_N))=\Theta(n). \]
  1. \(C_n\) remains locally testable with constant query complexity and constant soundness: choose one component uniformly at random and run its local tester on that component. The rejection probability is the average of the two component rejection probabilities, hence still lower-bounds distance to \(C_n\) up to a constant factor.
  2. For the balanced partition \(L\) consisting of the coordinates of the first summand, [[cross-cut-stabilizer-rank-rank-formula.md]] gives
\[ \lambda_{C_n}(L)=0. \]

Equivalently, for the associated stabilizer space,

\[ \chi_L(\mathcal S_n)=0. \]

Therefore local testability does not fix the balanced-cut connectivity problem left open by [[good-code-parameters-do-not-imply-cut-rank.md]]. Any successful route from local testability to Conjecture 3 must use more than LTC soundness alone, for example some irreducibility, connectedness, or expansion property that rules out direct-sum style decompositions.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[good-code-parameters-do-not-imply-cut-rank.md]]
  • [[quantum-tanner-constituent-ltc.md]]

Conflicts/Gaps

  • This is again a disconnected counterexample. It does not rule out the possibility that a connected expander-style LTC family must have large balanced-cut rank-connectivity.
  • The node shows that local testability alone is insufficient, but it does not identify the extra hypothesis that would make the implication true.
  • The example concerns classical codes. Translating any eventual positive theorem back to the quantum stabilizer-space frontier will still require additional work.

Sources

  • 10.48550/arXiv.2202.13641