Suppose we have a finite subset of an abelian group, and I told you it was additively structured. There are lots of different things this vague term could mean:
- The set is not much bigger than .
- There are lots of quadruples such that (the number of such quadruplets is called the additive energy, and I denote it by ).
- The Fourier transform of the characteristic function of the set, , is lumpy and takes on large values quite often.
- behaves like an additive substructure, such as a subgroup or an arithmetic progression.
- contains lots of little structured bits, like arithmetic progressions or subgroups,
and more exotic things. One of the main themes of additive combinatorics, which could perhaps be taken as a definition of the area, is that these different definitions are all roughly equivalent to each other, and the most important theorems of the area can be roughly divided into two camps: those which provide such equivalences, and those which show that a given set is structured in one of the senses above.
The list above is still very vague. To make things more precise, we note that all of the different definitions are true in some trivial way. For example, we can trivially bound , or , and so on. In general, we can measure how much better we can do than these trivial bounds, which gives us some parameter which measures how structured our set is. By showing rough equivalence, I mean that if we know that one type of structure is true for some parameter then all the others are with some parameters depending only on .
Let’s explain one of the easiest examples to give you a flavour: showing that 1. implies 2. Suppose we know that (we say that is the doubling constant for ), then, and our task is to give a lower bound for .
For any let denote the number of pairs such that . It is easy to see that
and so by Cauchy-Schwarz we get that
But by expanding out the sum on the left hand side, we see that it is exactly equal to . Hence we get that
and we are done. Notice that if , which means that then we get the best possible and if then we get the trivial . We leave it as an exercise for the reader to interpret these facts.
Here we have an easy and powerful equivalence: if 1. is true with parameter then 2. is true with parameter . In general, we can’t hope for equivalences this strong, and for some any kind of polynomial dependence on is impossible. We will return to showing other kinds of equivalences in future posts.