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

Abstract

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
Pages27-33
Number of pages7
ISBN (Electronic)9783110754216
ISBN (Print)9783110753431
DOIs
StatePublished - Apr 19 2022

ASJC Scopus subject areas

  • General Mathematics

Cite this