Sets without k‐term progressions can have many shorter progressions. Issue 3 (15th December 2020)

• Record Type: Journal Article
• Authors: Fox, Jacob; Pohoata, Cosmin
• Is Part Of: Random structures & algorithms. Volume 58:Issue 3(2021)
• Page Start: 383
• Page End: 389
• Publication Date: 2020-12-15
• Subjects: additive combinatorics -- arithmetic progressions -- probabilistic methods -- Szemerédi's theorem; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20984
• Languages: English
• ISSNs: 1042-9832

Abstract

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.