Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


``Weak yet strong'' restrictions of Hindman's Finite Sums Theorem

Author: Lorenzo Carlucci
Journal: Proc. Amer. Math. Soc. 146 (2018), 819-829
MSC (2010): Primary 03D80, 05P10; Secondary 03F35
Published electronically: September 28, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present a natural restriction of Hindman's Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman's Theorem with analogous properties.

References [Enhancements On Off] (What's this?)

  • [1] Andreas Blass, Some questions arising from Hindman's theorem, Sci. Math. Jpn. 62 (2005), no. 2, 331-334. MR 2179959
  • [2] Andreas R. Blass, Jeffry L. Hirst, and Stephen G. Simpson, Logical analysis of some theorems of combinatorics and topological dynamics, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 125-156. MR 891245,
  • [3] A. T. Brauer, Über Sequenzen von Potenzresten, Sitz. Ber. Preuss. Akad. Wiss., Phys. -math. Klasse (1928), pp. 9-16.
  • [4] L. Carlucci. A weak variant of Hindman's Theorem stronger than Hilbert's Theorem, Archive for Mathematical Logic, to appear.
  • [5] Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey's theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1-55. MR 1825173,
  • [6] D. Dzhafarov, C. G. Jockusch, R. Solomon, and L. B. Westrick, Effectiveness of Hindman's Theorem for bounded sums. In A. Day, M. Fellows, N. Greenberg, B. Khoussainov, and A. Melnikov, eds., Proceedings of the International Symposium on Computability and Complexity (in honour of Rod Downey's 60th birthday), Lecture Notes in Computer Science, Springer, pp. 134-142. Springer (2017).
  • [7] Harvey Friedman and Stephen G. Simpson, Issues and problems in reverse mathematics, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 127-144. MR 1770738,
  • [8] Emanuele Frittaion, Brown's lemma in second-order arithmetic, Fund. Math. 238 (2017), no. 3, 269-283. MR 3654099,
  • [9] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, Wiley-Interscience Series in Discrete Mathematics, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1980. MR 591457
  • [10] Neil Hindman, The existence of certain ultra-filters on $ N$ and a conjecture of Graham and Rothschild, Proc. Amer. Math. Soc. 36 (1972), 341-346. MR 0307926,
  • [11] Neil Hindman, Finite sums from sequences within cells of a partition of $ N$, J. Combinatorial Theory Ser. A 17 (1974), 1-11. MR 0349574
  • [12] Neil Hindman, Imre Leader, and Dona Strauss, Open problems in partition regularity, Special issue on Ramsey theory, Combin. Probab. Comput. 12 (2003), no. 5-6, 571-583. MR 2037071,
  • [13] Denis R. Hirschfeldt, Slicing the truth, On the computable and reverse mathematics of combinatorial principles. Edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin and Yue Yang, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. MR 3244278
  • [14] Jeffry L. Hirst, Hilbert versus Hindman, Arch. Math. Logic 51 (2012), no. 1-2, 123-125. MR 2864401,
  • [15] Carl G. Jockusch Jr., Ramsey's theorem and recursion theory, J. Symbolic Logic 37 (1972), 268-280. MR 0376319,
  • [16] Antonio Montalbán, Open questions in reverse mathematics, Bull. Symbolic Logic 17 (2011), no. 3, 431-454. MR 2856080,
  • [17] Hans Jürgen Prömel, Ramsey theory for discrete structures, with a foreword by Angelika Steger, Springer, Cham, 2013. MR 3157030
  • [18] Jon Henry Sanders, A generalization of Schur's Theorem, ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)-Yale University, 1968. MR 2617864
  • [19] Y. Setyawan, Combinatorial number theory: Results of Hilbert, Schur, Folkman, and Hindman., Thesis (M.Sc.), Simon Fraser University, 1998.
  • [20] I. Schur, Über die Kongruenze $ x^m+y^m \cong z^m (\mathrm {mod}\, p)$, Jber. Deutsch. Math.-Verein. 25 (1916), 114-117.
  • [21] Saharon Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), no. 3, 683-697. MR 929498,
  • [22] Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689
  • [23] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212-216.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D80, 05P10, 03F35

Retrieve articles in all journals with MSC (2010): 03D80, 05P10, 03F35

Additional Information

Lorenzo Carlucci
Affiliation: Dipartimento di Informatica, Sapienza Università di Roma Via Ariosto 25, 00185 Rome, Italy

Received by editor(s): November 4, 2016
Received by editor(s) in revised form: March 29, 2017
Published electronically: September 28, 2017
Additional Notes: The work was done partially while the author was visiting the Institute for Mathematical Sciences, National University of Singapore in 2016. The visit was supported by the Institute.
Communicated by: Mirna Džamonja
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society