Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
2 solved out of 17 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]. 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$.
Additional thanks to: Zachary Hunter
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 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?\] Is it true that \[\limsup \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/3}}=\infty?\]
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.\]
Let $M\geq 1$ and $N$ be sufficiently large in terms of $M$. Is it true that for every maximal Sidon set $A\subset \{1,\ldots,N\}$ there is another Sidon set $B\subset \{1,\ldots,N\}$ of size $M$ such that $(A-A)\cap(B-B)=\{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$?
Let $N\geq 1$ and $A\subset \{1,\ldots,N\}$ be a Sidon set. Is it true that, for any $\epsilon>0$, there exist $M=M(\epsilon)$ and $B\subset \{N+1,\ldots,M\}$ such that $A\cup B\subset \{1,\ldots,M\}$ is a Sidon set of size at least $(1-\epsilon)M^{1/2}$?
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 finite Sidon sets.
Let $A$ be a finite Sidon set and $A+A=\{s_1<\cdots<s_t\}$. Is it true that \[\frac{1}{t}\sum_{1\leq i<t}(s_{i+1}-s_i)^2 \to \infty\] as $\lvert A\rvert\to \infty$?
A similar problem can be asked for infinite Sidon sets.
Let $A\subset \{1,\ldots,N\}$ be a Sidon set with $\lvert A\rvert\sim N^{1/2}$. Must $A+A$ be well-distributed over all small moduli? In particular, must about half the elements of $A+A$ be even and half odd?
Lindström [Li98] has shown this is true for $A$ itself, subsequently strengthened by Kolountzakis [Ko99].
Let $F(N)$ be the size of the largest Sidon subset of $\{1,\ldots,N\}$. Is it true that for every $k\geq 1$ we have \[F(N+k)\leq F(N)+1\] for all sufficiently large $N$?
This may even hold with $k\approx \epsilon N^{1/2}$.
Does there exist a maximal Sidon set $A\subset \{1,\ldots,N\}$ of size $O(N^{1/3})$?
Does there exist an infinite Sidon set which is an asymptotic basis of order 3?
Yes, as shown by Pilatte [Pi23].
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.
If $A\subset \mathbb{N}$ is a Sidon set then must the complement of $A$ contain an infinite arithmetic progression?
The answer is yes, as shown by Baumgartner [Ba75].
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.
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].