17
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Shahrooz
    May 15, 2016 at 21:54

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Shahrooz
    May 16, 2016 at 19:20
  • $\begingroup$ Either the set is a $B^*[999] $ set, or there is a positive integer with at least 1000 representations. $\endgroup$ May 19, 2016 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.