Tricki
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.

Prerequisites

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.