{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T23:02:52Z","timestamp":1778540572810,"version":"3.51.4"},"reference-count":31,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2019,11,12]],"date-time":"2019-11-12T00:00:00Z","timestamp":1573516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2020,5,13]]},"abstract":"<jats:p>The relations between (restrictions of) Hindman\u2019s Finite Sums Theorem and (variants of) Ramsey\u2019s 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 [Formula: see text]. Also, we show that Hindman\u2019s Theorem restricted to sums of exactly n elements is equivalent to [Formula: see text] for each [Formula: see text], 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\u2019s Theorem for pairs introduced by Dzhafarov and Hirst. The latter reduces to the former in the technical sense known as strong computable reducibility.<\/jats:p>","DOI":"10.3233\/com-190264","type":"journal-article","created":{"date-parts":[[2019,11,13]],"date-time":"2019-11-13T08:14:47Z","timestamp":1573632887000},"page":"139-153","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":7,"title":["New bounds on the strength of some restrictions of Hindman\u2019s Theorem"],"prefix":"10.1177","volume":"9","author":[{"given":"Lorenzo","family":"Carlucci","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Rome I, Italy."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leszek Aleksander","family":"Ko\u0142odziejczyk","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, University of Warsaw, Poland."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Lepore","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Rome I, Italy."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konrad","family":"Zdanowski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Natural Sciences, Cardinal Stefan Wyszy\u0144ski University in Warsaw, Poland."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2019,11,12]]},"reference":[{"key":"ref001","unstructured":"S.\u00a0Argyros and S.\u00a0Todor\u010devi\u0107, Ramsey Methods in Analysis, Advanced Courses in Mathematics CRM Barcelona, Birkh\u00e4user, Basel-Boston-Berlin, 2005."},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/530\/10439"},{"key":"ref003","first-page":"331","volume":"62","author":"Blass A.","year":"2005","journal-title":"Scientiae Mathematicae Japonicae"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/065\/891245"},{"key":"ref005","unstructured":"L.\u00a0Carlucci, Bounded Hindman\u2019s Theorem and increasing polarized Ramsey\u2019s theorem, In: Logic Blog, A.\u00a0Nies, ed., Part 4, Section\u00a09, 2016, available at: https:\/\/arxiv.org\/abs\/1703.01573."},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-017-0576-1"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/13856"},{"key":"ref008","unstructured":"L.\u00a0Carlucci, L.A.\u00a0Ko\u0142odziejczyk, F.\u00a0Lepore and K.\u00a0Zdanowski, New bounds on the strength of some restrictions of Hindman\u2019s Theorem, in: Unveiling Dynamics and Complexity\u00a0\u2013 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12\u201316, 2017, J.\u00a0Kari, F.\u00a0Manea and I.\u00a0Petre, eds, Proceedings, Lecture Notes in Computer Science, Vol.\u00a010307, Springer, 2017, pp.\u00a0210\u2013220."},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.27"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.3233\/COM-180094"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1254748693"},{"key":"ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50062-1_11"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2014-12261-1"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2016.1"},{"key":"ref015","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-008-0108-0"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-07-04323-1"},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"R.L.\u00a0Graham and B.L.\u00a0Rothschild Ramsey Theory, Wiley, New York, 1990.","DOI":"10.1038\/scientificamerican0790-112"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"issue":"2","key":"ref019","first-page":"341","volume":"36","author":"Hindman N.","year":"1972","journal-title":"Proceedings of the American Mathematical Society"},{"key":"ref020","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(74)90023-5"},{"key":"ref021","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303005716"},{"key":"ref022","unstructured":"D.R.\u00a0Hirschfeldt, Slicing the truth (on the computable and reverse mathematics of combinatorial principles), Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol.\u00a028."},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-011-0257-4"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.2307\/2006985"},{"key":"ref025","unstructured":"F.C.\u00a0Lepore, The effective content and logical strength of Hindman\u2019s finite sums theorem, BSc. Thesis, Computer Science Department, University of Rome I, 2016."},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1309952320"},{"key":"ref027","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71130-3"},{"key":"ref028","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1433-3"},{"key":"ref029","unstructured":"L.\u00a0Patey, Somewhere over the rainbow Ramsey theorem for pairs, Preprint, arXiv:1501.07424."},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90041-3"},{"key":"ref031","doi-asserted-by":"crossref","unstructured":"S.\u00a0Simpson, Subsystems of Second Order Arithmetic, 2nd edn, Cambridge University Press, New York, NY, 2009, Association for Symbolic Logic.","DOI":"10.1017\/CBO9780511581007"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-190264","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-190264","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-190264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:00:12Z","timestamp":1777392012000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-190264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,12]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,5,13]]}},"alternative-id":["10.3233\/COM-190264"],"URL":"https:\/\/doi.org\/10.3233\/com-190264","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,12]]}}}