Seminar: April 20

Uniformity and Testing Correlations in $F_p^n$

The $k$-th Gowers uniformity norm of a function can be described by the average that is defined through a $k$-dimensional cube shaped linear structure. I will show that roughly speaking when $p$ is a sufficiently large prime, in the group $F_p^n$, every notion of uniformity that can be described by the averages defined through linear structures is equivalent to one of the Gowers' notions of uniformity.

It is possible to interpret this result from the perspective of property testing. For bounded functions it is possible to empirically estimate Gowers norms and more generally every average that is defined through the linear structures by reading the value of the function at a few random sample points. On the other hand it is known that a bounded function has large Gowers uniformity norm if and only if it correlates with certain structured functions. These two facts show that having correlation with certain structured functions is testable. Our result implies that roughly speaking the only correlation testable families of functions are the ones that can be tested by Gowers uniformity norms. This talk is based on a joint work with Shachar Lovett.