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.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper
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.
Funding AgencyGrant Number
Subject Keywords:additive combinatorics; arithmetic progressions; probabilistic methods; Szemerédi's theorem
Issue or Number:3
Record Number:CaltechAUTHORS:20200110-150751274
Persistent URL:
Official Citation:Fox, J, Pohoata, C. Sets without k‐term progressions can have many shorter progressions. Random Struct Alg. 2021; 58: 383–389.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100642
Deposited By: Tony Diaz
Deposited On:11 Jan 2020 00:54
Last Modified:12 Mar 2021 22:07

Repository Staff Only: item control page