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

$\endgroup$
  • 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 Dec 1 '15 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 Dec 1 '15 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 Dec 2 '15 at 4:16
  • $\begingroup$ See en.wikipedia.org/wiki/Sidon_sequence $\endgroup$ – Lucia Dec 2 '15 at 4:55
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.

| cite | improve this answer | |
$\endgroup$
  • $\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 Dec 2 '15 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 Dec 2 '15 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 Dec 2 '15 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 Dec 3 '15 at 9:36
  • $\begingroup$ @DocBrown exactly $\endgroup$ – Fedor Petrov Dec 3 '15 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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