{
  "id": "1701.06095",
  "version": "v1",
  "published": "2017-01-21T22:52:56.000Z",
  "updated": "2017-01-21T22:52:56.000Z",
  "title": "New bounds on the strength of some restrictions of Hindman's Theorem",
  "authors": [
    "Lorenzo Carlucci",
    "Leszek Aleksander Kołodziejczyk",
    "Francesco Lepore",
    "Konrad Zdanowski"
  ],
  "categories": [
    "math.LO",
    "math.CO"
  ],
  "abstract": "We prove upper and lower bounds on the effective content and logical strength for a variety of natural restrictions of Hindman's Finite Sums Theorem. For example, we show that Hindman's Theorem for sums of length at most 2 and 4 colors implies $\\ACA_0$. An emerging {\\em leitmotiv} is that the known lower bounds for Hindman's Theorem and for its restriction to sums of at most 2 elements are already valid for a number of restricted versions which have simple proofs and better computability- and proof-theoretic upper bounds than the known upper bound for the full version of the theorem. We highlight the role of a sparsity-like condition on the solution set, which we call apartness.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-21T22:52:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hindmans theorem",
      "lower bounds",
      "hindmans finite sums theorem",
      "proof-theoretic upper bounds",
      "colors implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}