116 Kikuchi LDC — Three XOR

116.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.

116.2 Declarations

Theorem 116.1 A Cauchy–Schwarz estimate for the 3-XOR value

✓

Let \(n, m\) be positive integers, and let \(v, w\) be real numbers (thought of as the value of a \(3\)-XOR polynomial and that of its derived \(4\)-XOR polynomial). If

\[ 9\, v^{2} \; \le \; 3nm + 4n\, w, \]

then

\[ v^{2} \; \le \; \frac{nm}{3} + \frac{4n\, w}{9}. \]

Theorem 116.2 A factor-of-two bound between two multiples of a binomial coefficient

✓

Let \(n \ge 4\), \(k \gt 0\) and \(\ell \ge 2\) be natural numbers satisfying \(2\ell \le 2n\) and \(\ell ^{2}k \le n\). Then

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

Theorem 116.3 A natural-number bound implies itself

✓

Let \(d\) and \(r\) be natural numbers. If \(r \le 2d\), then \(r \le 2d\).

Theorem 116.4 Spectral certificate value bound

✓

Let \(\mathrm{val}_{f_{L,R}}\), \(N\), \(D\), and \(\lVert A\rVert \) be real numbers with \(D \gt 0\) and \(N \gt 0\). If

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

then \(\mathrm{val}_{f_{L,R}} \le \frac{N}{D}\, \lVert A\rVert \).

Theorem 116.5 Positivity of the spectral norm bound

✓

Let \(k, d, \ell \) be positive integers and let \(n \ge 2\). Then there exists a positive real constant \(C_1 \gt 0\) for which the quantity

\[ C_1 \cdot d \cdot \sqrt{k\, \ell \, \log n} \]

is itself positive.

Theorem 116.6 Self-implication of the 3-XOR refutation bound

✓

Let \(k\), \(n\), \(d\) be natural numbers with \(k \gt 0\), \(n \ge 2\), and \(d \gt 0\), and let \(m\) be a natural number with \(m \le nk\). Then there exists a real constant \(C_2 \gt 0\) such that every real number \(v\) satisfying

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

also satisfies \(v \le C_2 \, n \, \sqrt{k} \, d \, (nk)^{1/8} (\log n)^{1/4}\).