3
$\begingroup$

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$?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ If $A$ is such a set, isn't $kA = \{ka : a\in A\}$ also such a set? And clearly $\max(kA)$ can be made arbitrarily large by taking $k$ large. Maybe you meant to ask something different than this. $\endgroup$
    – Joe Silverman
    Commented Dec 1, 2015 at 21:54
  • $\begingroup$ On the other hand, if $A$ is such a set, then the same is true of $A + k$ for all $k \in \bf N$. So you may want to require at least that $\min(A) = 1$ (which also implies $\gcd(A) = 1$ and rules out Joe Silverman's rescaling argument). But even then the question doesn't look that interesting: Suppose $A$ is an $n$-element set such that $\min(A) = 1$, and let $A_\ast:=A \setminus \{\max(A)\}$. Then $|A_\ast + A_\ast|=\frac{1}{2}(n-1)n$, and it is clear that $A_b:=A_\ast\cup\{b\}$ satisfies $|A_b+A_b|=\frac{1}{2}n(n+1)$ for every sufficiently large $b\in \bf N$. $\endgroup$
    – Salvo Tringali
    Commented Dec 1, 2015 at 23:46
  • $\begingroup$ Okay, I see what you want, but your edited version still talks about just $\max(A)$. What you really want, with correct notation, is an upper bound, as a function of $n$, for the function $$S(n):=\min_{\substack{A\subset\mathbb N\\ |A|=n\\|A+A|=(n^2+n)/2\\}} \max(A).$$ $\endgroup$
    – Joe Silverman
    Commented Dec 2, 2015 at 4:16
  • $\begingroup$ See en.wikipedia.org/wiki/Sidon_sequence $\endgroup$
    – Lucia
    Commented Dec 2, 2015 at 4:55

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks a lot, that looks very promising and gives me the right pointers to look for. I will wait some time to see if someone else gives an even better answer before I accept yours. $\endgroup$
    – Doc Brown
    Commented Dec 2, 2015 at 8:13
  • $\begingroup$ I guess, in the Bose-Chowla construction, $p^2-1$ should be $p^2-p$, and "numbers $g+1,\dotsc,g+p$" should be "elements $g+1,\dotsc,g+p$". $\endgroup$
    – Seva
    Commented Dec 2, 2015 at 15:11
  • 1
    $\begingroup$ Yes, they are elements, but $p^2-1$ is ok. We work in a field with $p^2$ elements, not with residues modulo $p^2$. $\endgroup$
    – Fedor Petrov
    Commented Dec 2, 2015 at 15:14
  • $\begingroup$ When you write "of their indices", you mean the indices within the multiplicative group of the field, given by the exponent of a generating element, right? $\endgroup$
    – Doc Brown
    Commented Dec 3, 2015 at 9:36
  • $\begingroup$ @DocBrown exactly $\endgroup$
    – Fedor Petrov
    Commented Dec 3, 2015 at 9:38
7
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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