Number of arithmetic progressions in dense random subsets of ℤ/nℤ

2019/07/26 by Berkowitz, Ross, Sah, Ashwin, Sawhney, Mehtaab
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.11807

Abstract

We examine the behavior of the number of k-term arithmetic progressions in a random subset of ℤ/nℤ. We prove that if a set is chosen by including each element of ℤ/nℤ independently with constant probability p, then the resulting distribution of k-term arithmetic progressions in that set, while obeying a central limit theorem, does not obey a local central limit theorem. The methods involve decomposing the random variable into homogeneous degree d polynomials with respect to the Walsh/Fourier basis. Proving a suitable multivariate central limit theorem for each component of the expansion gives the desired result.

Related

• Limit Theorems for Descents in Permutations and Arithmetic Progressions in ℤ/pℤ
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• On distribution of three-term arithmetic progressions in sparse subsets of F_pⁿ
• Small subsets without k-term arithmetic progressions
• The number of subsets of integers with no k-term arithmetic progression