Arithmetic progressions in sumsets of sparse sets

Noga Alon, Ryan Alweiss, Yang P. Liu, Anders Martinsson, Shyam Narayanan

Research output: Chapter in Book/Report/Conference proceedingChapter


A set of positive integers A ⊂ Z>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 logsparse subsets of Z>0. We prove that for any log-sparse subsets S1,., Sn of Z>0, the sumset S = S1 + . + Sn 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 S1,., Sn such that S1 + . + Sn contains an arithmetic progression of size n(1-o(1))n.

Original languageAmerican English
Title of host publicationNumber Theory and Combinatorics
Subtitle of host publicationA Collection in Honor of the Mathematics of Ronald Graham
Publisherde Gruyter
Number of pages7
ISBN (Electronic)9783110754216
ISBN (Print)9783110753431
StatePublished - Apr 19 2022

ASJC Scopus subject areas

  • General Mathematics

Cite this