3
$\begingroup$

How to find a set $A \subset \mathbb{N}$ such that any sum of at most three Elements $a_i \in A$ is different if at least one element in the sum is different.

Example with $|A|=3$: Out of the set $A := \{1,7,11\}$ follow 19 sums 1,2,3,7,8,9,11,12,13,14,15,18,19,21,22,23,25,29,33 which are all distinct!

Is there an algorithm to construct such sets for a given number of elements $n=|A|$ with the smallest maximum possible?

Improve this question
$\endgroup$
2
  • $\begingroup$ This is what I figured out so far: Such sets are known as $B_k[1]$ sets. k is the number of elements in the sum. Therefore im interested in $B_3[1]$ sets. Sets with distinct sums of only two elements $B_2[1]$ are also known as Sidon sets. $\endgroup$
    – Shannon
    Commented Jul 19, 2014 at 20:25
  • 2
    $\begingroup$ The first place to turn for this kind of question is Richard Guy's book, Unsolved Problems In Number Theory. Unfortunately, I don't have it handy right now. Also, it won't be as up-to-date as Tony Huynh's answer, but it will give some context and history and references. $\endgroup$
    – Gerry Myerson
    Commented Jul 20, 2014 at 1:08

3 Answers 3

Reset to default
8
$\begingroup$

There is an algorithm: look at all $n$-element subsets of $S:=\{1,2,3,\dots,4^{n-1}\}$. There is at least one $B_3[1]$ subset among them, namely $\{1,4,4^2,\dots,4^{n-1}\}$. So list all $n$-element $B_3[1]$ subsets of $S$, and pick the one with the smallest maximum.

Improve this answer
$\endgroup$
0
7
$\begingroup$

Note that there is a bit of a discrepancy between $B_3[1]$ sets and your notion. For $B_3[1]$ sets, one considers sums with exactly 3 elements, instead of at most 3 elements. However, I do not think this will make a big difference. Basically the main point is that we can do much better than GH from MO's answer by taking a random subset of integers and using the probabilistic method. Indeed, this was carried out by Erdős–Rényi for Sidon sets and claimed (but not proven) for $B_3[1]$ sets. The first correct proof for $B_3[1]$ sets is attributed to Vu in this thesis of Carlos Vinuesa del Río. That thesis also has the current state of the art for your problem. See Theorem 2.1.2. Specializing that result we have the following theorem.

Theorem. For any $\epsilon > 0$, there is an infinite $B_3[1]$ sequence $A$ such that $A(x) \gg x^{\frac{1}{5} - \epsilon}$.

Here $A(x)$ is the number of elements of $A$ that are at most $x$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that the OP only asked if there is an algorithm to find a suitable set with given cardinality and smallest maximum. The possible answers to this question are "yes", "no", "undecidable". With all that, I appreciate your response which contains far more mathematics. $\endgroup$
    – GH from MO
    Commented Jul 19, 2014 at 23:00
  • 1
    $\begingroup$ Yes, I absolutely agree that you completely answered the question as asked. I +1ed it. $\endgroup$
    – Tony Huynh
    Commented Jul 19, 2014 at 23:21
  • 1
    $\begingroup$ Isn't it enough to add $0$ to the set to get a $B_3[1]$ set? (Bearing in mind I have not looked up what $B_3[1]$ means...) $\endgroup$
    – Bruno Le Floch
    Commented Jul 20, 2014 at 3:51
3
$\begingroup$

The probabilistic method shows the existence of an infinite $B_h[1]$ sequence of positive integers $A$ with $A(x)>x^{1/(2h-1)+o(1)}$. The proof is easy for $h=2$ but involved for $h\ge 3$. In particular it gives the exponent $1/5$ for $h=3$.

Ruzsa improved the exponent $1/3$ to $\sqrt 2-1$ for $h=2$ and very recently Cilleruelo, using a new method, improved the exponent $1/(2h-1)$ to $\sqrt{(h-1)^2+1}-(h-1)$ for any $h\ge 3$. http://www.sciencedirect.com/science/article/pii/S000187081400022X

Furthermore, for $h=2$ this method provides an explicit $B_2[1]$ sequence $A$ with $A(x)>x^{\sqrt 2-1+o(1)}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .