Skip to content

Left-Right Cayley LTC Comes From Local Agreement Plus Expansion

Claim/Theorem

Let

\[ X=\operatorname{Cay}^2(A,G,B) \]

be a left-right Cayley complex such that both \(\operatorname{Cay}(G,A)\) and \(\operatorname{Cay}(G,B)\) are \(\lambda\)-expanders and the noncollision condition of the paper holds. Let \(C_A\subseteq\{0,1\}^A\) and \(C_B\subseteq\{0,1\}^B\) be base codes of relative distances \(\delta_A,\delta_B>0\), and suppose the tensor code \(C_A\otimes C_B\) is \(\kappa_0\)-agreement testable. Define

\[ c=\frac{\kappa_0}{8+\kappa_0}\min(\delta_A,\delta_B). \]

If

\[ c>\lambda, \]

then the global square code

\[ C=C[G,A,B,C_A,C_B] \]

is \(\kappa\)-locally testable with \(|A||B|\) queries, where

\[ \kappa = \min\!\left\{ \frac{1}{4(1+|A|+|B|)}, \frac{c-\lambda}{2(|A|+|B|)} \right\}. \]

Equivalently, for every word \(f\) on squares,

\[ \Pr_g[f|_{X_g}\notin C_g]\ge \kappa\,\operatorname{dist}(f,C). \]

The proof is local-to-global:

  1. each vertex test checks membership in the local tensor code \(C_A\otimes C_B\);
  2. an iterative correction algorithm reduces local disagreement between neighboring views;
  3. expansion of both one-skeleton directions, together with the parallel-walk consistency argument, forces either global agreement with a nearby codeword or a constant fraction of violated local tests.

So the nearby classical code family in the left-right Cayley framework is not just an LTC in the abstract sense. It is an LTC produced by the stronger package: local tensor agreement testability plus two-direction expansion plus a local-to-global consistency mechanism.

Dependencies

  • None.

Conflicts/Gaps

  • The conclusion is still only global local testability. By [[good-ltc-does-not-imply-balanced-cut-rank.md]], that alone cannot force balanced-cut rank-connectivity.
  • The node therefore isolates a candidate extra ingredient for the frontier, but it does not yet convert that ingredient into trellis-width, branchwidth, or intrinsic cut-rank lower bounds.
  • Translating this left-right-Cayley local-to-global mechanism into the stabilizer-space quantity [[stabilizer-cut-rank-functional.md]] remains fully open.

Sources

  • 10.1145/3519935.3520024