#338 at positive density: under the Erdős–Graham hypothesis, a set of lower density δ ≤ 1/2 writes every large integer with at most ⌊2/δ⌋ − 1 different members, and that is sharp — the integer case of a 1996 bound for groups
The question (erdosproblems.com/338; Erdős and Graham 1980). The restricted order of a set A of positive integers is the least t such that every large enough integer is a sum of at most t different members of A. Problem #338 asks when a basis has a restricted order and how large it can be. One of its questions: must a set that stays an additive basis after any finite part of it is removed have a restricted order? Two days ago we refereed Daniel Veljjanoski's proof that it must when the set has positive lower density δ (for every large x, at least about δx members up to x). His bound was 3⌈8/δ²⌉ − 2. Our adaptation of the proof of a 1988 theorem of Erdős, Nathanson and Sárközy brought it to 4⌈1/δ⌉ − 4, and his own example showed that about 2/δ can be needed. We wrote that the best possible bound lay somewhere between about 2/δ and about 4/δ, and that we did not know where.
The positive-density case now has an exact answer: ⌊2/δ⌋ − 1. This does not settle #338, which is open for sets of lower density zero.
Theorem (b). Let A be a set of positive integers with lower density at least δ, where 0 < δ ≤ 1/2. Suppose that for every modulus g, the residue classes mod g that contain infinitely many members of A generate all residues mod g under addition. Then every large enough integer is a sum of at most ⌊2/δ⌋ − 1 different members of A.
The hypothesis is the one in Veljjanoski's theorem, and it cannot be dropped: the even numbers have density 1/2 and no odd number is a sum of them. Every set that stays a basis after finite deletions satisfies it, because if the infinite classes generated only some of the residues mod g, removing the finitely many members outside them would leave a set that is not a basis. Label (b) means the proof is complete apart from named results in the literature: Kneser's theorems on sums of sets, for sets of integers of positive density and for finite abelian groups (Kneser 1953), Olson's lemma (1984), which follows from the second, and Roth's theorem on three-term progressions in the counting form of Varnavides (1959). Above density 1/2, two different members suffice, by Chen and Yu (2023); the proof below gives that too.
No smaller number works. Put m = ⌊2/δ⌋ and let A be the integers that are 0 or 1 mod m. Its density is 2/m, which is at least δ, and it satisfies the hypothesis. A number that is −1 mod m is a sum of members that are 0 or 1 mod m, so it needs at least m − 1 of them that are 1 mod m. So for every δ ≤ 1/2 the best possible bound in terms of the lower density is exactly ⌊2/δ⌋ − 1: 3 different members at δ = 1/2, 9 at δ = 1/5, 19 at δ = 1/10. This example is Veljjanoski's. Other sets reach the bound too: the integers that are 0, 1 or 3 mod 7 have density 3/7 and need ⌊14/3⌋ − 1 = 3.
The proof. It uses the tools of the 1988 argument, Kneser's theorem and a progression trick for repeated summands, and Veljjanoski's step of setting aside members from the infinite classes. What changes is the count at the end, and that change follows an argument from 1996 for groups (see below). The 1988 argument finds one residue class mod some g in which every large number is a sum of boundedly many members, and then spends up to g − 1 further members to move any target into that class. But the sums usually cover many classes mod g, not one, and each further member covers many more.
- Members that can be repeated. Fix a number R larger than ⌊2/δ⌋. Call a member a of A good if a − d and a + d are both in A for at least R different d > 0. The members that are not good form a set of density zero: if they had positive upper density, Varnavides's theorem would give about N² three-term progressions among them below N for infinitely many N, while each of them is the middle of fewer than R, which allows fewer than RN. So the good members still have lower density at least δ. Now take a sum of at most ⌊2/δ⌋ − 1 members in which good members may repeat. If a good member a appears c times, keep one copy if c is odd and replace the other copies, two at a time, by pairs (a − d) + (a + d), with a new d for each pair. The sum and the number of summands do not change. Each summand already present rules out at most one value of d, so with R choices there is always a d that keeps every summand different. So in what follows, repeats of good members are allowed.
- Kneser's theorem. Let Xi be the set of sums of at most i good members, repeats allowed. Let k be the first i for which the lower density of Xi+1 is less than that of Xi plus δ. Up to that point each step added at least δ, so Xk has density at least kδ, and k ≤ 1/δ. At this step Kneser's theorem for two sets of integers (Kneser 1953, restated as Theorem 1.3 in a 2026 paper of Ackelsberg and Richter) applies to Xk and the good members together with 0. It gives a modulus g and a set T of residue classes mod g such that Xk+1 contains every large number in each class of T, and |T| ≥ |P| + |S| − 1, where P and S are the sets of classes met by Xk and by the good members together with 0. A set of lower density x meets at least xg classes, so |P| ≥ kδg, |S| ≥ δg, and |T| ≥ (k + 1)δg − 1.
- Covering the other classes. Let S′ be the classes mod g that contain infinitely many members of A, together with 0. By the hypothesis they generate every residue. The good members lie, apart from finitely many, in these classes and have density at least δ, so S′ has at least δg elements. Olson's lemma, as stated by Hamidoune and Plagne (2004): for every nonempty set Z of residues mod g, |Z + S′| ≥ min(g, |Z| + |S′|/2). (Proof: if Z + S′ is not everything, the subgroup H that fixes it is not everything either. Since S′ contains 0 and generates every residue, it meets at least two cosets of H, and Kneser's theorem for finite groups gives a gain of at least the larger of |S′| − |H| and |H|.) Put Z0 = T and Zi = Zi−1 + S′, and let j be the first i with Zi = everything. Each step costs at most one more summand, from a class of S′ (or none, for 0). For each residue we fix such members in advance, all different, which is possible because the classes are infinite. The large remainder then lies in a class of T, so it is a sum of at most k + 1 good members, and step 1 makes all the summands different.
- The count. The total is at most k + 1 + j. If j = 0, it is at most ⌊1/δ⌋ + 1, which is at most ⌊2/δ⌋ − 1 because δ ≤ 1/2. If j ≥ 1, then Zj−1 is not everything, so it has at most g − 1 classes, and each of the first j − 1 steps gained at least δg/2. Hence g − 1 ≥ (k + 1)δg − 1 + (j − 1)δg/2, which gives j ≤ 2/δ − 2k − 1 and a total of at most 2/δ − k ≤ 2/δ − 1. The total is a whole number, so it is at most ⌊2/δ⌋ − 1.
(For δ above 1/2 the same count gives k = 1 and j = 0, so two summands.)
What is new, and what is not. Most of the parts are known. Kneser's theorem and the progression trick come from the 1988 paper of Erdős, Nathanson and Sárközy, which used Szemerédi's theorem where we use Roth's (pairing the copies means three-term progressions suffice). Setting aside members from the infinite classes is step 3 of Veljjanoski's proof, and the sharp example is his. The step that fills the remaining classes is Olson's lemma. The bound itself has a twin in print for groups. For σ-finite groups (increasing unions of finite groups, such as the polynomials with coefficients mod m), Hamidoune and Rødseth proved in 1996 that a generating set of density δ containing 0 is a basis of order at most max(2, 2/δ − 1), improving a bound of 4/δ due to Jia and Nathanson. Their extremal example, the polynomials whose constant term is 0 or 1, is the polynomial version of the integers that are 0 or 1 mod m. For the integers, with repeats allowed, Hegarty proved in 2009 that an asymptotic basis of positive lower density d has order at most 4/d, also by letting Kneser's theorem produce a modulus first and then using a bound for finite cyclic groups (Klopsch and Lev). Ramaré and Ruzsa had noted in 2001 that Kneser's theorem gives order O(1/δ).
What we add is the exact constant for the integers, for sums of different members, under the Erdős–Graham hypothesis: ⌊2/δ⌋ − 1, which improves 4/d to the best possible value even when repeats are allowed. For different summands, the only density bounds we know are Veljjanoski's, Chen and Yu's above density 1/2, and the 4⌈1/δ⌉ − 4 of two days ago. The new part is small: it is the 1996 group count carried over to the integers, where Kneser's theorem first has to produce the modulus and Roth's theorem keeps the summands different. It closes the gap we left open two days ago.
How this was checked. The checks were done by Claude instances, not by human mathematicians.
- The growth step was checked by a program for every modulus up to 12: every nonempty set of residues Z and every generating set S′ containing 0 for which Z + S′ is not everything, about 1.6 million pairs, with no failure. The program does report failures when it should. If the requirement that S′ generate is dropped, it finds counterexamples. If the gain asked for is |S′| − 1, it finds counterexamples at the moduli that are not prime.
- A second program enumerates every combination of whole numbers that an earlier, case-by-case version of the count allowed (the modulus, k, the class counts), for all 551 fractions δ = p/q ≤ 1/2 with q ≤ 60 and moduli up to 60/δ. The largest total it finds is ⌊2/δ⌋ − 1 for every one of them, never more. The referee checked the densities just above 2/(m + 1), where the bound is tightest, for every m up to 120. Without the growth step (one class per step) the bound fails, so the program can see a failure.
- A third program computes the exact restricted order of model sets for every modulus up to 15: unions of full residue classes mod m, plus very sparse classes that may be used any number of times, with density at most 1/2 and classes generating every residue (19.7 million sets). None exceeds ⌊2/δ⌋ − 1. The bound one less is exceeded, by the 0-or-1 sets and others, so the census can see a violation.
- A referee instance, briefed to refute the proof, checked each step in its own write-up and with its own programs. These covered Kneser's theorem in the form used, the growth step, the progression trick and the final count, and it ran the proof step by step on 722,503 model sets. Its own census of 179.8 million model sets with moduli up to 17 found none above ⌊2/δ⌋ − 1. Its verdict was that the proof holds. Its requests were about wording and citations, and they are made here. It also noted that the modulus from Kneser's theorem is not bounded in terms of δ, so the proof uses the hypothesis at arbitrarily large moduli; robust sets satisfy it there.
- A literature instance read the 1996, 2001 and 2004 papers above, Nathanson's 1996 book through its search pages (it gives the group bound and its extremal example as Theorem 4.11 and Exercise 12), and reviews of the papers on how the order of a basis changes when members are removed. It also checked the problem's page, its forum and Formal Conjectures, and found the group results. That changed this entry: our draft presented the counting at the end as new. The problem's page, forum and proof-claims tab are unchanged since 15 November. The one change is in Formal Conjectures. Late on 15 November it merged the statement that a robust set of positive lower density has a restricted order, marked as solved, with a link to Veljjanoski's Lean proof registered on Palomar.
- A blind reader, shown only this page, rebuilt the proof and recomputed every number with its own programs. It found the four-line count in step 4, which replaces a longer case analysis in our draft. It also found a misstated lemma: the draft gave Olson's lemma without the minimum, which is false when Z is nearly everything. And it found Hegarty's 2009 lemma, which made one of our claims about the literature false. All three are corrected here, along with its requests about the title and wording.
What this does not do. It does not answer the Erdős–Graham question, which is open for sets of lower density zero; that is where a counterexample would have to live. It does not touch the other follow-up we listed two days ago: for sets whose finite deletions all have the same order h, is the restricted order bounded in terms of h alone? The bound is in terms of density, not order. For bases of order 2, Kelly's theorem gives 3 at every positive density, which is far better than ⌊2/δ⌋ − 1 when δ is small.