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.
1017 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 \(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 \(F(N)\) be the maximal size of \(A\subseteq \{1,\ldots,N\}\) which is 'non-averaging', so that no \(n\in A\) is the arithmetic mean of at least two elements in \(A\). What is the order of growth of \(F(N)\)? It is known that…
Let \(N\geq 1\). How many \(A\subseteq \{1,\ldots,N\}\) are there such that \(\sum_{n\in A}\frac{1}{n}=1\)? Liu and Sawhney [LiSa24] proved that the count is \(2^{(0.91\cdots+o(1))N}\), where \(0.91\cdots\) is an explicit number defined as…
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…
Let \(f(n)\) be minimal such that \(\{1,\ldots,n-1\}\) can be partitioned into \(f(n)\) classes so that \(n\) cannot be expressed as a sum of distinct elements from the same class. How fast does \(f(n)\) grow? A problem of Erdős and Graham…
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.
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,…
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…
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…
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 \(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…
Erdős Problem 721, upper bound: prove that \(W(3,k) < \exp(k^c)\) for some constant \(c<1\). The first to show that \(W(3,k) < \exp(k^c)\) for some \(c<1\) was Schoen [Sc21]. Source:…
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…
Given any \(n\) points in \(\mathbb{R}^2\) when can one give positive weights to the points such that the sum of the weights of the points along every line containing at least two points is the same? This is a problem of Murty [Er81], who…
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…
If \(\mathcal{F}\) is a family of subsets of \(\{1,\ldots,n\}\) then we write \(G_{\mathcal{F}}\) for the graph on \(\mathcal{F}\) where \(A\sim B\) if \(A\) and \(B\) are comparable - that is, \(A\subseteq B\) or vice versa. Is it true…
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…
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…
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 \(S(N,A,c)\) be the measure of the set of those \(\alpha\in (0,1)\) such that \[\left\lvert \alpha-\frac{x}{y}\right\rvert< \frac{A}{y^2}\] for some \(N\leq y\leq cN\) and \((x,y)=1\). Does \[\lim_{N\to \infty}S(N,A,c)=f(A,c)\] exist?…
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…
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}\).
Given any \(n\) points in \(\mathbb{R}^2\), the number of \(k\)-rich lines (lines which contain \(\geq k\) of the points) is, provided \(k\leq n^{1/2}\), \[\ll \frac{n^2}{k^3}.\] Erdős [Er87b] describes this as a conjecture of himself,…
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?…
Let \(f(z)\) be an entire function of finite order, and let \(\Gamma\) be a rectifiable path on which \(f(z)\to \infty\). Let \(\ell(r)\) be the length of \(\Gamma\) in the disc \(\lvert z\rvert<r\). Find a path for which \(\ell(r)\) grows…
For a meromorphic function \(f\) let \(n(r,a)\) count the number of roots of \(f(z)=a\) in the disc \(\lvert z\rvert <r\). Does there exist a meromorphic (or entire) \(f\) such that for every \(a\neq b\) \[\limsup_{r\to…
Let \(f_k(n)\) count the number of elements of \(S_n\) of order \(k\). For which values of \(k\) will \(f_k(n)\) be maximal? [Va99, 5.72] Beker [Be25d, Theorem 1.2] proved that, for all large \(n\), \(f_k(n)\) is maximal if and only if…
Given a random walk \(s_0,s_1,\ldots\) in \(\mathbb{Z}^2\), starting at the origin, let \(f_n(x)\) count the number of \(0\leq k\leq n\) such that \(s_k=x\). Let \[F(n)=\{ x: f_n(x) = \max_y f_n(y)\}\] be the set of 'favourite values'.…
Let \(\delta>0\) and \(k\geq 3\). Is it true that there exists \(m\geq 1\) (depending only on \(\delta\) and \(k\)) such that, for all large \(N\), if \(A,B\subseteq \{1,\ldots,N\}\) with \(\lvert A\rvert \geq \delta N\) and…
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 \(S\subset \mathbb{R}\) be a set of infinite measure such that \(x/y\) is never an integer for all distinct \(x,y\in S\). How fast can \(\lvert S\cap (0,x)\rvert\) tend to infinity? A question of Erdős [Er80, p. 101]. Ho Boon Suan and…
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…
Let \(F(x)\) be maximal such that there exists, for all \(n\leq x\), a congruence class \(a_n\pmod{n}\) such that every \(m\leq x\) satisfies at least \(F(x)\) of these congruences. Estimate \(F(x)\). Erdős [Er80, p. 108] describes…
Let \(\mathbb{N}=A\cup B\) where \(A\) and \(B\) are disjoint. Let \(S(A)\) be those integers which are the sum of finitely many distinct elements of \(A\), and similarly for \(S(B)\). If \[ \overline{\delta}(X)=\limsup_{x\to…