What does additive structure mean?

Suppose we have a finite subset A of an abelian group, and I told you it was additively structured. There are lots of different things this vague term could mean:

  1. The set A+A=\{ a+a' : a,a'\in A\} is not much bigger than A.
  2. There are lots of quadruples (a,b,c,d)\in A such that a+b=c+d (the number of such quadruplets is called the additive energy, and I denote it by E(A)).
  3. The Fourier transform of the characteristic function of the set, \widehat{A}, is lumpy and takes on large values quite often.
  4. A behaves like an additive substructure, such as a subgroup or an arithmetic progression.
  5. A 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 \lvert A+A\rvert\leq \lvert A\rvert^2, or E(A)\leq \lvert A\rvert^3, 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 K then all the others are with some parameters depending only on K.

Let’s explain one of the easiest examples to give you a flavour: showing that 1. implies 2. Suppose we know that \lvert A+A\rvert= K\lvert A\rvert (we say that K is the doubling constant for A), then, and our task is to give a lower bound for E(A).

For any x\in A+A let r(x) denote the number of pairs (a,a')\in A\times A such that x=a+a'. It is easy to see that

\sum_{x\in A+A}r(x)=\lvert A\rvert^2,

and so by Cauchy-Schwarz we get that

\left(\sum_{x\in A+A}r(x)^2\right)\lvert A+A\rvert\geq \lvert A\rvert^4.

But by expanding out the sum on the left hand side, we see that it is exactly equal to E(A). Hence we get that

E(A)\geq K^{-1}\lvert A\rvert^3

and we are done. Notice that if K=1, which means that A+A=A then we get the best possible E(A)\geq \lvert A\rvert^3 and if K=\lvert A\rvert then we get the trivial E(A)\geq \lvert A\rvert^2. 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 K then 2. is true with parameter K^{-1}. In general, we can’t hope for equivalences this strong, and for some any kind of polynomial dependence on K is impossible. We will return to showing other kinds of equivalences in future posts.

This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s