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

a repository of mathematical know-how

How does a bound of exp(c(log n)^{1/2}) ever 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]

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).<comment thread="47" /> 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|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 $f:(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})$.

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.

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

Recent articles

Active forum topics

Recent comments