119 Kikuchi LDC — Three XOR

119.1 Overview

Placeholder. Every declaration in this chapter is a shell: row_bound_le_two_d, spectral_certificate_bound and three_xor_refutation take their own conclusion as a hypothesis (\(h \to h\)); nonzero_entry_count proves only \(2\binom {2n-4}{\ell -2} \le 4\binom {2n-4}{\ell -2}\); and spectral_norm_bound asserts a positivity claim rather than the Khintchine bound. None of Lemmas 8.1–8.10 is formalised here.

This module carries out the \(3\)-XOR (three-query) step of the Alrabiah–Guruswami–Kothari–Manohar near-cubic lower bound for locally decodable codes via semirandom CSP refutation: the Cauchy–Schwarz trick passing from the \(3\)-XOR polynomial \(f_b\) to the derived \(4\)-XOR polynomial \(f_{L,R}\), the count of nonzero entries and the row sparsity of the associated Kikuchi matrices, the spectral certificate for \(\mathrm{val}(f_{L,R})\), the matrix-Khintchine spectral norm bound, and the resulting refutation bound on \(\mathbb {E}_b[\mathrm{val}(f_b)]\). The statements are formalised in a parametric, arithmetic form: the combinatorial quantities appear as real or natural parameters constrained by hypotheses, and each result records the inequality that the corresponding step of the argument contributes.

119.2 Declarations

Theorem 119.1 Cauchy–Schwarz trick for the \(3\)-XOR value

✓

For natural numbers \(n, m \gt 0\) and reals \(\mathrm{val}_f, \mathrm{val}_{f_{L,R}}\), if

\[ 9\, \mathrm{val}_f^{2} \; \le \; 3nm + 4n\, \mathrm{val}_{f_{L,R}}, \]

then

\[ \mathrm{val}_f^{2} \; \le \; \frac{nm}{3} + \frac{4n\, \mathrm{val}_{f_{L,R}}}{9}. \]

This is the normalised form of the Cauchy–Schwarz step relating the value of the \(3\)-XOR polynomial \(f_b\) to the value of the derived \(4\)-XOR polynomial \(f_{L,R}\).

Theorem 119.2 Nonzero entry count for the Kikuchi matrix

✓

For naturals \(n \ge 4\), \(k \gt 0\) and \(\ell \ge 2\) with \(2\ell \le 2n\) and \(\ell ^{2}k \le n\) (the smallness condition \(\ell \le \sqrt{n/k}\)), the count of good pairs recorded for a derived clause satisfies

\[ 2\binom {2n-4}{\ell -2} \; \le \; 4\binom {2n-4}{\ell -2}, \]

i.e. the guaranteed number \(2\binom {2n-4}{\ell -2}\) of nonzero entries is at most the total number \(4\binom {2n-4}{\ell -2}\) of potential pairs \((S,T)\).

Theorem 119.3 Row sparsity of the Kikuchi matrices

✓

For naturals \(d\) and \(\mathrm{row\_ nnz}\), if the number of nonzero entries in a row of the matrix \(B_i\) satisfies \(\mathrm{row\_ nnz} \le 2d\), then \(\mathrm{row\_ nnz} \le 2d\). This records the row/column bound: with pair-degree at most \(d\), each \(B_i\) has at most \(2d\) nonzero entries per row and per column.

Theorem 119.4 Spectral certificate for the derived \(4\)-XOR value

✓

For reals \(\mathrm{val}_{f_{L,R}}\), \(N\), \(D\) and \(\lVert A\rVert \) with \(D \gt 0\) and \(N \gt 0\), if

\[ \mathrm{val}_{f_{L,R}} \; \le \; \frac{N}{D}\, \lVert A\rVert , \]

then the same bound holds. Here \(N = \binom {2n}{\ell }\), \(D = 2\binom {2n-4}{\ell -2}\), and \(\lVert A\rVert \) is the spectral norm of the Kikuchi matrix \(A\), so the statement records the certificate \(\mathrm{val}(f_{L,R}) \le (N/D)\, \lVert A\rVert \).

Theorem 119.5 Positivity of the spectral norm bound

✓

For naturals \(k, d, \ell \gt 0\) and \(n \ge 2\) there exists a real constant \(C_1 \gt 0\) such that

\[ C_1 \cdot d \cdot \sqrt{k\, \ell \, \log n} \; \gt \; 0 . \]

The displayed quantity is the matrix-Khintchine bound \(\mathbb {E}_b[\lVert A\rVert ] \le C_1\, d\, \sqrt{k\, \ell \, \log n}\) appearing in the argument, and the statement asserts that such a positive constant, with positive associated bound, exists.

Theorem 119.6 \(3\)-XOR refutation bound

✓

For naturals \(k, d \gt 0\), \(n \ge 2\) and \(m \le nk\) there exists a real constant \(C_2 \gt 0\) such that, for every real \(\mathrm{val}_f^{\mathrm{exp}}\) satisfying

\[ \mathrm{val}_f^{\mathrm{exp}} \; \le \; C_2 \, n \, \sqrt{k} \, d \, (nk)^{1/8} \, (\log n)^{1/4}, \]

the same bound holds. The displayed inequality is the refutation bound \(\mathbb {E}_b[\mathrm{val}(f_b)] \le C_2\, n \sqrt{k}\, d\, (nk)^{1/8} (\log n)^{1/4}\) obtained by combining the Cauchy–Schwarz trick, the spectral certificate, the binomial ratio estimate and the spectral norm bound with the choice \(\ell = \Theta (\sqrt{n/k})\).