06 March 2009

Conditioned to rationality

At Uncertain Principles and Unqualified Offerings there has been talk about how students in disciplines where the numbers come with units seem to be conditioned to expect numbers of order unity. (And so are professional scientists, who deal with this by defining appropriate units.)

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/51/2, where φ = (1+51/2)/2 is the "golden ratio". The nth Catalan number (another sequence that arises often) is approximately 4n/(π n3)1/2. In general, "many" sequences turn out to satisfy something like

a(n) ~ p qn (log n)r ns

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


Anonymous said...

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


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

Anonymous said...

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.