Quick description
There are certain kinds of arguments that always lead to certain kinds of bounds. Therefore, if you are trying to prove a bound, you can often be sure that certain techniques will not be sufficient. This makes the search for techniques that do work more efficient. This article is closely related to the article about which techniques lead to which kinds of bounds.
Three examples and how they differ
Consider the following three problems. We write for the group of integers mod
and assume (for convenience of the discussion) that
is prime.
This is another illustration of a phenomenon discussed in the extremal combinatorics front page: that problems that are superficially very similar can have extremely different solutions. This makes it a good idea to have ways of guessing in advance what techniques are likely to be successful. One way is the topic of this article: deducing from a lower bound that certain techniques will be unable to give good results for the upper bound.
In order to see this, let us come up with some lower bounds. We are now trying to find sets with given properties. More precisely, we are trying to find sets that are as large as possible subject to certain constraints. A good meta-technique for tackling problems of this kind is to look at the Tricki articles on existence proofs and extremal combinatorics. If you follow this meta-technique, then one of the ideas you will be led to is the probabilistic method. Upon reading Example 2 in that article, you will be aware of the simple technique of choosing elements of randomly and independently with probability
, with
chosen in such a way that the expected number of structures you are trying to avoid is less than half the expected size of the set you will obtain.
Applying that technique to the three problems above, one can easily prove lower bounds of ,
, and
, respectively. Can we improve on these bounds?
As it happens, we can in all three cases. For Problem 1 we can take all elements of that lie between
and
to obtain a lower bound of about
; for Problem 2 we can use a very nice algebraic construction of Erdős (which we have come across because we know that sometimes algebraic techniques can do better than random ones, and it happens that this one is discussed in the Tricki page on algebraic methods) that improves the bound to
; and for Problem 3 there is a beautiful construction of Behrend that gives a bound of
. (An account of this construction can be found either in the article about how bounds of the form
can ever arise or in the page of off-the-shelf examples in additive combinatorics.)
The existence of a lower bound of this type for Problem 1 completely changes our attitude to the problem. Suddenly, it seems that the extremal examples are highly structured sets rather than ones that look random, so the appropriate techniques for the problem are likely to be direct and combinatorial. What is more, if we look at this particular example, we rapidly see that it only just works, in the sense that every number not in the set can be written as the sum of two numbers that are in the set. That observation leads to the following question: how small can be if
is a subset of
of size
? A theorem of Cauchy and Davenport (one of the more interesting mathematical collaborations, since their lives did not come close to overlapping) gives the answer
, which is attained when
is a set of the form
. (If
is even, we could take all even numbers and this would be false. It is for this kind of reason that we are taking
to be prime.) Therefore, a sum-free set
cannot have more than about
elements.
The precise details of the above proof are less important to this discussion than the fact that the existence of a linear lower bound (and in this case the particular nature of the set that achieves the bound) have a substantial effect on how we go about solving the problem: we look for a direct combinatorial argument and we hope to obtain an exact best possible result.
Now let us look at Problem 2. It seems hard to improve on the bound of , and after a moment's thought it becomes obvious why. If a subset
of
contains no non-trivial solutions to the equation
then all pairs
must have distinct sums, except that
is allowed to equal
. This means that if
has size
, then
must be at most
, which gives a bound of the form
.
This approach doesn't seem to work for Problem 3, so let us see if we can think of any other approaches. One way of trying to get some inspiration is to generalize Problem 2 by asking the following question: if is a subset of
, then how few quadruples
can there be in
such that
? This question is a good example of one that can be answered by the analytic method. We define a function
by setting
to be the number of pairs
such that
and
are elements of
and
. Then the number of quadruples in
with
is
. It is easy to see that
(since every pair
has a sum), so we find ourselves wanting to answer the following analytic question: if
are real numbers such that
, then how small can
be? An important special case of the Cauchy-Schwarz inequality tells us that the minimum occurs when the
are all equal, and then it is
. Thus, we know that there must be at least
quadruples
in
with
.
Provided that is reasonably dense, this lower bound can be approximately matched by an upper bound. This is a simple application of the probabilistic method: one simply chooses the elements of
randomly with a probability that gives the right sort of size for
.
Finally we come to the main point of these three examples. It turns out that Problem 3 is still wide open, but we do at least have a good understanding of why it is hard. And a large part of that understanding comes from the existence of the Behrend lower bound. It has been essentially the best known bound for a long time now, so there is some reason to think that it might be the correct bound. But there is no hope of proving such a bound using simple applications of inequalities such as Hölder's inequality or the Cauchy-Schwarz inequality because these inequalities always result in power-type bounds. [Can anyone give a precise justification for this assertion?] The best known upper bounds for Problem 3 are obtained by much more complicated arguments, but the existence of the Behrend bound shows that these arguments (or rather, the complicated aspects of them) are in some sense necessary. (There is another important distinction between Problems 2 and 3, which is that while both problems can be easily reformulated as problems about functions, we have a positivity that allows the reformulation of Problem 2 to work for functions with values in , while the reformulation of Problem 3 works only for functions with values in
. Details about this will be added later.)