Combinatorial Proof of the Minimal Excludant Theorem

Cristina Ballantine; Mircea Merca

REVIEW 3 major objections 4 minor 14 references

Combinatorial Proof of the Minimal Excludant Theorem

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves the minimal-excludant theorem by an explicit staircase-profile bijection: sum of minimal excludants equals the number of two-color distinct-part partitions, with the bijection also proving r-gap generalizations and parity…

desk verdict Solid, useful partition-theory paper that delivers the requested mex bijection and an r-gap generalization, but the load-bearing staircase-profile step is asserted rather than proved in the text. read the letter →

arxiv 1908.06789 v2 pith:PEZGDMG3 submitted 2019-08-19 math.NT math.CO

Cristina Ballantine , Mircea Merca This is my paper · ORCID

classification math.NTmath.CO MSC 11A6311P8105A19

keywords minimalexcludantmexleastr-gappartitionbijectionstaircaseprofiletwo-colorpartitionstruncatedthetaseriesoverpartitions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper seeks a purely combinatorial proof of a theorem that was previously established analytically: the sum sigma_mex(n) of minimal excludants, taken over all partitions of n, equals D2(n), the number of partitions of n into distinct parts in two colors. The contribution is a direct bijection, built from a staircase-profile construction, that makes the equality visible as a matching of partitions rather than an identity of series. The same construction proves the parity criterion for sigma_mex and extends to r-gaps: sigma_r mex(n), the sum of least r-gaps, equals the number of two-color partitions whose color-0 parts are distinct multiples of r and whose color-1 parts appear at most 2r-1 times. A sympathetic reader cares because the bijection exposes a structural reason for the identity and supplies combinatorial proofs of several truncated series identities, inequalities, and convolution formulas involving sigma_mex.

What carries the argument

The central object is the staircase-profile bijection phi, adapted from a classical proof of the triple product identity: given a partition $\lambda$ and a nonnegative integer k, append a rotated staircase of height k to $\lambda$'s Ferrers diagram and draw the zig-zag staircase profile; $\alpha$ (column lengths left of the profile) and $\beta$ (row lengths right of the profile) are distinct-part partitions whose part-count difference lies between k and k+1, and coloring $\alpha$ with color k mod 2 and $\beta$ with color k+1 mod 2 produces a two-color distinct-part partition. The inverse removes the top k rows from the conjugate of the shifted diagram of the color class with more parts. This map carries the identity sigma_mex(n) = sum_{k>=0} p(n - k(k+1)/2) to the counting of D2(n), and its r-scaled version, together with the standard bounded-multiplicity bijection, proves Theorem 6.1.

What would settle it

Take any Ferrers diagram with an appended rotated staircase of height k, draw the staircase profile, and check directly that the column lengths on the left and the row lengths on the right are distinct parts satisfying k <= ell(alpha)-ell(beta) <= k+1; a diagram where a length repeats or where the declared inverse does not remove a rotated staircase invalidates the bijection. Short of that, enumerating all partitions of n for n = 0 through 30 and comparing sigma_mex(n) with D2(n) would settle Theorem 1.1 numerically.

Watch

Extended reading notes

Core claim

The paper's central claim is that the equality sigma_mex(n) = D2(n), first obtained analytically, is a bijection. For each k >= 0 and each partition lambda of n - k(k+1)/2, append the rotated Ferrers diagram of the staircase k + (k-1) + ... + 1 to the top of lambda's Ferrers diagram, run the staircase profile (a zig-zag line of alternating right and down steps) through the combined diagram, and split the boxes: the column lengths to the left of the profile form a partition alpha into distinct parts, the row lengths to the right form a partition beta into distinct parts, and k <= ell(alpha) - ell(beta) <= k+1. Coloring alpha and beta with opposite colors gives a two-color distinct-part partition of n; running the recipe backward, removing the top k rows from the conjugate of the shifted diagram of the color class with more parts, is the inverse. The same construction, applied to the parts of lambda divisible by r after dividing by r, plus the standard bounded-multiplicity bijection for the remaining parts, proves the r-gap generalization sigma_r mex(n) counts two-color partitions whose color-0 parts are distinct multiples of r and whose color-1 parts occur at most 2r-1 times.

Load-bearing premise

The construction rests on a geometric fact about the staircase profile that the text states rather than fully verifies: the column lengths on the left and the row lengths on the right always form distinct parts whose counts differ by exactly k or k+1, so the inverse recipe (removing the top k rows from the conjugate shifted diagram of the larger color class) really reverses the map.

Editorial extensions

If this is right

The equality sigma_mex(n) = D2(n) is now realized by an explicit bijection, so each partition's minimal excludant is encoded in the color-count difference of its matched two-color distinct-part partition.
The parity statement follows combinatorially from color interchange and the pentagonal number theorem: sigma_mex(n) is odd exactly when n is twice a generalized pentagonal number.
The r-gap generalization (Theorem 6.1) identifies sigma_r mex(n) with the number of two-color partitions whose color-0 parts are distinct multiples of r and whose color-1 parts occur at most 2r-1 times.
The truncated identities in Section 3 produce an infinite family of linear inequalities for sigma_mex and give the sums on the right a three-color distinct-part interpretation.
Sections 4 and 5 link sigma_mex to overpartitions and to gap-free two-color partitions, yielding convolution formulas such as sigma_mex(n) = sum_{j=0}^n pod(j) D2^*(n-j).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same staircase-profile mechanism should transfer to any partition statistic whose generating function is a sum over triangular shifts of the ordinary partition function; every identity expressible as sum_{k>=0} p(n - k(k+1)/2) is a candidate for a two-color interpretation of the same kind.
The r-gap bijection suggests a nested family of constructions: iterating the bounded-multiplicity map should interpret sums of higher-order gap statistics, such as the second least r-gap, in terms of partitions with three or more color classes with prescribed multiplicity bounds.
Because the parity proof relies only on a color-swapping involution, a parallel parity criterion is plausible for sigma_r mex(n), linking its parity to partitions into distinct parts divisible by r and their generalized pentagonal thresholds.
The combinatorial framework may also yield algorithmic dividends: the explicit inverse map gives a way to compute, from any two-color distinct-part partition, the original partition and the value of its minimal excludant without enumerating all partitions of n.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this paper does what it says: it gives a combinatorial proof of the Andrews–Newman result sigma_mex(n)=D2(n), plus a parity proof and a whole family of truncated identities. The main theorem itself is not new, but the bijection in Section 2.1 is, and it is clearly laid out in both directions with an example. The r-gap generalization in Theorem 6.1, using Glaisher's bijection, is a nice touch. The analytic proofs in Sections 3–5 are standard manipulations of known generating functions and are sound. The citation pattern is fine: the authors build on their own earlier work and on Yee, where the relevant identities already appeared.

The soft spot is exactly the one flagged in the stress test. The map phi in Section 2.1 is defined by drawing a staircase profile and then asserting that the resulting alpha and beta have distinct parts, satisfy k ≤ ell(alpha) − ell(beta) ≤ k+1, and that the specified inverse really does reverse phi. None of that is proved in the text. This is the hinge for Theorem 1.1, Proposition 3.1, and Theorem 6.1. If the authors had cited Wright's article as containing the precise geometric lemma, or had inserted a short proof, this would be fine. As written, a reader either takes the construction on faith or has to reconstruct a nontrivial argument. This is a moderate gap, not a fatal one: the result is already known through generating functions, so there is no danger of the theorem collapsing. But the paper's central claim is that it provides a purely combinatorial proof, and that proof is incomplete at the critical step.

Proposition 3.1 is similar in miniature: the proof is one sentence saying the transformation is straightforward. Given that the same staircase construction is involved, it would benefit from a few more details.

This is a careful paper by people who know the area, and I would send it to a serious referee. My recommendation: accept, but ask the authors to spell out the staircase-profile lemma or to point the reader to a self-contained reference for it. It would strengthen what is otherwise a nice contribution that partition-theory readers will find genuinely useful.

Referee Report

3 major / 4 minor

Summary. The paper provides a bijective proof of the Andrews–Newman theorem σmex(n)=D2(n), together with a combinatorial proof of the parity characterization of σmex(n), several truncated-series identities involving σmex(n), and a generalization to the sum of least r-gaps. The central construction in Section 2.1 adapts the Sylvester–Wright staircase-profile bijection: from a partition λ of n−k(k+1)/2, append a rotated staircase of height k, draw the staircase profile, and read off a two-color partition into distinct parts from the column lengths left and row lengths right of the profile. The inverse is specified by deleting k rows from the conjugate shifted diagram of the appropriate color class. Theorem 6.1 extends the construction to σr mex(n).

Significance. If the missing geometric verification is supplied, the paper answers an explicit question of Andrews and Newman with a purely combinatorial proof, and it generalizes the interpretation to a natural r-gap statistic. The paper also contains several new analytic identities and connects them to overpartition statistics and Watson-type identities. The exposition includes worked examples and the bijection is defined in both directions, which is valuable. However, the load-bearing step of the main bijection is asserted without proof, so the advertised combinatorial proof is not yet complete as written.

major comments (3)

[§2.1] The core geometric assertion after Definition 1 — that for the diagram obtained by appending the rotated staircase η(k), the column lengths α left of the staircase profile and the row lengths β right of the profile have distinct parts and satisfy k ≤ ℓ(α)−ℓ(β) ≤ k+1 — is stated without proof. The converse construction in (i)–(ii) is also asserted to produce the inverse of φ for every µ ∈ D2(n), but no verification is given. Since the theorem's bijective proof rests entirely on this staircase-profile lemma, the reader cannot currently verify that φ is a bijection from the text alone. The worked Example 2.3 illustrates one case, but it does not replace a general proof.
[§3, Proposition 3.1] The proof of Proposition 3.1 says that applying the Section 2.1 transformation 'is now straightforward' and gives no details. Because the bijectivity of that transformation is precisely the unproved geometric lemma identified above, the gap transfers to the count D3^(k)(n). The conditions in the definition of D3^(k)(n) are intricate, so the reader needs an explicit demonstration that the bijection preserves exactly those conditions.
[§6, Theorem 6.1] The bijection ξ in the proof of Theorem 6.1 is built directly on φ and φ−1 from Section 2.1. The verification that ξ and ξ−1 are inverse, and in particular that applying φ−1 to µ0/r ∪ α1/r produces a partition of t1+t2 − j(j+1)/2 for some nonnegative integer j, relies on the same unproved distinctness and length-difference properties. Thus the r-gap generalization inherits the same incompleteness.

minor comments (4)

[§2.1] In the second paragraph after Example 2.1, 'λ(1) and λ(2) are partitions into distinct parts' should presumably read 'λ(0) and λ(1)', since only two colors are used at that point.
[§5, Theorem 5.1] The convention 'D1(x) = 0 if x is not a positive integer' is inconsistent with the usual value D1(0)=1, which is needed in the coefficient extraction for n=0. Please use 'nonnegative integer' or explicitly set D1(0)=1.
[§4] The overpartition statistic M̅k is notationally very close to the partition statistic Mk used in Section 3; a distinct symbol or a clearer typographical distinction would reduce confusion.
[General] Several typos and OCR artifacts remain, including 'W orcester' in the affiliation, 'o f n' in the abstract, and nonstandard inequality symbols. A careful proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the central bijection is self-contained and external published identities are used as inputs, not as disguised conclusions.

full rationale

Theorem 1.1 is proved by an explicit bijection φ from the disjoint union of P(n−k(k+1)/2) over k≥0 to D2(n). The map is defined geometrically via staircase profiles and colorings; it does not use σ_mex(n) or the cardinality D2(n) in its definition. If the geometric lemma is valid, φ independently establishes σ_mex(n)=D2(n) after summing over k. No fitted parameter is renamed as a prediction, and no equation in the proof is identical to the target statement by construction. The paper relies on identity (1) from the authors' prior work [5] and on identity (5) from Yee [14], but these are published, parameter-free results with independent proofs; identity (1) is also attributed to Andrews–Newman [4], so the self-citation is not the sole support. The generating-function arguments in Sections 3–5 use standard manipulations of published identities and do not assume the theorem being proved. Section 6 constructs ξ explicitly from φ and Glaisher's bijection, with an inverse specified, so Theorem 6.1 is not obtained by assuming its own conclusion. The main weakness is that the key staircase-profile assertion—that α and β have distinct parts, satisfy k≤ℓ(α)−ℓ(β)≤k+1, and that the listed inverse exactly reverses φ—is stated without a full proof in the text. This is an omitted-proof or completeness concern, not a circularity, because the assertion is a geometric fact about the construction rather than an analytic equivalent of the target equality.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims introduce no fitted parameters and no new postulates; the setup uses standard partition-theoretic objects. The paper does import several published identities, two from the authors' own earlier work, as lemmas.

assumptions (6)

standard math Euler's pentagonal number theorem via Franklin's involution: q(m) is odd exactly when m is a generalized pentagonal number.
Used in Section 2.2 to determine the parity of sigma_mex(n) from the parity of q(n/2).
domain assumption Identity (1): sigma_mex(n)=sum_{k>=0} p(n-k(k+1)/2), and its r-gap generalization (12), proved combinatorially in the authors' earlier paper [5].
Invoked in Sections 2 and 6; the paper cites [5] for the combinatorial proof rather than reproducing it.
domain assumption Yee's truncated Jacobi triple product identity, stated as identity (5) in Section 3, is available with a combinatorial proof.
Used to make the proof of Theorem 1.3 combinatorial; the paper relies on [14] without restating the proof.
domain assumption Truncated theta series identities from Andrews and Merca [3, Theorems 7 and 9], including generating functions for M_k(n) and MP_k(n).
Used in the analytic proofs of Theorems 4.1 and 5.3.
standard math Standard q-series facts: (q;q)_infinity=(q;q^2)_infinity(q^2;q^2)_infinity, the pentagonal-number product, and the theta identity (q^2;q^2)_infinity/(-q;q^2)_infinity=sum_{n>=0}(-q)^{n(n+1)/2}.
Used throughout Sections 3-5 for coefficient extraction; these are classical and not proved in the paper.
standard math Glaisher's bijection between partitions with no part divisible by r and partitions with each part repeated at most r-1 times.
Used in the proof of Theorem 6.1 to move between color-1 parts and non-multiples of r.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Combinatorial Proof of the Minimal Excludant Theorem." pith.science (2026). https://pith.science/paper/PEZGDMG3

@misc{pith2026190806789,
  author       = {Pith},
  title        = {Pith review of: Combinatorial Proof of the Minimal Excludant Theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PEZGDMG3}},
  note         = {Machine review of arXiv:1908.06789}
}

abstract

The minimal excludant of a partition $\lambda$, $\rm{mex}(\lambda)$, is the smallest positive integer that is not a part of $\lambda$. For a positive integer $n$, $ \sigma\, \rm{mex}(n)$ denotes the sum of the minimal excludants of all partitions of $n$. Recently, Andrews and Newman obtained a new combinatorial interpretations for $\sigma\, \rm{mex}(n)$. They showed, using generating functions, that $\sigma\, \rm{mex}(n)$ equals the number of partitions of $n$ into distinct parts using two colors. In this paper, we provide a purely combinatorial proof of this result and new properties of the function $\sigma\, \rm{mex}(n)$. We generalize this combinatorial interpretation to $\sigma_r\, \rm{mex}(n)$, the sum of least $r$-gaps in all partitions of $n$. The least $r$-gap of a partition $\lambda$ is the smallest positive integer that does not appear at least $r$ times as a part of $\lambda$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

[1]

Andrews, The Theory of Partitions , Cambridge Math

G.E. Andrews, The Theory of Partitions , Cambridge Math. Lib., Cam- bridge University Press, Cambridge, 1998

work page 1998
[2]

Andrews, M

G.E. Andrews, M. Merca, The truncated pentagonal number th eorem, J. Combin. Theory Ser. A , 119 (2012) 1639–1643

work page 2012
[3]

Andrews, M

G.E. Andrews, M. Merca, Truncated Theta Series and a Problem o f Guo and Zeng, J. Combin. Theory Ser. A , 154 (2018) 610–619

work page 2018
[4]

Andrews, D

G.E. Andrews, D. Newman, Partitions and the minimal excludant, Ann. Comb., 23(2) (2019) 249–254

work page 2019
[5]

Ballantine, M

C. Ballantine, M. Merca, Bisected theta series, least r-gaps in partitions, and polygonal numbers Ramanujan J , 52 (2020) 433–444

work page 2020
[6]

Ballantine, M

C. Ballantine, M. Merca, On identities of Watson type, Ars Math. Con- temp., 17 (2019), no. 1, 277–290

work page 2019
[7]

Corteel, J

S. Corteel, J. Lovejoy, Overpartitions, Trans. Amer. Math. Soc., 356 (2004) 1623–1635

work page 2004
[8]

P. J. Grabner, A. Knopfmacher, Analysis of some new partition s tatistics. Ramanujan J. 12 (2006), no. 3, 439–454

work page 2006

Show all 14 references

[9]

Grundy, Mathematics and games, Eureka 2 (1939) 6–8

P.M. Grundy, Mathematics and games, Eureka 2 (1939) 6–8. Reprinted in, Eureka 27 (1964) 9–11

1939
[10]

Hirschhorn, J.A

M.D. Hirschhorn, J.A. Sellers, Arithmetic properties of partition s with odd parts distinct, Ramanujan J , 22 (2010) 273–284

2010
[11]

Sprague, ¨Uber mathematische Kampfspiele, Tohoku Math

R.P. Sprague, ¨Uber mathematische Kampfspiele, Tohoku Math. J. , 41 (193536) 438–444
[12]

Sylvester, F

J.J. Sylvester, F. Franklin, A constructive theory of partition s, arranged in three acts, an interact and an exodion, Amer. J. Math. , 5 (1882) 251–330
[13]

Wright, An enumerative proof of an identity of Jacobi, J

E.M. Wright, An enumerative proof of an identity of Jacobi, J. London Math. Soc. , 40 (1965) 55–57

1965
[14]

Yee, A truncated Jacobi triple product theorem, J

A.J. Yee, A truncated Jacobi triple product theorem, J. Combin. Theory Ser. A , 130 (2015), 1–14. 15

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Andrews, The Theory of Partitions , Cambridge Math

G.E. Andrews, The Theory of Partitions , Cambridge Math. Lib., Cam- bridge University Press, Cambridge, 1998

work page 1998

[2] [2]

Andrews, M

G.E. Andrews, M. Merca, The truncated pentagonal number th eorem, J. Combin. Theory Ser. A , 119 (2012) 1639–1643

work page 2012

[3] [3]

Andrews, M

G.E. Andrews, M. Merca, Truncated Theta Series and a Problem o f Guo and Zeng, J. Combin. Theory Ser. A , 154 (2018) 610–619

work page 2018

[4] [4]

Andrews, D

G.E. Andrews, D. Newman, Partitions and the minimal excludant, Ann. Comb., 23(2) (2019) 249–254

work page 2019

[5] [5]

Ballantine, M

C. Ballantine, M. Merca, Bisected theta series, least r-gaps in partitions, and polygonal numbers Ramanujan J , 52 (2020) 433–444

work page 2020

[6] [6]

Ballantine, M

C. Ballantine, M. Merca, On identities of Watson type, Ars Math. Con- temp., 17 (2019), no. 1, 277–290

work page 2019

[7] [7]

Corteel, J

S. Corteel, J. Lovejoy, Overpartitions, Trans. Amer. Math. Soc., 356 (2004) 1623–1635

work page 2004

[8] [8]

P. J. Grabner, A. Knopfmacher, Analysis of some new partition s tatistics. Ramanujan J. 12 (2006), no. 3, 439–454

work page 2006