Mathematicians, of course, don't have this luxury. But we are conditioned to think, perhaps, that rational numbers are better than irrational ones, that algebraic numbers are better than transcendental ones (except maybe π and e), and so on. In my corner of mathematics (discrete probability/analysis of algorithms/combinatorics), often sequences of integers a(1), a(2), ... arise and you want to know approximately how large the nth term is. For example, the nth Fibonacci number is approximately φ

^{n}/5

^{1/2}, where φ = (1+5

^{1/2})/2 is the "golden ratio". The nth Catalan number (another sequence that arises often) is approximately 4

^{n}/(π n

^{3})

^{1/2}. In general, "many" sequences turn out to satisfy something like

a(n) ~ p q

^{n}(log n)

^{r}n

^{s}

where p, q, r, and s are constants. There are deep reasons for this that can't fully be explained in a blog post, but have to do with the fact that a(n) often has a generating function of a certain type. What's surprising is that while p and q are often irrational, r and s are

*almost never*irrational, at least for sequences that arise in the "real world". Furthermore, they usually tend to be "simple" rational numbers -- 3/2, not 26/17. If you told me some sequence of numbers grows like π

^{n}I'd be interested. If you told me some sequence of numbers grows like n

^{π}. I'd assume I misheard you. Of course, there's the possibility of sampling bias -- I think that the exponents tend to be rational because if they weren't rational I wouldn't know what to do! They do occur -- for example, consider the Hardy-Ramanujan asymptotic formula for the number of partitions p(n) of an integer n:

p(n) ~ exp(π (2n/3)

^{1/2})/(4n √3)).

I know this exists, but it still just looks weird.

(This is an extended version of a comment I left at Uncertain principles.)

## 2 comments:

If you sum a multiplicative function f(n) over integers up to N, then assuming it is such that f(n) doesn't grow faster than a power of n (e.g., typically, if f is bounded on primes, and polynomially bounded on prime powers in terms of the exponent of the prime), then the typical asymptotic will be

cN(log N)^{r-1}

where r is the average value of f restricted to primes. This can be quite arbitrary (in my recent post

http://blogs.ethz.ch/kowalski/2009/02/28/a-beautiful-analogy-2/

there is a case where it is is used with r ranging over the whole unit circle...)

I have always been fascinated whenever numbers greater than 1 show up (which, in my current fields of interest, is infrequent). One of the memorable instances I recall was in the proof in Rudin's book of the polynomial approximation theorem for continuous functions on compact sets which are holomorphic in the interior, where even 10,000 came up.

Post a Comment