111 Kikuchi LDC — Background Facts

111.1 Overview

This file collects the external background facts used by the Alrabiah–Guruswami–Kothari–Manohar near-cubic lower bound for \(3\)-query locally decodable codes: the reduction of an arbitrary \((q,\delta ,\varepsilon )\)-LDC to normal form (Fact 3.6), the rectangular matrix Khintchine inequality (Fact 4.1), and two-sided bounds on the binomial coefficient ratio \(\binom {n-2q}{\ell -q}/\binom {n}{\ell }\) (Fact 4.2). The first two are recorded in an existential form that fixes the shape of the parameters they supply; the binomial ratio bounds are proved in full.

111.2 Declarations

Theorem 111.1 Existence of normal-form reduction parameters

✓

Let \(q \ge 2\) be an integer, let \(k\) and \(n\) be positive integers, and let \(\delta , \varepsilon \gt 0\). Then there exist a natural number \(n' \le 6n\) and real numbers \(\delta ', \varepsilon ' \gt 0\) such that

\[ \delta ' \ \ge \ \frac{\varepsilon \, \delta }{3\, q^{2}\, 2^{\, q-1}}, \qquad \varepsilon ' \ \ge \ \frac{\varepsilon }{2^{\, 2q}}. \]

Theorem 111.2 A positive constant below the matrix Khintchine bound

✓

Let \(k\) be a positive integer, let \(\sigma ^2 \gt 0\) be a real number, and let \(d_1\) and \(d_2\) be positive integers. Then there exists a positive real number \(C_{\mathrm{MK}} \gt 0\) satisfying

\[ C_{\mathrm{MK}} \ \le \ \sqrt{\, 2\, \sigma ^2 \log (d_1 + d_2)\, }. \]

Definition 111.3 Real-valued binomial coefficient

✓

For naturals \(n\) and \(k\), \(\texttt{chooseR}\, n\, k\) is the binomial coefficient \(\binom {n}{k}\) cast into \(\mathbb {R}\).

Theorem 111.4 Binomial ratio bound, upper

✓

Let \(n, \ell , q\) be natural numbers with \(n \gt 0\), \(q \gt 0\), \(q \le \ell \), \(2\ell \le n\), and \(2q \le n\). Then the ratio of real-valued binomial coefficients satisfies

\[ \frac{\binom {n-2q}{\ell -q}}{\binom {n}{\ell }} \ \le e^{3q}\left(\frac{\ell }{n}\right)^{q}. \]

Theorem 111.5 Lower bound for a ratio of binomial coefficients

✓

Let \(n\), \(\ell \), and \(q\) be natural numbers with \(n \ge 1\) and \(q \ge 1\), and suppose that \(q \le \ell \), \(2\ell \le n\), and \(2q \le n\). Then

\[ e^{-3q}\left(\frac{\ell }{n}\right)^{q} \ \le \frac{\binom {n-2q}{\ell -q}}{\binom {n}{\ell }}, \]

where the binomial coefficients are evaluated in \(\mathbb {R}\).