The Taub Faculty of Computer Science Events and Talks

The Gowers uniformity norms U_k measure a certain kind of psuedo randomness. For example, a function f on a finite (large) dimensional vector space V over a finite field F has small U_2 norm if and only if all its Fourier coefficients are small - i.e it has no significant correlation with linear phase functions.

The content of the inverse conjecture for the Gowers norms is that a similar relation exists between the U_k norms and polynomials of degree smaller than k; namely a function f has small U_k norm if and only if it has no significant correlation with a polynomial phase function of degree smaller than k. This conjecture plays an important role in counting solutions to systems of linear equations in subsets of vector spaces, and in polynomiality testing.

I will describe a proof of this conjecture in the case where char(F) is greater equal k, using tools from ergodic theory. In the low characteristic case, we show that if f has small U_k norm then it has no significant correlation with a polynomial phase function of bounded degree c(k).

I will define all relevant notions. Joint works with V. Bergelson and T. Tao.