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 → ∞?
No claims yet Be the first →
Ben Green's 100 open problems — formalised and open
Ben Green (Oxford) keeps a list of 100 open problems, mostly in additive combinatorics and related number theory, with notes on what is known. The problems here are the ones Formal Conjectures has stated in Lean and that are still open; each links back to its entry in Green's list. Use this page to follow which of them people are working on.
Source: Ben Green, 100 open problems (PDF). Licence: Lean statements from Formal Conjectures (Apache 2.0); problem text in our own words.
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?
No claims yet Be the first →
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]
No claims yet Be the first →
Ben Green's Open Problem 2
Let A ⊂ ℤ be a set of n integers. Is there a set S ⊂ A of size (log n)^100 such that the restricted sumsetS hat+ S is disjoint from A?
No claims yet Be the first →
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.
No claims yet Be the first →
Ben Green's Open Problem 31
Can we improve the lower bound N^1/2 + O(1), at least for infinitely many N?
No claims yet Be the first →
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]
No claims yet Be the first →
Ben Green's Open Problem 35
Lower bound for c(p) for 1 < p ≤ ∞, improving the known value √(4/7) at p = 2 or the known value 0.64 at p = ∞.
No claims yet Be the first →
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.
No claims yet Be the first →
Ben Green's Open Problem 4
What is the largest product-free set in the alternating group A_n?
No claims yet Be the first →
Ben Green's Open Problem 40
Does f(r) → ∞? [Gr24]
No claims yet Be the first →
Ben Green's Open Problem 41
How many rotated (about the origin) copies of the 'pyjama set' \(x, y) ∈ ℝ^2 : dist(x, ℤ) ≤ ε\ are needed to cover ℝ^2? That is, determine the minimal number of rotations as a function of ε > 0.
No claims yet Be the first →
Ben Green's Open Problem 45
Can we pick residue classes a_p pmodp, one for each prime p ≤ N, such that every integer ≤ N lies in at least 10 of them? Erdős remarks that he does not know how to answer it with 10 replaced by 2; this is Erdos689.erdos_689.
No claims yet Be the first →
Ben Green's Open Problem 46
We conjecture that the best-known lower bound can be improved.
No claims yet Be the first →
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.
No claims yet Be the first →
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/α))?
No claims yet Be the first →
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?
No claims yet Be the first →
Ben Green's Open Problem 60
Is there an absolute constant c > 0 such that, whenever A ⊆ ℕ is a set of squares with |A| ≥ 2, the sumset A + A satisfies |A + A| ≥ |A|^1 + c?
No claims yet Be the first →
Ben Green's Open Problem 61
Suppose that A + A contains the first n squares. Is |A| ≥ n^1 - o(1)? It is known that necessarily |A| ≥ n^2/3 - o(1), whilst in the other direction there do exist such A with |A| ≪_C n / log^C n for any C.
No claims yet Be the first →
Ben Green's Open Problem 62
Let p be a large prime, and let A be the set of all primes less than p. Is every x ∈ 1, …, p-1 congruent to some product a_1 a_2 where a_1, a_2 ∈ A?
No claims yet Be the first →
Ben Green's Open Problem 66
Is there always a sum of two squares between X - 1/10X^1/4 and X? We formalize this as an eventual statement for sufficiently large real X.
No claims yet Be the first →
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?
No claims yet Be the first →
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?
No claims yet Be the first →
Ben Green's Open Problem 82
Let A ⊂ ℤ be a set of size n. For how many θ ∈ ℝ/ℤ must we have Σ_a ∈ A cos(2π aθ) = 0? The answer is the function minZeros.
No claims yet Be the first →
Ben Green's Open Problem 94
Let A ⊂ R be a set of positive measure. Does A contain an affine copy of 1, 1/2, 1/4, . . . ?
No claims yet Be the first →
Green's Open Problem 12
Let G be an abelian group of size N, and suppose that A ⊂ G has density α. Are there at least α^15 N^10 tuples (x_1, …, x_5, y_1, …, y_5) ∈ G^10 such that x_i + y_j ∈ A whenever j ∈ i, i+1, i+2? Note: We interpret indices modulo 5.
No claims yet Be the first →
Green's Open Problem 15
Does there exist a Lipschitz function f : ℕ → ℤ whose graph Γ = (n, f(n)) : n ∈ ℕ ⊆ ℤ^2 is free of 3-term progressions?
No claims yet Be the first →
Green's Open Problem 22
If 1, …, N is r-coloured then, for N geqslant N_0(r), there are integers x, y geqslant 3 such that x + y, xy have the same colour. Find reasonable bounds for N_0(r). The goal is to improve upon the Green-Sawhney bound.
No claims yet Be the first →
Green's Open Problem 24
If A is a set of n integers, what is the maximum number of affine translates of the set lbrace 0,1,3 rbrace that A can contain? Conjectured in [Aa19] p.579: (1/3 + o(1)) n^2.
No claims yet Be the first →
Green's Open Problem 25
For which values of k is the following true: whenever we partition [N] = A_1 ∪ … ∪ A_k, |bigcup^k_i=1 (A_i hat+ A_i)| ≥ 1/10 N?
No claims yet Be the first →
Green's Open Problem 27
What is the size of the smallest set A ⊂ ℤ / pℤ (with at least two elements) for which no element in the sumset A + A has a unique representation?
No claims yet Be the first →
Green's Open Problem 28
Suppose that X, Y are two finitely-supported independent random variables taking integer values, and such that X + Y is uniformly distributed on its range. Are X and Y themselves uniformly distributed on their ranges?
No claims yet Be the first →
Green's Open Problem 32
Let p be a prime and let A ⊂ ℤ/pℤ be a set of size ⌊ √(p) ⌋. Is there a dilate of A containing a gap of length 100√(p)?
No claims yet Be the first →
Green's Open Problem 36
Do the following exist, for arbitrarily large n? An abelian group H with |H| = n^2+o(1), together with subsets A_1, ..., A_n, B_1, ..., B_n satisfying |A_i||B_i| ≥ n^2-o(1) and |A_i + B_i| = |A_i||B_i|, such that the sets A_i + B_i are disjoint from the sets A_j + B_k (j ≠ k)?
No claims yet Be the first →
Green's Open Problem 38
Can we improve the best upper bound? The base c must be positive, since =O compares norms.
No claims yet Be the first →
Green's Open Problem 39
If A ⊂ ℤ/pℤ is random, |A| = √(p), can we almost surely cover ℤ/pℤ with 100√(p) translates of A? [Gr24]
No claims yet Be the first →
Green's Open Problem 42
Can the Cohn-Elkies scheme be used to prove the optimal bound for circle-packings in 2 dimensions?
No claims yet Be the first →
Green's Open Problem 44
Sieve [N] by removing half the residue classes mod p_i, for primes 2 leqslant p_1 < p_2 < … < p_1000 < N^9/10. Does the remaining set have size at most 1/10 N? We interpret "half the residue classes" as ⌊ p_i / 2 ⌋.
No claims yet Be the first →
Green's Open Problem 51
Suppose that A ⊂ 𝔽_2^n is a set of density α. What is the largest size of coset guaranteed to be contained in 2A? We phrase this by asking for the exact function F(α, n) giving the maximum dimension of a guaranteed coset.
No claims yet Be the first →
Green's Open Problem 52
Suppose that A ⊂ 𝔽_2^n is a set with an additive complement of size K. Does 2A contain a coset of codimension O_K(1)?
No claims yet Be the first →
Green's Open Problem 53
Suppose that 𝔽_2^n is partitioned in to sets A_1, ..., A_K. Does 2A_i contain a coset of codimension O_K(1) for some i?
No claims yet Be the first →
Green's Open Problem 64
Do there exist infinitely many primes p for which p - 2 has an odd number of prime factors, counted with multiplicity (i.e. Ω(p - 2) is odd)?
No claims yet Be the first →
Green's Open Problem 85
Suppose that A is an open subset of [0, 1]^2 with measure α. Are there four points in A determining an axis-parallel rectangle with area gt c α^2?
No claims yet Be the first →
Green's Open Problem 9
Problem 9 (ii): is r_5(N) ≪ N(log N)^-c?
No claims yet Be the first →