{
  "id": "2004.13690",
  "version": "v1",
  "published": "2020-04-28T17:46:21.000Z",
  "updated": "2020-04-28T17:46:21.000Z",
  "title": "Tower-type bounds for Roth's theorem with popular differences",
  "authors": [
    "Jacob Fox",
    "Huy Tuan Pham",
    "Yufei Zhao"
  ],
  "comment": "29 pages",
  "categories": [
    "math.CO",
    "math.NT"
  ],
  "abstract": "Green developed an arithmetic regularity lemma to prove a strengthening of Roth's theorem on arithmetic progressions in dense sets. It states that for every $\\epsilon > 0$ there is some $N_0(\\epsilon)$ such that for every $N \\ge N_0(\\epsilon)$ and $A \\subset [N]$ with $|A| = \\alpha N$, there is some nonzero $d$ such that $A$ contains at least $(\\alpha^3 - \\epsilon) N$ three-term arithmetic progressions with common difference $d$. We prove that the minimum $N_0(\\epsilon)$ in Green's theorem is an exponential tower of 2s of height on the order of $\\log(1/\\epsilon)$. Both the lower and upper bounds are new. It shows that the tower-type bounds that arise from the use of a regularity lemma in this application are quantitatively necessary.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-28T17:46:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "roths theorem",
      "tower-type bounds",
      "popular differences",
      "arithmetic regularity lemma",
      "three-term arithmetic progressions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}