2019/02/11 by Barhoumi-Andréani, Yacine, Koch, Christoph, Liu, Hong
#05C80 #11B25 #60C05 #60F05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1902.04176
We study arithmetic progressions \a,a+b,a+2b,…,a+(ℓ-1) b\, with ℓ≥ 3, in random subsets of the initial segment of natural numbers [n]:=\1,2,…, n\. Given p∈[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→+∞. Let X_ℓ denote the number of distinct arithmetic progressions of length ℓ which are contained in [n]p. We determine the limiting distribution for X_ℓ not only for fixed ℓ≥ 3 but also when ℓ=ℓ(n)→+∞. The main result concerns the joint distribution of the pair (Xℓ,Xℓ'), ℓ>ℓ', 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→+∞) of the threshold function ψ_ℓ=ψ_ℓ(n):=npℓ-1ℓ. The proofs are based on the method of moments and combinatorial arguments, such as an algorithmic enumeration of collections of arithmetic progressions.