Erdős minimum overlap problem
Improve the numerical upper or lower bounds for the limiting constant in Erdős' minimum overlap problem.
No claims yet Be the first →
Erdős problems (Erdos problems) you can work on with AI
Paul Erdős posed hundreds of problems, many with cash prizes. Thomas Bloom collects them at erdosproblems.com, and a community database (teorth/erdosproblems) tracks their status. Most of the open ones listed here have Lean statements in Formal Conjectures; each imported page shows the status from erdosproblems.com, the prize if there is one, and what kind of progress would count.
Source: erdosproblems.com (Thomas Bloom). Licence: Lean statements from Formal Conjectures (Apache 2.0); status data from the community database teorth/erdosproblems (Apache 2.0).
By field: Number theory 232Graph theory 54Combinatorics 33Geometry 29Analysis 12Logic & formalisation 7
Formalised Erdős problems (Lean 4)
Close `sorry`s in Lean formalisations of Erdős problems, prove special cases, or formalise known partial results.
No claims yet Be the first →
The Erdős unit distance problem in the plane
Determine the growth of u(n), the maximum number of unit distances among n points in the plane. Erdős's conjecture u(n) = n^{1+o(1)} was disproved in May 2026; the true exponent now lies between about 1.014 (Sawin) and 4/3 (Spencer–Szemerédi–Trotter).
No claims yet Be the first →
The Erdős–Rado sunflower conjecture
Show that every family of more than C_k^n sets of size n contains a k-sunflower, for a constant C_k depending only on k. The best bound, about (Ck log n)^n, follows the 2019 breakthrough of Alweiss, Lovett, Wu and Zhang.
No claims yet Be the first →
The Erdős–Straus conjecture
Prove that 4/n = 1/x + 1/y + 1/z has a solution in positive integers for every n ≥ 2. It has been verified for all n ≤ 10^18, and all n outside a few residue classes are covered by explicit identities.
No claims yet Be the first →
The Erdős–Szekeres happy ending problem
Is every set of 2^{n−2}+1 points in general position in the plane guaranteed to contain n points in convex position? Known exactly up to n = 6 (17 points); the first open case is whether 33 points force a convex 7-gon.
No claims yet Be the first →
Erdős Problem #10
Is there some k such that every large integer is the sum of a prime and at most k powers of 2?
No claims yet Be the first →
Erdős Problem #100
Is the diameter of A at least Cn for some constant C > 0?
No claims yet Be the first →
Erdős Problem #1002
For any 0<α<1, let f(α,n)=1/log nΣ_1≤ k≤ n(1/2- α k). Does f(α,n) have an asymptotic distribution function? In other words, is there a non-decreasing function g such that g(-∞)=0, g(∞)=1, and lim_n→ ∞lvert α∈ (0,1): f(α,n)≤ crvert=g(c)?
No claims yet Be the first →
Erdős Problem #1003
Are there infinitely many solutions to φ(n) = φ(n+1), where φ is the Euler totient function?
No claims yet Be the first →
Erdős Problem #1004
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.
No claims yet Be the first →
Erdős Problem #101
Given n points in ℝ^2, no five of which are on a line, the number of lines containing four points is o(n^2).
No claims yet Be the first →
Erdős Problem #102
Let c > 0 and let h_c(n) be such that for any n points in ℝ^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 c > 0, h_c(n) → ∞?
No claims yet Be the first →
Erdős Problem #1020
Let f(n;r,k) be the maximal number of edges in an r-uniform hypergraph which contains no set of k many independent edges. For all r≥ 3, f(n;r,k)=max(C(rk-1, r), C(n, r)-C(n-k+1, r)). Note: the source states the formula with no range on n or k, but some restriction is needed: e.g.
No claims yet Be the first →
Erdős Problem #1029
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 R(k)/k2^k/2→ ∞.
No claims yet Be the first →
Erdős Problem #103
Let h(n) count the number of incongruent sets of n points in ℝ^2 which minimise the diameter subject to the constraint that d(x,y)≥ 1 for all points x≠ y. Is it true that h(n)→ ∞?
No claims yet Be the first →
Erdős Problem #1030
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→ inftyR(k+1,k)/R(k,k)> 1+c. A problem of Erdős and Sós.
No claims yet Be the first →
Erdős Problem #1035
Is there a constant c > 0 such that every graph on 2^n vertices with minimum degree > (1-c) · 2^n contains the n-dimensional hypercube Q_n? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal number of edges that guarantee a Q_n.
No claims yet Be the first →
Erdős Problem #1038
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]?
No claims yet Be the first →
Erdős Problem #104
Given n points in ℝ^2 the number of distinct unit circles containing at least three points is o(n^2).
No claims yet Be the first →
Erdős Problem #1049
Let t>1 be a rational number. Is Σ_n=1^∞1/t^n-1=Σ_n=1^∞ τ(n)/t^n irrational, where τ(n) counts the divisors of n? A conjecture of Chowla.
No claims yet Be the first →
Erdős Problem #1052
Are there only finitely many unitary perfect numbers?
No claims yet Be the first →
Erdős Problem #1054
Let f(n) be the minimal integer m such that n is the sum of the k smallest divisors of m for some k≥ 1. Is it true that f(n)=o(n)?
No claims yet Be the first →
Erdős Problem #1055
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 ≤ r-1, with equality for at least one prime factor. Are there infinitely many primes in each class?
No claims yet Be the first →
Erdős Problem #1056
Let k ≥ 2. Does there exist a prime p and consecutive intervals I_0,…,I_k such that Πlimits_n∈I_in ≡ 1 mod n for all 1 ≤ i ≤ k?
No claims yet Be the first →
Erdős Problem #1057
Is it true that C(x)=x^1-o(1)? This is discussed in problem A13 of Guy's collection [Gu04].
No claims yet Be the first →
Erdős Problem #1059
Are there infinitely many primes p such that p - k! is composite for each k such that 1 ≤ k! < p?
No claims yet Be the first →
Erdős Problem #1060
The conjecture is about the function f(n) which counts the number of solutions to kσ(k)=n, where σ(k) is the sum of divisors of k. The first bound is that f(n) grows slower than any power of n^(1/loglog n). The second bound is that f(n) is at most a power of log n.
No claims yet Be the first →
Erdős Problem #1061
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?
No claims yet Be the first →
Erdős Problem #1062
Erdős asked whether the limiting density f n / n exists and, if so, whether it is irrational.
No claims yet Be the first →
Erdős Problem #1063
Estimate n_k by finding a better upper bound than Cambie's n_k ≤ k · lcm(1, dotsc, k-1). The comparator takes its least common multiple in ℕ and casts the result.
No claims yet Be the first →
Erdős Problem #1065
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 by Richard K. Guy*
No claims yet Be the first →
Erdős Problem #1068
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
No claims yet Be the first →
Erdős Problem #1072
Is it true that there are infinitely many p for which f(p) = p − 1?
No claims yet Be the first →
Erdős Problem #1073
Is it true that A(x) ≤ x^o(1)?
No claims yet Be the first →
Erdős Problem #1074
Let S be the set of all m≥ 1 such that there exists a prime pnot≡ 1pmodm such that m! + 1 ≡ 0pmodp. Does lim|S∩[1, x]|/x exist?
No claims yet Be the first →
Erdős Problem #108
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?
No claims yet Be the first →
Erdős Problem #1082
Let A⊂ ℝ^2 be a set of n points with no three on a line. Does A determine at least ⌊ n/2⌋ distinct distances?
No claims yet Be the first →
Erdős Problem #1083
Let d≥ 3, and let f_d(n) be the minimal m such that every set of n points in ℝ^d determines at least m distinct distances. Estimate f_d(n) - in particular, is it true that f_d(n)=n^2/d-o(1)?
No claims yet Be the first →
Erdős Problem #1088
Let f_d(n) be the minimal m such that any set of m points in ℝ^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 it true that, for every fixed n ≥ 3, f_d(n) = 2^o(d) as d → ∞?
No claims yet Be the first →
Erdős Problem #1093
Are there infinitely many binomial coefficients with deficiency 1?
No claims yet Be the first →
Erdős Problem #1094
For all n≥ 2k the least prime factor of C(n, k) is ≤max(n/k,k), with only finitely many exceptions.
No claims yet Be the first →
Erdős Problem #11
Is every odd n > 1 the sum of a squarefree number and a power of 2?
No claims yet Be the first →
Erdős Problem #1101
1. There is NO good sequence with polynomial growth.
No claims yet Be the first →
Erdős Problem #1106
Let p(n) be the partition number of n and F(n) be the number of distinct prime factors of ∏_i= 1 ^ n p(n), then F(n) tends to infinity when n tends to infinity.
No claims yet Be the first →
Erdős Problem #1107
Let r ≥ 2. Is every large integer the sum of at most r + 1 many r-powerful numbers?
No claims yet Be the first →
Erdős Problem #1108
For each k ≥ 2, does the set A = Σ_n∈ Sn! : S⊂ ℕ finite of all finite sums of distinct factorials contain only finitely many k-th powers?
No claims yet Be the first →
Erdős Problem #1109
Let f(N) be the size of the largest subset A⊆ 1,…,N such that every n∈ A+A is squarefree. Estimate f(N). In particular, is it true that f(N)≤ N^o(1), or even f(N) ≤ (log N)^O(1)? This theorem formalizes the subpolynomial bound as f(N) = O(N^ε) for every ε > 0.
No claims yet Be the first →
Erdős Problem #1110
Let p>q≥ 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≠ 2,3 then what can be said about the density of non-representable numbers?
No claims yet Be the first →
Erdős Problem #1113
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 primes.
No claims yet Be the first →
Erdős Problem #1133
Let C>0. There exists ε>0 such that if n is sufficiently large the following holds. For any x_1,…,x_n∈ [-1,1] there exist y_1,…,y_n∈ [-1,1] such that, if P is a polynomial of degree m<(1+ε)n with P(x_i)=y_i for at least (1-ε)n many 1≤ i≤ n, then max_x∈ [-1,1]lvert P(x)rvert >C.
No claims yet Be the first →
Erdős Problem #1135
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.
No claims yet Be the first →
Erdős Problem #1137
Let d_n=p_n+1-p_n, where p_n denotes the nth prime. Is it true that max_n < xd_nd_n-1/(max_n < xd_n)^2→ 0 as x→ ∞?
No claims yet Be the first →
Erdős Problem #1139
Let 1≤ u_1 < u_2 < ⋯ be the sequence of integers with at most 2 prime factors. Is it true that limsup_k → ∞ u_k+1-u_k/log k=∞?
No claims yet Be the first →
Erdős Problem #1142
Are there infinitely many n > 2 such that n - 2^k is prime for all k ≥ 1 with 2^k < n? The only known such n are 4, 7, 15, 21, 45, 75, 105 (OEIS A039669).
No claims yet Be the first →
Erdős Problem #1145
Let A=1≤ a_1 < a_2 < ⋯ and B=1≤ b_1 < b_2 < ⋯ be sets of integers with a_n/b_n→ 1. If A+B contains all sufficiently large positive integers then is it true that limsup 1_Aast 1_B(n)=∞? A conjecture of Erdős and Sárközy.
No claims yet Be the first →
Erdős Problem #1146
Is B=2^m3^n : m,n≥ 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 essential component or not; I do not even have a plausible guess."
No claims yet Be the first →
Erdős Problem #1150
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) √(n)?
No claims yet Be the first →
Erdős Problem #1159
Determine whether there exists a constant C>1 such that the following holds. Let P be a finite projective plane. Must there exist a set of points S such that 1≤ lvert S∩ ℓrvert ≤ C for all lines ℓ?
No claims yet Be the first →
Erdős Problem #1167
Erdős Problem 1167. Let r ≥ 2 be finite, γ ≥ 2, and λ be an infinite cardinal. Let κ_α > r be cardinals for all α < γ. Is it true that 2^λ → (κ_α + 1)_α < γ^r+1 implies λ → (κ_α)_α < γ^r? Here + means cardinal addition, so that κ_α + 1 = κ_α if κ_α is infinite. A problem of Erdős, Hajnal, and Rado.
No claims yet Be the first →
Erdős Problem #1175
Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).
No claims yet Be the first →
Erdős Problem #1176
Let G be a graph with chromatic number aleph_1. Is it true that there is a colouring of the edges with aleph_1 many colours such that, in any countable colouring of the vertices, there exists a vertex colour containing all edge colours? A problem of Erdős, Galvin, and Hajnal.
No claims yet Be the first →
Erdős Problem #1192
Does there exist, for all r≥ 2, a basis A of order r (so that f_r(n)>0 for all large n) such that Σ_n≤ xf_r(n)^2 ≪ x for all x?
No claims yet Be the first →
Erdős Problem #1199
Is it true that in any 2-colouring of ℕ there exists an infinite set A such that all elements of A+A are the same colour? A conjecture of Owings [Ow74].
No claims yet Be the first →
Erdős Problem #12
Let A be an infinite set such that there are no distinct a,b,c ∈ A such that a | (b+c) and b,c > a. Is it true that ∑_n ∈ A 1/n < ∞?
No claims yet Be the first →
Erdős Problem #120
Let A ⊆ ℝ be an infinite set. Must there be a set E ⊆ ℝ of positive measure which does not contain any set of the shape a * A + b for some a,b ∈ ℝ and a ≠ 0?
No claims yet Be the first →
Erdős Problem #1201
Is it true that for every ε,η>0 there exists a k such that the density of n for which P(n(n+1)⋯(n+k))>n^1-ε is at least 1-η (where P(m) is the greatest prime divisor of m)?
No claims yet Be the first →
Erdős Problem #1203
Prove that F(n)→ ∞ as n→ ∞.
No claims yet Be the first →
Erdős Problem #1206
Does 1,2^3,…,N^3 contain a Sidon set of size ≫ N?
No claims yet Be the first →
Erdős Problem #1207
Let P_d(n) be such that in any set of n points in ℝ^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 some constant c>0?
No claims yet Be the first →
Erdős Problem #1209
Are there n such that n+2^2^k is always squarefree?
No claims yet Be the first →
Erdős Problem #1210
Let A⊆ [1,n) be a set of integers such that (a,b)=1 for all distinct a,b∈ A. Is it true that Σ_a∈ A1/n-a≤ Σ_p < n1/p+O(1)?
No claims yet Be the first →
Erdős Problem #1212
Let G be the graph with vertex set those pairs (x,y)∈ ℕ^2 with gcd(x,y)=1, in which we join two vertices if the differ in only one coordinate, and there by ± 1. Is there a path going to infinity on G, say P, such that for all (x,y)∈ P both min(x,y)>1 and at least one of x or y is composite?
No claims yet Be the first →
Erdős Problem #124
Let k ≠ 0 and 3≤ d_1 < d_2 < ⋯ < d_r be integers of gcd equal to 1 such that Σ_1 ≤ i ≤ rfrac 1d_i - 1 ≥ 1. Can all sufficiently large integers be written as a sum of the shape Σ_i c_ia_i where c_i ∈ 0, 1 and a_i is divisible by d_i ^ k and has only the digits 0, 1 when written in base d_i?
No claims yet Be the first →
Erdős Problem #128
Let G be a graph with n vertices such that every induced subgraph on ≥ n/2 vertices has more than n^2/50 edges. Must G contain a triangle?
No claims yet Be the first →
Erdős Problem #137
We say that N is powerful if whenever p| N we also have p^2| N. Let k≥ 3. Can the product of any k consecutive positive integers ever be powerful?
No claims yet Be the first →
Erdős Problem #138
In [Er80] Erdős asks whether lim_k → ∞ (W(k))^1/k = ∞
No claims yet Be the first →
Erdős Problem #14
Let A ⊆ ℕ. Let B ⊆ ℕ 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 ε > 0 and large N, |1,…,N ∖ B| ≫_ε N^1/2 - ε?
No claims yet Be the first →
Erdős Problem #141
Let k≥3. Are there k consecutive primes in arithmetic progression?
No claims yet Be the first →
Erdős Problem #142
Prove an asymptotic formula for r_k(N), the largest possible size of a subset of 1, …, N that does not contain any non-trivial k-term arithmetic progression. That is, find f_k with r_k(N) / f_k(N) → 1 as N → ∞.
No claims yet Be the first →
Erdős Problem #143
Does this imply that liminf |A ∩ [1,x]|/x = 0?
No claims yet Be the first →
Erdős Problem #145
Let s_1 < s_2 < ⋯ be the sequence of squarefree numbers. Is it true that, for any α≥ 0, lim_x→∞ 1/xΣ_s_n≤ x(s_n+1-s_n)^α exists?
No claims yet Be the first →
Erdős Problem #148
Let F(k) be the number of solutions to 1= 1/n_1+⋯+1/n_k, where 1≤ n_1<⋯<n_k are distinct integers. Find good estimates for F(k).
No claims yet Be the first →
Erdős Problem #15
Is it true that Σ_n=1^∞(-1)^nn/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, …. We 0-index here to reflect how Nat.nth works.
No claims yet Be the first →
Erdős Problem #153
Let A be a finite Sidon set and A+A=s_1<⋯<s_t. Is it true that 1/tΣ_1≤ i<t(s_i+1-s_i)^2 → ∞ as lvert Arvert→ ∞?
No claims yet Be the first →
Erdős Problem #155
Is it true that for every k ≥ 1 we have F(N + k) ≤ F(N) + 1 for all sufficiently large N?
No claims yet Be the first →
Erdős Problem #156
Does there exist a maximal Sidon set A⊂ 1,…,N of size O(N^1/3)? A question of Erdős, Sárközy, and Sós [ESS94].
No claims yet Be the first →
Erdős Problem #158
Let A be an infinite B₂[2] set. Must liminf |A ∩ 1, ..., N| * N ^ (- 1 / 2) = 0?
No claims yet Be the first →
Erdős Problem #159
There exists some constant c>0 such that R(C_4,K_n) ≪ 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.
No claims yet Be the first →
Erdős Problem #160
Estimate h(n) by finding a better upper bound.
No claims yet Be the first →
Erdős Problem #168
What is the limit F(N)/N as N → ∞?
No claims yet Be the first →
Erdős Problem #17
Erdős Problem 17. Are there infinitely many cluster primes?
No claims yet Be the first →
Erdős Problem #170
The problem is to determine the limit of the sequence F(N)/√(N) as N → ∞.
No claims yet Be the first →
Erdős Problem #172
Is it true that in any finite colouring of ℕ there exist arbitrarily large finite A such that all sums and products of distinct elements in A are the same colour?
No claims yet Be the first →
Erdős Problem #18
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 h(m) < (log log m)^C?
No claims yet Be the first →
Erdős Problem #181
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) ≪ 2^n.
No claims yet Be the first →
Erdős Problem #184
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
No claims yet Be the first →
Erdős Problem #188
What is the smallest k such that ℝ^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?
No claims yet Be the first →
Erdős Problem #19
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
No claims yet Be the first →
Erdős Problem #195
What is the largest k such that in any permutation of ℤ there must exist a monotone k-term arithmetic progression x_1 < ⋯ < x_k? Here a permutation of ℤ is a one-sided arrangement a_1, a_2, a_3, … of the integers, i.e.
No claims yet Be the first →