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 [ErFr91], 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.

View the LaTeX source

This page was last edited 14 September 2025.

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}$. This was further optimised by O'Bryant [OB22]. The current record is\[h(N)\leq N^{1/2}+0.98183N^{1/4}+O(1),\]due to Carter, Hunter, and O'Bryant [CHO25].

Singer [Si38] was the first to show that $h(N)\geq (1-o(1))N^{1/2}$ for all $N$. For a detailed survey of the literature we refer to [OB04].

See also [241] and [840].

This problem is Problem 31 on Green's open problems list.

This is discussed in problem C9 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 19 October 2025.

The trivial greedy construction achieves $\gg N^{1/3}$. The first improvement on this was achieved by Ajtai, Komlós, and Szemerédi [AKS81b], who found an infinite Sidon set with growth rate $\gg (N\log 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$. Later he [Er77c] offered \$100 for a construction which achieves $\omega(N)N^{1/3}$ for some $\omega(N)\to \infty$.

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.\]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$.

This is discussed in problem C9 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

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.\]This is discussed in problem C11 of Guy's collection [Gu04], in which Guy says Erdős offered \$500 for the general problem of whether, for all $h\geq 2$,\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/h}}=0\]whenever the sum of $h$ terms in $A$ are distinct. This was proved for $h=4$ by Nash [Na89] and for all even $h$ by Chen [Ch96b].

View the LaTeX source

This page was last edited 30 September 2025.

View the LaTeX source

This page was last edited 14 September 2025.

Since it is known that $f(N)\sim \sqrt{N}$ (see [30]) the latter question is equivalent to asking whether, if $\lvert A\rvert=\lvert B\rvert$,\[\lvert A\rvert \leq \left(\frac{1}{\sqrt{2}}-c+o(1)\right)\sqrt{N}\]for some constant $c>0$. In the comments Tao has given a proof of this upper bound without the $-c$.

View the LaTeX source

This page was last edited 03 December 2025.

See also [329] and [707] (indeed a positive solution to [707] implies a positive solution to this problem, which in turn implies a positive solution to [329]).

This is discussed in problem C9 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

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

View the LaTeX source

A similar problem can be asked for infinite Sidon sets.

View the LaTeX source

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.

View the LaTeX source

This may even hold with $k\approx \epsilon N^{1/2}$.

View the LaTeX source

A question of Erdős, Sárközy, and Sós [ESS94]. It is easy to prove that the greedy construction of 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}$.

See also [340].

View the LaTeX source

Yes, as shown by Pilatte [Pi23].

View the LaTeX source

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

View the LaTeX source

The answer is no; Erdős and Graham report this was proved by Baumgartner, presumably referring to the paper [Ba75], which does not state this exactly, but the following simple construction is implicit in [Ba75].

Let $P_1,P_2,\ldots$ be an enumeration of all countably many infinite arithmetic progressions. We choose $a_1$ to be the minimal element of $P_1\cap \mathbb{N}$, and in general choose $a_n$ to be an element of $P_n\cap \mathbb{N}$ such that $a_n>2a_{n-1}$. By construction $A=\{a_1<a_2<\cdots\}$ contains at least one element from every infinite arithmetic progression, and is a lacunary set, so is certainly Sidon.

AlphaProof has found the following explicit construction:\[A = \{ (n+1)!+n : n\geq 0\}.\]This is a Sidon set, and intersects every arithmetic progression, since for any $a,d\in \mathbb{N}$,\[(a+d+1)!+(a+d)\in A,\]and $d$ divides $(a+d+1)!+d$.

See also [199].

This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.

View the LaTeX source

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

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]).

This is discussed in problem C11 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

Erdős proved that $1/2$ is possible and Krückeberg [Kr61] proved $1/\sqrt{2}$ is possible. Erdős and Turán [ErTu41] have proved this $\limsup$ is always $\leq 1$.

The fact that $1$ is possible would follow if any finite Sidon set is a subset of a perfect difference set (see [44] and [707]).

This question can also be asked for $B_2[g]$ sequences (i.e. where the number of solutions to $n=a_1+a_2$ with $a_1\leq a_2$ is at most $g$ for all $n$, so that a $B_2[1]$ set is a Sidon set). Kolountzakis [Ko96] constructed a $B_2[2]$ sequence where the $\limsup$ is $1$, and for larger $g$ constructions were provided by Cilleruelo and Trujillo [CiTr01].

View the LaTeX source

This page was last edited 18 November 2025.

This sequence is sometimes called the Mian-Chowla sequence. It is trivial that this sequence grows at least like $\gg N^{1/3}$.

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$ (see A080200). It may be true that all or almost all integers are in $A-A$.

This sequence is at OEIS A005282.

See also [156].

View the LaTeX source

This page was last edited 18 November 2025.

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}.\]This problem can also be considered in the real numbers: that is, what is the size of the 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$? Erdős had conjectured (see [Er73] and [Er77c]) that $\lvert A\rvert=o(x)$.

In [ErGr80] Erdős and Graham report that Alexander had given a construction disproving this conjecture, establishing that $\lvert A\rvert\gg x$ is possible. Alexander's construction is given in [Er80], and we sketch a simplified version. Let $B\subseteq [1,X^2]$ be a Sidon set of integers of size $\gg X$ and\[A=\{ X e^{b/X^2} : b\in B\}.\]It is easy to check that\[\lvert ab-cd\rvert \geq X^2\lvert 1-e^{1/X^2}\rvert \gg 1\]for distinct $a,b,c,d\in A$, and (after rescaling $A$ by some constant factor) this produces a set of size $\gg X$ with the desired property in the interval $[X,O(X)]$. Furthermore, a simple modification allows for $A$ to also be $1$-separated.

In [Er77c] Erdős considers a similar generalisation for sets of complex numbers or complex integers.


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

View the LaTeX source

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.)

This is discussed in problem C9 of Guy's collection [Gu04].

See also [1088] for a higher-dimensional generalisation.

View the LaTeX source

This page was last edited 16 October 2025.

See also [44] and [329] (indeed a positive solution to this problem implies a positive solution to [44], and thence also to [329]).

This is discussed in problems C9 and C10 of Guy's collection [Gu04], and was also asked by Erdős in the 1991 problem session of Great Western Number Theory. The prize of \$1000 was offered in [Er80] for a proof or disproof of this conjecture. In some sources (such as [Er77c]) Erdős weakens this to whether any finite Sidon set can be contained in the perfect difference set modulo $m^2+m+1$ for some (not necessarily prime) $m$. In [Er97c] he admits this conjecture is 'perhaps too optimistic'.

Alexeev and Mixon [AlMi25] have disproved this conjecture, proving that $\{1,2,4,8\}$ cannot be extended to a perfect difference set modulo $p^2+p+1$ for any prime $p$, and also that $\{1,2,4,8,13\}$ cannot be extended to any perfect difference set. Their proof has been formalised in Lean with the assistance of ChatGPT.

Surprisingly, they discovered that this conjecture was actually first disproved by Hall in 1947 [Ha47], long before Erdős asked this question. Hall proved that $\{1,3,9,10,13\}$ cannot be extended to any perfect difference set.

It is trivial that any Sidon set of size $2$ can be extended to a perfect difference set. In a discussion on MathOverflow, Sawin has proved that any Sidon set of size $3$ can also be extended. It remains open whether any Sidon set of size $4$ can be extended to a perfect difference set, but in the same MathOverflow discussion Mueller has shown that $\{0,1,3,11\}$ is a candidate counterexample, in that all the known ways to construct perfect difference sets cannot succeed.

View the LaTeX source

This page was last edited 26 October 2025.

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.)

View the LaTeX source

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).

View the LaTeX source

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}$. The lower bound was improved to\[\lvert A\rvert \gg N^{2/3}\]by Lefmann and Thiele [LeTh95].

View the LaTeX source

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}.\](Although both bounds were already given by Erdős in [Er81h].) 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].

View the LaTeX source

This page was last edited 19 October 2025.

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 [KLRS15].

See also [862].

This is discussed in problem C9 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 15 October 2025.

A problem of Cameron and Erdős.

See also [861].

View the LaTeX source

This page was last edited 18 November 2025.

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

View the LaTeX source

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].

View the LaTeX source