Erdős Problem #455
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) = ∞?
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).
Erdős Problem #456
Is it true that m_n<p_n for almost all n?
No claims yet Be the first →
Erdős Problem #458
Let lcm(1, …, n) denote the least common multiple of 1, …, n. Let p_k be the k-th prime. Is it true that for all k ≥ 1, lcm(1, …, p_k+1-1) < p_k · lcm(1, …, p_k)?
No claims yet Be the first →
Erdős Problem #462
Let p(n) denote the least prime factor of n. Is there a constant C>0 such that Σ_x≤ n≤ x+C√(x)(log x)^2p(n)/n≫ 1 for all sufficiently large x?
No claims yet Be the first →
Erdős Problem #463
Is there a function f with f(n)→∞ as n→∞ 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.
No claims yet Be the first →
Erdős Problem #470
Are there any odd weird numbers?
No claims yet Be the first →
Erdős Problem #478
Let p be a prime and A_p = k! pmodp : 1≤ k<p. Is it true that lvert A_prvert ∼ (1-1/e)p?
No claims yet Be the first →
Erdős Problem #479
Is it true that, for every integer k≠ 1, there are infinitely many n such that 2^n≡ kpmodn?
No claims yet Be the first →
Erdős Problem #488
Let A be a finite set and B= n ≥ 1 : a| ntextrm for some a∈ A. Is it true that, for every m>n≥ max(A), lvert B∩ [1,m]rvert /m< 2lvert B∩ [1,n]rvert/n?
No claims yet Be the first →
Erdős Problem #495
Let α,β ∈ ℝ. Is it true thatliminf_n→ ∞ n ‖ nα ‖ ‖ nβ‖ =0? This is also known as the Littlewood conjecture.
No claims yet Be the first →
Erdős Problem #5
Let C≥ 0. Is there an infinite sequence of n_i such that lim_i→ inftyp_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 : ℕ → ℕ.
No claims yet Be the first →
Erdős Problem #50
Let f be the asymptotic distribution function of φ(n)/n, so that for each c ∈ [0,1], f(c) is the natural density of n : φ(n) < cn. Is it true that there is no x such that the derivative f'(x) exists and is positive?
No claims yet Be the first →
Erdős Problem #501
For every x ∈ ℝ let A_x ⊂ ℝ be a bounded set with outer measure < 1. Must there exist an infinite independent set, that is, some infinite X ⊆ ℝ such that x ∉ A_y for all x ≠ y ∈ X? If the sets A_x are closed and have measure < 1, then must there exist an independent set of size 3?
No claims yet Be the first →
Erdős Problem #503
What is the size of the largest A ⊆ ℝ^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|, |y - z|, |x - z| are equal.
No claims yet Be the first →
Erdős Problem #506
Erdős Problem #506
No claims yet Be the first →
Erdős Problem #507
Let α(n) be such that every set of n points in the unit disk contains three points which determine a triangle of area at most α(n). Estimate α(n).
No claims yet Be the first →
Erdős Problem #508
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?
No claims yet Be the first →
Erdős Problem #509
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?
No claims yet Be the first →
Erdős Problem #51
Is there an infinite set A ⊂ ℕ such that for every a ∈ A, there is an integer n such that φ(n)=a, and yet if n_a is the smallest such integer, then n_a/a → ∞ as a → ∞?
No claims yet Be the first →
Erdős Problem #510
Chowla's cosine problem If A⊂ ℕ is a finite set of positive integers of size N > 0 then is there some absolute constant c>0 and θ such that Σ_n∈ Acos(nθ) < -cN^1/2?
No claims yet Be the first →
Erdős Problem #513
Let f be a transcendental entire function. What is the greatest possible value of liminf (fun r : ℝ => ratio r f) atTop?
No claims yet Be the first →
Erdős Problem #517
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?
No claims yet Be the first →
Erdős Problem #52
Let A be a finite set of integers. Is it true that for every ε>0 max( lvert A+Arvert,lvert AArvert)≫_ε lvert Arvert^2-ε?
No claims yet Be the first →
Erdős Problem #522
Let f(z)=Σ_0≤ k≤ n ε_k z^k be a random polynomial, where ε_k∈ -1,1 independently uniformly at random for 0≤ k≤ n. Is it true that, if R_n is the number of roots of f(z) in z∈ ℂ : lvert zrvert ≤ 1, then R_n/n/2→ 1 almost surely?
No claims yet Be the first →
Erdős Problem #535
Let r ≥ 3, and let f_r(N) denote the size of the largest subset of 1,…,N such that no subset of size r has the same pairwise greatest common divisor between all elements.
No claims yet Be the first →
Erdős Problem #536
Let ε>0 and N be sufficiently large. Is it true that if A⊆ 1,…,N has size at least ε N then there must be distinct a,b,c∈ A such that [a, b]=[b, c]=[a, c], where [·, ·] denotes the least common multiple?
No claims yet Be the first →
Erdős Problem #538
Let r≥ 2 and suppose that A⊆1,…,N is such that, for any m, there are at most r solutions to m=pa where p is prime and a∈ A. Give the best possible upper bound for Σ_n∈ A1/n. Erdős observed that Σ_n∈ A1/n≪ rlog N/loglog N, and the order Θ_r(log N / loglog N) is known (see erdos_538.matching_order).
No claims yet Be the first →
Erdős Problem #539
Let h(n) be maximal such that, for any set A⊆ ℕ of size n, the set a/(a,b): a,b∈ Ahas size at least h(n). Estimate h(n).
No claims yet Be the first →
Erdős Problem #544
Show that R(3,k+1)-R(3,k)→∞ as k→ ∞. A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #545
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'?
No claims yet Be the first →
Erdős Problem #551
Prove that R(C_k,K_n)=(k-1)(n-1)+1 for k≥ n≥ 3 (except when n=k=3). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #552
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.
No claims yet Be the first →
Erdős Problem #562
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 complete r-uniform hypergraph on n vertices.
No claims yet Be the first →
Erdős Problem #563
Let F(n,α) denote the smallest m such that there exists a 2-colouring of the edges of K_n so that every X⊆ [n] with lvert Xrvert≥ m contains more than α C(lvert Xrvert, 2) many edges of each colour. Prove that, for every 0≤ α < 1/2, F(n,α)∼ c_αlog n for some constant c_α depending only on α.
No claims yet Be the first →
Erdős Problem #564
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 constant c>0 such that R_3(n) ≥ 2^2^cn?
No claims yet Be the first →
Erdős Problem #566
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) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?
No claims yet Be the first →
Erdős Problem #567
Erdős Problem 567 (Q3) Is Q_3 (the 3-dimensional hypercube) Ramsey size linear?
No claims yet Be the first →
Erdős Problem #568
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m? In other words, is G Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #569
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ 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.
No claims yet Be the first →
Erdős Problem #572
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #579
Let δ > 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 δ n^2 edges, must G contain an independent set of size ≫_δ n? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83].
No claims yet Be the first →
Erdős Problem #583
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
No claims yet Be the first →
Erdős Problem #592
Determine which countable ordinals β have the property that, if α = ω^β, then in any red/blue colouring of the edges of K_α there is either a red K_α or a blue K_3.
No claims yet Be the first →
Erdős Problem #593
Erdős Problem 593 (\500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number > aleph_0. The answer is the set of obligatory finite 3-uniform hypergraphs, represented here on the labelled vertex sets Fin n.
No claims yet Be the first →
Erdős Problem #595
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].
No claims yet Be the first →
Erdős Problem #596
Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G_1, G_2) is it true that (1) for every n ≥ 1 there is a graph H without a G_1 such that any n-colouring of H's edges contains a monochromatic G_2, and yet (2) for every graph H without a G_1 there is an aleph_0-colouring of H's edges…
No claims yet Be the first →
Erdős Problem #598
Erdős Problem 598: Let m be an infinite cardinal and κ be the successor cardinal of 2^aleph_0. Can one colour the countable subsets of m using κ many colours so that every X ⊆ m with |X| = κ contains subsets of all possible colours?
No claims yet Be the first →
Erdős Problem #60
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
No claims yet Be the first →
Erdős Problem #600
Let r ≥ 2. Is it true that e(n,r+1) - e(n,r) → ∞ as n → ∞?
No claims yet Be the first →
Erdős Problem #602
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 ≠ j, the intersection A_i ∩ A_j is finite and |A_i ∩ A_j| ≠ 1.
No claims yet Be the first →
Erdős Problem #609
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).
No claims yet Be the first →
Erdős Problem #61
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.
No claims yet Be the first →
Erdős Problem #617
Let r≥ 3. If the edges of K_r^2+1 are r-coloured then there exist r+1 vertices with at least one colour missing on the edges of the induced K_r+1. In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99].
No claims yet Be the first →
Erdős Problem #623
Let X be a set of cardinality aleph_ω and f be a function from the finite subsets of X to X such that f(A)not∈ A for all A. Must there exist an infinite Y⊆ X that is independent - that is, for all finite B⊂ Y we have f(B)not∈ Y?
No claims yet Be the first →
Erdős Problem #624
Let X be a finite set of size n and H(n) be such that there is a function f:A : A⊆ X→ X so that for every Y⊆ X with lvert Yrvert ≥ H(n) we have f(A) : A⊆ Y=X. Prove that H(n)-log_2 n → ∞.
No claims yet Be the first →
Erdős Problem #628
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
No claims yet Be the first →
Erdős Problem #64
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
No claims yet Be the first →
Erdős Problem #647
Let τ(n) count the number of divisors of n. Is there some n > 24 such that max_m < n(m + τ(m)) ≤ n + 2?
No claims yet Be the first →
Erdős Problem #65
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #653
Let x_1,…,x_n∈ ℝ^2 and let R(x_i)=\# lvert x_j-x_irvert : j≠ i, where the points are ordered such that R(x_1)≤ ⋯ ≤ R(x_n). Let g(n) be the maximum number of distinct values the R(x_i) can take. Is it true that g(n) ≥ (1-o(1))n?
No claims yet Be the first →
Erdős Problem #66
Is there and A ⊂ ℕ is such that lim_n→ ∞1_Aast 1_A(n)/log n exists and is ≠ 0?
No claims yet Be the first →
Erdős Problem #660
Let x_1, …, x_n ∈ ℝ^3 be the vertices of a convex polyhedron. Are there at least (1 - o(1)) n/2 many distinct distances between the x_i?
No claims yet Be the first →
Erdős Problem #672
Can the product of an arithmetic progression of positive integers n, n + d, ..., n + (k - 1)d of length k ≥ 4, with (n, d) = 1, be a perfect power? Erdős believed not, i.e. that Erdos672With k l holds for all k ≥ 4 and l > 1.
No claims yet Be the first →
Erdős Problem #677
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 ≥ n + k, we get M(m, k) ≠ M(n, k)?
No claims yet Be the first →
Erdős Problem #68
Is Σ_n=2^∞ 1/n!-1 irrational?
No claims yet Be the first →
Erdős Problem #680
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?
No claims yet Be the first →
Erdős Problem #681
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 ?
No claims yet Be the first →
Erdős Problem #683
Let P(n, k) be the largest prime factor of C(n, k). There exists c > 0 such that P(n, k) ≥ min(n - k + 1, k^1 + c) for all 0 < k ≤ n/2. Erdős stated this for 1 ≤ k ≤ n with the bound min(n-k+1, k^1+c) [Er79d].
No claims yet Be the first →
Erdős Problem #686
Can every integer N≥2 be written as N=Π_1≤ i≤ k(m+i)/Π_1≤ i≤ k(n+i) for some k≥2 and m≥n+k?
No claims yet Be the first →
Erdős Problem #688
Estimate ε_n.
No claims yet Be the first →
Erdős Problem #689
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)?
No claims yet Be the first →
Erdős Problem #695
Let q_1 < q_2 < ⋯ be a sequence of primes such that q_i + 1 ≡ 1 pmodq_i. Is it true that lim_k → ∞ q_k^1/k = ∞?
No claims yet Be the first →
Erdős Problem #699
Erdős Problem 699. Is it true that for every 1 ≤ i < j ≤ n / 2 there exists a prime p ≥ i with p | gcd(C(n, i), C(n, j))?
No claims yet Be the first →
Erdős Problem #7
Is there a covering system all of whose moduli are odd (and greater than 1)?
No claims yet Be the first →
Erdős Problem #70
Erdős Problem 70: Let c be the order type of the real numbers, let β be a countable ordinal, and let 2 ≤ n < ω. Is it true that c → (β, n)^3_2? Note: The cases n ≤ 3 are trivially true (compare omega_three), so the genuine content of the conjecture begins at n = 4.
No claims yet Be the first →
Erdős Problem #700
Let f(n) = min_1 < k ≤ n/2 gcd(n, C(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) when n is a product of two primes (erdos_700.variants.prime_mul), with n = 30 a further example.
No claims yet Be the first →
Erdős Problem #701
Let F be a family of sets closed under taking subsets (i.e. if B⊆ AinF then B∈ F). There exists some element x such that whenever F'⊆ F is an intersecting subfamily we have lvert F'rvert ≤ lvert A∈ F : x∈ Arvert.
No claims yet Be the first →
Erdős Problem #713
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)∼ cn^α? The condition that G have at least two edges excludes degenerate forbidden graphs whose extremal number is eventually zero, for which the displayed asymptotic with c>0 is impossible.
No claims yet Be the first →
Erdős Problem #714
Is it true that ex(n; K_r,r) ≫ n^2-1/r?
No claims yet Be the first →
Erdős Problem #723
If there is a finite projective plane of order n then must n be a prime power?
No claims yet Be the first →
Erdős Problem #726
As n→ ∞ ranges over integers Σ_p≤ n1_n∈ (p/2,p)pmodp1/p∼ loglog n/2? A conjecture of Erdős, Graham, Ruzsa, and Straus [EGRS75]. By n∈ (p/2,p)pmodp we mean n≡ rpmodp for some integer r with p/2<r<p. The remainder n % p is computed in ℕ before casting to ℝ.
No claims yet Be the first →
Erdős Problem #727
Let k ≥ 2. Does ((n+k)!)^2∣(2n)! hold for infinitely many n?
No claims yet Be the first →
Erdős Problem #740
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
No claims yet Be the first →
Erdős Problem #742
Murty-Simon Conjecture Let G be a graph on n vertices with diameter 2 such that deleting any edge increases the diameter. Is it true that G has at most ⌊ n^2 / 4 ⌋ edges? Equality is conjectured to hold for the complete balanced bipartite graph K_⌈ n/2 ⌉, ⌊ n/2 ⌋.
No claims yet Be the first →
Erdős Problem #749
Let ε>0. Does there exist A⊆ ℕ such that the lower density of A+A is at least 1-ε and yet 1_Aast 1_A(n) ≪_ε 1 for all n?
No claims yet Be the first →
Erdős Problem #75
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 - ε)?
No claims yet Be the first →
Erdős Problem #757
What is the supremum of the set of admissible numbers?
No claims yet Be the first →
Erdős Problem #77
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→ inftyR(k)^1/k. This problem is #3 in Ramsey Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #770
For every prime p, does the density of integers with h n = p exist?
No claims yet Be the first →
Erdős Problem #773
What is the size of the largest Sidon subset A⊆1,2^2,…,N^2? Is it N^1-o(1)?
No claims yet Be the first →
Erdős Problem #774
Is every proportionately dissociated (infinite) set the union of a finite number of dissociated sets?
No claims yet Be the first →
Erdős Problem #779
Erdős Problem #779
No claims yet Be the first →
Erdős Problem #78
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.
No claims yet Be the first →
Erdős Problem #786
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?
No claims yet Be the first →
Erdős Problem #789
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).
No claims yet Be the first →
Erdős Problem #80
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 shared by at least m different triangles. Estimate f_c(n).
No claims yet Be the first →
Erdős Problem #812
Is it true that R(n+1)/R(n)≥ 1+c for some constant c>0, for all large n?
No claims yet Be the first →
Erdős Problem #817
Erdős Problem #817
No claims yet Be the first →
Erdős Problem #82
F(n) / log n → ∞ as n → ∞
No claims yet Be the first →
Erdős Problem #821
Is it true that, for every ε>0, there exist infinitely many n such that g(n) > n^1-ε?
No claims yet Be the first →