How does a bound of exp(c(log n)^{1/2}) ever arise?

Quick description

If you have not seen a proof that yields a bound of the form $\exp(c\sqrt{\log n})$ for some (possibly negative) constant $c$ then it may seem surprising that this function often arises naturally. This article explains why and gives an example. More examples would greatly improve the article.

General discussion

The answer to why such a bound ever occurs is simple, and similar answers apply to many functions. It often happens that one has an idea for how to obtain a bound, but the proof depends on a parameter, such as the size of some set, or dimension of some space, that is needed in the proof. It is not obvious in advance what value of this parameter will best suit your purposes, so you keep it as a variable, $t$ , say. Then at the end of the proof, you find that the quantity $m$ that you are trying to maximize can be at least as big as $\max_t\{f(n,t),g(n,t)\}$ , where $f$ increases with $t$ , $g$ decreases with $t$ , and $n$ is the main parameter that specifies the size of the problem. The resulting bound $m=m(n)$ can easily be quite a bit more exotic than the functions $f$ and $n$ that are used to define it. For example, to obtain the bound $m=\exp(c\sqrt{\log n})$ one can take $f(n,t)=e^t$ and $g(n,t)=n^{1/t}$ . Taking logs, one sees that these two are equal when $t=t^{-1}\log n$ , so $t=\sqrt{\log n}$ , so $m=\exp(\sqrt{\log n})$ .

In a moment we shall see an example of a proof where a bound of this kind arises, but note that we can already guess something important about it. Almost certainly it will involve a construction where one has to balance two things that can go wrong, and one chooses a certain parameter optimally at the end. And we can guess all this before we even know what the statement is that will be proved! Such is the power of metamathematics.

Actually, that was an exaggeration. It is possible to conceive of other ways in which a bound of $\exp(c\sqrt{\log n})$ might arise. For example, suppose that $n$ counted the number of points in some vector space $V$ over $\mathbb{F}$ and $m$ counted the number of points in a subspace $W$ . If the optimal dimension of $W$ was the square root of the dimension of $V$ , then $m$ would be $2^{\sqrt{\log_2n}}=\exp(\sqrt{\log 2\log n})$ . That is, another feature of the function $\exp(\sqrt{\log n})$ that makes it reasonably natural is that it is a conjugation of one very natural function by another: on a logarithmic scale one is simply taking square roots. For this reason one often thinks of this function as being "half way" between bounded functions and polynomials (because $\sqrt{x}$ is "half way" between constant functions and linear functions).^♦ Having said that, it is still not completely obvious why one would ever want to take the square root of a dimension: the answer in some cases turns out to be that one is still optimizing a parameter as above.

Example 1: Behrend's set

Behrend's set is an example of a surprisingly dense subset of $[n]=\{0,1,2,\dots,n-1\}$ that does not contain any arithmetic progression of length 3. Here is a sketch of how it is constructed.

Observe first that the surface of a sphere in $\mathbb{R}^d$ contains no arithmetic progression of length 3, if by "arithmetic progression" we mean a set of the form $\{v,v+w,v+2w\}$ with $w\ne 0$ .
Next, consider the grid $[m]^d$ (that is, the set of all points $(x_1,\dots,x_d)$ such that each $x_i$ is an integer between $0$ and $m-1$ ). The number of possible values of $x_1^2+\dots+x_d^2$ is at most $m^2d$ , since this number is always an integer between 0 and $m^2d-1$ .
Therefore, by the pigeonhole principle, there must be some $t$ such that $x_1^2+\dots+x_d^2=t$ for at least $m^d/m^2d$ points $(x_1,\dots,x_d)$ in the grid $[m^d]$ .
By the first observation, the set $S_t$ of all such points does not contain an arithmetic progression of length 3.
Consider the map $(x_1,\dots,x_d)\mapsto\sum_{i=1}^dx_i(2m)^{i-1}$ . (This map thinks of a sequence in $[m]^d$ as the digits of a number in base $2m$ , written backwards.) This map takes values in the set $[(2m)^d]$ . It is easy to check that if $f(x)$ , $f(y)$ and $f(z)$ form an arithmetic progression of length 3 in $[(2m)^d]$ , then $x$ , $y$ and $z$ form one in $[m]^d$ .
It follows that $f(S_t)$ contains no arithmetic progression of length 3.

From this argument we see that we can obtain a subset of $[n]$ of size $m^d/m^2d$ with no progression of length 3, provided that $(2m)^d$ is at most $n$ . Thus, we are faced with a simple optimization problem: maximize $m^d/m^2d$ subject to the constraint that $(2m)^d$ is at most $n$ . To solve this, we reduce the number of variables by one by taking $(2m)^d$ to be equal to $n$ . (There is a small problem here, which is that both $m$ and $d$ have to be integers. But that is easy to deal with and doesn't affect the answer by very much.) That is, we shall take $m$ to be $n^{1/d}/2$ . Then $m^d=n/2^d$ , so we are trying to maximize $4n/2^dn^{2/d}d$ . Equivalently, we would like to minimize $2^dn^{2/d}d$ . Taking logs, we find that we would like to minimize $d\log 2+2\log n/d+\log d$ . Since $\log d$ is much smaller than $d$ , and since the sum of two positive real numbers is comparable to the maximum of those two numbers, this minimum occurs roughly when $d\log 2$ and $2\log n/d$ are equal, which tells us that $d=c\sqrt{\log n}$ for some constant $c$ . (This general trick is explored further in the article To optimize a sum try making the terms roughly equal in size.) And then $n^{1/d}$ is $\exp(\log n/d)$ , which is of the form $\exp(c\sqrt{\log n})$ . And feeding that back in we find that $m^d/m^2d$ is of the form $n\exp(-c\sqrt{\log n})$ . (Here the constant $c$ changes from line to line but is always positive.)

General discussion

Note that in the above example we had to balance two considerations. On the one hand, the fact that we have to use base $2m$ representations of integers rather than base $m$ representations costs us a factor of $2^d$ , and on the other hand the fact that we have to pass from the grid $[m]^d$ to a $(d-1)$ -dimensional subset of the grid costs us a factor of $m^2$ (which we couldn't expect to improve to anything better than $m$ ), which equals $n^{2/d}$ . So we are in almost exactly the situation described at the beginning of the article.

Another remark that makes the function $\exp(c\sqrt{\log n})$ slightly less mysterious is that it is in a sense the most natural function that is bigger than any power of $\log n$ and smaller than any power of $n$ . To see that, ask yourself the following question: what is the most natural function that is bigger than $\log n$ and smaller than any linear function in $n$ ? Surely the answer is $\sqrt n$ . This suggests that the most natural function to lie between $\log\log n$ and any function of the form $c\log n$ is $\sqrt{\log n}$ . And then, exponentiating, we conclude that the most natural function to lie between $\log n$ and any power of $n$ is $\exp(\sqrt{\log n})$ .

Comments

Inline comments

The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.

Minor correction

Thu, 09/04/2009 - 06:19 — Josh (not verified)

I believe it should say: $\exp(\sqrt{\log n})$ is thought of as being "half-way" between *exponential* functions and polynomials, in a similar manner to how $\sqrt{x}$ is though of as being "half-way" between *constants* and polynomials.

In the first case, I believe it was just a typo. In the second case, "bounded function" could be a bit misleading. For example, I don't think many people would consider $\sqrt{x}$ as "half-way" between $e^{-x}$ and $x$ , even if they would consider it "half-way" between a constant function and $x$ .

Thanks – I've changed "bounded" to "constant".

Whoops

Thu, 09/04/2009 - 06:24 — Josh (not verified)

In the first half of my last comment I was thinking of $\exp(\sqrt{n})$ , which can be though of as "half-way" between polynomial $=\exp(c\log n)$ and exponentials like $\exp(cn)$ .

Factoring

Thu, 09/04/2009 - 06:28 — Anonymous (not verified)

Similar functions, such as $\exp(\sqrt{n \log n})$ (which can also be though of as "half-way" between polynomial and exponential) arise as the running times of various algorithms for factoring integers.

Post new comment

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