Tricki

## 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 be a finite set of integers. The sumset of is defined to be the set and the difference set of is defined to be the set . Suppose that you know that . What does that imply about the size of ?

It turns out, and this is not obvious at all, that must be at most , but we shall be concerned with proving a bound in the opposite direction. We shall show that can be as large as This example is intended to illustrate how a certain kind of proof can give rise to a bound with a strange power like .

The proof is simple. Let be the set . Then which has size , while which has size . This answers the question for one value of , but we are more interested in a bound for a general . 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 all -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 consists of all numbers with digits or 6, while consists of all numbers with digits or 3. So , and . Therefore, we can take and .

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.