Computer Science/Discrete Mathematics Seminar I

I will be describing recent joint efforts with Tim Gowers to decompose a bounded function into a sum of polynomially structured phases and a uniform error, based on the recent inverse theorem for the U^k norms on F_p^n by Bergelson, Tao and Ziegler. The main innovation is the idea of defining the rank of a cubic or higher- degree polynomial (or a locally defined quadratic phase) analytically via the corresponding exponential sum, which turns out to imply all the properties of rank needed in proofs. As an application we prove a conjecture regarding the complexity of a system of linear forms that we made in 2007: A system of linear forms L_1, ... , L_m on F_p^n is controlled by the U^{k+1} norm if and only if k is the least integer such that the functions L_i^{k+1} are linearly independent.