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 proceedingConference contribution


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 logsparse subsets of 0. We prove that for any log-sparse subsets S1, Sn of 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 languageEnglish (US)
Title of host publicationNumber Theory and Combinatorics - A Collection in Honor of the Mathematics of Ronald Graham
EditorsBruce M. Landman, Florian Luca, Melvyn B. Nathanson, Jaroslav Nesetril, Aaron Robertson
PublisherWalter de Gruyter GmbH
Number of pages7
ISBN (Electronic)9783110753431
StatePublished - Apr 19 2022

Publication series

NameDe Gruyter Proceedings in Mathematics
ISSN (Print)2942-4801
ISSN (Electronic)2942-4828

All Science Journal Classification (ASJC) codes

  • Applied Mathematics


Dive into the research topics of 'Arithmetic progressions in sumsets of sparse sets'. Together they form a unique fingerprint.

Cite this