3   Probabilistic Tools  All probability spaces in this course will be finite   Theorem 3 1   Khintchine s inequality    Assuming that   p     2        X 1   X 2       X n independent random variables      X i   x i     1 2       X i     x i    Then          i   1 n X i   L p         O   p 1 2     i   1 n   X i   L 2       2   1 2         Proof  By nesting of norms  it suffices to prove the case p   2 k for some k      Write X     i   1 n X i  and assume   i   1 n   X i   L         2   1  Note that in fact   i   1 n   X i   L 2       2     i   1 n   X i   L         2  hence   i   1 n   X i   L 2       2   1   By Chernoff s inequality  Example 2 5    for all     0 we have            X           4 exp       2 4         and so using the fact that       X     t       0 t   X   s   d s we have       X   L 2 k       2 k     0   t 2 k   X   t   d t     0   2 k t 2 k   1       X     t   d t integration by parts     0   8 k t 2 k   1 exp     t 2 4   d t       I   K       We shall show by induction on k that I   K     2 2 k   2 k   k 4 k  Indeed  when k   1        0   t exp     t 2 4   d t       2 exp     t 2 4     0     2   2       For k   1  integrate by parts to find that     I   K       0   t 2 k   2   u   t exp     t 2 4     v d t     t 2 k   2       2 exp     t 2 4       0       0     2 k   2   t 2 k   3     2 exp     t 2 4     d t   4   k   1     0   t 2   k   1     1 exp     t 2 4   d t   4   k   1   I   K   1     4   k   1   2 2   k   1     2   k   1     k   1 4   k   1     2 2 k   2 k   k 4 k       Corollary 3 2   Rudin s Inequality    Let        2 n   be a linearly independent set and let p     2        Then for any  f     l 2                      f             L P     2 n     O   p   f     l 2               Corollary 3 3  Let        2 n   be a linearly independent set and let p     1   2    Then for all f   L p     2 n          f     l 2         O   p p   1   f   L p     2 n           Proof  Let f   L p     2 n   and write  g           f            Then       f     l 2       2             f           2     f     g     l 2     2 n         f   g   L 2     2 n   by Plancherel s identity     which is bounded above by   f   L p     2 n     g   L p       2 n   where 1 p   1 p     1  using H lder s inequality   By Rudin s Inequality         g   L p       2 n     O   p     g     l 2           O   p p   1   f     l 2                 Recall that given A     2 n of density     0  we had     Spec       A         2     1  This is best possible as the example of a subspace shows  However  in this case the large spectrum is highly structured   Theorem 3 4   Special case of Chang s Theorem    Assuming that   A     2 n of density     0      0  Then  there exists  H     2 n   of dimension O       2 log     1   such that   H   Spec       A     Proof  Let       Spec       A   be a maximal linearly independent set  Let   H     Spec       A      Clearly dim   H            By Corollary 3 3  for all p     1   2                       2                     A           2       A     l 2       2   O   p p   1     A   L p     2 n   2         so              O       2     2   2   p p p   1         Set p   1     log     1     1 to get         O       2     2     2   e 2     log     1   1         Definition 3 5   Dissociated    Let G be a finite abelian group  We say S   G is dissociated  if   s   S   s s   0 for         1   0   1     S    then     0   Clearly  if G     2 n  then S   G is dissociated if and only if it is linearly independent   Theorem 3 6   Chang s Theorem    Assuming that   G a finite abelian group  A   G be of density     0       Spec       A   is dissociated  Then          O       2 log     1   We may bootstrap Khintchine s inequality to obtain the following   Theorem 3 7   Marcinkiewicz Zygmund    Assuming that   p     2         X 1   X 2       X n     p       independent random variables      i   1 n X i   0  Then          i   1 n X i   L p         O   p 1 2     i   1 n   X i   2   L p   2       1 2         Proof  First assume the distribution of the X i s is symmetric  i e      X i   a         X i     a   for all a      Partition the probability space   into sets   1     2         M  write   j for the induced measure on   j such that all X i s are symmetric and take at most 2 values  By Khintchine s inequality  for each j     M            i   1 n X i   L p     j   p   O   p p   2     i   1 n   X i   L 2     j   2   p   2     O   p p   2     i   1 n   X i   2   L p   2     j   p   2       so summing over all j and taking p th roots gives the symmetric case  Now suppose the X i s are arbitrary  and let Y 1       Y n be such that Y i   X i and X 1   X 2       X n   Y 1   Y 2       Y n are all independent  Applying the symmetric case to X i   Y i          i   1 n   X i   Y i     L p             O   p 1 2     i   1 n   X i   Y i   2   L p   2           1 2     O   p 1 2     i   1 n   X i   Y i   2   L p   2       1 2       But then         i   1 n X i   L p             i   1 n X i     Y   i   1 n Y i     0   L p       p     X     X i     Y   Y i   p     X     Y     X i   Y i     p     X   Y       X i   Y i     p by Jensen say         X i   Y i     L p           p     concluding the proof     Theorem 3 8   Croot Sisask almost periodicity    Assuming that   G a finite abelian group      0  p     2        A   B   G are such that   A   B     K   A    f   G      Then  there exists b   B and a set X   B   b such that   X     2   1 K   O       2 p     B   and          x f     A   f     A   L p   G         f   L p   G     x   X       where   x g   y     g   y   x   for all y   G  and as a reminder     A is the characteristic measure of A   Proof  The main idea is to approximate      f     A   y       x f   y   x     A   x       x   A f   y   x       by 1 m   i   1 m f   y   z i    where z i are sampled independently and uniformly from A  and m is to be chosen later   For each y   G  define  Z i   y         z i f   y     f     A   y    For each y   G  these are independent random variables with mean 0  so by Marcinkiewicz Zygmund          i   1 m Z i   y     L p       p   O   p p   2     i   1 m   Z i   y     2   L p   2       p   2     O   p p   2     z 1       z m     A m     i   1 m   Z i   y     2   p   2       By H lder with 1 p     2 p   1  we get         i   1 m   Z i   y     2   p   2       i   1 m 1 p     1 p     p 2     i   1 m   Z i   y     2   p   2   2 p   p 2       i   1 m 1 p     p 2   1     i   1 m   Z i   y     2   p   2   2 p   p 2   m p   2   1   i   1 m   Z i   y     p     so          i   1 m Z i   y     L p       p   O   p p   2 m p   2   1     z 1       z m     A m   i   1 m   Z i   y     p         Summing over all y   G  we have        y   G     i   1 m Z i   y     L p       p   O   p p   2 m p   2   1     z 1       z m     A m   i   1 m   y   G   Z i   y     p       with         y   G   Z i   y     p   1 p     Z i   L p   G           z i f   f     A   L p   G             z i f   L p   G       f     A   L p   G       f   L p   G       f   L q   G       A   L 1   G     2   f   L p   G       by Young   H lder     f   g   L r   G       f   L p   G     g   L q   G   where 1   1 r   1 p   1 q    So we have          z 1       z m     A m   y   G     i   1 m Z i   y     p   O   p p   2 m p   2   1   i   1 m   2   f   L p   G     p     O     4 p   p   2 m p   2   f   L p   G   p         Choose m   O       2 p   so that the RHS is at most     4   f   L p   G     p  whence          z 1       z m     A m   y   G   1 m   i   1 m     z i f   y     f     A   y     p             O     4 p   p   2 m p   2   f   L p   G   p         4   f   L p   G     p       Write      L     z     z 1       z m     A m               2   f   L p   G     p         By Markov inequality  since                    4   f   L p   G     p   2   p     2   f   L p   G     p       we have        A m   L     A m                     2   f   L p   G     p                 2 p             2   p     so   L       1   1 2 p     A   m   1 2   A   m  Let     D       b   b       b     m   b   B         Now   L   D     A   B   m  whence        L   D       A   B   m   K m   A   m   2 K m   L         By Lemma 1 17       E   L   D       L   2   D   2   L   D     1 2 K   m   D   2   L       so there are at least   D   2 2 K m pairs   d 1   d 2     D   D such that  r L   L   d 2   d 1     0  In particular  there exists b   u b and X   B   b of size   X       D   2 K m     B   2 K m such that for all x   X  there exists l 2   x     L such that for all i     m    l 1   x   i   l 2   x   i   x  But then for each x   X  by the triangle inequality            x f     A   f     A   L p   G           x f     A       x   1 m   i   1 m     l 2   x   i f     L p   G           x   1 m   i   1 m     l 2   x i   f     f     A   L p   G       f     A   1 m   i   1 m     l 2   x   i f   L p   G       1 m   i   1 m     x   l 2   x   i f   f     A   L p   G     2     2   f   L p   G       by definion of L     Theorem 3 9   Bogolyubov again  after Sanders    Assuming that   A     p n of density     0  Then  there exists a subspace V     p n of codimension O   log 4     1   such tht   V   A   A   A   A   Almost periodicity is also a key ingredient in recent work of Kelley and Meka  showing that any A     N   containing no non trivial 3 term arithmetic progressions has size   A     exp     C log 1 1 1 N   N