Positivity and negativity for h-bases for n
summary
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…
In short
The paper compares extremal functions for h-bases of order n, denoted nh(k), with those allowing negative elements, n_♭ h(k). It investigates when these two functions are equal or different based on whether the order h is even or odd, providing new proofs for these comparisons.
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.
Terminology used across episodes
This episode discusses
- Positivity and negativity for h-bases for n · Paper Radio
- Aristotle: IMO-level Automated Theorem Proving
- Problems in additive number theory, VII: The structure of additive h-bases for n
The paper
Positivity and negativity for h-bases for n · Read on arXiv
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.
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.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors