3 solved out of 18 shown

$1000

Let $h(N)$ be the maximum size of a Sidon set in $\{1,\ldots,N\}$. Is it true that, for every $\epsilon>0$,
\[h(N) = N^{1/2}+O_\epsilon(N^\epsilon)?\]

It may even be true that $h(N)=N^{1/2}+O(1)$, but Erdős remarks this is perhaps too optimistic. Erdős and Turán [ErTu41] proved an upper bound of $N^{1/2}+O(N^{1/4})$, with an alternative proof by Lindström [Li69]. Both proofs in fact give
\[h(N) \leq N^{1/2}+N^{1/4}+1.\]
Balogh, Füredi, and Roy [BFR21] improved the bound in the error term to $0.998N^{1/4}$, which has been further optimised by O'Bryant [OB22] to yield
\[h(N)\leq N^{1/2}+0.99703N^{1/4}\]
for sufficiently large $N$.

$50

Is there an infinite Sidon set $A\subset \mathbb{N}$ such that
\[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\]
for all $\epsilon>0$?

The trivial greedy construction achieves $\gg N^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98]. (Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$.) Erdős proved that for every infinite Sidon set $A$ we have
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0,\]
and also that there is a set $A\subset \mathbb{N}$ with $\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}$ such that $1_A\ast 1_A(n)=O(1)$.

$500

Let $A\subset\mathbb{N}$ be an infinite set such that the triple sums $a+b+c$ are all distinct for $a,b,c\in A$ (aside from the trivial coincidences). Is it true that
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=0?\]

Erdős proved that if the pairwise sums $a+b$ are all distinct aside from the trivial coincidences then
\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0.\]

$100

If $A,B\subset \{1,\ldots,N\}$ are two Sidon sets such that $(A-A)\cap(B-B)=\{0\}$ then is it true that
\[ \binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1),\]
where $f(N)$ is the maximum possible size of a Sidon set in $\{1,\ldots,N\}$? If $\lvert A\rvert=\lvert B\rvert$ then can this bound be improved to
\[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq (1-c)\binom{f(N)}{2}\]
for some constant $c>0$?

For any $M\geq 1$, if $A\subset \mathbb{N}$ is a sufficiently large finite Sidon set then there are at least $M$ many $a\in A+A$ such that $a+1,a-1\not\in A+A$.

There may even be $\gg \lvert A\rvert^2$ many such $a$. A similar question can be asked for truncations of infinite Sidon sets.

Let $A\subset \mathbb{N}$ be an infinite set such that, for any $n$, there are most $2$ solutions to $a+b=n$ with $a\leq b$. Must
\[\liminf_{N\to\infty}\frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0?\]

If we replace $2$ by $1$ then $A$ is a Sidon set, for which Erdős proved this is true.

$100

Let $f(N)$ be the maximum size of $A\subseteq \{1,\ldots,N\}$ such that the sums $a+b+c$ with $a,b,c\in A$ are all distinct (aside from the trivial incidences). Is it true that
\[ f(N)\sim N^{1/3}?\]

Originally asked to Erdős by Bose. Bose and Chowla [BoCh62] provided a construction proving one half of this, namely
\[(1+o(1))N^{1/3}\leq f(N).\]
The best upper bound known to date is due to Green [Gr01],
\[f(N) \leq ((7/2)^{1/3}+o(1))N^{1/3}\]
(note that $(7/2)^{1/3}\approx 1.519\cdots$).

Let $A=\{1,2,4,8,13,21,31,45,66,81,97,\ldots\}$ be the greedy Sidon sequence: we begin with $1$ and iteratively include the next smallest integer that preserves the Sidon property. What is the order of growth of $A$? Is it true that
\[\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2-\epsilon}\]
for all $\epsilon>0$ and large $N$?

Erdős and Graham [ErGr80] also ask about the difference set $A-A$, whether this has positive density, and whether this contains $22$.

This sequence is at OEIS A005282.

Let $F(n)$ be the maximum possible size of a subset $A\subseteq\{1,\ldots,N\}$ such that the products $ab$ are distinct for all $a<b$. Is there a constant $c$ such that
\[F(n)=\pi(n)+(c+o(1))n^{3/4}(\log n)^{-3/2}?\]

Erdős [Er68] proved that
\[F(n)-\pi(n)\asymp n^{3/4}(\log n)^{-3/2}.\]
Surprisingly, if we consider the corresponding problem in the reals (so the largest $m$ such that there are reals $1\leq a_1<\cdots <a_m\leq x$ such that for any distinct indices $i,j,r,s$ we have $\lvert a_ia_j-a_ra_s\rvert \geq 1$) then Alexander proved that $m> x/8e$ is possible.

See also [490].

Let $\ell(N)$ be maximal such that in any finite set $A\subset \mathbb{R}$ of size $N$ there exists a Sidon subset $S$ of size $\ell(N)$ (i.e. the only solutions to $a+b=c+d$ in $S$ are the trivial ones). Determine the order of $\ell(N)$.

Originally asked by Riddell [Ri69]. Erdős noted the bounds
\[N^{1/3} \ll \ell(N) \leq (1+o(1))N^{1/2}\]
(the upper bound following from the case $A=\{1,\ldots,N\}$). The lower bound was improved to $N^{1/2}\ll \ell(N)$ by Komlós, Sulyok, and Szemerédi [KSS75]. The correct constant is unknown, but it is likely that the upper bound is true, so that $\ell(N)\sim N^{1/2}$.