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.
Is it true that, for any \(C > 0\), there infinitely many \(n\) such that: \[ p_{n + 1} - p_n > C \frac{\log\log n\log\log\log\log n}{(\log\log\log n) ^ 2}\log n \]
There are infinitely many \(n\) such that \(d_n < d_{n+1} < d_{n+2}\), where \(d\) denotes the prime gap function.
If \(A \subseteq \{1, ..., N\}\) is a set with no \(a, b, c \in A\) such that \(a | (b+c)\) and \(a < \min(b,c)\), then \(|A| \le N/3 + O(1)\). This has been solved by Bedert [Be23]. [Be23] Bedert, B., _On a problem of Erdős and Sárközy…
Let \(f(n)\) be minimal such that there is an intersecting family \(\mathcal{F}\) of sets of size \(n\) (so \(A\cap B\neq\emptyset\) for all \(A,B\in \mathcal{F}\)) with \(\lvert \mathcal{F}\rvert=f(n)\) such that any set \(S\) with…
Let \(\epsilon > 0\) and let \(n\) be sufficiently large depending on \(\epsilon\). Is there a graph on \(n\) vertices with at least \(n^2/8\) many edges which contains no \(K_4\), such that the largest independent set has size at most…
Does every triangle-free graph on \(5n\) vertices contain at most \(n^5\) copies of \(C_5\)? Győri proved this with \(1.03n^5\), which has been improved by Füredi. The answer is yes, as proved independently by Grzesik [Gr12] and Hatami,…
Is there an explicit construction of a set \(A\subseteq \mathbb{N}\) such that \(A+A=\mathbb{N}\) but \(1_A\ast 1_A(n)=o(n^\epsilon)\) for every \(\epsilon>0\)? The existence of such a set was asked by Sidon to Erdős in 1932. Erdős…
Given any infinite set \(A\subset \mathbb{N}\) there is a set \(B\) of density \(0\) such that \(A+B\) contains all except finitely many integers. Conjectured by Erdős and Straus. Proved by Lorentz [Lo54].
Let \(B\subseteq\mathbb{N}\) be an additive basis of order \(k\) with \(0\in B\). Is it true that for every \(A\subseteq\mathbb{N}\) we have \[d_s(A+B)\geq \alpha+\frac{\alpha(1-\alpha)}{k},\] where \(\alpha=d_s(A)\) and \[d_s(A) = \inf…
Does there exist \(B \subset \mathbb{N}\) which is not an additive basis, but is such that for every set \(A \subseteq \mathbb{N}\) of Schnirelmann density \(\alpha\) and every \(N\) there exists \(b \in B\) such that \[ \lvert (A \cup…
Let \(k\geq 2\). Is there an integer \(n_k\) such that, if \(D=\{ 1<d<n_k : d\mid n_k\}\), then for any \(k\)-colouring of \(D\) there is a monochromatic subset \(D'\subseteq D\) such that \(\sum_{d\in D'}\frac{1}{d}=1\)? This follows from…
Does every finite colouring of the integers have a monochromatic solution to \(1=\sum \frac{1}{n_i}\) with \(2\leq n_1<\cdots <n_k\)? The answer is yes, as proved by Croot [Cr03] - indeed, there are infinitely many disjoint such…
If \(\delta>0\) and \(N\) is sufficiently large in terms of \(\delta\), and \(A\subseteq\{1,\ldots,N\}\) is such that \(\sum_{a\in A}\frac{1}{a}>\delta \log N\) then must there exist \(S\subseteq A\) such that…
Are there infinitely many integers \(n, m\) such that \(ϕ(n) = σ(m)\)?
Let \(A=\{a_1<\cdots<a_t\}\subseteq \{1,\ldots,N\}\) be such that \(\phi(a_1)<\cdots<\phi(a_t)\). The primes are such an example. Are they the largest possible? Can one show that \(\lvert A\rvert<(1+o(1))\pi(N)\) or even…
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…
If \(G\) is a graph with infinite chromatic number and \(a_1 < a_2 < \cdots\) are lengths of the odd cycles of \(G\) then \(\sum \frac{1}{a_i} = \infty\). Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20].…
If \(G\) is a graph which contains odd cycles of \(\leq k\) different lengths then \(\chi(G)\leq 2k+2\), with equality if and only if \(G\) contains \(K_{2k+2}\). Conjectured by Bollobás and Erdős. Proved by Gyárfás [Gy92].
Does every graph with infinite chromatic number contain a cycle of length \(2^n\) for infinitely many \(n\)? Conjectured by Mihók and Erdős. Solved affirmatively following the work of Liu and Montgomery [LiMo20]. The linked formal proof…
Erdős discrepancy problem
**The Erdős discrepancy problem** If \(f\colon \mathbb N \rightarrow \{-1, +1\}\) then is it true that for every \(C>0\) there exist \(d, m \ge 1\) such that \[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\] This is true, and was…
Is it true that for every infinite arithmetic progression \(P\) which contains even numbers there is some constant \(c=c(P)\) such that every graph with average degree at least \(c\) contains a cycle whose length is in \(P\)? In [Er82e]…
Is there a set \(A\subset \mathbb{N}\) of density \(0\) and a constant \(c>0\) such that every graph on sufficiently many vertices with average degree \(\geq c\) contains a cycle whose length is in \(A\)? Bollobás [Bo77] proved that such a…
Let \(k\ge 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\ge (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) be the union of a bipartite graph and \(O_k(1)\) many…
We say \(G\) is Ramsey size linear if \(R(G,H)\ll m\) for all graphs \(H\) with \(m\) edges and no isolated vertices. Are there infinitely many graphs \(G\) which are not Ramsey size linear but such that all of its proper subgraphs are?…
Suppose that we have a family \(\mathcal{F}\) of subsets of \([4n]\) such that \(\lvert A\rvert=2n\) for all \(A\in\mathcal{F}\) and for every \(A,B\in \mathcal{F}\) we have \(\lvert A\cap B\rvert \geq 2\). Then \[\lvert \mathcal{F}\rvert…
For any \(\epsilon>0\) there exists \(\delta=\delta(\epsilon)>0\) such that if \(G\) is a graph on \(n\) vertices with no independent set or clique of size \(\geq \epsilon\log n\) then \(G\) contains an induced subgraph with \(m\) edges…
If \(n\) distinct points in \(\mathbb{R}^2\) form a convex polygon then they determine at least \(\lfloor \frac{n}{2}\rfloor\) distinct distances. Solved by Altman [Al63].
Suppose \(n\) points in \(\mathbb{R}^2\) determine a convex polygon and the set of distances between them is \(\{u_1,\ldots,u_t\}\). Suppose \(u_i\) appears as the distance between \(f(u_i)\) many pairs of points. Then \[\sum_i f(u_i)^2…
Let \(x_1,\ldots,x_n\in\mathbb{R}^2\) determine the set of distances \(\{u_1,\ldots,u_t\}\). Suppose \(u_i\) appears as the distance between \(f(u_i)\) many pairs of points. Then for all \(\epsilon>0\) \[\sum_i f(u_i)^2 \ll_\epsilon…
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].
If \(p(z)\) is a polynomial of degree \(n\) such that \(\{z : \lvert p(z)\rvert\leq 1\}\) is connected then is it true that \[\max_{\substack{z\in\mathbb{C}\\ \lvert p(z)\rvert\leq 1}} \lvert p'(z)\rvert \leq (\tfrac{1}{2}+o(1))n^2?\]…
Let \(p(z)=\prod_{i=1}^n (z-z_i)\) for \(\lvert z_i\rvert \leq 1\). Is it true that \[\lvert\{ z: \lvert p(z)\rvert <1\}\rvert>n^{-O(1)}\] (or perhaps even \(>(\log n)^{-O(1)}\))? Conjectured by Erdős, Herzog, and Piranian [EHP58]. The…
Let \(a, b, c\) be three integers which are pairwise coprime. Is every large integer the sum of distinct integers of the form \(a^k b^l c^m\) (\(k, l, m ≥ 0\)), none of which divide any other? Equivalently: is the set…
Let \(f(n)\) be maximal such that if \(A\subseteq\mathbb{N}\) has \(|A| = n\) then \(\prod_{a\neq b\in A}(a + b)\) has at least \(f(n)\) distinct prime factors. Is it true that \(\frac{f(n)}{\log n} \to\infty\)? The answer is yes, and a…
Let \(f(m)\) be maximal such that every graph with \(m\) edges must contain a bipartite graph with \[\geq \frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}+f(m)\] edges. Is there an infinite sequence of \(m_i\) such that \(f(m_i)\to \infty\)?…
Let \(\epsilon,\delta>0\) and \(n\) be sufficiently large in terms of \(\epsilon\) and \(\delta\). Let \(G\) be a triangle-free graph on \(n\) vertices with maximum degree \(<n^{1/2-\epsilon}\). Can \(G\) be made into a triangle-free graph…
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)\).
A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let \(c(n)\) be the maximum number of minimal cuts a graph on \(n\) vertices can have. Does \(c(n)^{1/n}\to \alpha\) for some \(\alpha <2\)? It is…
Must lim f n = ∞? This was proved formally by the DeepMind prover agent [DM26a].
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.…
Does there exist an infinite Sidon set which is an asymptotic basis of order \(3\)? Yes, as shown by Pilatte [Pi23].
Burr-Erdős conjecture
The Burr-Erdős conjecture: For any \(d\geq 1\) if \(H\) is a graph such that every subgraph contains a vertex of degree at most \(d\) then \[R(H)\ll_d n.\] Solved by Lee [Le17], who proved that \(R(H) \leq 2^{2^{O(d)}}n\). This problem is…
A set \(A\subset \mathbb{N}\) is primitive if no member of \(A\) divides another. Is the sum \[\sum_{n\in A}\frac{1}{n\log n}\] maximised over all primitive sets when \(A\) is the set of primes? Erdős [Er35] proved that this sum always…
Prove that \[R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.\] This is true, and was proved by Mattheus and Verstraëte [MaVe23], who showed that \(R(4,k) \gg \frac{k^3}{(\log k)^4}\). This problem is #5 in Ramsey Theory in the graphs problem…
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…
Show that, for any \(n\geq 5\), the binomial coefficient \(\binom{2n}{n}\) is not squarefree.
Let \(A_1,A_2,\ldots\) be an infinite collection of infinite sets of integers, say \(A_i=\{a_{i1}<a_{i2}<\cdots\}\). Does there exist some \(f:\mathbb{N}\to\{-1,1\}\) such that \[\max_{m, 1\leq i\leq d} \left\lvert \sum_{1\leq j\leq m}…
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 \(C>0\) be arbitrary. Is it true that, if \(n\) is sufficiently large depending on \(C\), then in any \(2\)-colouring of \(\binom{\{2,\ldots,n\}}{2}\) there exists some \(X\subseteq \{2,\ldots,n\}\) such that \(\binom{X}{2}\) is…
For any \(g\geq 2\), if \(n\) is sufficiently large and \(\equiv 1,3\pmod{6}\) then there exists a 3-uniform hypergraph on \(n\) vertices such that - every pair of vertices is contained in exactly one edge (i.e. the graph is a Steiner…
Let \(f(n)\) be the sharp guarantee such that, for any \(n\) points in \(\mathbb R^2\), not all on a line, there are at least \(f(n)\) lines which contain exactly two points (called ordinary lines). Does \(f(n)\to\infty\)? That…
Let \(1\leq k<n\). Given \(n\) points in \(\mathbb{R}^2\), at most \(n-k\) on any line, there are \(\gg kn\) many lines which contain at least two points. Solved by Beck [Be83] and Szemerédi and Trotter [SzTr83].
Let \(S\subset \mathbb{R}^2\) be such that no two points in \(S\) are distance \(1\) apart. Must the complement of \(S\) contain four points which form a unit square? The answer is yes, proved by Juhász [Ju79], who proved more generally…
Does there exist \(S\subseteq \mathbb{R}^2\) such that every set congruent to \(S\) (that is, \(S\) after some translation and rotation) contains exactly one point from \(\mathbb{Z}^2\)? An old question of Steinhaus. Erdős was 'almost…
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_
Let \(n \geq 1\) and \[A = \{a_1 < \cdots < a_{\phi(n)}\} = \{1 \leq m < n : (m, n) = 1\}.\] Is it true that \[\sum_{1 \leq k < \phi(n)} (a_{k+1} - a_k)^2 \ll \frac{n^2}{\phi(n)}?\] A problem of Erdős [Er40, Er73, ErGr80], which is…
Is there a set \(A\subset\mathbb{N}\) such that, for all large \(N\), \[\lvert A\cap\{1,\ldots,N\}\rvert \ll N/\log N\] and such that every large integer can be written as \(2^k+a\) for some \(k\geq 0\) and \(a\in A\)? Lorentz [Lo54]…
If \(A\subseteq \mathbb{R}^d\) is any set of \(2^d+1\) points then some three points in \(A\) determine an obtuse angle. The general case was proved by Danzer and Gr\"{u}nbaum [DaGr62].
Let \[ f(\theta) = \sum_{0\leq k\leq n}c_k e^{ik\theta}\] be a trigonometric polynomial all of whose roots are real, such that \(\max_{\theta\in [0,2\pi]}\lvert f(\theta)\rvert=1\). Then \[\int_0^{2\pi}\lvert f(\theta)\rvert…
Is there an entire non-linear function \(f\) such that, for all \(x\in\mathbb{R}\), \(x\) is rational if and only if \(f(x)\) is? Barth and Schneider [BaSc70] proved the stronger result for countable dense subsets of \(\mathbb{R}\).
Let \((S_n)_{n \ge 1}\) be a sequence of sets of complex numbers, none of which have a finite limit point. Does there exist an entire transcendental function \(f(z)\) such that, for all \(n \ge 1\), there exists some \(k_n \ge 0\) such…
Let \(N_k=2\cdot 3\cdots p_k\) and \(\{a_1<a_2<\cdots <a_{\phi(N_k)}\}\) be the integers \(<N_k\) which are relatively prime to \(N_k\). Then, for any \(c\geq 0\), the limit \[\frac{\#\{ a_i-a_{i-1}\leq c \frac{N_k}{\phi(N_k)} : 2\leq…
Let \(A\subseteq \mathbb{N}\) be a set such that \(\lvert A\cap \{1,\ldots,N\}\rvert \gg \log N\) for all large \(N\). Let \(f(n)\) count the number of solutions to \(n=p+a\) for \(p\) prime and \(a\in A\). Is it true that…
Let \(f:\mathbb{N}\to \{-1,1\}\) be a multiplicative function. Is it true that \[ \lim_{N\to \infty}\frac{1}{N}\sum_{n\leq N}f(n)\] always exists? The answer is yes, as proved by Wirsing [Wi67], and generalised by Halász [Ha68].
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…
Let \((a,b)=1\). The set \(\{a^kb^l: k,l\geq 0\}\) is complete - that is, every large integer is the sum of distinct integers of the form \(a^kb^l\) with \(k,l\geq 0\). We state the nontrivial case \(a,b\geq 2\), proved by Birch [Bi59].
Are there infinitely many \(n\) such that \(\omega(n + k) \ll k\) for all \(k \geq 1\)? Here \(\omega(n)\) is the number of distinct prime divisors of \(n\).
Is \[ \sum_{n=1}^\infty \frac{\sigma(n)}{2^n} \] irrational? Here \(\sigma(n)\) is the sum of divisors function. The answer is yes, as shown by Nesterenko [Ne96]. [Ne96] Nesterenko, Yu V., _Modular functions and transcendence questions_,…
Let \(a_n \to \infty\) be a sequence of non-zero natural numbers. Is \(\sum_n \frac{d(n)}{(a_1 ... a_n)}\) irrational, where \(d(n)\) is the number of divisors of \(n\)? This was proved affirmatively by Chojecki and GPT-5.4 Pro [Ch26], and…
Is \(\sum_{n} \mu(n)^2\frac{n}{2^n}\) irrational? This is true, and was proved by Chen and Ruzsa. [ChRu99] Chen, Yong-Gao and Ruzsa, Imre Z., On the irrationality of certain series. Period. Math. Hungar. (1999), 31--37.
Let X be the set of points in Fin d → ℝ of the shape fun i : Fin d => ∑' n : A, (1 : ℝ) / (n + i) for some infinite subset A ⊆ ℕ such that 1 / n is summable over A. X has nonempty interior. This is proved in [KoTa24]. -
If a finite system of \(r\) congruences \(\{ a_i\pmod{n_i} : 1\leq i\leq r\}\) (the \(n_i\) are not necessarily distinct) covers \(2^r\) consecutive integers then it covers all integers. This is best possible as the system…
Is it true that, for every \(c\), there exists an \(n\) such that \(\sigma(n)>cn\) but there is no covering system whose moduli all divide \(n\)? This was answered affirmatively by Haight [Ha79].
Let \(n_1<n_2<\cdots\) be an infinite sequence such that, for any choice of congruence classes \(a_i\pmod{n_i}\), the set of integers not satisfying any of the congruences \(a_i\pmod{n_i}\) has density \(0\). Is it true that for every…
Let \(p\colon \mathbb{Z} \rightarrow \mathbb{Z}\) be a polynomial (with rational coefficients, taking integer values at all integers) whose leading coefficient is positive and such that there exists no \(d≥2\) with \(d ∣ p(n)\) for all…
Let \(f(k)\) be the minimal value of \(n_k\) such that there exist \(n_1 < n_2 < \dots < n_k\) with \[ 1 = \frac{1}{n_1} + \cdots + \frac{1}{n_k}. \] Is it true that \[ f(k) = (1 + o(1)) \frac{e}{e - 1} k ? \] Proved by Martin [Ma00].…
Let \(k\geq 2\). Is it true that there exists an interval \(I\) of width \((e-1+o(1))k\) and integers \(n_1<\cdots<n_k\in I\) such that \[1=\frac{1}{n_1}+\cdots+\frac{1}{n_k}?\] The answer is yes, proved by Croot [Cr01].
Let \(a\geq 1\). Must there exist some \(b>a\) such that \[\sum_{a\leq n\leq b}\frac{1}{n}=\frac{r_1}{s_1}\textrm{ and } \sum_{a\leq n\leq b+1}\frac{1}{n}=\frac{r_2}{s_2},\] with \((r_i,s_i)=1\) and \(s_2<s_1\)? If so, how does this…
Let \(A\) be the set of \(n\in \mathbb{N}\) such that there exist \(1\leq m_1<\cdots <m_k=n\) with \(\sum\tfrac{1}{m_i}=1\). Explore \(A\). In particular, does \(A\) have density \(1\)? Straus observed that \(A\) is closed under…
Let \(N\geq 1\) and let \(k(N)\) be maximal such that there are \(k\) disjoint \(A_1,\ldots,A_k\subseteq \{1,\ldots,N\}\) with \(\sum_{n\in A_i}\frac{1}{n}=1\) for all \(i\). Estimate \(k(N)\). Is it true that \(k(N)=o(\log N)\)? Hunter…
Does every set \(A \subseteq \mathbb{N}\) of positive density contain some finite \(S \subset A\) such that \(\sum_{n \in S} \frac{1}{n} = 1\)? The answer is yes, proved by Bloom [Bl21] (even if 'positive density' is interpreted as…
Is it true that in any finite colouring of the integers there exists a monochromatic solution to \(\frac 1 a = \frac 1 b + \frac 1 c\) with distinct \(a, b, c\)? This is true, as proved by Brown and Rödl [BrRo91]. This was formalized in…
For integers \(1\leq a<b\) let \(D(a,b)\) be the minimal value of \(n_k\) such that there exist integers \(1\leq n_1<\cdots <n_k\) with \[\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}.\] Estimate \(D(b)=\max_{1\leq a<b}D(a,b)\). Is it…
Let \(N\geq 1\). What is the smallest integer not representable as the sum of distinct unit fractions with denominators from \(\{1,\ldots,N\}\)? This was essentially solved by Croot [Cr99] (see erdos_308.variants.croot); in particular, for…
Let \(\alpha >0\) and \(N\geq 1\). Is it true that for any \(A\subseteq \{1,\ldots,N\}\) with \(\lvert A\rvert \geq \alpha N\) there exists some \(S\subseteq A\) such that \[\frac{a}{b}=\sum_{n\in S}\frac{1}{n}\] with…
Let \(n\geq 1\) and let \(m\) be minimal such that \(\sum_{n\leq k\leq m}\frac{1}{k}\geq 1\). We define \[\epsilon(n) = \sum_{n\leq k\leq m}\frac{1}{k}-1.\] How small can \(\epsilon(n)\) be? Is it true that \[\liminf n^2\epsilon(n)=0?\]…
Let \(u_1=1\) and \(u_{n+1}=u_n(u_n+1)\), so that \(\sum_{k\geq 1}\frac{1}{u_k+1}\) and \(u_k=\lfloor c_0^{2^k}+1\rfloor\) for \(k\geq 1\), where \[c_0=\lim u_n^{1/2^n}=1.264085\cdots.\] Let \(a_1<a_2<\cdots \) be any other sequence with…
Does there exist a minimal basis \(A \subset \mathbb{N}\) with positive density such that, for any \(n \in A\), the (upper) density of integers which cannot be represented without using \(n\) is positive? Neither set is asked to have a…
The set of subset sums of a set A ⊆ ℕ. -/ local notation "𝓟" A => subsetSums A /-- Is there a sequence \(A=\{a_1\leq a_2\leq \cdots\}\) of integers with \[\lim \frac{a_{n+1}}{a_n}=2\] such that \[P(A')= \left\{\sum_{n\in B}n : B\subseteq…
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 \(p(x) \in \mathbb{Q}[x]\) be a non-constant rational polynomial with positive leading coefficient. Is it true that \[A=\{ p(n)+1/n : n \in \mathbb{N}\}\] is strongly complete, in the sense that, for any finite set \(B\),…
Let \(A\subseteq \mathbb{R}^2\) be a measurable set with infinite measure. Must \(A\) contain the vertices of an isosceles trapezoid of area \(1\)? What about an isosceles triangle, or a right-angled triangle, or a cyclic quadrilateral, or…
Is there a lacunary sequence \(A\subseteq \mathbb{N}\) (so that \(A=\{a_1 < \cdots\}\) and there exists some \(\lambda > 1\) such that \(a_{n+1}/a_n\geq \lambda\) for all \(n\geq 1\)) such that \[\left\{ \sum_{a\in A'}\frac{1}{a} :…
Let \(A=\{a_1 < \cdots\}\) be an infinite sequence of integers. Let \(f(n)\) count the number of solutions to \[n=\sum_{u\leq i\leq v}a_i.\] Is there such an \(A\) for which \(f(n)\to \infty\) as \(n\to \infty\)? Tao [Ta26] constructed…
Let \(A\subseteq \mathbb{N}\) be a finite set of size \(N\). Is it true that, for any fixed \(t\), there are \[\ll \frac{2^N}{N^{3/2}}\] many \(S\subseteq A\) such that \(\sum_{n\in S}n=t\)? Erdős and Moser [Er65] proved the first bound…
Let \(\epsilon>0\) and \(k\geq 2\). Is it true that, for all sufficiently large \(n\), there is a sequence of \(k\) consecutive integers in \(\{1,\ldots,n\}\) all of which are \(n^\epsilon\)-smooth? The problem is trivially true as written…
Are there infinitely many \(n\) such that the largest prime factor of \(n\) is \(< n^{\frac{1}{2}}\) and the largest prime factor of \(n + 1\) is \(< (n + 1)^{\frac{1}{2}}\). Steinerberger has pointed out this problem has a trivial…
Let \(P(n)\) denote the largest prime factor of \(n\). There are infinitely many \(n\) such that \(P(n)>P(n+1)>P(n+2)\).
Let \(S(n)\) denote the largest integer such that, for all \(1 ≤ k < n\), the binomial coefficient \(\binom{n}{k}\) is divisible by \(p^S(n)\) for some prime \(p\) (depending on \(k\)).Then \(\limsup S(n) = \infty\). This was formalized in…
If \(1<k<n-1\) then \(\binom{n}{k}\) is divisible by a prime \(p\leq n/2\) (except \(\binom{7}{3}=\binom{7}{4}=5\cdot 7\)). A conjecture of Erdős and Selfridge [ErGr80]. Proved by Ecklund [Ec69], who made the stronger conjecture that…
Let \(t(n)\) be maximal such that there is a representation \[n!=a_1\cdots a_n\] with \(t(n)=a_1\leq \cdots \leq a_n\). Obtain good bounds for \(t(n)/n\). In particular, is it true that \[\lim \frac{t(n)}{n}=\frac{1}{e}?\] It is easy to…
Let \(A(n)\) denote the least value of \(t\) such that \[ n! = a_1 \cdots a_t \] with \(a_1 \leq \cdots \leq a_t\leq n^2\). Then \[ A(n) = \frac{n}{2} - \frac{n}{2\log n} + o\left(\frac{n}{\log n}\right). \]
reverse Littlewood-Offord problem
If \(z_1,\ldots,z_n\in \mathbb{C}\) with \(\lvert z_i\rvert=1\) then is it true that the probability that \[\lvert \epsilon_1z_1+\cdots+\epsilon_nz_n\rvert \leq \sqrt{2},\] where \(\epsilon_i\in \{-1,1\}\) uniformly at random, is…
Is there some function \(f(r)\) such that \(f(r)\to \infty\) as \(r\to\infty\), such that, for infinitely many \(n\), there exist \(a_1,a_2\) with \[a_1+a_2> n+f(r)\log n\] such that \(a_1!a_2! \mid n!2^n3^n\cdots p_r^n\)? It is ambiguous…
Prove that, for any finite set \(A\subset\mathbb{N}\), there exist \(a, b\in A\) such that \[ \gcd(a, b)\leq a/|A|. \]
Does the equation \[2^m=a_1!+\cdots+a_k!\] with \(a_1<a_2<\cdots <a_k\) have only finitely many solutions? Asked by Burr and Erdős. Frankl and Lin [Li76] independently showed that the answer is yes, and the largest solution is…
Let \(p\) be an odd prime. Is it true that the equation \((p-1)!+a^{p-1}=p^k\) has only finitely many solutions? Originally proposed by Erdős and Graham [ErGr80]. Brindza and Erdős [BrEr91] proved that there are finitely many such…
Let \(w(n)\) count the number of solutions to \[n=2^a+3^b+2^c3^d\] with \(a,b,c,d\geq 0\) integers. Is it true that \(w(n)\) is bounded by some absolute constant? A conjecture originally due to Newman. This is true, and was proved by…
Are there infinitely many integers not of the form \(n - \phi(n)\)? Asked by Erdős and Sierpiński. Numbers not of the form we call non-cototients. Browkin and Schinzel [BrSc95] provided an affirmative answer to this question, proving that…
**Erdős Problem 427**: is it true that, for every \(n\) and \(d\), there exists \(k\) such that \[ d \mid p_{n + 1} + \cdots + p_{n + k}, \] where \(p_r\) denotes the \(r\)th prime?
For every fixed \(k \geq 2\), Erdős and Graham conjectured that \[g(k,n) \sim \frac{n^2}{k-1}.\] The conjecture was proved by Dixmier [Di90].
Let \(k \le n\). What choice of \(A\subseteq\{1, \dots, n\}\) (with \(\text{gcd}(A) = 1\)) of size \(|A| = k\) maximises the number of integers not representable as the sum of finitely many elements from \(A\) (with repetitions allowed)?…
Let \(n\in\mathbb{N}\) with \(n\neq p^k\) for any prime \(p\) and \(k\geq 0\). What is the largest integer not of the form \[\sum_{1\leq i<n}c_i\binom{n}{i}\] where the \(c_i\geq 0\) are integers? If \(n=\prod p_k^{a_k}\) then the largest…
Let \(1\leq a_1<\cdots<a_k\leq x\). How many of the partial products \(a_1,a_1a_2,\ldots,a_1\cdots a_k\) can be squares? Is it true that, for any \(\epsilon>0\), there can be more than \(x^{1-\epsilon}\) squares? The answer is yes, which…
Let \(m,n\geq 1\). What is \[\# \{ k(m-k) : 1\leq k\leq m/2\} \cap \{ l(n-l) : 1\leq l\leq n/2\}?\] Can it be arbitrarily large? This was solved independently by Hegyvári [He25] and Cambie (unpublished), who show that if \(m>n\) then the…
Let \(A\subseteq\mathbb{N}\) be infinite and \(d_A(n)\) count the number of \(a\in A\) which divide \(n\). Is it true that, for every \(k\), \[\limsup_{x\to \infty} \frac{\max_{n<x}d_A(n)}{\left(\sum_{n\in A\cap[1,x)}\frac{1}{n}\right)^k}…
How large can a union-free collection \(\mathcal{F}\) of subsets of \([n]\) be? By union-free we mean there are no solutions to \(A\cup B=C\) with distinct \(A,B,C\in \mathcal{F}\). Must \(\lvert \mathcal{F}\rvert =o(2^n)\)? In [Er65b]…
Is there some \(\epsilon > 0\) such that there are infinitely many \(n\) where all primes \(p \le (2 + \epsilon) \log n\) divide \[ \prod_{1 \le i \le \log n} (n + i)? \] This was formalized in Lean by Baretto and van Doorn using Aristotle.
Let \(A=\{n_1<n_2<\cdots\}\subset \mathbb{N}\) be a lacunary sequence (so there exists some \(\epsilon>0\) with \(n_{k+1}\geq (1+\epsilon)n_k\) for all \(k\)). Must there exist an irrational \(\theta\) such that \[\{ \|\theta n_k\| : k\geq…
Let \(N(X,\delta)\) denote the maximum number of points \(P_1,\ldots,P_n\) which can be chosen in a circle of radius \(X\) such that \[\| \lvert P_i-P_j\rvert \| \geq \delta\] for all \(1\leq i<j\leq n\). (Here \(\|x\|\) is the distance…
Let \(A\) be the set of all \(n\) such that \(n = d_1 + ⋯ + d_k\) with \(d_i\) distinct proper divisors of \(n\), but this is not true for any \(m ∣ n\) with \(m < n\). Does: \[ \sum_{n ∈ A} \frac 1 n \] converge? Yes: the sum converges.…
Is there a permutation \(a_1, a_2, \ldots\) of the positive integers such that \(a_k + a_{k+1}\) is always prime? A question of Segal [ErGr80, p.94]. The answer is yes, as shown by Odlyzko. The linked formal proof (Codex and GPT-5.6 Sol)…
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 \(x_1,x_2,\ldots\in [0,1]\) be an infinite sequence. Is it true that \[\inf_n \liminf_{m\to \infty} n \lvert x_{m+n}-x_m\rvert\leq 5^{-1/2}\approx 0.447?\] A conjecture of Newman.
Let \(a_1,\ldots,a_r,b_1,\ldots,b_r\in \mathbb{N}\) such that \(\sum_{i}\frac{1}{a_i}>1\). For any finite sequence of \(n\) (not necessarily distinct) integers \(A=(x_1,\ldots,x_n)\) let \(T(A)\) denote the sequence of length \(rn\) given…
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 \(f(k)\) be the minimum number of terms in \(P(x)^2\), where \(P \in \mathbb{Q}[x]\) ranges over all polynomials with exactly \(k\) non-zero terms. Is it true that \(f(k) \to \infty\) as \(k \to \infty\)? A conjecture of Erdős and…
Let \(A\subseteq \mathbb{N}\) have positive density. Must there exist distinct \(a,b,c\in A\) such that \([a,b]=c\) (where \([a,b]\) is the least common multiple of \(a\) and \(b\))? This is true, a consequence of the positive solution to…
Let \(A,B\subseteq \{1,\ldots,N\}\) be such that all the products \(ab\) with \(a\in A\) and \(b\in B\) are distinct. Is it true that \[\lvert A\rvert \lvert B\rvert \ll \frac{N^2}{\log N}?\] This would be best possible, for example…
Let \(f : \mathbb{N} \to \mathbb{R}\) be an additive function (so that \(f(ab) = f(a) + f(b)\) whenever \((a, b) = 1\)). If \(|f(n+1) - f(n)| < c\) for some constant \(c\) and all \(n\), then must there exist some \(c'\) such that…
Does there exist a \(k\) such that every sufficiently large integer can be written in the form \[\prod_{i=1}^k a_i - \sum_{i=1}^k a_i\] for some integers \(a_i\geq 2\)? Erdős attributes this question to Schinzel. Eli Seamans has observed…
strong Littlewood-Offord problem
Let \(z_1,\ldots,z_n\in\mathbb{C}\) with \(1\leq \lvert z_i\rvert\) for \(1\leq i\leq n\). Let \(D\) be an arbitrary disc of radius \(1\). Is it true that the number of sums of the shape \[\sum_{i=1}^n\epsilon_iz_i \textrm{ for…
Let \(M\) be a real \(n \times n\) doubly stochastic matrix. Does there exist some \(σ \in S_n\) such that \[ \prod_{1 \leq i \leq n} M_{i, σ(i)} \geq n^{-n}? \] This is true, and was proved by Marcus and Minc [MaMi62] [MaMi62] Marcus,…
Littlewood's conjecture
Is it true that, if \(A\subset \mathbb{Z}\) is a finite set of size \(N\), then \[\int_0^1 \left\lvert \sum_{n\in A}e(n\theta)\right\rvert \mathrm{d}\theta \gg \log N,\] where \(e(x)=e^{2\pi ix }\)? Littlewood's conjecture, proved…
Let f = ∑ aₖzⁿₖ be an entire function of finite order such that nₖ / k → ∞. Then limsup (fun r => ratio r f) atTop = 1. This is proved in [Fu63].
Let \(z_1,\ldots,z_n\in \mathbb{C}\) with \(z_1=1\). Must there exist an absolute constant \(c>0\) such that \[ \max_{1\leq k\leq n}\left\lvert \sum_{i}z_i^k\right\rvert>c? \] Atkinson proved that \(c=1/6\) suffices.
Is it true that all except at most \(o(2^n)\) many degree \(n\) polynomials with \(\pm 1\)-valued coefficients \(f(z)\) have \(\lvert f(z)\rvert <1\) for some \(\lvert z\rvert=1\)? The answer is yes: Littlewood [Li66] conjectured the…
If \(\mathbb{N}\) is 2-coloured then is there some infinite set \(A\subseteq \mathbb{N}\) such that all finite subset sums\[ \sum_{n\in S}n\](as \(S\) ranges over all non-empty finite subsets of \(A\)) are monochromatic? Asked by Graham…
Is it true that if \(A\subseteq \mathbb{Z}/N\mathbb{Z}\) has size \(\gg N^{1/2}\) then there exists some non-empty \(S\subseteq A\) such that \(\sum_{n\in S}n\equiv 0\pmod{N}\)? Szemerédi proved the answer is yes, in fact for arbitrary…
Let \(a_1, \dots, a_p\) be (not necessarily distinct) residues modulo a prime \(p\), such that there exists some \(r\) so that if \(S \subseteq [p]\) is non-empty and \[\sum_{i \in S} a_i \equiv 0 \pmod{p}\] then \(|S| = r\). Must there be…
Let \(G\) be a graph with no isolated vertices and \(m\) edges. Is it true that \[R(G) \leq 2^{O(m^{1/2})}?\] This is true, and was proved by Sudakov [Su11]. This problem is #11 in Ramsey Theory in the graphs problem collection.
If \(T\) is a tree on \(n\) vertices then \[R(T) \leq 2n-2.\] This problem is #14 in Ramsey Theory in the graphs problem collection. Solved: the bound follows from the Erdős–Sós theorem (Erdős problem 548) by the pigeonhole principle, as…
Let \(n\geq k+1\). Every graph on \(n\) vertices with at least \(\frac{k-1}{2}n+1\) edges contains every tree on \(k+1\) vertices.
Let \(R_k(G)\) denote the minimal \(m\) such that if the edges of \(K_m\) are \(k\)-coloured then there is a monochromatic copy of \(G\). Is it true that \[R_k(T)\leq kn+O(1)\] for any tree \(T\) on \(n\) vertices? The answer is yes, with…
Let \(k\geq 3\). Is it true that, if \(m\) is sufficiently large, for any graph \(H\) on \(m\) edges without isolated vertices, \[R(C_k,H) \leq 2m+\left\lfloor\frac{k-1}{2}\right\rfloor?\] This was proved for even \(k\) by Erdős, Faudree,…
Show that for any rational \(\alpha \in [1,2)\) there exists a bipartite graph \(G\) such that \[\mathrm{ex}(n;G)\asymp n^{\alpha}.\] The proof constructs balanced rooted models for all rational parameters. Its upper-bound closure replaces…
Does there exist a graph \(G\) which contains no \(K_4\), and yet any \(2\)-colouring of the edges produces a monochromatic \(K_3\)? Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman…
Let \(α\) be the infinite ordinal \(\omega^{\omega}\). It was proved by Chang [Ch72] that any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\).
Let \(α\) be the infinite ordinal \(\omega^{\omega^2}\). Is it true that any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\)? This is true and was proved independently by Schipperus [Sc10] and…
**Erdős Problem 594** (Erdős–Hajnal [ErHa66], [Er69b]): Does every graph \(G\) with chromatic number \(\geq \aleph_1\) contain all sufficiently large odd cycles? The answer is **Yes**, proved by Erdős, Hajnal, and Shelah [EHS74]. A graph…
Erdős-Menger conjecture
**Erdős Problem 599** (the Erdős–Menger conjecture). Let \(G\) be a (possibly infinite) graph and let \(A, B\) be disjoint independent sets of vertices. Must there exist a family \(P\) of pairwise vertex-disjoint paths from \(A\) to \(B\),…
For a triangle-free graph \(G\) let \(h_2(G)\) be the smallest number of edges that need to be added to \(G\) so that it has diameter \(2\) and is still triangle-free. Is it true that if \(G\) has maximum degree \(o(n^{1/2})\) then…
Let \(G\) be a graph on \(n\) vertices, \(\alpha_1(G)\) be the maximum number of edges that contain at most one edge from every triangle, and \(\tau_1(G)\) be the minimum number of edges that contain at least one edge from every triangle.…
Suppose \(G\) is a graph on \(n\) vertices which contains no complete graph or independent set on \(\gg \log n\) many vertices. Must \(G\) contain \(\gg n^{5/2}\) induced subgraphs which pairwise differ in either the number of vertices or…
Is it true that if the edges of \(K_n\) are 2-coloured then there are at most \(n^2/4\) many edges which do not occur in a monochromatic triangle? Solved by Erdős, Rousseau, and Schelp for large \(n\), but unpublished. Alon has observed…
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 \(p_1,\ldots,p_k\) be distinct primes. Are there infinitely many \(n\) such that \(n!\) is divisible by an even power of each of the \(p_i\)? The answer is yes, proved by Berend [Be97], who further proved that the sequence of such…
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(\alpha_k\) be minimal such that, for all large enough \(n\),…
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…
Is there a set of \(n\) points in \(\mathbb{R}^2\) such that every subset of \(4\) points determines at least \(3\) distances, yet the total number of distinct distances is \(\ll \frac{n}{\sqrt{\log n}}\)? There does exist such a set: a…
Let \(1=d_1<\cdots <d_{\tau(n)}=n\) be the divisors of \(n\) and \[G(n) = \sum_{1\leq i<\tau(n)}\frac{d_i}{d_{i+1}}.\] Is it true that \(G(n)\to \infty\) for almost all \(n\)? The answer is yes: Tao observed that…
Are there any integer solutions to \(x^xy^y=z^z\) with \(x,y,z>1\)? Ko [Ko40] proved there are none if \((x,y)=1\), but there are in fact infinitely many solutions in general - for example, \(x=2^{12}3^6\), \(y = 2^83^8\), and…
Write \(M(n, k)\) be the least common multiple of \(\{n+1, \dotsc, n+k\}\). Let \(k\) be sufficiently large. Are there infinitely many \(m, n\) with \(m \geq n + k\) such that \[ M(n, k) > M(m, k + 1) \]? The answer is yes, as proved in a…
Is it true that for almost all \(n\) there exists some \(m\in (p_n,p_{n+1})\) such that \[p(m) \geq p_{n+1}-p_n,\] where \(p(m)\) denotes the least prime factor of \(m\)? This was solved in the affirmative by Gafni and Tao [GaTa25]. This…
For each \(m\) and \(\alpha\), the density of the set of integers which are divisible by some \(d \equiv 1 \pmod{m}\) with \(1 < d < \exp (m ^ \alpha)\) exists.
Is there some \(h(n)\to \infty\) such that for all \(2\leq i<j\leq n/2\) \[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq h(n)?\] This was resolved by Bergman [Be11], who proved that for any \(2\leq i<j\leq n/2\)…
Let \(r\geq 1\) and define \(T(n,r)\) to be maximal such that there exists a family \(\mathcal{F}\) of subsets of \(\{1,\ldots,n\}\) of size \(T(n,r)\) such that \(\lvert A\cap B\rvert\neq r\) for all \(A,B\in \mathcal{F}\). Estimate…
Ruzsa-Szemerédi problem
Let \(\mathcal{F}\) be the family of all \(3\)-uniform hypergraphs with \(6\) vertices and \(3\) \(3\)-edges. Is it true that \[\mathrm{ex}_3(n,\mathcal{F})=o(n^2)?\] The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known…
Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges such that in any \(2\)-colouring of the edges of \(H\) there is a monochromatic copy of \(G\). Is it true…
Let \(k>r\) and \(n\) be sufficiently large in terms of \(k\) and \(r\). Does there always exist a block \(r-(n,k,1)\) design (or Steiner system with parameters \((n,k,r)\)), provided the trivial necessary divisibility conditions…
Let \(\varepsilon\) be sufficiently small and \(C, C' > 0\). Are there integers \(a, b, n\) such that \[a, b > \varepsilon n\quad a!\, b! \mid n!\, (a + b - n)!, \] and \[C \log n < a + b - n < C' \log n ?\] Note that the website currently…
Let \(C>0\) be a constant. Are there infinitely many integers \(a,b,n\) with \(a+b> n+C\log n\) such that the denominator of \[\frac{n!}{a!b!}\]contains only primes \(\ll_C 1\)? Erdős [Er68c] proved that if \(a!b!\mid n!\) then…
Call a sequence \(1< X_1\leq \cdots \leq X_m\leq n\) block-compatible if there is a pairwise balanced block design \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(\lvert A_i\rvert=X_i\) for \(1\leq i\leq m\). (A pairwise block…
Cameron-Erdős conjecture
Let \(f(n)\) count the number of sum-free \(A\subseteq \{1,\ldots,n\}\), i.e. \(A\) contains no solutions to \(a=b+c\) with \(a,b,c\in A\). Is it true that \[f(n)=2^{(1+o(1))\frac{n}{2}}?\] The Cameron–Erdős conjecture. This is true, and…
Let \(f(m)\) be some function such that \(f(m)\to \infty\) as \(m\to \infty\). Does there exist a graph \(G\) of infinite chromatic number such that every subgraph on \(m\) vertices contains an independent set of size at least…
Erdős asked whether every \(n\)-point set in \(\mathbb{R}^6\) spans at most \((1/27 + o(1)) n^3\) unit equilateral triangles. Clemen, Dumitrescu, and Liu [CDL25b] proved the stronger any-size statement \(T_6(n) = (1/27 + o(1)) n^3\). The…
Let \(A\subset \mathbb{R}^2\) be a set of \(n\) points. Can there be \(\gg n\) many distinct distances each of which occurs for more than \(n\) many pairs from \(A\)? The answer is yes: Bhowmick [Bh24] constructs a set of \(n\) points in…
The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or independent set. If \(G\) is a graph with…
Let \(g_k(n)\) be the maximal number of edges possible on a graph with \(n\) vertices which does not contain a cycle with \(k\) chords incident to a vertex on the cycle. Is it true that \[g_k(n)=(k+1)n-(k+1)^2\] for \(n\) sufficiently…
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…
Suppose \(n\geq kr+(t-1)(k-1)\) and the edges of the complete \(r\)-uniform hypergraph on \(n\) vertices are \(t\)-coloured. Prove that some colour class must contain \(k\) pairwise disjoint edges. In other words, this problem asks to…
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 \(F(n)\) be the maximum possible size of a subset \(A \subseteq \{1, \ldots, n\}\) such that \(a \nmid bc\) whenever \(a, b, c \in A\) with \(a \neq b\) and \(a \neq c\). Is there a constant \(c\) such that \[F(n) = \pi(n) + (c + o(1))…
Let \(t(n)\) be the minimum number of points in \(\{1,\ldots,n\}^2\) such that the \(\binom{t}{2}\) lines determined by these points cover all points in \(\{1,\ldots,n\}^2\). Estimate \(t(n)\). In particular, is it true that \(t(n)=o(n)\)?…
If \(G\) is a graph on \(n\) vertices which has no two adjacent vertices of degree \(\geq 3\) then \[R(G)\ll n,\] where the implied constant is absolute. A problem of Burr and Erdős. Solved in the affirmative by Alon [Al94].
If \(G\) is a graph on \(n\) vertices containing no independent set on \(>n^{1/2}\) vertices then there is a set of \(\leq n^{1/2}\) vertices containing \(\gg n^{1/2}\log n\) edges. Proved by Alon [Al96b].
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 \(k\geq 2\) and \(G\) be a graph with \(n\geq k-1\) vertices and \[(k-1)(n-k+2)+\binom{k-2}{2}+1\] edges. Does there exist some \(c_k>0\) such that \(G\) must contain an induced subgraph on at most \((1-c_k)n\) vertices with minimum…
Let \(G\) be a graph with \(2n+1\) vertices and \(n^2+n+1\) edges. Must \(G\) contain two vertices of the same degree which are joined by a path of length \(3\)? A problem of Erdős and Hajnal. The example of \(K_{n,n+1}\) shows that this…
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…
Does the set of integers of the form \(n + \varphi(n)\) have positive (lower) density? [GIL24] proved this was true.
Is there an absolute constant \(C > 0\) such that every integer \(n\) with \(\sigma(n) > Cn\) is the distinct sum of proper divisors of \(n\)? This has been solved in the affirmative by Larsen - in fact, for any \(\epsilon>0\) there exists…
Does there exist an absolute constant \(c>0\) such that, for all \(r\geq 2\), in any \(r\)-uniform hypergraph with chromatic number \(3\) there is a vertex contained in at least \((1+c)^r\) many edges? This was solved by Erdős and Lovász…
Let \(G\) be a graph on \(3n\) vertices formed by taking \(n\) vertex disjoint triangles and adding a Hamiltonian cycle (with all new edges) between these vertices. Does \(G\) have chromatic number at most \(3\)? The answer is yes, proved…
Let \(A\subseteq \{1,\ldots,N\}\) be such that, for all \(a,b\in A\), the product \(ab\) is not squarefree. Is the maximum size of such an \(A\) achieved by taking \(A\) to be the set of even numbers and odd non-squarefree numbers? A…
Let \(\epsilon > 0\). Is there some \(r \ll_\epsilon 1\) such that the density of integers of the form \(2^k+n\), where \(k \geq 0\) and \(n\) has at most \(r\) prime divisors, is at least \(1-\epsilon\)? This was proved affirmatively by…
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…
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…
Let \(A=\{n_1<n_2<\cdots\}\subset \mathbb{N}\) be a lacunary sequence (so there exists some \(\epsilon>0\) with \(n_{k+1}\geq (1+\epsilon)n_k\) for all \(k\)). Is it true that there must exist a finite colouring of \(\mathbb{N}\) with no…
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…
Erdős-Mordell inequality
If \(A,B,C\in \mathbb{R}^2\) form a triangle and \(P\) is a point in the interior then, if \(N\) is where the perpendicular from \(P\) to \(AB\) meets the triangle, and similarly for \(M\) and \(L\), \[…
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 \(n=p^2+p+1\) for some prime power \(p\), and let \(A_1,\ldots,A_t\subseteq \{1,\ldots,n\}\) be a block design (so that every pair \(x,y\in \{1,\ldots,n\}\) is contained in exactly one \(A_i\)). Is it true that if \(t>n\) then…
Let \(r\geq 2\) and let \(t_r(n)\) be the Turán number (the maximal number of edges in a graph on \(n\) vertices with no \(K_{r+1}\)). If \(G\) is a graph with \(n\) vertices and \(m\geq t_r(n)\) edges there exists a clique on \(r\)…
Every graph with \(n\) vertices and \(>n^2/4\) edges contains an edge which is in at least \(n/6\) triangles. A conjecture of Bollobás and Erdős. This was proved independently by Edwards (unpublished) and Khadzhiivanov and Nikiforov…
Let \(f:\mathbb{R}\to \mathbb{R}\) be such that \(f(x+h)-f(x)\) is continuous for every \(h>0\). Is it true that \[f=g+h\] for some continuous \(g\) and additive \(h\) (i.e. \(h(x+y)=h(x)+h(y)\))? A conjecture of Erdős from the early…
Let \(r\geq 2\) and \(m\geq 1\). Every graph with \(rm\) vertices and minimum degree at least \(m(r-1)\) contains \(m\) vertex disjoint copies of \(K_r\). When \(r=2\) this follows from Dirac's theorem. Corrádi and Hajnal [CoHa63] proved…
Let \(k\geq 4\) and let \(f_k(n)\) be the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) in which every odd cycle has length \(> m\). Then \[f_k(n) \asymp n^{\frac{1}{k-2}}.\] A question of Erdős and…
Let \(k\geq 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\geq (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) have chromatic number at most \(k+2\)? A question of…
Is it true that, for every \(k\), there is some \(f(k)\) such that if \(G\) has chromatic number \(\geq f(k)\) then \(G\) contains a triangle-free subgraph with chromatic number \(\geq k\)? This is true, as shown by Rödl [Ro77].
Let \(k\geq 4\). Is it true that \[\mathrm{ex}(n;H_k) \ll_k n^{3/2},\] where \(H_k\) is the graph on vertices \(x,y_1,\ldots,y_k,z_1,\ldots,z_{\binom{k}{2}}\), where \(x\) is adjacent to all \(y_i\) and each pair of \(y_i,y_j\) is adjacent…
Are there infinitely many four-term arithmetic progressions of coprime powerful numbers? (A number \(n\) is *powerful* if \(p \mid n \to p^2 \mid n\); Nat.Powerful.) Erdős [Er76d] asked this; the answer is **yes**: Bajpai, Bennett and Chan…
There are infinitely many \(n\) such that \(τ(n) = τ(n+1)\). Proved in [He84]. Here τ is the divisor counting function, which is σ 0 in mathlib.
There is no exact covering system - that is, a finite collection of congruence classes \(a_i\pmod{n_i}\) with distinct \(n_i\) such that every integer satisfies exactly one of these congruence classes. This is true, and was proved…
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…
Let \(z_1,\ldots,z_n\in \mathbb{C}\) be a sequence such that \(z_1=1\). Suppose that the sequence of \[s_k=\sum_{1\leq i\leq n}z_i^k\] contains infinitely many \((n-1)\)-tuples of consecutive values of \(s_k\) which are all \(0\). Then…
If \(P(m)\) is the greatest prime divisor of \(m\), then is it true that \[\frac{P(2^n-1)}{n}\to \infty\] as \(n\to \infty\)? Schinzel [Sc62] proved that \(P(2^n-1)>2n\) for \(n>12\). In [Er65b] Erdős also asks about \(P(n!+1)\). Stewart…
Let \(\epsilon > 0\) and \(f_\epsilon(p)\) be the smallest integer \(m\) such that \(\sum_{n\leq N} \left(\frac{n}{p}\right)<\epsilon N\) for all \(N\geq m\). Prove that \[\sum_{p<x}f_\epsilon(p)\sim c_\epsilon \frac{x}{\log x}\] for some…
For any fixed \(s\geq 3\), \[R(s,k) \gg \frac{k^{s-1}}{(\log k)^c}\] for some constant \(c=c(s)>0\). According to Chung and Graham [ChGr98] this was first conjectured by Erdős in 1947. Proved by Bradač [Br26], with \(c=2s-4\). The linked…
Question 1: Is it true that \(\limsup_{k \to \infty} A_k = \infty\)? Erdős [Er64b] remarks it is "easy to see" that \(\limsup_k \sup_n |\sum_{j \le n} e(k x_j)| = \infty\). Erdős [Er65b] later found a "very easy" proof that…
Is it true that, for every \(\alpha\), the sequence \(\{ \alpha p_n\}\) is not well-distributed, if \(p_n\) is the sequence of primes? The answer is yes, by [APSSV26, Section 4]; a Lean formalisation is available in [Mo26].
Duffin-Schaeffer conjecture
For any function \(f:\mathbb{N}\to \mathbb{R}_{\geq 0}\) the property that, for almost all \(\alpha\) \[\left\lvert \alpha-\frac{p}{q}\right\rvert < \frac{f(q)}{q}\] has infinitely many solutions with \((p,q)=1\), is equivalent to…
Let \(A=\{n_1<n_2<\cdots\}\) be an infinite sequence of positive integers, and let \(\phi_A(k)\) count the number of \(1\leq m\leq n_k\) such that the fraction \(\frac{m}{n_k}\) cannot be written as \(\frac{b}{n_j}\) for any integer \(b\)…
Does every graph with \(m\) edges contain a subgraph with \(\gg m^{2/3}\) edges which contains no \(C_4\)? This problem was first solved in the affirmative by Conlon, Fox, and Sudakov [CFS14b]. A simple proof is given by Hunter in the…
Is it true that, for every \(c>0\), there exists \(f(c)\) such that every graph on \(n\) vertices with at least \(\lfloor n^2/4\rfloor+k\) edges, where \(k<c n\), contains at least \(k-f(c)\) many edge disjoint triangles? Erdős [Er71]…
Let \(t<\lfloor n/2\rfloor\). Does every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+t\) edges contain at least \(t\lfloor n/2\rfloor\) triangles? Rademacher proved that every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+1\)…
Let \(R(k,l)\) be the Ramsey number, so the minimal \(n\) such that every graph on at least \(n\) vertices contains either a \(K_k\) or an independent set on \(l\) vertices. Prove, for fixed \(k\geq 3\), that \[\lim_{l\to…
Is it true that, for every \(k \geq 3\), there is a constant \(c_k > 0\) such that \[\mathrm{ex}(n, G_k) \ll n^{3/2 - c_k},\] where \(G_k\) is the bipartite graph between \(\{y_1, \ldots, y_k\}\) and \(\{z_1, \ldots, z_{\binom{k}{2}}\}\),…
Is there a constant \(c_t\), where \(c_t\to \infty\) as \(t\to \infty\), such that if \(\mathcal{F}\) is a finite family of finite sets, all of size at least \(t\), and for every set \(X\) there are \(<c_t\lvert X\rvert\) many…
Let \(c>0\), and let \(n\) be sufficiently large depending on \(c\). Suppose that \(\mathcal{F}\) is a family of at most \(c2^n\) many finite sets of size \(n\). Let \(X=\cup_{A\in \mathcal{F}}A\). Must there exist…
Let \(G\) be a graph on \(n\) vertices which does not contain a trivial (empty or complete) graph on more than \(c\log n\) vertices. Must \(G\) contain at least \(2^{\Omega_c(n)}\) many induced subgraphs which are not pairwise isomorphic?…
**Erdős Problem 1050.** The series \(\sum_{n=1}^\infty \frac{1}{2^n - 3}\) is irrational. The source sum runs over \(n \ge 1\); as a tsum over ℕ (which starts at \(0\)) it is reindexed \(n \mapsto n + 1\), i.e.…
Is it true that if \(a_0 < a_1 < a_2 < \cdots\) is a strictly increasing sequence of integers with \(\liminf a_n^{1/2^n} > 1\), then the series \(\sum_{n=0}^\infty \frac{1}{a_n \cdot a_{n+1}}\) is irrational? This was solved in the…
Let \(2=p_1<p_2<\cdots\) be the sequence of prime numbers. Are there only finitely many \(n\) such that \(n\in [p_{k-1},p_k)\) and the only primes dividing \(n!+1\) are \(p_{k}\) and \(p_{k+1}\)? A conjecture of Erdős and Stewart, as…
Let \(ϕ(n)\) be the Euler's totient function, then the \(n\) satisfies \(ϕ(n)>ϕ(n - ϕ(n))\) have asymptotic density 1. Reference: [LuPo02] Luca, Florian and Pomerance, Carl, On some problems of {M}\polhk akowski-{S}chinzel and {E}rd\H os…
Can a finite set of disjoint unit segments in a unit square be maximal? Solved affirmatively by [Da85], who gave an explicit construction. This was formalized in Lean by Alexeev using Aristotle and ChatGPT.
Let \(k\geq 3\). Does there exist a finite set \(A\subset \mathbb{R}^2\) such that, in any \(2\)-colouring of \(A\), there exists a line which contains at least \(k\) points from \(A\), and all the points of \(A\) on the line have the same…
Let \(1<q<1+\epsilon\) and consider the set of numbers of the shape \(\sum_{i\in S}q^i\) (for all finite \(S\)), ordered by size as \(0=x_1<x_2<\cdots\). Is it true that, provided \(\epsilon>0\) is sufficiently small,…
Let \(G\) be a group and \(\Gamma=\Gamma(G)\) be the non-commuting graph, with vertices the elements of \(G\) and an edge between \(g\) and \(h\) if and only if \(g\) and \(h\) do not commute, \(gh\neq hg\). If \(\Gamma\) contains no…
Let \(1=d_1<\cdots<d_{\tau(n)}=n\) be the divisors of \(n\), and for \(\alpha>1\) let \[h_\alpha(n) = \sum_i \left( \frac{d_{i+1}}{d_i}-1\right)^\alpha.\] Is it true that \[\liminf_{n\to \infty}h_\alpha(n) \ll_\alpha 1?\] Erdős [Er81h]…
The anti-Ramsey number \(\mathrm{AR}(n,G)\) is the maximum possible number of colours in which the edges of \(K_n\) can be coloured without creating a rainbow copy of \(G\) (i.e. one in which all edges have different colours). Let \(C_k\)…
If \(C_1,\ldots,C_n\) are circles in \(\mathbb{R}^2\) with radii \(r_1,\ldots,r_n\) such that no line disjoint from all the circles divides them into two non-empty sets then the circles can be covered by a circle of radius \(r=\sum r_i\).…
Let \(f:\mathbb{R}\to \mathbb{R}\) be such that \[2f(x) \leq f(x+h)+f(x+2h)\] for every \(x\in \mathbb{R}\) and \(h>0\). Must \(f\) be monotonic? A problem of Kemperman [Ke69], who proved it is true if \(f\) is measurable. Erdős [Er81b]…
If \[f(x+y)=f(x)+f(y)\] for almost all \(x,y\in \mathbb{R}\) then there exists a function \(g\) such that \[g(x+y)=g(x)+g(y)\] for all \(x,y\in\mathbb{R}\) such that \(f(x)=g(x)\) for almost all \(x\). Proved independently by de Bruijn…
Does there exist \(A\subset \mathbb{N}\) with lower density \(>1/3\) such that \(a+b\neq 2^k\) for any \(a,b\in A\) and \(k\geq 0\)? Müller [Mu11] settled this question in the affirmative: in fact one can take \(A\) to be the set of all…
Can every large integer \(n\) be written as \(n=x^2+y^2-z^2\) with \(\max(x^2,y^2,z^2)\leq n\)? This was proved affirmatively by Chojecki [Ch26], using a Duke-type equidistribution theorem. A Lean formalisation of the reduction…
Let \(\alpha>0\) be a real number, not an integer. The density of integers \(n\geq 1\) for which \((n,\lfloor n^\alpha\rfloor)=1\) is \(6/\pi^2\). This is true, and was proved by Bergelson and Richter [BeRi17].
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 \(\epsilon>0\). Does there exist a constant \(C_\epsilon\) such that, for all primes \(p\), every residue modulo \(p\) is the sum of at most \(C_\epsilon\) many elements of \[\{ n^{-1} : 1\leq n\leq p^\epsilon\}\] where \(n^{-1}\)…
Is it true that, for any \(x\), if \(A\subset [x,\infty)\) is a primitive set of integers (so that no distinct elements of \(A\) divide each other) then\[\sum_{a\in A}\frac{1}{a\log a}< 1+o(1),\]where the \(o(1)\) term \(\to 0\) as…
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…
Let \(x,y\geq 1\) be integers such that, for all \(n\geq 1\), the set of primes dividing \(x^{n}-1\) is equal to the set of primes dividing \(y^n-1\). Must \(x=y\)? Erdős asked this at a 1988 number theory conference in Banff. A positive…
Let \((n_k)\) be an increasing sequence of integers such that \(2^{\aleph_{n_k}}\) is strictly increasing, and \(2^{\aleph_{n_0}} > \aleph_\omega\). Is it true that \[\sum_k 2^{\aleph_{n_k}} \to (\aleph_\omega)^2?\] Here…