2$ or $g>3$.
Also on the ``most wanted'' list is a construction of $\Bhg{h}{g}$ sequences, with $g>h!$, which is dense but is
not merely several $B_h$ sets woven together (such sets do exist:~\cite{1980.Erdos}).
We measure the thickness of $\Bhg{h}{g}$ sets with the quantity:
$$\sigma_h(g):= \lim_{n\to\infty} \frac{R_h(g,n)}{\sqrt[h]{\floor{g/h!}n}}.$$
Strictly speaking, this limit is not known to exist for $h>2$ or for $g>3$. One should always understand a
lower bound on $\sigma_h(g)$ as being a lower bound on the corresponding $\liminf$, and an upper bound as being
an upper bound on the $\limsup$. If $g=h!$, then we simply write $\sigma_h$.
There are a number of conjectures that are natural to make:
\begin{enumerate}
\item The limit in the definition of $\sigma_h(g)$ is in fact well-defined.
\item For each $h$, $\sigma_h(g)$ is an increasing function of $g$.
\item For each $h$, $\lim_{g\to\infty} \sigma_h(g)$ is defined and finite.
\item If $kh!\le g_1\le g_2 < (k+1)h!$, then $\sigma_h(g_1)=\sigma_h(g_2)$.
\end{enumerate}
As basic as these questions may seem, they remain unanswered. Regarding question 3, the limit is known to be
bounded between two positive constants. Sadly, there isn't even a conjecture as to growth of $\sigma_h$ as a
function of $h$ (it may well depend on the parity of $h$).
The only explicit values known are $\sigma_2(2)=\sigma_2(3)=1$.
\subsection{$h=2$}
Erd\H{o}s offered USD 500 for answer to the question, ``Is $R_2(2,n)-\sqrt{n}$ unbounded?'' The answer is
likely ``yes''; it is also likely that $R(2,n)-\sqrt{n}$ is nonnegative. Unfortunately, there has been no
progress on these questions since 1941, when it was found that
$$-n^{\alpha/2} < R(2,n)-\sqrt{n} < n^{1/4}+1,$$
the lower bound holding only for $n$ sufficiently large, with $\alpha$ being a real number such that there is
always a prime between $n-n^{\alpha}$ and $n$ (the current record is $\alpha=0.525$).
\begin{figure}\label{fig:sigma2}
\begin{picture}(432,270)
\put(0,0){\includegraphics{sigma2g}}
\end{picture}
\caption{The best known upper and lower bounds on $\sigma_2(g)$.}
\end{figure}
The best known upper and lower bounds on $\sigma_2(g)$ are shown in Figure~\ref{fig:sigma2}. The lower bound is
$$
\begin{array}{r@{{}\ge{}}l@{{}>{}}l}
\sigma_2(4) & \sqrt{8/7} & 1.069, \\ \vspace{1mm}
\sigma_2(6) & \sqrt{16/15} & 1.032, \\ \vspace{1mm}
\sigma_2(8) & \sqrt{8/7} & 1.069, \\ \vspace{1mm}
\sigma_2(10) & \sqrt{49/45} & 1.043, \\ \vspace{1mm}
\sigma_2(12) & \sqrt{6/5} & 1.095,
\end{array}
\qquad
\begin{array}{r@{{}\ge{}}l@{{}>{}}l}
\sigma_2(14) & \sqrt{121/105} & 1.073, \\ \vspace{1mm}
\sigma_2(16) & \sqrt{289/240} & 1.097, \\ \vspace{1mm}
\sigma_2(18) & \sqrt{32/27} & 1.088, \\ \vspace{1mm}
\sigma_2(20) & \sqrt{40/33} & 1.100, \\ \vspace{1mm}
\sigma_2(22) & \sqrt{324/275} & 1.085,
\end{array}
$$
and for $g\ge 12$
$$\sigma_2(2g) \ge \sqrt{2} \frac{g+2\floor{g/3}+\floor{g/6}}{\sqrt{6g^2-2g\floor{g/3}+2g}}.$$
In particular,
$$\lim_{g\to\infty} \sigma_2(g) \ge \sqrt{121/96} > 1.122.$$
The upper bound is a combination of
$$\sigma_2(2g) \le \sqrt{\tfrac 74 (2-1/g)}$$
and
$$\frac{\floor{g/2}}{g}\sigma_2(g)^2 \leq
\left\{%
\begin{array}{ll}
1.74043-{1.00483}/g,
& \hbox{$g\le8$ and even;} \\
1.58337-\frac{0.026335}g + \sqrt{0.011572-\frac{0.083397}g+\frac{0.00069356}{g^2}},
& \hbox{$g\ge 10$ and even;}\\
1.74043-\frac{4.75492}g,
& \hbox{$g\le 23$ and odd;} \\
1.58337-\frac{0.071949}g + \sqrt{0.011572-\frac{0.22784}g+\frac{0.0051768}{g^2}},
& \hbox{$g\ge 25$ and odd.}
\end{array}%
\right.
$$
In particular,
$$\lim_{g\to\infty} \sigma_2(g) \le 1.839.$$
For $g=2$, the upper bound is due to Erd\H{o}s \& Tur\`{a}n~\cite{1941.Erdos.Turan} and the upper bound is due to
Singer~\cite{1938.Singer}. For $g=3$, the upper bound is Ruzsa's~\cite{1993.Ruzsa}, and the lower bound is from
$R(g+1,n)\le R(g,n)$. For $g>3$ the upper bound is a combination of Green~\cite{2001.Green} (for small $g$) and
Martin~\& O'Bryant~\cite{Martin.OBryant} (for large $g$). The lower bound for $g=4$ is due to Habsieger \&
Plagne~\cite{2002.Habsieger.Plagne}, the $g=6$ and $g=8$ bounds are due to
\cite{2002.Cilleruelo.Ruzsa.Trujillo}, and for all other even $g$ by Martin \& O'Bryant
\cite{2004.Martin.OBryant}. The lower bounds for odd $g>3$ are just $\sigma_2(2g)\le \sigma_2(2g+1)$.
The proof of $\sigma_2(2) = 1$ is succinct and elegant; we present it momentarily. The upper bound was found
initially in~\cite{1941.Erdos.Turan} and simplified in~\cite{1969.2.Lindstrom}. The lower bound was found in
\cite{1938.Singer} and simplified to this form in~\cite{1993.Ruzsa}.
\begin{thm} The largest Sidon subset of $[n]$ has $\sim \sqrt{n}$ elements, i.e.,
$\sigma_2 = 1$.
\end{thm}
\begin{proof} Let $1\le a_1 10^{-3} (n \log n)^{1/3}$$
for sufficiently large $n$. Erd\H{o}s asked~\cite{1982.Erdos} if there is a sequence $a_1

17^2$.}
\articlecites{\cite{1932.Sidon},~\cite{1941.Erdos.Turan}}
%---------------------------------------------------------------------------------------
\bib{1945.Bose.Chowla}{article}{
author={Bose, R.~C.},
author={Chowla, S.},
title={On the construction of affine difference sets},
date={1945},
journal={Bull. Calcutta Math. Soc.},
volume={37},
pages={107\ndash 112},
review={\MR{7,365g}},
}
\annotation{This paper considers of the mechanics of converting Bose's construction~\cite{1942.Bose} into actual
numbers. Suppose that $p$ is a power of a prime, and $\theta\in \GF{p^2}$ is a primitive element satisfying
$\theta^2+a\theta+b=0$. Define $f_1=0$ and $f_m\equiv \tfrac{b}{a-f_m} \pmod{p}$. Define also $\log_b(N)$ to be
the unique integer $t\in [0,p)$ such that $b^t \equiv N \pmod{p}$. Then the set $\{d_1,\dots,d_p\}$, defined by
$d_1=1, d_{m-1}=1+d_m-(p+1) \ind(f_m-a)$, witnesses $C_2(2,p^2-1)\geq p$.}
\articlecites{\cite{1938.Singer}}
%---------------------------------------------------------------------------------------
\bib{1955.Stohr}{article}{
author={St\"{o}hr, Alfred},
title={Gel\"oste und ungel\"oste Fragen \"uber Basen der nat\"urlichen Zahlenreihe. I, II},
date={1955},
journal={J. Reine Angew. Math.},
volume={194},
pages={40\ndash 65, 111\ndash 140},
review={\MR{17,713a}},
}
\annotation{This survey addresses Sidon sets in $\S 12 a\beta$ on pages 129--135. Two results of Erd\H{o}s
are given: There is an infinite Sidon set whose counting function $A(n)$ satisfies $\limsup
\frac{A(n)}{\sqrt{n}} \geq \frac12$; Every infinite Sidon set has a counting function $A(n)$ satisfying
$\liminf \frac{A(n)}{\sqrt{n}}=0$.
St\"{o}hr notes that this second result shows that the guess of Mian \& Chowla~\cite{1944.Chowla.Mian} that the
$n$-th term of the greedy Sidon set is at most $n^2$ is false. He also notes that the second statement (and its
proof) can be made more precise: Every infinite Sidon set has a counting function $A(n)$ satisfying $\liminf
\frac{A(n)\sqrt{\log n } }{\sqrt{n}} \ll 1$. These results are also reported as Theorems 8 and 9 of
\cite{1983.Halberstam.Roth}*{Chapter II}.
St\"{o}hr then raises the question of how large $\liminf \frac{A(n)\sqrt{\log n } }{\sqrt{n}}$ can be, and
if the answer is 0, then what would be a suitable replacement for $\frac{\sqrt{\log n}}{\sqrt{n}}$. He
also asks if there is a Sidon set for which $0< \liminf \frac{A(n)\sqrt{\log n } }{\sqrt{n}}\leq \limsup
\frac{A(n)\sqrt{\log n } }{\sqrt{n}}<\infty$. Similar questions are raised for $B_h$ sets.
St\"{o}hr then considers the greedy Sidon set, and notes that its $n$-th element $a_n$ is at most $(n-1)^3+1$.}
\articlecites{\cite{1938.Singer},~\cite{1941.Erdos.Turan},~\cite{1944.Chowla},~\cite{1944.Erdos},
\cite{1944.Chowla.Mian}}
%---------------------------------------------------------------------------------------
\bib{1960.Erdos.Renyi}{article}{
author={Erd{\H{o}}s, P.},
author={R\'{e}nyi, A.},
title={Additive properties of random sequences of positive integers},
date={1960},
journal={Acta Arith.},
volume={6},
pages={83\ndash 110},
review={\MR{22:10970}},
}
\annotation{This papers examines the behavior of $S^\ast(n)$ for sets $S$ defined by $\Prob(k\in S)=p_k$, for
various sequences $p_k$. The result relating to Sidon sequences states that for every $\delta>0$, there exists
a $B^\ast[g]$ sequence $\{a_1,a_2,\dots\}$ satisfying $a_k=\bigO{k^{2(1+2(g-1)^{-1})}}$.
We give the main steps of the proof. Set $p_n=n^{-\frac12-\epsilon}$ (with $\epsilon > (g+1)^{-1}$) and
$q_n=1-p_n$. Define the independent random variables $X_n$ to be 1 with probability $p_n$ and 0 with
probability $q_n$. Define the random function $f(n)=\sum_{k=1}^{n/2} X_kX_{n-k}$; we wish to show that
almost surely $f(n) \leq \frac{g}{2}$ (with finitely many exceptions). Then
\begin{align*}
\E[\exp(t f(n) )] &=\prod_{k\leq n/2} \left(1+
\frac{e^t-1}{(k(n-k))^{1/2+\epsilon}}\right) \\
& \leq \prod_{k \leq n/2} \exp \left(
\frac{e^t-1}{(k(n-k))^{1/2+\epsilon}}\right) \\
&\leq
\exp\left(\frac{e^t-1}{n^{2\epsilon}}I(\epsilon)\right),
\end{align*}
where $I(\epsilon)$ is a constant depending only on $\epsilon$ as $n\to\infty$. Set
$t=\log(1+n^{2\epsilon})$ and apply the Exponential Chebyshev Theorem to find (with $K=g/2$):
$$\Prob(f(n) > K) \leq \frac{\E[\exp(t f(n))]}{\exp(t(K+1))} \leq \frac{C_1}{n^{2\epsilon(K+1)}}.$$
Thus $\sum_{n=1}^\infty P(f(n) > K)$ converges, and the Borel-Cantelli Lemma guarantees that $\{n \colon
X_n=1\}$ is almost surely a $B^\ast[g]$ sequence (at least, after deleting finitely many terms).
This, and other results of this paper, are given in~\cite{1983.Halberstam.Roth}*{Chapter 3}.}
\articlecites{\cite{1932.Sidon},~\cite{1941.Erdos.Turan}}
%---------------------------------------------------------------------------------------
\bib{1961.Kruckeberg}{article}{
author={Kr\"{u}ckeberg, Fritz},
title={$B\sb{2}$-Folgen und verwandte Zahlenfolgen},
date={1961},
journal={J. Reine Angew. Math.},
volume={206},
pages={53\ndash 60},
review={\MR{23:A3729}},
}
\annotation{Theorem 1:
$$\frac 1h \sqrt[h]{h} \leq \sigma_h \le (h\cdot h!)^{1/h}$$
Theorem 2:
$$\frac 1{2h^2} \leq \sigma_h(h!g) \leq (h\cdot h!)^{1/h}.$$
Theorem 3: There is $B^\ast[2]$ set $\cA$ with
$$\limsup_{n\to\infty} \frac{|\cA \cap [n]|}{\sqrt{2n}} \geq \frac 12.$$
The lower bounds in Theorems 1 and 2 are worse than those obtained by the construction of Singer
\cite{1938.Singer} (simplified and generalized to $h>2$ in~\cite{1962.Bose.Chowla}), and the upper bounds are
from the obvious pigeonhole argument. Theorem 3 is proved in English in~\cite{1966.Halberstam.Roth}*{Chapter
2}.}
\articlecites{\cite{1932.Sidon},~\cite{1938.Singer},~\cite{1941.Erdos.Turan},~\cite{1944.Chowla},
\cite{1944.Chowla.Mian},~\cite{1955.Stohr}}
%---------------------------------------------------------------------------------------
\bib{1962.Bose.Chowla}{article}{
author={Bose, R.~C.},
author={Chowla, S.},
title={Theorems in the additive theory of numbers},
date={1962/1963},
journal={Comment. Math. Helv.},
volume={37},
pages={141\ndash 147},
review={\MR{26:2418}},
}
\annotation{If $m$ is a prime power, then $C_h(h!,m^h-1) \geq m$ and $C_h\left(h!,\tfrac{m^{h+1}-1}{m-1}\right)
\geq m+1$. Thus, $\sigma_h \geq 1.$}
\articlecites{\cite{1942.Bose},~\cite{1944.Chowla},~\cite{1941.Erdos.Turan},~\cite{1938.Singer}}
%---------------------------------------------------------------------------------------
\bib{1963.Halberstam.Laxton}{article}{
author={Halberstam, H.},
author={Laxton, R.~R.},
title={On perfect difference sets},
date={1963},
journal={Quart. J. Math. Oxford Ser. (2)},
volume={14},
pages={86\ndash 90},
review={\MR{28:5027}},
}
\annotation{The authors simplify the construction of~\cite{1938.Singer}. They also consider the problem of
identifying those $t$ such that there is an $s$ with $t\cA+s \equiv \cA\pmod{m}$, where $\cA$ is a
$B^\ast[2]\pmod{m}$ set.}
\articlecites{\cite{1938.Singer}}
%---------------------------------------------------------------------------------------
\bib{1964.Halberstam.Laxton}{article}{
author={Halberstam, H.},
author={Laxton, R.~R.},
title={Perfect difference sets},
date={1964},
journal={Proc. Glasgow Math. Assoc.},
volume={6},
pages={177\ndash 184 (1964)},
review={\MR{29:5748}},
}
\mathreview{B. Gordon}{Let $\Pi$ be the projective plane over $\text{GF}(p\sp n)$, and $C$ a collineation of
$\Pi$ of period $q=p\sp {2n}+p\sp n+1$. If the points of $\Pi$ are denoted by $0,1,\cdots,q-1$, where
$C(i)=i+1$, then the points of any line of $\Pi$ form a perfect difference set $\text{mod}\,q$, called a Singer
difference set (S.d.s.). The authors give a new proof of the theorem that the only multipliers of such a set
are the powers of $p\,(\text{mod}\,q)$. They then show that if $A$ and $B$ are any two S.d.s.'s
$(\text{mod}\,q)$, there is an integer $t$ with $(t,q)=1$ such that $tA$ and $B$ are equivalent (i.e.,
translates of each other $\text{mod}\,q$). Combining these results, it follows that the number of inequivalent
S.d.s.'s $(\text{mod}\,q)$ is $\varphi(q)/3n$. \{Actually the paper deals only with the case where $C$ is the
collineation induced in $\Pi=\text{GF}(p\sp {3n})\sp */\text{GF}(p\sp n)\sp *$ by the map
$\alpha\rightarrow\zeta\alpha$ of $\text{GF}(p\sp {3n})\sp *$ onto itself, where $\zeta$ is a generator of
$\text{GF}(p\sp {3n})\sp *$. However, it is easily seen using canonical forms that every S.d.s. is equivalent
to one obtained in this way.\}}
%---------------------------------------------------------------------------------------
%---------------------------------------------------------------------------------------
\bib{1966.Halberstam.Roth}{book}{
author={Halberstam, H.},
author={Roth, K.~F.},
title={Sequences. Vol. I},
publisher={Clarendon Press, Oxford},
date={1966},
review={\MR{35:1565}},
}
\annotation{This book is {\em the} reference for Sidon set research prior to 1969. It also contains the first
rigorous treatment of the probabilistic method, and introduction to sieves, and a lengthy discussion of
different notions of density and their uses. Making a copy of this oft-referenced text available online would
be a valuable service to the community.}
\mathreview{J. Kubilius}{Chapter II concerns the number of representations of positive integers as sums of $h$
summands from a given sequence. For the most part, $h=2$. Let $r\sb n{}'({\cal A})$ denote the number of
representations of $n$ in the form $n=a+a'$, $a\leq a'$, $a\in{\cal A}$, $a'\in{\cal A}$. Among others, the
authors give the theorems of Erdos and Kr\"{u}ckeberg on the asymptotic behavior of the counting function $A(n)$ of
sequences ${\cal A}$ satisfying $r\sb n{}'({\cal A})\leq 1$ for all $n$. They prove also the Erdos-Fuchs
theorem on the rate of growth of $\sum\sb {n=0}\sp NR\sb n({\cal A})$, where $R\sb n({\cal A})$ denotes the
number of representations of the integer $n$ in the form $n=a+a'$, $a\in{\cal A}$, $a'\in{\cal A}$.}
%---------------------------------------------------------------------------------------
\bib{1969.2.Lindstrom}{article}{
author={Lindstr\"{o}m, Bernt},
title={An inequality for $B\sb{2}$-sequences},
date={1969},
journal={J. Combinatorial Theory},
volume={6},
pages={211\ndash 212},
review={\MR{38:4436}},
}
\annotation{This is the book proof that $\sigma_2 \le 1$. The argument is reproduced in the survey accompanying
this bibliography.}
\mathreview{J. M. Gandhi}{A sequence $a\sb 1,a\sb 2,\cdots,a\sb r$ of integers is called a $B\sb 2$ sequence if
all the sums $a\sb i+a\sb j$, $1\leq i\leq j\leq r$, are different. Let $F\sb 2(n)$ be the maximum number of
elements that can be selected from the set $\{1,2,\cdots,n\}$ so as to form a $B\sb 2$ sequence. P. Erdos and P.
Turan~\cite{1941.Erdos.Turan} proved that $F\sb 2(n)* 0$, then eventually $\limsup\sb n r\sb 1(n) = \infty$ (this is
its weakest form). In this section some new results of the authors are presented along with the survey.
In ${\S}5$ Sidon sets (or $B\sb 2[1]$ sets) along with $B\sb 2[g]$ sets are discussed. A set is of type
$B\sb 2[g]$ if $r\sb 2(n) \le g$ for all $n$. Various results and problems regarding mainly the size of
such (finite and infinite) sets are given.
Difference sets are discussed in ${\S}6$. A set of positive integers $B$ is the difference set of a set $A$
if it is equal to all the positive differences one can form from $A$. The main question here is which
sets $B$ are difference sets. Several more general problems are posed in ${\S}7$, and in ${\S}8$ the
probabilistic method is lightly touched upon. The survey contains an excellent collection of very
interesting problems in the field.
Sometimes the numbers of the citations mentioned in the text do not correspond to the list at the end of
the paper, and some references [e.g., P. Erdos and R. Freud, Mat. Lapok 1 (1991), 1--44; per bibl.] are
hard to find.}
%---------------------------------------------------------------------------------------
\bib{1998.Bajnok}{article}{
author={Bajnok, B\'{e}la},
title={\href{http://www.springerlink.com/openurl.asp?genre=article&eissn=1435-5914&volume=14&issue=2&spage=97}
{Constructions of spherical $3$-designs}},
journal={Graphs Combin.},
volume={14},
date={1998},
number={2},
pages={97\ndash 107},
issn={0911-0119},
review={\MR{99f:05020}},
}
\authorsabstract{Spherical t-designs are Chebyshev-type averaging sets on the $d$-sphere $S^{d}\subset R^{d+1}$ which are
exact for polynomials of degree at most $t$. This concept was introduced in 1977 by Delsarte, Goethals, and
Seidel, who also found the minimum possible size of such designs, in particular, that the number of points in a
3-design on $S^d$ must be at least $n\geq 2d+2$. In this paper we give explicit constructions for spherical
3-designs on $S^d$ consisting of $n$ points for $d=1$ and $n\geq 4$; $d=2$ and $n=6, 8, \geq 10$; $d=3$ and
$n=8, \geq 10$; $d=4$ and $n=10, 12, \geq 14$; $d\geq 5$ and $n\geq 5(d+1)/2$ odd or $n\geq 2d+2$ even. We also
provide some evidence that 3-designs of other sizes do not exist. We will introduce and apply a concept from
additive number theory generalizing the classical Sidon-sequences. Namely, we study sets of integers $S$ for
which the congruence ${\varepsilon }_1x_1+{\varepsilon }_2x_2+\cdots+{\varepsilon }_t x_t\equiv 0$ mod n, where
${\varepsilon }_i=0, \ \pm 1$ and $x_i\in S$ $(i=1, 2, \ldots, t)$, only holds in the trivial cases. We call
such sets Sidon-type sets of strength $t$, and denote their maximum cardinality by $s(n, t)$. We find a lower
bound for $s(n, 3)$, and show how Sidon-type sets of strength 3 can be used to construct spherical 3-designs.
We also conjecture that our lower bound gives the true value of $s(n, 3)$ (this has been verified for $n\le
125$).}
%---------------------------------------------------------------------------------------
\bib{1998.Hsu.Jia}{inproceedings}{
author={Hsu, D.~Frank},
author={Jia, Xingde},
title={Some nonexistence results on perfect addition sets},
date={1998},
booktitle={Proceedings of the twenty-ninth southeastern international
conference on combinatorics, graph theory and computing (Boca Raton, fl,
1998)},
volume={134},
pages={131\ndash 137},
review={\MR{2000a:11021}},
}
\mathreview{Georges Grekos}{An addition set with parameters $n,k,h,\lambda$ is a subset $A=\{a\sb 1,\cdots,a\sb
k\}$ of $\mathbf Z/n\mathbf Z$ such that for each $m\in\mathbf Z/n\mathbf Z$, $m\neq 0$, the equation (1)
$m=a\sb {i\sb 1}+\cdots+a\sb {i\sb h}$, $i\sb 1\leq\cdots\leq i\sb h$, has $\lambda$ solutions. A variant is to
require in (1) that $i\sb 1<\cdots N\sp {1/3}$. The author shows here that
there exist maximal Sidon sets of size at most $C (N \log N)\sp {1/3}$. The proof is based on the existence
(due to Singer) of a $p$-element subset $B = \{b\sb 1,\cdots,b\sb p\}$ of the integers mod $q$, where $q =
1+p+p\sp 2$ and $p$ is a prime, such that all sums $b\sb i+b\sb j$, $i\ge j$, are distinct (a large "mod $q$"
Sidon set). One chooses $p \sim (N \log N)\sp {1/3}$ and then defines the Sidon set $$ A\sb 0 = \{b\sb i + d\sb
i q\colon i=1,\cdots,p\},
$$ where the random variables $d\sb i$ are independent and uniformly distributed in $\{1,\cdots,\lfloor N/q
\rfloor\}$. Finally, take any maximal Sidon set $A$ containing $A\sb 0$. It is shown that, with positive
probability, $\vert A\vert \sim \vert A\sb 0\vert $.}
%---------------------------------------------------------------------------------------
\bib{1999.Baltz.Schoen.Srivastav}{incollection}{
author={Baltz, Andreas},
author={Schoen, Tomasz},
author={Srivastav, Anand},
title={Probabilistic construction of small strongly sum-free sets via large Sidon sets},
date={1999},
booktitle={Randomization, approximation, and combinatorial optimization (Berkeley, CA, 1999)},
series={Lecture Notes in Comput. Sci.},
volume={1671},
publisher={Springer},
address={Berlin},
pages={138\ndash 143},
review={\MR{2001e:68137}},
}
\mathreview{}{Summary: ``We give simple randomized algorithms leading to new upper bounds for combinatorial
problems of Choi and Erd\"{o}s: For an arbitrary additive group $G$ let $\scr P_n(G)$ denote the set of all subsets
$S$ of $G$ with $n$ elements having the property that 0 is not in $S+S$. Call a subset $A$ of $G$ admissible
with respect to a set $S$ from $\scr P_n(G)$ if the sum of each pair of distinct elements of $A$ lies outside
$S$. For $S\in \scr P_n(G)$ let $h(S)$ denote the maximal cardinality of a subset of $S$ admissible with
respect to $S$. In particular we show $h(n):= \min\{h(S)| G\text{ a group},\ S\in\scr P_n(G)\}=O((\ln n)^2)$.
The innovation of the whole approach is the use of large Sidon sets.''}
%---------------------------------------------------------------------------------------
\bib{1999.Godbole.Janson.Locantore.Rapoport}{article}{
author={Godbole, Anant~P.},
author={Janson, Svante},
author={Locantore, Nicholas~W., Jr.},
author={Rapoport, Rebecca},
title={\href{http://dx.doi.org/10.1006/jnth.1998.2325}
{Random Sidon sequences}},
date={1999},
ISSN={0022-314X},
journal={J. Number Theory},
volume={75},
number={1},
pages={7\ndash 22},
review={\MR{2000c:11031}},
}
\authorsabstract{A subset $\cA$ of the set $[n]=\{1,2,\dots,n\}$, $|\cA| =k$ is said to form a Sidon (or $B_h$)
sequence $h\ge 2$, if each of the sums $a_1+a_2+\dots + a_h$, $a_1\le a_2 \le \dots \le a_h$; $a_i\in\cA$, are
distinct. We investigate threshold phenomena for the Sidon property, showing that if $\cA_n$ is a random subset
of $[n]$, then the probability that $\cA_n$ is a $B_h$ sequence tends to unity as $n\to\infty$ if $k_n =|\cA_n|
\ll n^{1/2h}$, and that ${\bf P}(\cA_n\text{ is Sidon}) \to 0$ provided that $k_n \gg n^{1/2h}$. The main tool
employed is the Janson exponential inequality. The validity of the Sidon property {\em at} the threshold is
studied as well. We prove, using the Stein-Chen method of Poisson approximation, that ${\bf P}(\cA_n\text{ is
Sidon}) \to \exp{-\lambda}$ ($n\to \infty$) if $k_n \sim \Lambda \cdot n^{1/2h}$ ($\Lambda \in {\bf R}^+$),
where $\lambda$ is a constant that depends in a well-specified way on $\Lambda$. Multivariate generalizations
are presented.}
\mathreview{Mihail N. Kolountzakis}{The uniform distribution is considered on all $k$-element subsets of
$\{1,2,\cdots,n\}$ and the problem of when a random set $A$ (as above) has the $B_h$ property (i.e., all sums
$a_1+\cdots+a_h$, with $a_i \in A$ and $a_1 \le \cdots \le a_h$, are distinct) is studied. It is known that the
largest $B_h$ subset of $\{1,\cdots,n\}$ is of size $\sim n^{1/h}$. However, it turns out that when we are
choosing random sets we cannot expect that such a large set is $B_h$. In this very clearly written paper it is
proved that when $k = o(n^{1/2h})$ then $A$ is almost surely a $B_h$ set and that when $n^{1/2h} = o(k)$ the
random set $A$ is almost surely not a $B_h$ set. The authors go even further and study the problem at threshold
size $k \sim \Lambda n^{1/2h}$, $\Lambda$ a constant. They prove that in this case (as $n \to \infty$) ${\rm
Prob}(A {\rm is Sidon}) \to e^{-\lambda}$, where $\lambda$ is an explicit function of $\Lambda$.
For the study of the problem away from the threshold the authors use the so-called Janson correlation
inequality, which estimates the probability for the intersection of a collection of events with few
dependencies among them (the proof that a set below the threshold is almost certainly $B_h$ does not
demand this machinery and is a straightforward calculation). At the threshold the Stein-Chen method of
Poisson approximation is used. It is pointed out that either method could have been used for both the
threshold and away-from-threshold problem.}
%---------------------------------------------------------------------------------------
\bib{1999.Kolountzakis}{article}{
author={Kolountzakis, Mihail~N.},
title={\href{http://dx.doi.org/10.1006/jnth.1998.2351}
{On the uniform distribution in residue classes of dense sets of integers with distinct sums}},
date={1999},
ISSN={0022-314X},
journal={J. Number Theory},
volume={76},
number={1},
pages={147\ndash 153},
review={\MR{2000a:11028}},
}
\authorsabstract{A set $\cA \subseteq \{1, \dots, N\}$ is of the type $B_2$ if all sums $a+b$, with $a\ge b$,
$a, b \in \cA$, are distinct. It is well known that the largest such set is of size asymptotic to $N^{1/2}$.
For a $B_2$ set $\cA$ of this size we show that, under mild assumptions on the size of the modulus $m$ and on
the difference $N^{1/2}-|\cA |$ (these quantities should not be too large), the elements of $\cA$ are uniformly
distributed in the residue classes mod $m$. Quantitative estimates on how uniform the distribution is are also
provided. This generalizes recent results of Lindstr\"{o}m whose approach was combinatorial. Our main tool is an
upper bound on the minimum of a cosine sum of $k$ terms, $\sum_1^k \cos \lambda_jx$, all of whose positive
integer frequencies $j$ are at most $(2-\epsilon) k$ in size. }
\mathreview{Nikolai Volodin}{A set $A \subseteq \{1,\cdots,N\}$ is of the type $B\sb {2}$ if all sums $a+b$,
with $a \geq b$, $a, b\in A$, are distinct. Let $$ a(x)=a\sb {m}(x)=\left \vert \{a \in A\colon a=x \bmod
m\}\right \vert , x \in Z\sb {m}. $$ Theorem. Suppose $A \subseteq \{1,\cdots,N\}$ is a $B\sb {2}$ set and
that $k=\vert A \vert \geq N\sp {1/2} - l$, with $l=l(N)= o(N\sp {1/2})$. Assume also that $m=o(N\sp
{1/2})$. Then $$ \left(\sum\sb {x \in Z\sb {m}}\left\vert a(x)- {\tfrac km} \right\vert \sp {2} \right)\sp
{1/2} \leq C \begin{cases} N\sp {3/8}m\sp {-{1/4}}, & \text{if $l \leq N^{1/4} m^{1/2}$;}, \\ N\sp {1/4}
l\sp {1/2} m \sp {-{1/2}}, & \text{otherwise}. \end{cases} $$ }
%---------------------------------------------------------------------------------------
\bib{1999.1.Lindstrom}{article}{
author={Lindstr\"{o}m, B.},
title={Primitive quadratics reflected in $B\sb 2$-sequences},
date={1999},
ISSN={0032-5155},
journal={Portugal. Math.},
volume={56},
number={3},
pages={257\ndash 263},
review={\MR{2000j:11029}},
}
\mathreview{Norbert Hegyv\'{a}ri}{Let $A=\{a\sb 1r^{-2}$); ${\rm ms}( R/ Z,r)=r^{-2}$ (here ${\scr S}={\scr S}_+$); and some results on
arbitrary compact abelian $G$ ($µ$ is then Haar measure). (3) Consider geometric figures, especially the ball
$V^k$ and sphere $S^{k-1}$ in $ R^k$, with normed Lebesgue measure. ${\scr S}$ consists of non-identical
isometries leaving $\Omega$ invariant. Some results: For $\Omega=V^k,S^{k-1}$ we have ${\rm
ms}(\Omega,r)=r^{-2}$; the disc $V^2$ can be $r$-colored so that $µ(A)\le r^{-2}$ for every monochromatic
symmetric subset. Some results on figures with a finite number of symmetries are given (without proofs). (4)
It is proved that the minimum $r$ for which $\chi\colon Z^k\rightarrow [r]$ exists without infinite
monochromatic symmetric set (symmetries here are $s(x)=g-x$) is $k+1$. The bound $r\le k+1$ is shown by a
simple construction and $r>k$ is proved by the Borsuk-Ulam antipodal theorem. A general version of this
question for infinite abelian groups is given and is related to the generalized continuum hypothesis. 14 open
problems are posed.}
%---------------------------------------------------------------------------------------
\bib{2000.1.Cilleruelo}{article}{
author={Cilleruelo, Javier},
title={\href{http://dx.doi.org/10.1006/jcta.1999.3012}{An upper bound for $B\sb 2[2]$ sequences}},
date={2000},
ISSN={0097-3165},
journal={J. Combin. Theory Ser. A},
volume={89},
number={1},
pages={141\ndash 144},
review={\MR{2001d:11026}},
}
\annotation{Cilleruelo gives a combinatorial proof that $R(4,n) \leq \sqrt{6n}+1$, whence $\sigma_2(4)\le
\sqrt{3}$.}
%---------------------------------------------------------------------------------------
\bib{2000.2.Cilleruelo}{article}{
author={Cilleruelo, Javier},
title={\href{http://www.integers-ejcnt.org/vol0.html}
{Gaps in dense Sidon sets}},
date={2000},
volume ={0},
journal={Integers},
pages={Paper A11, 6pp. (electronic)},
review={\MR{2001m:11129}},
}
\authorsabstract{We prove that if $\cA\subset[1,N]$ is a Sidon set with $N^{1/2}-L$ elements, then any interval
$I\subset[1,N]$ of length $cN$ contains $c|\cA|+E_I$ elements of $\cA$, with $|E_I| \le 52 N^{1/4}(1+c^{1/2}
N^{1/8})(1+L_+^{1/2}) N^{-1/8}$, $L_+ = \max\{0,L\}$. In particular, if $|A|=N^{1/2}+\bigO{N^{1/4}}$, and
$g(A)$ is the maximum gap in $\cA$, we deduce that $g(A) \ll N^{3/4}$. We also prove that, under this
condition, the exponent $3/4$ is sharp.}
\mathreview{Mihail N. Kolountzakis}{A finite sequence $A$ of positive integers is called a Sidon set if all
sums one can form with two elements of $A$ are distinct except for the trivial coincidences. (This is
equivalent to all differences of two elements of $A$ being distinct.) It has long been known that the largest
Sidon subset of $[1,N]$ has size $\sim N^{1/2}$, and that such sets, which satisfy this asymptotic upper bound,
must be rather regular both in terms of their distribution modulo some (small) residue and in terms of being
"uniformly distributed" in the interval $[1,N]$.
As the author points out, a result claiming uniform distribution implies an upper bound on the maximum gap
such a set may have. The author gives an improved uniform distribution result which implies an improved (and
best possible, in the extreme cases at least) upper bound for the maximum gap.
The improved uniform distribution result claims that if $A \subseteq [1,N]$ is a Sidon set with $N^{1/2}-L$
elements and $I$ is a subinterval of $[1,N]$ of size $cN$ then $$ | c|A| - |A\cap I| | \le 52 N^{1/4}
(1+\sqrt c N^{1/8}) (1+(L^+)^{1/2}N^{-1/8}). $$ The improved upper bound on the maximum gap implied by this
is $C N^{6/8}$, whereas the previously known upper bound was $C N^{7/8}$.}
%---------------------------------------------------------------------------------------
\bib{2000.Cilleruelo.JimenezUrroz}{article}{
author={Cilleruelo, Javier},
author={Jim\'{e}nez-Urroz, Jorge},
title={$B\sb h[g]$ sequences},
journal={Mathematika},
volume={47},
date={2000},
number={1-2},
pages={109\ndash 115 (2002)},
issn={0025-5793},
review={\MR{1924491}},
}
\authorsabstract{We give new upper and lower bounds for $F_h(g,N)$, the maximum size of a $B_h[g]$ sequence
contained in $[1,N]$. We prove
$$F_h(g,N) \le (\sqrt{3h} h! g N)^{1/h},$$
and for any $\epsilon>0$ and $g>g(\epsilon,h)$,
$$F_h(g,N) \ge \left( (1-\epsilon) \sqrt{\frac{\pi}{6}} \sqrt{h} g N\right)^{1/h}+\littleo(N^{1/h}).$$}
\annotation{This means that $\sigma_h(h!g) \le (h!\sqrt{3h})^{1/h}$ (an improvement for $h>7$) and
$\liminf_{g\to \infty} \sigma_h(h!g)h^{-1/(2h)} \ge \sqrt{\pi/6}$.}
\mathreview{Mihail N. Kolountzakis}{Let $A$ be a set of integers. We write $r_h(n)$ for the number of
representations of $n$ as a sum of $h$ not-necessarily-distinct terms from $A$ where we ignore the order of the
summands. A set $A$ is called a $B_h[g]$ set if $r_h(n) \le g$ for all integers $n$. The size of the largest
$B_h[g]$ set contained in $\{1,\dots,N\}$ is denoted by $F_h(g, N)$ in this paper. If $g=1$ the size of
$F_h(g,N)$ is much better known than for $g>1$. In this paper the authors prove two improved (upper and lower)
bounds for the quantity $F_h(g,N)$. It is proved that $F_h(g,N) \le (\sqrt{3h} h! g N)^{1/h}$ and $F_h(g,N) \ge
((1-\epsilon)\sqrt{\pi/6}\sqrt h g N)^{1/h} + o(N^{1/h})$. The lower bound holds for any $\epsilon>0$ and for
$g>g(\epsilon,h)$. The upper and lower bounds improve the previously known such bounds when $h\ge7$ and $h\ge
3$ respectively. The improvements concern the constant factors and not the dependence on the quantities $g, h$
and $N$.}
%---------------------------------------------------------------------------------------
\bib{2000.1.Lindstrom}{article}{
author={Lindstr\"{o}m, B.},
title={A translate of Bose-Chowla $B\sb 2$-sets},
date={2000},
ISSN={0081-6906},
journal={Studia Sci. Math. Hungar.},
volume={36},
number={3-4},
pages={331\ndash 333},
review={\MR{2001j:11005}},
}
\mathreview{Norbert Hegyv\'{a}ri}{A set $A=\{a_1,a_2,\dots,a_r\}$ is said to be a $B_2$ set $({\rm mod}\,m)$ if the
sums $a_i+a_j, 1\leq i\leq j\leq r$, are different $({\rm mod}\,m)$. A celebrated $B_2$ set is the Bose-Chowla
set $A(q,\theta)$; defined by $$A(q,\theta)=\{a\colon 1\leq a\leq q^2-1, \theta^a-\theta\in{\rm GF}(q)\}$$
provided $\theta$ is a primitive element in ${\rm GF}(q^2)$. Let $$B(q,\theta)=\{b\colon 1\leq b\leq q^2-1,\
\theta^b+\theta^{bq}=1\}.$$ In the present paper the author proves that $B(q,\theta)$ is a translate of $A(q,
\theta)$ and a fortiori that it is a $B_2$ set. It is proved that $B(q,\theta)\equiv A(q,\theta)-C({\rm
mod}\,q^2-1)$, where $C$ is defined by $\theta^C=\theta-\theta^q.$ Furthermore, it is proved that
$\{\theta^b\colon b\in B(q,\theta)\}$ are the roots of $x^q+x-1$ over ${\rm GF}(p)$. Some consequences of this
result are derived.}
%---------------------------------------------------------------------------------------
\bib{2000.2.Lindstrom}{article}{
author={Lindstr\"{o}m, Bernt},
title={\href{http://www.ams.org/jourcgi/jour-getitem?pii=S0002993999051229}
{$B\sb h[g]$-sequences from $B\sb h$-sequences}},
date={2000},
ISSN={0002-9939},
journal={Proc. Amer. Math. Soc.},
volume={128},
number={3},
pages={657\ndash 659},
review={\MR{2000e:11022}},
}
\annotation{If $\cA$ is a $B_h$ set and $\cB=\{0,1,\dots,m\}$, then
$$
m\cA+\cB=\{ma+b \colon a\in\cA, b \in \cB\}
$$
is a $B_h[g]$ set. Consequently, $R_h(h! m^{h-1},n) \ge (m^{h-1}n)^{1/h} (1+\littleo{1}).$
This is the same construction of~\cite{1996.Jia}, but here it is analyzed correctly.}
%---------------------------------------------------------------------------------------
\bib{2000.Nathanson}{article}{
author={Nathanson, Melvyn~B.},
title={\href{http://www.kluweronline.com/article.asp?PIPS=257546}
{$N$-graphs, modular Sidon and sum-free sets, and partition identities}},
date={2000},
ISSN={1382-4090},
journal={Ramanujan J.},
volume={4},
number={1},
pages={59\ndash 67},
review={\MR{2001c:05011}},
}
\authorsabstract{Using a new graphical representation for partitions, the author obtains a family of partition
identities associated with partitions into distinct parts of an arithmetic progression, or, more generally,
with partitions into distinct parts of a set that is a finite union of arithmetic progressions associated with
a modular sum-free Sidon set. Partition identities are also constructed for sets associated with modular
sum-free sets.}
\mathreview{Christian Krattenthaler}{Let $\lambda=(\lambda\sb 1,\lambda\sb 2,\cdots,\lambda\sb m)$ be a
partition. Given a fixed positive integer $m$, write each $\lambda\sb i$ as $mq\sb i+r\sb i$, $1\le r\sb i\le
m$. Instead of representing the partition $\lambda$ in the form of a Ferrers diagram, represent $\lambda$ as a
planar array of integers in which the $i$th row consists of $q\sb i$ entries $m$ and then the entry $r\sb i$.
If $m=1$, then the Ferrers diagram of $\lambda$ is recovered, in which boxes are replaced by 1's. To each such
planar array there is associated a hook partition, which is obtained by summing the entries along the principal
hooks of the array. This is not a one-to-one correspondence, though. The results of the paper are partition
identities that express the number of such planar arrays in which the last entries must belong to a given set
of weighted sums over certain hook partitions.}
%---------------------------------------------------------------------------------------
\bib{2000.Serra.Zemor}{article}{
author={Serra, Oriol},
author={Z\'{e}mor, Gilles},
title={\href{http://www.integers-ejcnt.org/vol0.html}
{On a generalization of a theorem by Vosper}},
journal={Integers},
volume={0},
date={2000},
pages={Paper A10, 10 pp. (electronic)},
review={\MR{2001f:11178}},
}
\authorsabstract{Let $S,T$ be subsets of $\Z/p\Z$ with $\min \{ |S|,|T|\}>1$.
The Cauchy-Davenport theorem states that $|S+T|\ge \min\{ p,|S|+|T|-1\}$. A theorem by Vosper characterizes the
critical pair in the above inequality. We prove the following generalization of Vosper's theorem. If $|S+T|\le
\min\{ p-2, |S|+|T|+m\}$, $2\le |S|,|T|$, and $|S|\le p-{\binom{m+4}{2}}$, then $S$ is a union of at most $m+2$
arithmetic progressions with the same difference. The term $\binom{m+4}{2}$ is best possible, i.e. cannot be
replaced by a smaller number. }
\mathreview{Alain Plagne}{This paper is concerned with additive number theory in $\bold Z/p\bold Z$. A
well-known theorem of A. L. Cauchy [J. \'{E}cole Polytech. 9 (1813), 99--123], rediscovered by H. Davenport [J.
London Math. Soc. 10 (1935), 30--32; Zbl 010.38905], states that for any $S,T\subset\bold Z/p\bold Z$, the
following holds: $|S+T|\geq \min(p,|S|+|T|-1)$. A. G. Vosper's theorem [J. London Math. Soc. 31 (1956),
200--205; MR 17, 1056c] is a characterization of those $S,T$ such that equality holds in the Cauchy-Davenport
theorem.
Y. O. Hamidoune generalized Vosper's result in several directions. He obtained [J. Algebra 179 (1996), no. 2,
622--630; MR 96m:20034] a result valid in more general groups than $\bold Z/p\bold Z$. To prove this, he
developed the so-called isoperimetric method, for which he defined important tools such as $k$-isoperimetric
numbers, $k$-critical sets and $k$-atoms (a terminology coming from graph theory).
Also, in the case of $\bold Z/p\bold Z$, Hamidoune and {\O}. J. R{\o}dseth [Acta Arith. 92 (2000), no. 3, 251--262;
MR 2001c:11114] went a step further than Vosper by characterizing completely those sets $S,T$ such that
$|S+T|=|S|+|T|$.
Let us mention that there is also a result by G. A. Fre\u\i man [ Elements of a structural theory of set
addition (Russian), Kazan. Gosudarstv. Ped. Inst, 1966; MR 50:12943; English translation; MR 50:12944], in
the case $S=T$ only, which describes the situation up to $|S+S|=12|S|/5-4$.
In the paper under review, the authors partially (the atomic part only) generalize Hamidoune and R{\o}dseth's
result by giving (Theorem 6) necessary conditions that must be satisfied by sets $S,T$ such that $|S+T|\leq
|S|+|T|+m$ for some given integer $m$. Under the (best possible) cardinality condition $2\leq |S|,
|T|*