Smooth LTC Has Cayley Spectral And Metric Characterizations¶

Claim/Theorem¶

Let \(C\) be an \(\mathbb F_2\)-linear code of blocklength \(n\), dimension \(k\), and distance \(d\).

Then the following are equivalent:

\[ \mathcal G=\operatorname{Cay}(\mathbb F_2^h,\mathcal D) \]

and a set \(S=\{b_1,\dots,b_n\}\) of linear maps \(b_i:\mathbb F_2^h\to\mathbb F_2\) such that

\[ h=n-k, \]

\(S\) is \(d\)-wise linearly independent,

\[ \lambda(b_i)\ge 1-2\varepsilon \qquad \text{for all }i, \]

and

\[ \lambda(b)\le 1-2\delta\,\operatorname{rk}_S(b) \qquad \text{for every linear map }b:\mathbb F_2^h\to\mathbb F_2, \]

where \(\operatorname{rk}_S(b)\) is the minimum size of a subset \(T\subseteq S\) with \(b=\sum_{i\in T} b_i\).

In the asymptotically good strong-soundness regime, this further specializes to the metric statement:

there is an asymptotically good smooth LTC with \(\varepsilon/\delta=O(1)\) if and only if there is a Cayley graph

\[ \mathcal G=\operatorname{Cay}(\mathbb F_2^h,S) \]

with

\[ |S|=(1+\Omega(1))h, \]

\(S\) \(\Omega(h)\)-wise linearly independent, and shortest-path metric embedding into \(\ell_1\) with distortion \(O(1)\).

So smooth LTC is exactly a Cayley-graph phenomenon with equivalent spectral and metric formulations.

This node gives an equivalence, not a stronger structural hypothesis than smooth LTC itself.
It therefore does not by itself identify the extra irreducibility needed for the balanced-cut connectivity frontier in Conjecture 3.
Combined with [[good-ltc-does-not-imply-balanced-cut-rank.md]], it shows that neither the Cayley, spectral, nor metric reformulation of LTC by itself can settle the current cut-rank problem.