Arithmetic progressions in sumsets of sparse sets

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

Research output: Contribution to journalArticlepeer-review


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 log-sparse 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 languageEnglish (US)
Article numberA3
StatePublished - 2021

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Discrete Mathematics and Combinatorics


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

Cite this