{
  "id": "1603.08249",
  "version": "v1",
  "published": "2016-03-27T19:45:01.000Z",
  "updated": "2016-03-27T19:45:01.000Z",
  "title": "Effectiveness of Hindman's theorem for bounded sums",
  "authors": [
    "Damir D. Dzhafarov",
    "Carl G. Jockusch, Jr.",
    "Reed Solomon",
    "Linda Brown Westrick"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "We consider the strength and effective content of restricted versions of Hindman's Theorem in which the number of colors is specified and the length of the sums has a specified finite bound. Let $\\mathsf{HT}^{\\leq n}_k$ denote the assertion that for each $k$-coloring $c$ of $\\mathbb{N}$ there is an infinite set $X \\subseteq \\mathbb{N}$ such that all sums $\\sum_{x \\in F} x$ for $F \\subseteq X$ and $0 < |F| \\leq n$ have the same color. We prove that there is a computable $2$-coloring $c$ of $\\mathbb{N}$ such that there is no infinite computable set $X$ such that all nonempty sums of at most $2$ elements of $X$ have the same color. It follows that $\\mathsf{HT}^{\\leq 2}_2$ is not provable in $\\mathsf{RCA}_0$ and in fact we show that it implies $\\mathsf{SRT}^2_2$ in $\\mathsf{RCA}_0$. We also show that there is a computable instance of $\\mathsf{HT}^{\\leq 3}_3$ with all solutions computing $0'$. The proof of this result shows that $\\mathsf{HT}^{\\leq 3}_3$ implies $\\mathsf{ACA}_0$ in $\\mathsf{RCA}_0$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-27T19:45:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hindmans theorem",
      "bounded sums",
      "effectiveness",
      "infinite set",
      "specified finite bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160308249D"
    }
  }
}