🔢 mathematics

Problems in additive number theory, VII: The structure of additive $h$ -bases for $n$

This paper introduces a new class of problems concerning the structure of additive $h$ -bases for integers up to $n$ , specifically designed to be solvable by artificial intelligence.

Original authors: Melvyn B. Nathanson

Published 2026-05-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Melvyn B. Nathanson

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

The Big Picture: Building Bridges with Numbers

Imagine you have a set of special building blocks (integers). You are allowed to stack exactly $h$ of these blocks together to make a tower. The height of the tower is the sum of the numbers on the blocks.

The central question of this paper is: How high can we build a continuous, unbroken staircase of towers starting from the ground (0)?

If you can build towers of height 0, 1, 2, 3, 4, and so on, all the way up to some number $n$ , without any gaps, then your set of blocks is called an " $h$ -basis for $n$ ."

The paper introduces a new set of puzzles about these block sets. The author, Nathanson, is essentially saying: "We know how to build these staircases, but we don't fully understand the patterns of how big they can get or how the blocks need to be arranged. Here are some new riddles to solve, some of which might be tricky even for advanced AI."

The Four Main Characters (The Functions)

The paper defines four different ways to measure the "best" possible staircase you can build with a specific number of blocks ( $k$ ). Think of these as four different scoring systems for a game:

The "Ground-Up" Score ( $n_h(k)$ ):
- The Rule: You must use only positive blocks (or zero). You must start your staircase exactly at 0.
- The Goal: How high can you go without a gap?
- Analogy: You are building a ramp starting from the floor. You can't use negative numbers (digging a hole), and you can't start floating in the air.
The "Floating" Score ( $n^\sharp_h(k)$ ):
- The Rule: You must use only positive blocks (or zero), but you can start your staircase anywhere (at height 5, 100, or -50).
- The Goal: What is the longest continuous stretch of numbers you can cover, regardless of where it starts?
- Analogy: You can build a bridge anywhere in the universe, as long as you only use positive bricks.
The "Full-Range" Score ( $m_h(k)$ ):
- The Rule: You can use any integers (positive, negative, or zero). You must start at 0.
- The Goal: How high can you go without a gap?
- Analogy: You have a magic toolbox with negative numbers (like "anti-bricks" that subtract height). You must start at the floor, but you can use these special tools to extend your reach.
The "Ultimate" Score ( $m^\sharp_h(k)$ ):
- The Rule: You can use any integers, and you can start your staircase anywhere.
- The Goal: What is the absolute longest continuous stretch of numbers you can cover?
- Analogy: You have the full toolbox and total freedom to place your bridge anywhere.

The Paper's Discovery:
Nathanson proves that for the "Floating" and "Ultimate" scores (scoring systems 2 and 4), it doesn't actually matter if you allow negative numbers or not. If you can build a long bridge using negative numbers, you can rearrange your blocks to build an equally long bridge using only positive numbers. The "best" length is the same in both cases.

The "Isolated" Blocks and the "Sidon" Secret

The paper also looks at the shape of the set of numbers you create.

The Problem: Sometimes, when you add your blocks together, you get a perfect staircase (0, 1, 2, 3...), but then you get a huge gap, and then a single, lonely number (an "isolated" integer) floating far away.
The Goal: Nathanson wants to know: Can we build a staircase that is perfectly isolated? Meaning, we get a long, unbroken interval, and nothing else exists nearby except tiny sub-parts of that interval?

To solve this, he uses a concept called a Sidon Set.

The Analogy: Imagine a set of musical notes. In a normal set, you might play C+E and get a chord that sounds the same as D+F. That's confusing.
The Sidon Set: This is a set of notes where every possible combination of two notes creates a unique chord. No two pairs of notes ever add up to the same total.
The "Delta-Separated" Twist: Nathanson takes this further. He creates sets where not only are the sums unique, but they are also far apart from each other. If you add two numbers, the result is guaranteed to be a certain distance away from any other result. This "spacing" allows him to construct sets that create a perfect staircase and then immediately stop, leaving the rest of the number line empty.

The AI Challenge

The author explicitly mentions that this paper is designed to test the limits of Artificial Intelligence.

What AI can do: Solve very hard math problems (like a PhD thesis).
What AI struggles with: Deciding what is an interesting problem or inventing new categories of questions.
The Paper's Role: Nathanson is handing AI a list of new riddles (Problems 1 through 11). Some are marked with an asterisk (*) because they are likely too abstract or require a "human intuition" about what makes a pattern "beautiful" or "interesting" that current AI might miss.

Summary of the "Problems"

The paper lists about 11 specific challenges for mathematicians (and AI) to solve:

Pattern Hunting: Can you predict the exact list of all possible "staircase heights" for a given number of blocks?
Gap Analysis: How does the length of the staircase change if you add just one more block?
Negative Numbers: Does using negative numbers actually help you build a longer staircase starting from zero? (The paper suggests the answer is "No" for the maximum length, but it's a question to prove).
Sparsity: Can we build these block sets so that the numbers are very far apart (sparse) but still create a perfect staircase?
Multiple Staircases: Can we build a set of blocks that creates exactly two separate staircases and nothing else in between?

The "Caveat" (A Warning to the Reader)

At the end, Nathanson adds a "Caveat Lector" (Reader Beware). He notes that there is a lot of old, mostly forgotten literature (mostly in German) about these specific numbers. It is possible that the answers to these new riddles are already buried in old journals, waiting to be found again. He is essentially saying, "We might be reinventing the wheel, but it's a wheel worth turning."

In a Nutshell

This paper is a map of uncharted territory in the world of adding numbers. It defines the rules of the game, proves a few basic laws (like "negative numbers don't help you go further"), and then draws a treasure map pointing to 11 new X's where the gold (the solution) might be hidden. It invites both human mathematicians and AI systems to go digging.

Technical Summary: Problems in Additive Number Theory, VII: The Structure of Additive h-Bases for n

Introduction and Motivation
This paper, authored by Melvyn B. Nathanson, introduces a new class of problems in additive number theory concerning the structure of additive $h$ -bases for $n$ . The work is framed within the context of the evolving capabilities of artificial intelligence in mathematics. While AI systems have demonstrated the ability to solve complex problems suitable for Ph.D. theses, they currently lack the capacity to identify "interesting" problems or formulate new conjectures. Consequently, this paper posits that the formulation of novel, solvable questions remains a distinct advantage of human mathematicians. The problems presented are designed to be solvable by humans and, in some cases, by current AI systems applied to arithmetic.

Definitions and Framework
The paper establishes a rigorous framework based on the following definitions:

Additive $h$ -basis for $n$ : A finite set of integers $A$ is an additive $h$ -basis for $n$ if the $h$ -fold sumset $hA$ (the set of all sums of $h$ not necessarily distinct elements of $A$ ) contains the interval $[0, n]$ .
Interval $h$ -basis for $n$ : A set $A$ is an interval $h$ -basis for $n$ if $hA$ contains an interval $[c, c+n]$ for some integer $c$ .
Maximal Intervals: For a set $A$ , $\ell_h(A)$ denotes the largest $n$ such that $[0, n] \subseteq hA$ , and $\ell^\sharp_h(A)$ denotes the largest $n$ such that $[c, c+n] \subseteq hA$ for some $c$ .
Four Key Functions: The paper defines four functions based on sets of size $k$ $k$ :
1. $n_h(k)$ : The maximum $n$ such that a set $A \subseteq \mathbb{N}_0$ of size $k$ satisfies $[0, n] \subseteq hA$ .
2. $n^\sharp_h(k)$ : The maximum $n$ such that a set $A \subseteq \mathbb{N}_0$ of size $k$ satisfies $[c, c+n] \subseteq hA$ for some $c$ .
3. $m_h(k)$ : The maximum $n$ such that a set $A \subseteq \mathbb{Z}$ of size $k$ satisfies $[0, n] \subseteq hA$ .
4. $m^\sharp_h(k)$ : The maximum $n$ such that a set $A \subseteq \mathbb{Z}$ of size $k$ satisfies $[c, c+n] \subseteq hA$ for some $c$ .

Key Contributions and Results

Monotonicity of Functions:
Theorem 1 proves that the sequences $(n_h(k))$ , $(m_h(k))$ , $(n^\sharp_h(k))$ , and $(m^\sharp_h(k))$ are strictly increasing for $h, k \ge 2$ . The proof relies on the construction of a set $A'$ of size $k+1$ by adding an element to a maximal set $A$ of size $k$ , thereby extending the covered interval by at least one unit.
Generalization of Sidon Sets:
To construct specific interval bases, the paper introduces the concept of $\Delta$ -separated sets of level $H$ . A set is $\Delta$ -separated of level $\infty$ if the difference between any two distinct subset sums is at least $\Delta$ .
- Theorem 2 demonstrates that the set of powers $A(g) = \{g^i : i \in \mathbb{N}\}$ with $g = \Delta + 1$ is $\Delta$ -separated of level $\infty$ . This provides a method to construct sets with highly separated sumsets.
Construction of Interval 2-Bases:
Theorem 3 presents a constructive proof for the existence of sets $A$ of size $2n+2$ such that $2A$ contains a unique interval $[c, c+n]$ and no other intervals (except subintervals of $[c, c+n]$ ). All elements in $2A \setminus [c, c+n]$ are isolated. The construction utilizes a sequence of integers growing rapidly enough to ensure the separation of sums outside the target interval.
Equivalence of Nonnegative and Integer Bases:
Theorem 5 establishes that $n^\sharp_h(k) = m^\sharp_h(k)$ . This result indicates that allowing negative integers in the basis set does not increase the maximum length of an interval that can be covered by an $h$ -fold sumset, provided the interval can be translated. The proof involves translating a set containing negative integers to a set of nonnegative integers without altering the length of the covered interval.
Diameter Bounds:
Theorem 6 provides an upper bound on the diameter of a set $A \subseteq \mathbb{N}_0$ that achieves the maximum interval length $n_h(k)$ . Specifically, if $\ell_h(A) = n_h(k)$ , then $\text{diam}(A) \le n_h(k)$ . The proof argues that if the largest element were greater than $n_h(k)$ , it would be redundant for covering the interval $[0, n_h(k)]$ , contradicting the maximality of $n_h(k)$ .

Open Problems and Methodology
The paper does not solve the primary computational problems but rather formulates them as challenges for future research. The methodology involves:

Pattern Recognition: Listing specific values for small $h$ and $k$ (e.g., $L_{\mathbb{N}_0, h}(k)$ ) to identify hidden patterns.
Constructive Proofs: Using rapidly growing sequences (powers of integers) to isolate specific sumsets.
Translation Arguments: Utilizing the division algorithm to shift intervals and relate problems over $\mathbb{Z}$ to those over $\mathbb{N}_0$ .

The paper identifies several specific problems, many marked with an asterisk (*) to denote potential difficulty for AI:

Problem 1 & 2: Describing the sets of possible values for $\ell_h(A)$ and $\ell^\sharp_h(A)$ for fixed $h$ and $k$ .
Problem 3: Computing the sequences of the four functions and developing algorithms to decide if a given integer $w$ belongs to their ranges.
Problem 4: Analyzing the difference sequences of these functions.
Problem 5: Determining if the inclusion of negative numbers strictly increases the size of the maximal interval $[0, n]$ .
Problems 7–9: Investigating the possibility of constructing sets where the sumset contains intervals only at specific, widely spaced locations.
Problem 10: Determining the equality of the four functions (e.g., is $n_h(k) = m_h(k)$ ?).

Significance and Scope
The paper claims significance primarily in the formulation of these new questions. It acknowledges that the function $n_h(k)$ has been studied extensively in older German literature (citing authors such as Bloom, Hofmeister, and Rohrbach), and solutions may exist in historical journals. However, the paper aims to modernize the inquiry by:

Systematically defining the four related functions ( $n_h, n^\sharp_h, m_h, m^\sharp_h$ ).
Introducing the concept of $\Delta$ -separated sets to construct interval bases with specific structural properties.
Explicitly framing these problems as benchmarks for AI capabilities in mathematical discovery.

The work is modest in its claims, noting that it introduces "new questions" rather than providing definitive solutions to the asymptotic behavior of these functions. It highlights that while the counting function $n_h(k)$ has been the focus of previous research, the other counting functions and the structural properties of interval bases remain largely unstudied. The paper concludes by suggesting that analogous problems exist for other sets (squares, primes) and other configurations (arithmetic progressions), leaving a broad agenda for future investigation.