On the number of missing integers in partitions

1. Problem Statement and Motivation

The paper investigates a specific partition statistic: the number of missing integers in a partition.

• Definition: A "missing integer" in a partition $\pi$ of $n$ is defined as a positive integer $k$ such that $k < \ell(\pi)$ (where $\ell(\pi)$ is the largest part) and $k$ does not appear as a part in $\pi$.
• Context: This concept is closely related to the Minimal Excludant (mex), defined as the smallest positive integer missing from a partition. While the mex has been extensively studied recently (by Andrews, Newman, and others), this paper shifts focus to the entire set of missing integers rather than just the smallest one.
• Scope: The authors analyze this statistic in two distinct classes:
  1. Unrestricted Partitions: Standard integer partitions.
  2. Overpartitions: Partitions where the first occurrence of any integer may be overlined.
• Goal: To derive generating functions for the number of partitions with exactly $m$ missing integers, establish congruence relations, and propose bias-type inequalities regarding the parity of the count of missing integers.

2. Methodology

The authors primarily employ $q$-series techniques and generating functions. Key mathematical tools include:

• $q$-Pochhammer Symbol: $(a; q)_n$ and $(a; q)_\infty$.
• $q$-Binomial Theorem: Used to sum series tails and derive closed forms.
• Jacobi Triple Product Identity: Crucial for establishing congruences modulo 3 and 4.
• Euler's Partition Identity: Relating products of distinct parts to unrestricted partitions.
• Differentiation: Used to extract coefficients corresponding to specific counts (e.g., partitions with exactly one missing integer) from generating functions.
• Combinatorial Interpretation: The authors provide bijective arguments linking the algebraic results to specific partition structures (e.g., partitions with repeated parts).

3. Key Contributions and Results

A. Unrestricted Partitions

Generating Functions:

• Theorem 2.1: The authors derive a general generating function for $P_j(n, m)$, the number of partitions of $n$ with exactly $m$ missing integers $\ge j$.
  $$\sum_{n=1}^\infty \sum_{m=0}^\infty P_j(n, m) w^m q^n = \frac{w^{-j}}{( \frac{w-1}{w}; q)_j} \left( \frac{((w-1)q; q)_\infty}{(wq; q)_\infty} - \sum_{\ell=0}^{j-1} \frac{(\frac{w-1}{w}; q)_\ell}{(q; q)_\ell} (wq)^\ell \right)$$
• Corollary 2.2: For $j=1$ (all missing integers), the generating function simplifies to:
  $$\sum_{n=0}^\infty \sum_{m=0}^\infty P(n, m) w^m q^n = \frac{((w-1)q; q)_\infty}{(wq; q)_\infty}$$
• Special Cases:
  • Setting $w=0$ yields the generating function for gap-free partitions (partitions with no missing integers), recovering the known identity $\sum P^*(n)q^n = (-q; q)_\infty$.
  • Setting $w=1$ recovers the standard partition generating function $1/(q; q)_\infty$.
  • Differentiating with respect to $w$ at $w=0$ yields the generating function for partitions with exactly one missing integer ($P(n, 1)$). This is shown to be equinumerous with partitions where exactly one part repeats twice and all others are distinct.

Parity and Congruences:

• The authors define $Me(n)$ (partitions with an even number of missing integers) and $Mo(n)$ (partitions with an odd number).
• Corollary 2.5: The generating function for the difference $Me(n) - Mo(n)$ is:
  $$\sum_{n=0}^\infty (Me(n) - Mo(n)) q^n = \frac{(-2q; q)_\infty}{(-q; q)_\infty}$$
• Theorem 2.6 (Congruence Modulo 3):
  $$Me(n) - Mo(n) \equiv \begin{cases} 0 \pmod 3 & \text{if } n \text{ is not a square} \\ 1 \pmod 3 & \text{if } n \text{ is an odd square} \\ 2 \pmod 3 & \text{if } n \text{ is an even square} \end{cases}$$
  This result is derived using the Jacobi Triple Product identity.

Generalized Statistic (Multiplicity):

• Theorem 2.9: The authors extend the concept to count distinct integers less than the largest part that appear with multiplicity less than $k$. They prove that the total count of such integers across all partitions of $n$ equals the total number of parts different from $k$ in all partitions of $n$.

Conjectures:

• Conjecture 2.7: For $n > 34$, $Me(n) > Mo(n)$. This suggests a "bias" where partitions with an even number of missing integers are more frequent.
• Conjecture 2.8: For $n > 10$, $Me(n) - Mo(n) < q(n)$, where $q(n)$ is the number of partitions into distinct parts.

B. Overpartitions

The paper extends the analysis to overpartitions (where the first occurrence of a part can be overlined).

Generating Functions:

• Theorem 3.1 & Corollary 3.2: Analogous generating functions are derived for overpartitions. For $j=1$:
  $$\sum_{n=0}^\infty \sum_{m=0}^\infty P(n, m) w^m q^n = \frac{((w-2)q; q)_\infty}{(wq; q)_\infty}$$
• Corollary 3.3: The generating function for gap-free overpartitions is $(-2q; q)_\infty$, which corresponds to overpartitions into distinct parts.

Parity and Congruences:

• Corollary 3.5: The generating function for the difference in overpartitions is:
  $$\sum_{n=0}^\infty (Me(n) - Mo(n)) q^n = \frac{(-3q; q)_\infty}{(-q; q)_\infty}$$
• Theorem 3.7 (Congruence Modulo 4):
  $$Me(n) - Mo(n) \equiv \begin{cases} 0 \pmod 4 & \text{if } n \text{ is not a square} \\ 2 \pmod 4 & \text{if } n \text{ is a square} \end{cases}$$
  The authors note that $Me(n) - Mo(n)$ is always even because the total number of overpartitions is even.

Conjectures:

• Conjecture 3.6: For $n > 27$, $Me(n) > Mo(n)$ for overpartitions, mirroring the bias found in unrestricted partitions.

4. Significance and Future Directions

• New Statistics: The paper formalizes the study of the count of missing integers, moving beyond the minimal excludant (mex) to a broader structural analysis of partitions.
• Combinatorial Connections: It establishes surprising bijections, such as the link between partitions with exactly one missing integer and partitions with exactly one repeated part.
• Congruence Theory: The derivation of congruences modulo 3 and 4 for the parity difference of missing integers adds to the body of partition congruence results, utilizing deep $q$-series identities.
• Open Problems: The authors highlight several open questions:
  • Finding bijective proofs for the derived identities (e.g., Theorem 2.9).
  • Investigating congruences for other moduli.
  • Deriving asymptotic and Hardy-Ramanujan-Rademacher type exact formulas for the sequences $Me(n) - Mo(n)$.
  • Extending the multiplicity results (Theorem 2.9) to overpartitions.

In summary, this paper provides a rigorous analytic framework for understanding the distribution of missing integers in partitions, uncovering deep connections between partition statistics, $q$-series, and number-theoretic congruences.