Why the lower bound for 3-query LCC’s doesn’t extend to LDC’s.
We aren’t using anything about the form of \(\phi\) other than small dual Gowers uniformity…
An interpretation of the AP differences \(y\): it fails to be an LDC if you can’t arbitrarily specify the (relative) density of AP’s in those directions.
A MVC is linear on \(\F_p\), not \(\Z/m\). The coefficients and evaluations are in \(\F_p\) even though the vectors aren’t. (Could we do better with codes on \(\Z/m\)?) A linear code on \(\F_p\) can be converted to a code on \(\F_2\) but it loses linearity.
However, a MVC is NOT captured by the “query at an AP formalism.” Although the codeword index space is \(\F_p^N\), we’re not using that group structure for querying. Rather, we’re using the group structure of \(\F_p^{\times N}\). So it could still be possible to prove a lower bound querying AP’s.
That is false, it IS captured. The group can be different! There is a group, and there is a field. Two different things!
Q4.14 in “APs and LDCs”: When \(N\) grows large, there doesn’t even exist a degree 1 polynomial for which this holds. This doesn’t seem promising; the only interesting case is for \(n\) constant or small.
Variations on the poly method:
How to use it for small finite fields? (In Kakeya, \(p\to \iy\).)
How about considering polynomials with multiple outputs, ex. \(\F_p^n\to \F_p^{n-2}\) to capture vanishing on a plane?
To study: Guth’s course. Does the idea for the plane/regulus theorem help in thinking about \(\de\)-SG configurations and LDC’s?