Premium
Sets without k ‐term progressions can have many shorter progressions
Author(s) -
Fox Jacob,
Pohoata Cosmin
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20984
Subject(s) - term (time) , arithmetic progression , mathematics , combinatorics , set (abstract data type) , arithmetic , discrete mathematics , computer science , physics , quantum mechanics , programming language
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.