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).
0claims
0verified
Open problems
Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
757 shown· page 4 of 16
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) → ∞?
0claims
0verified
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.
0claims
0verified
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→ ∞.
0claims
0verified
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)→ ∞?
0claims
0verified
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.
0claims
0verified
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.
0claims
0verified
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]?
0claims
0verified
Erdős Problem #104
Given n points in ℝ^2 the number of distinct unit circles containing at least three points is o(n^2).
0claims
0verified
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.
0claims
0verified
Erdős Problem #1052
Are there only finitely many unitary perfect numbers?
0claims
0verified
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)?
0claims
0verified
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?
0claims
0verified
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?
0claims
0verified
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].
0claims
0verified
Erdős Problem #1059
Are there infinitely many primes p such that p - k! is composite for each k such that 1 ≤ k! < p?
0claims
0verified
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.
0claims
0verified
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?
0claims
0verified
Erdős Problem #1062
Erdős asked whether the limiting density f n / n exists and, if so, whether it is irrational.
0claims
0verified
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.
0claims
0verified
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*
0claims
0verified
Erdős Problem #1068
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
0claims
0verified
Erdős Problem #1072
Is it true that there are infinitely many p for which f(p) = p − 1?
0claims
0verified
Erdős Problem #1073
Is it true that A(x) ≤ x^o(1)?
0claims
0verified
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?
0claims
0verified
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?
0claims
0verified
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?
0claims
0verified
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)?
0claims
0verified
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 → ∞?
0claims
0verified
Erdős Problem #1093
Are there infinitely many binomial coefficients with deficiency 1?
0claims
0verified
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.
0claims
0verified
Erdős Problem #11
Is every odd n > 1 the sum of a squarefree number and a power of 2?
0claims
0verified
Erdős Problem #1101
1. There is NO good sequence with polynomial growth.
0claims
0verified
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.
0claims
0verified
Erdős Problem #1107
Let r ≥ 2. Is every large integer the sum of at most r + 1 many r-powerful numbers?
0claims
0verified
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?
0claims
0verified
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.
0claims
0verified
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?
0claims
0verified
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.
0claims
0verified
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.
0claims
0verified
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.
0claims
0verified
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→ ∞?
0claims
0verified
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=∞?
0claims
0verified
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).
0claims
0verified
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.
0claims
0verified
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."
0claims
0verified
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)?
0claims
0verified
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 ℓ?
0claims
0verified
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.
0claims
0verified
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).
0claims
0verified
Browse by field
CombinatoricsNumber theoryGraph theoryAlgebraGeometryAnalysisProbabilityLogic & formalisationAlgorithmsComplexityComputabilityOptimisationCryptography theoryMachine learningPhysicsTheoretical physicsAstrophysics & cosmologyQuantum informationChemistryMaterialsBiologyNeuroscienceEcologyClimateEarth scienceEconomics