Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
Let \(A ⊆ \mathbb{N}\). Let \(B ⊆ \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\),…
Is it true that, for every \(\varepsilon > 0\), \(h(N) = \sqrt N + O_{\varepsilon}(N^\varepsilon)\)
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 \(\varepsilon > 0\)?
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_{N \to \infty} \frac{\lvert A \cap…
**Erdős Problem 42**: Let M ≥ 1 and N be sufficiently large in terms of M. Is it true that for every maximal Sidon set A ⊆ {1,…,N} there is another Sidon set B ⊆ {1,…,N} of size M such that (A - A) ∩ (B - B) = {0}? This was proved for all…
If \(A\) and \(B\) are Sidon sets in \(\{1,\ldots,N\}\) with \((A-A)\cap(B-B)=\{0\}\), is it true that \[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?\] The answer is no; the Erdős Problems page notes that…
**Erdős Problem 44:** Let N ≥ 1 and A ⊆ {1,…,N} be a Sidon set. Is it true that, for any ε > 0, there exist M = M(ε) and B ⊆ {N+1,…,M} such that A ∪ B ⊆ {1,…,M} is a Sidon set of size at least (1−ε)M^{1/2}? This problem asks whether any…
Must lim f n = ∞? This was proved formally by the DeepMind prover agent [DM26a].
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\)?
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? The answer is yes.…
Is it true that for every \(k \geq 1\) we have \[ F(N + k) \leq F(N) + 1 \] for all sufficiently large \(N\)?
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].
Does there exist an infinite Sidon set which is an asymptotic basis of order \(3\)? Yes, as shown by Pilatte [Pi23].
Let A be an infinite B₂[2] set. Must liminf |A ∩ {1, ..., N}| * N ^ (- 1 / 2) = 0?
Let \(V\) be a vector space over the rationals and let \(k\) be a fixed positive integer. Then there is a set \(X_k \subseteq V\) such that \(X_k\) meets every infinite arithmetic progression in \(V\) but \(X_k\) intersects every…
Is it true that \(f(N)\sim N^{1/3}\)? Originally asked to Erdős by Bose. This is discussed in problem C11 of Guy's collection [Gu04].
Does there exist a polynomial \(f(x)\in\mathbb{Z}[x]\) such that all the sums \(f(a)+f(b)\) with \(a < b\) nonnegative integers are distinct?
**Erdős Problem 329.** Let A ⊆ ℕ be a Sidon set. How large can lim sup_{N → ∞} |A ∩ {1,…,N}| / N^{1/2} be?
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 (i.e. there are no non-trivial solutions…
Is there a polynomial \(f:\mathbb{Z}\to \mathbb{Z}\) of degree at least \(2\) and a set \(A\subset \mathbb{Z}\) such that for any \(n\in \mathbb{Z}\) there is exactly one \(a\in A\) and \(b\in \{ f(k) : k\in\mathbb{Z}\}\) such that…
**Erdős Problem 707**: It is false that any finite Sidon set can be embedded in a perfect different set modulo some \(n\). As described in [arxiv/2510.19804], a counterexample is provided in [Ha47], see below. The proof of this has been…
What is the supremum of the set of admissible numbers?
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…
What is the size of the largest Sidon subset \(A\subseteq\{1,2^2,\ldots,N^2\}\)? Is it \(N^{1-o(1)}\)?
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? Following [Er81h, p. 175], we…
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})}?\] A problem of Cameron and Erdős. This is resolved as a consequence of results of Saxton and Thomason [SaTh15] - they…
Let \(A\subseteq \{1,\ldots,N\}\) be a set such that there exists at most one \(n\) with more than one solution to \(n=a+b\) (with \(a\leq b\in A\)). Estimate the maximal possible size of \(|A|\). In particular, is it true that \[|A| \leq…
Let \(A\subset\mathbb{N}\) be an infinite Sidon set. Is it true that \[\liminf_{x\to \infty} \frac{\lvert A\cap [1,x]\rvert}{x^{1/2}}(\log x)^{1/2}=0?\] Here \(x\) runs over \(\mathbb{N}\) and the \(\liminf\) is taken in ℝ≥0∞, so that it…
Does \(\{1,2^3,\ldots,N^3\}\) contain a Sidon set of size \(\gg N\)?