Arithmetic progressions in sumsets of sparse sets

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

doi:10.1515/9783110754216-003

Arithmetic progressions in sumsets of sparse sets

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

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

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 S₁,., S_n of Z_>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.

Original language	English (US)
Title of host publication	Number Theory and Combinatorics
Subtitle of host publication	A Collection in Honor of the Mathematics of Ronald Graham
Publisher	de Gruyter
Pages	27-33
Number of pages	7
ISBN (Electronic)	9783110754216
ISBN (Print)	9783110753431
DOIs	https://doi.org/10.1515/9783110754216-003
State	Published - Apr 19 2022

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1515/9783110754216-003

Cite this

@inbook{becf2e8933b54b12b084c93db7d99694,

title = "Arithmetic progressions in sumsets of sparse sets",

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.",

author = "Noga Alon and Ryan Alweiss and Liu, {Yang P.} and Anders Martinsson and Shyam Narayanan",

note = "Publisher Copyright: {\textcopyright} 2022 Walter de Gruyter GmbH, Berlin/Boston.",

year = "2022",

month = apr,

day = "19",

doi = "10.1515/9783110754216-003",

language = "English (US)",

isbn = "9783110753431",

pages = "27--33",

booktitle = "Number Theory and Combinatorics",

publisher = "de Gruyter",

address = "Germany",

}

TY - CHAP

T1 - Arithmetic progressions in sumsets of sparse sets

AU - Alon, Noga

AU - Alweiss, Ryan

AU - Liu, Yang P.

AU - Martinsson, Anders

AU - Narayanan, Shyam

PY - 2022/4/19

Y1 - 2022/4/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85182846958&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85182846958&partnerID=8YFLogxK

U2 - 10.1515/9783110754216-003

DO - 10.1515/9783110754216-003

M3 - Chapter

AN - SCOPUS:85182846958

SN - 9783110753431

SP - 27

EP - 33

BT - Number Theory and Combinatorics

PB - de Gruyter

ER -

Arithmetic progressions in sumsets of sparse sets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this