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.
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.
To answer the Shahrooz Janbaz's question, there is nothing too special about 1000 except that it removes "just compute all possibilities" as a possible strategy. That is, if "1000" is replaced by 4 or 5 or 6, then we could perhaps just search through all possibilities. Perhaps a clever program (SAT solver?) could handle 10 or 20. But 1000 clearly requires a deeper understanding of addition.
