2024/09/12 by Matan Harel, Harel, Matan, Frank Mousset +3
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #History and Theory of Mathematics #Mathematical and Theoretical Analysis #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2409.08383
openalex publication_date 2024/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let X be the number of k-term arithmetic progressions contained in the p-biased random subset of the first N positive integers. We give asymptotically sharp estimates on the logarithmic upper-tail probability log Pr(X ≥ E[X] + t) for all Ω(N-2/k) ≤ p ≪ 1 and all t ≫ √(Var(X)), excluding only a few boundary cases. In particular, we show that the space of parameters (p,t) is partitioned into three phenomenologically distinct regions, where the upper-tail probabilities either resemble those of Gaussian or Poisson random variables, or are naturally described by the probability of appearance of a small set that contains nearly all of the excess t progressions. We employ a variety of tools from probability theory, including classical tilting arguments and martingale concentration inequalities. However, the main technical innovation is a combinatorial result that establishes a stronger version of `entropic stability' for sets with rich arithmetic structure.