26

It is somewhat miraculous to me that even very complicated sequences $a_n$ which arise in various areas of mathematics have the property that there exists an elementary function $f(n)$ such that $a_n = \Theta(f(n))$ or, even better, $a_n \sim f(n)$. Examples include

  • Stirling's approximation $n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$ (and its various implications),
  • The asymptotics of the partition function $p_n \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$,
  • The prime number theorem $\pi(n) \sim \frac{n}{\log n}$,
  • The asymptotics of the off-diagonal Ramsey numbers $R(3, n) = \Theta \left( \frac{n^2}{\log n} \right)$.

What are examples of sequences $a_n$ which occur "in nature" and which provably don't have this property (either the weak or strong version)? Simpler examples preferred.

(I guess I should mention that I am not interested in sequences which don't have this property for computability reasons, e.g. the busy beaver function. I am more interested in, for example, natural examples of sequences with "half-exponential" asymptotic growth.)

Qiaochu Yuan
  • 114,941
  • 4
    Let us not forget that something like $\pi(x) \sim \mathrm{Li}(x)$ is a much more accurate statement than $\pi(x) \sim x/\log x$ (as the error term is smaller), where $\mathrm{Li}(x) = \int_{2}^{x}{\frac{dt}{\log t}}$. Now $\mathrm{Li}(x)$ isn't an elementary function, but it is asymptotically equivalent to $x/\log x$ (via integration by parts), so it is worth noting that often a complicated sequence may be more naturally asymptotic to a sum or integral involving elementary functions, and then one can in turn show that such a sum or integral is also asymptotic to some elementary function. – Peter Humphries Nov 08 '10 at 10:25
  • 4
    The inverse Ackermann function arises as such an $f$ in various counting problems in Combinatorics. It seems likely to me that it cannot be expressed using elementary functions, though I can't seem to find a reference for this. – Mark Nov 08 '10 at 10:51

8 Answers8

19

Since this is community wiki, I won't feel that bad about not offering any crisp answers, but more of an abstract point of view which might suggest another avenue of pursuit.

To me the basic subject matter goes by the name "Hardy fields": fields of germs of real-valued functions at infinity. One of the basic examples is the field of germs of all functions that can be built up from polynomials, exponentials, and logarithms, and closed under the four arithmetic operations and composition.

A wonderful fact is the trichotomy law: that such "log-exp functions" are either eventually positive, eventually zero, or eventually negative. This is perhaps along the lines of the monotonicity assumptions Qiaochu mentioned above. It guarantees that the germs at infinity of such functions do indeed form a field $K$. Sitting inside the field is a valuation ring consisting of germs of bounded functions, $O$. There is a corresponding valuation on $K$ whose value group is $K^\ast/O^\ast$.

The elements of $K^\ast/O^\ast$ may be called "rates of growth". Indeed, two germs of functions $[f]$, $[g]$ are equivalent mod $O^\ast$ iff both $f/g$ and $g/f$ are bounded, which is to say they are asymptotic (up to a constant) -- remember that by trichotomy, these bounded functions do not oscillate but tend to a definite limit.

From this point of view, we are interested in naturally arising Hardy fields whose value groups strictly contain the value group of the log-exp class mentioned above (so that we get "intermediate rates of growth").

The reason I mention all this is that I think there is a pretty big literature on constructions of Hardy fields (which unfortunately I am not very familiar with). One area of research is via model theory and particularly o-minimal structures, where o-minimality guarantees the trichotomy law above. There are experts out there (for example, David Marker, if he's listening) who may be able to give us "natural" examples of o-minimal structures with such intermediate rates of growth at infinity. I'd be interested in this myself.

Edit: And now that I've written this, I have a memory that there are theorems in o-minimal structure theory which tend to rule out such intermediate rates of growth! That in itself would be interesting, and anyhow maybe someone like David Marker would know some interesting examples anyway, whether from o-minimal structure theory or not.

Todd Trimble
  • 52,336
  • "o-minimality guarantees the trichotomy law above": I know almost nothing about o-minimal structures, but I'd be interested to learn. Could you say in a few words what the definition of "o-minimality" is? – André Henriques Jul 18 '11 at 20:42
  • 1
    @Andr'e: it's short for "order-minimal". Let $T$ be a first-order theory that includes a predicate $\lt$ satisfying the axioms for a linear order. Let $R$ be a model of $T$. For example, $T$ might be the theory of ordered fields, and $R$ might be the real numbers. Call a subset of some $R^n$ "definable" if it can be defined by an $n$-ary predicate expressed in the language of $T$. Then $R$ is o-minimal if every definable subset of $R$ is a finite union of points and (possibly half-infinite) intervals. This condition has surprisingly strong consequences for the structure of definable sets! – Todd Trimble Jul 18 '11 at 22:09
  • A very readable book (for those who aren't model theorists), which goes into the remarkable consequences of o-minimality, is the book by Lou van den Dries, Tame Topology and O-Minimal Structures. For example, it is shown that if the real numbers $R$ are o-minimal with respect to some theory, such as the theory of ordered exponential fields, then every definable subset of $R^n$ possesses a nice tame (Whitney) stratification into finitely many smooth pieces, of the type one expects from the theory of real algebraic varieties and real semi-algebraic varieties. – Todd Trimble Jul 18 '11 at 22:20
11

Several arithmetical functions don't have an equivalent in terms of an elementary function, but only have an equivalent "in the mean". For instance $d(n)$, the number of divisors of $n$, is quite irregular, but satisfies $$\frac1n(d(1)+\cdots+d(n))\sim\log n.$$ Likewise, the sum $\sigma(n)$ of divisors of $n$ is irregular (though a little less than $d(n)$) but satisfies $$\frac1n(\sigma(1)+\cdots+\sigma(n))\sim\frac{\pi^2n}{12}.$$ Finally, the average order of the Euler indicator $\phi(n)$ is $\frac{3n}{\pi^2}$.

Denis Serre
  • 51,599
  • 2
    Good point. Perhaps I should impose some monotonicity hypotheses... – Qiaochu Yuan Nov 08 '10 at 13:58
  • 1
    In a similar vein, one can consider things like the number of equivalent classes of positive definite binary quadratic forms of discriminant $d$. Another example would be $\tau(n)$, the Fourier coefficients of the Ramanujan $\Delta$ function; if you prefer positive numbers, then take $|\tau(n)|^2$. Perhaps the best example is simply the characteristic function of the primes. We tend to think of these sequences as "random" so they don't have asymptotics with elementary functions. – Matt Young Nov 08 '10 at 23:00
  • 4
    What unifies $\tau$ and the examples I gave is that they are multiplicative functions: if $n\wedge m=1$, then $f(nm)=f(n)f(m)$. Such functions are unlikely to have an asymptotics, unless each restriction $f_p$ of $f$ to ${1,p,p^2,p^3,\ldots}$ have the same asymptotics. – Denis Serre Nov 09 '10 at 06:39
8

Davenport–Schinzel sequences are related to complexity of arrangements of various geometric shapes (e.g. envelopes of line segments). Their asymptotics is described in terms of the inverse Ackermann function.

Boris Bukh
  • 7,746
  • 1
  • 34
  • 71
6

The Bell numbers, have asymptotics related to the Lambert W function.

EDIT: I was poking around on mathworld today, and found that the Gram Points also have W function related asymptotics.

graveolensa
  • 975
  • 2
    Is it known whether the asymptotic behavior of the W function can be described using elementary functions? – Qiaochu Yuan Nov 08 '10 at 12:12
  • It definitely may be described using elementary functions with any prescribed accuracy. (And in general, I would call inverses of elementary functions also "expressible by elementary functions"). – Fedor Petrov Nov 08 '10 at 12:18
  • @Qiaochu Yuan: Yes, it can, as Fedor wrote. But is not helpful at all in many cases, as the usual series expansion for the W function converges very slowly. – zhoraster Nov 08 '10 at 12:49
  • 8
    W(x) is asymptotic to log(x/log x), which is elementary. So W is in the same boat as Li(x), already mentioned. – Gerald Edgar Nov 12 '10 at 21:33
5

Consider Cantor staircase function $f:\ [0,1]\rightarrow [0,1]$ and the moment function $F(x):=\int_0^1 (f(t))^x dt$. When $x$ tends to $+\infty$, it behaves like $x^{-\sigma}$, $\sigma:=\ln 3/\ln 2$. But the limit $F(x)\cdot x^{\sigma}$ does not exist: this value oscillates very slowly around a constant $1.9967\dots$

See more in Russian here: http://www.math.spbu.ru/analysis/f-doska/lap_can.pdf

Fedor Petrov
  • 102,548
  • 1
    I like this example, but again I think the objection can be raised that this is not very natural. – Thierry Zell Nov 08 '10 at 13:32
  • 1
    well, it is just the Laplace transform asymptotics of the Cantor function (of course, it is just example, but for similar functions you get similar effects).

    I would say that is not much less natural then the Cantor function itself.

     – Fedor Petrov Nov 08 '10 at 22:15
5

Some algorithms have a running time which involves $\log^* n$, the number of iterations of $\log$ before the result is at most $1$. This is essentially the inverse of tetration base $e$. For example, the Fredman-Tarjan algorithm for finding a minimal weight spanning tree has run time $E ~\log^* V$, and the randomized algorithm by Clarkson et al. for triangulating a simple polygon with $n$ vertices has expected running time $n ~\log^* n$. (In both cases, there are asymptotically faster algorithms by Bernard Chazelle.)

Douglas Zare
  • 27,806
3

Suppose F is a field of finite characteristic and u,v,w lie in A=F[x,y]. Let a_n be the dimension of the vector space A/(u^n,v^n,w^n). Suppose a_1 is >0 and finite. Then as n grows, (a_n)/(n^2), though bounded above and bounded away from 0 generally has an oscillating "fractal-like" behavior.

paul Monsky
  • 5,412
  • 2
  • 25
  • 45
1

Iterated exponentials $\exp^{[n]}(x)$ grow faster than any elementary function. It is possible to construct many functions which grow even faster.

Anixx
  • 9,302
  • 7
    Yes, but in what sense are these natural? – Qiaochu Yuan Nov 08 '10 at 12:12
  • 4
    See http://sci.tech-archive.net/Archive/sci.math.research/2007-03/msg00129.html for a thread Physical Applications of Tetration. In brief, iterated exponentials have no known natural occurrence. –  Nov 08 '10 at 13:40
  • "In addition, it is worth to note that these numbers appear in combinatorial physics, in the problem of the normal ordering of quantum field theoretical operators." http://arxiv.org/abs/0812.4047v1

    But in what sense do you want it to be natural?

     – Anixx Nov 08 '10 at 22:55