Cayley LTC Characterization Is Insufficient For Balanced Cut Rank¶

Claim/Theorem¶

No hypothesis that is merely equivalent to smooth local testability can, by itself, force linear balanced-cut rank-connectivity.

More precisely, consider any proposed theorem whose assumptions are only properties equivalent, via [[smooth-ltc-cayley-characterization.md]], to smooth LTC, for example:

a large \(d\)-wise independent generator set in a low-dimensional Cayley graph together with constant-distortion \(\ell_1\) embedding, or
the spectral package

\[ \lambda(b_i)\ge 1-2\varepsilon, \qquad \lambda(b)\le 1-2\delta\,\operatorname{rk}_S(b). \]

If such a theorem implied that every asymptotically good family had

\[ \lambda_C(L)\in\Omega(n) \]

for every balanced cut \(L\), equivalently

\[ \chi_L(\mathcal S)\in\Omega(n), \]

then every asymptotically good LTC family would satisfy linear balanced-cut connectivity.

But [[good-ltc-does-not-imply-balanced-cut-rank.md]] gives asymptotically good LTC families with a balanced cut \(L\) such that

\[ \lambda_C(L)=0 \qquad\text{and}\qquad \chi_L(\mathcal S)=0. \]

Therefore any route to the Conjecture-3 frontier must use extra structure that is not captured by the Gopalan--Vadhan--Zhou equivalences alone.

Dependencies¶

[[smooth-ltc-cayley-characterization.md]]
[[good-ltc-does-not-imply-balanced-cut-rank.md]]
[[cross-cut-stabilizer-rank-rank-formula.md]]

Conflicts/Gaps¶

This is a negative metatheorem. It rules out a class of shortcut arguments, but it does not identify a sufficient positive hypothesis.
It still leaves open the possibility that a stricter subclass of LTCs, such as irreducible left-right Cayley-complex codes with additional expansion, does force balanced-cut rank-connectivity.
The obstruction is asymptotic and structural; it does not say anything about finite-size explicit instances.

Sources¶

10.1145/2554797.2554807
10.48550/arXiv.2202.13641