Take the 2-minute tour ×

Fix an arithmetic progression $R=(a, a+m, a+2m, \ldots)$, and assume that $gcd(a,m)=1$. Define $q_R(n)$ as the following coefficients: $$\prod_{i=0}^\infty (1+ t^{a+mi}) = \sum_{n=0}^\infty q_R(n) t^n $$ In other words, $q_R(n)$ is number integer partitions of $n$ into distinct parts from $R$.

Problem 1. Prove that $q_R(n)$ are increasing for $\ n\ge n(a,m)$ large enough.

I first assumed this is either standard, well known, or easily follows from the existing results. Now I am less sure. My literature search gives only papers like this (A. Tripathi, "Coin exchange problem for arithmetic progressions"). Note that for $a=m=1$, we get the usual partitions into distinct parts and the claim follows from Euler's theorem that they are equinumerous with partitions into odd parts.

More generally, I need to prove that all finite differences are positive for large enough $n$. Formally, define $$(t-1)^r \prod_{i=0}^\infty (1+ t^{a+mi}) = \sum_{n=0}^\infty q_R(n,r) t^n $$

Problem 2. For every $r\ge 1$, prove that $q_R(n,r)>0$ for $\ n\geq n(a,m,r)$ large enough.

share|improve this question
Have you checked Nyblom & Evans, On the enumeration of partitions with summands in arithmetic progression, Australasian J Combinatorics 28 (2003) 149--159, ajc.maths.uq.edu.au/pdf/28/ajc_v28_p149.pdf ? –  Gerry Myerson Nov 5 '12 at 4:30
There is also Munagi and Shonhiwa, On the partitions of a number into arithmetic progressions, J Integer Sequences 11 (2008) 08.5.4, cs.uwaterloo.ca/journals/JIS/VOL11/Shonhiwa/shonhiwa13.ps –  Gerry Myerson Nov 5 '12 at 4:33
@Gerry - yeas, I saw these. If you open the links, you will see these papers are unrelated. –  Igor Pak Nov 5 '12 at 4:50
If m=1, the statement is trivial for all a, you don't have to use Euler's theorem or anything else. Just increase the biggest term by 1 to go from a partition of n to a partition of n+1 (such that the largest term-1 is not used). –  domotorp Nov 5 '12 at 8:42
Here's a trivial observation that might help with the "follows from known results" angle. We have $n=ra+sm$ with $r>0, s \geq 0$ for around $n/(ma)$ values of $r$, and $q_R(n)$ is the sum over these $r$ of the number of ways of partitioning the corresponding $s$ into at most $r$ parts. –  Ben Barber Nov 5 '12 at 14:01
show 3 more comments

3 Answers

Problem 1 is solved completely, in the affirmative, in the following paper of Grosswald:

Emil Grosswald, Some theorems concerning partitions, Trans. Amer. Math. Soc. 89, 1958, 113–128.

Grosswald in fact gives a very accurate estimate for the asymptotics of $q_R(n)$, showing that they grow exponentially fast with $n$, and generalizes things to the case that R consists of any finite union of arithmetic progressions as well. (If you look at his rather intricate paper, look at the function that he calls $H(x)$).

share|improve this answer
Great! Let me take a look first. Many thanks, –  Igor Pak Nov 8 '12 at 5:45
add comment

The answer is indeed affirmative, but was worked out before Grosswald's paper. The earliest paper I found which deals with a general version of this problem is

Roth, K.F., Szekeres, G. "Some asymptotic formulae in the theory of partitions", Quart. J. Math., Oxford Ser. (2) 5, (1954). 241–259, MR0067913

Suppose $\lbrace u_k\rbrace$ is an eventually increasing sequence of positive integers satisfying some mild technical conditions. The paper above gives accurate asymptotics for $p_u(n)$, the number of partitions of $n$ with distinct parts from $\lbrace u_k\rbrace$. The most relevant result is that for $n$ greater than some $n_0$ which depends on $\lbrace u_k\rbrace$ and $\delta$ we have a constant $c$ so that $$p_u(n+1)-p_u(n)\geq cn^{-\frac{s}{s+1}-\delta}p_u(n),$$ where $s=\lim_{k \to \infty}\frac{\log u_k}{\log k}$. In particular their result works for sequences $u_k=p(k)$ where $p$ is a polynomial taking integers to integers with $\gcd(p(1),p(2),\dots)=1$.

share|improve this answer
Many thanks! This is very useful. –  Igor Pak Nov 10 '12 at 5:10
add comment

[This is more of a comment than an answer, but I lack the reputation.] For partitions with repetitions allowed, the analogue of your Problem #2 is solved by a very general theorem of Bateman and Erdos:


Let $A$ be an arbitrary set of natural numbers. For each nonnegative integer $k$, define $p_k(n)$ so that $$ \sum_{n=0}^{\infty} p_k(n) X^n = (1-X)^k \prod_{a \in A} (1-X^a)^{-1}. $$

They show that $p_k(n)$ is positive for all sufficiently large $n$ if and only if the following holds: There are more than $k$ elements in $A$, and if we remove an arbitrary subset of $k$ elements of $A$, the remaining elements have greatest common divisor $1$.

Unfortunately they remark that the problem of partitions into distinct parts is much harder and refer to the paper of Roth and Szekeres already mentioned in Gjergji's answer.

share|improve this answer
add comment

Your Answer


