{
  "id": "math/0703108",
  "version": "v1",
  "published": "2007-03-05T16:12:36.000Z",
  "updated": "2007-03-05T16:12:36.000Z",
  "title": "Discrepancy of Sums of two Arithmetic Progressions",
  "authors": [
    "Nils Hebbinghaus"
  ],
  "comment": "15 pages, 0 figures",
  "categories": [
    "math.NT"
  ],
  "abstract": "Estimating the discrepancy of the hypergraph of all arithmetic progressions in the set $[N]=\\{1,2,\\hdots,N\\}$ was one of the famous open problems in combinatorial discrepancy theory for a long time. An extension of this classical hypergraph is the hypergraph of sums of $k$ ($k\\geq 1$ fixed) arithmetic progressions. The hyperedges of this hypergraph are of the form $A_{1}+A_{2}+\\hdots+A_{k}$ in $[N]$, where the $A_{i}$ are arithmetic progressions. For this hypergraph Hebbinghaus (2004) proved a lower bound of $\\Omega(N^{k/(2k+2)})$. Note that the probabilistic method gives an upper bound of order $O((N\\log N)^{1/2})$ for all fixed $k$. P\\v{r}\\'{i}v\\v{e}tiv\\'{y} improved the lower bound for all $k\\geq 3$ to $\\Omega(N^{1/2})$ in 2005. Thus, the case $k=2$ (hypergraph of sums of two arithmetic progressions) remained the only case with a large gap between the known upper and lower bound. We bridge his gap (up to a logarithmic factor) by proving a lower bound of order $\\Omega(N^{1/2})$ for the discrepancy of the hypergraph of sums of two arithmetic progressions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-03-05T16:12:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11K38"
    ],
    "keywords": [
      "arithmetic progressions",
      "lower bound",
      "combinatorial discrepancy theory",
      "long time",
      "famous open problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007math......3108H"
    }
  }
}