By: David Bressoud @dbressoud

MAA has just published Addressing Challenges to the Precalculus through Calculus II Sequence through Case Studies, the Notes volume summarizing the results of the NSF-sponsored project, Progress through Calculus, case studies of interventions in the Precalculus through Calculus II sequence. It is available at https://www.maa.org/sites/default/files/pdf/pubs/books/members/NTE92.pdf. The Introduction with a description of the study and the contents of this volume is available at https://macalester.edu/~bressoud/misc/PtC-Introduction.pdf.

Problem: Prove that the number of ways of writing an integer as a sum of integers that are congruent to +1 or –1 modulo 6 is equal to the number of ways of writing that integer as a sum of integers that differ by at least 3, with multiples of 3 differing by at least 6.

As an example, there are six partitions of 12 that satisfy the first restriction: 11+1, 7+5, 7+1+1+1+1+1, 5+5+1+1, 5+1 +1+1+1+1 +1+1, and 1+1+1+1+1+1+1+1+1+1+1+1. There are also six partitions of 12 that satisfy the second: 12, 11+1, 10+2, 9+3, 8+4, and 7+3+1.

A word about this problem before I move on to my story: Euler had shown that the number of ways of writing an integer as a sum of odd integers (congruent to +1 or –1 modulo 4) is equal to the number of ways of writing that integer as a sum of distinct integers (differing by at least 1). As presented in my last column, the q-series identities discovered independently by L.J. Rogers and S. Ramanujan imply that the number of ways of writing an integer as a sum of integers congruent to +1 or –1 modulo 5 is equal to the number of ways of writing that integer as a sum of integers that differ by at least 2. The equality given in the problem, which was discovered by Issai Schur in 1926, seems to fall into that pattern. Schur is best known for his work in representation theory, but he also made significant contributions to combinatorics and number theory, including the theory of partitions where he independently discovered the Rogers-Ramanujan identities.

One is tempted to try to extend these identities to the modulus 7. Nothing comparable seems to work there or for any larger modulus. This is a prime example of Richard Guy’s strong law of small numbers: “There aren’t enough small numbers to meet the many demands made of them.” Just because a pattern seems to emerge for a few small cases does not necessarily imply it continues. As Basil Gordon was to discover in 1961 and as I explain later in this column, the fruitful generalization to higher moduli was not in terms of which residue classes are kept but rather which residue classes are excluded.

In 1956 Henry Alder conjectured a weaker extension of Schur’s theorem, that the number of partitions of n into parts differing by at least d is always greater than or equal to the number of partitions of n into parts congruent to +1 or –1 modulo d+3. In 1971 George Andrews proved this for the cases where d is one less than a power of 2. In 2004 Ae Ja Yee established the truth of this conjecture for all d great than 31. The remaining cases were proven in 2011 by Claudia Alfes, Marie Jameson, and Robert J. Lemke Oliver. See the references at the end of this column.

Henry Alder was on the faculty of UC Davis. He served as Secretary of MAA from 1960 to 1975 and as President from 1977 to 1979. I include Schur’s theorem because very early in my career I discovered a simple proof, sufficiently appealing that Henry Alder in his retiring address as MAA President included it in his talk. I had arrived.

I return to my story in the summer of 1976. The bulk of the results that would form my doctoral thesis had been found. Grosswald recommended that I go to the summer math meetings, which were held at the University of Toronto that year, to talk about my findings. This was an unsolicited 10-minute talk from a total unknown, which usually is a sign there will be a pretty small audience. To make it worse, my presentation was opposite the last-minute presentation by Appel and Hawkin of their proof of the four-color theorem, the computer intensive proof that any planar map can always be colored with four colors without any two adjacent regions needing to share the same color.

As I remember it, there were three people in the audience for my presentation: the person who spoke before me and who needed to introduce my talk, the person scheduled to speak after me and who was nervously waiting his turn, and Dick Askey.

Dick had scoured the abstracts and picked out my work as demonstrating potential. He then spent the rest of the afternoon with me, explaining how my work connected to the theory of q-series and telling me what I needed to read, most especially George Andrews’ The Theory of Partitions, which had appeared in 1976, and Theory and Applications of Special Functions, the collection of papers presented in 1976 at a special seminar at the University of Wisconsin. He particularly directed me toward George Andrews’ article “Problems and Prospects for Basic Hypergeometric Functions,” which I proceeded to study in detail.

Dick also believed that I would benefit from meeting George. I am not sure exactly how it came about. Grosswald knew Andrews. They shared the same doctoral adviser, Hans Rademacher. They had overlapped at Penn where George was a graduate student and Grosswald an instructor, and they knew each other’s work. It was quite natural for Grosswald to invite Andrews, who was just up the road at Penn State, to come down to Temple to present a colloquium, which he did early in 1977. Dick, who was very close to George, may have planted the suggestion.

In any event, George came, talked about q-series, and presented a variety of open problems. The writing of my thesis was pretty well wrapped up by now so I was free to throw myself into George’s problems. I found solutions to several of them.

At the time, my job prospects were not bright. I had been to the Joint Math Meetings and emerged with only one promising lead.  SUNY Binghamton seemed interested in me. Before they made any decision, I received an offer from Penn State. As I have since learned, the Penn State math department does not hire anyone who does not have an advocate among their faculty, and a powerful advocate such as George carries a lot of weight. They offered me a two-year visiting position.

That spring turned out to be extremely fruitful. By June I had proven one of my most significant results, a generalization of the Rogers-Ramanujan identities that extends to any modulus. In 1961, Basil Gordon published an extension of the Rogers-Ramanujan identities to any odd modulus (Figure 1). By 1967 George Andrews had the case where the modulus is congruent to 2 modulo 4 and the value of r, giving the two excluded residue classes other than 0, is odd. He included the case where the modulus is congruent to 2 modulo 4 and r is even in his 1976 The Theory of Partitions. In the spring of 1977 while preparing for and making my move to State College, I discovered and proved the case for arbitrary even modulus (Figure 2).

This in turn led to multiple generalizations and extensions of these identities and their analytical underpinnings which I published as an AMS Memoir in 1980. The acceptance of this Memoir helped establish my reputation as a research mathematician, and in 1979 I was appointed to a tenure-track position at Penn State.

My progression was unusual in the extreme. I went from a doctorate at a Research 2 university to what would become a tenured position and then full professorship at one of the 25 elite public Research 1 universities. I recognize how much my subsequent career has built on that intervention by Dick and George. I am forever in their debt.

The experience taught me two deep lessons about choosing a doctoral advisor. First, it has to be someone with whom you can build an easy rapport. The specific area in which one chooses to work is far less important. In fact Grosswald specifically warned me not to expect that I would continue to work in the area in which I had received my doctorate. The doctorate is a signal that one is capable of making a significant, original contribution to mathematics viewed broadly, nothing more. Secondly, the reputation of the doctoral advisor and the extent to which he or she is plugged into a network of researchers is extremely important. This should never outweigh the first consideration. Many highly respected mathematicians make lousy advisors. But it is an important consideration for launching a successful career. 

The first step in establishing the correspondence between the two types of partitions is to note that the integers congruent to +1 or –1 modulo 6 are simply the odd integers that are not divisible by 3. Euler had used generating functions to establish that the number of partitions of n into odd integers is equal to the number of partitions into distinct integers. Hardy and Wright gave a nice combinatorial proof. Either proof shows that eliminating multiples of 3 among the odd integers implies eliminating the multiples of 3 among the distinct integers. Because it is purely combinatorial, I will give the Hardy and Wright proof.

Every positive integer has a unique representation as a power of 2 (which might be 2^0) times an odd integer (which might be 1) that I will refer to as the odd root. We take the distinct integers and group those that share the same odd root. The sum of the corresponding powers of 2 yields a unique integer that will designate the number of times this odd integer appears in the partition into odd integers. For example, the partition into distinct integers 1 + 4 + 5 + 6 + 8 + 20 is grouped as (1 + 4 + 8)*1 + (2)*3 + (1 + 4)*5, giving thirteen 1’s, two 3’s, and five 5’s. This is clearly uniquely reversible. If there are no multiples of 3 among the distinct integers, there will be no multiples of 3 among the odd integers, and vice-versa.

The next piece was my contribution. Given a partition into distinct integers with no multiples of 3, we find the largest pair that differ by less than 3 and add them together, then continue moving down among the remaining integers until we find the next largest pair with difference less than 3 and again add them together. Continue until all of the integers not divisible by 3 differ by at least 3. Within each pair, necessarily one of the numbers is congruent to +1 and the other –1 modulo 3, so each sum is divisible by 3. Consider the following example,

1+2+4+7+8+14 -> 1 + 6 + 15 + 14. We subtract 3 from the second number, 6 from the third, and in general 3(k–1) from the kth. We place the remaining integers in increasing order, then add back in 3 to the second, 6 to the third, and so on,

1 + 6 + 15 + 14 => 1 + 3 + 9 + 5 => 1 + 3 + 5 + 9 => 1 + 6 + 11 + 18.

All of these integers will differ by at least 3, and the multiples of 3 must differ by at least 6 because at the intermediate stage the multiples of 3 are distinct. What may not be immediately obvious is that this procedure is uniquely reversible.

Unfortunately, the verification that I had to use, shown in Figures 3, 4, and 5, is not as simple as I would like it to be. Note that the actual theorem and my proof of it are more general.

For 0 < r < m/2, the number of partitions of n into distinct parts congruent to +r or –r modulo m is equal to the number of partitions of n into parts congruent to 0, +r, or –r modulo m that differ by at least m, with parts divisible by m differing by at least 2m. The same correspondence works for this more general case. You can find the full statement and proof in my article “A Combinatorial Proof of Schur’s 1926 Partition Theorem’’ which was published in the Proceedings of the American Mathematical Society, vol. 79, 1980, 338–340.

I should add that after it was published I realized that I did not like the article as it was written. It lacks examples or any sense of the simplicity of the idea. That is what Alder emphasized in his presentation, ignoring the unique reversibility and simply asserting its truth. Of course, that was a public presentation, not a rigorous proof. While published research must be logically complete, it also must communicate the spirit of the proof. I failed to do that in this paper, but I did learn from this misrendering. In some sense, this column is my attempt at correcting that error 

References

Alder, H.L. (1956). Research problem no. 4, Bull. Amer. Math. Soc. 62, 76

Alfes, C., Jameson, M. and Lemke Oliver, R.J., (2011), Proof of the Alder-Andrews Conjecture, Proc. AMS, 139, 63–78.

Andrews, G.E. (1967). Some new partition theorems. J. Combinatorial Theory, 2, 431–436.

Andrews, G.E. (1971). On a partition problem of H. L. Alder. Pacific J. Math., 36, 279–284.

Andrews, G.E. (1976). The Theory of Partitions. Reading, MA: Addison-Wesley.

Bressoud, D. (1979). A generalization of the Rogers-Ramanujan identities for all moduli. J. Combinatorial Theory, Series A. 27, 64–68.

Bressoud, D. (1980). A combinatorial proof of Schur’s 1926 partition theorem, Proc. AMS, 79, 338–340.

Bressoud, D. (1980). Analytic and combinatorial generalizations of the Rogers-Ramanujan identities. Memoirs of the American Mathematical Society #227. Providence RI: AMS.

Gordon, B. (1961). A combinatorial generalization of the Rogers-Ramanujan identities. Amer. J. Math. 83, 393–399.

Yee, A.J. (2004). Partitions with difference conditions and Alder’s conjecture. Proc. Natl. Acad. Sci. USA, 101, 16417–16418.

Yee, A.J. (2008). Alder’s Conjecture, J. Reine Angew. Math. 616, 67–88

Download the list of all past Launchings columns, dating back to 2005, with links to each column.