REVIEW 1 major objections 5 minor 14 references
Experimenting with the Garsia-Milne Involution Principle
T0 review · 1 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read Under a uniform random assignment of mistresses, the number of requests a faithful man makes before finding a faithful woman follows a hypergeometric distribution, and the total requests across all faithful men follows a related…
desk verdict A small, correct note on the random-model complexity of the Garsia–Milne involution principle; Section 5's proof sketch has a spurious f! factor that needs fixing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the random 'village' model: $c$ cheating men, $f$ faithful men, and equally many women, with monogamous marriages and monogamous extramarital affairs. The assignment of mistresses to cheating men is a uniformly random injection from the $c$ cheating men to the $c+f$ women, with $(c+f)!/f!$ possibilities. A faithful man follows the chain wife $\to$ lover $\to$ lover's wife $\to\cdots$ until he reaches a faithful woman; the length of this chain is the request count. The paper encodes path lengths with the generating function $c!f!/(c+f)!$ times a coefficient extraction, which turns the distributional question into a Taylor-expansion problem solvable by standard coefficient extraction.
What would settle it
Enumerate or simulate the random village model for small $c$ and $f$ (e.g., $c=f=2$, where there are $4!/2!=12$ assignments) and compare the empirical request-count distribution for one specific faithful man with the claimed hypergeometric probabilities. For $c=f=2$, the formula gives $P(i)=(4-i)/6$ for $i=1,2,3$; a complete enumeration of all 12 configurations that produces different probabilities would refute the paper's claim.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the complexity of the Garsia–Milne involution principle—measured by the number of 'requests' a faithful man must make before reaching a faithful woman—has precise statistical laws under a uniformly random assignment of mistresses. For one specific faithful man, the probability of needing exactly $i$ requests is $\binom{f+c-i}{f-1}/\binom{c+f}{c}$ for $i=1,\dots,c+1$, a hypergeometric distribution with mean $(c+f+1)/(f+1)$. For the total number of requests by all faithful men, the probability of $i$ total requests is $\binom{i-1}{f-1}/\binom{c+f}{c}$ for $i=f,\dots,c+f$. The paper derives these via a weight-enumerator (generating function) over path lengths, and observes that for $c=kf$ the single-man distribution tends to $\mathrm{Ge}(1/(k+1))$.
Load-bearing premise
The statistical analysis assumes that the assignment of mistresses to cheating men is equally likely among all possible monogamous arrangements; if the real assignments in partition-theory applications are not uniform, the derived distributions need not hold.
Editorial extensions
If this is right
- If the distributions are correct, the average request count for one faithful man grows like $c/f$ when cheating men greatly outnumber faithful men, the typical regime in partition-theory applications.
- The total number of requests has mean $f(c+f+1)/(f+1)$, so the process terminates in about this many steps with high probability.
- In the large-$f$ limit with $c=kf$, the single-man request count converges to a geometric distribution with success probability $1/(k+1)$, giving a simple asymptotic benchmark.
- The weight-enumerator approach provides a template for computing similar statistics for other involution-principle scenarios.
Reading between the lines
- The paper's random model intentionally departs from the deterministic constructions used in the actual Rogers–Ramanujan bijection; the derived distributions describe a uniform random scenario, not the structured sets in original applications, so the complexity bounds should be read as a general benchmark rather than a statement about those specific bijections.
- The same generating-function framework could be adapted to measure other features of the involution principle, such as the distribution of cycle lengths or the length of the longest chain, for which the paper does not give formulas.
- The paper's simulation procedures offer a direct empirical check; extending simulations to non-uniform assignment distributions could show how sensitive the complexity is to the structure of the original sets.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a randomized version of the Garsia-Milne involution principle. In a village with c cheating couples and f faithful couples, the assignment of each cheating man's mistress is drawn uniformly from all injections from the c cheating men to the c+f women. For this model, the authors derive the distribution of the number of requests made by one specific faithful man, P(i)=C(f+c-i, f-1)/C(c+f,c) for i=1,...,c+1, and the distribution of the total number of requests by all faithful men, P(i)=C(i-1, f-1)/C(c+f,c) for i=f,...,c+f. They give means, variances, third and fourth central moments, and show that with c=kf the single-man distribution tends to a geometric law with parameter 1/(k+1). The paper includes a Maple package and simulation procedures as empirical confirmation, and Section 5 sketches a generating-function derivation.
Significance. The distributional results are concrete and correct; they agree with direct enumeration for small parameters and with the stated large-f asymptotics. The paper provides a clean statistical description of the 'complexity' (number of requests) of the GM algorithm in a random model, with explicit hypergeometric and negative-hypergeometric formulas and limiting behavior. The Maple package and simulation code make the results reproducible and the claims falsifiable. The note is not a deep theorem paper, but it is a useful and honest experimental study. However, the analytic derivation in Section 5 is flawed as written, which affects the paper's proof of its main formulas.
major comments (1)
- [Section 5] The unnormalized weight-enumerator contains a spurious f! factor. The text states that the enumerator is the coefficient of z^c in f!/(1-z) times the product over i=c+1 to c+f of t_i/(1-z t_i), supported by the claim that 'each such assignment of path-lengths can occur in f! ways.' This is false. For c=1, f=2, the displayed expression gives coefficient [z^1] of 2x/((1-xz)(1-z)^2)=4x+2x^2; after normalization by c!f!/(c+f)!=1/3 this yields (4/3)x+(2/3)x^2, which sums to 2 and contradicts the paper's own P(1)=2/3, P(2)=1/3 from Section 3. Removing the f! gives 2x+x^2, which after the same normalization reproduces the correct probabilities. Since Section 5 is the only analytic justification of the central formulas, this is a load-bearing error that must be corrected, together with the accompanying sentence explaining the f! factor.
minor comments (5)
- [Section 1] In the quotation from George Andrews, 'theq-world' should be 'the q-world' with a space.
- [Section 1] In the same quotation, 'early 1980' should be 'early 1980s'.
- [Section 5] The notation 'ta1_{c+1}' is ambiguous; it should be written as t_{c+1}^{a_1} or with an explicit product notation over the faithful men.
- [Section 6] The example uses n=4 and k=3, but the text does not explicitly state that the number of faithful couples is f=n-k; this is clear from context but could be stated for clarity.
- [Section 2] The paper would benefit from an explicit statement that the probability model is the uniform distribution over the (c+f)!/f! possible lists [M1,...,Mc].
Circularity Check
No circularity: the hypergeometric distributions are derived by direct counting from the stated uniform random model; the Section 5 f! factor is a proof-sketch error, not a circular reduction.
full rationale
The paper's quantitative claims are the hypergeometric probabilities for request counts in a random monogamous assignment of mistresses, stated in Sections 3 and 4 and briefly justified in Section 5. The derivation starts from the explicit probability model of Section 2: the mistress assignment is a uniformly random list of c distinct entries from {1,...,c+f}. The path-length enumerators are built directly from that model, and the coefficient extractions with the stated normalization yield the claimed formulas by elementary binomial identities. The parameters c and f are free variables of the model, not fitted values, and none of the displayed distributions is imposed by normalization to match the target result. The Maple package and the simulation procedures are presented as computational and empirical confirmations, not as inputs that force the formulas, and no load-bearing conclusion rests on a self-citation: the references to Garsia-Milne, Remmel, O'Hara, Wilf, and others supply historical and motivational context only. The Section 5 display containing the extra f! factor is internally inconsistent with the given normalization, as a direct small-case check shows, and the correct enumerator omits that factor; however, this is a correctness flaw in the proof sketch, not a circular step, because correcting it does not presuppose the claimed probabilities. No specific reduction of the form 'Eq. X equals Eq. Y by construction' or 'fitted parameter renamed as prediction' was found, so the honest finding is no significant circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption The mistress assignment is a uniformly random injection: each of the (c+f)!/f! possible lists [M1,...,Mc] is equally likely.
- domain assumption The Garsia-Milne matching algorithm is well-defined and terminates: following the chain of wives and lovers always reaches a faithful woman.
- standard math The weight enumerator for path lengths is given by the coefficient of z^c in f!/(1-z) * product t_i/(1-z t_i).
Cite this review
Pith. "Pith review of Experimenting with the Garsia-Milne Involution Principle." pith.science (2026). https://pith.science/paper/NUXOR5WT
@misc{pith2026250118061,
author = {Pith},
title = {Pith review of: Experimenting with the Garsia-Milne Involution Principle},
year = {2026},
howpublished = {\url{https://pith.science/paper/NUXOR5WT}},
note = {Machine review of arXiv:2501.18061}
}
read the original 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.
Reference graph
Works this paper leans on
-
[1]
Number Theory16 (1983), 235–241
Bressoud D.M., An easy proof of the Rogers–Ramanujan identities, J. Number Theory16 (1983), 235–241
work page 1983
-
[2]
Feldman D., Propp J., Producing new bijections from old, Adv. Math.113 (1995), 1–44
work page 1995
-
[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
work page Pith review arXiv 2020
-
[4]
Garsia A.M., Milne S.C., Method for constructing bijections for classical partition identities, Proc. Nat. Acad. Sci. USA78 (1981), 2026–2028
work page 1981
-
[5]
Garsia A.M., Milne S.C., A Rogers–Ramanujan bijection, J. Combin. Theory Ser. A31 (1981), 289–339
1981
- [6]
-
[7]
Mansour T., Interview with George E. Andrews, Enumer. Comb. Appl.1 (2021), S3I12, 7 pages
work page 2021
-
[8]
O’Hara K.M., Bijections for partition identities, J. Combin. Theory Ser. A49 (1988), 13–25
work page 1988
Show all 14 references
-
[9]
Remmel J.B., Bijective proofs of some classical partition identities, J. Combin. Theory Ser. A33 (1982), 273–286
1982
-
[10]
Sills A.V., An invitation to the Rogers–Ramanujan identities, CRC Press, Boca Raton, FL, 2018
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. A34 (1983), 80–89
1983
-
[14]
Gowers, Princeton University Press, 2008, 550–561, available at http://sites.math.rutgers.edu/ ~zeilberg/mamarim/mamarimPDF/enuPCM.pdf
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
2008
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.