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 →
Formal Conjectures: open problems with Lean statements
Formal Conjectures is an open repository, started by Google DeepMind, of conjectures stated in Lean 4 with Mathlib. Every open problem from it that we import keeps its exact Lean statement, so a proof submitted here is checked by the Lean kernel against that statement. The collection covers Erdős problems, OEIS conjectures, Ben Green's open problems, Wikipedia's lists of unsolved problems, MathOverflow questions and more.
Source: google-deepmind/formal-conjectures. Licence: Apache License 2.0.
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 →
Erdős Problem #826
Are there infinitely many n such that, for all k≥ 1 τ(n + k) ≪ k?
No claims yet Be the first →
Erdős Problem #828
Is it true that, for any a ∈ ℤ, there are infinitely many n such that φ(n) | n + a?
No claims yet Be the first →
Erdős Problem #829
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 → ∞?
No claims yet Be the first →
Erdős Problem #830
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?
No claims yet Be the first →
Erdős Problem #835
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?
No claims yet Be the first →
Erdős Problem #839
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 = ∞?
No claims yet Be the first →
Erdős Problem #849
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?
No claims yet Be the first →
Erdős Problem #85
Is it true that, for all large n, f(n + 1) ≥ f(n)?
No claims yet Be the first →
Erdős Problem #850
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?
No claims yet Be the first →
Erdős Problem #853
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) → ∞?
No claims yet Be the first →
Erdős Problem #855
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.
No claims yet Be the first →
Erdős Problem #857
Estimate m(n,k), or better give an asymptotic formula.
No claims yet Be the first →
Erdős Problem #859
The density of the divisor sum set is asymptotically equivalent to c_1 / log(t)^c_2.
No claims yet Be the first →
Erdős Problem #86
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?
No claims yet Be the first →
Erdős Problem #87
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.
No claims yet Be the first →
Erdős Problem #872
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.
No claims yet Be the first →
Erdős Problem #873
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^ε?
No claims yet Be the first →
Erdős Problem #881
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?
No claims yet Be the first →
Erdős Problem #883
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].
No claims yet Be the first →
Erdős Problem #885
Is it true that, for every k ≥ 1, there exist integers N_1 < … < N_k such that |∩_i D(N_i)| ≥ k?
No claims yet Be the first →
Erdős Problem #886
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.
No claims yet Be the first →
Erdős Problem #887
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).
No claims yet Be the first →
Erdős Problem #889
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→ ∞?
No claims yet Be the first →
Erdős Problem #89
Erdős [Er46] asked whether every set of n distinct points in ℝ^2 determines ≫ n/√(log n) many distinct distances.
No claims yet Be the first →
Erdős Problem #890
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?
No claims yet Be the first →
Erdős Problem #891
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?
No claims yet Be the first →
Erdős Problem #893
Does the limit lim_n→∞ f(2n)/f(n) tend to infinity? (Other finite limits have been ruled out by [KoLu25], see below)
No claims yet Be the first →
Erdős Problem #9
Is the upper density of the set of odd numbers that cannot be expressed as a prime plus two powers of 2 positive?
No claims yet Be the first →
Erdős Problem #906
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.
No claims yet Be the first →
Erdős Problem #91
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.
No claims yet Be the first →
Erdős Problem #912
Prove that there exists some c>0 such that h(n) ∼ c (n/log n)^1/2 as n→ ∞.
No claims yet Be the first →
Erdős Problem #913
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?
No claims yet Be the first →
Erdős Problem #918
Erdős Problem #918
No claims yet Be the first →
Erdős Problem #930
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?
No claims yet Be the first →
Erdős Problem #931
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?
No claims yet Be the first →
Erdős Problem #932
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.
No claims yet Be the first →
Erdős Problem #933
If n(n+1)=2^k3^lm, where (m,6)=1, then is it true that limsup_n→ ∞ 2^k3^l/nlog n=∞?
No claims yet Be the first →
Erdős Problem #938
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?
No claims yet Be the first →
Erdős Problem #939
If r≥4 then can the sum of r-2 coprime r-powerful numbers ever be itself r-powerful?
No claims yet Be the first →
Erdős Problem #940
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?
No claims yet Be the first →
Erdős Problem #942
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).
No claims yet Be the first →
Erdős Problem #943
Let A be the set of powerful numbers. Is is true that 1_Aast 1_A(n)=n^o(1) for every n?
No claims yet Be the first →
Erdős Problem #944
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?
No claims yet Be the first →
Erdős Problem #945
Is it true that F(x) ≤ (log x)^O(1)?
No claims yet Be the first →
Erdős Problem #949
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?
No claims yet Be the first →
Erdős Problem #950
Is it true that liminf f(n)=1?
No claims yet Be the first →
Erdős Problem #951
If 1 < a 0 < ... has property Erdos951Prop, is it true that #a i ≤ x ≤ π x?
No claims yet Be the first →
Erdős Problem #952
Is there an infinite sequence of distinct Gaussian primes x_1,x_2,… such that lvert x_n+1-x_nrvert ≪ 1?
No claims yet Be the first →
Erdős Problem #955
If A⊂ ℕ has density 0 then s^-1(A) must also have density 0. A conjecture of Erdős, Granville, Pomerance, and Spiro [EGPS90].
No claims yet Be the first →
Erdős Problem #959
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).
No claims yet Be the first →
Erdős Problem #96
If n points in ℝ^2 form a convex polygon then there are O(n) many pairs which are distance 1 apart.
No claims yet Be the first →
Erdős Problem #961
It is conjectured that f(k) ≪ (log k)^O(1).
No claims yet Be the first →
Erdős Problem #962
Main conjecture: log k(n) ≤ (log n)^(1/2 + o(1))
No claims yet Be the first →
Erdős Problem #968
Does the set n | u n < u (n+1) have positive lower density?
No claims yet Be the first →
Erdős Problem #97
Does every convex polygon have a vertex with no other 4 vertices equidistant from it?
No claims yet Be the first →
Erdős Problem #970
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?
No claims yet Be the first →
Erdős Problem #971
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?
No claims yet Be the first →
Erdős Problem #972
Erdős problem 972. Let α > 1 be irrational. Are there infinitely many primes p such that ⌊ pα ⌋ is also prime?
No claims yet Be the first →
Erdős Problem #975
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.
No claims yet Be the first →
Erdős Problem #978
If k>3 (and k ≠ 2^l), and for all primes p there exists n such that p^k-2nmid f(n), then are there infinitely many n for which f(n) is (k-2)-power-free?
No claims yet Be the first →
Erdős Problem #979
Let k ≥ 2, and let f_k(n) count the number of solutions to n = p_1^k + … + p_k^k, where the p_i are prime numbers. Is it true that limsup f_k(n) = ∞?
No claims yet Be the first →