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 \(f(n)\) be the smallest number of colours required to colour the edges of \(K_n\) such that every \(K_4\) contains at least \(5\) colours. Determine the size of \(f(n)\). Asked by Erdős and Gyárfás [Er97b], who proved…
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…
Let \(R(N)\) be the size of the largest \(A\subseteq\{1, ..., N\}\) such that all sums \(\sum_{n\in S} \frac{1}{n}\) are distinct for \(S\subseteq A\). What is \(R(N)\)?
Is it true that for every lacunary, strongly complete sequence A that is not complete whenever infinitely many terms are removed from it, lim A (n + 1) / A n = (1 + √5) / 2? The answer is no. A counterexample recorded at…
Is there an absolute constant \(c > 0\) such that, for all \(1 \leq k < n\), the binomial coefficient \(\binom{n}{k}\) has a divisor in \((cn, n]\)? Bui, Naprienko, Pratt, and Zaharescu [BNPZ26] answered this negatively.
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\}\).
There exists a sequence \(1 \le d_1 < d_2 < \dots\) with density 1 such that all products \(\prod_{u \le i \le v} d_i\) are distinct. This was solved affirmatively; see [Pratt26].
How large can \(A \subseteq \{1, \ldots, N\}\) be if \(A + A\) contains no square numbers? A problem of Erdős [Er80, Er80c, ErGr80]. Taking all integers \(\equiv 1 \pmod 3\) gives \(|A| \ge N/3\), and Massias observed that all integers…
Let \(A=\{a_1<a_2<\cdots\}\subseteq \mathbb{N}\) be infinite and let \(A(x)\) count the number of indices for which \(\mathrm{lcm}(a_i,a_{i+1})\leq x\). Is it true that \(A(x) \ll x^{1/2}\)? The answer is yes: Tao has given a simple proof,…
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…
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…
Define a sequence by \(a_1=1\) and \[a_{n+1}=\lfloor\sqrt{2}(a_n+1/2)\rfloor\] for \(n\geq 1\). The difference \(a_{2n+1}-2a_{2n-1}\) is the \(n\)th digit in the binary expansion of \(\sqrt{2}\). Find similar results for…
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…
Blumenthal's problem
**Erdős–Szekeres (1960).** For \(n \ge 3\), \(\alpha_{2^n} = \pi\left(1 - \frac{1}{n}\right)\).
What is the largest possible subset \(A\subseteq\{1,\ldots,N\}\) which contains \(N\) such that \(\mathrm{gcd}(a,b)>1\) for all \(a\neq b\in A\)? Erdős conjectured that if \(N=q_1^{k_1}\cdots q_r^{k_r}\) (where \(q_1<\cdots <q_r\) are…
Is it true that if \(A\subseteq\{1,\ldots,n\}\) is a set such that \([a,b]>n\) for all \(a\neq b\), where \([a,b]\) is the least common multiple, then \[\sum_{a\in A}\frac{1}{a}\leq \frac{31}{30}?\] The answer is yes, proved by Schinzel…
Let \(f(m)\) be the maximal \(k\) such that a triangle-free graph on \(m\) edges must contain a bipartite graph with \(k\) edges. Determine \(f(m)\). Resolved by Alon [Al96], who showed that there exist constants \(c_1,c_2>0\) such that…
Let \((A_i)\) be a family of countably infinite sets such that \(\lvert A_i\cap A_j\rvert \neq 2\) for all \(i\neq j\). Find the smallest cardinal \(C\) such that \(\cup A_i\) can always be coloured with at most \(C\) colours so that no…
**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…
A triangle whose side lengths and angles are integrally independent is cuttable only into a non-zero square number of congruent triangles. This is proved in [So09c].
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 \(d_k(p)\) be the density of those integers whose \(k\)th smallest prime factor is \(p\) (i.e. if \(p_1<p_2<\cdots\) are the primes dividing \(n\) then \(p_k=p\)). For fixed \(k\geq 1\) is \(d_k(p)\) unimodular in \(p\)? That is, it…
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)\)…
Are there infinitely many pairs of integers \(n < m\) such that \(\binom{2n}{n}\) and \(\binom{2m}{m}\) have the same set of prime divisors? Yes: there are infinitely many consecutive pairs \((n, n+1)\). The formal proof registered as…
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…
How large should \(\ell(n)\) be such that, almost surely, a random \(3\)-uniform hypergraph on \(3n\) vertices with \(\ell(n)\) edges must contain \(n\) vertex-disjoint edges? The precise asymptotic was given by Kahn [Ka23], proving that…
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…
Does there exist a \(3\)-critical \(3\)-uniform hypergraph in which every vertex has degree \(\geq 7\), where criticality means that the transversal number is \(3\) and deleting any edge reduces it to \(2\)? In the first formulation, the…
Let \(t_n\) be minimal such that \(\{n+1,\ldots,n+t_n\}\) contains a subset whose product with \(n\) is a square number (and let \(t_n=0\) if \(n\) is itself square). Estimate \(t_n\). A problem of Erdős, Graham, and Selfridge. For…
Let \(A\subseteq \{1,\ldots,N\}\) be such that there is no solution to \(at=b\) with \(a,b\in A\) and the smallest prime factor of \(t\) is \(>a\). Estimate the maximum of \[\frac{1}{\log N}\sum_{n\in A}\frac{1}{n}.\] This has been solved…
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 in the set \[\left\{ \sum_{a\in S} a : \emptyset\neq S\subseteq A\right\}\] no two distinct elements divide each other? A problem of Erdős and Sárközy. The answer is…
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).
Let \(G\) be a graph with \(1+n(m-1)\) vertices and \(1+n\binom{m}{2}\) edges. Must \(G\) contain two points which are connected by \(m\) disjoint paths? A conjecture of Bollobás and Erdős [BoEr62]. This would be the best possible, as…
Is it true that, for \(k\geq 4\), \(f_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}}\) for some constant \(c_k>0\)? This problem follows immediately from Mattheus and Verstraete's lower bound [MaVe23] for k = 4 and Bradač's lower…
Is there a function \(f(n)\) and a \(k\) such that in any \(k\)-colouring of the integers there exists a sequence \(a_1 < a_2 < \cdots\) such that \(a_n < f(n)\) for infinitely many \(n\) and the set \[\left\{ \sum_{i \in S} a_i :…
Let \(\frac{a_1}{b_1}, \frac{a_2}{b_2}, \ldots\) be the Farey fractions of order \(n \geq 4\). Let \(f(n)\) be the largest integer such that if \(1 \leq k < l \leq k + f(n)\) then \(\frac{a_k}{b_k}\) and \(\frac{a_l}{b_l}\) are similarly…
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(n)\) be such that every \(3\)-uniform linear hypergraph on \(n\) vertices contains an independent set on \(f(n)\) vertices. Estimate \(f(n)\). Phelps and Rödl [PhRo86] proved \(f(n) \asymp (n\log n)^{1/2}\).
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…
Let \(r\geq 4\). If \(G\) is a graph on \(n\) vertices with at least \(\mathrm{ex}(n;K_r)\) edges then must \(G\) contain a vertex with degree \(d\gg_r n\) whose neighbourhood contains at least \(\mathrm{ex}(d;K_{r-1})\) edges? As Erdős…
Let \(g_d(n)\) be minimal such that every collection of \(g_d(n)\) points in \(\mathbb{R}^d\) determines at least \(n\) many distinct distances. Estimate \(g_d(n)\). In particular, does \[\lim_{d \to \infty} \frac{g_d(n)}{d^{n-1}}\] exist?…
If A = {a₁ < a₂ < …} has property P, then A has natural density 0. Equivalently, (a_j / j) → ∞ as j → ∞. -
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 \[\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…
Let \(\epsilon > 0\). Does there exist \(k\) such that, for every \(n\), any primes \(p_1 < \cdots < p_k < n^{1-\epsilon}\) and any sets \(A_i\) of \(\frac{p_i - 1}{2}\) residue classes modulo \(p_i\), the number of \(m \le n\) that avoid…