Experimenting with the Garsia-Milne Involution Principle

Shalosh B. EKHAD and Doron ZEILBERGER

In memory of Adriano M. Garsia (1928-2024) and in honor of Stephen C. Milne on his

75th birthday

Abstract: In 1981, Adriano Garsia and Stephen Milne found the first bijective proof of the celebrated Rogers-Ramanujan identities. To achieve this feat, they invented a versatile tool that they called the Involution Principle. In this note we revisit this useful principle from a very general perspective, independent of its application to specific combinatorial identities, and will explore its complexity.

The “Million Dollar” Problem in Partition Theory Back in 1980

One of the most famous identities in both enumerative combinatorics and number theory are the Rogers-Ramanujan identities (see Drew Sills’ wonderful book [S] for their fascinating history and for many references). Already by 1940, G.H. Hardy knew of seven different proofs. In his own words ([H]):

“I can remember very well his surprise, and the admiration which he expressed for Rogers’ work. A correspondence followed in the course of which Rogers was led to a considerable simplification of his original proof. About the same time I. Schur, who was then cut off from England by the war, rediscovered the identities again. Schur published two proofs, one of which is ‘combinatorial’ and quite unlike any other proof known. There are now seven published proofs, the four referred to already, the two much simpler proofs found later by Rogers and Ramanujan and published in the Papers, and a much later proof by Watson based on quite different ideas. None of these proofs can be called both simple and straightforward, since the simplest are essentially verifications; and no doubt it would be unreasonable to expect a really easy proof.”

Forty years later, in the early 1980s, there were a few additional proofs, including a lovely combinatorial proof by Dave Bressoud [B]. But none of them was bijective. Recall that the first Rogers-Ramanujan identity is equivalent to the fact that the cardinality of the set of integer partitions of n into parts that differ from each other by at least 2, let’s call it A(n), has the same number of elements as the set of integer partitions of n whose parts are congruent to one or four modulo five. The great open problem at that time was to find an explicit bijection from the set A(n) onto the set B(n). This means to come up with an algorithm, let’s call it ϕ, that inputs a member a ∈ A(n) and outputs a member b ∈ B(n), and does not use the fact that |A(n)| = |B(n)|, thereby giving a bijective proof of this identity.

The (already then) grand old man of partition theory, George Andrews, offered a monetary prize for this challenge, that Adriano Garsia and Stephen Milne proudly won [GM1][GM2]. Fairly recently, George Andrews, in one of the fascinating interviews conducted by the visionary enumerative enumerator Toufik Mansour, commented [AM]:

“Finally, and most importantly, the q-world is the natural home of the generating functions for integer partitions. For example, the celebrated Rogers-Ramanujan identities were first proved in 1894 by Rogers. It took until 1981 when Garsia and Milne published a purely bijective proof in a 50-page paper.”

Very recently (Jan. 24, 2025) George Andrews confirmed it in an Email message, that he kindly allowed us to quote:

“As I recall, Steve called me and said they had a proof. I was skeptical until I heard the word ‘non-canonical’. That meant to me that their algorithm would somehow blindly match things up but, at the end, you would have no feeling for what happened, nor would you have any idea of a refinement of Rogers-Ramanujan. I wrote the check for 50 dollars on the spot and sent it to Milne that evening. I think this was in the early 1980”.

Like Christopher Columbus [Wik1] and Alexander the Great [Wik2] before them, Garsia and Mline had a brilliant idea: think outside the box! First come up with two much larger (but still finite) sets X(n) and Y (n) such that there are natural bijections,

ϕ : X(n) → Y (n) ,

and

ψ : X(n)\A(n) → Y (n)\B(n) ,

then construct the artificial bijection

α : A(n) → B(n) ,

as follows. Given a ∈ A(n), let k be the smallest non-negative integer such that (ϕψ^{−1})^{k}ϕ(a) ∈ B(n), and define α(a) := (ϕψ^{−1})^{k}ϕ(a).

Comment: The original set-up for the Involution Principle (hence the name), succinctly summarized by Jeff Remmel ([R], section 1), involved a pair of involutions α and β and sets A = A^{+} ∪A^{−}, B = B^{+} ∪ B^{−} as well as a sign-preserving bijection from A to B and sign-reversing involutions α and β defined on A and B respectively. It is easy to see that this scenario can be reduced to the above simplified version.

Artificial or not it was brilliant and became iconic. It was deemed important enough to be included in the chapter “Enumerative and Algebraic Combinatorics” [Z] in the monumental Princeton Companion to Mathematics , edited by Sir Timothy Gowers. Let us quote:

“When we perform algebraic (and logical, and even analytical) manipulations, we are really rearranging and combining symbols, hence doing combinatorics in disguise. In fact, everything is combinatorics. All we need to do is to take the combinatorics out of the closet, and make it explicit. The plus sign turns into (disjoint) union, the multiplication sign becomes Cartesian product, and induction turns into recursion. But what about the combinatorial counterpart of the minus sign?

In 1982, Adriano Garsia and Steven Milne filled this gap by producing an ingenious ‘Involution principle’ that enables one to translate the implication

a = b and c = d ⇒ a − c = b − d ,

into a bijective argument, in the sense that if C ⊂ A and D ⊂ B, and there are natural bijections f : A → B and g : C → D establishing that a := |A| equals b := |B|, and c := |C| equals d := |D|, then it is possible to construct an explicit bijection between A\C and B\D. Let us define it in terms of people. Suppose that in a certain village all the adults are married, and hence there is a natural bijection between the set of married men to the set of married women, m → W ifeOf(m), with its inverse w → HusbandOf(w). In addition, some of the people have extra-marital affairs, (but only one per person, and all within the village). There is a natural bijection between the set of cheating men to the set of cheating women, called m → MistressOf(m), with its inverse w → LoverOf(w). It follows that there are as many faithful men as there are faithful women. How to match them up? (say if a faithful man wants a faithful woman to go to Church with him). A faithful man first asks his wife to come with him. If she is faithful, she agrees. If she is not, she has a lover, and that lover has a wife. So she tells her husband: sorry, hubby, but I am going to the pub with my lover, but my lover’s wife may be free, so the man asks the wife of the lover of his wife to go with him, and if she is faithful, she agrees. If she is not, he keeps asking the wife of the lover of the woman who just rejected his proposal, and since the village is finite, he will eventually get to a faithful woman.

The reaction of the combinatorial enumeration community to the Involution Principle was mixed. On the one hand it had the universal appeal of a general principle, that should be useful in many attempts to find bijective proofs of combinatorial identities. On the other hand, its universality is also a major drawback, since Involution Principle proofs usually do not give any insight into the specific structures involved, and one feels a bit cheated. Such a proof answers the letter of the question, but misses its spirit. In these cases one still hopes for a really natural, ‘Involution Principle- free proof’. This is the case with the celebrated Rogers-Ramanujan identity that states that the number of partitions of an integer into parts that leave remainder 1 or 4 when divided by 5 equals the number of partitions of that integer with the property that the difference between parts is at least 2. For example if n = 7 the cardinalities of {61, 4111, 1111111} and {7, 61, 52} are the same. Garsia and Milne invented their notorious Principle in order to give a Rogers-Ramanujan bijection, thereby winning a 50 dollar prize from George Andrews. However, finding a really nice bijective proof is still an open problem.”

Implementing and Experimenting with Random Garsia-Milne Scenarios

In order to utilize their ingenious new principle, Garsia and Milne [GM1][GM2] had to come up with a specific set-up for which it could be applied. Jeff Remmel [R] also applied it brilliantly to many other scenarios. This was further extended to general partition identities by Kathy O’Hara [O], Herb Wilf [Wil], David Feldman and Jim Propp [FP], and others. We should also mention the interesting approach of Ilse Fischer and Matjaž Konvalinka, who turned the involution principle into a calculus of ‘signed sets’ and ‘sijections’ (as they call them).

Here we will forget about the origin of the Involution Principle in partition theory and study it completely generally, using the very general framework of cheating and faithful men and women, where the assignment of the mapping “mistress of” is completely arbitrary and random. Suppose you have c cheating men and f faithful men, and also c cheating women and f faithful women. Without loss of generality the cheating men are Mr. i, for 1 ≤ i ≤ c and the faithful men are Mr. i for c + 1 ≤ i ≤ c + f. Both marital and extra-marital relationships are monogamous. So any such situation can be described as a list of length c

[M_{1}, …, M_{c}] ,

where Mrs. M_{i} is the mistress of Mr. i. The entries are all distinct and belong to {1, …, c + f}.

Note that there are (c + f)(c + f − 1) ⋯ (f + 1) ways of doing it.

We were wondering about the complexity (i.e. the number of requests) of the resulting mapping from faithful men to faithful women, both for one specific individual (without loss of generality, Mr. c + 1) and also about the total complexity adding up all the requests by all faithful men.

The Statistical Distribution of the Number of Requests of ONE specific faithful man

For any specific faithful man (w.l.o.g. Mr. c+1) what is the probability that he would have to make i requests? If his wife is faithful (has no lover) it is one request. The other extreme is i = c + 1, where he had to ask all the cheating women, c of them, until he got a match. It turns out (see below) that this probability is:

\begin{matrix}( & {f+c−i \atop f−1} & ) \\ ( & {c+f \atop c} & ) \end{matrix} .

This is a hypergeometric distribution whose mean is

\frac{c + f + 1}{f + 1} .

Note that if the number of cheating men far exceeds the number of faithful men (that is definitely the case in all the applications to partition identities) this average complexity is rather large and tends to the ratio c/f.

The variance is

\frac{(c + f + 1) cf}{(f + 1)^{2} (2 + f)} .

The third central moment is:

\frac{(c + f + 1) cf (2cf + f^{2} − 2c − 1)}{(f + 1)^{3} (2 + f) (3 + f)} .

The fourth central moment is:

\frac{(c + f + 1) cf (9c^{2}f^{2} + 9c f^{3} + f^{4} − 3c^{2}f + 6c f^{2} − 3f^{3} + 6c^{2} + 3cf − 9f^{2} + 6c − 5f)}{(f + 1)^{4} (2 + f) (3 + f) (4 + f)} .

For higher central moments see the output file:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGMIP2s.txt .

Letting c = f it is easily seen that the limiting distribution as f goes to infinity is the Geometric distribution Ge(1/2). More generally for any fixed k setting c = kf and letting f go to infinity, the limiting distribution is Ge(1/(k + 1)). The Statistical Distribution of the Number of Total Requests by All Faithful Men What about the total number of requests by all faithful men until they find a woman to go to church with? This number can be anything between f (where all the faithful men are married to faithful women) and c + f. The probability that it is i equals

\begin{matrix}( & {i−1 \atop f−1} & ) \\ ( & {c+f \atop c} & ) \end{matrix} .

The mean is, by linearity of expectation, f times the mean for one individual, given above, hence:

\frac{f (c + f + 1)}{f + 1} .

The variance is

\frac{(c + f + 1) cf}{(f + 1)^{2} (2 + f)} .

The third central moment is:

−\frac{(c + f + 1) cf (2cf + f^{2} − 2c − 1)}{(f + 1)^{3} (2 + f) (3 + f)} .

The fourth central moment is:

\frac{(c + f + 1) cf (9c^{2}f^{2} + 9c f^{3} + f^{4} − 3c^{2}f + 6c f^{2} − 3f^{3} + 6c^{2} + 3cf − 9f^{2} + 6c − 5f)}{(f + 1)^{4} (2 + f) (3 + f) (4 + f)} .

For higher central moments see the output file:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGMIP1.txt .

A brief explanation

All the above results were obtained via the Maple package GMIP.txt written by the second author and executed by the first one. It is available from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/GMIP.txt .

Denoting the lengths of the paths of the f faithful men until they reach their matched faithful woman by

[a_{1}, …, a_{f}] ,

it is readily seen that

f ≤ a_{1} + … + a_{f} ≤ c + f .

Each such assignment of path-lengths can occur in f! ways. Hence assigning the weight t_{c+1}^{a_{1}} ⋯ t_{c+f}^{a_{f}} to each matching, the weight-enumerator is the coefficient of z^{c} in the Taylor expansion of

\frac{f!}{1 − z} · ∏_{i=c+1}^{c+f} \frac{t_{i}}{1 − zt_{i}} .

If we want to focus on one specific man, say Mr. c + 1, we set t_{c+1} = x and t_{c+2} = … = t_{c+f} = 1, and normalize, in order to convert it into a probability generating function, we get that it equals the coefficient of z^{c} in the Taylor expansion of

\frac{c!f!}{(c + f)!} · \frac{x}{(1 − xz)(1 − z)^{f}} .

If we want to focus on the total complexity, you set all the t_{i} = x getting that the probability generating function is the coefficient of z^{c} in the Taylor expansion of

\frac{c!f!}{(c + f)!} · \frac{x^{f}}{(1 − z) (1 − xz)^{f}} .

Encore

Our package can also spell out any random scenario. Procedure RandL(n,k) gives a random assignment when there are n men and n women and k cheating men and k cheating women. Procedure GMstory(n,L) spells out all the requests by the faithful men and gives the resulting matching. Here is a small example: Typing RandL(4,3); may yield (out of 4·3·2 = 24 possibilities).

L = [2, 4, 3] .

Then typing GMstory(4,L); tells you the story:

Once upon a time there was a village with 4 married couples. Let us call them Mr. i and Mrs. i, where Mr. i and Mrs. i are married to each other, where i goes from 1 to 4.

It so happened that Mr. 1, Mr 2, and Mr 3 are cheaters. They each have one mistress:

• The Mistress of Mr. 1 is Mrs. 2 (and hence the Lover of Mrs 2 is Mr. 1)

• The Mistress of Mr. 2 is Mrs. 4 (and hence the Lover of Mrs 4 is Mr. 2)

• The Mistress of Mr. 3 is Mrs. 3 (and hence the Lover of Mrs 3 is Mr. 3) (this can happen!) The 3 cheating men and their mistresses refuse to go to Church on Sunday, they rather go to the pub. There must be a way to match the only faithful man, Mr. 4 with the only faithful woman Mrs. 1. Mr. 4 first asks his wife: “My dear wife, will you go with me to Church?” She replies: “Sorry, hubby, but I am going to the pub with my lover, Mr. 2, perhaps his wife Mrs. 2 is willing? So Mr. 4 asks Mrs. 2 and she replies : “Sorry Mr. 4, I can’t make it, I am going to the pub with my lover Mr. 1, why won’t you ask his wife, Mrs. 1? So he asks Mrs. 1, and she happily accepts, since she has no lover and rather go to Church. So Mr. 4 goes to Church with Mrs. 1. Simulation: We also have simulation procedures, that empirically confirm the theoretical results. Enjoy! Conclusion When Adriano Garsia and Stephen Milne astounded the enumerative combinatorics community with the first proof of the Rogers-Ramanujan identities, in some sense they “cheated”, but in a good way! By doing it they invented an essential tool for constructing bijections between combinatorial objects that often do not seem to have a natural canonical mapping between them, so faute de mieux, one has to resort to it. Since it is so general, one can forget about the specific combinatorial framework and play around with random men and women and study the statistical distribution of their interactions. Acknowledgment: Many thanks to Svante Janson for helfpul probability guidance. Also many thanks to two anonymous referees for corrections and insightful comments. References

[AM] George Andrews and Toufik Mansour, Interview of George Andrews by Toufik Mansour, Enumerative Combinatorics and Applications 1:3 (2021) Interview #S3I12.

https://ecajournal.haifa.ac.il/Volume2021/ECA2021 S3I12.pdf .

[B] David M. Bressoud An easy proof of the Rogers-Ramanujan identities, Journal of Number Theory 16 (1983), 235-241.

https://www.sciencedirect.com/science/article/pii/0022314X83900434

[FP] D. Feldman and J. Propp, Producing new bijections from old, Advances in Mathematics 113 (1995), 1-44.

[FK] Ilse Fischer and Matjaž Konvalinka, A bijective proof of the ASM theorem: the operator formula, Electronic Journal of Combinatorics 27(3) (2020) #3.35

https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i3p35/pdf ,

[GM1] Adriano M. Garsia and Stephen C. Milne, Method for constructing bijections for classical partition identities, Proc. Nat. Acad. Sci. U.S.A. 78 (1981), 2026-2028.

[GM2] Adriano M. Garsia and Stephen C. Milne, A Rogers-Ramanujan bijection, J. Combin. Theory Ser. A 31 (1981), 289-339.

[H] G. H. Hardy, “Ramanujan”, Cambridge University Press, 1940. Available online from:

https://archive.org/details/in.ernet.dli.2015.212059/page/n3/mode/2up .

[O] Kathy M. O’Hara, Bijections for partition identities, J. Combin Theory Ser. A 49 (1988), 13-25.

[R] Jeffrey B. Remmel, Bijective proofs of some classical partition identities, J. of Combinatorics Series A 33 (1982), 272-286.

[S] Andrew V. Sills, An invitation to the Rogers-Ramanujan identities, CRC Press, 2018.

[Wik1] Wikipedia, Egg of Columbus https://en.wikipedia.org/wiki/Egg of Columbus .
[Wik2] Wikipedia, Gordian Knot https://en.wikipedia.org/wiki/Gordian Knot .

[Wil] Herbert S. Wilf, Sieve equivalence in generalized partition theory, J. Combin. Theory Ser. A 34 (1983) 80-89.

[Z] Doron Zeilberger, Enumerative and Algebraic Combinatorics, in: Princeton Companion to Mathematics , (Timothy Gowers, ed.), Princeton University Press, 550-561, 2008.

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enuPCM.pdf .

Shalosh B. Ekhad, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

First writen: Jan. 30, 2025. This version: Feb. 25, 2025.