Three Questions of Erdős-Nathanson on Asymptotic Bases of Order 2

Imagine you have an infinite bag of numbers. You want to build a special "recipe book" (a set of numbers) where, if you take any two numbers from the book and add them together, you can eventually make every large number in existence. Mathematicians call this an Asymptotic Basis.

The paper you provided is about testing how "sturdy" or "robust" these recipe books are. The author, Daniel Larsen, asks three specific questions about these books:

The "Crowded" Test (Divergent Representation): If you pick a huge number, does it have many different ways to be made by adding two numbers from your book? Or does it only have one or two? A "robust" book should have many ways to make every number.
The "Split" Test (Decomposability): Can you cut your recipe book in half, throw away one half, and still be able to make every number using only the remaining half? If you can do this, your book is "decomposable." If you can't, it's "indecomposable" (meaning every single number in the book is essential).
The "Minimal" Test (Existence of a Minimal Basis): Does your book contain a "core" subset that is just barely enough to make every number? If you remove even one number from this core, the whole system breaks.

The Big Mystery

In the 1980s, two famous mathematicians, Erdős and Nathanson, discovered a rule: If your recipe book is super crowded (meaning every number can be made in lots of ways, specifically more than a certain amount related to the logarithm of the number), then two things happen automatically:

You can split the book in half and still be fine.
You can find a "minimal core" inside it.

They wondered: Is this rule true even if the book isn't that crowded? Maybe if the numbers are just "okay" crowded, these properties might act independently?

The Answer: "Yes, They Are Independent!"

Daniel Larsen's paper proves that yes, they are independent. You can mix and match these properties however you want. You can have a book that is:

Crowded but cannot be split.
Sparse but has a minimal core.
Crowded but has no minimal core.
And so on for all 8 possible combinations.

How Did He Do It? (The Construction)

To prove this, Larsen didn't just find one example; he built a universal machine (a mathematical construction) that can generate any of these 8 types of books.

Think of it like building a giant wall out of bricks, but you do it in stages (intervals of numbers that get exponentially bigger: 1 to 10, 10 to 100, 100 to 1000, etc.).

The Randomness: In each stage, he randomly decides which numbers to put in "Book A" and which to put in "Book B."
The Selection Mechanism: He uses a clever "selector" (a set of rules) to decide which numbers to keep and which to discard.
- If he wants the book to be Crowded, the selector keeps many numbers.
- If he wants the book to be Sparse, the selector keeps few numbers.
- If he wants the book to be Splitable, the selector ensures that Book A and Book B are both strong enough to stand alone.
- If he wants a Minimal Core, the selector ensures that every single number is the only way to make certain specific "critical" numbers.

The "Magic" of the Construction

The paper uses a probabilistic method (like rolling dice) to ensure that the numbers are distributed just right.

The "Critical" Numbers: Imagine there are specific "trapdoor" numbers (like $N_k$ ) that are very hard to make.
The Strategy:
- To make a book Indecomposable (cannot be split), the construction ensures that for every "trapdoor" number, there is only one specific pair of numbers that can make it. If you remove either of those two numbers, the trapdoor number can no longer be made. This forces the book to be "all or nothing."
- To make a book Decomposable, the construction ensures there are so many pairs that can make the trapdoor numbers that you can throw away half the book and still have enough pairs left over.

The "AI" Twist

The paper has a very modern, slightly humorous twist in its acknowledgments. The author admits that he used AI (specifically Claude 4.5 and Gemini 3 Pro) to help build the initial construction and ChatGPT 5.2 Pro to proofread the text. This is a rare admission in a pure math paper, highlighting how modern tools are starting to assist in deep theoretical research.

Summary in a Nutshell

The Goal: To see if "having many ways to make numbers" forces a set to be "splitable" or to have a "minimal core."
The Old Belief: If you have many ways, you must be splitable and have a core.
The New Discovery: No! You can have a set that is crowded but unsplitable, or sparse but splitable, etc. All 8 combinations are possible.
The Method: A step-by-step, randomized construction that carefully adds or removes numbers in huge intervals to force the specific properties you want, like a master chef adjusting ingredients to get the exact texture of a cake.

The paper essentially shows that the world of number sets is much more flexible and chaotic than previously thought, and that "robustness" isn't a single package deal—it's a menu of options you can pick and choose from.

Here is a detailed technical summary of the paper "Three Questions of Erdős-Nathanson on Asymptotic Bases of Order 2" by Daniel Larsen.

1. Problem Statement and Context

The paper addresses three fundamental questions regarding the robustness of asymptotic bases of order 2. A set $A \subseteq \mathbb{N}$ is an asymptotic basis of order 2 if every sufficiently large integer $n$ can be written as $n = a + a'$ with $a, a' \in A$ . The representation function $r_A(n)$ counts the number of such representations.

The author investigates the logical independence of the following three properties:

(P1) Divergent Representation Function: $r_A(n) \to \infty$ as $n \to \infty$ .
(P2) Decomposability: $A$ can be partitioned into two disjoint asymptotic bases ( $A = B \cup C$ ).
(P3) Existence of a Minimal Basis: $A$ contains a subset $B \subseteq A$ that is an asymptotic basis, but no proper subset of $B$ is an asymptotic basis.

Historical Context:
Erdős and Nathanson previously established that if the representation function grows sufficiently fast (specifically $r_A(n) > C \log n$ for a specific constant $C$ ), then both (P2) and (P3) hold. They posed questions regarding whether these implications hold for slower growth rates or generally:

Does (P1) imply (P2)? (Previously answered "No" by the author).
Does (P1) imply (P3)? (Previously answered "No" by the author).
Does (P2) imply (P3)? (The primary new result of this paper).

Main Objective:
To prove that for weaker growth rates, these three properties are mutually independent. Specifically, the paper constructs asymptotic bases satisfying all $2^3 = 8$ possible combinations of (P1), (P2), and (P3).

2. Methodology

The proof relies on a unified inductive construction defined on exponentially growing intervals. The core mechanism involves a randomized iterative process to build two disjoint sets, $B$ and $C$ , which are then combined or used separately to form the basis $A$ .

Key Construction Elements:

Intervals: The construction proceeds in stages $k$ , utilizing intervals defined by $N_k = 4^{k+1}$ .
Selection Mechanism ( $S$ ): A mechanism determines which elements to include or exclude from the sets at each stage. It takes inputs of previously constructed sets ( $B_i, C_i, G_i, H_i$ ) and outputs new sets ( $G_k, H_k$ ).
Auxiliary Functions: Two functions, $\phi(n)$ $ϕ (n)$ and $\psi(n)$ $ψ (n)$ , are defined based on the desired properties:
- $\phi(n)$ controls the density of the basis to satisfy (P1). If $\phi(n) = n$ , $r_A(n) \to \infty$ ; if $\phi(n) = 2$ or $1$, the growth is bounded.
- $\psi(n)$ controls the "eligibility" of subsets for minimal basis construction. If $\psi(n) = 1$ , minimal bases exist; if $\psi(n) = n$ , they do not.
Randomized Iteration: The sets $B_k$ $B_{k}$ and $C_k$ $C_{k}$ are constructed within the interval $(N_k, N_{k+1})$ $(N_{k}, N_{k + 1})$ using a probabilistic partition of integers into three sets $X_1, X_2, X_3$ $X_{1}, X_{2}, X_{3}$ .
- $B_k$ and $C_k$ are formed by intersecting specific unions of intervals with $X_1$ and $X_2$ respectively.
- The construction ensures that sums of elements cover the necessary integers while maintaining disjointness.

Theoretical Framework (Theorem 2):

The paper establishes a general theorem (Theorem 2) stating that if a selection mechanism $S$ satisfies specific disjointness and boundedness conditions, the resulting sets $B$ and $C$ will:

Be disjoint.
Have representation functions bounded below by a helper function $h(n) = \lfloor n \cdot 10^{-8} \rfloor$ for most integers.
Ensure that representations of specific boundary numbers ( $N_{k+1}$ ) rely on specific "forbidden" sets $F_k$ .

3. Key Contributions and Results

A. Resolution of Erdős-Nathanson Question 4

The paper proves that (P2) does not imply (P3).

Result: There exist decomposable bases ( $A = B \cup C$ ) that contain no minimal asymptotic basis.
Mechanism: By setting $\psi(n) = n$ (growing) and $\phi(n) = n$ (divergent), the construction ensures that any subbasis $D$ can have its smallest element removed while still remaining a basis. This is achieved by ensuring that for any candidate subbasis, there are "eligible" sets of elements that must be represented, and removing a single element does not destroy the ability to represent these critical sums.

B. Complete Classification of All 8 Cases

The author provides a single construction framework that, by tuning $\phi$ and $\psi$ , generates bases for all logical combinations of the three properties:

Case	(P1) Divergent?	(P2) Decomposable?	(P3) Minimal Basis Exists?	Construction Strategy
1	Yes	Yes	No	$\phi=n, \psi=n, A=B \cup C$
2	Yes	Yes	Yes	$\phi=n, \psi=1, A=B \cup C$
3	No	Yes	No	$\phi=2, \psi=n, A=B \cup C$
4	No	Yes	Yes	$\phi=2, \psi=1, A=B \cup C$
5	Yes	No	No	$\phi=n, \psi=n, A=B$ (Indecomposable)
6	Yes	No	Yes	$\phi=n, \psi=1, A=B$
7	No	No	No	$\phi=1, \psi=n, A=B$
8	No	No	Yes	$\phi=1, \psi=1, A=B$

Note: In the "Indecomposable" cases (5-8), the set $C$ is constructed but discarded, and $A$ is taken as $B$ alone.

C. Technical Lemmas

Lemma 5 & 6 (Probabilistic Bounds): These lemmas use Chernoff bounds to prove that with probability 1, the random construction yields sets with sufficiently high representation counts ( $r_A(n)$ ) in the "core" of sum intervals. This ensures the resulting sets are indeed asymptotic bases.
Lemma 4: Proves that if a subbasis $D$ is "dense enough" (removing a small number of elements doesn't destroy the basis property), then a minimal basis can be extracted or shown not to exist depending on the $\psi$ function.

4. Significance

Independence of Robustness Notions: The paper definitively settles the relationship between divergent representation, decomposability, and the existence of minimal bases. It demonstrates that high representation counts (divergence) do not guarantee structural decomposability or the existence of minimal substructures, and vice versa.
Refutation of Conjectures: It confirms that the "mysterious constant" $(\log \frac{4}{3})^{-1}$ found by Erdős and Nathanson is a sharp threshold; below this growth rate, the logical implications between the properties break down completely.
Methodological Innovation: The use of a multi-stage inductive scheme on exponentially growing intervals combined with randomized set selection (partitioning $\mathbb{N}$ into $X_1, X_2, X_3$ ) provides a powerful new tool for constructing additive number theory counterexamples.
AI Integration: The paper explicitly acknowledges the use of AI tools (Claude 4.5, Gemini 3 Pro, ChatGPT 5.2 Pro) for constructing specific counterexamples, proofreading, and generating graphics. This highlights a shift in mathematical research methodology where AI assists in the rigorous construction of complex combinatorial objects.

Conclusion

Daniel Larsen's paper resolves long-standing open questions in additive number theory by proving that the three natural properties of asymptotic bases of order 2 are logically independent. Through a sophisticated probabilistic construction, the author demonstrates that one can engineer bases with any desired combination of divergent representation, decomposability, and minimal subbases, thereby clarifying the precise conditions under which these structural properties emerge.