RESTRICTED INTEGER PARTITION FUNCTIONS

Noga Alon

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:

  1. The Uniqueness Problem: Is it possible for every positive integer to have a unique representation given infinite sets $A$ and $M$?
  2. 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

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},
}
Figure