Logo
All Random Solved Random Open
5 solved out of 28 shown (show only solved or open)
OPEN
Let $A\subseteq \mathbb{N}$. Let $B\subseteq \mathbb{N}$ be the set of integers which are representable in exactly one way as the sum of two elements from $A$.

Is it true that for all $\epsilon>0$ and large $N$ \[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/2-\epsilon}.\] Is it true that \[\lvert \{1,\ldots,N\}\backslash B\rvert =o(N^{1/2})?\]

Apparently originally considered by Erdős and Nathanson, although later Erdős attributes this to Erdős, Sárközy, and Szemerédi (but gives no reference), and claims a construction of an $A$ such that for all $\epsilon>0$ and all large $N$ \[\lvert \{1,\ldots,N\}\backslash B\rvert \ll_\epsilon N^{1/2+\epsilon},\] and yet there for all $\epsilon>0$ there exist infinitely many $N$ where \[\lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/3-\epsilon}.\]

Erdös and Freud investigated the finite analogue in 'a recent Hungarian paper', proving that there exists $A\subseteq \{1,\ldots,N\}$ such that the number of integers not representable in exactly one way as the sum of two elements from $A$ is $<2^{3/2}N^{1/2}$, and suggest the constant $2^{3/2}$ is perhaps best possible.

OPEN - $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)?\]
A problem of Erdős and Turán. 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$.

See also [241] and [840].

Additional thanks to: Zach Hunter
OPEN - $500
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)$.

Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that \[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\] for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

OPEN - $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.\]
Additional thanks to: Zachary Chase
OPEN
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\}$?
OPEN - $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$?
OPEN
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}$?
See also [707].
OPEN
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.
Additional thanks to: Cedric Pilatte
OPEN
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.
SOLVED
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]. It follows immediately using the Sidon property that $A+A$ is similarly well-distributed.
Additional thanks to: Zach Hunter
OPEN
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}$.
OPEN
Does there exist a maximal Sidon set $A\subset \{1,\ldots,N\}$ of size $O(N^{1/3})$?
A question of Erdős, Sárközy, and Sós [ESS94]. It is easy to prove that a maximal Sidon set in $\{1,\ldots,N\}$ has size $\gg N^{1/3}$. Ruzsa [Ru98b] constructed a maximal Sidon set of size $\ll (N\log N)^{1/3}$.
SOLVED
Does there exist an infinite Sidon set which is an asymptotic basis of order 3?
Yes, as shown by Pilatte [Pi23].
OPEN
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.
SOLVED
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].
OPEN - $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 coincidences). 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$).

More generally, Bose and Chowla conjectured that the maximum size of $A\subseteq \{1,\ldots,N\}$ with all $r$-fold sums distinct (aside from the trivial coincidences) then \[\lvert A\rvert \sim N^{1/r}.\] This is known only for $r=2$ (see [30]).

Additional thanks to: Cedric Pilatte
OPEN
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 asked about the difference set $A-A$, whether this has positive density, and whether this contains $22$. It does contain $22$, since $a_{15}-a_{14}=204-182=22$. The smallest integer which is unknown to be in $A-A$ is $33$. It may be true that all or almost all integers are in $A-A$.

This sequence is at OEIS A005282.

Additional thanks to: Vjekoslav Kovac
OPEN
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}?\]

If $A\subseteq \{1,\ldots,n\}$ is such that all products $a_1\cdots a_r$ are distinct for $a_1<\cdots <a_r$ then is it true that \[\lvert A\rvert \leq \pi(n)+O(n^{\frac{r+1}{2r}})?\]

Erdős [Er68] proved that there exist some constants $0<c_1\leq c_2$ such that \[\pi(n)+c_1 n^{3/4}(\log n)^{-3/2}\leq F(n)\leq \pi(n)+c_2 n^{3/4}(\log n)^{-3/2}.\] Surprisingly, if we consider the corresponding problem in the reals (so consider the largest $A\subset [1,x]$ such that for any distinct $a,b,c,d\in A$ we have $\lvert ab-cd\rvert \geq 1$) then Alexander proved that $\lvert A\rvert> x/8e$ is possible (disproving an earlier conjecture of Erdős [Er73] that $m=o(x)$). Alexander's construction seems to be unpublished, and I have no idea what it is.

See also [490], [793], and [796].

Additional thanks to: Rishika Agrawal
OPEN
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)$.

In particular, is it true that $\ell(N)\sim N^{1/2}$?

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}$.

In [AlEr85] Alon and Erdős make the stronger conjecture that perhaps $A$ can always be written as the union of at most $(1+o(1))N^{1/2}$ many Sidon sets. (This is easily verified for $A=\{1,\ldots,N\}$ using standard constructions of Sidon sets.)

OPEN - $500
Let $A\subset \mathbb{N}$ be a finite Sidon set. Is there some set $B$ with $A\subseteq B$ which is perfect difference set modulo $p^2+p+1$ for some prime $p$?
See also [44] and [329].
OPEN
Let $A\subset \mathbb{R}_{>0}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert =4$ has $\lvert B-B\rvert\geq 11$. Find the best constant $c>0$ such that $A$ must always contain a Sidon set of size $\geq cn$.
For comparison, note that if $B$ were a Sidon set then $\lvert B-B\rvert=13$, so this condition is saying that at most one difference is 'missing' from $B-B$. Equivalently, one can view $A$ as a set such that every four points determine at least five distinct distances, and ask for a subset with all distances distinct.

Erdős and Sós proved that $c\geq 1/2$. Gyárfás and Lehel [GyLe95] proved \[\frac{1}{2}<c<\frac{3}{5}.\] (The example proving the upper bound is the set of the first $n$ Fibonacci numbers.)

SOLVED
Let $k\geq 1$ and $H_k(n)$ be the maximal $r$ such that if $A\subset\mathbb{N}$ has $\lvert A\rvert=n$ and $\| 1_A\ast 1_A\|_\infty \leq k$ then $A$ contains a Sidon set of size at least $r$.

Is it true that $H_k(n)/n^{1/2}\to \infty$? Or even $H_k(n) > n^{1/2+c}$ for some constant $c>0$?

Erdős [Er84d] proved that \[H_k(n) \ll n^{2/3}\] (where the implied constant is absolute). The lower bound $H_k(n)\gg n^{1/2}$ follows from the fact that any set of size $n$ contains a Sidon set of size $\gg n^{1/2}$ (see [530]).

The answer is yes, and in fact \[H_k(n) \gg_k n^{2/3},\] proved by Alon and Erdős [AlEr85]. We sketch their proof as follows: take a random subset $A'\subset A$, including each $n\in A'$ with probability $\asymp n^{-1/3}$. The number of non-trivial additive quadruples in $A$ is $\ll n^2$ and hence only $\ll n^{2/3}$ non-trivial additive quadruples remain in $A'$. Since the size of the random subset is $\gg n^{2/3}$, all of the remaining non-trivial additive quadruples can be removed by removing at most $\lvert A'\rvert/2$ (choosing the constants suitably).

Additional thanks to: Noga Alon
OPEN
What is the size of the largest Sidon subset $A\subseteq\{1,2^2,\ldots,N^2\}$? Is it $N^{1-o(1)}$?
A question of Alon and Erdős [AlEr85], who proved $\lvert A\rvert \geq N^{2/3-o(1)}$ is possible (via a random subset), and observed that \[\lvert A\rvert \ll \frac{N}{(\log N)^{1/4}},\] since (as shown by Landau) the density of the sums of two squares decays like $(\log N)^{-1/2}$.
OPEN
Let $f(N)$ be the size of the largest quasi-Sidon subset $A\subset\{1,\ldots,N\}$, where we say that $A$ is quasi-Sidon if \[\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}.\] How does $f(N)$ grow?
Considered by Erdős and Freud [ErFr91], who proved \[\left(\frac{2}{\sqrt{3}}+o(1)\right)N^{1/2} \leq f(N) \leq \left(2+o(1)\right)N^{1/2}.\] Note that $2/\sqrt{3}=1.15\cdots$. The lower bound is taking a genuine Sidon set $B\subset [1,N/3]$ of size $\sim N^{1/2}/\sqrt{3}$ and taking the union with $\{N-b : b\in B\}$. The upper bound was improved by Pikhurko [Pi06] to \[f(N) \leq \left(\left(\frac{1}{4}+\frac{1}{(\pi+2)^2}\right)^{-1/2}+o(1)\right)N^{1/2}\] (the constant here is $=1.863\cdots$).

The analogous question with $A-A$ in place of $A+A$ is simpler, and there the maximal size is $\sim N^{1/2}$, as proved by Cilleruelo.

See also [30], [819], and [864].

Additional thanks to: Terence Tao
SOLVED
Let $f(N)$ be the size of the largest Sidon subset of $\{1,\ldots,N\}$ and $A(N)$ be the number of Sidon subsets of $\{1,\ldots,N\}$. Is it true that \[A(N)/2^{f(N)}\to \infty?\] Is it true that \[A(N) = 2^{(1+o(1))f(N)}?\]
A problem of Cameron and Erdős. It is known that $f(N)\sim N^{1/2}$ and conjectured (see [30]) that $f(N)=N^{1/2}+O(N^{\epsilon})$.

While $A(N)$ has not been completely determined, both of these questions are now settled, the first positively and the second negatively. The current best bounds are (for large $N$) \[2^{1.16f(N)}\leq A(N) \leq 2^{6.442f(N)}.\] The lower bound is due to Saxton and Thomason [SaTh15], the upper bound is due to Kohayakawa, Lee, Rödl, and Samotij [KLRS].

See also [862].

OPEN
Let $A_1(N)$ be the number of maximal Sidon subsets of $\{1,\ldots,N\}$. Is it true that \[A_1(N) < 2^{o(N^{1/2})}?\] Is it true that \[A_1(N) > 2^{N^c}\] for some constant $c>0$?
A problem of Cameron and Erdős.

See also [861].

OPEN
Let $r\geq 2$ and let $A\subseteq \{1,\ldots,N\}$ be a set of maximal size such that there are at most $r$ solutions to $n=a+b$ with $a\leq b$ for any $n$. (That is, $A$ is a $B_2[r]$ set.)

Similarly, let $B\subseteq \{1,\ldots,N\}$ be a set of maximal size such that there are at most $r$ solutions to $n=a-b$ for any $n$.

If $\lvert A\rvert\sim c_rN^{1/2}$ as $N\to \infty$ and $\lvert B\rvert \sim c_r'N^{1/2}$ as $N\to \infty$ then is it true that $c_r\neq c_r'$ for $r\geq 2$? Is it true that $c_r'<c_r$?

According to Erdős, first formulated in conversation with Berend, and later independently reformulated with Freud.

It is true that $c_1=c_1'$, and the classical bound on the size of Sidon sets (see [30]) implies $c_1=c_1'=1$.

OPEN
Let $A\subseteq \{1,\ldots N\}$ be a set of maximal size such that there exists at most $n$ with more than one solution to $n=a+b$ (with $a\leq b$). Estimate $\lvert A\rvert$ - in particular, is it true that \[\lvert A\rvert \leq (1+o(1))\frac{2}{\sqrt{3}}N^{1/2}?\]
A problem of Erdős and Freud, who prove that \[\lvert A\rvert \geq (1+o(1))\frac{2}{\sqrt{3}}N^{1/2}.\] This is shown by taking a genuine Sidon set $B\subset [1,N/3]$ of size $\sim N^{1/2}/\sqrt{3}$ and taking the union with $\{N-b : b\in B\}$.

For the analogous question with $n=a-b$ they prove that $\lvert A\rvert\sim N^{1/2}$.

This is a weaker form of [840].