# Combinatorics problem about sum of natural numbers

Following combinatorics problem is claimed to be an open problem in "The Princeton Companion to Mathematics" (pp. 6)

Let $a_1,a_2,a_3,...$ be a sequence of positive integers, and suppose that each $a_n$ lies between $n^2$ and $(n+ 1)^2$. Will there always be a positive integer that can be written in a thousand different ways as a sum of two numbers from the sequence?

I am curious to know current status and references for this problem.

• Nice question! Is there anything special about "thousand"? I think you can send an email to the writers of the book for more details about this problem. May 15, 2016 at 21:54

If the sequence $a_1, a_2,\dots$ has the property that each integer can be written in at most $g$ ways (counting order and allowing repetition), then we call the set $\{a_1,a_2,\ldots\}$ a $B^\ast[g]$ set. I wrote an extensive bibliography about 10 years ago, and published it in the Electronic Journal of Combinatorics section on hot bibliographies. Unfortunately, I've never gotten around to updating it. For some reason, Math Sci-Net never cataloged it, either.
A related and more famous question, asked by Erdos and Turan, is if it is possible for a $B^\ast[g]$ set of nonnegative integers to also be a basis, that is, is it possible for every positive integer to have a representation while no positive integer has more than $g$ representations? The answer is known to be "no" for small $g$; the proofs are essentially a depth first search through $B^\ast[g]$ sets.
• Thanks for your answer. Also, I saw your paper and it is interesting. I hope you can update it asap. As I understood, this problem is open, yes? Also, the question asks about the existence of a special integer which can be written in thousand different ways. But in your definition, the sequence has this property that each integer can be written in at most $g$ ways (allowing repetition). May 16, 2016 at 19:20
• Either the set is a $B^*[999]$ set, or there is a positive integer with at least 1000 representations. May 19, 2016 at 17:39