{
  "id": "2409.08383",
  "version": "v1",
  "published": "2024-09-12T20:17:48.000Z",
  "updated": "2024-09-12T20:17:48.000Z",
  "title": "Upper tails for arithmetic progressions revisited",
  "authors": [
    "Matan Harel",
    "Frank Mousset",
    "Wojciech Samotij"
  ],
  "comment": "51 pages, 1 figure",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "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 \\ge E[X] + t)$ for all $\\Omega(N^{-2/k}) \\le p \\ll 1$ and all $t \\gg \\sqrt{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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-09-12T20:17:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "upper tails",
      "poisson random variables",
      "term arithmetic progressions",
      "rich arithmetic structure",
      "martingale concentration inequalities"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 51,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}