Welcome to MathOverflow

Question

6

How many of the partitions of a natural number $n$ are comprised only of its divisors? That is, if $$p(n)=\sum_{\sum_{1}^n kj_k=n:j_k\geq 0} 1_{[j_1,j_2,...]},$$ is the ordinary partition function (i.e. the total number of partitions of $n$), then I want to know something about the counting function $$s(n)=\sum_{\sum_{d|n}dj_d=n:j_d\geq 0}1_{[j_1,...,j_d,...]}.$$

I would be happy to hear of anything that is known about this function, but I am particularly interested in (a) its generating functions, and (b) a bijection between this restricted partition and another (hopefully more intuitive to count) restricted partition. Any insights would be welcome.

I should add that google finds a number of papers that study "partitions of $n$ into divisors of $m$", e.g. Gupta, 1970s, but those methods reduce to rather vacuous statements when evaluated at $m=n$.

Thanks!

edited Dec 4 at 20:53

Ryan Budney
21.6k●1●40●101

asked Dec 3 at 21:37

Kevin Smith
553●2●8

1

It's tabulated at oeis.org/A018818 but I don't see any answers there. – Gerry Myerson Dec 3 at 21:48

Yes, the only thing referred to there that possibly gives a clue is the integral found when you evaluate the generating function used by Gupta at $m=n$. By Cauchy's theorem and the fact that $\sum_{d|n}phi(d)=n$, you get $$s(n)=\frac{1}{2\pi i}\int_{C}\prod_{d|n}q^{-\phi(d)}(1-q^d)^{-1}frac{dq}{q}.$$ – Kevin Smith Dec 3 at 22:37

How do you edit comments to correct latex errors? If I've not got rights would somebody do so here please? – Kevin Smith Dec 3 at 22:43

1

Comments are unfortunately not editable. You can delete it and post a corrected one (but there is no need in this case, your comment is perfectly comprehensible as it is). – Emil Jeřábek Dec 4 at 11:54

Douglas Bowman · Accepted Answer · 2012-12-04 03:24:36Z UTC

7

Bounds for this partition function were given by the editors of The American Mathematical Monthly, Paul Erdos, and Andrew Odlyzko in the March 1992 issue, p. 277, as a solution to Advance Problem number 6640. The bounds they prove are:

$$ ({\tau(n)}/{2}-1)(\log n + O({\log n}/{\log \log n})) \leq \log s(n) \leq ({\tau (n)}/{2})\log n + O(\log \log n), $$ where $\tau(n)$ is the number of divisors of $n$.

edited Dec 4 at 3:24

answered Dec 4 at 3:08

Douglas Bowman
151●3●6

Great - I'd wondered if this had cropped up. Thank you. Is an electronic copy available online do you know? I can only fond the contents page, in which the problem solutions are not listed. – Kevin Smith Dec 4 at 10:18

A copy can be obtained from JSTOR: jstor.org/stable/2325075 It looks like you should be able to see the article for free by creating a "My JSTOR" account. – Douglas Bowman Dec 4 at 14:37

2

Ah! Douglas, you didn't mention that it was you who set the problem! Not surprisingly their proof is marvellous, but it doesn't use anything deeper than the evaluation at $m=n$ of the coefficients of the polynomial mentioned above (though evidently this result is certainly not a trivial deployment of it). None-the-less, I remain particularly curious as yo what more is known... What were your interests in this function? How come you posed the problem? – Kevin Smith Dec 4 at 17:01

I considered the function arround 1982 during a time I was doing a lot of reading on partitions and analytic number theory. My motivation was that the ordinary partition function $P(n)$ has very nice asymptotics, while in multiplicative number theory, much more irregular behavior is typical. I created the function as an interesting synthesis. I thought that the generating function would likely provide purchase for finding asymptotics. In 1989 I presented the problem at a conference, where Erdos and Odlyzko got excited about it. Monthly editors then asked me to pose it as a problem. – Douglas Bowman Dec 5 at 0:27

And indeed it did provide purchase. Well, thank you for the insight, I'm very grateful. So, do you know if the upper bound is tight, or at least that $$\limsup_{n\rightarrow\infty}\frac{s(n)}{n^{\tau(n)/2}}=\infty$$? The $\liminf=1$ and this is the $\lim$ through both primes and squares of primes, but the upper bound (if tight) still suggests a lot of irregularity, specifically that $s(n)^{1/\tau(n)}=O(n^{1/2}+\epsilon)$ for every $\epsilon>0$ but not $\epsilon=0$, which is the "best-case scenario" in a lot of multiplicative number theory. – Kevin Smith Dec 5 at 12:34

show 3 more comments

Partitions comprised only of divisors

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.