New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Partitions with difference conditions and Alder's conjecture

Edited by Richard V. Kadison, University of Pennsylvania, Philadelphia, PA, and approved October 6, 2004 (received for review September 20, 2004)
Abstract
In 1956, Alder conjectured that the number of partitions of n into parts differing by at least d is greater than or equal to that of partitions of n into parts ≡ ±1 (mod d + 3) for d ≥ 4. In 1971, Andrews proved that the conjecture holds for d = 2 ^{r} – 1, r ≥ 4. We sketch a proof of the conjecture for all d ≥ 32.
1. Introduction
The well known Rogers–Ramanujan identities may be stated partitiontheoretically 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 Δ_{1}(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 Δ_{2}(n) = 0 for n > 0 by the first Rogers–Ramanujan identity, and that Δ_{3}(n) ≥ 0 for all n > 0 by Schur's theorem, which states that Δ_{3}(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 ^{i} (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 ^{i} (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 qseries
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 ^{i} 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 = λ_{1} + λ_{2} + ··· + λ _{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} = 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^{n} in an infinite series s(q) by [q^{n} ](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.
Acknowledgments
I thank George E. Andrews for suggesting that I work on this project and Bruce C. Berndt for his comments and advice.
Footnotes

↵ * Email: yee{at}math.psu.edu.

This paper was submitted directly (Track II) to the PNAS office.
 Copyright © 2004, The National Academy of Sciences
References

↵
Schur, I. (1926) Sitzungsber. Preuss. Akad. Wiss. Phys.Math. Kl., 488–495.

↵
Alder, H. L. (1956) Bull. Am. Math. Soc. 62 , 76.

↵
Andrews, G. E. (1971) Pacific J. Math. 36 , 279–284.

↵
Andrews, G. E. (1998) The Theory of Partitions (AddisonWesley, Reading, MA, 1976; reissued by Cambridge Univ. Press, Cambridge, MA).

↵
Andrews, G. E. (1969) Am. J. Math. 91 , 18–24.

↵
Alder, H. L. (1948) Bull. Am. Math. Soc. 54 , 712–722.

↵
Lehmer, D. H. (1946) Bull. Am. Math. Soc. 52 , 538–544.