LTC Sparse Cut Forces Product Decomposition

Claim/Theorem

Let \(C\) be a \((\gamma,\varepsilon)\)-LTC of relative distance \(\Delta\), and let \(G=(V,E)\) be its associated constraint graph with average degree

\[ d=\frac{|E|}{|V|}. \]

Suppose a cut \((S_1,S_2)\) satisfies

\[ \alpha:=\frac{|S_1|}{|V|}\ge 3\gamma \]

and

\[ E(S_1,S_2)<\tau d\alpha\,|S_1| \qquad \text{for some }\tau\le \varepsilon. \]

Then the code approximately factors across that cut:

\[ C\approx_\gamma C_{S_1}\times C_{S_2}. \]

More precisely, there exist codes \(C'_i\subseteq C_{S_i}\) such that

1. \(C'_i\approx_\gamma C_{S_i}\),
2. \(C'_i\) is a \((2\gamma/\alpha,\varepsilon-\tau)\)-LTC,
3. the relative distance of \(C'_i\) is at least

\[ \frac{\Delta-\gamma}{\alpha}, \]

and in particular

\[ C\approx_{2\gamma} C'_1\times C'_2. \]

Interpretation: a sparse tester cut is impossible unless the code itself is close to a Cartesian product across that same cut.

Dependencies

• None.

Conflicts/Gaps

• This is an approximate decomposition theorem for a chosen tester or constraint graph, not an intrinsic statement about the matroid-connectivity quantity from [[cross-cut-stabilizer-rank-rank-formula.md]].
• The conclusion is approximate product structure, not exact vanishing of balanced cut rank.
• To use this against Conjecture 3, one still needs a bridge from sparse tester cuts or approximate factorization to the stabilizer-space lower-bound functional [[stabilizer-cut-rank-functional.md]].

Sources

• dinurLocallyTestableCodes