CaltechAUTHORS
  A Caltech Library Service

Sets without k-term progressions can have many shorter progressions

Fox, Jacob and Pohoata, Cosmin (2021) Sets without k-term progressions can have many shorter progressions. Random Structures & Algorithms, 58 (3). pp. 383-389. ISSN 1042-9832. https://resolver.caltech.edu/CaltechAUTHORS:20200110-150751274

[img] PDF - Submitted Version
See Usage Policy.

134kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200110-150751274

Abstract

Let f_(s, k)(n) be the maximum possible number of s‐term arithmetic progressions in a set of n integers which contains no k‐term arithmetic progression. For all fixed integers k > s ≥ 3, we prove that f_(s, k)(n) = n^(2 − o(1)), which answers an old question of Erdős. In fact, we prove upper and lower bounds for f_(s, k)(n) which show that its growth is closely related to the bounds in Szemerédi's theorem.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1002/rsa.20984DOIArticle
https://arxiv.org/abs/1908.09905arXivDiscussion Paper
ORCID:
AuthorORCID
Pohoata, Cosmin0000-0002-3757-2526
Additional Information:© 2020 Wiley Periodicals LLC. Issue Online: 10 March 2021; Version of Record online: 15 December 2020; Manuscript accepted: 27 July 2020; Manuscript received: 10 April 2020. Funding Information: NSF Grant Number: DMS‐1855635.
Funders:
Funding AgencyGrant Number
NSFDMS‐1855635
Subject Keywords:additive combinatorics; arithmetic progressions; probabilistic methods; Szemerédi's theorem
Issue or Number:3
Record Number:CaltechAUTHORS:20200110-150751274
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200110-150751274
Official Citation:Fox, J, Pohoata, C. Sets without k‐term progressions can have many shorter progressions. Random Struct Alg. 2021; 58: 383–389. https://doi.org/10.1002/rsa.20984
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100642
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:11 Jan 2020 00:54
Last Modified:12 Mar 2021 22:07

Repository Staff Only: item control page