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

We show that for infinitely many primes p, there exist dual functions of order k over Fnp that cannot be approximated in L∞-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∞-approximations of dual functions over N (a.k.a. multiple correlation sequences) by nilsequences.

• View at Publisher

Free Full Text ( Final Version , 321kb )

See Also
techReport High-entropy dual functions over finite fields and locally decodable codes J. Briët (Jop) and F.S. Labib (Farrokh)
inProceedings High-entropy dual functions over finite fields and locally decodable codes J. Briët (Jop) and F.S. Labib (Farrokh)
onlineVideo High-entropy dual functions over finite fields and locally decodable codes J. Briët (Jop) and F.S. Labib (Farrokh)
onlineVideo Dual functions not approximable by higher-order characters J. Briët (Jop)