Positivity and negativity for h-bases for n
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Positivity and negativity for h-bases for n".
Emmy: Here's the gist of the paper. A set A of integers is an h-basis for n if every integer in
0, n: belongs to the sumset hA, that is, can be represented as the sum of exactly h not necessarily distinct elements of A<ref:2610.19470#pg2>.
Ada: The paper investigates the comparison between extremal functions for bases of order h for n and those allowing negative elements, providing new proofs for these results<ref:2610.19470#pg6>.
Emmy: Extremal Functions for Bases of Order h The paper defines an h-basis as a set A where
0, n: ⊆ hA<ref:2610.19470#pg2>.
Ada: For a set of nonnegative integers, the classical postage stamp problem seeks the largest integer nh(k) such that
0, nh(k): ⊆ hA for some set A of size k + 1<ref:2610.19470#pg3>.
Paper summary: Ada: So we're looking at this paper titled "Positivity and negativity for h-bases for n". It's about comparing the classical postage stamp problem, which deals with sets of non-negative integers, against a version that allows negative numbers.
Emmy: Exactly. The main thrust here is to look at how these extremal functions behave when you start allowing negative elements in the set A. The paper claims some specific comparisons between n h(k) and n h(k).
Kolya: What does that actually mean for us? It seems like they are looking at the boundary of what's possible when we introduce a single negative number into the set. I'm curious if this changes the fundamental structure of how these bases work.
Ada: Well, it claims that for k equals two, which is what we usually think about, there are specific conditions on h, the order of our basis, that determine whether the maximum size you can reach stays the same or if it gets smaller when you allow negative numbers.
Emmy: Specifically, they state that n h(two) is smaller than n h(two) if h is odd or if h equals four <ref:2610.19470#pg1,2)$ if $h$ is odd or>. But they find that for even values of h that are not four, the largest integer you can reach stays exactly the same.
Kolya: That's interesting because it suggests a very stable behavior for bases when you move from just non-negative integers to allowing negatives, as long as h is even and not four. What does this stability imply about the underlying algebraic structure of these sumsets?
Ada: It implies that for those specific cases, the ability to represent all integers up to a certain point doesn't fundamentally change when you have that one negative number in the set. However, they also provide proofs for these comparisons, which is new work.
Emmy: And they do this using a formal reasoning agent called Aristotle from Harmonic, and it seems those proofs are quite solid because they were verified in Lean. That gives us confidence in the comparison itself.
Kolya: I'm interested in the computational aspects mentioned later. They talk about computing n h(two) for different types of h, like when h is congruent to two modulo four, or when it's even and greater than eight and divisible by four <ref:2610.19470#pg1>.
Ada: Yes, they do give specific results for certain conditions. For instance, if the order h is congruent to two modulo four, then the largest integer you can reach with a negative element set is actually equal to the largest integer you can reach without one.
Emmy: And they tackle the case of h being odd by showing that if n h(two) equals n h(two), there must exist a set A of three integers where one of them is negative <ref:2610.19470#pg1>. That leads to some specific relationships involving variables like m and U.
Kolya: I see the connection they're making between the equality case and the structure of that set A having a negative element. It feels like they are saying that if you achieve the same bound, you *must* have a specific kind of structure involving negatives in your set A.
Ada: They then go on to discuss how this relates to other cases, like when h is even and greater than eight and divisible by four, where they show the equality holds again. It's a lot of conditions leading to the same result.
Emmy: The structure behind these results seems very intricate because they have to handle both the odd and even cases separately with different tools, but it all points back to how those sumsets grow.
Kolya: So, if you are just listening for what this means for additive number theory in general, it suggests that adding one negative element doesn't always hurt the reach of the set when h is even and not four. It just depends on the exact value of h.
Ada: That's the practical implication. It shows that for many orders, you can have a very predictable structure regarding how far out you can reach, even with a little bit of negativity allowed in your set A.
Emmy: We're looking at this paper "Positivity and negativity for h-bases for n" and its authors Van Doorn, Monticone, and Nathanson. They are tackling the comparison between classical bases and those that include negative integers.
Kolya: The main point is that the behavior of these extremal functions depends heavily on whether h is odd or even, which dictates whether the largest reachable integer stays the same or gets smaller when you allow a negative element in your set A.
Ada: It means for even h not equal to four, you maintain the same maximum reach, but for odd h or if h is four, that reach tends to decrease when negatives are introduced.
Emmy: The paper uses new proofs from Aristotle in Lean to confirm these results. This gives us a strong foundation for understanding these comparisons between the sets of non-negative and general integer bases.
Conclusion: Ada: So we’ve seen how this paper by Van Doorn, Monticone, and Nathanson looks at bases for n when you start allowing negative numbers.
Emmy: They’re basically comparing the standard non-negative problem to one where you can have negatives in your set A. It boils down to whether the maximum reach stays the same or shrinks depending on what h is.
Kolya: So, if we put it simply, for most cases, adding a negative number doesn't hurt how far you can go with the sumset. But there are specific conditions on h where that reach gets smaller.
Ada: Exactly. The title of this paper tells you right away that they’re looking at both positivity and negativity in these bases and what happens when you mix them up.
Emmy: It suggests a pretty stable structure for these sets A when h is even and not equal to four, meaning the maximum sumset size doesn't change much if you introduce a negative element.
Kolya: And it highlights that for odd h or when h equals four, the situation changes significantly because adding that one negative number can actually reduce the maximum integer you can represent.
Ada: The real implication here is understanding the boundary conditions for these additive bases and how sensitive they are to small changes in their elements.
Emmy: It gives us a clearer picture of the algebraic geometry behind these problems, showing exactly when we see those structural differences between positive and general bases.
Kolya: It’s interesting because it shows that even with negatives allowed, there are still very specific mathematical rules governing these bounds for the order h.
Ada: And that leads us to thinking about what else we can discover about these bases when we look at bigger orders or more complex sets A.
math.CO, math.NT
Submitted: 2026-10-14
Updated: 2026-11-08
Comments: 10 pages
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 87/100
The gist: A set A of integers is an h-basis for n if every integer in [0, n] belongs to the sumset hA, that is, can be represented as the sum of exactly h not necessarily distinct elements of…
Key concepts
- h-basis
- A set A of integers is an h-basis for n if every integer from 0 to n can be written as a sum of exactly h elements from A, where repetition is allowed. This concept extends the idea of a basis to sums involving multiple copies of the same elements.
- nh(k)
- This function represents the largest integer such that every number in [0, nh(k)] can be formed by summing exactly k elements from an h-basis. It is related to classical problems like the postage stamp problem for nonnegative integers.
- n_♭ h(k)
- This function considers bases that are allowed to contain negative integers. It is compared against nh(k) to see how the presence of negative numbers affects the maximum range [0, n] that can be covered by sums of h elements.
Summary
A set A of integers is an h-basis for n if every integer in [0, n] belongs to the sumset hA, that is, can be represented as the sum of exactly h not necessarily distinct elements of A<ref:2610. p. 0 A set A of integers is an h-basis for n if every integer in [0, n] = {0, 1, 2, . , n} belongs
to the sumset hA, that is, can be represented as the sum of exactly h not necessarily distinct
elements of A. In this paper we give new proofs of these results. Extremal functions for bases of order h for n
Let N0 = {0, 1, 2, 3, .Where the paper says it
Where the paper says it
Extremal Functions for Bases of Order h
The paper defines an h-basis as a set A where [0, n] ⊆ hA<ref:2610.19470#pg2>. For a set of nonnegative integers, the classical postage stamp problem seeks the largest integer nh(k) such that [0, nh(k)] ⊆ hA for some set A of size k + 1<ref:2610. p. 0 , n} belongs
to the sumset hA, that is, can be represented as the sum of exactly h not necessarily distinct
elements of A. The classical postage stamp problem asks for the largest integer nh(k) such that
[0, nh(k)] ⊆ hA for some set A of nonnegative integers of size k + 1.Where the paper says it
0, 1, c
for some integer c > 1<ref:2610.19470#pg4>. Theorem 3.1 provides a new proof of Stöhr’s formula for nh(2), stating that nh(2) = h squared + 6h + 1 /4
<ref:2610.19470#pg6>.
Positivity and Negativity Comparison
The paper compares the extremal function n h(k) with nh(k)<ref:2610.19470#pg3>. Aristotle showed that for k = 2, n h(2) < nh(2) if h is odd or h = 4, and that n h(2) = nh(2) if h is even and h! p. 1 The AI system Aristotle [1] answered a “negativity” question for k = 2, that is, for sets A = {a, b, c}
with a < b < c and a < 0. Aristotle showed that n
♭
h
(2) < nh(2) for all odd h and for h = 4, and
that n
♭
h
(2) = nh(2) for all even h ̸= 4. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610. Proofs of these comparison results
were autonomously discovered and formally verified in Lean by Aristotle, a formal reasoning agent
developed by Harmonic. In this paper we give new proofs of these results.Where the paper says it
Where the paper says it
Where the paper says it
Computing n h(2)
Theorem 3.3 states that if h ≡ 2 (mod 4), then n h(2) = nh(2)<ref:2610. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610. This completes the proof. Computing n
♭
h
(2) for odd h
Theorem 4. Then
tn1 < tn2
and
h + 1 ≥ n2 − n1 = (tn2 − tn1
) y ≥ y. This proves (2.Where the paper says it
Where the paper says it
Where the paper says it
Computing n h(k) for Even and Odd h
Theorem 3.4 shows that if h ≥ 8 and h ≡ 0 (mod 4), then n h(2) = nh(2)<ref:2610. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610. There are 3
5
2
= 30 sets A = {a, a + x, a + y} that satisfy these conditions. Computer calculation
(using Maple) shows that n4(A) ≤ 8 for each of these 30 sets and that n4(A) = 8 for the five sets
listed in the statement of Theorem 3.Where the paper says it
Where the paper says it
Computing n h(k) for Odd h
The proof for Theorem 4.1 demonstrates that if n h(2) = nh(2), then there must exist a set A = Then sn + tn ≤ h and
n = rna + snb + tnc
= (rn + sn + tn)a + sn(b − a) + tn(c − a)
= ha + snx + tny. Thus, n ∈ hA implies (2.a, b, c
with a **. This leads to the conclusion that y = m + 2 and ha = U = (y − 1)(1 − x). This implies n h(2). p. 2Where the paper says it
AI Usage
The first proofs of the comparison results for the extremal functions nh(2) and n h(2) were autonomously discovered and formally verified in Lean by Aristotle, a formal reasoning agent developed by Harmonic<ref:2610.19470#pg6>. MBN studied Aristotle’s arguments and used its conversational interface to clarify the reasoning<ref:2610. p. 0 For k = 2, we have n
♭
h(2) < nh(2)
if h is odd or h = 4 and n
♭
h(2) = nh(2) if h is even and h ̸= 4. Proofs of these comparison results
were autonomously discovered and formally verified in Lean by Aristotle, a formal reasoning agent
developed by Harmonic.Where the paper says it
References
[1] T. Achim et al., Aristotle: IMO-level Automated Theorem Proving, arXiv preprint arXiv:2510. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
[2] M. B. Nathanson, Problems in additive number theory, VII: The structure of additive h-bases for n, arXiv preprint arXiv:2605. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
[3] H. Rohrbach, Ein Beitrag zur additiven Zahlentheorie, Math. p. 0 1
arXiv:2610. 19470v1 [math. 2 VAN DOORN, MONTICONE, AND NATHANSON
If A is a set of nonnegative integers, then nh(A) ≥ 0 if and only if 0 ∈ A and nh(A) ≥ 1 if and
only if 0, 1 ∈ A if and only if nh(A) ≥ h. The classical postage stamp problem for sets of nonnegative
integers (introduced by Hans Rohrbach [3, 4] in 1937) is to compute the extremal function
nh(k) = max (
nh(A) : A ∈
N0
k + 1! h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
Where the paper says it
[4] H. Rohrbach, Einige neuere Untersuchungen über die Dichte in der additiven Zahlentheorie, Jb. p. 1 2 VAN DOORN, MONTICONE, AND NATHANSON
If A is a set of nonnegative integers, then nh(A) ≥ 0 if and only if 0 ∈ A and nh(A) ≥ 1 if and
only if 0, 1 ∈ A if and only if nh(A) ≥ h. The classical postage stamp problem for sets of nonnegative
integers (introduced by Hans Rohrbach [3, 4] in 1937) is to compute the extremal function
nh(k) = max (
nh(A) : A ∈
N0
k + 1! 1
arXiv:2610. 19470v1 [math. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
Where the paper says it
[5] A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe. p. 1 If A
is an extremal basis for nh(2), then A = {0, 1, c} for some integer c > 1. Alfred Stöhr [5] solved the postage stamp problem for k = 2 in 1955. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
[6] Groningen, The Netherlands<ref:2610. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
[7] Email address: wonterman1@hotmail.com<ref:2610. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
[8] Harmonic, London, UK<ref:2610. p. 0 For k = 2, we have n
♭
h(2) < nh(2)
if h is odd or h = 4 and n
♭
h(2) = nh(2) if h is even and h ̸= 4. Proofs of these comparison results
were autonomously discovered and formally verified in Lean by Aristotle, a formal reasoning agent
developed by Harmonic.Where the paper says it
[9] Email address: pietro. p. 0 POSITIVITY AND NEGATIVITY FOR h-BASES FOR n
WOUTER VAN DOORN, PIETRO MONTICONE, AND MELVYN B. NATHANSON
Abstract. For k = 2, we have n
♭
h(2) < nh(2)
if h is odd or h = 4 and n
♭
h(2) = nh(2) if h is even and h ̸= 4. Proofs of these comparison results
were autonomously discovered and formally verified in Lean by Aristotle, a formal reasoning agent
developed by Harmonic. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
Where the paper says it
[10] Lehman College (CUNY), Bronx, NY 10468<ref:2610. p. 0 h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
[Email address: melvyn. p. 0 POSITIVITY AND NEGATIVITY FOR h-BASES FOR n
WOUTER VAN DOORN, PIETRO MONTICONE, AND MELVYN B. NATHANSON
Abstract. POSITIVITY AND NEGATIVITY FOR h-BASES FOR n
WOUTER VAN DOORN, PIETRO MONTICONE, AND MELVYN B. NATHANSON
Abstract. h-bases for n, sumsets, postage stamp problem, additive number theory, combinatorial
number theory, AI proofs. 1
arXiv:2610.Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
AI can formally verify original proofs by using Aristotle, a formal reasoning agent developed by Harmonic, to ensure mathematical correctness for complex results like
new proofs of these comparison results.
-
The AI system can be used to compute extremal functions such as nh(k) and nh(k), including finding the
largest integer nh(A) such that A is a basis of order h for n,
by leveraging the lemmas provided. -
The system can perform comparisons between classical additive number theory problems, like the postage stamp problem for sets of nonnegative integers, and its extensions involving negative elements to determine if "nh(2) < nh(2) if h is odd or h = 4."
-
AI can construct extremal bases for bases of order h for n, such as finding the sets A that achieve the maximum value nh(A), by employing techniques derived from Lemma 2.3 and Theorem 3.1.
-
The system can execute complex proofs involving modular arithmetic and number theory constraints, as seen in the proof of Theorem 4.1, to establish strict inequalities like "n h(2) = 3.
Abstract
A set A of integers is an h-basis for n if every integer in [0,n] = 0,1,2,,n belongs to the sumset hA, that is, can be represented as the sum of exactly h not necessarily distinct elements of A. The classical postage stamp problem asks for the largest integer n h(k) such that [0,n h(k)] hA for some set A of nonnegative integers of size k+1. We consider the effect of allowing negative elements. Let n h(k) be the largest integer such that [0,n h(k)] hA for some set A of integers of size k+1 containing at least one negative integer. For k=2, we have n h(2) < n h(2) if h is odd or h=4 and n h(2) = n h(2) if h is even and h not equal to 4. Proofs of these comparison results were autonomously discovered and formally verified in Lean by https://aristotle.harmonic.fun/ Aristotle, a formal reasoning agent developed by https://www.harmonic.fun/ Harmonic. In this paper we give new proofs of these results.
Sources
- Aristotle: IMO-level Automated Theorem Proving
- Problems in additive number theory, VII: The structure of additive $h$-bases for $n$
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality