Bivariate fluctuations for the number of arithmetic progressions in random sets

Abstract

We study arithmetic progressions $\{a,a+b,a+2b,\dots ,a+(\ell -1)b\}$, with $\ell \ge 3$, in random subsets of the initial segment of natural numbers $[n]:=\{1,2,\dots ,n\}$. Given $p\in [0,1]$ we denote by $[n{]}_p$ the random subset of $[n]$ which includes every number with probability $p$, independently of one another. The focus lies on sparse random subsets, i.e.\ when $p=p(n)=o(1)$ as $n\to +\infty$. Let $X_{\ell }$ denote the number of distinct arithmetic progressions of length $\ell$ which are contained in $[n{]}_p$. We determine the limiting distribution for $X_{\ell }$ not only for fixed $\ell \ge 3$ but also when $\ell =\ell (n)\to +\infty$. The main result concerns the joint distribution of the pair $(X_{\ell },X_{{\ell }^{\prime }})$, $\ell >{\ell }^{\prime }$, for which we prove a bivariate central limit theorem for a wide range of $p$. Interestingly, the question of whether the limiting distribution is trivial, degenerate, or non-trivial is characterised by the asymptotic behaviour (as $n\to +\infty$) of the threshold function ${\psi }_{\ell }={\psi }_{\ell }(n):=n{p}^{\ell -1}\ell$. The proofs are based on the method of moments and combinatorial arguments, such as an algorithmic enumeration of collections of arithmetic progressions.

30 pages