Sumsets with distinct numbers, upper bound for maximum element

Question

Let $A$ be a finite set of positive natural numbers with $n$ elements, $|A|=n$, with the property that all sums of two (not necessarily different) elements are distinct, or in the usual notation for sumsets, $|A+A|$= $1\over2$ $n (n+1)$.

I am looking for ways to choose the elements of $A$ (for a given $n$) so $\max(A)$ gets as minimal as possible. Obviously, $2^{n-1}$ is a trivial upper bound for $\max(A)$, when one picks $A=\{1,2,4,8,...,2^{n-1}\}$. But, for example, when $n=11$, A can be chosen as $\{1,3,8,9,20,23,41,51,67,76,80\}$, so $\max(A)=80$, which is far less than $2^{10}=1024$.

So, are there any known nontrivial upper bounds for

$$S(n) = \min_{A \subset N, |A|=n, |A+A|=n(n+1)/2}( \max(A))$$ ?

Ideally with a construction rule for $A$?

Answer 1

Set $A$, $|A|=n$, with $|A+A|=n(n+1)/2$, is known as a `Sidon set'. This is a subject of numerous studies. As for your specific question, $c_1n^2<S(n)<c_2 n^2$ for some absolute constants, but I do not know current records. UPD: already know, from Lucia's answer.

If you do not care on constants, then:

1) lower estimate is easy: all $n(n-1)/2$ positive distinct differences do not exceed $S(n)-1$, hence $S(n)\geq n(n-1)/2+1$.

2) The following construction originally belongs to Erdős and Turan, 1941 (see Lucia's answer): take odd prime $p$ and all numbers of the form $a_k=2pk+(k^2\mod p)$, $k=0,1,\dots,p-1$ (increase them by 1 if you do not like 0). If $a_k+a_l=a_m+a_n$, then $k+l=[(a_k+a_l)/2p]=m+n$ and $k^2+l^2=m^2+n^2$ modulo $p$, this implies that $\{k,l\}=\{m,n\}$ modulo $p$. This gives $S(p)\leq 2p(p-1)+2$, hence $S(n)\leq (2+o(1))n^2$ for any $n$.

We may improve this up to $(1+o(1))n^2$ by more involved construction. Namely, choose $g$ in a finite field $\mathbb{F}_{p^2}$, but $g\notin \mathbb{F}_p$. Consider elements $g+1,\dots,g+p$. I claim that their products are different in $\mathbb{F}_{p^2}$. It implies that sums of their indices are different modulo $p^2-1$, hence $S(p)\leq p^2-1$. Indeed, if $(g+i)(g+j)=(g+a)(g+b)$, we get $g(i+j-a-b)=ab-ij$, but since $g\notin \mathbb{F}_p$, it is possible only if $ab=ij$, $a+b=i+j$ modulo $p$, hence $\{a,b\}=\{i,j\}$. This construction is taken from the paper

Bose R.C., Chowla S. Theorems in the additive theory of numbers. // Comment. Math. Helv. 1962/63. Vol. 37. P. 141–147.

Answer 2

It can be shown that $S(n) \sim n^2$. The upper bound (constructing large Sidon sets) was given in Fedor Petrov's answer, and is a construction of Bose and Chowla. The lower bound (showing that Sidon sets can't be too big) follows from a simple argument of Erdos and Turan from 1941. This exploits the fact that if $a_i + a_j$ are all distinct, then so are the differences $a_i-a_j$, and the argument proceeds by dividing the big interval $[1,n^2]$ into smaller intervals of size about $n^{3/2}$ and considering only differences in the smaller intervals. Incidentally, Erdos and Turan also gave the argument in Petrov's answer obtaining a weaker upper bound (before the work of Bose and Chowla).

Finally, a $B_2[g]$ sequence is one where the sums $a+b$ may be repeated at most $g$ times (so that a Sidon sequence above is one with $g=2$). A substantial recent advance on this problem was made in the work of Cilleruelo, Ruzsa and Vineusa.