Abstract
For two sets $A$ and $M$ of positive integers and for a positive integer $n$, let $p(n,A,M)$ denote the number of partitions of $n$ with parts in $A$ and multiplicities in $M$. This represents the number of ways to write $n = \sum_{a \in A} m_a a$ where $m_a \in M \cup \{0\}$ for all $a$, and only finitely many $m_a$ are non-zero. This paper demonstrates that there exist infinite sets $A$ and $M$ such that $p(n,A,M)=1$ for every positive integer $n$, settling a problem posed by Canfield and Wilf. Additionally, for sparse sets $A$ such as factorials ($k!$) or powers ($k^k$), it is shown that there exists an infinite set $M$ and constants $c$ and $n_0$ such that $0 < p(n,A,M) < n^c$ for all $n > n_0$. This result answers a question of Ljujić and Nathanson regarding the possibility of polynomial growth in restricted partitions.
Introduction
In combinatorial number theory, a partition of an integer $n$ is typically a way of expressing $n$ as a sum of positive integers. The study of restricted partitions introduces constraints on which integers can be used as parts (the set $A$) and how many times each part can be used (the set of multiplicities $M$). The function $p(n, A, M)$ counts these representations.
This paper addresses two primary challenges in this field:
- The Uniqueness Problem: Is it possible for every positive integer to have a unique representation given infinite sets $A$ and $M$?
- The Growth Problem: For very sparse sets of parts, can we find a set of multiplicities that ensures every integer is representable without the number of representations growing exponentially?
Settling the Canfield-Wilf Problem
The question of whether there exist infinite sets $A$ and $M$ such that $p(n, A, M) = 1$ for all $n \geq 1$ was a long-standing puzzle. Noga Alon provides a constructive proof of this uniqueness by leveraging the properties of binary representations.
Every positive integer has a unique representation as a sum of distinct powers of 2. Alon's approach involves partitioning the set of all non-negative integers (the exponents of 2) into two disjoint infinite sets, $I$ and $J$. By carefully constructing $A$ from powers of 2 indexed by $I$, and $M$ from sums of powers of 2 indexed by $J$, the uniqueness of the binary system is effectively "split" between the parts and their multiplicities. This ensures that the "handshake" between $A$ and $M$ for any $n$ is always unique, satisfying $p(n, A, M) = 1$.
Polynomial Growth and Sparse Sets
The second part of the paper addresses a question by Ljujić and Nathanson. They noted that if $A$ is too dense, the number of representations must grow quickly. However, they questioned the behavior when $A$ is very sparse, such as $A = \{1!, 2!, 3!, \dots\}$ or $A = \{1^1, 2^2, 3^3, \dots\}$.
Alon proves that for such sparse sets—specifically where the number of elements in $A$ up to $n$ is approximately $\frac{\log n}{\log \log n}$—there exists an infinite set $M$ such that $p(n, A, M)$ is always at least 1 but never exceeds a polynomial bound (specifically $n^{8+o(1)}$). This confirms that polynomial growth is achievable even when the available parts are rare.
Methodology: The Probabilistic Method
To prove the existence of $M$ for the growth problem, Alon utilizes the probabilistic method. Rather than constructing $M$ explicitly, he defines $M$ as a union of random subsets of specific integer intervals. To ensure this random set $M$ meets the required criteria, the paper employs two powerful probabilistic tools:
- Chernoff-Hoeffding Bounds: These are used to show that the number of representations $p(n, A, M)$ is unlikely to exceed the polynomial upper bound.
- Janson Inequality: This is used to prove that the probability of an integer $n$ having zero representations is extremely small. By showing this probability is low enough across all $n$, Alon proves that a set $M$ must exist that covers every integer.
Key Insights and Future Work
The research highlights a fascinating threshold in additive combinatorics: the point where the density of $A$ allows for a transition from exponential to polynomial growth in partition functions. While the uniqueness result is fully constructive, the growth result remains existential.
Future research may focus on:
- Constructive Multiplicities: Finding an explicit, rule-based description for $M$ in the case of factorials or powers.
- Optimization: Refining the polynomial exponent (currently $c=8$), which Alon notes was not optimized in this study.
- Density Thresholds: Pinpointing the exact density of $A$ at which polynomial growth becomes impossible.
Summary updated