Partitions with difference conditions and Alder's conjecture

1. Introduction

The well known Rogers–Ramanujan identities may be stated partition-theoretically as follows. If c = 1 or 2, then the number of partitions of n into parts ≡ ±c (mod 5) equals the number of partitions of n into parts ≥ c with minimal difference 2 between parts. In 1926, I. Schur (1) proved that the number of partitions of n with minimal difference 3 between parts and no consecutive multiples of 3 equals the number of partitions into parts ≡ ±1 (mod 6).

In 1956, H. L. Alder (2) posed the following problems. Let q_d(n) be the number of partitions of n into parts differing by at least d; let Q_d(n) be the number of partitions of n into parts ≡±1 (mod d + 3); let Δ_d(n) = q_d(n) – Q_d(n). (a) Is Δ_d(n) nonnegative for all positive d and n? It is known that Δ₁(n) = 0 for n > 0 by Euler's identity, that the number of partitions of n into distinct parts equals that of partitions of n into odd parts, that Δ₂(n) = 0 for n > 0 by the first Rogers–Ramanujan identity, and that Δ₃(n) ≥ 0 for all n > 0 by Schur's theorem, which states that Δ₃(n) equals the number of those partitions of n into parts differing by at least 3 that contain at least one pair of consecutive multiples of 3. (b) If problem a is true, can Δ_d(n) be characterized as the number of partitions of n of a certain type, as is the case for d = 3?

In 1971, G. E. Andrews (3) gave some partial answers to problem a.

Theorem 1.1 (ref. 3 ). For any d ≥ 4, lim_{n →∞} Δ_d(n) = ∞.

Theorem 1.2 (ref. 3 ). If d = 2^r – 1, r ≥ 4, then Δ_d(n) ≥ 0 for all n.

To prove Theorem 1.2, Andrews studied the set of partitions of n into distinct parts ≡ 2ⁱ (mod d) for 0 ≤ i < r, the size of which is greater than or equal to Q_d(n) for any n, and he succeeded in finding a set of partitions with difference conditions between parts that are complicated but much stronger than the difference condition for q_d(n). He then proved that partitions into distinct parts ≡ 2ⁱ (mod d) for 0 ≤ i < r and partitions with the difference conditions are equinumerous. As a result, he was able to prove Alder's conjecture in these particular cases.

By generalizing Andrews' methods and constructing an injection, we are able to prove that Alder's conjecture holds for d = 7 and d ≥ 32 (unpublished work). Therefore, Alder's conjecture still remains unresolved for 4 ≤ d ≤ 30 and d ≠ 7, 15.

In Section 2, we will give an outline of the proof of the case when d = 2^r – 1, r ≥ 4 by Andrews, and in Section 3, we will sketch the proof of the case when d ≥ 32.

In the sequel, we assume that |q| < 1 and use the customary notation for q-series

2. The Case When d = 2^r – 1

From the definitions of q_d(n) and Q_d(n), the generating functions for q_d(n) and Q_d(n) are, respectively, (see ref. 4, chapter 1).

For a given d = 2^r – 1, define Then Let and Let β_d(m) denote the least positive residue of m modulo d. For m ∈ A′_d, let b(m) be the number of terms appearing in the binary representation of m, and let v(m) denote the least 2ⁱ in this representation. We need a theorem of Andrews (5), which we state without proof in the following theorem.

Theorem 2.1. Let D(A_d; n) denote the number of partitions of n into distinct parts taken from A_d, and let E(A′_d; n) denote the number of partitions of n into parts taken from A′_d of the form n = λ₁ + λ₂ + ··· + λ_s, such that Then D(A_d; n) = E(A′_d; n).

Meanwhile, Andrews (3) established the following general theorem in the theory of partitions.

Theorem 2.2. Let and be two strictly increasing sequences of positive integers such that b ₁ = 1 and a_i ≥ b_i for all i. Let ρ(S; n) and ρ(T; n) denote the numbers of partitions of n into parts taken from S and T, respectively. Then, for n ≥ 1,

By comparing parts arising in partitions counted by Q_d(n) and L_d(n), we see that L_d(n) ≥ Q_d(n) for r ≥ 4. Because L_d(n) = D(A_d; n) and q_d(n) ≥ E(A′_d; n), it follows from Theorem 2.1 that q_d(n) ≥ L_d(n). Therefore, we have shown that q_d(n) ≥ Q_d(n) for d = 2^r – 1, r ≥ 4.

3. The Case When d ≠ 2^r – 1

We denote the coefficient of qⁿ in an infinite series s(q) by [qⁿ](s(q)).

For a given d, uniquely define the integer r by and let L′_d(n) be the number of partitions of n into distinct parts ≡ 1, 2, 4,..., 2^{r –1} (mod d). Then the generating function f_d(q) for L′_d(n) is

By examining the generating function f_d(q), we find from Theorem 2.2 that for d ≥ 32, where L′_d(m) = 0 if m ≤ 0. Thus, we only need to prove that Let X(d; n) and Y(d; n) be the sets of partitions of n counted by q_d(n) and L′_d(n), respectively. Then because the conditions for Y(d; n) are much stronger than those for X(d; n). Thus, if there exists an injection from Y(d; n – 2^r) to X(d; n)\Y(d; n), then the Alder conjecture holds.

Lemma 3.1. For any d ≥ 32 not of the form 2^r – 1,

To obtain Lemma 3.1, we construct an injection from Y(d; n – 2^r) to X(d; n) such that the image of a partition in Y(d; n – 2^r) does not satisfy the conditions for Y(d; n). For n < 4d + 2^r, we can show that q_d(n) ≥ Q_d(n) by merely counting q_d(n) and Q_d(n). Therefore, from Lemma 3.1, inequality 3.1, and Andrews' result we obtain the following theorem.

Theorem 3.2. For d ≥ 31,

4. Conclusion

The most intriguing identities in the theory of partitions have been the Rogers–Ramanujan identities. Extremely motivated by these identities, Schur searched for further analogous partition identities. In 1926, Schur (1) proved that the number of partitions of n with minimal difference 3 between parts and no consecutive multiples of 3 equals the number of partitions of n into parts ≡ ±1 (mod 6).

Alder's conjecture has naturally arisen from the Rogers– Ramanujan identities and the Schur identity, and has been open for ≈50 years. The difficulty in dealing with the conjecture is that no set S exists such that the number of partitions of n with parts from S is equal to q_d(n) for d ≥ 3 (see refs. 6 and 7). Thus finding injections between two sets might not be the most efficient method, but it is the best approach for the conjecture at this point.