New bounds on the strength of some restrictions of Hindman’s Theorem

Article type: Research Article

Authors: Carlucci, Lorenzo^{a; *} | Kołodziejczyk, Leszek Aleksander^b | Lepore, Francesco^c | Zdanowski, Konrad^d

Affiliations: [a] Department of Computer Science, University of Rome I, Italy. carlucci@di.uniroma1.it | [b] Institute of Mathematics, University of Warsaw, Poland. lak@mimuw.edu.pl | [c] Department of Computer Science, University of Rome I, Italy. lepore90@gmail.com | [d] Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszyński University in Warsaw, Poland. k.zdanowski@uksw.edu.pl

Correspondence: [*] Corresponding author. carlucci@di.uniroma1.it.

Abstract: The relations between (restrictions of) Hindman’s Finite Sums Theorem and (variants of) Ramsey’s Theorem give rise to long-standing open problems in combinatorics, computability theory and proof theory. We present some results motivated by these open problems. In particular we investigate the restriction of the Finite Sums Theorem to sums of at most two elements, which is the subject of a long-standing open question by Hindman, Leader and Strauss. We show that this restriction has the same proof-theoretic and computability-theoretic lower bound that is known to hold for the full version of the Finite Sums Theorem. In terms of reverse mathematics it implies ACA0. Also, we show that Hindman’s Theorem restricted to sums of exactly n elements is equivalent to ACA0 for each n⩾3, provided a certain sparsity condition is imposed on the solution set. The same results apply to bounded versions of the Finite Union Theorem, in which such a sparsity condition is already built-in. Further we show that the Finite Sums Theorem for sums of at most two elements is tightly connected to the Increasing Polarized Ramsey’s Theorem for pairs introduced by Dzhafarov and Hirst. The latter reduces to the former in the technical sense known as strong computable reducibility.

Keywords: Reverse mathematics, Hindman’s Theorem, Finite Unions Theorem

DOI: 10.3233/COM-190264

Journal: Computability, vol. 9, no. 2, pp. 139-153, 2020