What can a lower bound say about potential proofs of the upper bound?

a repository of mathematical know-how

What can a lower bound say about potential proofs of the upper bound?

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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?|which techniques lead to which kinds of bounds.]]

=== Three examples and how they differ ===

Consider the following three problems. We write $\mathbb{Z}_n$ for the group of integers mod $n$ and assume (for convenience of the discussion) that $n$ is prime.

[problem sumfree] How large can a subset of $\mathbb{Z}_n$ be if it contains no three elements $x$, $y$ and $z$ with $x+y=z$? [/problem]

[problem sidon] How large can a subset of $\mathbb{Z}_n$ be if it contains no four distinct elements $x$, $y$, $z$ and $w$ with $x+y=z+w$? [/problem]

[problem roth] How large can a subset of $\mathbb{Z}_n$ be if it contains no three distinct elements $x$, $y$ and $z$ with $x+y=2z$? [/problem]

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 front page|extremal combinatorics]]. If you follow this meta-technique, then one of the ideas you will be led to is [[Applying the probabilistic method|the probabilistic method]]. Upon reading Example 2 in that article, you will be aware of the simple technique of choosing elements of $\mathbb{Z}_n$ randomly and independently with probability $p$, with $p$ 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 $cn^{2/3}$, $cn^{1/3}$, and $cn^{2/3}$, 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 $\mathbb{Z}_n$ that lie between $n/3$ and $2n/3$ to obtain a lower bound of about $n/3$; for Problem 2 we can use a very nice algebraic construction of Erd\H{o}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 $cn^{1/2}$; and for Problem 3 there is a beautiful construction of Behrend that gives a bound of $n\exp(-c\sqrt{\log n})$. (An account of this construction can be found either in the article about [[How does a bound of exp(c(log n)^{1/2}) ever arise?|how bounds of the form $\exp(c\sqrt{\log n})$ can ever arise]] or in the page of [[important examples in additive combinatorics|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 $A+A$ be if $A$ is a subset of $\mathbb{Z}_n$ of size $m$? 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 $2m-1$, which is attained when $A$ is a set of the form $\{a,a+d,\dots,a+(m-1)d\}$. (If $n$ is even, we could take all even numbers and this would be false. It is for this kind of reason that we are taking $n$ to be prime.) Therefore, a sum-free set $A$ cannot have more than about $n/3$ 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 $cn^{1/2}$, and after a moment's thought it becomes obvious why. If a subset $A$ of $\mathbb{Z}_n$ contains no non-trivial solutions to the equation $x+y=z+w$ then all pairs $(x,y)$ must have distinct sums, except that $x+y$ is allowed to equal $y+x$. This means that if $A$ has size $m$, then $\binom m2$ must be at most $n$, which gives a bound of the form $Cn^{1/2}$.

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 $A$ is a subset of $\mathbb{Z}_n$, then how few quadruples $(x,y,z,w)$ can there be in $A$ such that $x+y=z+w$? This question is a good example of one that can be answered by [[Turn sets into functions|the analytic method]]. We define a function $f:\mathbb{Z}_n\rightarrow\mathbb{R}$ by setting $f(u)$ to be the number of pairs $(x,y)$ such that $x$ and $y$ are elements of $A$ and $x+y=u$. Then the number of quadruples in $A$ with $x+y=z+w$ is $\sum_u f(u)^2$. It is easy to see that $\sum_uf(u)=|A|^2$ (since every pair $(x,y)$ has a sum), so we find ourselves wanting to answer the following analytic question: if $a_1,\dots,a_n$ are real numbers such that $\sum_{i=1}^na_i=t$, then how small can $\sum_{i=1}^na_i^2$ be? [[The second-moment method|An important special case of the Cauchy-Schwarz inequality]] tells us that the minimum occurs when the $a_i$ are all equal, and then it is $t^2/n$. Thus, we know that there must be at least $|A|^4/n$ quadruples $(x,y,z,w)$ in $A$ with $x+y=z+w$.

Provided that $A$ is reasonably dense, this lower bound can be approximately matched by an upper bound. This is a simple application of [[Applying the probabilistic method|the probabilistic method]]: one simply chooses the elements of $A$ randomly with a probability that gives the right sort of size for $A$.

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\"older'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 $[-1,1]$, while the reformulation of Problem 3 works only for functions with values in $[0,1]$. Details about this will be added later.)

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

What can a lower bound say about potential proofs of the upper bound?

Recent articles

Active forum topics

Recent comments