Sets without <i>k</i>‐term progressions can have many shorter progressions

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 &gt; 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.

Locations

• CaltechAUTHORS (California Institute of Technology) - View - PDF
• CaltechAUTHORS (California Institute of Technology) - View - PDF
• Random Structures and Algorithms - View