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 \subset \mathbb{N}\) has \(\sum_{n \in A}\frac 1 n = \infty\), then must \(A\) contain arbitrarily long arithmetic progressions? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26]; see the linked Lean proof.
Let \(C\geq 0\). Is there an infinite sequence of \(n_i\) such that \[\lim_{i\to \infty}\frac{p_{n_i+1}-p_{n_i}}{\log n_i}=C?\] We formalise "an infinite sequence of \(n_i\)" as a strictly monotone sequence of indices n : ℕ → ℕ. Note that…
Is the upper density of the set of odd numbers that cannot be expressed as a prime plus two powers of 2 positive?
Is there some \(k\) such that every large integer is the sum of a prime and at most \(k\) powers of \(2\)?
Is every large odd integer \(n\) the sum of a squarefree number and a power of 2?
Let \(A\) be an infinite set such that there are no distinct \(a,b,c \in A\) such that \(a \mid (b+c)\) and \(b,c > a\). Is there such an \(A\) with \(\liminf \frac{|A \cap \{1, \dotsc, N\}|}{N^{1/2}} > 0\) ? The DeepMind prover agent has…
Let \(A ⊆ \mathbb{N}\). Let \(B ⊆ \mathbb{N}\) be the set of integers which are representable in exactly one way as the sum of two elements from \(A\). Is it true that for all \(\epsilon > 0\) and large \(N\),…
Is it true that \(\sum_{n=1}^\infty(-1)^n\frac{n}{p_n}\) converges, where \(p_n\) is the sequence of primes? Note: In the problem statement, \(p_n\) is the \(n\)-th prime, indexed such that \(p_1=2, p_2=3, \ldots\). We 0-index here to…
cluster primes
**Erdős Problem 17.** Are there infinitely many cluster primes?
practical numbers
**Conjecture 1.** Are there infinitely many practical numbers \(m\) such that \(h(m) < (\log \log m)^{O(1)}\)? More precisely: does there exist a constant \(C > 0\) such that for infinitely many practical numbers \(m\), we have…
sunflower conjecture
Is it true that \(f(n,k) < c_k^n\) for some constant \(c_k>0\) and for all \(n > 0\)?
Let \(n_1 < n_2 < \dots\) be an arbitrary sequence of integers, each with an associated residue class \(a_i \pmod{n_i}\). Let \(A\) be the set of integers \(n\) such that for every \(i\) either \(n < n_i\) or…
If \(A ⊆ \mathbb{N}\) is such that \(A + A\) contains all but finitely many integers then \(\limsup 1_A ∗ 1_A(n) = \infty\).
Is it true that, for every \(\varepsilon > 0\), \(h(N) = \sqrt N + O_{\varepsilon}(N^\varepsilon)\)
Does there exist a set \(A \subseteq \mathbb{N}\) such that \(|A \cap \{1, \ldots, N\}| = o((\log N)^2)\) and every sufficiently large integer can be written as \(p + a\) for some prime \(p\) and \(a \in A\)?
Let A ⊆ ℕ be a set such that every integer can be written as n^2 + a for some a in A and n ≥ 0. -/ -- Formalisation note: Changed 'every large integer' to 'every integer' as for the statement these -- conditions are equivalent. Also, this…
minimum overlap problem
Find the value of the limit of MinOverlapQuotient!
Is there an infinite Sidon set \(A\subset \mathbb{N}\) such that \(\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\) for all \(\varepsilon > 0\)?
For what functions \(g(N) → \infty\) is it true that \[\lvert A\cap \{1,\ldots,N\}\rvert \gg \frac{N^{1/2}}{g(N)}\] implies \(\limsup 1_A\ast 1_A(n)=\infty\)?
Let \(A \subset \mathbb{N}\) be an infinite set such that the triple sums \(a+b+c\) are all distinct for \(a,b,c \in A\) (aside from the trivial coincidences). Is it true that \[\liminf_{N \to \infty} \frac{\lvert A \cap…
**Erdős Problem 44:** Let N ≥ 1 and A ⊆ {1,…,N} be a Sidon set. Is it true that, for any ε > 0, there exist M = M(ε) and B ⊆ {N+1,…,M} such that A ∪ B ⊆ {1,…,M} is a Sidon set of size at least (1−ε)M^{1/2}? This problem asks whether any…
Schoenberg [Sch38] proved that the asymptotic distribution function of \(\varphi(n)/n\) exists. That is, for any \(c \in [0, 1]\), the proportion of integers \(n \le N\) satisfying \(\varphi(n)/n < c\) approaches a limit as…
Is there an infinite set \(A \subset \mathbb{N}\) such that for every \(a \in A\), there is an integer n such that \(\phi(n)=a\), and yet if \(n_a\) is the smallest such integer, then \(\frac{n_a}{a} → \infty\) as \(a → ∞\)?
sum-product problem
Let \(A\) be a finite set of integers. Is it true that for every \(\epsilon>0\) \(\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\)
Does every graph on \(n\) vertices with \(>\mathrm{ex}(n;C_4)\) edges contain \(\gg n^{1/2}\) many copies of \(C_4\)?
The Erdős–Hajnal Conjecture states that there is a constant \(c(H) > 0\) for each \(H\) such that we can take \(f(n) = n^{c(H)}\) in the above formulation.
Let \(G\) be a graph with \(n\) vertices and \(kn\) edges, and \(a_1<a_2<\cdots\) be the lengths of cycles in \(G\). Assume \(n>0\). Is it true that \[\sum\frac{1}{a_i}\gg \log k?\] Gyárfás, Komlós, and Szemerédi [GKS84] have proved that…
Is there and \(A \subset \mathbb{N}\) is such that \[\lim_{n\to \infty}\frac{1_A\ast 1_A(n)}{\log n}\] exists and is \(\ne 0\)?
Is \[\sum_{n=2}^\infty \frac{1}{n!-1}\] irrational?
**Erdős Problem 70**: Let \(\mathfrak{c}\) be the order type of the real numbers, let \(\beta\) be a countable ordinal, and let \(2 \le n < \omega\). Is it true that \(\mathfrak{c} \to (\beta, n)^3_2\)? Note: The cases \(n \le 3\) are…
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
If \(R(k)\) is the Ramsey number for \(K_k\), the minimal \(n\) such that every \(2\)-colouring of the edges of \(K_n\) contains a monochromatic copy of \(K_k\), then find the value of \[\lim_{k\to \infty}R(k)^{1/k}.\] This problem is #3…
Let \(R(k)\) be the Ramsey number for \(K_k\). Give a constructive proof that \(R(k) > C^k\) for some constant \(C > 1\). Equivalently, give an explicit construction of graphs on \(n\) vertices which contain no clique and no independent…
Let \(c>0\) and let \(f_c(n)\) be the maximal \(m\) such that every graph \(G\) with \(n\) vertices and at least \(cn^2\) edges, where each edge is contained in at least one triangle, must contain a book of size \(m\), that is, an edge…
Let \(G\) be a chordal graph on \(n\) vertices - that is, \(G\) has no induced cycles of length greater than \(3\). Can the edges of \(G\) be partitioned into \(n^2/6+O(n)\) many cliques?
\(F(n) / \log n \to \infty as n \to \infty\)
Is it true that, for all large \(n\), \(f(n + 1) \ge f(n)\)?
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 every subgraph of \(Q_n\) with \[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\] many edges contains a \(C_4\)?
Let \(0 < \epsilon < 1\). Is it true that, if \(k\) is sufficiently large, then \[R(G) > (1-\epsilon)^k R(k)\] for every graph \(G\) with chromatic number \(\chi(G)=k\)? The restriction \(\epsilon < 1\) excludes negative bases in…
Erdős distance problem
Erdős [Er46] asked whether every set of \(n\) distinct points in \(\mathbb{R}^2\) determines \(\gg \frac{n}{\sqrt{\log n}}\) many distinct distances.
Suppose \(A\subset \mathbb{R}^2\) has \(\lvert A\rvert=n\) and minimises the number of distinct distances between points in \(A\). Prove that for large \(n\) there are at least two (and probably many) such \(A\) which are non-similar.
If \(n\) points in \(\mathbb{R}^2\) form a convex polygon then there are \(O(n)\) many pairs which are distance \(1\) apart.
Let \(h(n)\) be such that any \(n\) points in \(\mathbb{R}^2\), with no three on a line and no four on a circle, determine at least \(h(n)\) distinct distances. Does \(h(n)/n\to \infty\)?
For sufficiently large n, is it the case that any set of n points with minimum distance \(1\) that minimizes diameter must contain an equilateral triangle of side length 1?
Is the diameter of \(A\) at least \(Cn\) for some constant \(C > 0\)?
Given \(n\) points in \(\mathbb{R}^2\), no five of which are on a line, the number of lines containing four points is \(o(n^2)\).
Let \(c > 0\) and let \(h_c(n)\) be such that for any \(n\) points in \(\mathbb{R}^2\) with at least \(cn^2\) lines that each contain more than three of the points, some line contains \(h_c(n)\) of the points. Is it true that, for fixed…
Let \(h(n)\) count the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which minimise the diameter subject to the constraint that \(d(x,y)\geq 1\) for all points \(x\neq y\). Is it true that \(h(n)\to \infty\)?
Given \(n\) points in \(\mathbb{R}^2\) the number of distinct unit circles containing at least three points is \(o(n^2)\).
For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?
Erdős similarity problem
Let \(A \subseteq \mathbb{R}\) be an infinite set. Must there be a set \(E \subseteq \mathbb{R}\) of positive measure which does not contain any set of the shape \(a * A + b\) for some \(a,b \in \mathbb{R}\) and \(a \neq 0\)?
Let \(3 \le d_1 < d_2 < \dots < d_r\) be integers such that \[\sum_{1 \le i \le r}\frac 1{d_i - 1} \ge 1.\] Can all sufficiently large integers be written as a sum of the shape \(\sum_i c_ia_i\) where \(c_i \in \{0, 1\}\) and \(a_i\) has…
ambiguous statement
Let \(A\subset\mathbb{R}^2\) be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in \(A\), where two vertices are joined by an edge if and only if they are…
Let \(F(N)\) be the maximal size of \(A \subseteq \{1, \dots, N\}\) such that no \(a \in A\) divides the sum of any distinct elements of \(A \setminus \{a\}\). Is it true that \(F(N) > N^{1/2 - o(1)}\)? The answer is no, by the bound of…
We say that \(N\) is powerful if whenever \(p\mid N\) we also have \(p^2\mid N\). Let \(k\geq 3\). Can the product of any \(k\) consecutive positive integers ever be powerful?
Asserts that for any number of colors r and any progression length k, there always exists some number N large enough to guarantee a monochromatic arithmetic progression. In other words, the set monoAP_guarantee_set is non-empty. This is…
Let \(k≥3\). Are there \(k\) consecutive primes in arithmetic progression?
Prove an asymptotic formula for \(r_k(N)\), the largest possible size of a subset of \(\{1, \dots, N\}\) that does not contain any non-trivial \(k\)-term arithmetic progression. That is, find \(f_k\) with \(r_k(N) / f_k(N) \to 1\) as…
Does this imply that \[ \liminf \frac{|A \cap [1,x]|}{x} = 0? \]
Let \(s_1 < s_2 < \cdots\) be the sequence of squarefree numbers. Is it true that, for any \(\alpha\geq 0\), \[ \lim_{x\to\infty} \frac{1}{x}\sum_{s_n\leq x}(s_{n+1}-s_n)^\alpha \] exists?
Let \(F(k)\) be the number of solutions to \[ 1= \frac{1}{n_1}+\cdots+\frac{1}{n_k},\] where \(1\leq n_1<\cdots<n_k\) are distinct integers. Find good estimates for \(F(k)\).
For a graph \(G\), let \(\tau(G)\) denote the minimal number of vertices that include at least one from each maximal clique of \(G\) on at least two vertices. Let \(H(n)\) be maximal such that every triangle-free graph on \(n\) vertices…
Let \(A\) be a finite Sidon set and \(A+A=\{s_1<\cdots<s_t\}\). Is it true that \[\frac{1}{t}\sum_{1\leq i<t}(s_{i+1}-s_i)^2 \to \infty\] as \(\lvert A\rvert\to \infty\)?
Is it true that for every \(k \geq 1\) we have \[ F(N + k) \leq F(N) + 1 \] for all sufficiently large \(N\)?
Does there exist a maximal Sidon set \(A\subset \{1,\ldots,N\}\) of size \(O(N^{1/3})\)? A question of Erdős, Sárközy, and Sós [ESS94].
Let A be an infinite B₂[2] set. Must liminf |A ∩ {1, ..., N}| * N ^ (- 1 / 2) = 0?
There exists some constant \(c>0\) such that \[R(C_4,K_n) \ll n^{2-c}.\] The prize of $100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
On [Mathoverflow](https://mathoverflow.net/a/410815) user [leechlattice](https://mathoverflow.net/users/125498/leechlattice) shows that \(h(n) \ll n^{\frac 2 3}\).
Let \(\alpha\in[0,1/2)\) and \(n,t\geq 1\). Let \(F^{(t)}(n,\alpha)\) be the smallest \(m\) such that we can \(2\)-colour the edges of the complete \(t\)-uniform hypergraph on \(n\) vertices such that if \(X\subseteq [n]\) with…
Let \(\alpha > 0\) and \(n \geq 1\). Let \(F(n,\alpha)\) be the largest \(k\) such that there exists some 2-colouring of the edges of \(K_n\) in which any induced subgraph \(H\) on at least \(k\) vertices contains more than…
What is the limit \(F(N)/N\) as \(N \to \infty\)?
sparse ruler problem
The problem is to determine the limit of the sequence \(\frac{F(N)}{\sqrt{N}}\) as \(N \to \infty\).
Is it true that in any finite colouring of \(\mathbb{N}\) there exist arbitrarily large finite \(A\) such that all sums and products of distinct elements in \(A\) are the same colour?
In any \(2\)-colouring of \(\mathbb{R}^2\), for all but at most one triangle \(T\) (up to congruence), there is a monochromatic congruent copy of \(T\). The colouring is arbitrary. No measurability is assumed. ≅ compares vertices with the…
A finite set \(A\subset \mathbb{R}^n\) is called Ramsey if, for any \(k\geq 1\), there exists some \(d=d(A,k)\) such that in any \(k\)-colouring of \(\mathbb{R}^d\) there exists a monochromatic copy of \(A\). Characterise the Ramsey sets…
Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Prove that \[R(Q_n) \ll 2^n.\]
Any graph on \(n\) vertices can be decomposed into \(O(n)\) many edge-disjoint cycles and edges. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
What is the smallest \(k\) such that \(\mathbb{R}^2\) can be red/blue coloured with no pair of red points unit distance apart, and no \(k\)-term arithmetic progression of blue points with distance 1?
What is the largest \(k\) such that in any permutation of \(\mathbb{Z}\) there must exist a monotone \(k\)-term arithmetic progression \(x_1 < \cdots < x_k\)? Here a permutation of \(\mathbb{Z}\) is a one-sided arrangement…
Must every permutation of \(\mathbb{N}\) contain a monotone 4-term arithmetic progression? Here a monotone \(k\)-term arithmetic progression in a permutation \(f\) is a set of indices \(i_1 < \cdots < i_k\) such that…
Can \(\mathbb{N}\) be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?
Does the longest arithmetic progression of primes in \(\{1,\ldots,N\}\) have length \(o(\log N)\)?
Is there an integer \(m\) with \((m, 6) = 1\) such that none of \(2^k \cdot 3^\ell \cdot m + 1\) are prime, for any \(k, \ell \ge 0\)?
Let \(s_1 < s_2 < \dots\) be the sequence of squarefree numbers. Is it true that for any \(\epsilon > 0\) and large \(n\), \(s_{n+1} - s_n \ll_\epsilon s_n^\epsilon\)?
Is there a dense subset of ℝ^2 such that all pairwise distances are rational?
Let \(n \geq 4\). Are there \(n\) points in \(\mathbb{R}^2\), no three on a line and no four on a circle, such that all pairwise distances are integers?
A conjecture by Heath-Brown: The sum of squares of the first \(N\) gaps between consecutive primes behaves like \(N * (log N)^2\).
Is it true that for all c ≥ 0, the density f c of integers for which (p (n + 1) - p n) / log n < c exists and is a continuous function of c?
Let \(f(n)\) count the number of solutions to \(n=p+2^k\) for prime \(p\) and \(k\geq 0\). Show that \(f(n)=o(\log n)\).
Let c₁, c₂ > 0. Is it true that for any sufficiently large x, there exists more than c₁ * log x many consecutive primes ≤ x such that the difference between any two is > c₂?
Is it true that \(f(N)\sim N^{1/3}\)? Originally asked to Erdős by Bose. This is discussed in problem C11 of Guy's collection [Gu04].
Let \(a_1 < a_2 < \dots\) be a sequence of integers such that \(\lim_{n\to\infty} \frac{a_n}{a_{n-1}^2} = 1\) and \(\sum \frac{1}{a_n} \in \mathbb{Q}\). Then, for all sufficiently large \(n \ge 1\), \(a_n = a_{n-1}^2 - a_{n-1} + 1\).
Let \(C > 1\). Does the set of integers of the form \(p + \lfloor C^k \rfloor\), for some prime \(p\) and \(k\geq 0\), have density \(>0\)?
Let \(n_1 < n_2 < \cdots\) be a sequence of integers such that \[ \limsup \frac{n_k}{k} = \infty. \] Is \[ \sum_{k=1}^{\infty} \frac{1}{2^{n_k}} \] transcendental?
Is \[\sum_{n} \frac{\phi(n)}{2^n}\] irrational? Here \(\phi\) is the Euler totient function.
Is \(\sum_{n=1}^\infty \frac{p_n}{2^n}\) irrational? Here \(p_n\) is the \(n\)-th prime (\(p_1=2, p_2=3, \dots\)).
Erdős Problem 252: irrationality of the sum for a given \(k\).
Let \(A\subseteq \mathbb{N}\) be such that \(\lvert A\cap [1,2x]\rvert -\lvert A\cap [1,x]\rvert \to \infty\textrm{ as }x\to \infty\) and \(\sum_{n\in A} \{ \theta n\}=\infty\) for every \(\theta\in (0,1)\), where \(\{x\}\) is the distance…
Let \(A\subseteq\mathbb{N}\) be an infinite set. Is \[ \sum_{n\in A} \frac{1}{2^n - 1} \] irrational?
Let \(a_1 < a_2 < \cdots\) be an increasing sequence such that \(\frac{a_n}{n} \to \infty\). Is the sum \(\sum_{n}^{\infty} \frac{a_n}{2^{a_n}}\) irrational? For a proof, see [Wang, *Sparse Polynomial-Weighted Expansions*]…
Are there infinitely many positive integers \(n\) such that there exist some \(t \ge 2\) and distinct integers \(a_1, \ldots, a_t \ge 1\) satisfying \[\frac{n}{2^n} = \sum_{1 \le k \le t} \frac{a_k}{2^{a_k}}?\] In [Er88c], Erdős notes that…
Is \(a_n = 2^{2^n}\) an irrationality sequence in the above sense?
Is \(2^n\) an example of an irrationality sequence? Kovač and Tao proved that it is not [KoTa24] [KoTa24] Kovač, V. and Tao T., On several irrationality problems for Ahmes series. arXiv:2406.17593 (2024).
ambiguous statement
Let \(F_1=F_2=1\) and \(F_{n+1} = F_n + F_{n-1}\) be the Fibonacci sequence. Let \(n_1 < n_2 < \dots\) be an infinite sequence with \(\frac{n_{k+1}}{n_k} \ge c > 1\). Must \(\sum_k \frac 1 {F_{n_k}}\) be irrational?
Stanley sequences
Let \(N\geq 1\). What is the largest \(t\) such that there are \(A_1,\ldots,A_t\subseteq \{1,\ldots,N\}\) with \(A_i\cap A_j\) a non-empty arithmetic progression for all \(i\neq j\)?
Is there a covering system all of whose moduli are of the form \(p-1\) for some primes \(p \geq 5\)?
Herzog-Schönheim conjecture
If \(G\) is a group, can there exist an exact covering of \(G\) by more than one coset of different sizes? (i.e. each element is contained in exactly one of the cosets.) The conjectured answer is no: in every such exact covering, two of…
Is there an infinite Lucas sequence \(a_0, a_1, \ldots\) where \(a_{n+2} = a_{n+1} + a_n\) for \(n \ge 0\) such that all \(a_k\) are composite, and yet no integer has a common factor with every term of the sequence?
Let \(k\geq 3\). Is there a choice of congruence classes \(a_p\pmod{p}\) for every prime \(p\) such that all sufficiently large integers can be written as \(a_p+tp\) for some prime \(p\) and integer \(t\geq k\)?
Let \(A\subseteq \mathbb{N}\) be an infinite set and consider the following greedy algorithm for a rational \(x\in (0,1)\): choose the minimal \(n\in A\) not used so far such that \(n\geq 1/x\) and repeat with \(x\) replaced by…
Is it true that there are only finitely many pairs of intervals \(I_1\), \(I_2\) such that \[ \sum_{n_1 \in I_1} \frac{1}{n_1} + \sum_{n_2 \in I_2} \frac{1}{n_2} \in \mathbb{N}? \]
Is it true that, for all sufficiently large \(k\), there exist finite intervals \(I_1, \dotsc, I_k \subset \mathbb{N}\), distinct, not overlapping or adjacent, with \(|I_i| \geq 2\) for \(1 \leq i \leq k\) such that \[ 1 = \sum_{i=1}^k…
Let \(n\geq 1\) and define \(L_n\) to be the least common multiple of \(\{1,\ldots,n\}\) and \(a_n\) by \(\sum_{1\leq k\leq n}\frac{1}{k}=\frac{a_n}{L_n}\). Is it true that \((a_n,L_n)=1\) occurs for infinitely many \(n\)?
ambiguous statement
Let \(k(N)\) denote the smallest \(k\) such that there exists \(N ≤ n_1 < ⋯ < n_k\) with \(\frac 1 {n_1} + ... + \frac 1 {n_k} = 1\) Is it true that \(\lim_{N \to \infty} k(N) - (e - 1)N = \infty\)?
Let \(f(N)\) be the size of the largest \(A\subseteq \{1,\ldots,N\}\) such that there are no solutions to \[\frac{1}{a}= \frac{1}{b}+\frac{1}{c}\] with distinct \(a,b,c\in A\)? Estimate \(f(N)\). The colouring version of this is [303],…
Is it true that \[N(b) \ll \log \log b\]? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
Let \(\frac a b\in \mathbb{Q}_{>0}\) with \(b\) squarefree. Are there integers \(1 < n_1 < \dots < n_k\), each the product of two distinct primes, such that \(\frac{a}{b}=\frac{1}{n_1}+\cdots+\frac{1}{n_k}\)?
Let \(\delta(N)\) be the minimal non-zero value of \(\lvert 1-\sum_{n\in A}\frac{1}{n}\rvert\) as \(A\) ranges over all subsets of \(\{1,\ldots,N\}\). Is it true that \[\delta(N)=e^{-(c+o(1))N}\] for some constant \(c\in (0,1)\)? The…
Does there exist a constant c > 0 such that, for any K > 1, whenever A is a sufficiently large finite multiset of integers with \(\sum_{n \in A} 1/n > K\) there exists some \(S \subseteq A\) such that…
Are there infinitely many pairs (m, P) where m ≥ 2 is an integer and P is a set of distinct primes such that the following equation holds: \(\sum_{p \in P} \frac{1}{p} = 1 - \frac{1}{m}\)?
Is there some constant \(c>0\) such that for every \(n\geq 1\) there exists some \(\delta_k\in \{-1,0,1\}\) for \(1\leq k\leq n\) with \[0< \left\lvert \sum_{1\leq k\leq n}\frac{\delta_k}{k}\right\rvert < \frac{c}{2^n}?\]
What is the size of the largest \(A\subseteq\{1, \dots, N\}\) such that there is a function \(\delta : A \to \{-1, 1\}\) such that \[ \sum_{n\in A} \frac{\delta n}{n} = 0 \] and \[ \sum_{n\in A'}\frac{\delta n}{n} \neq 0 \] for all…
Let \(k\geq 3\) and \(A\subset \mathbb{N}\) be the set of \(k\)th powers. What is the order of growth of \(1_A^{(k)}(n)\), i.e. the number of representations of \(n\) as the sum of \(k\) many \(k\)th powers? Does there exist some \(c>0\)…
Is it true that \(f_{k,k}(x) \gg_\epsilon x^{1-\epsilon}\) for all \(\epsilon>0\)? This would have significant applications to Waring's problem. Erdős and Graham describe this as 'unattackable by the methods at our disposal'.
Does there exist a polynomial \(f(x)\in\mathbb{Z}[x]\) such that all the sums \(f(a)+f(b)\) with \(a < b\) nonnegative integers are distinct?
Writing \(f_{k, 3}(x)\) for the number of integers \(\leq x\) which are the sum of three \(k\)th powers, is it true that \(f_{k, 3}(x) \gg x ^ (3 / k)\)?
Does there exist \(A = \{a_1 < a_2 < \cdots\} \subset \mathbb{N}\) which is a minimal basis of order \(2\) (i.e. every large integer is the sum of \(2\) elements from \(A\), and no proper subset of \(A\) has this property), such that…
**Erdős Problem 329.** Let A ⊆ ℕ be a Sidon set. How large can lim sup_{N → ∞} |A ∩ {1,…,N}| / N^{1/2} be?
Let \(A\subseteq \mathbb{N}\) and \(D(A)\) be the set of those numbers which occur infinitely often as \(a_1 - a_2\) with \(a_1, a_2\in A\). What conditions on \(A\) are sufficient to ensure \(D(A)\) has bounded gaps? The sufficient…
The restricted order of a basis \(A\) is the least integer \(t\) (if it exists) such that every large integer is the sum of at most \(t\) distinct summands from \(A\). What are necessary and sufficient conditions that this exists? A…
Let \(A = \{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\}\) be the greedy Sidon sequence: we begin with \(1\) and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions…
Let \(A=\{a_1 < \cdots < a_k\}\) be a finite set of integers and extend it to an infinite sequence \(\overline{A}=\{a_1 < a_2 < \cdots \}\) by defining \(a_{n+1}\) for \(n \geq k\) to be the least integer exceeding \(a_n\) which is not of…
Do infinitely many pairs \((a, a+2)\) occur in Ulam's sequence?
Let \(A\subseteq \mathbb{N}\) be a complete sequence, and define the threshold of completeness \(T(A)\) to be the least integer \(m\) such that all \(n\geq m\) are in \[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\]…
For what values of \(0 \leq m < n\) is there a complete sequence \(A = \{a_1 \leq a_2 \leq \cdots\}\) of integers such that 1. \(A\) remains complete after removing any \(m\) elements, but 2. \(A\) is not complete after removing any \(n\)…
For what values of \(t,\alpha \in (0,\infty)\) is the sequence \(\lfloor t\alpha^n\rfloor\) complete (that is, all sufficiently large integers are the sum of distinct integers of the form \(\lfloor t\alpha^n\rfloor\))?
Is there some \(c > 0\) such that every measurable \(A \subseteq \mathbb{R}^2\) of measure \(\geq c\) contains the vertices of a triangle of area 1?
Let \(\alpha,\beta\in \mathbb{R}_{>0}\) such that \(\alpha/\beta\) is irrational. Is the multiset \[\{ \lfloor \alpha\rfloor,\lfloor 2\alpha\rfloor,\lfloor 4\alpha\rfloor,\ldots\}\cup \{ \lfloor \beta\rfloor,\lfloor 2\beta\rfloor,\lfloor…
Let \(f(n)\) be the maximal \(k\) such that there exist integers \(1 \le a_1 < \dotsc < a_k \le n\) such that all sums of the shape \(\sum_{u \le i \le v} a_i\) are distinct. Is \(f(n)=o(n)\)?
segmented numbers
Let \(a_1< a_2 < ⋯ \) be an infinite sequence of integers such that \(a_1=1\) and \(a_{i+1}\) is the least integer which is not a sum of consecutive earlier \(a_j\)s. Show that \(a_k / k \to \infty\).
Let \(c > 0\) and \(n\) be some large integer. What is the size of the largest set \(A \subseteq \{1, \ldots, \lfloor c n \rfloor\}\) such that \(n\) is not a sum of a subset of \(A\)? Does this depend on \(n\) in an irregular way?
Do all pairs of consecutive powerful numbers \(n\) and \(n+1\) come from solutions to Pell equations? In other words, must either \(n\) or \(n+1\) be a square? The answer to the first question is no: Golomb [Go70] observed that both…
Let \(B_2(n)\) be the \(2\)-full part of \(n\) (that is, \(B_2(n)=n/n'\) where \(n'\) is the product of all primes that divide \(n\) exactly once). Is it true that, for every fixed \(k \geq 1\),…
How large is the largest prime factor of \(n(n+1)\)? The truth is probably \(F(n)\gg (\log n)^2\) for all \(n\).
Let \(P(n)\) denote the largest prime factor of \(n\). Show that the set of \(n\) with \(P(n+1) > P(n)\) has density \(\frac{1}{2}\). This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
Show that the equation n!=a_1!a_2!···a_k!, with n−1 > a_1 ≥ a_2 ≥ ··· ≥ a_k, has only finitely many solutions.
Are there infinitely many \(n\) such that \({2n\choose n}\) is coprime to \(105\)?
Is there some absolute constant \(C > 0\) such that \[ \sum_{p \leq n} 1_{p\nmid {2n \choose n}}\frac{1}{p} \leq C \] for all \(n\)?
Let \(u \leq v\) be such that the largest prime dividing \(\prod_{u \leq m \leq v} m\) appears with exponent at least \(2\). Is it true that \(v - u = v^{o(1)}\)? We read this as: for every \(\epsilon > 0\), every such pair with \(v\)…
Is it true that for every \(k\) there are infinitely many primes \(p\) such that the largest prime divisor of \[ \prod_{i = 0}^k (p ^ 2 + i) \] is \(p\)?
Let \(F(n) := \max\{m + p(m) \mid \textrm{\)m < n\( composite}\}\}\) where \(p(m)\) is the least prime divisor of \(m\). Is it true that \(F(n)>n\) for all sufficiently large \(n\)?
Let \(2 \le k \le n - 2\). Can \(\binom{n}{k}\) be the product of consecutive primes infinitely often? Here \(k\) may vary with \(n\): the question asks for infinitely many admissible binomial coefficients, not for a single \(k\) that…
Are there only finitely many solutions of \[\prod_{1\leq i\leq k_1}(m_1+i)=\prod_{1\leq j\leq k_2}(m_2+j)\] with \(k_1,k_2>3\) and \(m_1+k_1\leq m_2\)? Here \(m_1, m_2 \geq 0\), so every factor is positive and the condition…
Is it true that for every \(n \geq 1\) there is a \(k\) such that \[ n(n + 1) \cdots (n + k - 1) \mid (n + k) \cdots (n + 2k - 1)? \]
Let \(f(n)\) denote the minimal \(m\geq 1\) such that \[n! = a_1\cdots a_t\] with \(a_1<\cdots <a_t=a_1+m\). What is the behaviour of \(f(n)\)? We formalise the question as: does \(f(n) \to \infty\)? A result of Luca [Lu02] implies a…
Is it true that \(\sum_{n\leq x}t_2(n)\ll \frac{x^2}{(\log x)^c}\) for some \(c>0\)?
Is it true that for every \(k\) there exists \(n\) such that \[\prod_{0\leq i\leq k}(n-i) \mid \binom{2n}{n}?\]
Can one show that \(\sum_{n\leq x}g_k(n) \sim c_k x\log x\) for some constant \(c_k\)?
Is it true that there are only finitely many powers of \(2\) which have only the digits \(0\) and \(1\) when written in base \(3\)?
Let \(\phi(n)\) be the Euler totient function and \(\phi_k(n)\) be the iterated \(\phi\) function, so that \(\phi_1(n)=\phi(n)\) and \(\phi_k(n)=\phi(\phi_{k-1}(n))\). Let \[f(n) = \min\{k : \phi_k(n)=1\}.\] Does \(f(n)/\log n\) have a…
Let \(c(n)\) be the minimum number of iterations of \(n\mapsto\phi(n) + 1\) before a prime is reached. What is \(\Theta(c(n))\)?
Let \(σ_1(n) = σ(n)\), the sum of divisors function, and \(σ_k(n) = σ(σ_{k-1}(n))\). Is it true that \(\lim_{k → ∞} σ_k(n)^{\frac 1 k} = ∞\)? This is problem (iii) from Erdos, Granville, Pomerance, Spiro "On the normal behavior of the…
partial r=2 result
Let \(σ_1(n)=σ(n)\), the sum of divisors function, and \(σ_k(n) = σ(σ_{k-1}(n))\). Is it true that, for every \(m, n ≥ 2\), there exist some \(i, j\) such that \(σ_i(m) = σ_j(n)\)?
Are there infinitely many barriers for ω?
Let \(h_1(n) = h(n)\) and \(h_k(n) = h(h_{k-1}(n))\). Is it true, for any \(m,n\), there exist \(i\) and \(j\) such that \(h_i(m) = h_j(n)\)?
Let V(x) count the number of n≤x such that ϕ(m)=n is solvable. Does V(2x)/V(x)→2 ? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof, which gives V(cx)/V(x)→c for every fixed c>0.
Let\[V'(x)=\#\{\phi(m) : 1\leq m\leq x\}\]and\[V(x)=\#\{\phi(m) \leq x : 1\leq m\}.\] Does \(\lim V(x)/V'(x)\) exist?
If \(\tau(n)\) counts the number of divisors of \(n\) then let \[F(f,n)=\frac{\tau((n+\lfloor f(n)\rfloor)!)}{\tau(n!)}.\] Is it true that \[\lim_{n\to \infty}F((\log n)^C,n)=\infty\] for large \(C\)? "For large \(C\)" means for all…
Let \(f(1) = f(2) = 1\) and for \(n > 2\) \[ f(n) = f(n - f(n - 1)) + f(n - f(n - 2)). \] Does \(f(n)\) miss infinitely many integers?
Erdős Problem 423 [Er77c, p.71; ErGr80, p.83]: Let \(a(1) = 1\), \(a(2) = 2\), and for \(k \ge 3\) let \(a(k)\) be the least integer greater than \(a(k-1)\) that is a sum of at least two consecutive terms of the sequence. What is the…
Let \(a_1 = 2\) and \(a_2 = 3\) and continue the sequence by appending to \(a_1, \ldots, a_n\) all possible values of \(a_i a_j - 1\) with \(i \neq j\). Is it true that the set of integers which eventually appear has positive density? As…
Is there a set \(A\subseteq \mathbb{N}\) such that, for infinitely many \(n\), all of \(n-a\) are prime for all \(a\in A\) with \(0 < a < n\) and \[\liminf\frac{\lvert A\cap [1,x]\rvert}{\pi(x)}>0?\]
Fix some integer \(n\) and define a decreasing sequence in \([1,n)\) by \(a_1=n-1\) and, for \(k\geq 2\), letting \(a_k\) be the greatest integer in \([1,a_{k-1})\) such that all of the prime factors of \(a_k\) are \(>n-a_k\). Is it true…
inverse Goldbach problem
Are there two infinite sets \(A\) and \(B\) such that \(A+B\) agrees with the primes up to finitely many exceptions? This was disproved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
If \(p\) is a prime and \(k, m \geq 2\), let \(r(k, m, p)\) be the minimal \(r\) such that \(r, r + 1, \ldots, r + m - 1\) are all \(k\)th power residues modulo \(p\), and let \(\Lambda(k, m) = \limsup_{p \to \infty} r(k, m, p)\). Is…
Is it true that, for any \(c>1/2\), if \(p\) is a sufficiently large prime then, for any \(n\geq 0\), there exist \(a,b\in(n,n+p^c)\) such that \(ab\equiv 1\pmod{p}\)? This is discussed in this MathOverflow question [MathOverflow].
How large must \(y=y(\epsilon,n)\) be such that the number of integers in \((x,x+y)\) with a divisor in \((n,2n)\) is at most \(\epsilon y\)? The bound is required for every \(x\) and every window length at least \(y\), and…
Determine the largest length of an interval in \([x,2x]\) on which \(\omega(n) > \log\log n\) everywhere.
Is it true that limsup (fun n => (f n - 2 * n.nth Prime : ℕ∞)) atTop = ⊤?
Let q : ℕ → ℕ be a strictly increasing sequence of primes such that q (n + 2) - q (n + 1) ≥ q (n + 1) - q n. Must lim q n / (n ^ 2) = ∞?
Is it true that \(m_n<p_n\) for almost all \(n\)?
ambiguous statement
Let \(s_t(n)\) be the \(t\)-smooth component of \(n\) - that is, the product of all primes \(p\) (with multiplicity) dividing \(n\) such that \(p<t\). Let \(f(n,t)\) count the number of distinct possible values for \(s_t(m)\) for…
Let \(p(n)\) denote the least prime factor of \(n\). Is there a constant \(C>0\) such that \[\sum_{x\leq n\leq x+C\sqrt{x}(\log x)^2}\frac{p(n)}{n}\gg 1\] for all sufficiently large \(x\)?
Is there a function \(f\) with \(f(n)\to\infty\) as \(n\to\infty\) such that, for all large \(n\), there is a composite number \(m\) such that \[ n + f(n) < m < n + p(m) \] Here \(p(m)\) is the least prime factor of \(m\).
ambiguous statement
For every sufficiently large \(x\), choose a congruence class \(a_p\pmod p\) for each prime \(p\leq x\). Can the primes be decomposed into two nonempty sets \(A\) and \(B\) such that every \(n<x\) lies in a chosen class from \(A\) and in a…
Are there any odd weird numbers?
Given a finite sequence of primes \(q_1<\cdots<q_m\), extend it by taking \(q_{n+1}\) to be the smallest prime of the form \(q_n+q_i-1\) for \(n\geq m\). Is there an initial sequence for which this process continues forever?
Let \(p\) be a prime and \[A_p = \{ k! \pmod{p} : 1\leq k<p\}.\] Is it true that \[\lvert A_p\rvert \sim (1-\tfrac{1}{e})p?\]
Is it true that, for every integer \(k\neq 1\), there are infinitely many \(n\) such that \(2^n\equiv k\pmod{n}\)?
Let \(f(k)\) be the minimal \(N\) such that if \(\{1,\ldots,N\}\) is \(k\)-coloured then there is a monochromatic solution to \(a+b=c\). Estimate \(f(k)\). In particular, is it true that \(f(k) < c^k\) for some constant \(c>0\)? The…
Let \(A \subseteq \mathbb{N}\), and for each \(n \in A\) choose some \(X_n \subseteq \mathbb{Z}/n\mathbb{Z}\). Let \(B = \{m \in \mathbb{N} : m \not\in X_n \pmod{n} \text{ for all } n \in A \text{ with } m > n\}\). Must \(B\) have a…
Let \(A\subseteq \mathbb{N}\) be a set such that \(\lvert A\cap [1,x]\rvert=o(x^{1/2})\). Let \(B=\{ n\geq 1 : a\nmid n\textrm{ for all }a\in A\}\). If \(B=\{b_1 < b_2 < \cdots\}\) then is it true that \[\lim_{x \to \infty}…
Littlewood conjecture
Let \(\alpha,\beta \in \mathbb{R}\). Is it true that\[\liminf_{n\to \infty} n \| n\alpha \| \| n\beta\| =0\]? This is also known as the Littlewood conjecture.
What is \(\mathrm{ex}_3(n,K_4^3)\)? That is, the largest number of \(3\)-edges which can placed on \(n\) vertices so that there exists no \(K_4^3\), a set of 4 vertices which is covered by all 4 possible \(3\)-edges. See also…
What is the size of the largest \(A \subseteq \mathbb{R}^n\) such that every three points from \(A\) determine an isosceles triangle? That is, for any three points \(x\), \(y\), \(z\) from \(A\), at least two of the distances \(|x - y|\),…
Heilbronn's triangle problem
Let \(\alpha(n)\) be such that every set of \(n\) points in the unit disk contains three points which determine a triangle of area at most \(\alpha(n)\). Estimate \(\alpha(n)\).
Hadwiger-Nelson problem
The Hadwiger–Nelson problem asks: How many colors are required to color the plane such that no two points at distance 1 from each other have the same color? It is known that \(6 \leq \chi(\mathbb{R}^2) \leq 7\); see…
Let \(f(z) ∈ ℂ[z]\) be a monic non-constant polynomial. Can the set \(\{z ∈ ℂ : |f(z)| ≤ 1\}\) be covered by a set of closed discs the sum of whose radii is \(≤ 2\)?
Chowla's cosine problem
**Chowla's cosine problem** If \(A\subset \mathbb{N}\) is a finite set of positive integers of size \(N > 0\) then is there some absolute constant \(c>0\) and \(\theta\) such that \[\sum_{n\in A}\cos(n\theta) < -cN^{1/2}?\]
Let f be a transcendental entire function. What is the greatest possible value of liminf (fun r : ℝ => ratio r f) atTop?
If f(z) = ∑ aₖzⁿₖ is an entire function (with aₖ ≠ 0 for all k) such that nₖ / k → ∞, is it true that f assumes every value infinitely often?
Prime entries are random variables. -/ measurable_of_prime p : p.Prime → Measurable (f p) /-- Prime entries are independent. -/ iIndepFun_primes : iIndepFun (fun p : Primes ↦ f p) ℙ /-- Primes entries are uniformly distributed on {-1, 1}.…
Let \((\epsilon_k)_{k\geq 0}\) be independently uniformly chosen at random from \(\{-1,1\}\). If \(R_n\) counts the number of real roots of \(f_n(z)=\sum_{0\leq k\leq n}\epsilon_k z^k\) then is it true that, almost surely, \[\lim_{n\to…
Let \(r \geq 3\), and let \(f_r(N)\) denote the size of the largest subset of \(\{1,\ldots,N\}\) such that no subset of size \(r\) has the same pairwise greatest common divisor between all elements. Erdős [Er64] proved that…
Let \(\epsilon>0\) and \(N\) be sufficiently large. Is it true that if \(A\subseteq \{1,\ldots,N\}\) has size at least \(\epsilon N\) then there must be distinct \(a,b,c\in A\) such that \[[a, b]=[b, c]=[a, c],\] where \([\cdot, \cdot]\)…
Let \(r\geq 2\) and suppose that \(A\subseteq\{1,\ldots,N\}\) is such that, for any \(m\), there are at most \(r\) solutions to \(m=pa\) where \(p\) is prime and \(a\in A\). Give the best possible upper bound for…
Let \(h(n)\) be maximal such that, for any set \(A\subseteq \mathbb{N}\) of size \(n\), the set\[\left\{ \frac{a}{(a,b)}: a,b\in A\right\}\]has size at least \(h(n)\). Estimate \(h(n)\).
Show that \[R(3,k+1)-R(3,k)\to\infty\] as \(k\to \infty\). A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
Let \(m\) be sufficiently large and let \(G\) be a graph with \(m\) edges and no isolated vertices. Is the Ramsey number \(R(G)\) maximised when \(G\) is 'as complete as possible'? That is, if \(m=\binom{n}{2}+t\) edges with…
Determine the Ramsey number \[R(C_4, S_n),\] where \(S_n=K_{1,n}\) is the star on \(n+1\) vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Let \(R_k(G)\) be the least \(m\) such that every \(k\)-colouring of the edges of \(K_m\) contains a monochromatic copy of \(G\). Determine \(R_k(C_{2n})\).
Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges such that in any \(2\)-colouring of the edges of \(H\) there is a monochromatic copy of \(G\). Determine…
F(s,n) is the disjoint union of the stars \(K_{1,n_i}\). The vertex \((i,0)\) is the center of component \(i\); its other \(n_i\) vertices are leaves. -/ local notation "F(" s ", " n ")" => fromRel (fun (u v : Σ i : Fin s, Fin (n i + 1)) ↦…
Let \(R_r(n)\) denote the \(r\)-uniform hypergraph Ramsey number: the minimal \(m\) such that if we \(2\)-colour all edges of the complete \(r\)-uniform hypergraph on \(m\) vertices then there must be some monochromatic copy of the…
Let \(F(n,\alpha)\) denote the smallest \(m\) such that there exists a \(2\)-colouring of the edges of \(K_n\) so that every \(X\subseteq [n]\) with \(\lvert X\rvert\geq m\) contains more than \(\alpha \binom{\lvert X\rvert}{2}\) many…
Let \(R_3(n)\) be the minimal \(m\) such that if the edges of the \(3\)-uniform hypergraph on \(m\) vertices are \(2\)-coloured then there is a monochromatic copy of the complete \(3\)-uniform hypergraph on \(n\) vertices. Is there some…
Let \(G\) be such that any subgraph on \(k\) vertices has at most \(2k-3\) edges. Is it true that, if \(H\) has \(m\) edges and no isolated vertices, then \(R(G,H) \ll m\)? In other words: if \(G\) is sparse (every induced subgraph on…
**Erdős Problem 567 (Q3)** Is \(Q_3\) (the 3-dimensional hypercube) Ramsey size linear?
Let \(G\) be a graph such that \(R(G,T_n)\ll n\) for any tree \(T_n\) on \(n\) vertices and \(R(G,K_n)\ll n^2\). Is it true that, for any \(H\) with \(m\) edges and no isolated vertices, \[R(G,H)\ll m?\] In other words, is \(G\) Ramsey…
Let \(k\geq 1\). What is the best possible \(c_k\) such that \[R(C_{2k+1},H)\leq c_k m\] for any graph \(H\) on \(m\) edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
Show that for \(k\geq 3\) \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.\] This problem is #46 in Extremal Graph Theory in the graphs problem collection.
Is it true that \[\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?\] A problem of Erdős and Simonovits. This problem is asking whether the threshold is the same as for forbidding \(C_4\) and all odd cycles (see erdos_573.variants.kst) if one…
Let \(\delta > 0\). If \(n\) is sufficiently large and \(G\) is a graph on \(n\) vertices with no \(K_{2,2,2}\) (the octahedron) and at least \(\delta n^2\) edges, must \(G\) contain an independent set of size \(\gg_\delta n\)? This is a…
Let \(f_k(n)\) be minimal such that if \(n\) points in \(\mathbb{R}^2\) have no \(k+1\) points on a line then there must be at most \(f_k(n)\) many lines containing at least \(k\) points. Is it true that \[f_k(n) = o(n^2)\] for…
Determine which countable ordinals \(β\) have the property that, if \(α = \omega^β\), then in any red/blue colouring of the edges of \(K_α\) there is either a red \(K_α\) or a blue \(K_3\).
**Erdős Problem 593 (\\(500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number \)> \aleph_0…
**Erdős Problem 595 (\\(250)**: Is there an infinite graph \)G\( which contains no \)K_4$ and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
**Erdős Problem 596** (Erdős–Hajnal, [Er87]). For which graph pairs \((G_1, G_2)\) is it true that (1) for every \(n \geq 1\) there is a graph \(H\) without a \(G_1\) such that any \(n\)-colouring of \(H\)'s edges contains a monochromatic…
**Erdős Problem 598:** Let \(m\) be an infinite cardinal and \(\kappa\) be the successor cardinal of \(2^{\aleph_0}\). Can one colour the countable subsets of \(m\) using \(\kappa\) many colours so that every \(X \subseteq m\) with…
Let \(r \geq 2\). Is it true that \(e(n,r+1) - e(n,r) \to \infty\) as \(n \to \infty\)?
Property B
Does every almost-disjoint family of countably infinite sets whose pairwise intersections all have size ≠ 1 have Property B? Formally: let α be any type, let (A_i)_{i ∈ I} be a family of countably infinite subsets of α such that for all i…
pinned distance problem
Given \(n\) distinct points \(A\subset\mathbb{R}^2\), must there be a point \(x\in A\) such that \[\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}?\] This is the pinned distance problem, a stronger form of Problem 89. Here \(n^{1-o(1)}\) means: for…
Let \(f(n)\) be the minimal \(m\) such that if the edges of \(K_{2^n+1}\) are coloured with \(n\) colours then there must be a monochromatic odd cycle of length at most \(m\). Estimate \(f(n)\).
Let \(f(n,k)\) be minimal such that there is a graph with \(n\) vertices and \(f(n,k)\) edges where every set of \(k+2\) vertices induces a subgraph with maximum degree at least \(k\). Determine \(f(n,k)\).
Let \(r\geq 3\). For an \(r\)-uniform hypergraph \(G\) let \(\tau(G)\) denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in \(G\). Determine the best…
Erdős-Rogers problem
Let \(X\) be a set of cardinality \(\aleph_\omega\) and \(f\) be a function from the finite subsets of \(X\) to \(X\) such that \(f(A)\not\in A\) for all \(A\). Must there exist an infinite \(Y\subseteq X\) that is independent - that is,…
Let \(X\) be a finite set of size \(n\) and \(H(n)\) be such that there is a function \(f:\{A : A\subseteq X\}\to X\) so that for every \(Y\subseteq X\) with \(\lvert Y\rvert \geq H(n)\) we have \(\left\{ f(A) : A\subseteq Y\right\}=X\).…
Let \(k \geq 4\) and let \(g_k(n)\) denote the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) and girth \(> m\) (i.e. containing no cycle of length \(\leq m\)). Does…
Let \(\omega(G)\) denote the clique number of \(G\) and \(\chi(G)\) the chromatic number. If \(f(n)\) is the maximum value of \(\chi(G)/\omega(G)\), as \(G\) ranges over all graphs on \(n\) vertices, then does…
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…
For every \(k \geq 3\), does there exist \(f(k)\) such that every finite graph of chromatic number at least \(f(k)\) has an odd cycle whose vertices induce a graph of chromatic number at least \(k\)? The cycle may have chords in the…
Let \(f(n)\) be the maximal number of edges in a graph on \(n\) vertices such that all cycles have more vertices than chords. Is it true that \(f(n)\ll n\)? A problem of Hamburger and Szegedy. A chord is an edge between two vertices of the…
Let \(f(n;t)\) be minimal such that if a \(t\)-uniform hypergraph on \(n\) vertices contains at least \(f(n;t)\) edges then there must be four edges \(A,B,C,D\) such that \[A\cup B= C\cup D\] and \[A\cap B=C\cap D=\emptyset.\] Estimate…
Let \(f(k,r)\) be minimal such that if \(A_1,A_2,\ldots\) is a family of sets, all of size \(k\), such that for every collection of \(r\) of the \(A_is\) there is some pair \(\{x,y\}\) which intersects all of the \(A_j\), then there is…
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(g(n)\) be the maximum number of distinct values the \(R(x_i)\)…
ambiguous statement
Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) be such that no circle whose centre is one of the \(x_i\) contains three other points. Are there at least \[(1+c)\frac{n}{2}\] distinct distances determined between the \(x_i\), for some constant…
Is it true that if \(A\subset \mathbb{R}^2\) is a set of \(n\) points such that every subset of \(3\) points determines \(3\) distinct distances (that is, \(A\) has no isosceles triangles, degenerate ones included) then \(A\) determines at…
ambiguous statement
Let \(x_1, \ldots, x_n \in \mathbb{R}^3\) be the vertices of a convex polyhedron. Are there at least \[(1 - o(1)) \frac{n}{2}\] many distinct distances between the \(x_i\)? The \((1 - o(1)) \frac{n}{2}\) lower bound is formalised as: for…
Are there, for all large \(n\), some points \(x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2\) such that the number of distinct distances \(d(x_i,y_j)\) is \[o\left(\frac{n}{\sqrt{\log n}}\right)?\] We require all \(2n\) points to be…
ambiguous statement
Let \(k \geq 2\), and let \(q(n,k)\) denote the least prime which does not divide \(\prod_{1 \leq i \leq k}(n+i)\). Is it true that, if \(k\) is fixed and \(n\) is sufficiently large, then \(q(n,k) < (1+o(1))\log n\)?
A pairwise balanced design for \(\{1,\ldots,n\}\) is a collection of sets \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that \(2\leq \lvert A_i\rvert <n\) and every pair of distinct elements \(x,y\in \{1,\ldots,n\}\) is contained in…
Let \(p, q \geq 1\) be fixed integers. Define \(H(n) = H(n; p, q)\) to be the largest \(m\) such that any graph on \(n\) vertices where every set of \(p\) vertices spans at least \(q\) edges must contain a complete graph on \(m\) vertices.…
Is it true that the number of incongruent sets of \(n\) points in \(\mathbb{R}^2\) which maximise the number of unit distances tends to infinity as \(n\to\infty\)? The actual maximal number of unit distances is the subject of [Erdős…
orchard problems
Let \(A\subseteq \mathbb{R}^d\) be a set of \(n\) points such that all pairwise distances differ by at least \(1\). Is the diameter of \(A\) at least \((1+o(1))n^2\)? The quantifiers in the source are ambiguous. Following the remarks on…
Is every sufficiently large integer of the form \(ap^2+b\) for some prime \(p\) and integers \(a \geq 1\) and \(0 \leq b < p\)?
Denote by \(M(n, k)\) the least common multiple of the finite set \(\{n+1, \dotsc, n+k\}\). Is it true that for all \(m \geq n + k\), we get \(M(m, k) \neq M(n, k)\)?
Let \(\epsilon>0\) and \(\omega(n)\) count the number of distinct prime factors of \(n\). Are there infinitely many values of \(n\) such that \[\omega(n-k) < (1+\epsilon)\frac{\log k}{\log\log k}\] for all \(k<n\) which are sufficiently…
Is it true that, for all sufficiently large \(n\), there exists some \(k\) such that \[ p(n+k)>k^2+1, \] where \(p(m)\) denotes the least prime factor of \(m\)?
**Erdős problem 681.** Is it true that for all large \(n\) there exists \(k\) such that \(n + k\) is composite and \(p(n+k) > k^2\), where \(p(m)\) is the least prime factor of \(m\) ?
Let \(P(n, k)\) be the largest prime factor of \(\binom{n}{k}\). There exists \(c > 0\) such that \(P(n, k) \ge \min(n - k + 1, k^{1 + c})\) for all \(0 < k \le n/2\). Erdős stated this for \(1 \le k \le n\) with the bound…
Let \(f(n)\) be the smallest \(0 \leq k \leq n\) for which the factor of \(\binom{n}{k}\) supported on primes at most \(k\) exceeds \(n^2\). Give bounds for \(f(n)\). An internal OpenAI model [APSSV26] has given an elementary argument…
Let \(\epsilon > 0\) and let \(n\) be large depending on \(\epsilon\). Is it true that for all \(n^{\epsilon} < k \leq n^{1-\epsilon}\) the number of distinct prime divisors of \(\binom{n}{k}\) is \[(1+o(1))\, k \sum_{k < p < n}…
Can every integer \(N≥2\) be written as \[N=\frac{\prod_{1\leq i\leq k}(m+i)}{\prod_{1\leq i\leq k}(n+i)}\] for some \(k≥2\) and \(m≥n+k\)?
Let \(Y(x)\) be the maximal \(y\) such that there exists a choice of congruence classes \(a_p\) for all primes \(p\leq x\) such that every integer in \([1,y]\) is congruent to at least one of the \(a_p\pmod{p}\). Give good estimates for…
Estimate \(\epsilon_n\).
Let n be sufficiently large. Is there some choice of congruence class a_p for all primes 2 ≤ p ≤ n such that every integer in [1,n] satisfies at least two of the congruences ≡ a_p (mod p)? Yes: this follows from the greedy-matching…
Given \(A \subseteq \mathbb{N}\), let \(M_A = \{n \geq 1 : a \mid n \text{ for some } a \in A\}\). Find a necessary and sufficient condition on \(A\) for \(M_A\) to have density \(1\).
Let \(q_1 < q_2 < \cdots\) be a sequence of primes such that \(q_{i + 1} \equiv 1 \pmod{q_i}\). Is it true that \[ \lim_{k \to \infty} q_k^{1/k} = \infty? \]
Let \(f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})\) and let \(P(n)\) be the largest prime dividing \(n\). **(a)** Characterise those composite \(n\) such that \(f(n) = n/P(n)\). Erdős–Szekeres [ErSz78] note that \(f(n) = n/P(n)\)…
Let \(\mathcal{F}\) be a family of sets closed under taking subsets (i.e. if \(B\subseteq A\in\mathcal{F}\) then \(B\in \mathcal{F}\)). There exists some element \(x\) such that whenever \(\mathcal{F}'\subseteq \mathcal{F}\) is an…
Does \(\chi(G_n)\) grow exponentially in \(n\)? Yes: Frankl and Wilson [FrWi81] proved an exponential lower bound and Larman and Rogers [LaRo72] proved an exponential upper bound. Here exponential growth means that there are constants…
Let \(f(n)\) be minimal such that, for any \(A=\{a_1,\ldots,a_n\}\subseteq [2,\infty)\cap\mathbb{N}\) of size \(n\), in any interval \(I\) of \(f(n)\max(A)\) consecutive integers there exist distinct \(x_1,\ldots,x_n\in I\) such that…
Let \(f(n)\) be minimal such that in \((n,n+f(n))\) there exist distinct integers \(a_1,\ldots,a_n\) such that \(k\mid a_k\) for all \(1\leq k\leq n\). Obtain an asymptotic formula for \(f(n)\).
Let \(f(n,m)\) be minimal such that \((m,m+f(n,m))\) contains distinct integers \(a_1,\ldots,a_n\) with \(k \mid a_k\) for \(1 \leq k \leq n\). Prove that \(\max_m f(n,m) \leq n^{1+o(1)}\).
Determine, for any \(k>r>2\), the limiting value as \(n\to\infty\) of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where \(\mathrm{ex}_r(n,K_k^r)\) is the largest number of \(r\)-edges which can placed on \(n\) vertices so that there…
Is it true that, for every bipartite graph \(G\), there exists some \(\alpha\in [1,2)\) and \(c>0\) such that \[\mathrm{ex}(n;G)\sim cn^\alpha?\] The condition that \(G\) have at least two edges excludes degenerate forbidden graphs whose…
Is it true that \[\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?\]
Let \(r\geq 2\), and let \(\mathrm{ex}_r(n;K_{r+1}^r)\) be the maximum number of \(r\)-edges that can be placed on \(n\) vertices without forming a \(K_{r+1}^r\) (the \(r\)-uniform complete graph on \(r+1\) vertices). Is every…
Give an asymptotic formula for the number of \(k\times n\) Latin rectangles. The formula \(F(k,n)\) must satisfy \(L(k,n)\sim F(k,n)\) as \(n\to\infty\) for every choice of \(k=k(n)\leq n\), so it also covers Latin squares (\(k=n\)).
As \(n\to \infty\) ranges over integers \(\sum_{p\leq n}1_{n\in (p/2,p)\pmod{p}}\frac{1}{p}\sim \frac{\log\log n}{2}\)? A conjecture of Erdős, Graham, Ruzsa, and Straus [EGRS75]. By \(n\in (p/2,p)\pmod{p}\) we mean \(n\equiv r\pmod{p}\)…
Let \(k ≥ 2\). Does \(((n+k)!)^2∣(2n)!\) hold for infinitely many \(n\)?
Find some reasonable function \(f(n)\) such that, for almost all integers \(n\), the least integer \(m\) such that \(m\nmid \binom{2n}{n}\) satisfies \[m\sim f(n).\] Here "almost all" means natural density \(1\), and \(m \sim f(n)\) means…
Find, for all large \(n\), a non-trivial pairwise balanced block design \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that, for all \(t\), there are \(O(n^{1/2})\) many \(i\) such that \(\lvert A_i\rvert=t\).
Let \(\mathfrak{m}\) be an infinite cardinal and \(G\) be a graph with chromatic number \(\mathfrak{m}\). Let \(r\geq 1\). Must \(G\) contain a subgraph of chromatic number \(\mathfrak{m}\) which does not contain any odd cycle of length…
Let \(\epsilon>0\). Does there exist \(A\subseteq \mathbb{N}\) such that the lower density of \(A+A\) is at least \(1-\epsilon\) and yet \(1_A\ast 1_A(n) \ll_\epsilon 1\) for all \(n\)?
What is the supremum of the set of admissible numbers?
Let \(f(n;k,l)=\min \mathrm{ex}(n;G)\), where \(G\) ranges over all graphs with \(k\) vertices and \(l\) edges. Give good estimates for \(f(n;k,l)\) in the range \(k<l\leq k^2/4\). In [Er64c, p. 33] this question is asked for…
Let \(c(n)\) be minimal such that if \(k\geq c(n)\) then the \(n\)-dimensional unit cube can be decomposed into \(k\) homothetic \(n\)-dimensional cubes. Give good bounds for \(c(n)\) — in particular, is it true that \(c(n)\gg n^n\)? The…
For every prime p, does the density of integers with h n = p exist?
What is the size of the largest Sidon subset \(A\subseteq\{1,2^2,\ldots,N^2\}\)? Is it \(N^{1-o(1)}\)?
Is every proportionately dissociated (infinite) set the union of a finite number of dissociated sets?
Let \(\epsilon > 0\). Is there some set \(A\subset\mathbb{N}\) of density \(> 1 - \epsilon\) such that \(a_1\cdots a_r = b_1\cdots b_s\) with \(a_i, b_j\in A\) can only hold when \(r = s\)?
Let \(g(n)\) be maximal such that given any set \(A\subset \mathbb{R}\) with \(\lvert A\rvert=n\) there exists some \(B\subseteq A\) of size \(\lvert B\rvert\geq g(n)\) such that \(b_1+b_2\not\in A\) for all \(b_1\neq b_2\in B\). Estimate…
Let \(h(n)\) be maximal such that if \(A\subseteq \mathbb{Z}\) with \(\lvert A\rvert=n\) then there is \(B\subseteq A\) with \(\lvert B\rvert \geq h(n)\) such that if \(a_1+\cdots+a_r=b_1+\cdots+b_s\) with \(a_i,b_i\in B\) then \(r=s\).…
Let \(k\geq 2\) and let \(g_k(n)\) be the largest possible size of \(A\subseteq \{1,\ldots,n\}\) such that every \(m\) has \(<k\) solutions to \(m=a_1a_2\) with \(a_1<a_2\in A\). Is it true that \[g_3(n)=\frac{\log\log n}{\log…
Is it true that any \(K_r\)-free graph on \(n\) vertices with average degree \(t\) contains an independent set on \[\gg_r \frac{\log t}{t}n\] many vertices? A conjecture of Ajtai, Erdős, Komlós, and Szemerédi [AEKS81].
Does there exist some \(\epsilon>0\) such that, for all sufficiently large \(n\), there exists a graph \(G\) on \(n\) vertices with at least \(\epsilon n^2\) edges whose edges can be coloured with \(n\) colours so that every \(C_4\)…
\(R(n)\) denotes the diagonal Ramsey number \(R(n,n)\), i.e., hypergraphRamsey 2 n. -/ local notation "R" => hypergraphRamsey 2 /-- Is it true that \(\frac{R(n+1)}{R(n)}\geq 1+c\) for some constant \(c>0\), for all large \(n\)?
Let \(h(n)\) be minimal such that every graph on \(n\) vertices where every set of \(7\) vertices contains a triangle must contain a clique on at least \(h(n)\) vertices. Estimate \(h(n)\). In particular, do there exist constants…
Let \(f(N)\) be maximal such that there exists \(A\subseteq \{1,\ldots,N\}\) with \(\lvert A\rvert=\lfloor N^{1/2}\rfloor\) such that \(\lvert (A+A)\cap [1,N]\rvert=f(N)\). Estimate \(f(N)\).
Let \(H(n)\) be the smallest integer \(l\) such that there exists \(k < l\) with \((k^n-1, l^n-1) = 1\). Is it true that \(H(n) = 3\) infinitely often? That is, is \((2^n-1, 3^n-1) = 1\) for infinitely many \(n\) (see…
Is it true that, for every \(\epsilon>0\), there exist infinitely many \(n\) such that \(g(n) > n^{1-\epsilon}\)?
Let \(h(x)\) count the number of integers \(1\leq a<b<x\) such that \((a,b)=1\) and \(\sigma(a)=\sigma(b)\), where \(\sigma\) is the sum of divisors function. Is it true that \(h(x)>x^{2-o(1)}\)? That is, is it true that for every…
Are there infinitely many \(n\) such that, for all \(k\geq 1\) \[ \tau(n + k) \ll k? \]
Is it true that, for any \(a \in \mathbb{Z}\), there are infinitely many \(n\) such that \[\phi(n) | n + a\]?
**Erdős Problem 829 (open).** Let \(A \subseteq \mathbb{N}\) be the set of perfect cubes. Is it true that \((1_A \ast 1_A)(n) \ll (\log n)^{O(1)}\)? That is, does there exist a natural number \(C\) such that the number of representations…
**Erdos Problem 830, Part 1** We say that \(a,b\in \mathbb{N}\) are an amicable pair if \(\sigma(a)=\sigma(b)=a+b\). Are there infinitely many amicable pairs?
Let \(r\geq 2\) and let \(G\) be an intersecting \(r\)-uniform hypergraph with chromatic number \(3\). Must \(G\) contain \(O(r^2)\) many vertices? Vertices are counted in the union of the edges, so isolated vertices are excluded. Alon has…
Let \(k\geq 2\) and \(A_k\subseteq [0,1]\) be the set of \(\alpha\) such that there exists some \(\beta(\alpha)>\alpha\) with the property that, if \(G_1,G_2,\ldots\) is a sequence of \(k\)-uniform hypergraphs with \[\liminf…
Erdős Problem 839 (Part 1) [Er78f][Er92c]: Let \(1 \leq a_1 < a_2 < \cdots\) be a strictly increasing sequence of positive integers such that no \(a_i\) is the sum of consecutive \(a_j\) for \(j < i\). Is it true that…
Let \(f(N)\) be the size of the largest quasi-Sidon subset \(A\subset\{1,\ldots,N\}\), where we say that \(A\) is quasi-Sidon if \[\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}.\] How does \(f(N)\) grow? Following [Er81h, p. 175], we…
Singmaster's conjecture
Is it true that, for every integer \(t\geq1\), there is some integer \(a\) such that \({n \choose k} = a\) with \(1\leq k \le \frac{n}{2}\) has exactly \(t\) solutions?
Erdős-Woods conjecture
Can there exist two distinct integers \(x\) and \(y\) such that \(x,y\) have the same prime factors, \(x+1,y+1\) have the same prime factors, and \(x+2,y+2\) also have the same prime factors?
Let \(d_n = p_{n+1} - p_n\), where \(p_n\) is the \(n\)th prime. Let \(h(x)\) be maximal such that for some \(n < x\) the numbers \(d_n, d_{n+1}, \ldots, d_{n+h(x)-1}\) are all distinct [Er85c]. Estimate \(h(x)\). In particular, is it true…
Let \(d_n = p_{n+1} - p_n\), where \(p_n\) is the \(n\)th prime. Let \(r(x)\) be the smallest even integer \(t\) such that \(d_n = t\) has no solutions for \(n \le x\). Is it true that \(r(x) \to \infty\)?
second Hardy-Littlewood conjecture
Erdős Problem 855 (Segal's conjecture): \(\pi(x + y) \le \pi(x) + \pi(y)\) for all sufficiently large \(x, y\), i.e. for all \(x, y \ge N\) for some \(N\).
weak sunflower problem
Estimate m(n,k), or better give an asymptotic formula.
The density of the divisor sum set is asymptotically equivalent to \(c_1 / \log(t)^{c_2}\).
Let \(h(n)\) be such that, for any \(m\geq 1\), in the interval \((m,m+h(n))\) there exist distinct integers \(a_i\) for \(1\leq i\leq \pi(n)\) such that \(p_i\mid a_i\), where \(p_i\) denotes the \(i\)th prime. Estimate \(h(n)\).
Let \(A\subseteq \{1,\ldots,N\}\) be a set such that there exists at most one \(n\) with more than one solution to \(n=a+b\) (with \(a\leq b\in A\)). Estimate the maximal possible size of \(|A|\). In particular, is it true that \[|A| \leq…
Erdős Problem 872, part (i) (weak form): there exists a constant \(\epsilon > 0\) such that the game length is at least \(\epsilon \cdot n\) for all sufficiently large \(n\).
Let \(A = \{a_1 < a_2 < \dots\} \subseteq \mathbb{N}\) and let \(F(A,X,k)\) count the number of \(i\) such that \([a_i,a_{i+1}, \dots ,a_{i+k−1}] < X\), where the left-hand side is the least common multiple. Is it true that, for every…
Is it true that, for almost all \(n\), \(f(n)=o(n\log\log n)\) and \(F(n)\gg n\log\log n\)? The answer is yes; a Lean proof is given in [Ki26].
Let A ⊂ ℕ be an additive basis of order k which is minimal in the sense that if B ⊂ A is any infinite set, then A \ B is not a basis of order k. Must there exist an infinite B ⊂ A such that A \ B is an additive basis of order k + 1?
For \(A\subseteq \{1,\ldots,n\}\) let \(G(A)\) be the graph with vertex set \(A\), where two integers are joined by an edge if they are coprime. Is it true that if \[|A| > \lfloor n/2 \rfloor + \lfloor n/3 \rfloor - \lfloor n/6 \rfloor\]…
Is it true that, for every \(k \geq 1\), there exist integers \(N_1 < \dots < N_k\) such that \(|\cap_i D(N_i)| \geq k\)?
Let \(\epsilon>0\). Is it true that, for all large \(n\), the number of divisors of \(n\) in \((n^{1/2},n^{1/2}+n^{1/2-\epsilon})\) is \(O_\epsilon(1)\)? Erdős attributes this conjecture to Ruzsa.
Is there an absolute constant \(K\) such that, for every \(C > 0\), if \(n\) is sufficiently large then \(n\) has at most \(K\) divisors in \((n^{\frac{1}{2}}, n^{\frac{1}{2}} + C n^{\frac{1}{4}})\).
Let \(v(n,k)\) count the prime factors of \(n+k\) which do not divide \(n+i\) for \(0\leq i < k\). Is it true that \(v_0(n)=\max_{k\geq 0}v(n,k)\to \infty\) as \(n\to \infty\)?
If \(\omega_k(n)\) counts the number of distinct prime factors of \(n\) which are \(>k\), then is it true that, for every \(k\geq 1\), \[\liminf_{n\to \infty}\sum_{0\leq i < k}\omega_k(n+i)\leq k?\]
Let \(2=p_1 < p_2 < \cdots\) be the primes and \(k\geq 2\). Is it true that, for all sufficiently large \(n\), there must exist an integer in \([n,n+p_1\cdots p_k)\) with \(>k\) many prime factors?
Does the limit \(\lim_{n\to\infty} \frac{f(2n)}{f(n)}\) tend to infinity? (Other finite limits have been ruled out by [KoLu25], see below)
Let \(m(n)\) be minimal such that there is an \(n\)-uniform hypergraph with \(m(n)\) edges which is \(3\)-chromatic. Estimate \(m(n)\).
Let \(f(n)\) be minimal such that there is a tournament (a complete directed graph) on \(f(n)\) vertices such that every set of \(n\) vertices is dominated by at least one other vertex. Estimate \(f(n)\).
Does there exists an entire non-zero transcendental function f : ℂ → ℂ such that for any sequence n₀ < n₁ < ..., { z | ∃ k, iteratedDeriv (n k) f z = 0 } is dense.
Prove that there exists some \(c>0\) such that \[h(n) \sim c \left(\frac{n}{\log n}\right)^{1/2}\] as \(n\to \infty\).
Are there infinitely many \(n\) such that if \[ n(n + 1) = \prod_i p_i^{k_i} \] is the factorisation into distinct primes then all exponents \(k_i\) are distinct?
Is it true that, for every \(r\), there is a \(k\) such that if \(I_1,\ldots,I_r\) are disjoint intervals of consecutive integers, all of length at least \(k\), then \[ \prod_{1\leq i\leq r}\prod_{m\in I_i}m \] is not a perfect power?
Let \(k_1 \geq k_2 \geq 3\). Are there only finitely many \(n_2\geq n_1 + k_1\) such that \[ \prod_{1\leq i\leq k_1}(n_1 + i)\ \text{and}\ \prod_{1\leq j\leq k_2} (n_2 + j) \] have the same prime factors?
Let \(p_k\) denote the \(k\)th prime. For infinitely many \(r\) there are at least two integers \(p_r < n < p_{r+1}\) all of whose prime factors are \(< p_{r + 1} - p_r\).
If \(n(n+1)=2^k3^lm\), where \((m,6)=1\), then is it true that \(\limsup_{n\to \infty} \frac{2^k3^l}{n\log n}=\infty\)?
Let \(A=\{n_1 < n_2 < \cdots\}\) be the sequence of powerful numbers (if \(p\mid n\) then \(p^2\mid n\)). Are there only finitely many three-term progressions of consecutive terms \(n_k,n_{k+1},n_{k+2}\)?
If \(r≥4\) then can the sum of \(r-2\) coprime \(r\)-powerful numbers ever be itself \(r\)-powerful?
Let \(r \ge 3\). Is it true that the set of integers which are the sum of at most \(r\) \(r\)-powerful numbers has density \(0\)?
Is there some constant \(c > 0\) such that \(h(n) < (\log n)^{c + o(1)}\) and, for infinitely many \(n\), \(h(n) > (\log n)^{c - o(1)}\).
Let \(A\) be the set of powerful numbers. Is is true that \(1_A\ast 1_A(n)=n^{o(1)}\) for every \(n\)?
Let \(k \ge 4\) and \(r\ge 1\). Must there exist a graph \(G\) with chromatic number \(k\) such that every vertex is critical, yet every critical set of edges has size \(>r\)?
Is it true that \(F(x) \leq (\log x)^{O(1)}\)?
Let \(S \subseteq \mathbb{R}\) be a set containing no solutions to \(a + b = c\). Must there be a set \(A \subseteq \mathbb{R} \setminus S\) of cardinality continuum such that \(A + A \subseteq \mathbb{R}\setminus S\)?
Is it true that \(\liminf f(n)=1\)?
If 1 < a 0 < ... has property Erdos951Prop, is it true that #{a i ≤ x} ≤ π x?
Gaussian moat problem
Is there an infinite sequence of distinct Gaussian primes \(x_1,x_2,\ldots\) such that \(\lvert x_{n+1}-x_n\rvert \ll 1\)? No. This was disproved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
If \(A\subset \mathbb{N}\) has density \(0\) then \(s^{-1}(A)\) must also have density \(0\). A conjecture of Erdős, Granville, Pomerance, and Spiro [EGPS90].
Let \(A\subseteq \mathbb{R}^2\) be a set of size \(n\) and let \(\{d_1,\ldots,d_k\}\) be the set of distinct distances determined by \(A\). Let \(f(d)\) be the number of times the distance \(d\) is determined, ordered so that…
Sylvester and Schur [Er34] proved that every set of \(k\) consecutive integers greater than \(k\) contains an integer divisible by a prime greater than \(k\), i.e. not \((k+1)\)-smooth.
Main conjecture: \(\log k(n) \le (\log n)^{(1/2 + o(1))}\)
Does the set {n | u n < u (n+1)} have positive lower density? Yes. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
Jacobsthal's function
Let \(h(k)\) be Jacobsthal's function, defined to as the minimal \(m\) such that, if \(n\) has at most \(k\) prime factors, then in any set of \(m\) consecutive integers there exists an integer coprime to \(n\). Determine the order of…
Let p(a, d) be the least prime congruent to a (mod d). Does there exist a constant c > 0 such that for all large d, p(a, d) > (1 + c) * φ(d) * log d for ≫ φ(d) many values of a?
**Erdős problem 972.** Let \(\alpha > 1\) be irrational. Are there infinitely many primes \(p\) such that \(\lfloor p\alpha \rfloor\) is also prime?
For an irreducible polynomial \(f \in \mathbb{Z}[x]\) with \(f(n) \ge 1\) for sufficiently large \(n\), does there exists a constant \(c = c(f) > 0\) such that \(\sum_{n \le x} \tau(f(n)) \approx c \cdot x \log x\)? Note that it is unclear…
Let f ∈ ℤ[X] be an irreducible polynomial with positive leading coefficient. Suppose that the degree k of f is larger than 2, is not equal to a power of 2, and f n has no fixed (k - 1)-th power divisors other than 1. Then the set of n such…
Let \(k ≥ 2\), and let \(f_k(n)\) count the number of solutions to \(n = p_1^k + \dots + p_k^k\), where the \(p_i\) are prime numbers. Is it true that \(\limsup f_k(n) = \infty\)?
Is it true that, for every prime \(p\), there is a prime \(q \leq p\) which is a primitive root modulo \(p\)?
Erdős Problem 995: For every lacunary sequence \((n_k)\) of integers and every \(f \in L^2([0,1])\) with \(\int_0^1 f = 0\), is it true that for almost all \(\alpha\), \[\sum_{k < N} f(\{\alpha n_k\}) = o\!\left(N \sqrt{\log\log…
Does there exists a positive constant C such that for all f ∈ L²[0,1] and all lacunary sequences n, if ‖f - fₖ‖₂ = O(1 / log log log k ^ C), then for almost every x, lim ∑ k ∈ Finset.range N, f (n k • x)) / N = ∫ t, f t ∂t?
For any \(0<\alpha<1\), let \(f(\alpha,n)=\frac{1}{\log n}\sum_{1\leq k\leq n}(\tfrac{1}{2}- \{ \alpha k\})\). Does \(f(\alpha,n)\) have an asymptotic distribution function? In other words, is there a non-decreasing function \(g\) such…
Are there infinitely many solutions to \(\phi(n) = \phi(n+1)\), where \(\phi\) is the Euler totient function?
For any fixed c > 0, if x is sufficiently large then there exists n ≤ x such that the values of φ(n+k) are all distinct for 1 ≤ k ≤ (log x)^c. This is an open problem.
pancyclic graphs
If \(R(k)\) is the Ramsey number for \(K_k\), the minimal \(n\) such that every \(2\)-colouring of the edges of \(K_n\) contains a monochromatic copy of \(K_k\), then \[\frac{R(k)}{k2^{k/2}}\to \infty.\] In [Er93] Erdős offers…
Let \(R(k,l)\) be the usual Ramsey number: the smallest \(n\) such that if the edges of \(K_n\) are coloured red and blue then there exists either a red \(K_k\) or a blue \(K_l\). Prove the existence of some \(c>0\) such that \[\lim_{k\to…
Let \(h(n)\) be such that every graph on \(n\) vertices with \(>n^2/4\) many edges contains a triangle whose vertices have degrees summing to at least \(h(n)\). Estimate \(h(n)\). In particular, is it true that \[h(n)\geq…
Is there a constant \(c > 0\) such that every graph on \(2^n\) vertices with minimum degree \(> (1-c) \cdot 2^n\) contains the \(n\)-dimensional hypercube \(Q_n\)? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal…
What is the infimum of |{x ∈ ℝ : |f x| < 1}| over all nonconstant monic polynomials f such that all of its roots are real and contained in [-1,1]?
Let \(t>1\) be a rational number. Is \(\sum_{n=1}^\infty\frac{1}{t^n-1}=\sum_{n=1}^\infty \frac{\tau(n)}{t^n}\) irrational, where \(\tau(n)\) counts the divisors of \(n\)? A conjecture of Chowla.
unitary perfect numbers
Are there only finitely many unitary perfect numbers?
multiply perfect numbers
Let \(f(n)\) be the minimal integer \(m\) such that \(n\) is the sum of the \(k\) smallest divisors of \(m\) for some \(k\geq 1\). Is it true that \(f(n)=o(n)\)? The strong claim that \(f(n)=o(n)\) was disproved by Tao in the comments to…
A prime \(p\) is in class \(1\) if the only prime divisors of \(p+1\) are \(2\) or \(3\). In general, a prime \(p\) is in class \(r\) if every prime factor of \(p+1\) is in some class \(\leq r-1\), with equality for at least one prime…
Let \(k ≥ 2\). Does there exist a prime \(p\) and consecutive intervals \(I_0,\dots,I_k\) such that \(\prod\limits_{n{\in}I_i}n \equiv 1 \mod n\) for all \(1 \le i \le k\)?
Carmichael numbers
Is it true that \(C(x)=x^{1-o(1)}\)? This is discussed in problem A13 of Guy's collection [Gu04].
Are there infinitely many primes \(p\) such that \(p - k!\) is composite for each \(k\) such that \(1 ≤ k! < p\)?
The conjecture is about the function \(f(n)\) which counts the number of solutions to \(k\sigma(k)=n\), where \(\sigma(k)\) is the sum of divisors of \(k\). The first bound is that \(f(n)\) grows slower than any power of…
How many (ordered) solutions are there to σ(a) + σ(b) = σ(a + b) with a + b ≤ x? Is it true that this number is asymptotic to c * x for some constant c > 0?
Erdős asked whether the limiting density f n / n exists and, if so, whether it is irrational.
Estimate \(n_k\) by finding a better upper bound than Cambie's \(n_k \leq k \cdot \operatorname{lcm}(1, \dotsc, k-1)\). The comparator takes its least common multiple in ℕ and casts the result. Writing the ascription as ((… ).lcm (fun n :…
Are there infinitely many primes \(p\) such that \(p = 2^k * q + 1\) for some prime \(q\) and \(k ≥ 0\)? This is mentioned as B46 in [Unsolved Problems in Number Theory](https://doi.org/10.1007/978-0-387-26677-0) by *Richard K. Guy*
Does every graph with chromatic number \(\aleph_1\) contain a countable subgraph which is infinitely connected?
Is it true that there are infinitely many \(p\) for which \(f(p) = p − 1\)?
Is it true that \(A(x) \le x^{o(1)}\)?
Let \(S\) be the set of all \(m\geq 1\) such that there exists a prime \(p\not\equiv 1\pmod{m}\) such that \(m! + 1 \equiv 0\pmod{p}\). Does \[ \lim\frac{|S\cap[1, x]|}{x} \] exist?
Let \(r\geq 3\). There exists \(c_r>r^{-r}\) such that, for any \(\epsilon>0\), if \(n\) is sufficiently large, the following holds. Any \(r\)-uniform hypergraph on \(n\) vertices with at least \((1+\epsilon)(n/r)^r\) many edges contains a…
Let \(d\geq 3\), and let \(f_d(n)\) be the minimal \(m\) such that every set of \(n\) points in \(\mathbb{R}^d\) determines at least \(m\) distinct distances. Estimate \(f_d(n)\) - in particular, is it true that…
contact number problem
Let \(f_d(n)\) be the minimal \(m\) such that any set of \(m\) points in \(\mathbb{R}^d\) contains a set of \(n\) points for which any two determined distances are distinct. Erdős Problem 1088 asks to estimate \(f_d(n)\). In particular, is…
Are there infinitely many binomial coefficients with deficiency 1?
For all \(n\ge 2k\) the least prime factor of \(\binom{n}{k}\) is \(\le\max(n/k,k)\), with only finitely many exceptions.
The main conjecture: for any finite set of integers \(A\) with \(|A| = n\), the number of distinct common differences in three-term arithmetic progressions is \(O(n^{3/2})\). This conjecture was resolved negatively by showing that the…
1. There is NO good sequence with polynomial growth.
Let \(p(n)\) be the partition number of \(n\) and \(F(n)\) be the number of distinct prime factors of \(\prod_{i= 1} ^ {n} p(n)\), then \(F(n)\) tends to infinity when \(n\) tends to infinity. The answer is yes: Schinzel and Wirsing…
Let \(r \ge 2\). Is every large integer the sum of at most \(r + 1\) many \(r\)-powerful numbers?
For each \(k \geq 2\), does the set \(A = \left\{ \sum_{n\in S}n! : S\subset \mathbb{N}_{\geq 1}\text{ finite}\right\}\) of all finite sums of distinct factorials contain only finitely many \(k\)-th powers?
Let \(f(N)\) be the size of the largest subset \(A\subseteq \{1,\ldots,N\}\) such that every \(n\in A+A\) is squarefree. Estimate \(f(N)\). In particular, is it true that \(f(N)\leq N^{o(1)}\), or even \(f(N) \leq (\log N)^{O(1)}\)? This…
Let \(p>q\geq 2\) be two coprime integers. We call \(n\) representable if it is the sum of integers of the form \(p^kq^l\), none of which divide each other. If \(\{p,q\}\neq \{2,3\}\) then what can be said about the density of…
Sierpinski numbers
**Erdős Problem 1113.** Do there exist Sierpiński numbers that possess no finite covering set of primes? Erdős and Graham [ErGr80] conjectured that the answer is yes. A negative answer would imply that there are infinitely many Fermat…
Let \(f:\mathbb{N}\to \mathbb{R}\) be an additive function (i.e. \(f(ab)=f(a)+f(b)\) whenever \((a,b)=1\)). Let \[A=\{ n \geq 1: f(n+1)< f(n)\}.\] If \(\lvert A\cap [1,X]\rvert =o(X)\) then must \(f(n)=c\log n\) for some…
Let \(C>0\). There exists \(\epsilon>0\) such that if \(n\) is sufficiently large the following holds. For any \(x_1,\ldots,x_n\in [-1,1]\) there exist \(y_1,\ldots,y_n\in [-1,1]\) such that, if \(P\) is a polynomial of degree…
Collatz conjecture
The Collatz conjecture states that for any positive integer \(n\), there exists a natural number \(m\) such that the \(m\)-th term of the sequence is 1.
Let \(d_n=p_{n+1}-p_n\), where \(p_n\) denotes the \(n\)th prime. Is it true that \[\frac{\max_{n < x}d_{n}d_{n-1}}{(\max_{n < x}d_n)^2}\to 0\] as \(x\to \infty\)?
Let \(1\leq u_1 < u_2 < \cdots\) be the sequence of integers with at most \(2\) prime factors. Is it true that \[\limsup_{k \to \infty} \frac{u_{k+1}-u_k}{\log k}=\infty?\]
Are there infinitely many \(n > 2\) such that \(n - 2^k\) is prime for all \(k \geq 1\) with \(2^k < n\)? The only known such \(n\) are \(4, 7, 15, 21, 45, 75, 105\) (OEIS [A039669](https://oeis.org/A039669)).
Let \(A=\{1\leq a_1 < a_2 < \cdots\}\) and \(B=\{1\leq b_1 < b_2 < \cdots\}\) be sets of integers with \(a_n/b_n\to 1\). If \(A+B\) contains all sufficiently large positive integers then is it true that \(\limsup 1_A\ast 1_B(n)=\infty\)? A…
Is \(B=\{2^m3^n : m,n\geq 0\}\) an essential component? In [Ru99] Ruzsa states "The simplest set with a chance to be an essential component is the collection of numbers in the form \(2^m3^n\) and Erdős often asked whether it is an…
Is there some constant \(c > 0\) such that, for all large enough \(n\) and all polynomials \(P\) of degree \(n\) with coefficients in \(\{-1, 1\}\), \[\max_{|z|=1} |P(z)| > (1 + c) \sqrt{n}?\] No. This was disproved by an internal OpenAI…
Let \(s,k,r\geq 2\). Let \(\mathcal{F}\) be the family of all \(r\)-uniform hypergraphs with \(k\) vertices and \(s\) edges. Determine \[\mathrm{ex}_r(n,\mathcal{F}).\]
Let \(K_{t}(r)\) be the complete \(t\)-partite \(t\)-uniform hypergraph with \(r\) vertices in each class. Is it true that \[\mathrm{ex}_t(n,K_t(r)) \geq n^{t-r^{1-t}-o(1)}\] for all \(t,r\geq 2\)? The restriction \(r\geq 2\) excludes…
Determine whether there exists a constant \(C>1\) such that the following holds. Let \(P\) be a finite [projective plane](https://en.wikipedia.org/wiki/Projective_plane). Must there exist a set of points \(S\) such that…
ambiguous statement
**Erdős Problem 1167.** Let \(r \geq 2\) be finite, \(\gamma \geq 2\), and \(\lambda\) be an infinite cardinal. Let \(\kappa_\alpha > r\) be cardinals for all \(\alpha < \gamma\). Is it true that \[2^\lambda \to (\kappa_\alpha + 1)_{\alpha…
Let \(\kappa\) be an uncountable cardinal. Must there exist a cardinal \(\lambda\) such that every graph with chromatic number \(\lambda\) contains a triangle-free subgraph with chromatic number \(\kappa\)? Shelah proved that a negative…
Let \(G\) be a finite \(3\)-uniform hypergraph, and let \(F_G(\kappa)\) denote the collection of \(3\)-uniform hypergraphs with chromatic number \(\kappa\) not containing \(G\). If \(F_G(\aleph_1)\) is not empty then there exists…
For \(r\geq 3\) let \(d_r(e)\) be the minimal \(d\) such that \[\mathrm{ex}_r(n,\mathcal{F})=o(n^2),\] where \(\mathcal{F}\) is the family of \(r\)-uniform hypergraphs on \(d\) vertices with \(e\) edges. Prove that \[d_r(e)=(r-2)e+3\] for…
Let \(\delta_k\) be such that in any \(2\)-colouring of \(\{1,\ldots,n\}\) there exist at least \((\delta_k+o(1))n^2\) many monochromatic \(k\)-term arithmetic progressions. Give reasonable bounds (or even an asymptotic formula) for…
Call a set of distinct integers \(1<n_1<\cdots<n_k\) with associated congruence classes \(a_i\pmod{n_i}\) a distinct covering system if every integer satisfies at least one of these congruences. A minimal distinct covering system is one…
Let \(A\subset\mathbb{N}\) be an infinite Sidon set. Is it true that \[\liminf_{x\to \infty} \frac{\lvert A\cap [1,x]\rvert}{x^{1/2}}(\log x)^{1/2}=0?\] Here \(x\) runs over \(\mathbb{N}\) and the \(\liminf\) is taken in ℝ≥0∞, so that it…
Does there exist, for all \(r\geq 2\), a basis \(A\) of order \(r\) (so that \(f_r(n)>0\) for all large \(n\)) such that \[\sum_{n\leq x}f_r(n)^2 \ll x\] for all \(x\)?
Is it true that in any 2-colouring of \(\mathbb{N}\) there exists an infinite set \(A\) such that all elements of \(A+A\) are the same colour? A conjecture of Owings [Ow74].
Is it true that for every \(\epsilon,\eta>0\) there exists a \(k\) such that the density of \(n\) for which \(P(n(n+1)\cdots(n+k))>n^{1-\epsilon}\) is at least \(1-\eta\) (where \(P(m)\) is the greatest prime divisor of \(m\))?
Prove that \(F(n)\to \infty\) as \(n\to \infty\).
Does \(\{1,2^3,\ldots,N^3\}\) contain a Sidon set of size \(\gg N\)?
Let \(P_d(n)\) be such that in any set of \(n\) points in \(\mathbb{R}^d\) there exist at least \(P_d(n)\) many points which do not contain an isosceles triangle. Estimate \(P_d(n)\) - in particular, is it true that \[P_2(n)<n^{1-c}\] for…
Let \(A=\{a_1<a_2<\cdots\}\) be a sequence of integers which tends to infinity sufficiently fast. If there is an \(n\) such that all \(n+a_k\) are primes then must there exist infinitely many such \(n\)? Erdős [Er80] wrote 'unless I…
Let \(A\subseteq [1,n)\) be a set of integers such that \((a,b)=1\) for all distinct \(a,b\in A\). Is it true that \(\sum_{a\in A}\frac{1}{n-a}\leq \sum_{p < n}\frac{1}{p}+O(1)\)?
Let \(G\) be the graph with vertex set those pairs \((x,y)\in \mathbb{N}^2\) with \(\mathrm{gcd}(x,y)=1\), in which we join two vertices if the differ in only one coordinate, and there by \(\pm 1\). Is there a path going to infinity on…
ambiguous statement