Effectiveness of hindman’s theorem for bounded sums

Damir D. Dzhafarov, Carl G. Jockusch, Reed Solomon, Linda Brown Westrick

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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 HT≤nk denote the assertion that for each k-coloring c of ℕ there is an infinite set X ⊆ ℕ such that all sums ΣxF x for F ⊆ X and 0 < |F| ≤ n have the same color. We prove that there is a computable 2-coloring c of ℕ 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 HT≤22is not provable in RCA0 and in fact we show that it implies SRT22in RCA0 +BΠ01. We also show that there is a computable instance of HT≤33with all solutions computing 0′. The proof of this result shows that HT≤33 implies ACA0 in RCA0.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Effectiveness of hindman’s theorem for bounded sums'. Together they form a unique fingerprint.

Cite this