1   Combinatorial methods  Definition 1 1   Sumset    Let G be an abelian group  Given A   B   G  define the sumset  A   B to be      A   B       a   b   a   A   b   B       and the difference set  A   B to be      A   B       a   b   a   A   b   B         If A and B are finite  then certainly      max     A       B         A   B       A     B         Example 1 2  Let A     n         1   2       n        Then        A   A         2       2 n       2 n   1   2   A     1       Lemma 1 3  Assuming that   A     is finite   Then     A   A     2   A     1  with equality if and only if A is an arithmetic progression   Proof  Let A     a 1   a 2       a n   with a 1   a 2       a n  Then      a 1   a 1   a 1   a 2   a 1   a 2       a 1   a n   a 2   a n       a n   a n       so    A   A     2   A     1  But we could also have written      a 1   a 1   a 1   a 2   a 2   a 2   a 2   a 3   a 2   a 4       a 2   a n   a 3   a n       a n   a n       When    A   A     2   A     1  these two orderings must be the same  So a 2   a i   a 1   a i   1 for all i   2       n   1     Exercise   If A   B      then    A   B       A       B     1 with equality if and only if A and B are  arithmetic progressions with the same common difference   Example 1 4  Let A   B       p   with p prime  Then     A   B     p   1   A   B       p    Indeed    g   A   B   A     g   B        note that g   B means   g     B   But   g       p          A     g   B         A       g   B       A     g   B         A       B     p   1       Theorem 1 5   Cauchy Davenport    Assuming that   p is a prime  A   B       p   nonempty  Then        A   B     min   p     A       B     1         Proof  Assume   A       B     p   1  Without loss of generality assume that 1     A       B   and that 0   A  Apply induction on   A    The case   A     1  is trivial  Suppose   A     2  and let 0   a   A   Since   a   2 a   3 a         p   1   a   p a         p   and   A       B     p   1  there must exist m   0 such that m a   B but   m   1   a   B  Let B     B   m a  so 0   B    a   B      B         B     But 1     A   B         A    so the inductive hypothesis applies to A   B   and A   B    Since        A   B         A   B       A   B         we have        A   B       A   B           A   B         A   B           A   B         A   B       1     A       B     1         This fails for general abelian groups  or even general cyclic groups    Example 1 6  Let p be  fixed  small  prime  and let V     p n be a subspace  Then V   V   V  so   V   V       V    In fact  if A     p n is such that   A   A       A    then A must be a coset of a subspace    Example 1 7  Let A     p n be such that    A   A     3 2   A    Then there exists V     p n a subspace such that   V     3 2   A   and A is contained in a coset of V  See Example Sheet 1    Definition 1 8   Ruzsa distance    Given finite sets A   B   G  we define the Ruzsa distance  d   A   B   between A and B by     d   A   B     log   A   B     A     B       Note that this is symmetric  but is not necessarily non negative  so we cannot prove that it is a metric  It does  however  satisfy triangle inequality   Lemma 1 9   Ruzsa s triangle inequality    Assuming that   A   B   C   G finite  Then      d   A   C     d   A   B     d   B   C         Proof  Observe that        B       A   C       A   B       B   C         Indeed  writing each  d   A   C as d   a d   c d with a d   A  c d   C  the map         B     A   C       A   B       B   C     b   d       a d   b   b   c d       is injective  The triangle inequality now follows from the definition     Definition 1 10   Doubling   difference constant    Given a finite A   G  we write          A         A   A     A       for the doubling constant  of A and          A         A   A     A       for the difference constant  of A   Then Lemma 1 9 shows  for example  that      log     A     d   A   A     d   A     A     d     A   A     2 log     A         So       A         A   2  or    A   A       A   A   2   A     Notation  Given A   G and l   m     0  we write      l A   m A     A   A       A   l times   A   A       A   m times       Theorem 1 11   Plunnecke s Inequality    Assuming that   A   B   G are finite sets    A   B     K   A   for some K   1  Then    l   m     0        l B   m B     K l   m   A         Proof  Choose a non empty subset A     A such that the ratio    A     B     A     is minimised  and call this ratio K    Then    A     B     K     A      K     K  and   A     A     A     B     K     A       Claim   For every finite C   G     A     B   C     K     A     C     Let s complete the proof of the theorem assuming the claim  We first show that   m     0     A     m B     K   m   A      Indeed  the case m   0 is trivial  and m   1 is true by assumption  Suppose m   1 and the inequality holds for m   1  By the claim with C     m   1   B  we get        A     m B       A     B     m   1   B     K     A       m   1   B     K   m   A           But as in the proof of Ruzsa s triangle inequality    l   m     0  we can show        A       l B   m B       A     l B     A     m B     K   l   A     K   m   A       K   l   m   A     2       Hence    l B   m B     K   l   m   A       K   l   m   A    which completes the proof  assuming the claim    We now prove the claim by induction on   C    When   C     1 the statement follows from the assumptions  Suppose the claim is true for C  and consider C     C     x   for some x   C  Observe that      A     B   C       A     B   C         A     B   x       D   B   x         with   D     a   A     a   B   x   A     B   X     By definition of K       D   B     K     D    so       A     B   C         A     B   C       A     B   x       D   B   x     IH K     A     C     K     A       K     D     K       A     C       A         D         We apply this argument a second time  writing      A     C       A     C         A     x       E   x         where  E     a   A     a   x   A     C     D  We conclude that        A     C         A     C       A     x       E   x       A     C       A         D       so        A     B   C       K       A     C       A         D       K     A     C           proving the claim     We are now in a position to generalise Example 1 7   Theorem 1 12   Freiman Ruzsa    Assuming that   A     p n    A   A     K   A    i e       A     K   Then  A is contained in a subspace H     p n of size   H     K 2 p K 4   A     Proof  Choose  X   2 A   A maximal such that the translates  x   A with x   X are disjoint  Such a set X cannot be too large    x   X   x   A   3 A   A  so by Plunnecke s Inequality  since    3 A   A     K 4   A          X     A         x   X   x   A         3 A   A         So   X     K 4  We next show      2 A   A   X   A   A           Indeed  if  y   2 A   A and y   X  then by maximality of X   y   A   x   A     for some x   X  and if y   X  then clearly   y   X   A   A    It follows from      by induction that   l   2      l A   A     l   1   X   A   A            since      l A   A   A     l   1   A   A       l   2   X   A   A     l   2   X   2 A   A     X   A   A     l   1   X   A   A       Now let H     p n be the subgroup generated by A  which we can write as      H     l   1   l A   A             Y   A   A     where Y     p n is the subgroup generated by X   But every element of Y can be written as a sum of   X   elements of X with coefficients amongst 0   1       p   1  hence   Y     p   X     p K 4  To conclude  note that        U       Y     A   A     p K 4   p K 4 K 2   A         where we use Plunnecke s Inequality or even Ruzsa s triangle inequality     Example 1 13  Let A   V   R where V     p n is a subspace of dimension K   d   n   K and R consists of K   1 linearly independent vectors not in V   Then        A       V   R       V       R     p n   k   K   1   p n   k     V       and        A   A         V   R       V   R         V     V   R       R   R       K   V         But any subspace K     p n containing A must have size at least p n   K     K   1       V     p K  so the exponential dependence on K is necessary    Theorem 1 14   Polynomial Freiman Ruzsa  due to Gowers Green Manners Tao 2024    Assuming that   A     p n    A   A     K   A    Then  there exists a subspace K     p n of size at most C 1   K     A   such that for some x     p n        A     x   K         A   C 2   K         where C 1   K   and C 2   K   are polynomial in K   Proof  Omitted  because the techniques are not relevant to other parts of the course  See Entropy Methods in Combinatorics next term     Definition 1 15  Given A   B   G we define the additive energy  between A and B to be      E   A   B           a   a     b   b       A   A   B   B   a   b   a     b             We refer to the quadruples   a   a     b   b     such that a   b   a     b   as additive quadruples   Example 1 16  Let V     p n be a subspace  Then   E   V     E   V   V       V   3   On the other hand  if A       p   is chosen at random from     p    each element chosen independently with probability     0   then with high probability      E   A     E   A   A       4 p 3       A   3       Lemma 1 17  Assuming that   A   B   G  both non empty  Then      E   A   B       A   2   B   2   A   B         Proof  Define r A   B   x           a   b     A   B   a   b   x      and notice that this is the same as    A     x   B       Observe that     E   A   B           a   a     b   b       A 2   B 2   a   b   a     b         x   G r A   B   x   2     x   A   B r A   B   x   2       x   A   B r A   B   x     2   A   B   by Cauchy Schwarz     but              x   G   A     x   B         x   G   y   G   A   y     x   B   y       x   G   y   G   A   y     B   x   y       A     B        As usual     A here means the indicator function      In particular  if    A   A     K   A    then      E   A     E   A   A       A   4   A   A       A   3 K       The converse is not  true   Example 1 18  Let G be your favourite  class of  abelian group s   Then there exist constants         0 such that for all sufficiently large n  there exists A   G  with   A     n satisfying  E   A         A   3 and    A   A         A   2   Theorem 1 19   Balog Szemeredi Gowers  Schoen    Assuming that   A   G is finite  E   A         A   3 for some     0  Then  there exists A     A of size at least c 1         A   such that    A     A         A     c 2        where c 1       and c 2       are polynomial in     Idea   Find A     A such that   a   b   A   such that a   b has many representations as   a 1   a 2       a 3   a 4   with a i   A   We first prove a technical lemma  using a technique called  dependent random choice    Definition 1 20   gamma popular differences    Given A   G and     0  let     P       x   G     A     x   A           A         be the set of   popular  differences  of A   Lemma 1 21  Assuming that   A   G is finite  E   A         A   3  c   0  Then  there is a subset X   A of size   X         A     3 such that for all but a   1 6 c   proportion of pairs   a   b     X 2   a   b   P c     Proof  Let  U     x   G     A     x   A       1 2     A      Then       x   U   A     x   A     2   1 2     A     x   A     x   A       1 2     A   3   1 2 E   A       For 0   i     log 2     1    let     Q i     x   G     A   2 i   1     A     x   A         A   2 i         and set   i       1 2   2 i  Then          i   i   Q i       i   Q i     2 2 i   1     A   2   i   A   2 2 2 i   Q i     1     A   2   i   A   2 2 2 i   x   U       A   2 i   1     A     x   A         A   2 i     1     A   2   x   U   A     x   A     2   1     A   2   1 2 E   A       x   U   A     x   A     2   1 2 E   A       1 2   A             Let  S       a   b     A 2   a   b   P c      Then       i     a   b     S     A   a       A   b     Q i         a   b     S     A   a       A   b           A     a   b   A       c     A     by definition of S     S     c     A     c     A   3   2 c     A   2   1 2   A           2 c     A   2   i   i   Q i       Hence there exists i 0 such that          a   b     S     A   a       A   b     Q i 0     2 c     A   2   i 0   Q i 0         Let Q   Q i 0        i 0      2   i 0  So         a   b     S     A   a       A   b     Q     2 c       A   2   Q              Find x such that  X     A     A   x     is large   Given x   G  let X   x     A     x   A    Then        x   Q   X   x       1   Q     x   Q   A     x   A       1 2     A         Let  T   x         a   b     X   x   2   a   b   P c      Then       X   Q   T   x         x   Q       a   b       A     x   x   A   a   A   b   A     2   a   b   P c         1   Q     x   Q       a   b     S   x   A   a   A   b       1   Q       a   b     S     A   a       A   b     Q     1   Q   2 c     A   2     Q     2 c       A   2   2 c   2   A   2     Therefore        x   Q   X   x     2     1 6 c     1   T   x       C S     x   Q   X   x       2     1 6 c     1   x   Q   T   x           2   2   A   2     1 6 c     1 2 c   2   A   2       2 4     2 8     A   2     2 8   A       So there exists x   Q such that   X   x     2     2 8   A   2  in which case we have        X       8   A       3   A       and   T   x       1 6 c   X   2     Proof of Theorem  1 19     Given A   G with  E   A         A   3  apply Lemma 1 21 with c   2   7 to otain X   A of size   X       3   A   such that for all but 1 8 of pairs   a   b     X 2   a   b   P     2 7  In particular  the bipartite graph      G     X     X       x   y     X   X   x   y   P     2 7         has at least 7 8   X   2 edges  Let A       x   X   deg   x     3 4   X       Clearly    A         X   8  For any a   b   A    there are at least   X   2 elements y   X such that   a   y       b   y     E   G     a   y   b   y   P     2 7    Thus a   b     a   y       b   y   has at least        6   A     choices for y     2 7   A       2 7   A       3 2 1 7   A   3     representations of the form a 1   a 2     a 3   a 4   with a i   A   It follows that       3 2 1 7   A   3   A     A         A   4     A     A       2 1 7     3   A     2 2 2     4   A         Thus   A     A       2 4 4     8   A