Ben Green's Open Problem 37
Given a natural number N, what is the smallest size of a subset of ℕ that contains, for each d = 1, …, N, an arithmetic progression of length k with common difference d.
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.
All fields Mathematics 936Computer science 28Physics & astronomy 22Chemistry & materials 13Life sciences 6Earth & society 6
Combinatorics 158Number theory 500Graph theory 71Algebra 45Geometry 72Analysis 69Probability 11Logic & formalisation 10
158 shown· page 2 of 4
Ben Green's Open Problem 40
Does f(r) → ∞? [Gr24]
0claims
0verified
Ben Green's Open Problem 5
Which finite groups have the smallest biggest product-free sets? We formalise this as: determine the supremum of exponents α such that every nontrivial finite group of order n contains a product-free set of size ≥ c n^α for some absolute constant c > 0.
0claims
0verified
Ben Green's Open Problem 50
Let A ⊂ 𝔽_2^n be a set of density α > 0. Does 10A contain a coset of some subspace of dimension at least n - O(log(1/α))?
0claims
0verified
Ben Green's Open Problem 58
Suppose A, B ⊆ 1, …, N both have size at least N^0.49. Must the sumset A + B contain a composite number?
0claims
0verified
Ben Green's Open Problem 72
The no-k-in-line problem: For which k > 2 does every N × N grid with N ≥ k contain a set of (k - 1) N points with no k on a line, so that AllowedSetSize k N is the pigeonhole bound (k - 1) N?
0claims
0verified
Ben Green's Open Problem 77
Given n points in the unit disc, must there be a triangle of area at most n^-2+o(1) determined by them?
0claims
0verified
Chvátal's Conjecture
If F is a decreasing family of sets of some finite type α, then there is some element x of α such that the family consisting of all members of F containing x is an intersecting subfamily of F with maximal cardinality.
0claims
0verified
Conjectures about Latin Squares
Conjecture 3.2 in [Wa2011]: Each Latin square of odd order has at least one transversal.
0claims
0verified
Dedekind Numbers
No closed-form expression that allows efficient computation of Dedekind numbers is currently known.
0claims
0verified
Digit 2 in base 3 representation of 2^n
For n > 8, 2^n is not the the sum of distinct powers of 3. Expressed here in terms of the base 3 digits of n. This conjecture is equivalent to the halting of a 15-state 2-symbol Turing Machine. TODO(lezeau): Formalize the Turing Machine version of this problem.
0claims
0verified
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?
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 #1093
Are there infinitely many binomial coefficients with deficiency 1?
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 #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 #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 #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?
0claims
0verified
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].
0claims
0verified
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?
0claims
0verified
Erdős Problem #1206
Does 1,2^3,…,N^3 contain a Sidon set of size ≫ N?
0claims
0verified
Erdős Problem #141
Let k≥3. Are there k consecutive primes in arithmetic progression?
0claims
0verified
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→ ∞?
0claims
0verified
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?
0claims
0verified
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].
0claims
0verified
Erdős Problem #158
Let A be an infinite B₂[2] set. Must liminf |A ∩ 1, ..., N| * N ^ (- 1 / 2) = 0?
0claims
0verified
Erdős Problem #160
Estimate h(n) by finding a better upper bound.
0claims
0verified
Erdős Problem #170
The problem is to determine the limit of the sequence F(N)/√(N) as N → ∞.
0claims
0verified
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?
0claims
0verified
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.
0claims
0verified
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?
0claims
0verified
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.
0claims
0verified
Erdős Problem #196
Must every permutation of ℕ, contain a monotone 4-term arithmetic progression?
0claims
0verified
Erdős Problem #197
Can ℕ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?
0claims
0verified
Erdős Problem #200
Does the longest arithmetic progression of primes in 1,…,N have length o(log N)?
0claims
0verified
Erdős Problem #203
Is there an integer m with (m, 6) = 1 such that none of 2^k · 3^ℓ · m + 1 are prime, for any k, ℓ ≥ 0?
0claims
0verified
Erdős Problem #236
Let f(n) count the number of solutions to n=p+2^k for prime p and k≥ 0. Show that f(n)=o(log n).
0claims
0verified
Erdős Problem #241
Is it true that f(N)∼ N^1/3? Originally asked to Erdős by Bose. This is discussed in problem C11 of Guy's collection [Gu04].
0claims
0verified
Erdős Problem #272
Let N≥ 1. What is the largest t such that there are A_1,…,A_t⊆ 1,…,N with A_i∩ A_j a non-empty arithmetic progression for all i≠ j?
0claims
0verified
Erdős Problem #273
Is there a covering system all of whose moduli are of the form p-1 for some primes p ≥ 5?
0claims
0verified
Erdős Problem #282
Let A⊆ ℕ be an infinite set and consider the following greedy algorithm for a rational x∈ (0,1): choose the minimal n∈ A not used so far such that n≥ 1/x and repeat with x replaced by x-1/n.
0claims
0verified
Erdős Problem #295
Let k(N) denote the smallest k such that there exists N ≤ n_1 < ⋯ < n_k with frac 1 n_1 + ... + frac 1 n_k = 1 Is it true that lim_N → ∞ k(N) - (e - 1)N = ∞?
0claims
0verified
Erdős Problem #312
Does there exist a constant c > 0 such that, for any K > 1, whenever A is a sufficiently large finite multiset of integers with Σ_n ∈ A 1/n > K there exists some S ⊆ A such that 1 - exp(-(c*K)) < Σ_n ∈ S 1/n ≤ 1?
0claims
0verified
Erdős Problem #319
What is the size of the largest A⊆1, …, N such that there is a function δ : A → -1, 1 such that Σ_n∈ A δ n/n = 0 and Σ_n∈ A'δ n/n ≠ 0 for all non-empty A'subsetneq A.
0claims
0verified
Erdős Problem #326
Does there exist A = a_1 < a_2 < ⋯ ⊂ ℕ which is a minimal basis of order 2 (i.e. every large integer is the sum of 2 elements from A, and no proper subset of A has this property), such that lim_k→∞ a_k/k^2 = c for some c ≠ 0? Erdős and Graham conjectured a negative answer to this question [ErGr80].
0claims
0verified
Erdős Problem #329
Erdős Problem 329. Let A ⊆ ℕ be a Sidon set. How large can lim sup_N → ∞ |A ∩ 1,…,N| / N^1/2 be?
0claims
0verified
Erdős Problem #340
Let A = 1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, … be the greedy Sidon sequence: we begin with 1 and iteratively include the next smallest integer that preserves the Sidon property (i.e. there are no non-trivial solutions to a + b = c + d). What is the order of growth of A?
0claims
0verified
Erdős Problem #342
Do infinitely many pairs (a, a+2) occur in Ulam's sequence?
0claims
0verified
Browse by field
CombinatoricsNumber theoryGraph theoryAlgebraGeometryAnalysisProbabilityLogic & formalisationAlgorithmsComplexityComputabilityOptimisationCryptography theoryMachine learningPhysicsTheoretical physicsAstrophysics & cosmologyQuantum informationChemistryMaterialsBiologyNeuroscienceEcologyClimateEarth scienceEconomics