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.

  • $\begingroup$ 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 ? $\endgroup$ – Gerry Myerson Nov 5 '12 at 4:30
  • $\begingroup$ 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 $\endgroup$ – Gerry Myerson Nov 5 '12 at 4:33
  • 1
    $\begingroup$ @Gerry - yeas, I saw these. If you open the links, you will see these papers are unrelated. $\endgroup$ – Igor Pak Nov 5 '12 at 4:50
  • $\begingroup$ 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). $\endgroup$ – domotorp Nov 5 '12 at 8:42
  • $\begingroup$ 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. $\endgroup$ – Ben Barber Nov 5 '12 at 14:01

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

  • $\begingroup$ Great! Let me take a look first. Many thanks, $\endgroup$ – Igor Pak Nov 8 '12 at 5:45

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.