High-entropy dual functions over finite fields and locally decodable codes
arXiv:2010.14956 · doi:10.1017/fms.2021.1
Abstract
We show that for infinitely many primes , there exist dual functions of order over that cannot be approximated in -distance by polynomial phase functions of degree . This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on -approximations of dual functions over (a.k.a. multiple correlation sequences) by nilsequences.
arXiv comment13 pages; typos fixed, bibliography updated
References in corpus (5)
- Decompositions, approximate structure, transference, and the Hahn-Banach theorem
- The inverse conjecture for the Gowers norm over finite fields via the correspondence principle
- Some open problems on multiple ergodic averages
- Gaussian width bounds with applications to arithmetic progressions in random settings
- Multiple correlation sequences not approximable by nilsequences