Skip to content
Mathematics · 158 open problems

Open problems in combinatorics

Extremal and additive combinatorics are full of questions where a single construction or a sharper bound is real progress — cap sets, Ramsey numbers, sunflowers, union-closed families. Many results are machine-checkable: a certificate is verified by a deterministic checker, a proof by the Lean kernel.

Level A · Machine-checkable sub-problem

Cap sets in dimension 7

Find a cap set in F_3^7 larger than the best known construction, or prove a better upper bound.

0claims
0verified
Level A · Machine-checkable sub-problem

Cap sets in dimension 8

Find a cap set in F_3^8 larger than the best known construction.

0claims
0verified
Level B · Reproducible

Costas arrays of order 32 and 33

Find a Costas array of order 32 or 33, the smallest orders for which none is known, or extend the complete enumeration of Costas arrays beyond order 29.

0claims
0verified
Level A · Machine-checkable

Erdős minimum overlap problem

Improve the numerical upper or lower bounds for the limiting constant in Erdős' minimum overlap problem.

0claims
0verified
Level A · Machine-checkable

Hadamard matrices of open orders

Construct Hadamard matrices for orders 4k where none is known, starting with the smallest open orders.

0claims
0verified
Level A · Machine-checkable

Large cap sets in F_3^n

Find large subsets of F_3^n with no three points on a line (no x, y, z distinct with x + y + z = 0).

0claims
0verified
Level B · Reproducible

Optimal Golomb rulers

Find the shortest Golomb ruler (all pairwise mark differences distinct) with n marks. Optimality is proven up to 28 marks (length 585, distributed.net, 2022); 29 marks is the first open case, and shorter rulers for larger n would beat long-standing constructions.

0claims
0verified
Level B · Reproducible

Small van der Waerden numbers

Determine W(r,k), the least N such that every r-colouring of {1,…,N} contains a monochromatic k-term arithmetic progression. Only seven non-trivial values are known; the open cases W(2,7), W(3,5), W(4,4) and W(5,3) invite better lower-bound colourings and exact computations.

0claims
0verified
Level A · Machine-checkable

Smaller covering designs

Improve upper bounds C(v,k,t) for covering designs listed in the La Jolla Covering Repository.

0claims
0verified
Level B · Reproducible

Snake-in-the-box — longest induced paths in hypercubes

Find the longest induced path (snake) in the n-dimensional hypercube Q_n. Optimal lengths are known only up to n = 8 (98); for n = 9–13 new records were set in 2026 and further improvements are open.

0claims
0verified
Level B · Reproducible

The sixth Schur number S(6)

Find the largest N such that {1,…,N} can be split into six sum-free sets. After Heule's 2017 SAT proof that S(5) = 160, the best known bound is S(6) ≥ 536, with a large gap to the upper bound.

0claims
0verified
Level C · Reviewed Hard

Frankl's union-closed sets conjecture

Every finite union-closed family of sets other than {∅} has an element lying in at least half of its sets. Since Gilmer's 2022 entropy breakthrough the best proven fraction is about 0.38; closing the gap to 1/2 is open.

0claims
0verified
Level C · Reviewed Hard

The 1/3–2/3 conjecture for balanced pairs in posets

Every finite poset that is not a chain has elements x, y such that x precedes y in between 1/3 and 2/3 of its linear extensions. The best general constant is (5−√5)/10 ≈ 0.276; all posets with up to 14 elements have been verified.

0claims
0verified
Level B · Reproducible Hard

The chromatic number of the plane (Hadwiger–Nelson problem)

Determine how many colours are needed so that no two points of the plane at distance exactly 1 share a colour. The answer is known to be 5, 6 or 7; a concrete sub-goal is a smaller 5-chromatic unit distance graph than the 509-vertex record.

0claims
0verified
Level C · Reviewed Hard

The Erdős–Rado sunflower conjecture

Show that every family of more than C_k^n sets of size n contains a k-sunflower, for a constant C_k depending only on k. The best bound, about (Ck log n)^n, follows the 2019 breakthrough of Alweiss, Lovett, Wu and Zhang.

0claims
0verified
Level B · Reproducible Hard

The Erdős–Szekeres happy ending problem

Is every set of 2^{n−2}+1 points in general position in the plane guaranteed to contain n points in convex position? Known exactly up to n = 6 (17 points); the first open case is whether 33 points force a convex 7-gon.

0claims
0verified
Level B · Reproducible Hard

The lonely runner conjecture

For k+1 runners with distinct constant speeds on a unit circular track, each runner is at some time at distance at least 1/(k+1) from all others. Computer-assisted proofs now cover up to 13 runners; the general case is open.

0claims
0verified
Level B · Reproducible

4-slope Kakeya-type sum-difference constant

C_3c = SD(\0,1,2,∞\;-1) is the least exponent such that one has the inequality |A stackrelG- B| ≤ max(|A|, |B|, |A stackrelG+ B|, |A stackrelG+ 2B|)^C_3c whenever A, B are finite subsets of reals and G ⊂ A × B, where A stackrelG± rB := a ± rb: a ∈ A, b ∈ B.

0claims
0verified
Level B · Reproducible

A Sidon set constant

C_5a is the smallest constant such that Sidon sets in \1,…,N\ have cardinality N^1/2 + (C_5a + o(1))N^1/4.

0claims
0verified
Level B · Reproducible

Asymptotic counting exponent for partial Hadamard matrices

For integers n ≥ 2 and t ≥ 1, an n × t partial Hadamard matrix is a matrix with entries in \± 1\ whose rows are pairwise orthogonal. Let N_n,t denote the number of such matrices. For every fixed n one has N_n,4t = [1+o(1)] A_n,4t qquadas t → ∞, where A_n,4t := 2^4nt+(n-1)^2(8π t)^-n(n-1)/4.

0claims
0verified
Level B · Reproducible

Davenport constant for C_n^3

In zero-sum theory, the Davenport constant D(G) of a finite abelian group G is defined as the smallest integer l∈ℕ such that every sequence S over G of length lvert Srvert≥ l has a non-empty zero-sum subsequence.

0claims
0verified
Level B · Reproducible

Difference Bases

For any natural number n, let Δ(n) be the size of the smallest set B of integers such that every natural number from 1 to n is expressible as a difference of two elements of B (such sets are known as difference bases for the interval 1,…,n). Write C(n) := Δ^2(n)/n, and C := inf_n ≥ 1 C(n).

0claims
0verified
Level B · Reproducible

Erdős–Szemerédi 3-sunflower-free capacity

A family of three distinct sets A,B,C is a 3-sunflower (or Δ-system) if A∩ B = A∩ C = B∩ C. A family of sets is sunflower-free if it contains no 3-sunflower (equivalently, no sunflower of any size ≥ 3). Let [n]:=\1,2,…,n\ and let f(n) denote the maximum size of a sunflower-free family F⊆ 2^[n].

0claims
0verified
Level B · Reproducible

Exponential growth constant for diagonal Ramsey numbers

C_17 is the limit (if it exists) of R(k)^1/k as k → ∞, where the diagonal Ramsey number R(k) is the smallest integer n such that every red/blue colouring of the edges of the complete graph K_n contains a monochromatic copy of K_k.

0claims
0verified
Level B · Reproducible

Golay's Merit Factor

For n ≥ 1, let U_n denote the set of polynomials p(z) of degree n with coefficients ± 1.

0claims
0verified
Level B · Reproducible

Good asymptotic constructions of Szemerédi–Trotter

If n,m are natural numbers, let C(n,m) denote the maximum number of incidences that are possible between n points and m lines in the plane. Establish upper and lower bounds on C(n,m) that are as strong as possible.

0claims
0verified
Level B · Reproducible

Kakeya and Nikodym sets in finite fields

Let d ≥ 1, and let q be a prime power. Let 𝔽_q be a finite field of order q. A Kakeya set is a set K that contains a line in every direction, and an Nikodym set N is a set with the property that every point x in 𝔽_q^d is contained in a line that is contained in N ∪ x.

0claims
0verified
Level B · Reproducible

Kakeya-type sum-difference constant

C_3b = SD(\0,1,∞\;-1) is the least exponent such that one has the inequality |A stackrelG- B| ≤ max(|A|, |B|, |A stackrelG+ B|)^C_3b whenever A, B are finite subsets of reals and G ⊂ A × B, where A stackrelG± B := a ± b: a ∈ A, b ∈ B.

0claims
0verified
Level B · Reproducible

Komlós discrepancy constant

C_24 is the Komlós discrepancy constant (often denoted K). For a real matrix A∈ℝ^m× n, define its (sign) discrepancy by disc(A) := min_x∈-1,1^n ‖Ax‖_∞. For each n≥ 1, define the dimension-n Komlós discrepancy K_n := supdisc(A): A∈ℝ^n× n and ‖A_ast j‖_2≤ 1 for all columns j.

0claims
0verified
Level B · Reproducible

Marton's conjecture (Polynomial Freiman-Ruzsa) constant

C_18 is the least constant such that, whenever A is a subset of 𝔽_2^n with lvert A+Arvert ≤ Klvert Arvert, then A can be covered by K^C_18+o(1) cosets of a subspace of cardinality at most lvert Arvert, where the limit o(1) is with respect to the limit K → ∞.

0claims
0verified
Level B · Reproducible

Rate at which κ(n) approaches 1

Given a real matrix A, let its condition number be κ(A):=σ_max(A)/σ_min(A), where σ_min(A) and σ_max(A) denote the smallest and largest singular values of A, respectively (with κ(A)=∞ if σ_min(A)=0).

0claims
0verified
Level B · Reproducible

Sidon set density inside (4,5) sets

C_5b is the largest constant such that every (4,5)-set of size n (i.e., a set of reals such that every four-element subset determines at least five distinct differences) contains a Sidon set of cardinality C_5bn.

0claims
0verified
Level B · Reproducible

Single-set sum-difference exponent

For a finite nonempty subset A of an abelian group, write σ(A) := |A+A|/|A|, δ(A) := |A-A|/|A| for the doubling and difference constants. Ruzsa [Ru96] proved δ ≤ σ^2, and the Plünnecke–Ruzsa inequalities give the converse σ ≤ δ^2 [Bl26].

0claims
0verified
Level B · Reproducible

Stanley–Wilf limit for the permutation pattern 1324

Let Av_n(1324) be the set of permutations of \1,2,…,n\ that avoid the permutation pattern 1324, and let S_n(1324) := |Av_n(1324)|. <a href="#CJS12-def-Sn">[CJS12-def-Sn]</a> The Stanley–Wilf limit (growth constant) for the pattern 1324 is C_30 := lim_n→∞ bigl(S_n(1324)bigr)^1/n.

0claims
0verified
Level B · Reproducible

Subsets of the grid with no isosceles triangles

For n a natural number, let C(n) denote the size of the largest subset of [n]^2 = 1,…,n^2 that does not contain a (possibly flat) isosceles triangle. In other words, C(n) := max_S⊂ [n]^2|S|: a,b,c∈ S distinct implies ‖a-b‖ ≠ ‖b-c‖.

0claims
0verified
Level B · Reproducible

Sum-product exponent for the reals

For a finite set A ⊂ ℝ write A+A = \ a+b : a,b ∈ A \, AA = \ ab : a,b ∈ A \ for the sumset and product set. The (real) sum-product exponent is C_84b := liminf_n → ∞ min_substackA ⊂ ℝ \ lvert Arvert = n log max(lvert A+Arvert, lvert AArvert)/log n.

0claims
0verified
Level B · Reproducible

Sum-product problems

Given a natural number N and a ring R of size at least N, let C(R, N) denote the least possible value of max(|A+A|, |A · A|) where A ranges over subsets of R of cardinality N. Establish upper and lower bounds for C(R, N) that are as strong as possible.

0claims
0verified
Level B · Reproducible

The Arithmetic Kakeya Conjecture

For each slope r ∈ ℝ ∪ ∞ define the projection π_r : ℝ^2 → ℝ by π_r(a,b) = a + rb for r ≠ ∞ and π_∞(a,b)=b.

0claims
0verified
Level B · Reproducible

The hypergraph Turán number of the tetrahedron

Let C be the largest quantity such that, as n → ∞, one can locate a 3-uniform hypergraph on n vertices and at least (C-o(1)) C(n, 3) edges that contains no copy of the tetrahedron K^(3)_4. What is C?

0claims
0verified
Level B · Reproducible

Unnormalized single-set sum-difference exponent

For a finite non-empty set A of integers, C_3e is the least constant such that |A - A| ≤ |A + A|^C_3e for every such A; equivalently, C_3e = sup_A loglvert A-Arvert / loglvert A+Arvert. This is Problem 6.43 of [GGSWT2025].

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Babai–Seress Conjectures on the Diameter of Finite Groups

Babai–Seress Conjecture (Conjecture 1.5): There exists an absolute constant C such that the diameter of the alternating group A_n satisfies diam(A_n) ≤ n^C. Reference: L. Babai and Á. Seress, On the diameter of permutation groups, European Journal of Combinatorics 13 (1992), Conjecture 1.580029-0)

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Barker sequences

Every Barker sequence has length at most 13.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Beaver Math Olympiad (BMO)

BMO#1) Let (a_n)_n ≥ 1 and (b_n)_n ≥ 1 be two sequences such that (a_1, b_1) = (1, 2) and (a_n+1, b_n+1) = begincases (a_n-b_n, 4b_n+2) & if a_n ≥ b_n cr (2a_n+1, b_n-a_n) & if a_n < b_n endcases for all positive integers n. Does there exist a positive integer i such that a_i = b_i?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Beck–Fiala theorem and conjecture

The Beck–Fiala conjecture There exists a universal constant C > 0 such that every set system S_1, …, S_m ⊆ [n] of degree at most t admits a colouring χ : [n] → -1, +1 with |Σ_j ∈ S_i χ(j)| ≤ C √(t) for every i.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Ben Green's Open Problem 1

Let A be a set of n positive integers. Does A contain a sum-free set of size at least frac n 3 + Ω(n), where Ω(n) → ∞ as n → ∞?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Ben Green's Open Problem 16

What is the largest subset of [N] with no solution to x + 3y = 2z + 2w in distinct integers x, y, z, w?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Ben Green's Open Problem 18

Suppose that G is a finite group, and let A ⊂ G × G be a subset of density α. Is it true that there are ≫_α |G|^3 triples x, y, g such that (x, y), (gx, y), (x, gy) all lie in A? Note: A is taken as α-dense, i.e. |A| ≥ α |G|^2 [Au16, Question 2]

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Ben Green's Open Problem 21

Suppose that a_1, …, a_k are integers which do not satisfy Rado's condition: thus if Σ_i ∈ I a_i = 0 then I = ∅. It then follows from Rado's theorem that the equation a_1x_1 + ⋯ + a_kx_k = 0 is not partition regular.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Ben Green's Open Problem 31

Can we improve the lower bound N^1/2 + O(1), at least for infinitely many N?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Ben Green's Open Problem 33

Are there infinitely many q for which there is a set A ⊂ ℤ/qℤ, |A| = (√(2) + o(1))q^1/2, with A + A = ℤ/qℤ? [Gr24]

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

Conjectures about Latin Squares

Conjecture 3.2 in [Wa2011]: Each Latin square of odd order has at least one transversal.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Dedekind Numbers

No closed-form expression that allows efficient computation of Dedekind numbers is currently known.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

Erdős Problem #1093

Are there infinitely many binomial coefficients with deficiency 1?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

Erdős Problem #1206

Does 1,2^3,…,N^3 contain a Sidon set of size ≫ N?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Erdős Problem #141

Let k≥3. Are there k consecutive primes in arithmetic progression?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

Erdős Problem #158

Let A be an infinite B₂[2] set. Must liminf |A ∩ 1, ..., N| * N ^ (- 1 / 2) = 0?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Erdős Problem #160

Estimate h(n) by finding a better upper bound.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

Erdős Problem #170

The problem is to determine the limit of the sequence F(N)/√(N) as N → ∞.

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

Erdős Problem #196

Must every permutation of ℕ, contain a monotone 4-term arithmetic progression?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

Erdős Problem #200

Does the longest arithmetic progression of primes in 1,…,N have length o(log N)?

0claims
0verified
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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
Level A · Machine-checkable Hard Lean statement

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

All 158 problems in combinatorics →

How to contribute in combinatorics

  1. Get a task matched to your ability: a review, a lemma, a computation, a literature find or a documented dead end.
  2. Work on it with your model — a free chatbot through copy–paste prompts, or an agent connected over MCP.
  3. Submit a claim with evidence. It is checked by a machine where possible (Lean, certificate checkers), re-run where practical, and otherwise reviewed with stated reasons.

Everything is published under CC BY 4.0 with authorship recorded. How it works