Erdős Problem a Daythe open tracker
ERDŐS #338

#338: a basis of positive density that survives finite deletions has a restricted order — Daniel Veljjanoski's proof holds, and his bound of about 24/δ² comes down to about 4/δ using the proof of a 1988 theorem his note does not cite; in his counterexample to Kelly's conjecture, three different summands fall short at the numbers 2·3ʲ and nowhere else

PARTIALNOV 15, 2026
Community database OPENas of 2025-08-31tags number theory, additive basisproblem page · erdosproblems.com/338

The problem (erdosproblems.com/338; Erdős and Graham 1980). A set A of positive integers is a basis of order h if every large enough integer is a sum of at most h members of A, repeats allowed. Its restricted order is the least t such that every large enough integer is a sum of at most t different members of A. It need not exist: for h ≥ 3 the set {1} ∪ {multiples of h} is a basis of order h, but a number that is 2 more than a multiple of h needs the summand 1 twice (Bateman). Erdős and Graham asked when the restricted order exists and how large it can be. One of their questions: call A robust if it is still a basis after any finite set of its members is removed. Must a robust set have a restricted order? Bateman's set is not robust, since it stops being a basis when 1 is removed. The question is open.

Where it stands.

  • The proof claim on the problem's page. On 1 October 2026 Daniel Veljjanoski posted a note with two theorems. The first: a robust set of positive lower density δ has a restricted order, at most 3⌈8/δ²⌉ − 2. (Lower density δ means that, for every large x, the set has at least about δx members up to x.) So a counterexample to the Erdős–Graham question must have lower density zero. The second theorem concerns a model of the block constructions used for lower bounds. His note builds on our July report, which settled the eventually periodic case and gave a basis of order 3 with restricted order 6. We found no discussion of the note anywhere since it was posted, and the problem's page has not changed since September 2025.
  • Kelly's conjecture. A basis of order 2 has restricted order at most 4. Kelly proved this in 1957 for bases in the classical sense, where every integer is a sum of two members (we rely on the zbMATH review of his paper, which we could not obtain), and Hennecart proved it in 2005 for the definition above. Kelly conjectured that 3 always suffices, and proved it when the basis has positive lower density. Hennecart disproved the conjecture in 2005 with an example that needs 4; by Kelly's theorem any such example has lower density zero. On 8 November 2026 a Lean proof by Veljjanoski that the conjecture is false was merged into Formal Conjectures. It uses a counterexample he built himself, because he could not get Hennecart's paper. Neither could we, so we cannot say whether the two examples are the same set. We found no earlier machine-checked disproof.

Labels: (a) elementary proof · (b) rigorous, using a named theorem · (d) established by computation, reproducible from our bundle.

His Theorem 1, refereed (b): it holds. The statement is slightly more general than robustness. Let A have lower density δ > 0, and 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. (A robust set has this property: if those classes generated only part of the residues, removing the finitely many members outside them would leave a set that is not a basis.) Then every large enough integer is a sum of at most 3s − 2 different members of A, where s = ⌈8/δ²⌉. The proof has four steps.

  1. Popular sums. Fix a number R. Call an integer popular if it can be written as a + b with a < b in A in at least R ways. He shows by counting pairs that the popular integers have lower density at least δ²/4.
  2. Kneser's theorem. Take s so large that s times that density is at least 2. Kneser's theorem on sums of sets of positive density then gives a modulus g ≤ s − 1 and a residue class mod g in which every large enough integer is a sum of s popular integers.
  3. Fixing the residue. Because the infinite classes generate all residues, at most g − 1 different members of A move any target into that class.
  4. Keeping the summands different. Each popular integer has R representations, and two of its representations never share a member. With R = 3s, the s pairs can be chosen one after another, each avoiding the members already used.

His note credits two of these steps to the 2007 paper of Hegyvári, Hennecart and Plagne: the form of Kneser's theorem in step 2, and the argument of step 4. A referee instance briefed to break the proof found no gap. We read Kneser's theorem in the form quoted in that 2007 paper and in the 1988 paper discussed below, and did not go back to Kneser's 1953 paper. Veljjanoski has also formalised the statement that a restricted order exists (without the bound) in Lean; that proof is registered on Palomar and proposed to Formal Conjectures in a pull request that was open, with one approving review, when we wrote this (update, 17 November: it was merged late on 15 November). We did not check the Lean.

What we add, part 1: the bound is linear in 1/δ, and most of that was already in a 1988 paper. His note says: "Whether the right dependence on δ is linear in 1/δ is left open." It is linear.

The 1988 paper. Erdős, Nathanson and Sárközy studied sets A of lower density δ ≤ 1/2 and proved that the sums of a bounded number of different members of A contain an infinite arithmetic progression. Write k = ⌈1/δ⌉. Their proof shows more than their statement: for every s ≥ 1 there are a modulus g, at most k + (k² − 2k)/s, and a residue class mod g in which every large enough integer is a sum of exactly k + s different members of A. Kneser's theorem gives this with repeats allowed. To make the summands different they use Szemerédi's theorem: apart from a set of density zero, every member a of A is the middle of a long arithmetic progression inside A, so a repeated pair a + a can be replaced by (a − d) + (a + d). The paper does not discuss restricted orders, and its main theorem has no condition on residues. It is not cited in his note, in the literature lists on the problem's forum or in our July report, and our own first draft of this entry missed it too; today's literature pass found it.

Theorem C (b). Under the hypotheses of his Theorem 1 with δ ≤ 1/2, every large enough integer is a sum of at most 4⌈1/δ⌉ − 4 different members of A.

  • Proof, from the 1988 argument and his step 3. Take s = k − 1, so that g ≤ 2k − 2. First set aside, for every modulus g up to 2k − 2 and every residue class mod g, at most g − 1 different members of A whose sum lies in that class; his step 3 provides them. Only finitely many members are set aside, so the rest of A still has lower density δ. Apply the 1988 argument to the rest: in some class mod g, every large enough integer is a sum of 2k − 1 different members of the rest. Given a large target, subtract the set-aside members that move it into that class. What remains is a sum of 2k − 1 different members, none of them set aside. That makes at most (2k − 1) + (g − 1) ≤ 4k − 4 summands. No other choice of s does better with this argument.
  • Above density 1/2 two different members always suffice, by a direct count; Chen and Yu (2023) treat that case.

A second proof, changing one step of his own argument (b). This one avoids Szemerédi's theorem and gives a slightly weaker bound.

  • Lemma (a). If A has lower density δ > 0, the popular integers have lower density at least δ, for every R. Fix a number K and let a1 < … < aK be the K smallest members of A. Take a large N and consider all pairs (ai, b) with b a member of A above aK and at most N. There are K × (A(N) − K) of them, where A(N) counts the members of A up to N, and all their sums are at most N + aK. A given sum is hit by at most K of these pairs, one for each i. If the sum is not popular it is hit by at most R − 1 of them, because each pair is a representation of it. So K(A(N) − K) is at most K times the number of popular integers up to N + aK, plus (R − 1)(N + aK). Divide by K(N + aK) and let N grow: the popular integers have lower density at least δ − (R − 1)/K. Since K was arbitrary, the density is at least δ. This cannot be improved: for the multiples of m the popular integers are again multiples of m.
  • Theorem A (b). Under the hypotheses of his Theorem 1, every large enough integer is a sum of at most 3⌈2/δ⌉ − 2 different members of A. His steps 2 to 4 go through unchanged with s = ⌈2/δ⌉: the modulus satisfies g ≤ s − 1, the residue costs at most s − 2 members and the pairs cost 2s.
lower density δhis bound 3⌈8/δ²⌉ − 2Theorem A: 3⌈2/δ⌉ − 2Theorem C: 4⌈1/δ⌉ − 4needed by his example with m = 2/δ
1/2941043
1/559828169
1/102,398583619
1/5059,99829819699

The last column is a lower bound. It is his own example, which shows that no bound below about 2/δ is possible: the integers that are 0 or 1 mod m have density 2/m, satisfy the hypotheses, and have restricted order exactly m − 1, because a number that is −1 mod m needs m − 1 summands that are 1 mod m. So for δ ≤ 1/2 the best possible bound lies between ⌊2/δ⌋ − 1 and 4⌈1/δ⌉ − 4. Both are linear in 1/δ. Their ratio is at most 8/3 (for δ between 2/5 and 1/2 the two are 3 and 8) and tends to 2 as δ gets small. For the robust sets Erdős and Graham asked about: lower density δ forces a restricted order of at most about 4/δ. Update, 17 November: the lower end is the truth. A different count at the end of the same argument gives ⌊2/δ⌋ − 1 for every δ ≤ 1/2, matching his example; see the 17 November entry.

His Theorem 2, refereed: it holds, as a statement about a model. The lower bounds on the problem's page and forum for bases of order 4 and more (Hegyvári, Hennecart and Plagne in 2007, and the Bitter Lemma project's searches) come from unions of blocks: an interval from x to x + x², plus a few points x + cx² for c in a finite set C, at rapidly growing scales x. In a model that keeps only the leading terms, the restricted order of such a construction at order 3 is a number that depends on C alone. His Theorem 2 says this number is at most 4 for every finite set C of real numbers above 1. So within the model no block construction of order 3 beats restricted order 4; our periodic example with restricted order 6 is of a different kind. The proof is a short covering argument and the referee instance found no gap. His program reproduces his printed output exactly. The referee's own exact-arithmetic test of 20,000 random sets C with up to 7 elements, a hill-climbing search and an exhaustive grid of 7,806 sets all stop at 4. Passing from the model to actual sets of integers is carried out in the 2007 paper for its own sets C only. For general C it has not been done, by him or by us.

The counterexample to Kelly's conjecture, and exactly where three summands fall short. Let X be the set of integers whose base-3 digits are all 0 or 1 (0, 1, 3, 4, 9, 10, 12, 13, 27, …). Veljjanoski's set is A = {2a + 1 : a in X} ∪ {4a : a in X}, whose positive members are 1, 3, 4, 7, 9, 12, 16, 19, 21, 25, 27, 36, …. His Lean proof shows two things. Every positive integer is a sum of at most two members of A, so A is a basis of order 2. And 3 is not a restricted order for A: the argument shows that no number 2 × 3j is a sum of at most three different members. The pull request was merged on 8 November with no failing checks. We read the Lean file and did not compile it here.

What we add, part 2: Theorem B (a), confirmed by computation (d). The numbers 2 × 3j are the only ones for which three different members fall short: every other positive integer is a sum of at most three different members of A. And every positive integer except 2, 6 and 18 is a sum of at most four different members. So the restricted order of A is exactly 4, which is not in the Lean file, and Kelly's conjecture fails for this set on a very thin set of integers: about log3 N of the numbers up to N.

  • The key fact. For an integer q ≥ 0, the equation a + b + 2c = q has a solution with a, b, c in X and a ≠ b, unless q = 3j − 1 for some j ≥ 0, that is, unless q is 0 or every base-3 digit of q is 2. In that excluded case a = b is forced. For q = 0 all three are 0. Otherwise a, b and c are at most q, so they have no more digits than q. At the lowest digit, a, b and 2c contribute at most 4 and must leave the digit 2, so they contribute exactly 2 with no carry: either a and b both have digit 1 and c has 0, or a and b both have 0 and c has 1. The same then holds at each higher digit in turn. (This is also his Lean lemma.) In every other case, find the lowest digit of q that is not 2. Below it, give a and b the digit 0 and c the digit 1. If that digit is 1, give a a 1 there and b and c a 0, and split the higher digits of q as a′ + 2c′, which is always possible digit by digit without carries. If that digit is 0, then q has a non-zero digit above it, since otherwise q would be 3j − 1. Give a and c a 1 there and b a 0. This makes 3, so it leaves the digit 0 and carries 1, and the higher part of q, less 1, is split as before. In both cases a and b differ at that digit.
  • Odd numbers. If n is odd, write (n − 1)/2 = a + 2c. Then n = (2a + 1) + 4c: one odd member, plus a multiple of 4 if c is not 0.
  • Even numbers. An even sum of at most three members of A uses either no odd member or two. If n is 2 mod 4 it must use two, since multiples of 4 alone give a multiple of 4. So n = (2a + 1) + (2b + 1) + 4c with a ≠ b, where c = 0 means there is no third summand. That says a + b + 2c = (n − 2)/2. By the key fact this is possible exactly when (n − 2)/2 is not 3j − 1, that is, when n is not 2 × 3j. If n is a multiple of 4, then (n − 2)/2 is odd while 3j − 1 is even, so the same form always works.
  • Four summands. For j ≥ 3, use the members 12 and 16. What is left is (2a + 1) + (2b + 1) = 2 × 3j − 28, so a + b = 3j − 15, which in base 3 is 2…2110. Split it digit by digit (2 = 1 + 1, 1 = 1 + 0); a digit 1 makes a ≠ b. For example 54 = 19 + 7 + 12 + 16.
  • Computation. Three programs written separately list the numbers that are not sums of at most three different members: ours, which counts subset sums with bit sets, up to 9.6 million; the referee's, which works from pair counts, up to 100 million; and the blind reader's, up to 20 million. In each range these are exactly the numbers 2 × 3j (17 of them below 100 million), and the only numbers that are not sums of at most four different members are 2, 6 and 18. All three find that every number in range is a sum of at most two members when repeats are allowed. Removing the member 12, removing the member 1, or shifting the multiples of 4 by 4 each changes the lists, so the programs are able to report a failure.

How this was checked. The checks were done by Claude instances, not by human mathematicians. A hostile referee instance, briefed to break the claims, went line by line through his Theorems 1 and 2, the lemma and Theorems A, B and C, reading the 1988 paper from the scanned pages. It tested the counting inequalities with its own code on nine kinds of sets (random, periodic, block-structured, Bateman's, and sets produced by a search designed to violate them) and found no violation. It confirmed that his example has restricted order exactly m − 1 for m up to 8. It computed the true restricted order of all 8,667 periodic sets with period at most 13 and density at most 1/2 that satisfy the hypotheses: none exceeds Theorem C's bound and none beats his example. And it re-ran Theorem B's computation by a different method up to 100 million. It found no error in the mathematics. It asked for one correction, made here: an earlier draft said the upper and lower bounds differ by a factor of 2, which is false near δ = 1/2. Its other requests were about wording: say that the sets consist of positive integers, state the range of the best bound correctly for every δ, and note that the Lean set also contains 0, which changes nothing. A literature instance read the 2007 paper in two author versions, the reviews and abstracts of the papers we could not obtain (Kelly 1957 and Hennecart 2005 among them), and the state of the repositories and the forum. It found the 1988 paper, and that changed this entry: our first draft presented the linear bound as new. A blind reader, shown only this page, recomputed the table, re-ran Theorem B's computation with its own program up to 20 million, recounted the 8,667 periodic sets and checked the external facts it could reach. It found no mathematical error and asked for changes of wording and credit, made here. The title and summary had said that the counterexample "fails" where they meant that three summands fall short. They had credited the statement of the 1988 theorem with a bound that only its proof gives, and left out the range of δ. And the page had not said that his note credits two of its steps to the 2007 paper, or that Kelly's own theorem gives 3 at every positive density.

What this does not do. It does not answer either Erdős–Graham question. Sets of lower density zero are untouched, and that is where a counterexample would have to live. The bounds here depend on the density, not on the order: for robust sets whose finite deletions all have the same order h, whether the restricted order is bounded in terms of h alone is open even for positive density (in the eventually periodic case it equals h, by our July report). The linear bound is not a new idea of ours: Theorem C is the 1988 argument plus his step 3, and Theorem A is his own proof, with its steps from the 2007 paper, and one count changed. For bases of order 2, Kelly's theorem gives 3 at every positive density, which is far better than these bounds. We did not know the best bound between about 2/δ and about 4/δ (update, 17 November: it is ⌊2/δ⌋ − 1, proof here). Theorem B is about one set; it says nothing about how large the exception set of an order-2 basis can be in general, and we could not compare the set with Hennecart's.

← our attempt log · problem #338 on the board