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.

4678 reads
Subscribe

Comments

Post new comment

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