Bivariate fluctuations for the number of arithmetic progressions in random sets

DOI10.1214/19-EJP391MaRDI QIDQ2285791zbMATH OpenOpenAlexFDO

Authors Yacine Barhoumi-Andréani, Christoph Koch, Hong Liu

Publication date 9 January 2020

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.04176, https://projecteuclid.org/euclid.ejp/1577502322

zbMATH Keywords

arithmetic progressionbivariate fluctuationscentral limit theoremexploration processmethod of moments

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Arithmetic progressions (11B25) Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

Abstract: We study arithmetic progressions $a,a+b,a+2b,dots,a+(ell-1)b$, with $ellge3$, in random subsets of the initial segment of natural numbers $[n]:=1,2,dots,n$. Given $pin[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 $no+infty$. Let $X_{e}ll$ denote the number of distinct arithmetic progressions of length $ell$ which are contained in $[n{]}_p$. We determine the limiting distribution for $X_{e}ll$ not only for fixed $ellge3$ but also when $ell=ell(n)o+infty$. The main result concerns the joint distribution of the pair $(X_{ell},X_{el{l}^{\prime }})$, $ell>el{l}^{\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 $no+infty$) of the threshold function $ps{i}_{e}ll=ps{i}_{e}ll(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.

Recommendations

• Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\)
• Arithmetic progressions of length three in subsets of a random set
• Maximal arithmetic progressions in random subsets
• Upper tail large deviations for arithmetic progressions in a random set
• On the maximal length of arithmetic progressions

Cites work

• A transition of limiting distributions of large matchings in random graphs
• An introduction to large deviations for random graphs
• Arithmetic progressions of length three in subsets of a random set
• Combinatorial theorems in sparse random sets
• Distributions of sparse spanning subgraphs in random graphs
• Extremal results for random discrete structures
• Gaussian width bounds with applications to arithmetic progressions in random settings
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• scientific article; zbMATH DE number 4215043 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 3071148 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Jigsaw percolation on random hypergraphs
• Nonlinear large deviations
• Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs
• On random simplices in product distributions
• On sets of integers containing k elements in arithmetic progression
• On the probability of nonexistence in binomial subsets
• The eigenvalues of random symmetric matrices
• The infamous upper tail
• The lower tail: Poisson approximation revisited
• The primes contain arbitrarily long arithmetic progressions
• Threshold functions and Poisson convergence for systems of equations in random sets
• To Prove and Conjecture: Paul Erdos and His Mathematics
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Upper tail large deviations for arithmetic progressions in a random set
• Upper tails for arithmetic progressions in random subsets
• Upper tails for subgraph counts in random graphs
• Weighted dependency graphs
• When are small subgraphs of a random graph normally distributed?

Cited in

(6)

• Upper tails for arithmetic progressions in random subsets
• Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\)
• Normal limiting distributions for systems of linear equations in random sets
• Upper tails via high moments and entropic stability
• Maximal arithmetic progressions in random subsets
• Deviation probabilities for arithmetic progressions and irregular discrete structures

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Bivariate fluctuations for the number of arithmetic progressions in random sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285791)