4   Further Topics  In   p n  we can do much better   Theorem 4 1   Ellenberg Gijswijt  following Croot Lev Pach    Assuming that   A     3 n contains no non trivial 3 term arithmetic progressions  Then    A     o   2   7 5 6   n   Notation  Let M n be the set of monomials in x 1       x 2 whose degree in each variable is at most 2  Let V n be the vector space over   3 whose basis is M n  For any d     0   2 n    write M n d for the set of monomials in M n of  total  degree at most d  and V n d for the corresponding vector space  Set m d   dim   V n d       M n d     Lemma 4 2  Assuming that   A     3 n  P   V n d is a polynomial  P   a   a       0 for all a   a     A  Then          a   A   P   2 a     0       2 m d   2       Proof  Every  P   V n d can be written as a linear combination of monomials in  M n d  so      P   x   y       m   m     M n d deg   m m       d c m   m   m   x   m     y       for some coefficients c m   m    Clearly at least one of m   m   must have degree   d 2  whence      P   x   y       m   M n d   2 m   x   F m   y       m     M n d   2 m     y   G m     x         for some families of polynomials    F m   m   M n d   2     G m     m     M n d   2   Viewing   P   x   y     x   y   A as a   A       A   matrix C  we see that C can be written as the sum of at most  2 m d   2 matrices  each of which has rank 1  Thus  rank   C     2 m d   2  But by assumption  C is a diagonal matrix whose rank equals     a   A   P   a   a     0         Proposition 4 3  Assuming that   A     3 n a set containing no non trivial 3 term arithmetic progressions  Then     A     3 m 2 n   3   Proof  Let d     0   2 n   be an integer to be determined later  Let W be the space of polynomials in  V n d that vanish on    2   A   c  We have      dim   W     dim   V n d         2   A   c     m d     3 n     A           We claim that there exists P   W such that   supp   P       dim   W    Indeed  pick P   W with maximal support  If   supp   P       dim   W    then there would be a non zero polynomial Q   W vanishing on supp   P    in which case supp   P   Q     supp   P    contradicting the choice of P   Now by assumption         a   a     a   a     A     2   A           So any polynomial that vanishes on    2   A   c vanishes on   a   a     a   a     A    By Lemma 4 2 we now have that        A       3 n   m d     m d     3 n     A       dim   W       supp   P           x     3 n   P   x     0           a   A   P   2 a     0       2 m d   2     Hence     A     3 n   m d   2 m d   2  But the monomials in   M n   M n d are in bijection with the ones in  M 2 n   d via x 1   1   x n   n   x 1 2     1   x n 2     n  whence  3 n   m d   m 2 n   d  Thus setting d   4 n 3  we have     A     m 2 n   3   2 m 2 n   3   3 m 2 n   3     You will prove Theorem 4 1 on Example Sheet 3   We do not have at present a comparable bound for 4 term arithmetic progressions  Fourier techniques also fail   Example 4 4  Recall from Lemma 2 18 that given A   G              T 3     A     A     A       3     sup     1     A                 But it is impossible to bound                 T 4     A     A     A     A       4     x   d   A   x     A   x   d     A   x   2 d     A   x   3 d       4     by   sup     1     A            Indeed  consider Q     x     p n   x   x   0    By Problem 11 ii  on Sheet 1         Q   p n   1 p   O   p   n   2       and         sup t   0     Q     t       O   p   n   2         But given a 3 term arithmetic progression x   x   d   x   2 d   Q  by the identity      x 2   3   x   d   2   3   x   2 d   2     x   3 d   2   0   x   d       x   3 d automatically lies in Q  so                T 4     A     A     A     A     T 3     A     A     A       1 p   3   O   p   n   2       which is not close to   1 p   4   Definition 4 5   U 2 norm    Given f   G      define its U 2 norm  by  the formula        f   U 2   G   4     x   a   b   G f   x   f   x   a   f   x   b     f   x   a   b         Problem 1 i  on Sheet 2 showed that     f   U 2   G       f     l 4   G      so this is indeed a norm   Problem 1 ii  asserted the following   Lemma 4 6  Assuming that   f 1   f 2   f 3   G      Then        T 3   f 1   f 2   f 3       min i     3     f i   U 2   G       j   i   f j   L     G         Note that      sup     G     f           4         G     f           4   sup     G     f           2       G     f           2     and thus by Parseval s identity         f   U 2   G   4     f     l     G     4     f     l     G     2   f   L 2   G   2       Hence        f     l     G         f     l 4   G         f   U 2   G       f     l     G     1 2   f   L 2   G   1 2       Moreover  if   f   f A A     A      then               T 3   f   f   f     T 3     A         A         A         T 3     A     A     A       3       We may therefore reformulate the first step in the proof of Meshulam s Theorem as follows  if p n   2     2  then by Lemma 4 6         3 2       p n     3       T 3   f A A   f A A   f A A         f A A   U 2     p n         It remains to show that if    f A A   U 2     p n   is non trivial  then there exists a subspace V     p n of bounded codimension on which A has increased density   Theorem 4 7   U 2 Inverse Theorem    Assuming that   f     p n        f   L       p n     1      1    f   U 2     p n        Then  there exists b     p n such that          x     p n f   x   e     x   b   p         2       In other words      f             2 for     x     e     x   b   p   and we say  f correlates with a linear phase function    Proof  We have seen that        f   U 2     p n   2     f     l       p n       f   L 2     p n       f     l       p n           so        2     f     l       p n       sup t     p n       x f   x   e     x   t   p             Definition 4 8   U 3 norm    Given f   G      define its U 3 norm  by       f   U 3   G   8         x   a   b   c f   x   f   x   a   f   x   b   f   x   c     f   x   a   b   f   x   b   c   f   x   a   c   f   x   a   b   c         x   h 1   h 2   h 3   G         0   1   3 C       f   x       h       where C g   x     g   x     and       denotes the number of ones in     It is easy to verify that    c   G     c f   U 2   G   4 where   c g   x     g   x   g   x   c       Definition 4 9   U 3 inner product    Given functions f     G     for       0   1   3  define their U 3 inner product  by          f           0   1   3   U 3   G       x   h 1   h 2   h 3   G         0   1   3 C       f     x       h         Observe that     f   f   f   f   f   f   f   f   U 3   G       f   U 3   G   8   Lemma 4 10   Gowers Cauchy Schwarz Inequality    Assuming that   f     G            0   1   3  Then            f           0   1   3   U 3   G             0   1   3   f     U 3   G         Setting f     f for       0   1   2     0   and f     1 otherwise  it follows that    f   U 2   G   4     f   U 3   G   4 hence    f   U 2   G       f   U 3   G     Proposition 4 11  Assuming that   f 1   f 2   f 3   f 4     5 n      Then      T 4   f 1   f 2   f 3   f 4     min i     4     f i   U 3   G     j   i   f j   L       5 n         Proof  We additionally assume f   f 1   f 2   f 3   f 4 to make the proof easier to follow  but the same ideas are used for the general case  We additionally assume   f   L       5 n     1  by rescaling  since the inequality is homogeneous   Reparametrising  we have     T 4   f   f   f   f       a   b   c   d     5 n f   3 a   2 b   c   f   2 a   b   d   f   a   c   2 d   f     b   2 c   3 d     T 4   f   f   f   f     8       a   b   c     d f   2 a   b   d   f   a   c   2 d   f     b   2 c   3 d     2   4       d   d     a   b f   2 a   b   d   f   2 a   b   d         c f   a   c   2 d   f   a   c   2 d       f     b   2 c   3 d   f     b   2 c   3 d         4       d   d     a   b     c f   a   c   2 d   f   a   c   2 d       f     b   2 c   3 d   f     b   2 c   3 d         2   2       c   c     d   d     a f   a   c   2 d   f   a   c     2 d     f   a   c   2 d       f   a   c     2 d       b f     b   2 c   3 d   f     b   2 c     3 d     f     b   2 c   3 d       f     b   2 c     3 d       2     c   c     d   d     a     b f     b   2 c   3 d   f     b   2 c     3 d     f     b   2 c   3 d       f     b   2 c     3 d       2     b   b     c   c     d   d   f     b   2 c   3 d   f     b     2 c   3 d     f     b   2 c     3 d     f     b     2 c     3 d   f     b   2 c   3 d       f     b     2 c   3 d     f     b   2 c     3 d     f     b     2 c     3 d             Theorem 4 12   Szemeredi s Theorem for 4 APs    Assuming that   A     5 n a set containing no non trivial 4 term arithmetic progressions  Then    A     o   5 n     Idea   By Proposition 4 11 with   f   f A     A                   T 4     A   f A         A   f A         A   f A         A   f A           4   T 4   f A   f A   f A   f A           where   consists of 1 4 other terms in which between one and three of the inputs are equal to  f A   These are controlled by        f A   U 2     5 n       f A   U 3   G         whence              T 4     A     A     A     A       4     1 5   f A   U 3   G         So if A contains no non trivial 4 term arithmetic progressions and 5 n   2     3  then     f A   U 3   G       4 3 0   What can we say about functions with large U 3 norm   Example 4 13  Let M be an n   n symmetric matrix with entries in   5  Then f   x     e   x   M x   5   satisfies    f   U 3   G     1   Theorem 4 14   U 3 inverse theorem    Assuming that   f     5 n        f   L       5 n     1    f   U 3   G       for some     0  Then  there exists a symmetric n   n matrix M with entries in   5 and b     5 n such that          x f   x   e     x   M x   b   x     p       c           where c       is a polynomial in    In other words      f           c       for     x     e     x   M x   b   x     p   and we say  f correlates with a quadratic phase function    Proof  sketch    Let   h f   x   denote f   x   f   x   h         f   U 3   G         h     h f   U 2 4   1 8   STEP 1    Weak linearity  See reference   STEP 2    Strong linearity  We will spend the rest of the lecture discussing this in detail   STEP 3    Symmetry argument  Problem 8 on Sheet 3   STEP 4    Integration step  Problem 9 on Sheet 3   STEP 1  If    f   U 3   G   8     h     h   U 2 4     8  then for at least a   8 2 proportion of h     5 n     8 2       h f   U 2 4       h f     l   2  So for each such h     5 n  there exists t h such that      h f     t h     2     8 2   Proposition 4 15  Assuming that   f     5 n        f       1    f   U 3   G            5 n           1    Then  there exists S     5 n with   S               5 n     and a function      S     5 n   such that   i      h f         h               1      ii  There are at least           5 n   3   quadruples   s 1   s 2   s 3   s 4     S 4 such that s 1   s 2   s 3   s 4 and     s 1         s 2         s 4     STEP 2  If S and   are as above  then there is a linear function        5 n     5 n   which coincides with   for many elements of S   Proposition 4 16  Assuming that   S and   given as in Proposition 4 15  Then  there exists n   n matrix M with entries in   5 and b     5 n such that     x     M x   b         5 n     5 n    satisfies     x         x   for           5 n     elements x   S   Proof  Consider the graph of             h       h       h   S       5 n     5 n    By Proposition 4 15    has           5 n   3   additive quadruples   By Balog Szemeredi Gowers  Schoen  there exists         with                                     5 n     and                 O                udefine S     S by           h       h       h   S     and note   S                 5 n       By Freiman Ruzsa applied to          5 n     5 n    there exists a subspace  H     5 n     5 n   with   H     O                 O         5 n     such that       H   Denote by        5 n     5 n       5 n the projection onto the first n coordinates  By construction      H     S    Moreover  since   S                 5 n            ker       H         H     Im       H       O         5 n       S       O     1         We may thus partition H into O     1   cosets of some subspace H   such that     H is injective on each coset  By averaging  there exists a coset x   H   such that                x   H                                     5 n           Set               x   H      and define S   accordingly   Now     x     is injective and surjective onto V     Im       x   H      This means there is an affine linear map      V     5 n   such that   h       h           for all h   S       Then do steps 3 and 4     What to do if you have lots of additive quadruples   Balog Szemeredi Gowers   What to do if you have small doubling constant   Freiman Ruzsa  or Polynomial Freiman Ruzsa