Counting subsets of integers free of arithmetic configurations

2026/07/20 by Patrick Morris, Miquel Ortega, Juanjo Rué
#math.CO #math.NT

paper · pdf

Abstract

Cameron and Erdős asked if the number of sets free of arithmetic progressions of length k is 2^{r_k(n)(1+o(1))}, where r_k(n) is the maximum cardinality of a k-AP-free subset of \1, …, n\. Balogh, Liu and Sharifzadeh made significant progress on this question showing that it is 2^O(r_k(n)) for an infinite sequence of n. We improve their result in two ways. On the one hand, we prove that, for k≥ 5, the number of k-AP-free sets in [n] is 2^{r_k(n)(1+o(1))} for an infinite sequence of n, solving the question of Cameron and Erdős for infinitely many values. On the other hand, we also prove that for k ≥ 3 and all n the number of k-AP-free sets in [n] is 2^O(r_k(n)). These results are in fact special cases of a general framework that we develop to count families of sets excluding certain arithmetic patterns, which applies as long as the corresponding extremal threshold satisfies certain Behrend-type lower bounds. As further examples, we get analogous results for solution sets to almost all systems of linear equations as well as counting versions of the multidimensional Szemerédi theorem.

Related

• The number of subsets of integers with no k-term arithmetic progression
• A Constructive Lower Bound on Szemerédi's Theorem
• Small subsets without k-term arithmetic progressions
• An Approximate Counting Version of the Multidimensional Szemerédi Theorem
• On sets of integers not containing long arithmetic progressions