Why do power-type bounds arise?

a repository of mathematical know-how

Why do power-type bounds arise?

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]

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 e1|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:x,y\in A\}$ and the ''difference set'' of $A$ is defined to be the set $\{x-y: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.

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.

Why do power-type bounds arise?

Recent articles

Active forum topics

Recent comments