a repository of mathematical know-how

Why do power-type bounds arise?

Quick description

This article examines the nature of proofs that give rise to bounds of power type.


These vary from example to example. A familiarity with basic concepts from combinatorics would help.

Example 1: The sizes of sumsets and difference sets

Let A be a finite set of integers. The sumset of A is defined to be the set x,y\in A\} and the difference set of A is defined to be the set x,y\in A\}. Suppose that you know that |A+A|\leq C|A|. What does that imply about the size of A-A?

It turns out, and this is not obvious at all, that |A-A| must be at most C^2|A|, but we shall be concerned with proving a bound in the opposite direction. We shall show that |A-A| can be as large as C^{\log 6/\log 5}|A|. This example is intended to illustrate how a certain kind of proof can give rise to a bound with a strange power like \log (7/3)/\log 2.

The proof is simple. Let A be the set \{0,1,3\}. Then A-A=\{-3,-2,-1,0,1,2,3\}, which has size 7=(7/3)|A|, while |A+A|=\{0,1,2,3,4,6\}, which has size 6=2|A|. This answers the question for one value of C, but we are more interested in a bound for a general C. To obtain this we take a sort of "Cartesian product" (or "tensor product") of our example. One way of doing this is to look at the set A all m-digit numbers (including numbers that start with some zeros) where all the digits are 0, 1 or 3. If we write our numbers in base 10 but allow negative digits (so for instance 2(-3)3 stands for the number more conventionally denoted by 173) then we find that A+A consists of all numbers with digits 0,1,2,3,4 or 6, while A-A consists of all numbers with digits -3,-2,-1,0,1,2 or 3. So |A|=3^m, |A+A|=6^m and |A-A|=7^m. Therefore, we can take C=2^m and |A-A|=C^{\log(7/3)/\log 2)}|A|.

See also the article on the tensor power trick for some arguments of a closely related type.

General discussion

As this example illustrates, strange powers can arise when one "raises an example to a power". The power arising from the bound is just the power that you get from the initial example, which is typically a ratio of logarithms.


Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)