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.
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].…
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…
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]…
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…
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.…
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…
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…
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].
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 \(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,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 \(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 \(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…
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 \(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…
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…
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 \(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…
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 \(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.…
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 \(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…
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.
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 \(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…
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\).
**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…
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.…
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 \(\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…
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 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 \(\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…
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…
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)\)?…
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…
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…
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…
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…
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 \(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…
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].
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 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…
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].
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…
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 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 \(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…
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…
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…
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…