{
  "id": "0711.0185",
  "version": "v1",
  "published": "2007-11-01T18:56:56.000Z",
  "updated": "2007-11-01T18:56:56.000Z",
  "title": "The true complexity of a system of linear equations",
  "authors": [
    "W. T. Gowers",
    "J. Wolf"
  ],
  "comment": "30 pages",
  "doi": "10.1112/plms/pdp019",
  "categories": [
    "math.NT",
    "math.CO"
  ],
  "abstract": "It is well-known that if a subset A of a finite Abelian group G satisfies a quasirandomness property called uniformity of degree k, then it contains roughly the expected number of arithmetic progressions of length k, that is, the number of progressions one would expect in a random subset of G of the same density as A. One is naturally led to ask which degree of uniformity is required of A in order to control the number of solutions to a general system of linear equations. Using so-called \"quadratic Fourier analysis\", we show that certain linear systems that were previously thought to require quadratic uniformity are in fact governed by linear uniformity. More generally, we conjecture a necessary and sufficient condition on a linear system L which guarantees that any subset A of F_p^n which is uniform of degree k contains the expected number of solutions to L.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-11-01T18:56:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear equations",
      "true complexity",
      "linear system",
      "uniformity",
      "finite abelian group"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0711.0185G"
    }
  }
}