27
$\begingroup$

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.)

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Peter Humphries
    Commented Nov 8, 2010 at 10:25
  • 4
    $\begingroup$ 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. $\endgroup$
    – Mark
    Commented Nov 8, 2010 at 10:51

8 Answers 8

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "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? $\endgroup$
    – André Henriques
    Commented Jul 18, 2011 at 20:42
  • 1
    $\begingroup$ @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! $\endgroup$
    – Todd Trimble
    Commented Jul 18, 2011 at 22:09
  • $\begingroup$ 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. $\endgroup$
    – Todd Trimble
    Commented Jul 18, 2011 at 22:20
11
$\begingroup$

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}$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Good point. Perhaps I should impose some monotonicity hypotheses... $\endgroup$
    – Qiaochu Yuan
    Commented Nov 8, 2010 at 13:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Matt Young
    Commented Nov 8, 2010 at 23:00
  • 4
    $\begingroup$ 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. $\endgroup$
    – Denis Serre
    Commented Nov 9, 2010 at 6:39
8
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Is it known whether the asymptotic behavior of the W function can be described using elementary functions? $\endgroup$
    – Qiaochu Yuan
    Commented Nov 8, 2010 at 12:12
  • $\begingroup$ 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"). $\endgroup$
    – Fedor Petrov
    Commented Nov 8, 2010 at 12:18
  • $\begingroup$ @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. $\endgroup$
    – zhoraster
    Commented Nov 8, 2010 at 12:49
  • 8
    $\begingroup$ W(x) is asymptotic to log(x/log x), which is elementary. So W is in the same boat as Li(x), already mentioned. $\endgroup$
    – Gerald Edgar
    Commented Nov 12, 2010 at 21:33
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I like this example, but again I think the objection can be raised that this is not very natural. $\endgroup$
    – Thierry Zell
    Commented Nov 8, 2010 at 13:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Fedor Petrov
    Commented Nov 8, 2010 at 22:15
5
$\begingroup$

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.)

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ Yes, but in what sense are these natural? $\endgroup$
    – Qiaochu Yuan
    Commented Nov 8, 2010 at 12:12
  • 4
    $\begingroup$ See sci.tech-archive.net/Archive/sci.math.research/2007-03/… for a thread Physical Applications of Tetration. In brief, iterated exponentials have no known natural occurrence. $\endgroup$
    – user37691
    Commented Nov 8, 2010 at 13:40
  • $\begingroup$ "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." arxiv.org/abs/0812.4047v1 But in what sense do you want it to be natural? $\endgroup$
    – Anixx
    Commented Nov 8, 2010 at 22:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .