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

@article{Brit2021HighentropyDF, title={High-entropy dual functions over finite fields and locally decodable codes}, author={Jop Bri{\"e}t and Farrokh Labib}, journal={Forum of Mathematics, Sigma}, year={2021}, volume={9} }

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 analogue of a problem of Frantzikinakis on $L_\infty $-approximations of dual functions over ${\mathbb{N}}$ (a.k.a. multiple correlation sequences) by nilsequences.

#### 2 Citations

High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)

- Computer Science
- ITCS
- 2021

Szemerédi’s theorem with random differences, in particular lower bounds on ρk, can be used to show the existence of LDCs, and the finite-field conjecture is motivated mainly by the possibility that so-called dual functions can be approximated well by polynomial phases. Expand

Multiple correlation sequences not approximable by nilsequences

- Mathematics
- Ergodic Theory and Dynamical Systems
- 2021

<jats:p>We show that there is a measure-preserving system <jats:inline-formula>
<jats:alternatives>
<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png"… Expand

#### References

SHOWING 1-10 OF 53 REFERENCES

The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic

- Mathematics
- 2011

We establish the inverse conjecture for the Gowers norm over finite fields, which asserts (roughly speaking) that if a bounded function $${f : V \rightarrow \mathbb{C}}$$ on a finite-dimensional… Expand

Good cyclic codes and the uncertainty principle

- Computer Science, Mathematics
- L’Enseignement Mathématique
- 2018

It is pointed out that even a weak version of the uncertainty principle for fields of positive characteristic would imply that good cyclic codes do exist and some heuristic arguments supporting that this is indeed the case are provided. Expand

Random Sequences and Pointwise Convergence of Multiple Ergodic Averages

- Mathematics
- 2010

We prove pointwise convergence, as $N\to \infty$, for the multiple ergodic averages $\frac{1}{N}\sum_{n=1}^N f(T^nx)\cdot g(S^{a_n}x)$, where $T$ and $S$ are commuting measure preserving… Expand

Locally decodable codes and the failure of cotype for projective tensor products

- Mathematics, Computer Science
- ArXiv
- 2012

It is shown that for every $p\in (1,\infty)$ there exists a Banach space $X$ of finite cotype such that the projective tensor product $l_p\hat\otimes X$ fails to have finite cotype. More generally,… Expand

Gaussian width bounds with applications to arithmetic progressions in random settings

- Mathematics, Computer Science
- International Mathematics Research Notices
- 2018

Upper bounds are proved on the Gaussian width of the image of the $n$-dimensional Boolean hypercube under a mapping $\psi:\mathbb{R}^n\to\mathbb(R)^k$, where each coordinate is a constant-degree multilinear polynomial with $0/1$ coefficients. Expand

On Szemerédi’s theorem with differences from a random set

- Mathematics
- 2019

We consider, over both the integers and finite fields, Szemeredi's theorem on $k$-term arithmetic progressions where the set $S$ of allowed common differences in those progressions is restricted and… Expand

Outlaw Distributions and Locally Decodable Codes

- Mathematics, Computer Science
- ITCS
- 2017

This work gives a new characterization of LDCs using distributions over Boolean functions whose expectation is hard to approximate (in~$L_\infty$~norm) with a small number of samples and coin the term `outlaw distributions' for such distributions since they `defy' the Law of Large Numbers. Expand

Multiple correlation sequences not approximable by nilsequences

- Mathematics
- Ergodic Theory and Dynamical Systems
- 2021

<jats:p>We show that there is a measure-preserving system <jats:inline-formula>
<jats:alternatives>
<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png"… Expand

The inverse conjecture for the Gowers norm over finite fields via the correspondence principle

- Mathematics
- 2010

The inverse conjecture for the Gowers norms U d .V/ for finite-dimensional vector spaces V over a finite field F asserts, roughly speaking, that a bounded function f has large Gowers normk fkU d.V/… Expand

On a problem of Arnold: The average multiplicative order of a given integer

- Mathematics
- 2011

For coprime integers g and n, let l(g) (n) denote the multiplicative order of g modulo n. Motivated by a conjecture of Arnold, we study the average of l(g) (n) as n <= x ranges over integers coprime… Expand