Arithmetic Progressions in Sumsets of Sparse Sets

2021/04/04 by Alon, Noga, Alweiss, Ryan, Liu, Yang P. +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.01564

Abstract

A set of positive integers A ⊂ ℤ_{> 0} is log-sparse if there is an absolute constant C so that for any positive integer x the sequence contains at most C elements in the interval [x,2x). In this note we study arithmetic progressions in sums of log-sparse subsets of ℤ_{> 0}. We prove that for any log-sparse subsets S₁, …, S_n of ℤ_{> 0}, the sumset S = S₁ + ⋯ + S_n cannot contain an arithmetic progression of size greater than n^(1+o(1))n. We also show that this is nearly tight by proving that there exist log-sparse sets S₁, …, S_n such that S₁ + ⋯ + S_n contains an arithmetic progression of size n^{(1-o(1)) n}.

Related

• Arithmetic progressions in sets with small sumsets
• On product sets of arithmetic progressions
• The number of subsets of integers with no k-term arithmetic progression
• On arithmetic progressions in A + B + C
• Arithmetic properties of sparse subsets of ℤⁿ