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.
If \(A\subseteq\{1, ..., N\}\) with \(|A| = n\) is such that the subset sums \(\sum_{a\in S}a\) are distinct for all \(S\subseteq A\) then \[ N \gg 2 ^ n. \] This conjecture is false. A machine-checked disproof constructs sum-distinct sets…
If \(A \subset \mathbb{N}\) has \(\sum_{n \in A}\frac 1 n = \infty\), then must \(A\) contain arbitrarily long arithmetic progressions? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26]; see the linked Lean proof.
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)\)
minimum overlap problem
Find the value of the limit of MinOverlapQuotient!
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…
sum-product problem
Let \(A\) be a finite set of integers. Is it true that for every \(\epsilon>0\) \(\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\)
Let \(A\) be a finite set of integers. Is it true that, for every \(k\), if \(\lvert A\rvert\) is sufficiently large depending on \(k\), then there are least \(\lvert A\rvert^k\) many integers which are either the sum or product of…
Erdős sumset conjecture
Any \(A\subseteq \mathbb{N}\) of positive upper density contains a sumset \(B+C\) where both \(B\) and \(C\) are infinite. The Erdős sumset conjecture. Proved by Moreira, Richter, and Robertson [MRR19].
Asserts that for any number of colors r and any progression length k, there always exists some number N large enough to guarantee a monochromatic arithmetic progression. In other words, the set monoAP_guarantee_set is non-empty. This is…
Szemerédi's theorem
**Erdős Problem 139**: Let \(r_k(N)\) be the size of the largest subset of \({1,...,N}\) which does not contain a non-trivial \(k\)-term arithmetic progression. Prove that \(r_k(N) = o(N)\).
Let \(k≥3\). Are there \(k\) consecutive primes in arithmetic progression?
Prove an asymptotic formula for \(r_k(N)\), the largest possible size of a subset of \(\{1, \dots, N\}\) that does not contain any non-trivial \(k\)-term arithmetic progression. That is, find \(f_k\) with \(r_k(N) / f_k(N) \to 1\) as…
Is it true that for every \(k \geq 1\) we have \[ F(N + k) \leq F(N) + 1 \] for all sufficiently large \(N\)?
On [Mathoverflow](https://mathoverflow.net/a/410815) user [leechlattice](https://mathoverflow.net/users/125498/leechlattice) shows that \(h(n) \ll n^{\frac 2 3}\).
What is the limit \(F(N)/N\) as \(N \to \infty\)?
sparse ruler problem
The problem is to determine the limit of the sequence \(\frac{F(N)}{\sqrt{N}}\) as \(N \to \infty\).
density Hales-Jewett
Is it true that for every \(\epsilon>0\) and integer \(t\geq 1\), if \(N\) is sufficiently large and \(A\) is a subset of \([t]^N\) of size at least \(\epsilon t^N\) then \(A\) must contain a combinatorial line \(P\) (a set…
Is it true that in any finite colouring of \(\mathbb{N}\) there exist arbitrarily large finite \(A\) such that all sums and products of distinct elements in \(A\) are the same colour?
Let \(f_3(n)\) be the maximal size of a subset of \(\{0,1,2\}^n\) which contains no three points on a line. Is it true that \(f_3(n)=o(3^n)\)? Originally considered by Moser. It is trivial that \(f_3(n)\geq R_3(3^n)\), the maximal size of…
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…
Green-Tao theorem
Are there arbitrarily long arithmetic progressions of primes? Solution: yes. Ref: Green, Ben and Tao, Terence, _The primes contain arbitrarily long arithmetic progressions_
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].
Let \(A\subseteq\mathbb{N}\) be an infinite set such that \(|A\cap \{1, ..., N\}| = o(N)\). Is it true that \[ \limsup_{N\to\infty}\frac{|(A + A)\cap \{1, ..., N\}|}{|A \cap \{1, ..., N\}|} \geq 3? \] The answer is yes, proved by Freiman…
Stanley sequences
Let \(N\geq 1\). What is the largest \(t\) such that there are \(A_1,\ldots,A_t\subseteq \{1,\ldots,N\}\) with \(A_i\cap A_j\) a non-empty arithmetic progression for all \(i\neq j\)?
Suppose \(A\subseteq\mathbb{N}\) and \(C>0\) is such that \(1_A\ast 1_A(n)\leq C\) for all \(n\in\mathbb{N}\). Can \(A\) be partitioned into \(t\) many subsets \(A_1,\ldots,A_t\) (where \(t=t(C)\) depends only on \(C\)) such that…
Let \(A,B\subseteq \mathbb{N}\) such that for all large \(N\[\)\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}\]and\[\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.\] Is it true that there are infinitely many solutions to…
Let \(A\subseteq \mathbb{N}\) be an additive basis (of any finite order) such that \(\lvert A\cap \{1,\ldots,N\}\rvert=o(N)\). Is it true that \[ \lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert} {\lvert A\cap…
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…
If A ⊂ ℕ is a finite set of integers all of whose subset sums are distinct then ∑ n ∈ A, 1/n < 2. Proved by Ryavec. This was proved by Ryavec, who did not appear to ever publish the proof. Ryavec's proof is reproduced in [BeEr74]. More…
Let \(A\subseteq \mathbb{F}_p\). Let \[ A\hat{+}A = \{ a+b : a\neq b \in A\}. \] Is it true that \[ \lvert A\hat{+}A\rvert \geq \min(2\lvert A\rvert-3,p)? \] This is the Erdős-Heilbronn inequality, proved by Dias da Silva and Hamidoune.
Let \(f(k)\) be the minimal \(N\) such that if \(\{1,\ldots,N\}\) is \(k\)-coloured then there is a monochromatic solution to \(a+b=c\). Estimate \(f(k)\). In particular, is it true that \(f(k) < c^k\) for some constant \(c>0\)? The…
Prove that there exists an absolute constant \(c>0\) such that, whenever \(\{1,\ldots,N\}\) is \(k\)-coloured (and \(N\) is large enough depending on \(k\)) then there are at least \(cN\) many integers in \(\{1,\ldots,N\}\) which are…
Let \(h(n)\) be maximal such that, for any set \(A\subseteq \mathbb{N}\) of size \(n\), the set\[\left\{ \frac{a}{(a,b)}: a,b\in A\right\}\]has size at least \(h(n)\). Estimate \(h(n)\).
If ℕ is \(2\)-coloured then there must exist a monochromatic three-term arithmetic progression \(x,x+d,x+2d\) such that \(d>x\). This was first proved by Brown and Landman [BrLa99], who in fact show that this is always possible with…
Let \(\delta>0\) and \(N\) be sufficiently large depending on \(\delta\). Is it true that if \(A\subseteq \{1,\ldots,N\}^2\) has \(\lvert A\rvert \geq \delta N^2\) then \(A\) must contain the vertices of a square? A problem of Graham, if…
**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…
Let \(A\subseteq \mathbb{N}\) be such that \(A+A\) has positive upper density. Can one always decompose \(A=A_1\sqcup A_2\) such that \(A_1+A_1\) and \(A_2+A_2\) both have positive upper density? This was proved by the DeepMind prover…
Let \(\epsilon>0\). Does there exist \(A\subseteq \mathbb{N}\) such that the lower density of \(A+A\) is at least \(1-\epsilon\) and yet \(1_A\ast 1_A(n) \ll_\epsilon 1\) for all \(n\)?
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A(n) = cN+O(1)?\] A conjecture of Erdős and Turán. Erdős and Fuchs [ErFu56] proved that the answer is no in a strong form: in fact…
Let \(A\subseteq \mathbb{N}\). Can there exist some constant \(c>0\) such that \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+O(1)?\] The case of \(1_A\ast 1_A(n)\) is the subject of [763](https://www.erdosproblems.com/763). The answer is…
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…
Let \(f(k)\) be the minimal \(n\) such that any \(2\)-colouring of \(\{1,\ldots,n\}\) contains a monochromatic \(k\)-term descending wave: a sequence \(x_1<\cdots <x_k\) such that, for \(1<j<k\), \[x_j \geq \frac{x_{j+1}+x_{j-1}}{2}.\]…
exact additive complements
Let \(A,B\subseteq \mathbb{N}\) be infinite sets of positive integers such that \(A+B\) contains all large integers. Let \(A(x)=\lvert A\cap [1,x]\rvert\) and similarly for \(B(x)\). Is it true that if \(A(x)B(x)\sim x\) then…
Let \(g(n)\) be maximal such that given any set \(A\subset \mathbb{R}\) with \(\lvert A\rvert=n\) there exists some \(B\subseteq A\) of size \(\lvert B\rvert\geq g(n)\) such that \(b_1+b_2\not\in A\) for all \(b_1\neq b_2\in B\). Estimate…
Let \(h(n)\) be maximal such that if \(A\subseteq \mathbb{Z}\) with \(\lvert A\rvert=n\) then there is \(B\subseteq A\) with \(\lvert B\rvert \geq h(n)\) such that if \(a_1+\cdots+a_r=b_1+\cdots+b_s\) with \(a_i,b_i\in B\) then \(r=s\).…
Let \(A\subseteq \{1,\ldots,n\}\) with \(\lvert A\rvert \leq n^{1/2}\). Must there exist some \(B\subset\mathbb{Z}\) with \(\lvert B\rvert=o(n^{1/2})\) such that \(A\subseteq B+B\)? A problem of Erdős and Newman [ErNe77], who proved that…
Let \(A\) be a finite set of integers such that \(\lvert A+A\rvert \ll \lvert A\rvert\). Is it true that \[\lvert AA\rvert \gg \frac{\lvert A\rvert^2}{(\log \lvert A\rvert)^C}\] for some constant \(C>0\)? This was proved by Solymosi…
Let \(f(N)\) be maximal such that there exists \(A\subseteq \{1,\ldots,N\}\) with \(\lvert A\rvert=\lfloor N^{1/2}\rfloor\) such that \(\lvert (A+A)\cap [1,N]\rvert=f(N)\). Estimate \(f(N)\).
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 \subset \mathbb{N}\) be an infinite set for which there exists some \(\epsilon > 0\) such that in any subset of \(A\) of size \(n\) there is a subset of size at least \(\epsilon n\) which contains no three-term arithmetic…
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…
There exists a constant \(C>0\) such that, for all large \(N\), if \(A\subseteq \{1,\ldots,N\}\) has size at least \(\frac{5}{8}N+C\) then there are distinct \(a,b,c\in A\) such that \(a+b,a+c,b+c\in A\). A problem of Erdős and Sós (also…
Is it true that if \(A=\{a_1<\cdots <a_t\}\subseteq \{1,\ldots,N\}\) has no solutions to \[a_i+a_{i+1}+\cdots+a_j\in A\] then \[\lvert A\rvert \leq \frac{N}{2}+O(1)?\] In fact this problem is false. Freud [Fr93] constructed a sequence with…
Let \(f_m(n)\) count the number of maximal sum-free subsets \(A\subseteq\{1,\ldots,n\}\) - that is, there are no solutions to \(a=b+c\) in \(A\) and \(A\) is maximal with this property. Estimate \(f(n)\) - is it true that…
Is it true that, for all sufficiently large \(n\), if \(G\) is a triangle-free graph on \(\{1,\ldots,n\}\) then there must exist three independent points \(a,b,a+b\)? A problem of Erdős and Hajnal [Er95d]. The stated problem has been…
Let \(A\subseteq\mathbb{N}\) be an infinite set such that \(|A\cap \{1, ..., N\}| = o(N)\). Is it true that \[ \limsup_{N\to\infty}\frac{|(A - A)\cap \{1, ..., N\}|}{|A \cap \{1, ..., N\}|} = \infty? \] The answer is yes, proved by Ruzsa…
Let \(k,r\geq 2\). Does there exist a set \(A\subseteq \mathbb{N}\) that contains no non-trivial arithmetic progression of length \(k+1\), yet in any \(r\)-colouring of \(A\) there must exist a monochromatic non-trivial arithmetic…
The main conjecture: for any finite set of integers \(A\) with \(|A| = n\), the number of distinct common differences in three-term arithmetic progressions is \(O(n^{3/2})\). This conjecture was resolved negatively by showing that the…
Let \(A=\{1\leq a_1 < a_2 < \cdots\}\) and \(B=\{1\leq b_1 < b_2 < \cdots\}\) be sets of integers with \(a_n/b_n\to 1\). If \(A+B\) contains all sufficiently large positive integers then is it true that \(\limsup 1_A\ast 1_B(n)=\infty\)? A…
Let \(0<\epsilon<1\) and let \(g_\epsilon(N)\) be the minimal \(k\) such that if \(G\) is an abelian group of size \(N\) and \(A\subseteq G\) is a uniformly random subset of size \(k\), and \[F_A(g) = \#\left\{ S\subseteq A : g =…
Let \(\delta_k\) be such that in any \(2\)-colouring of \(\{1,\ldots,n\}\) there exist at least \((\delta_k+o(1))n^2\) many monochromatic \(k\)-term arithmetic progressions. Give reasonable bounds (or even an asymptotic formula) for…
Let \(k\geq 3\). Is it true that, in any finite colouring of the integers, there are monochromatic arithmetic progressions of primes of length \(k\)? It follows from the theorem of Green and Tao [GrTa08] (that any set of primes with…
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 there exist, for all \(r\geq 2\), a basis \(A\) of order \(r\) (so that \(f_r(n)>0\) for all large \(n\)) such that \[\sum_{n\leq x}f_r(n)^2 \ll x\] for all \(x\)?
Let \(A\subset \mathbb{N}\) and let \(g(n)\) be a non-decreasing function of \(n\) which is always \(>0\). Is the lower density of \[\{ n : 1_A\ast 1_A(n)=g(n)\}\] always \(0\)? The answer is trivially no to both questions: indeed if…
If \(\mathbb{N}\) is \(2\)-coloured, must there exist an infinite set \(A=\{a_1<a_2<\cdots\}\) such that all expressions of the shape \[\sum_{j=1}^{k}\prod_{i\in S_j}a_i,\] for \(k\geq 1\) and pairwise disjoint nonempty finite sets of…
Is it true that in any 2-colouring of \(\mathbb{N}\) there exists an infinite set \(A\) such that all elements of \(A+A\) are the same colour? A conjecture of Owings [Ow74].
Let \(a,K\geq 1\). Does there exist \(f(a,K)\) such that if \(a=a_1<\cdots <a_s\) is a sequence of integers with \(a_s> f(a,K)\) and with bounded gaps \(a_{i+1}-a_i\leq K\) then there are two distinct intervals \(I\) and \(J\) such that…