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.
If \(A\subseteq\{1, ..., N\}\) with \(|A| = n\) is such that the subset sums \(\sum_{a\in S}a\) are distinct for all \(S\subseteq A\) then \[ N \gg 2 ^ n. \] This conjecture is false. A machine-checked disproof constructs sum-distinct sets…
Can the smallest modulus of a covering system be arbitrarily large? This problem has a negative answer: there is a universal bound on the least modulus of any distinct covering system.
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…
Is the set of odd integers not of the form \(2^k+p\) the union of an infinite arithmetic progression and a set of density \(0\)? Erdős called this conjecture "rather silly". Chen [Ch23] has proved the answer is no. This was formalized in…
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,…
Let \(A\subset\mathbb{N}\) be infinite such that \(\sum_{a \in A} \frac{1}{a} = \infty\). Must there exist some \(k\geq 1\) such that almost all integers have a divisor of the form \(a+k\) for some \(a\in A\)? This was formalized in Lean…
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].
For any permutation \(\pi\in S_n\) of \(\{1,\ldots,n\}\) let \(S(\pi)\) count the number of distinct consecutive sums, that is, sums of the shape \(\sum_{u\leq i\leq v}\pi(i)\). Is it true that \[ S(\pi) = o(n^2) \] for all \(\pi\in S_n\)?…
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…
**Erdős Problem 42**: Let M ≥ 1 and N be sufficiently large in terms of M. Is it true that for every maximal Sidon set A ⊆ {1,…,N} there is another Sidon set B ⊆ {1,…,N} of size M such that (A - A) ∩ (B - B) = {0}? This was proved for all…
If \(A\) and \(B\) are Sidon sets in \(\{1,\ldots,N\}\) with \((A-A)\cap(B-B)=\{0\}\), is it true that \[\binom{\lvert A\rvert}{2}+\binom{\lvert B\rvert}{2}\leq\binom{f(N)}{2}+O(1)?\] The answer is no; the Erdős Problems page notes that…
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…
Suppose \(A \subseteq \{1,\dots,N\}\) is such that there are no \(k+1\) elements of \(A\) which are relatively prime. An example is the set of all multiples of the first \(k\) primes. Is this the largest such set? To avoid trivial…
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]…
Let \(f(n)\to \infty\) possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on \(n\) vertices can be made bipartite by deleting at most \(f(n)\) edges? The answer is no. A machine-checked…
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…
unit distance problem
Does every set of \(n\) distinct points in \(\mathbb{R}^2\) contain at most \(n^{1+O(\frac{1}{\log\log n})}\) many pairs which are distance \(1\) apart? This was…
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…
Let \(A,B\subset \mathbb{R}^2\) be disjoint sets of size \(n\) and \(n-3\) respectively, with not all of \(A\) contained on a single line. Is there a line which contains at least two points from \(A\) and no points from \(B\)? This has…
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 \(G\) is bipartite then \(\mathrm{ex}(n;G)\ll n^{3/2}\) if and only \(G\) is \(2\)-degenerate, that is, \(G\) contains no induced subgraph with minimal degree at least 3. Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered…
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…
Is it true that \(\limsup M_n = \infty\)? This is Problem 4.1 in [Ha74] where it is attributed to Erdős. The weaker conjecture that \(\limsup M_n=\infty\) was proved by Wagner [Wa80], who show that there is some \(c>0\) with…
Let \(F_{k}(N)\) be the size of the largest \(A\subseteq \{1,\ldots,N\}\) such that the product of no \(k\) many distinct elements of \(A\) is a square. Is \(F_5(N)=(1-o(1))N\)? Conjectured by Erdős, Sós, and Sárközy [ESS95], who proved…
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 \(A\) be the set of integers which have only the digits \(0, 1\) when written base 3, -/ local notation "A" => { x : ℕ | (digits 3 x).toFinset ⊆ {0, 1} } /-- and \(B\) be the set of integers which have only the digits \(0, 1\) when…
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)\).
If \(H\) is bipartite and is \(r\)-degenerate, that is, every induced subgraph of \(H\) has minimum degree \(\leq r\), then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\] The answer is no. OpenAI [OpenAI26] give a connected bipartite 2-degenerate H…
If \(H\) is bipartite with minimum degree \(r\) then there exists \(\epsilon=\epsilon(H)>0\) such that \[\mathrm{ex}(n;H) \gg n^{2-\frac{1}{r-1}+\epsilon}.\] Conjectured by Erdős and Simonovits [ErSi84]. A probabilistic argument shows that…
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}…
If \(\mathcal{F}\) is a finite set of finite graphs then \(\mathrm{ex}(n;\mathcal{F})\) is the maximum number of edges a graph on \(n\) vertices can have without containing any subgraphs from \(\mathcal{F}\). Note that it is trivial that…
Let \(R(3;k)\) be the minimal \(n\) such that if the edges of \(K_n\) are coloured with \(k\) colours then there must exist a monochromatic triangle. Determine \[\lim_{k\to \infty}R(3;k)^{1/k}.\] There is no finite limit:…
Let \(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…
If \(\mathbb{R}^2\) is finitely coloured then must there exist some colour class which contains the vertices of a rectangle of every area? Graham, "On Partitions of 𝔼ⁿ", Journal of Combinatorial Theory, Series A 28, 89-91 (1980). (See…
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 \(A=\{a_1,a_2,\ldots\}\subset \mathbb{R}^d\) be an infinite sequence such that \(a_{i+1}-a_i\) is a positive unit vector (i.e. is of the form \((0,0,\ldots,1,0,\ldots,0)\)). For which \(d\) must \(A\) contain a three-term arithmetic…
Let \(S \subseteq \mathbb{Z}^3\) be a finite set and let \(A = \lbrace a_1, a_2, \ldots \rbrace\) be an infinite \(S\)-walk, so that \(a_{i+1} - a_i \in S\) for all \(i\). Must \(A\) contain three collinear points? Cambie and Kalviainen…
Let \(k\geq 3\). Must any ordering of \(\mathbb{R}\) contain a monotone \(k\)-term arithmetic progression, that is, some \(x_1 <\cdots < x_k\) which forms an increasing or decreasing \(k\)-term arithmetic progression? The answer is no,…
Let \(V\) be a vector space over the rationals and let \(k\) be a fixed positive integer. Then there is a set \(X_k \subseteq V\) such that \(X_k\) meets every infinite arithmetic progression in \(V\) but \(X_k\) intersects every…
If \(A\subset \mathbb{R}\) does not contain a 3-term arithmetic progression then must \(\mathbb{R}\backslash A\) contain an infinite arithmetic progression? Baumgartner [Ba75] answered this in the negative.
Let \(n_1<\cdots < n_r\leq N\) with associated \(a_i\pmod{n_i}\) such that the congruence classes are disjoint (that is, every integer is \(\equiv a_i\pmod{n_i}\) for at most one \(1\leq i\leq r\)). How large can \(r\) be in terms of…
Are there \(n\) such that there is a covering system with moduli the divisors of \(n\) which is 'as disjoint as possible'? That is, for all \(d\mid n\) with \(d>1\) there is an associated \(a_d\) such that every integer is congruent to…
Is it true that all sufficiently large \(n\) can be written as \(2^k+m\) for some \(k\geq 0\), where \(\Omega(m)<\log\log m\)? (Here \(\Omega(m)\) is the number of prime divisors of \(m\) counted with multiplicity.) Barreto and Leeham,…
Let \(x>0\) be a real number. For any \(n\geq 1\) let \[R_n(x) = \sum_{i=1}^n\frac{1}{m_i}<x\] be the maximal sum of \(n\) distinct unit fractions which is \(<x\). Is it true that, for almost all \(x\), for sufficiently large \(n\), we…
Let \(A\) be a finite collection of \(d\geq 4\) non-parallel lines in \(\mathbb{R}^2\) such that there are no points where at least four lines from \(A\) meet. Must there exist a 'Gallai triangle' (or 'ordinary triangle'): three lines from…
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 \(P(z)=\sum_{1\leq k\leq n}a_kz^k\) for some \(a_k\in \mathbb{C}\) with \(\lvert a_k\rvert=1\) for \(1\leq k\leq n\). Does there exist a constant \(c>0\) such that, for \(n\geq 2\), we have \[\max_{\lvert z\rvert=1}\lvert P(z)\rvert…
Let \(S\) be a string of length \(2^k-1\) formed from an alphabet of \(k\) characters. Must \(S\) contain an abelian square: two consecutive blocks \(x\) and \(y\) such that \(y\) is a permutation of \(x\)? Erdős initially conjectured that…
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_1 < a_2 < \dotsc\) be an infinite sequence of positive integers such that \(\frac{a_{i+1}}{a_i} \to 1\). If every arithmetic progression contains infinitely many integers which are the sum of distinct \(a_i\) then every…
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 \(a_n\) be an infinite sequence of positive integers such that \(\sum \frac{1}{a_n}\) converges. There exists some integer \(t \ge 1\) such that \(\sum \frac{1}{a_n + t}\) is irrational. This was disproven by Kovač and Tao in [KoTa24].…
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]. -
Let \(f(n)\to \infty\) as \(n\to \infty\). Is it true that \[\sum_{n\geq 1} \frac{1}{(n+1)\cdots (n+f(n))}\] is irrational? Erdős and Graham [ErGr80] write 'the answer is almost surely in the affirmative if \(f(n)\) is assumed to be…
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 of integers with associated \(a_k\pmod{n_k}\), such that for some \(\epsilon>0\) we have \(n_k>(1+\epsilon)k\log k\) for all \(k\). Then \[ \#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for…
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 there an infinite sequence \(a_1 < a_2 < \dots\) such that \(a_{i+1} - a_i = O(1)\) and no finite sum of \(\frac{1}{a_i}\) is equal to 1? There does not exist such a sequence, which follows from the positive solution to…
Let \(A(N)\) denote the maximal cardinality of \(A\subseteq \{1,\ldots,N\}\) such that \(\sum_{n\in S}\frac{1}{n}\neq 1\) for all \(S\subseteq A\). Estimate \(A(N)\). Erdős and Graham [ErGr80] believe the answer is \(A(N)=(1+o(1))N\).…
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 \(N\geq 1\). How many integers can be written as the sum of distinct unit fractions with denominators from \(\{1,\ldots,N\}\)? Are there \(o(\log N)\) such integers? If the number of such integers is \(N(n)\) then it is trivial that…
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…
Is it true that if \(A \subseteq \mathbb{N}\setminus\{1\}\) is a finite set with \(\sum_{n \in A} \frac{1}{n} < 2\) then there is a partition \(A=A_1 \sqcup A_2\) such that \(\sum_{n \in A_i} \frac{1}{n} < 1\) for \(i=1,2\)? This is not…
There exists a set A with positive density that does not have property P₁. #TODO: prove this lemma by assuming erdos_318.contain_single_even. The density sits in an existential, so HasPosDensity is the *stronger* reading here and weakening…
Suppose \(A\subseteq\mathbb{N}\) and \(C>0\) is such that \(1_A\ast 1_A(n)\leq C\) for all \(n\in\mathbb{N}\). Can \(A\) be partitioned into \(t\) many subsets \(A_1,\ldots,A_t\) (where \(t=t(C)\) depends only on \(C\)) such that…
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…
Let \(A,B\subseteq \mathbb{N}\) such that for all large \(N\[\)\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}\]and\[\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}.\] Is it true that there are infinitely many solutions to…
Let \(A\subseteq \mathbb{N}\) be a set of density zero. Does there exist a \(B\) such that \(A\subseteq B+B\) and \[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\] for all large \(N\)? The answer is no. Erdős and Newman [ErNe77] have…
Let \(A\subseteq \mathbb{N}\) be an additive basis (of any finite order) such that \(\lvert A\cap \{1,\ldots,N\}\rvert=o(N)\). Is it true that \[ \lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert} {\lvert A\cap…
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…
Is it true that, for each fixed \(n\) and fixed sizes \(k_1,\ldots,k_n \geq 4\), there are only finitely many collections of disjoint intervals \(I_1,\ldots,I_n\) of size \(\lvert I_i\rvert = k_i\) for \(1\leq i\leq n\) such…
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…
Does there exists a constant c such that f n - 2 * n ~ c * (n / log n)?
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…
Are there only finitely many solutions to \[ \prod_i \binom{2m_i}{m_i}=\prod_j \binom{2n_j}{n_j} \] with the \(m_i,n_j\) distinct? Somani, using ChatGPT, has given a negative answer. In fact, for any \(a\geq 2\), if \(c=8a^2+8a+1\),…
Is it true that there are no solutions to n! = x^k ± y^k with x,y,n ∈ ℕ, x*y > 1, and k > 2? The answer is no: Jonas Barfield found the counterexample 10! = 48^4 - 36^4 (equivalently, 10! + 36^4 = 48^4). This is discussed in problem D2 of…
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…
If \(\tau(n)\) counts the number of divisors of \(n\), then what is the set of limit points of \[ \frac{\tau((n+1)!)}{\tau(n!)}? \] The limit points are exactly \(\{1\} \cup \{1+1/k : k \geq 1\}\).
We say \(H\) is a unique subgraph of \(G\) if there is exactly one way to find \(H\) as a subgraph (not necessarily induced) of \(G\). Is there a graph on \(n\) vertices with \[\gg \frac{2^{\binom{n}{2}}}{n!}\] many distinct unique…
**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?
Is it true that, if \(A\subseteq \mathbb{N}\) is sparse enough and does not cover all residue classes modulo \(p\) for any prime \(p\), then there exists some \(n\in \mathbb{Z}\) such that \(n+a\) is prime for all \(a\in A\)? Weisenberg…
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 \(N\geq 1\). What is the size of the largest \(A\subset \{1,\ldots,N\}\) such that \([a,b]\leq N\) for all \(a,b\in A\), where \([a,b]\) is the least common multiple of \(a\) and \(b\)? Is it attained by choosing all integers in…
Let \(\operatorname{Log} x := \max\{\log x, 1\}\), \(\operatorname{Log}_2x = \operatorname{Log} (\operatorname{Log} x)\), and \(\operatorname{Log}_3x = \operatorname{Log}(\operatorname{Log}(\operatorname{Log} x)).\) Is it true that if…
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]…
Let \(\tau(n)\) count the divisors of \(n\) and \(\tau^+(n)\) count the number of \(k\) such that \(n\) has a divisor in \([2^k, 2^{k+1})\). Is it true that, for all \(\epsilon > 0\), \[ \tau^+(n) < \epsilon \cdot \tau(n) \] for almost all…
Is it true that, for all sufficiently large \(n\), there exists some \(i<n\) such that \[ p_n^2 < p_{n+i}p_{n-i}, \] where \(p_k\) is the \(k\)th prime? Pomerance proved that the answer is no.
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 \(f(u)\) be the largest \(v\) such that no \(m\in (u,v)\) is composed entirely of primes dividing \(uv\). Estimate \(f(u)\). The estimate \(u + 2 \le f(u) \le u^2\) holds for every \(u \ge 2\). The upper bound is attained when \(u\) is…
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…
Dedekind's problem
How many antichains in \([n]\) are there? That is, how many families of subsets of \([n]\) are there such that, if \(\mathcal{F}\) is such a family and \(A,B\in \mathcal{F}\), then \(A\not\subseteq B\)? Sperner's theorem states that…
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,…
What is the size of the largest \(A\subseteq \mathbb{R}^n\) such that there are only two distinct distances between elements of \(A\)? That is, \[\# \{ \lvert x-y\rvert : x\neq y\in A\} = 2.\] Asked to Erdős by Coxeter. Bannai, Bannai, and…
Borsuk's problem
**Erdős Problem 505** (disproved). Borsuk's conjecture is false for sufficiently large \(n\): there exists a dimension \(n\) and a bounded set \(S \subseteq \mathbb{R}^n\) with at least two points that cannot be covered by \(n + 1\)…
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.
Let \(f(z)=\sum_{0\leq k\leq n} \epsilon_k z^k\) be a random polynomial, where \(\epsilon_k\in \{-1,1\}\) independently uniformly at random for \(0\leq k\leq n\). Is it true that, if \(R_n\) is the number of roots of \(f(z)\) in…
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…
Let \(\delta > 0\). If \(n\) is sufficiently large and \(G\) is a graph on \(n\) vertices with no \(K_5\) and at least \(\delta n^2\) edges, must \(G\) contain a set of \(\gg_\delta n\) vertices spanning no triangle? Equivalently, writing…
Let \(\epsilon>0\) and \(N\) be sufficiently large. If \(A\subseteq \{1,\ldots,N\}\) has \(\lvert A\rvert \geq \epsilon N\) then must there exist \(a_1,a_2,a_3\in A\) and distinct primes \(p_1,p_2,p_3\) such that \[a_1p_1=a_2p_2=a_3p_3?\]…
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 \(m_1\leq\cdots\leq m_k\) and \(n\) be sufficiently large. If \(T\) is a tree on \(n\) vertices and \(G\) is the complete multipartite graph with vertex class sizes \(m_1,\ldots,m_k\) then prove that \[R(T,G)\leq…
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…
**Erdős Problem 613:** Let \(n \geq 3\) and \(G\) be a graph with \(\binom{2n+1}{2} - \binom{n}{2} - 1\) edges. Must \(G\) be the union of a bipartite graph and a graph with maximum degree less than \(n\)?
Does there exist some constant \(c > 0\) such that for all sufficiently large \(n\), if \(G\) is a graph with \(n\) vertices and at least \((1/8 - c)n^2\) edges then \(G\) must contain either a \(K_4\) or an independent set on at least…
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…
**Erdős Problem 619** [EGR98, Er99]: For a triangle-free graph \(G\) let \(h_r(G)\) be the smallest number of edges that need to be added to \(G\) so that it has diameter \(r\) (while preserving the property of being triangle-free). Is it…
Let \(G\) 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 \(g(n)\) denote the largest \(t\) such that there exist integers \(2\leq a_1<a_2<\cdots <a_t <n\) such that \[P(a_1)>P(a_2)>\cdots >P(a_t)\] where \(P(m)\) is the greatest prime factor of \(m\). Estimate \(g(n)\). Stijn Cambie has…
Let \(P(m)\) denote the greatest prime factor of \(m\). Is it true that, for any two primes \(p,q\), there exists some integer \(n\) such that \(P(n)=p\) and \(P(n+1)=q\)? In fact, the answer to this question as written is easily seen to…
Let \(f(m)\) be such that if \(A\subseteq \{1,\ldots,N\}\) has \(\lvert A\rvert=m\) then every interval in \([1,\infty)\) of length \(2N\) contains \(\geq f(m)\) many distinct integers \(b_1,\ldots,b_r\) where each \(b_i\) is divisible by…
Let \(\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 \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Is it true that, for every \(\epsilon>0\), if \(n\) is sufficiently large, every subgraph of \(Q_n\) with \[\geq \epsilon…
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…
Let \(\delta_1(n,m)\) be the density of the set of integers with exactly one divisor in \((n,m)\). Is \(\delta_1(n,m)\) unimodular for \(m>n+1\) (i.e. increases until some \(m\) then decreases thereafter)? Cambie has calculated that…
Let \(f_\max(n)\) be the largest \(m\) such that \(\phi(m) = n\), and \(f_\min(n)\) be the smallest such \(m\), where \(\phi\) is Euler's totient function. Investigate \[ \max_{n\leq x}\frac{f_\max(n)}{f_\min(n)}. \] GPT-5.5 Pro (prompted…
Is it true that \(H(n)/h(n)\to \infty\) for almost all \(n\)? Formalised as: for every threshold \(M\), the set of \(n\) with \(h(n) > 0\) and \(H(n)/h(n) > M\) has natural density \(1\). This is false: in fact, \(H(n)/h(n) = 2 + o(1)\)…
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…
**Erdős Problem 707**: It is false that any finite Sidon set can be embedded in a perfect different set modulo some \(n\). As described in [arxiv/2510.19804], a counterexample is provided in [Ha47], see below. The proof of this has been…
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 \(A\subseteq \mathbb{N}\) be such that \(A+A\) has positive upper density. Can one always decompose \(A=A_1\sqcup A_2\) such that \(A_1+A_1\) and \(A_2+A_2\) both have positive upper density? This was proved by the DeepMind prover…
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…
Let \(G\) be a graph with chromatic number \(\chi(G)=4\). If \(m_1<m_2<\cdots\) are the lengths of the cycles in \(G\) then can \(\min(m_{i+1}-m_i)\) be arbitrarily large? The answer is no: Bondy and Vince [BoVi98] proved that every graph…
The list chromatic number \(\chi_L(G)\) is defined to be the minimal \(k\) such that for any assignment of a list of \(k\) colours to each vertex of \(G\) (perhaps different lists for different vertices) a colouring of each vertex by a…
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…
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 empty graph. Is it true that if \(G\) has no…
Give an asymptotic formula for \(\mathrm{ex}(n; C_4)\). Erdős and Klein [Er38] proved \(\mathrm{ex}(n; C_4) \asymp n^{3/2}\), and Reiman [Re58] proved \[\frac{1}{2\sqrt 2} \le \lim \frac{\mathrm{ex}(n; C_4)}{n^{3/2}} \le \frac12.\] Erdős…
Is there a \(3\)-uniform hypergraph on \(n\) vertices which contains at least \(n-O(1)\) different sizes of cliques (maximal complete subgraphs)? The answer is no, as proved by Gao [Ga25]: more generally, for any \(k\geq 3\), every…
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))…
Is it true that every \(3\)-uniform hypergraph on \(3n\) vertices with at least \(n^3+1\) edges must contain either a subgraph on \(4\) vertices with \(3\) edges or a subgraph on \(5\) vertices with \(7\) edges? Harris has provided the…
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)\)?…
We call a graph \(H\) \(D\)-balanced (or \(D\)-almost-regular) if the maximum degree of \(H\) is at most \(D\) times the minimum degree of \(H\). Is it true that for every \(m\geq 1\), if \(n\) is sufficiently large, any graph on \(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…
Let \(C > 0\). Is it true that the set of integers of the form \(n = b_1 + \cdots + b_t\), with \(b_1 < \cdots < b_t\), where \(b_i = 2^{k_i}3^{l_i}\) for \(1 \leq i\leq t\) and \(b_t \leq Cb_1\) has density \(0\)? van Doorn and Everts…
**Erdős Problem 846** Let A ⊂ ℝ² be an infinite set for which there exists some ϵ>0 such that in any subset of A of size n there are always at least ϵn with no three on a line. Is it true that A is the union of a finite number of sets…
Let \(A \subset \mathbb{N}\) be an infinite set for which there exists some \(\epsilon > 0\) such that in any subset of \(A\) of size \(n\) there is a subset of size at least \(\epsilon n\) which contains no three-term arithmetic…
Let \(A_1(N)\) be the number of maximal Sidon subsets of \(\{1,\ldots,N\}\). Is it true that \[A_1(N) < 2^{o(N^{1/2})}?\] A problem of Cameron and Erdős. This is resolved as a consequence of results of Saxton and Thomason [SaTh15] - they…
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…
Is it true that if \(A=\{a_1<\cdots <a_t\}\subseteq \{1,\ldots,N\}\) has no solutions to \[a_i+a_{i+1}+\cdots+a_j\in A\] then \[\lvert A\rvert \leq \frac{N}{2}+O(1)?\] In fact this problem is false. Freud [Fr93] constructed a sequence with…
Let \(A\) be an additive basis of order \(2\), let \(f(n)\) denote the number of ways in which \(n\) can be written as the sum of two elements from \(A\). If \(f(n) \to \infty\) as \(n \to \infty\), then must \(A\) contain a minimal…
Let \(A\) be an additive basis of order \(2\), and suppose \(1_A\ast 1_A(n)\to \infty\) as \(n\to \infty\). Can \(A\) be partitioned into two disjoint additive bases of order \(2\)? A question of Erdős and Nathanson [ErNa88], who proved…
For a natural number n, let \(1 = d_1 < \dotsc < d_{\tau(n)} = n\) denote the divisors of \(n\) in increasing order. Does it hold that…
What is the size of the largest \(A\subseteq \{1,\ldots,n\}\) such that if \(a\leq b\leq c\leq d\in A\) are such that \(abcd\) is a square then \(ad=bc\)? This was proved by GPT-5.5 Pro (prompted by Chojecki).
Let \(f(n)\) be an additive function (so that \(f(ab)=f(a)+f(b)\) if \((a,b)=1\) such that \(\limsup_{p,k} f(p^k) / \log(p^k) = ∞\). Is it true that \(\limsup_n (f(n+1)−f(n))/ \log n = ∞\)? The answer is no; this follows from a…
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].
Let \(g(n)\) be the maximum number of different sizes of cliques that can occur in a graph on \(n\) vertices. Estimate \(g(n)\) - in particular, is it true that \[g(n) = n - \log_2 n - \log_*(n) + O(1),\] where \(\log_*(n)\) is the number…
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 \(A\subset \mathbb{R}^2\) be a finite set of size \(n\), and let \(\{d_1,\ldots,d_k\}\) be the set of distances determined by \(A\). Let \(f(d)\) be the multiplicity of \(d\), that is, the number of unordered pairs from \(A\) of…
Erdős asks in [Er75b] if for every 2-coloring of ℝ, there is an uncountable set \(A ⊆ ℝ\) such that all sums \(a + b\) for \(a, b ∈ A, a ≠ b\) have the same colour. In [Ko16] Péter Komjáth constructed a counterexample. The same result was…
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 \(1<a_1<\cdots\) be a sequence of integers such that \(\sum\frac{1}{a_i}<\infty\). Is it true that, for every \(t\in \mathbb{R}\), \[1+\sum_{k}\frac{1}{a_k^{1+it}}\neq 0?\] Yip [Yi25] has proved that this is not always true - in fact,…
Does there exist a constant \(C>1\) such that, for every \(n\geq 2\), there exists a sequence \(z_i\in \mathbb{C}\) with \(z_1=1\) and \(\lvert z_i\rvert \geq 1\) for all \(1\leq i\leq n\) with…
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…
Let \(f=a_0+\cdots+a_dx^d\in \mathbb{C}[x]\) be a polynomial. Is it true that, if \(f\) has roots \(z_1,\ldots,z_d\) with corresponding arguments \(\theta_1,\ldots,\theta_d\in [0,2\pi]\), then for all intervals \(I\subseteq [0,2\pi]\) \[…
Let \(E\subseteq (0,1)\) be a meaurable subset with Lebesgue measure \(\lambda(E)\). Is it true that, for almost all \(\alpha\), \[\lim_{n\to \infty}\frac{1}{n}\sum_{1\leq k\leq n}1_{\{k\alpha \}\in E}=\lambda(E)\] for all \(E\)? This is a…
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\)…
The dimension of a graph \(G\) is the minimal \(n\) such that \(G\) can be embedded in \(\mathbb{R}^n\) such that every edge of \(G\) is a unit line segment. What is the smallest number of edges in a graph with dimension \(4\)? Answer: The…
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 \(F(n)\) be the maximal size of a family of subsets of \(\{1,\ldots,n\}\) such that no set in this family is the union of other members of the family. Is it true that there is a constant \(c>0\) such that \[F(n)\sim c…
Let \(f\) be a function from all pairs of elements in \(\{1,\ldots,n\}\) to \(\{1,\ldots,n\}\) such that \(f(x,y)\neq x\) and \(\neq y\) for all \(x,y\). We call \(X\subseteq \{1,\ldots,n\}\) independent if whenever \(x,y\in X\) we have…
Let \(x_1,\ldots,x_n\) be a sequence of distinct real numbers. Determine \[ \max\left(\sum x_{i_r}\right), \] where the maximum is taken over all monotonic subsequences. This is as Erdős posed the problem in [Er71], which is rather…
Let \[H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert,\] where \(f\) ranges over all functions \(f:\{1,\ldots,n\}^2\to \{-1,1\}\). Estimate \(H(n)\). Erdős [Er63d] proved \[\frac{n}{4}\leq H(n)…
Let \(G\) be a graph on \(n\) vertices with \(>n^2/4\) many edges. Must there be a triangle \(T\) in \(G\) and vertices \(y_1,\ldots,y_t\), where \(t>(\frac{1}{2}-o(1))n\), such that every \(y_i\) is joined to at least two vertices of…
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?…
Let \(G\) be a graph on \(n\) vertices in which every degree occurs at most twice, and the number of distinct degrees is \(>(\frac{1}{2}+\epsilon)n\). Must \(G\) contain a trivial (empty or complete) subgraph of size 'much larger' than…
**Erdős Problem 1043**: Let \(f\in \mathbb{C}[x]\) be a monic polynomial. Must there exist a straight line \(\ell\) such that the projection of \[\{ z: \lvert f(z)\rvert\leq 1\}\] onto \(\ell\) has measure at most \(2\)? Pommerenke [Po61]…
Let \(f(z)=\prod_{i=1}^n(z-z_i)\in\mathbb{C}[x]\) where \(\lvert z_i\rvert\leq 1\) for all \(i\). If \(\Lambda(f)\) is the maximum of the lengths of the boundaries of the connected components of \[ \{ z: \lvert f(z)\rvert<1\} \] then…
Let \(f\in \mathbb{C}[x]\) be a monic polynomial with \(m\) distinct roots, and let \(c>0\) be a constant small enough such that \(\{ z: \lvert f(z)\rvert\leq c\}\) has \(m\) distinct connected components. Must all these components be…
If \(f\in \mathbb{C}[x]\) is a monic polynomial with all roots satisfying \(\lvert z\rvert \leq r\) for some \(0 < r < 2\), then must \[\{ z: \lvert f(z)\rvert <1\}\] have a connected component with diameter \(>2-r\)? A problem of Erdős,…
**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…
Does every graph with chromatic number \(\aleph_1\) contain an infinitely connected subgraph with chromatic number \(\aleph_1\)? Komjáth [Ko13] proved that it is consistent that the answer is no. This was improved by Soukup [So15], who…
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.
We call a graph \(D\)-balanced (or \(D\)-almost-regular) if the maximum degree is at most \(D\) times the minimum degree. Let \(ε, α > 0\) and \(D\) and \(n\) be sufficiently large. If \(G\) is a graph on \(n\) vertices with at least…
Let \(G\) be a bipartite graph on \(n\) vertices such that one part has \(\lfloor n^{2/3}\rfloor\) vertices. Is there a constant \(c>0\) such that if \(G\) has at least \(cn\) edges then \(G\) must contain a \(C_6\)? The answer is no, as…
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…
Is it true that \(f_2(n) \gg n\)? Disproved by Rödl, who showed \(f_r(n) = o(n)\) for all fixed \(r \geq 2\). A conjecture of Erdős, Hajnal, and Szemerédi. This seems to be closely related to, but distinct from,…
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 A = {a₁ < a₂ < …} has property P, then A has natural density 0. Equivalently, (a_j / j) → ∞ as j → ∞. -
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…
**Prikry–Mills counterexample** (key lemma): There exists a 2-colouring \(f\) of a set of cardinality \(\aleph_1\) cubed such that no countable box \(A_1 \times B_1 \times C_1\) is monochromatic. This is the unpublished result of Prikry…
Let \(A\subseteq \mathbb{N}\) be the smallest set which contains \(1\) and is closed under the operations \[x\mapsto 2x+1,\quad x\mapsto 3x+1,\quad x\mapsto 6x+1.\] Does \(A\) have positive lower density? Lagarias [La16] reports that Erdős…
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…
**Erdős Problem 1138.** Let \(x/2 < y < x\) and \(C > 1\). If \(d = \max_{p_n < x}(p_{n+1} - p_n)\), where \(p_n\) denotes the \(n\)-th prime, then is it true that \[\pi(y + Cd) - \pi(y) \sim \frac{Cd}{\log y}\]?
Are there infinitely many \(n\) such that \(n-k^2\) is prime for all \(k\) with \((n,k)=1\) and \(k^2 < n\)? In [Va99] it is asked whether \(968\) is the largest integer with this property, but this is an error, since for example…
Let \(\alpha>0\) be an irrational number. Is the set \[A=\left\{ n\geq 1: \| \alpha n^2\| < \frac{1}{\log n}\right\},\] where \(\|\cdot\|\) denotes the distance to the nearest integer, an additive basis of order \(2\)? This was disproved…
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 \[\epsilon_m=\max \sum \frac{1}{n_i}\] where the maximum is taken over all finite sequences \(m<n_1<\cdots<n_k\) for which there exist congruences \(a_i\pmod{n_i}\) such that no integer satisfies two such congruences. Estimate…
Let \(A\subset \mathbb{N}\) and let \(g(n)\) be a non-decreasing function of \(n\) which is always \(>0\). Is the lower density of \[\{ n : 1_A\ast 1_A(n)=g(n)\}\] always \(0\)? The answer is trivially no to both questions: indeed if…
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 \(E\subset (0,\infty)\) be a set of positive measure. Is it true that, for almost all \(x>0\), for all sufficiently large (depending on \(x\)) integers \(n\) there exists an integer \(r\geq 1\) such that \(nx\in r\cdot E\)? A problem…