Restricted Integer Partition Functions

Noga Alon

TL;DR

Noga Alon settles a long-standing combinatorial puzzle by proving that there exist two infinite sets—one for "parts" and one for "multiplicities"—that allow every single positive integer to be represented as a unique partition. Furthermore, for very sparse sets of parts (like factorials), he uses the probabilistic method to show that a set of multiplicities exists that keeps the number of possible partitions growing only polynomially, rather than exponentially.

What Problem Does This Paper Address?

In number theory, a partition of an integer $n$ is a way of writing it as a sum of positive integers. Usually, we don't care how many times a number is used. However, this paper looks at restricted partitions.

Imagine you have a set of allowed "coin denominations" $A$ and a set of allowed "counts" $M$. For any integer $n$, we want to know how many ways we can form $n$ using parts from $A$, where the number of times we use each part must be an element of $M$ (or zero). This count is denoted as $p(n, A, M)$.

Two main questions were open:

  1. The Uniqueness Question: Can we find infinite sets $A$ and $M$ such that every integer $n$ has exactly one representation? (Proposed by Canfield and Wilf).
  2. The Growth Question: If $A$ is very sparse (like $A = \{1!, 2!, 3!, \dots\}$), can we find an infinite set $M$ such that every large $n$ can be represented, but the number of ways to do so doesn't explode? Specifically, can the number of representations be bounded by a polynomial $n^c$? (Proposed by Ljujić and Nathanson).

Methods

Alon employs two distinct mathematical toolkits to solve these:

  • Explicit Construction (for Uniqueness): To prove $p(n, A, M) = 1$, Alon leverages the properties of binary representations. He partitions the set of all non-negative integers (the exponents of 2) into two disjoint infinite sets. By carefully defining $A$ and $M$ based on these sets, he ensures that the uniqueness of binary representation "lifts" to the uniqueness of the partition.
  • The Probabilistic Method (for Growth): To tackle the growth questions, Alon doesn't construct $M$ by hand. Instead, he defines $M$ as a union of random subsets. He then uses sophisticated tools from probability—specifically Chernoff-Hoeffding bounds and the Janson Inequality—to prove that with high probability, this random set $M$ satisfies both conditions: it's "thick" enough to represent every $n$, but "thin" enough to keep the total number of representations polynomial.

Datasets

As a theoretical paper in combinatorics and number theory, no external datasets were used. The "data" consists of the properties of infinite sequences of integers (like factorials $k!$ and powers $k^k$).

Key Insights and Ideas

  • Binary Splitting: The most elegant insight is that any integer can be viewed as a unique sum of powers of 2. By splitting the "available" powers of 2 between the parts $A$ and the multiplicities $M$, you can force a unique "handshake" between the two sets for every integer $n$.
  • Sparsity vs. Growth: Ljujić and Nathanson previously showed that if $A$ is too dense (having more than $\delta \log n$ members), polynomial growth is impossible. Alon shows that if $A$ is sparse enough (specifically $|A \cap [n]| \approx \frac{\log n}{\log \log n}$), then polynomial growth is indeed achievable.
  • The Power of Randomness: The paper demonstrates that even in rigid number-theoretic structures, "random" sets of multiplicities are surprisingly efficient at covering all integers without creating too much redundancy.

Key Results

  • Theorem 1.1: There exist infinite sets $A$ and $M$ such that $p(n, A, M) = 1$ for every $n \geq 1$. This is the strongest possible answer to the Canfield-Wilf problem.
  • Theorem 1.2: For any infinite set $A$ that is sufficiently sparse (like factorials $k!$ or $k^k$), there exists an infinite set $M$ such that $0 < p(n, A, M) < n^{8+o(1)}$. This confirms that we can achieve "polynomial growth" even when the parts are very rare.

Limitations and Future Work

  • Density Bounds: The paper establishes a threshold for the density of $A$ where polynomial growth is possible. However, the exact "tipping point" for the density of $A$ remains an area for refinement.
  • Non-Constructive Multiplicities: While the uniqueness result is constructive, the polynomial growth result is existential (probabilistic). We know such a set $M$ exists for factorials, but we don't have a simple, "rule-based" description of it.
  • Optimization: Alon notes that the exponent in the polynomial bound ($n^8$) was not optimized and could likely be improved in future studies.

Summary updated

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$, that is, the number of representations of $n$ in the form $n=\sum_{a \in A} m_a a$ where $m_a \in M \cup {0}$ for all $a$, and all numbers $m_a$ but finitely many are 0. It is shown that there are infinite sets $A$ and $M$ so that $p(n,A,M)=1$ for every positive integer $n$. This settles (in a strong form) a problem of Canfield and Wilf. It is also shown that there is an infinite set $M$ and constants $c$ and $n_0$ so that for $A={k!}_{k \geq 1}$ or for $A=\{k^k\}_{k \geq 1}$, $0n_0$. This answers a question of Ljujić and Nathanson.
BibTeX
@article{alon2013restricted,
  author = {Noga Alon},
  title = {{Restricted Integer Partition Functions}},
  journal = {Integers},
  year = {2013},
}

Loading related content...

Figure