Experimenting with the Garsia-Milne Involution Principle
In 1981, Adriano Garsia and Steve 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, indep...
Збережено в:
| Опубліковано в: : | Symmetry, Integrability and Geometry: Methods and Applications |
|---|---|
| Дата: | 2025 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Інститут математики НАН України
2025
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/212876 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Experimenting with the Garsia-Milne Involution Principle. Shalosh B. Ekhad and Doron Zeilberger. SIGMA 21 (2025), 015, 6 pages |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860297415151583232 |
|---|---|
| author | Ekhad, Shalosh B. Zeilberger, Doron |
| author_facet | Ekhad, Shalosh B. Zeilberger, Doron |
| citation_txt | Experimenting with the Garsia-Milne Involution Principle. Shalosh B. Ekhad and Doron Zeilberger. SIGMA 21 (2025), 015, 6 pages |
| collection | DSpace DC |
| container_title | Symmetry, Integrability and Geometry: Methods and Applications |
| description | In 1981, Adriano Garsia and Steve 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 explore its complexity.
|
| first_indexed | 2026-03-21T18:31:05Z |
| format | Article |
| fulltext |
Symmetry, Integrability and Geometry: Methods and Applications SIGMA 21 (2025), 015, 6 pages
Experimenting with the Garsia–Milne Involution
Principle
Shalosh B. EKHAD and Doron ZEILBERGER
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA
E-mail: DoronZeil@gmail.com
URL: https://sites.math.rutgers.edu/~zeilberg/
Received January 31, 2025, in final form February 26, 2025; Published online March 04, 2025
https://doi.org/10.3842/SIGMA.2025.015
Abstract. In 1981, Adriano Garsia and Steve 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.
Key words: Garsia–Milne involution principle
2020 Mathematics Subject Classification: 05A19
In memory of Adriano M. Garsia (1928–2024)
and in honor of Stephen C. Milne on his 75th birthday
1 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 [10] for their fascinating history
and for many references). Already by 1940, G.H. Hardy knew of seven different proofs. In his
own words [6]:
“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 [1]. 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 us 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 us call it ϕ,
This paper is a contribution to the Special Issue on Basic Hypergeometric Series Associated with Root
Systems and Applications in honor of Stephen C. Milne’s 75th birthday. The full collection is available at
https://www.emis.de/journals/SIGMA/Milne.html
mailto:DoronZeil@gmail.com
https://sites.math.rutgers.edu/~zeilberg/
https://doi.org/10.3842/SIGMA.2025.015
https://www.emis.de/journals/SIGMA/Milne.html
2 S.B. Ekhad and D. Zeilberger
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 [4, 5]. Fairly
recently, George Andrews, in one of the fascinating interviews conducted by the visionary enu-
merative enumerator Toufik Mansour, commented [7]:
“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 (January 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 [11] and Alexander the Great [12] before them, Garsia and
Milne 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 fol-
lows. 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 (see [9, 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” [14] 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 Stephen Milne filled this gap by producing an ingenious ‘Invo-
lution 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→ WifeOf(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 bi-
jection between the set of cheating men to the set of cheating women, calledm→ MistressOf(m),
with its inverse w → LoverOf(w). It follows that there are as many faithful men as there are
Experimenting with the Garsia–Milne Involution Principle 3
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.”
2 Implementing and experimenting
with random Garsia–Milne scenarios
In order to utilize their ingenious new principle, Garsia and Milne [4, 5] had to come up with
a specific set-up for which it could be applied. Jeff Remmel [9] also applied it brilliantly to many
other scenarios. This was further extended to general partition identities by Kathy O’Hara [8],
Herb Wilf [13], David Feldman and Jim Propp [2], and others. We should also mention the inter-
esting approach of Ilse Fischer and Matjaž Konvalinka [3], 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 [M1, . . . ,Mc], where Mrs. Mi 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 map-
ping 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.
3 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
4 S.B. Ekhad and D. Zeilberger
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(
f+c−i
f−1
)(
c+f
c
) .
This is a hypergeometric distribution whose mean is 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
(c+ f + 1)cf
(f + 1)2(2 + f)
.
The third central moment is
(c+ f + 1)cf
(
2cf + f2 − 2c− 1
)
(f + 1)3(2 + f)(3 + f)
.
The fourth central moment is1
(c+ f + 1)cf
(
9c2f2 + 9cf3 + f4 − 3c2f + 6cf2 − 3f3 + 6c2 + 3cf − 9f2 + 6c− 5f
)
(f + 1)4(2 + f)(3 + f)(4 + f)
.
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)).
4 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(
i−1
f−1
)(
c+f
c
) .
The mean is, by linearity of expectation, f times the mean for one individual, given above, hence
f(c+f+1)
f+1 .
The variance is
(c+ f + 1)cf
(f + 1)2(2 + f)
.
The third central moment is
−
(c+ f + 1)cf
(
2cf + f2 − 2c− 1
)
(f + 1)3(2 + f)(3 + f)
.
The fourth central moment is2
(c+ f + 1)cf
(
9c2f2 + 9cf3 + f4 − 3c2f + 6cf2 − 3f3 + 6c2 + 3cf − 9f2 + 6c− 5f
)
(f + 1)4(2 + f)(3 + f)(4 + f)
.
1For higher central moments see the output file https://sites.math.rutgers.edu/~zeilberg/tokhniot/
oGMIP2s.txt.
2For higher central moments see the output file https://sites.math.rutgers.edu/~zeilberg/tokhniot/
oGMIP1.txt.
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGMIP2s.txt
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGMIP2s.txt
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGMIP1.txt
https://sites.math.rutgers.edu/~zeilberg/tokhniot/oGMIP1.txt
Experimenting with the Garsia–Milne Involution Principle 5
5 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.3
Denoting the lengths of the paths of the f faithful men until they reach their matched faithful
woman by [a1, . . . , af ], it is readily seen that f ≤ a1 + · · ·+ af ≤ c+ f.
Each such assignment of path-lengths can occur in f ! ways. Hence assigning the weight
ta1c+1 · · · t
af
c+f to each matching, the weight-enumerator is the coefficient of zc in the Taylor ex-
pansion of
f !
1− z
·
c+f∏
i=c+1
ti
1− zti
.
If we want to focus on one specific man, say Mr. c+1, we set tc+1 = x and tc+2 = · · · = tc+f = 1,
and normalize, in order to convert it into a probability generating function, we get that it equals
the coefficient of zc in the Taylor expansion of
c!f !
(c+ f)!
· x
(1− xz)(1− z)f
.
If we want to focus on the total complexity, you set all the ti = x getting that the probability
generating function is the coefficient of zc in the Taylor expansion of
c!f !
(c+ f)!
· xf
(1− z)(1− xz)f
.
6 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 would 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?
3It is available from https://sites.math.rutgers.edu/~zeilberg/tokhniot/GMIP.txt.
https://sites.math.rutgers.edu/~zeilberg/tokhniot/GMIP.txt
6 S.B. Ekhad and D. Zeilberger
So he asks Mrs. 1, and she happily accepts, since she has no lover and would 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!
7 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.
Acknowledgments
Many thanks to Svante Janson for helpful probability guidance. Also many thanks to anonymous
referees for corrections and insightful comments.
References
[1] Bressoud D.M., An easy proof of the Rogers–Ramanujan identities, J. Number Theory 16 (1983), 235–241.
[2] Feldman D., Propp J., Producing new bijections from old, Adv. Math. 113 (1995), 1–44.
[3] Fischer I., Konvalinka M., A bijective proof of the ASM theorem, Part I: The operator formula, Electron. J.
Combin. 27 (2020), 3.35, 29 pages, arXiv:1910.04198.
[4] Garsia A.M., Milne S.C., Method for constructing bijections for classical partition identities, Proc. Nat.
Acad. Sci. USA 78 (1981), 2026–2028.
[5] Garsia A.M., Milne S.C., A Rogers–Ramanujan bijection, J. Combin. Theory Ser. A 31 (1981), 289–339.
[6] Hardy G.H., Ramanujan, Cambridge University Press, 1940, available at https://archive.org/details/
in.ernet.dli.2015.212059/page/n3/mode/2up.
[7] Mansour T., Interview with George E. Andrews, Enumer. Comb. Appl. 1 (2021), S3I12, 7 pages.
[8] O’Hara K.M., Bijections for partition identities, J. Combin. Theory Ser. A 49 (1988), 13–25.
[9] Remmel J.B., Bijective proofs of some classical partition identities, J. Combin. Theory Ser. A 33 (1982),
273–286.
[10] Sills A.V., An invitation to the Rogers–Ramanujan identities, CRC Press, Boca Raton, FL, 2018.
[11] Wikipedia, Egg of Columbus, available at https://en.wikipedia.org/wiki/Egg_of_Columbus.
[12] Wikipedia, Gordian knot, available at https://en.wikipedia.org/wiki/Gordian_Knot.
[13] Wilf H.S., Sieve equivalence in generalized partition theory, J. Combin. Theory Ser. A 34 (1983), 80–89.
[14] Zeilberger D., Enumerative and algebraic combinatorics, in Princeton Companion to Mathematics, Edi-
tor T. Gowers, Princeton University Press, 2008, 550–561, available at http://sites.math.rutgers.edu/
~zeilberg/mamarim/mamarimPDF/enuPCM.pdf.
https://doi.org/10.1016/0022-314X(83)90043-4
https://doi.org/10.1006/aima.1995.1034
https://doi.org/10.37236/9082
https://doi.org/10.37236/9082
https://arxiv.org/abs/1910.04198
https://doi.org/10.1073/pnas.78.4.2026
https://doi.org/10.1073/pnas.78.4.2026
https://doi.org/10.1016/0097-3165(81)90062-5
https://archive.org/details/in.ernet.dli.2015.212059/page/n3/mode/2up
https://archive.org/details/in.ernet.dli.2015.212059/page/n3/mode/2up
https://doi.org/10.54550/eca2021v1s3i12
https://doi.org/10.1016/0097-3165(88)90026-X
https://doi.org/10.1016/0097-3165(82)90040-1
https://en.wikipedia.org/wiki/Egg_of_Columbus
https://en.wikipedia.org/wiki/Gordian_Knot
https://doi.org/10.1016/0097-3165(83)90042-0
https://doi.org/10.1515/9781400830398.550
http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enuPCM.pdf
http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enuPCM.pdf
1 The ``million dollar'' problem in partition theory back in 1980
2 Implementing and experimenting with random Garsia–Milne scenarios
3 The statistical distribution of the number of requests of ONE specific faithful man
4 The statistical distribution of the number of total requests by all faithful men
5 A brief explanation
6 Encore
7 Conclusion
References
|
| id | nasplib_isofts_kiev_ua-123456789-212876 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1815-0659 |
| language | English |
| last_indexed | 2026-03-21T18:31:05Z |
| publishDate | 2025 |
| publisher | Інститут математики НАН України |
| record_format | dspace |
| spelling | Ekhad, Shalosh B. Zeilberger, Doron 2026-02-13T13:49:26Z 2025 Experimenting with the Garsia-Milne Involution Principle. Shalosh B. Ekhad and Doron Zeilberger. SIGMA 21 (2025), 015, 6 pages 1815-0659 2020 Mathematics Subject Classification: 05A19 arXiv:2501.18061 https://nasplib.isofts.kiev.ua/handle/123456789/212876 https://doi.org/10.3842/SIGMA.2025.015 In 1981, Adriano Garsia and Steve 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 explore its complexity. Many thanks to Svante Janson for helpful probability guidance. Also, many thanks to anonymous referees for corrections and insightful comments. en Інститут математики НАН України Symmetry, Integrability and Geometry: Methods and Applications Experimenting with the Garsia-Milne Involution Principle Article published earlier |
| spellingShingle | Experimenting with the Garsia-Milne Involution Principle Ekhad, Shalosh B. Zeilberger, Doron |
| title | Experimenting with the Garsia-Milne Involution Principle |
| title_full | Experimenting with the Garsia-Milne Involution Principle |
| title_fullStr | Experimenting with the Garsia-Milne Involution Principle |
| title_full_unstemmed | Experimenting with the Garsia-Milne Involution Principle |
| title_short | Experimenting with the Garsia-Milne Involution Principle |
| title_sort | experimenting with the garsia-milne involution principle |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/212876 |
| work_keys_str_mv | AT ekhadshaloshb experimentingwiththegarsiamilneinvolutionprinciple AT zeilbergerdoron experimentingwiththegarsiamilneinvolutionprinciple |