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).
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 set of size ≥ c log n, for some constant c > 0.
Do the squares contain arbitrarily long quasi-progressions? That is, does there exist some constant C>0 such that, for any k, the squares contain a sequence x_1,…,x_k where, for some d and all 1≤ i<k, x_i+d≤ x_i+1≤ x_i+d+C. A question of Brown, Erdős, and Freedman [BEF90].
Let ε > 0. Is there some set A⊂ℕ of density > 1 - ε such that a_1⋯ a_r = b_1⋯ b_s with a_i, b_j∈ A can only hold when r = s?
Let g(n) be maximal such that given any set A⊂ ℝ with lvert Arvert=n there exists some B⊆ A of size lvert Brvert≥ g(n) such that b_1+b_2not∈ A for all b_1≠ b_2∈ B. Estimate g(n).
Let h(n) be maximal such that if A⊆ ℤ with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+⋯+a_r=b_1+⋯+b_s with a_i,b_i∈ B then r=s. Estimate h(n).
The weaker question from the same problem: is f_c(n) ≫ log n? Same feasibility bound on c as above.
Is it true that any K_r-free graph on n vertices with average degree t contains an independent set on ≫_r log t/tn many vertices? A conjecture of Ajtai, Erdős, Komlós, and Szemerédi [AEKS81].
For which functions g(n) with n>g(n)≥ (log n)^2 is there a graph on n vertices in which every induced subgraph on g(n) vertices contains a clique of size ≥ log n and an independent set of size ≥ log n? In particular, is there such a graph for g(n)=(log n)^3? This is the first part.
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?
Does there exist some ε>0 such that, for all sufficiently large n, there exists a graph G on n vertices with at least ε n^2 edges whose edges can be coloured with n colours so that every C_4 receives four distinct colours?
Is it true that R(n+1)/R(n)≥ 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 c_1, c_2 > 0 such that n^1/3+c_1 ≪ h(n) ≪ n^1/2-c_2?
Erdős Problem #817
Let f(N) be maximal such that there exists A⊆ 1,…,N with lvert Arvert=⌊ N^1/2⌋ such that lvert (A+A)∩ [1,N]rvert=f(N). Estimate f(N).
F(n) / log n → ∞ as 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 Erdos820.H_eq_three_iff)?
Is it true that, for every ε>0, there exist infinitely many n such that g(n) > n^1-ε?
Are there infinitely many n such that, for all k≥ 1 τ(n + k) ≪ k?
Let n_k be minimal such that if n_k points in ℝ^2 are in general position then there exists a subset of k points such that all C(k, 3) triples determine circles of different radii. Determine n_k.
Is it true that, for any a ∈ ℤ, there are infinitely many n such that φ(n) | n + a?
Erdős Problem 829 (open). Let A ⊆ ℕ be the set of perfect cubes. Is it true that (1_A ast 1_A)(n) ≪ (log n)^O(1)? That is, does there exist a natural number C such that the number of representations of n as a sum of two cubes is O((log n)^C) as n → ∞?
Erdos Problem 830, Part 1 We say that a,b∈ ℕ are an amicable pair if σ(a)=σ(b)=a+b. Are there infinitely many amicable pairs?
Let h(n) be maximal such that in any n points in ℝ^2 (with no three on a line and no four on a circle) there are at least h(n) many circles of different radii passing through three points. Estimate h(n). Erdős asks this in [Er75h, pp. 2-3] (see also [Er92e]); see also Problems 104 and 506.
Does there exist a k>2 such that the k-sized subsets of 1,...,2k can be coloured with k+1 colours such that for every A⊂ 1,…,2k with lvert Arvert=k+1 all k+1 colours appear among the k-sized subsets of A?
Let k≥ 2 and A_k⊆ [0,1] be the set of α such that there exists some β(α)>α with the property that, if G_1,G_2,… is a sequence of k-uniform hypergraphs with liminf e(G_n)/C(lvert G_nrvert, k) >α then there exist subgraphs H_n⊆ G_n such that lvert H_nrvert → ∞ and liminf e(H_n)/C(lvert H_nrvert, k)…
Let f(n) be maximal such that any n points in ℝ^2, with no three on a line, determine at least f(n) different convex subsets. Estimate f(n) - in particular, does there exist a constant c such that lim log f(n)/(log n)^2=c? A question of Erdős and Hammer [Er78c, pp. 52-53]. This is the first part.
Erdős Problem 839 (Part 1) [Er78f][Er92c]: Let 1 ≤ a_1 < a_2 < ⋯ 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 limsup a_n / n = ∞?
Let f(N) be the size of the largest quasi-Sidon subset A⊂1,…,N, where we say that A is quasi-Sidon if lvert A+Arvert=(1+o(1))C(lvert Arvert, 2). How does f(N) grow? Following [Er81h, p.
Is it true that, for every integer t≥1, there is some integer a such that n choose k = a with 1≤ k ≤ n/2 has exactly t solutions?
Is it true that, for all large n, f(n + 1) ≥ f(n)?
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 nth prime. Let h(x) be maximal such that for some n < x the numbers d_n, d_n+1, …, d_n+h(x)-1 are all distinct [Er85c]. Estimate h(x). In particular, is it true that h(x) > (log x)^c for some constant c > 0? The statement avoids defining h.
Let d_n = p_n+1 - p_n, where p_n is the nth prime. Let r(x) be the smallest even integer t such that d_n = t has no solutions for n ≤ x. Is it true that r(x) → ∞?
Let n_k denote the kth primorial, i.e. the product of the first k primes. If 1=a_1<a_2<⋯ <a_φ(n_k)=n_k-1 is the sequence of integers coprime to n_k, then estimate the smallest even integer not of the form a_i+1-a_i. Are there ≫ max_i (a_i+1-a_i) many even integers of the form a_j+1-a_j?
Erdős Problem 855 (Segal's conjecture): π(x + y) ≤ π(x) + π(y) for all sufficiently large x, y, i.e. for all x, y ≥ N for some N.
Let k≥ 3 and f_k(N) be the maximum value of Σ_n∈ A1/n, where A ranges over all subsets of 1,…,N which contain no subset of size k with the same pairwise least common multiple. Estimate f_k(N). This is the question of Erdős [Er70, p. 127].
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 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 ≥ (1/2+o(1))n2^n-1 many edges contains a C_4?
Let h(n) be such that, for any m≥ 1, in the interval (m,m+h(n)) there exist distinct integers a_i for 1≤ i≤ π(n) such that p_i| a_i, where p_i denotes the ith prime. Estimate h(n).
Let A⊆ 1,…,N be a set such that there exists at most one n with more than one solution to n=a+b (with a≤ b∈ A). Estimate the maximal possible size of |A|. In particular, is it true that |A| ≤ (1+o(1))2/√(3) N^1/2? A problem of Erdős and Freud [ErFr91] [Er92c].
Let 0 < ε < 1. Is it true that, if k is sufficiently large, then R(G) > (1-ε)^k R(k) for every graph G with chromatic number χ(G)=k? The restriction ε < 1 excludes negative bases in (1-ε)^k. This problem is #12 in Ramsey Theory in the graphs problem collection.
Erdős Problem 872, part (i) (weak form): there exists a constant ε > 0 such that the game length is at least ε · n for all sufficiently large n.
Let A = a_1 < a_2 < … ⊆ ℕ and let F(A,X,k) count the number of i such that [a_i,a_i+1, … ,a_i+k−1] < X, where the left-hand side is the least common multiple. Is it true that, for every ε > 0, there exists some k such that F(A,X,k) < X^ε?
Let A=a_1<a_2<⋯⊂ ℕ be an infinite set such that the sets S_r = a_1+⋯ +a_r : a_1<⋯<a_r∈ A are disjoint for distinct r≥ 1. How fast can such a sequence grow? How small can a_n+1-a_n be? In particular, for which c is it possible that a_n+1-a_n≤ n^c?
Let A=a_1<a_2<⋯⊂ ℕ be an infinite sum-free set - that is, there are no solutions to a=b_1+⋯+b_r with b_1<⋯<b_r<a∈ A. How small can a_n+1-a_n be? Is it possible that a_n+1-a_n<n? The gap question is discussed by Erdős in [Er98]. We state the second question.
Find an asymptotic formula for the number of n<x such that f(n)=F(n).
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⊆ 1,…,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| > ⌊ n/2 ⌋ + ⌊ n/3 ⌋ - ⌊ n/6 ⌋ then G(A) contains all odd cycles of length ≤ n/3 + 1? A problem of Erdős and Sárközy [ErSa97].
Is it true that, for every k ≥ 1, there exist integers N_1 < … < N_k such that |∩_i D(N_i)| ≥ k?
Let ε>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-ε) is O_ε(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^1/2, n^1/2 + C n^1/4).
Let v(n,k) count the prime factors of n+k which do not divide n+i for 0≤ i < k. Is it true that v_0(n)=max_k≥ 0v(n,k)→ ∞ as n→ ∞?
Erdős [Er46] asked whether every set of n distinct points in ℝ^2 determines ≫ n/√(log n) many distinct distances.
If ω_k(n) counts the number of distinct prime factors of n which are >k, then is it true that, for every k≥ 1, liminf_n→ ∞Σ_0≤ i < kω_k(n+i)≤ k?
Let 2=p_1 < p_2 < ⋯ be the primes and k≥ 2. Is it true that, for all sufficiently large n, there must exist an integer in [n,n+p_1⋯ p_k) with >k many prime factors?
Does the limit lim_n→∞ f(2n)/f(n) tend to infinity? (Other finite limits have been ruled out by [KoLu25], see below)
Is the upper density of the set of odd numbers that cannot be expressed as a prime plus two powers of 2 positive?
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.
Suppose A⊂ ℝ^2 has lvert Arvert=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.
Let hatR(G) denote the size Ramsey number, the minimal number of edges m such that there is a graph H with m edges that is Ramsey for G. Is there a function f such that f(x)/x→ ∞ as x→ ∞ such that, for all large C, if G is a graph with n vertices and e≥ Cn edges then hatR(G) > f(C) e?
Prove that there exists some c>0 such that h(n) ∼ c (n/log n)^1/2 as n→ ∞.
Are there infinitely many n such that if n(n + 1) = Π_i p_i^k_i is the factorisation into distinct primes then all exponents k_i are distinct?
Let k≥ 4 and f_k(n) be the largest number of edges in a graph on n vertices which has chromatic number k and is critical (i.e. deleting any edge reduces the chromatic number). Is it true that f_6(n)∼ n^2/4? This is the second part.
Erdős Problem #918
Let k≥ 2 be large and let S(k) be the minimal x such that there is a positive density set of n where n+1,n+2,…,n+k are all divisible by primes ≤ x. Estimate S(k) - in particular, is it true that S(k)≥ k^1-o(1)? A problem of Erdős [Er76d, p. 26]. This is the first part.
Is it true that, for every r, there is a k such that if I_1,…,I_r are disjoint intervals of consecutive integers, all of length at least k, then Π_1≤ i≤ rΠ_m∈ I_im is not a perfect power?
Let k_1 ≥ k_2 ≥ 3. Are there only finitely many n_2≥ n_1 + k_1 such that Π_1≤ i≤ k_1(n_1 + i) and Π_1≤ j≤ k_2 (n_2 + j) have the same prime factors?
Let p_k denote the kth 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→ ∞ 2^k3^l/nlog n=∞?
Let h_t(d) be minimal such that every graph G with h_t(d) edges and maximal degree ≤ d contains two edges whose shortest path between them has length ≥ t. Estimate h_t(d). A problem of Erdős and Nešetřil [Er88].
For any integer n=Π p^k_p let Q_2(n) be the powerful part of n, so that Q_2(n) = Π_substackp\ k_p≥ 2p^k_p. Is it true that, for every ε>0 and ℓ≥ 1, if n is sufficiently large then Q_2(n(n+1)⋯(n+ℓ))<n^2+ε? A problem of Erdős [Er76d, p.
Let A=n_1 < n_2 < ⋯ be the sequence of powerful numbers (if p| n then p^2| 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 ≥ 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_Aast 1_A(n)=n^o(1) for every n?
Let k ≥ 4 and r≥ 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) ≤ (log x)^O(1)?
Let S ⊆ ℝ be a set containing no solutions to a + b = c. Must there be a set A ⊆ ℝ ∖ S of cardinality continuum such that A + A ⊆ ℝ∖ S?
Is it true that liminf f(n)=1?
If 1 < a 0 < ... has property Erdos951Prop, is it true that #a i ≤ x ≤ π x?
Is there an infinite sequence of distinct Gaussian primes x_1,x_2,… such that lvert x_n+1-x_nrvert ≪ 1?
Let 0=a_0<a_1<a_2<⋯ be the sequence of integers defined by a_0=0 and a_1=1, and a_k+1 is the smallest integer n for which the number of solutions to a_i+a_j ≤ n (with 0≤ i≤ j≤ k and j≥ 1) is <n. Is the number of solutions to a_i+a_j ≤ x equal to x+O(x^1/4+o(1))?
If A⊂ ℕ has density 0 then s^-1(A) must also have density 0. A conjecture of Erdős, Granville, Pomerance, and Spiro [EGPS90].
Let A⊆ ℝ^2 be a set of size n and let d_1,…,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 f(d_1)≥ f(d_2)≥ ⋯ ≥ f(d_k).
If n points in ℝ^2 form a convex polygon then there are O(n) many pairs which are distance 1 apart.
It is conjectured that f(k) ≪ (log k)^O(1).
Main conjecture: log k(n) ≤ (log n)^(1/2 + o(1))
Let f(n) be the maximal k such that in any set A⊂ ℝ of size n there is a subset B⊆ A of size lvert Brvert≥ k which is dissociated that is, the sums Σ_b∈ Sb are distinct for all S⊆ B. Estimate f(n) - in particular, is it true that f(n)≥ ⌊ log_2 n⌋?
Does the set n | u n < u (n+1) have positive lower density?
Let Q(x) count the squarefree integers in [1,x], and define E(x) by Q(x)=6/π^2x+E(x). Determine the order of magnitude of E(x): an upper bound E(x)=O(g(x)) with a matching oscillation bound E(x)≠ o(g(x)).
Does every convex polygon have a vertex with no other 4 vertices equidistant from it?
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 magnitude of h(k). In particular, is it true that h(k) ≪ k^2?
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 α > 1 be irrational. Are there infinitely many primes p such that ⌊ pα ⌋ is also prime?
For an irreducible polynomial f ∈ ℤ[x] with f(n) ≥ 1 for sufficiently large n, does there exists a constant c = c(f) > 0 such that Σ_n ≤ x τ(f(n)) ≈ c · x log x? Note that it is unclear whether the polynomial should have integer coefficients or merely be integer-valued. We assume the former.
Let f∈ ℤ[x] be an irreducible polynomial of degree d≥ 2. Let F_f(n) be maximal such that there exists 1≤ m≤ n with f(m) is divisible by a prime ≥ F_f(n). Equivalently, F_f(n) is the greatest prime divisor of Π_1≤ m≤ nf(m). Estimate F_f(n).
