Asymptotics of the number of compositions whose summands are the divisors of a number? - MathOverflow

Asymptotics of the number of compositions whose summands are the divisors of a number?

2009-10-21T22:39:27Z

Let n be a natural number. Let dc(n) be the number of compositions of n where the summands are required to be in the set of divisors of n. Standard lore in analytic combinatorics yields the following formula for dc(n):

dc(n) = nth Taylor coefficient of 1/(1- \sum_{m ∈ divisors of n} z^m)

But what are the asymptotics of dc(n)? Here's a plot that I made (the y-axis is dc(n) on a log scale and the x-axis is n):

I would like to understand the "fanning", which presumably has something to do with whether numbers have lots of small divisors or not, and I would also like to understand why these fans seem to be so close to exponentials. The solid fit line at the top is 2^n, which is the number of unrestricted compositions.

If that's too much to ask for, I guess I'd like to know how one might use known facts about the number of divisors, etc. to say something about this, as this rather artificial construction ought to be governed by some more fundamental number theoretic functions.

Answer by Kevin P. Costello for Asymptotics of the number of compositions whose summands are the divisors of a number?

2009-10-21T23:25:48Z

(Edited because the n/2 in the exponent in my original sketch was wrong).

Here's what might correspond to a (very) sketchy explanation as to those fans:

What does a typical (unrestricted) composition of an integer look like? Since there are 2^{n-k} compositions of n beginning with k, the expectation of the first element of the composition is actually around 2, and more generally the probability the first number is k decays exponentially with k.

In other words, a toy model for such a composition would be to successively and independently choose integers a_i such that the probability each a_i is equal to k is 2^{-k}, and stop when we reach n. This is problematic in some ways (especially when our sum gets close to n), but this should only affect the last few terms. We fail if we encounter an integer that is not a divisor of n.

By the law of large numbers we need to succeed about n/e_n times, where e_n is the expected value of a_i once we condition on the composition consisting only of divisors of n. Each integer has the same fixed probability c_n of being a divisor (here c_n depends mainly on the small divisors of n, and my intuition is that e_n would be the same way). Making a bunch of unsubstantiated independence assumptions, we would expect the probability a random composition has only divisors to be c_n^{n/e_n}. The fans then correspond to n which share the same small divisors and have approximately equal c_n and e_n.

Answer by Michael Lugo for Asymptotics of the number of compositions whose summands are the divisors of a number?

2009-10-22T04:57:05Z

The number of compositions of n with all parts equal to 1 or 2, for example, is the (n+1)st Fibonacci number, which grows like φⁿ where φ = (1+√5)/2.

The number of compositions of 2p for p a prime, where all parts are equal to 1, 2, p, or 2p, isn't all that much bigger. In particular I believe it has the same exponential growth rate. I suspect this is one of the lines you see.

Replacing 2 with any integer, you can do the same sort of thing; this is what causes your points to fall, for the most part, along straight lines.