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).
No claims yet Be the first →
Open problems in additive combinatorics
Sumsets, arithmetic progressions in dense sets, sum-free sets and the structure of sets with few sums. Many of these problems are from Erdős's lists and Ben Green's list of 100 open problems; several have Lean statements in Formal Conjectures.
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.
No claims yet Be the first →
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?
No claims yet Be the first →
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].
No claims yet Be the first →
Erdős Problem #138
In [Er80] Erdős asks whether lim_k → ∞ (W(k))^1/k = ∞
No claims yet Be the first →
Erdős Problem #14
Let A ⊆ ℕ. Let B ⊆ ℕ be the set of integers which are representable in exactly one way as the sum of two elements from A. Is it true that for all ε > 0 and large N, |1,…,N ∖ B| ≫_ε N^1/2 - ε?
No claims yet Be the first →
Erdős Problem #141
Let k≥3. Are there k consecutive primes in arithmetic progression?
No claims yet Be the first →
Erdős Problem #142
Prove an asymptotic formula for r_k(N), the largest possible size of a subset of 1, …, N that does not contain any non-trivial k-term arithmetic progression. That is, find f_k with r_k(N) / f_k(N) → 1 as N → ∞.
No claims yet Be the first →
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?
No claims yet Be the first →
Erdős Problem #160
Estimate h(n) by finding a better upper bound.
No claims yet Be the first →
Erdős Problem #168
What is the limit F(N)/N as N → ∞?
No claims yet Be the first →
Erdős Problem #170
The problem is to determine the limit of the sequence F(N)/√(N) as N → ∞.
No claims yet Be the first →
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?
No claims yet Be the first →
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].
No claims yet Be the first →
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?
No claims yet Be the first →
Erdős Problem #3
If A ⊂ ℕ has Σ_n ∈ Afrac 1 n = ∞, then must A contain arbitrarily long arithmetic progressions?
No claims yet Be the first →
Erdős Problem #30
Is it true that, for every ε > 0, h(N) = sqrt N + O_ε(N^ε)
No claims yet Be the first →
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?
No claims yet Be the first →
Erdős Problem #39
Is there an infinite Sidon set A⊂ ℕ such that lvert A∩ 1…,Nrvert ≫_ε N^1/2-ε for all ε > 0?
No claims yet Be the first →
Erdős Problem #41
Let A ⊂ ℕ be an infinite set such that the triple sums a+b+c are all distinct for a,b,c ∈ A (aside from the trivial coincidences). Is it true that liminf_N → ∞ fraclvert A ∩ 1,…,NrvertN^1/3=0?
No claims yet Be the first →
Erdős Problem #44
Erdős Problem 44: Let N ≥ 1 and A ⊆ 1,…,N be a Sidon set. Is it true that, for any ε > 0, there exist M = M(ε) and B ⊆ N+1,…,M such that A ∪ B ⊆ 1,…,M is a Sidon set of size at least (1−ε)M^1/2?
No claims yet Be the first →
Erdős Problem #52
Let A be a finite set of integers. Is it true that for every ε>0 max( lvert A+Arvert,lvert AArvert)≫_ε lvert Arvert^2-ε?
No claims yet Be the first →
Erdős Problem #539
Let h(n) be maximal such that, for any set A⊆ ℕ of size n, the set a/(a,b): a,b∈ Ahas size at least h(n). Estimate h(n).
No claims yet Be the first →
Erdős Problem #749
Let ε>0. Does there exist A⊆ ℕ such that the lower density of A+A is at least 1-ε and yet 1_Aast 1_A(n) ≪_ε 1 for all n?
No claims yet Be the first →
Erdős Problem #789
Let h(n) be maximal such that if A⊆ ℤ with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+⋯+a_r=b_1+⋯+b_s with a_i,b_i∈ B then r=s. Estimate h(n).
No claims yet Be the first →
Erdős Problem #817
Erdős Problem #817
No claims yet Be the first →