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.
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.
Find a cap set in F_3^7 larger than the best known construction, or prove a better upper bound.
Find a cap set in F_3^8 larger than the best known construction.
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.
Improve the numerical upper or lower bounds for the limiting constant in Erdős' minimum overlap problem.
Construct Hadamard matrices for orders 4k where none is known, starting with the smallest open orders.
Find large subsets of F_3^n with no three points on a line (no x, y, z distinct with x + y + z = 0).
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.
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.
Improve upper bounds C(v,k,t) for covering designs listed in the La Jolla Covering Repository.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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].
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.
Let r(N) be the maximum size of a subset A⊂\1,…,N\ with no non-zero square differences a-b=n^2.Then C_4b is the least constant such that r(N) ≤ N^C_4b+o(1).
For n ≥ 1, let U_n denote the set of polynomials p(z) of degree n with coefficients ± 1.
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.
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.
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.
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.
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 → ∞.
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).
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.
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].
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.
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‖.
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.
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.
For each slope r ∈ ℝ ∪ ∞ define the projection π_r : ℝ^2 → ℝ by π_r(a,b) = a + rb for r ≠ ∞ and π_∞(a,b)=b.
C_3a is the largest constant such that there exist arbitrarily large sets A,B of integers such that |A+B| ≪ |A| and |A-B| ≫ |A+B|^C_3a.
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?
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].
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)
Every Barker sequence has length at most 13.
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?
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.
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 → ∞?
What is the largest subset of [N] with no solution to x + 3y = 2z + 2w in distinct integers x, y, z, w?
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]
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.
Can we improve the lower bound N^1/2 + O(1), at least for infinitely many N?
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]
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.
Does f(r) → ∞? [Gr24]
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.
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/α))?
Suppose A, B ⊆ 1, …, N both have size at least N^0.49. Must the sumset A + B contain a composite number?
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?
Given n points in the unit disc, must there be a triangle of area at most n^-2+o(1) determined by them?
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.
Conjecture 3.2 in [Wa2011]: Each Latin square of odd order has at least one transversal.
No closed-form expression that allows efficient computation of Dedekind numbers is currently known.
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.
Is there some k such that every large integer is the sum of a prime and at most k powers of 2?
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.
Are there infinitely many binomial coefficients with deficiency 1?
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.
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?
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.
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 ℓ?
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.
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?
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].
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?
Does 1,2^3,…,N^3 contain a Sidon set of size ≫ N?
Let k≥3. Are there k consecutive primes in arithmetic progression?
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→ ∞?
Is it true that for every k ≥ 1 we have F(N + k) ≤ F(N) + 1 for all sufficiently large N?
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].
Let A be an infinite B₂[2] set. Must liminf |A ∩ 1, ..., N| * N ^ (- 1 / 2) = 0?
Estimate h(n) by finding a better upper bound.
The problem is to determine the limit of the sequence F(N)/√(N) as N → ∞.
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?
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.
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?
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.
Must every permutation of ℕ, contain a monotone 4-term arithmetic progression?
Can ℕ be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions?
Does the longest arithmetic progression of primes in 1,…,N have length o(log N)?
Is there an integer m with (m, 6) = 1 such that none of 2^k · 3^ℓ · m + 1 are prime, for any k, ℓ ≥ 0?
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).
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].
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?
Is there a covering system all of whose moduli are of the form p-1 for some primes p ≥ 5?
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.
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 = ∞?
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?
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.
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].
Erdős Problem 329. Let A ⊆ ℕ be a Sidon set. How large can lim sup_N → ∞ |A ∩ 1,…,N| / N^1/2 be?
All 158 problems in combinatorics →
Everything is published under CC BY 4.0 with authorship recorded. How it works