“Weak yet strong” restrictions of Hindman’s Finite Sums Theorem

Carlucci, Lorenzo

doi:10.1090/proc/13856

“Weak yet strong” restrictions of Hindman’s Finite Sums Theorem
HTML articles powered by AMS MathViewer

by Lorenzo Carlucci PDF

Proc. Amer. Math. Soc. 146 (2018), 819-829 Request permission

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

Andreas Blass, Some questions arising from Hindman’s theorem, Sci. Math. Jpn. 62 (2005), no. 2, 331–334. MR 2179959
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, DOI 10.1090/conm/065/891245
A. T. Brauer, Über Sequenzen von Potenzresten, Sitz. Ber. Preuss. Akad. Wiss., Phys. -math. Klasse (1928), pp. 9–16.
L. Carlucci. A weak variant of Hindman’s Theorem stronger than Hilbert’s Theorem, Archive for Mathematical Logic, to appear.
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, DOI 10.2307/2694910
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).
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, DOI 10.1090/conm/257/04031
Emanuele Frittaion, Brown’s lemma in second-order arithmetic, Fund. Math. 238 (2017), no. 3, 269–283. MR 3654099, DOI 10.4064/fm221-9-2016
Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1980. MR 591457
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 307926, DOI 10.1090/S0002-9939-1972-0307926-0
Neil Hindman, Finite sums from sequences within cells of a partition of $N$, J. Combinatorial Theory Ser. A 17 (1974), 1–11. MR 349574, DOI 10.1016/0097-3165(74)90023-5
Neil Hindman, Imre Leader, and Dona Strauss, Open problems in partition regularity, Combin. Probab. Comput. 12 (2003), no. 5-6, 571–583. Special issue on Ramsey theory. MR 2037071, DOI 10.1017/S0963548303005716
Denis R. Hirschfeldt, Slicing the truth, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. 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. MR 3244278
Jeffry L. Hirst, Hilbert versus Hindman, Arch. Math. Logic 51 (2012), no. 1-2, 123–125. MR 2864401, DOI 10.1007/s00153-011-0257-4
Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
Antonio Montalbán, Open questions in reverse mathematics, Bull. Symbolic Logic 17 (2011), no. 3, 431–454. MR 2856080, DOI 10.2178/bsl/1309952320
Hans Jürgen Prömel, Ramsey theory for discrete structures, Springer, Cham, 2013. With a foreword by Angelika Steger. MR 3157030, DOI 10.1007/978-3-319-01315-2
Jon Henry Sanders, A GENERALIZATION OF SCHUR’S THEOREM, ProQuest LLC, Ann Arbor, MI, 1968. Thesis (Ph.D.)–Yale University. MR 2617864
Y. Setyawan, Combinatorial number theory: Results of Hilbert, Schur, Folkman, and Hindman., Thesis (M.Sc.), Simon Fraser University, 1998.
I. Schur, Über die Kongruenze $x^m+y^m \cong z^m (\mathrm {mod}\, p)$, Jber. Deutsch. Math.-Verein. 25 (1916), 114–117.
Saharon Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), no. 3, 683–697. MR 929498, DOI 10.1090/S0894-0347-1988-0929498-X
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, DOI 10.1017/CBO9780511581007
B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212–216.