🔢 mathematics

Restricted partition functions and additive complements

This paper positively answers a 2016 question by Dai and Chen by constructing infinite sets of positive integers that yield a restricted partition function with polynomial growth while ensuring every positive integer has at least one representation.

Original authors: Yuchen Ding

Published 2026-06-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuchen Ding

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, infinite toolbox filled with special building blocks. Each block has a specific size, determined by a number in a list called Set A. You also have a special rulebook called Set M that tells you how many of each block you are allowed to use.

The mathematician in this paper, Yuchen Ding, is asking a very specific question: Can we design these two lists (A and M) so that we can build every positive whole number (1, 2, 3, etc.) using these blocks, but without the number of ways to build them getting out of control?

Here is a breakdown of the concepts using everyday analogies:

1. The Building Blocks (Restricted Partitions)

Think of the number $n$ (like 100) as a tower you want to build.

Set A is your list of available block sizes (e.g., 1, 4, 16, 256...).
Set M is your rulebook for "multiples." It says, "You can use 0, 1, or 2 of the 4-block, but maybe 0, 5, or 10 of the 16-block."
The Goal: You want to be able to build any number $n$ using these rules.
The Problem: If you have too many ways to build the same number, the math gets messy. The author wants to prove that the number of ways to build any tower ( $p$ ) grows slowly—specifically, "polynomial growth."

The Analogy: Imagine you are baking cookies.

If you have 100 different recipes for a chocolate chip cookie, that's a lot of work to keep track of.
"Polynomial growth" means that as you try to bake bigger and bigger batches of cookies, the number of new, unique recipes you discover doesn't explode into the millions instantly. It grows at a manageable, predictable pace.

2. The "Gap" Problem

Before this paper, mathematicians knew how to make lists where you could build every number, but the "gap" between the sizes of the blocks wasn't huge.

The Question: Can we make a list where the blocks get massively bigger very quickly? Imagine a list where the first block is size 1, the next is size 100, the next is size 10,000, and the next is size 1,000,000.
The gap between these numbers is so wide that the math usually breaks down, making it impossible to build every number or causing the number of recipes to explode.

3. The Solution: The "Perfect Pair"

Ding proves that the answer is YES. You can create these massive gaps and still build every number with a manageable number of recipes.

He does this by introducing a clever trick involving Additive Complements.

The Metaphor: Imagine two teams, Team B and Team S.
- Team B has members who are powers of 2 (1, 2, 4, 8, 16...).
- Team S is a special group of numbers that fills in the "holes" left by Team B.
- Together, if you take one person from Team B and one from Team S and add their "values" together, you can form every number on the number line. They are "complements."

Ding uses a famous result by mathematician Ruzsa to find a Team S that is just sparse enough to be interesting, but dense enough to fill the gaps.

4. How the Construction Works

Ding creates his two magic lists, A and M, based on these teams:

Set A (The Blocks): He takes the numbers from Team B and turns them into powers of 2 (e.g., $2^1, 2^2, 2^4, 2^8...$ ). This creates the "massive gaps" required by the question.
Set M (The Rules): He creates rules based on Team S. The rules allow you to combine small pieces from Team S to form the coefficients (the "how many" part).

The Magic: Because Team B and Team S are perfect complements, you can always break any number down into a sum that fits these specific rules. Because Team S is carefully chosen, the number of ways to do this doesn't explode; it stays within a "polynomial" limit (a manageable growth rate).

5. Why This Matters (According to the Paper)

This paper answers a specific question asked by Dai and Chen in 2016.

The Question: "Do there exist two infinite sets where the blocks get infinitely far apart, yet we can still build every number with a manageable number of combinations?"
The Answer: Yes. Ding constructed a specific example where the gaps between blocks grow so fast that the ratio of their logs goes to infinity, yet the system still works perfectly.

A Note on the "AI" Ingredient

The author, Yuchen Ding, openly states that he used an AI tool (ChatGPT) during the research process.

What the AI did: It suggested looking at sets involving powers of 2 and pointed him toward a specific theorem by Ruzsa about "lacunary sequences" (sequences with big gaps).
What the Author did: The author verified the math, checked the logic, reorganized the proof, and wrote the final paper. He takes full responsibility for the accuracy of the work.

Summary

Yuchen Ding solved a puzzle about number building. He showed that you can have a set of building blocks that are spaced incredibly far apart (like a ladder with rungs that get further and further apart), and a set of rules for using them, such that:

You can build every whole number.
The number of ways to build them does not get out of control.

It's like proving you can have a ladder with rungs spaced a mile apart, yet you can still climb it smoothly without falling, using a specific, manageable set of climbing techniques.

Technical Summary: Restricted Partition Functions and Additive Complements

Problem Statement
The paper addresses a specific question in additive number theory concerning restricted partition functions. Let $\mathbb{N}$ be the set of positive integers and $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ . For subsets $A, M \subseteq \mathbb{N}$ , the restricted partition function $p(n, A, M)$ counts the number of representations of an integer $n$ in the form:
$n = \sum_{a \in A} m_a a$
where $m_a \in M \cup \{0\}$ for all $a \in A$ , and only finitely many $m_a$ are nonzero. The function $p$ is said to have polynomial growth if there exist constants $c > 0$ and $n_0$ such that $p(n, A, M) \leq n^c$ for all $n \geq n_0$ .

The central problem, posed by Dai and Chen in 2016 (Question 1), asks whether there exist two infinite sets $A = \{a_n\}_{n=1}^\infty$ and $M$ of positive integers such that:

The set $A$ is extremely sparse, satisfying $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ .
$p(n, A, M) > 0$ for all sufficiently large $n$ (i.e., every large integer is representable).
The partition function $p(n, A, M)$ exhibits polynomial growth.

Previous work by Alon (2012) and Dai and Chen (2016) had established the existence of such sets with polynomial growth under less stringent sparsity conditions or with specific exponent bounds (e.g., $p(n) < n^{2+o(1)}$ ), but the case of super-logarithmic sparsity remained open.

Methodology
The author, Yuchen Ding, employs a construction based on additive complements and binary expansions. The core strategy involves:

Defining Additive Complements: Two sets $B, S \subseteq \mathbb{N}_0$ are called complete additive complements if $B + S = \mathbb{N}_0$ .
Constructing Sets $A$ and $M$ : The paper constructs $A$ $A$ and $M$ $M$ based on a pair of additive complements $B$ $B$ and $S$ $S$ satisfying a specific counting condition. Specifically:
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ (finite subset sums of powers of 2 from $S$ ).
Injective Mapping: The proof establishes an injective map from the representations of $n$ counted by $p(n, A, M)$ to finite subsets of the product space $S \times B$ . By utilizing the uniqueness of binary expansions, the author shows that any representation of $n$ corresponds to a set of pairs $(s, b)$ such that $s+b \leq \log_2 n$ .
Bounding the Growth: The number of such representations is bounded by the number of pairs $(s, b) \in S \times B$ with $s+b \leq N$ (where $N \approx \log_2 n$ ). This count is shown to be bounded by $S(N)B(N)$ . If $B(x)S(x) \ll x$ , the resulting partition function grows polynomially.

Key Contributions and Results
The paper provides an affirmative answer to Question 1 of Dai and Chen through the following results:

Theorem 1: Let $B$ and $S$ be complete additive complements satisfying the counting condition $B(x)S(x) \ll x$ . If $A$ and $M$ are defined as above, then $p(n, A, M) > 0$ for every $n \in \mathbb{N}$ and $p(n, A, M)$ has polynomial growth.
Corollary 1 (Resolution of Question 1): By invoking a result of Ruzsa (1972) regarding additive complements of powers of two, the author constructs specific sets $A$ $A$ and $M$ $M$ that satisfy the conditions of Theorem 1.
- Let $B = \{0\} \cup \{2^k : k \geq 0\}$ .
- Let $S$ be a subset of $\mathbb{N}$ derived from Ruzsa's theorem such that $S(x) \ll x / \log x$ and $B+S = \mathbb{N}_0$ (after adding finitely many elements).
- The resulting set $A$ has elements $a_n = 2^{2^{n-2}}$ for $n \geq 2$ .
- This construction yields $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ , satisfying the extreme sparsity requirement.
- Since $B(x) \ll \log x$ and $S(x) \ll x / \log x$ , the product $B(x)S(x) \ll x$ holds, ensuring polynomial growth of $p(n, A, M)$ .

Significance
The paper claims to answer a 2016 question of Dai and Chen in the affirmative. It demonstrates that it is possible to construct restricted partition functions that are surjective (represent all positive integers) and have polynomial growth, even when the set of allowed parts $A$ is significantly sparser than previously known examples (specifically, satisfying a limit condition where the logarithmic gap between consecutive elements grows faster than any power of $\log n$ ).

The work generalizes previous results by linking the growth rate of restricted partition functions directly to the counting properties of additive complements. The author notes that the construction was initially explored with the assistance of generative AI (ChatGPT), which suggested the specific form of the sets and the connection to Ruzsa's theorem, though the mathematical verification, reorganization, and final proof are the author's independent work.