High-entropy dual functions over finite fields and locally decodable codes

Abstract

We show that for infinitely many primes $p$, there exist dual functions of order $k$ over ${\mathbb{F}}_p^n$ that cannot be approximated in $L_{\infty }$-distance by polynomial phase functions of degree $k-1$. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on $L_{\infty }$-approximations of dual functions over $\mathbb{N}$ (a.k.a. multiple correlation sequences) by nilsequences.

13 pages; typos fixed, bibliography updated

References in corpus (2)

• Gaussian width bounds with applications to arithmetic progressions in random settings
• Multiple correlation sequences not approximable by nilsequences