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.
**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…
Is it true that \(\limsup M_n = \infty\)? This is Problem 4.1 in [Ha74] where it is attributed to Erdős. The weaker conjecture that \(\limsup M_n=\infty\) was proved by Wagner [Wa80], who show that there is some \(c>0\) with…
Let \(R(3;k)\) be the minimal \(n\) such that if the edges of \(K_n\) are coloured with \(k\) colours then there must exist a monochromatic triangle. Determine \[\lim_{k\to \infty}R(3;k)^{1/k}.\] There is no finite limit:…
Let \(A=\{a_1,a_2,\ldots\}\subset \mathbb{R}^d\) be an infinite sequence such that \(a_{i+1}-a_i\) is a positive unit vector (i.e. is of the form \((0,0,\ldots,1,0,\ldots,0)\)). For which \(d\) must \(A\) contain a three-term arithmetic…
Let \(n_1<\cdots < n_r\leq N\) with associated \(a_i\pmod{n_i}\) such that the congruence classes are disjoint (that is, every integer is \(\equiv a_i\pmod{n_i}\) for at most one \(1\leq i\leq r\)). How large can \(r\) be in terms of…
Let \(A(N)\) denote the maximal cardinality of \(A\subseteq \{1,\ldots,N\}\) such that \(\sum_{n\in S}\frac{1}{n}\neq 1\) for all \(S\subseteq A\). Estimate \(A(N)\). Erdős and Graham [ErGr80] believe the answer is \(A(N)=(1+o(1))N\).…
There exists a set A with positive density that does not have property P₁. #TODO: prove this lemma by assuming erdos_318.contain_single_even. The density sits in an existential, so HasPosDensity is the *stronger* reading here and weakening…
If \(\tau(n)\) counts the number of divisors of \(n\), then what is the set of limit points of \[ \frac{\tau((n+1)!)}{\tau(n!)}? \] The limit points are exactly \(\{1\} \cup \{1+1/k : k \geq 1\}\).
Let \(f(u)\) be the largest \(v\) such that no \(m\in (u,v)\) is composed entirely of primes dividing \(uv\). Estimate \(f(u)\). The estimate \(u + 2 \le f(u) \le u^2\) holds for every \(u \ge 2\). The upper bound is attained when \(u\) is…
Dedekind's problem
How many antichains in \([n]\) are there? That is, how many families of subsets of \([n]\) are there such that, if \(\mathcal{F}\) is such a family and \(A,B\in \mathcal{F}\), then \(A\not\subseteq B\)? Sperner's theorem states that…
What is the size of the largest \(A\subseteq \mathbb{R}^n\) such that there are only two distinct distances between elements of \(A\)? That is, \[\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.\] Asked to Erdős by Coxeter. Bannai, Bannai, and…
**Erdős Problem 619** [EGR98, Er99]: For a triangle-free graph \(G\) let \(h_r(G)\) be the smallest number of edges that need to be added to \(G\) so that it has diameter \(r\) (while preserving the property of being triangle-free). Is it…
Let \(g(n)\) denote the largest \(t\) such that there exist integers \(2\leq a_1<a_2<\cdots <a_t <n\) such that \[P(a_1)>P(a_2)>\cdots >P(a_t)\] where \(P(m)\) is the greatest prime factor of \(m\). Estimate \(g(n)\). Stijn Cambie has…
Let \(f(m)\) be such that if \(A\subseteq \{1,\ldots,N\}\) has \(\lvert A\rvert=m\) then every interval in \([1,\infty)\) of length \(2N\) contains \(\geq f(m)\) many distinct integers \(b_1,\ldots,b_r\) where each \(b_i\) is divisible by…
Let \(f_\max(n)\) be the largest \(m\) such that \(\phi(m) = n\), and \(f_\min(n)\) be the smallest such \(m\), where \(\phi\) is Euler's totient function. Investigate \[ \max_{n\leq x}\frac{f_\max(n)}{f_\min(n)}. \] GPT-5.5 Pro (prompted…
Is it true that \(H(n)/h(n)\to \infty\) for almost all \(n\)? Formalised as: for every threshold \(M\), the set of \(n\) with \(h(n) > 0\) and \(H(n)/h(n) > M\) has natural density \(1\). This is false: in fact, \(H(n)/h(n) = 2 + o(1)\)…
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…
Give an asymptotic formula for \(\mathrm{ex}(n; C_4)\). Erdős and Klein [Er38] proved \(\mathrm{ex}(n; C_4) \asymp n^{3/2}\), and Reiman [Re58] proved \[\frac{1}{2\sqrt 2} \le \lim \frac{\mathrm{ex}(n; C_4)}{n^{3/2}} \le \frac12.\] Erdős…
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\) be an additive basis of order \(2\), let \(f(n)\) denote the number of ways in which \(n\) can be written as the sum of two elements from \(A\). If \(f(n) \to \infty\) as \(n \to \infty\), then must \(A\) contain a minimal…
What is the size of the largest \(A\subseteq \{1,\ldots,n\}\) such that if \(a\leq b\leq c\leq d\in A\) are such that \(abcd\) is a square then \(ad=bc\)? This was proved by GPT-5.5 Pro (prompted by Chojecki).
The dimension of a graph \(G\) is the minimal \(n\) such that \(G\) can be embedded in \(\mathbb{R}^n\) such that every edge of \(G\) is a unit line segment. What is the smallest number of edges in a graph with dimension \(4\)? Answer: The…
Let \(F(n)\) be the maximal size of a family of subsets of \(\{1,\ldots,n\}\) such that no set in this family is the union of other members of the family. Is it true that there is a constant \(c>0\) such that \[F(n)\sim c…
Let \(f\) be a function from all pairs of elements in \(\{1,\ldots,n\}\) to \(\{1,\ldots,n\}\) such that \(f(x,y)\neq x\) and \(\neq y\) for all \(x,y\). We call \(X\subseteq \{1,\ldots,n\}\) independent if whenever \(x,y\in X\) we have…
Let \(x_1,\ldots,x_n\) be a sequence of distinct real numbers. Determine \[ \max\left(\sum x_{i_r}\right), \] where the maximum is taken over all monotonic subsequences. This is as Erdős posed the problem in [Er71], which is rather…
Let \[H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert,\] where \(f\) ranges over all functions \(f:\{1,\ldots,n\}^2\to \{-1,1\}\). Estimate \(H(n)\). Erdős [Er63d] proved \[\frac{n}{4}\leq H(n)…
Let \(f(z)=\prod_{i=1}^n(z-z_i)\in\mathbb{C}[x]\) where \(\lvert z_i\rvert\leq 1\) for all \(i\). If \(\Lambda(f)\) is the maximum of the lengths of the boundaries of the connected components of \[ \{ z: \lvert f(z)\rvert<1\} \] then…
If A = {a₁ < a₂ < …} has property P, then A has natural density 0. Equivalently, (a_j / j) → ∞ as j → ∞. -
Let \[\epsilon_m=\max \sum \frac{1}{n_i}\] where the maximum is taken over all finite sequences \(m<n_1<\cdots<n_k\) for which there exist congruences \(a_i\pmod{n_i}\) such that no integer satisfies two such congruences. Estimate…
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…