The adjacent Hindman’s theorem and the ℤ \mathbb{Z} -Ramsey’s theorem

Bruno Fernando Aceves-Martínez, David J. Fernández-Bretón, L. F. Romero-García, Luis F. Villagómez-Canela · 2024

Read The adjacent Hindman’s theorem and the ℤ \mathbb{Z} -Ramsey’s theorem by Bruno Fernando Aceves-Martínez, David J. Fernández-Bretón, L. F. Romero-García, Luis F. Villagómez-Canela (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14558.txt.

Introduction

Bruno Fernando Aceves-Martínez and co-authors compare two math statements about patterns in whole numbers in a 2024 paper. Ramsey theory studies patterns forced by any coloring of number pairs. One restricted form uses only colorings that ignore shifts. Hindman type results promise sums inside one color class.

The team shows the restricted Ramsey form and the adjacent Hindman statement carry equal strength. The verdict holds under two lenses, proof strength and computing power. Higher dimensional cousins of both statements get the same treatment. Such matches help logicians sort the hidden cost of pattern theorems. The work ties two lines of combinatorics into one neat equivalence.

Catalog record

CREATORBruno Fernando Aceves-Martínez, David J. Fernández-Bretón, L. F. Romero-García, Luis F. Villagómez-Canela
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14558

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The adjacent Hindman’s theorem and the ℤ \mathbb{Z} -Ramsey’s theorem Bruno Fernando Aceves-Martínez, David J. Fernández-Bretón, L. F. Romero-García, Luis F. Villagómez-Canela Abstract . We consider the restriction of Ramsey’s theorem that arises from considering only translation-invariant colourings of pairs, and show that this has the same strength (both from the viewpoint of Reverse Mathematics and from the viewpoint of Computability Theory) as the Adjacent Hindman’s Theorem , proposed by L. Carlucci (Arch. Math. Log. 57 (2018), 381–359). We also investigate some higher dimensional versions of both of these statements. 2020 Mathematics Subject Classification Primary 03F35, 03D30, Secondary 05D10. 1. Introduction In this paper, we consider some Ramsey-theoretic combinatorial results from the perspective of both Computability Theory and Reverse Mathematics. Ramsey’s theorem in dimension n , denoted \mathnormal{\mathsf{RT}}^{n} ( n\geq 1 ), is the statement that for every c:[\mathbb{N}]^{n}\longrightarrow k (where k , an arbitrary finite number, is used to denote the set \{0,\ldots,k-1\} ), there exists an infinite set X\subseteq\mathbb{N} such that [X]^{n} is c -monochromatic. On the other hand, Hindman’s theorem, denoted \mathnormal{\mathsf{HT}} , is the statement that for every c:\mathbb{N}\longrightarrow k there exists an infinite set X\subseteq\mathbb{N} such that the set \fs(X)=\left\{\sum_{x\in F}x\bigg|F\subseteq X\text{ is finite and nonempty}\right\} is c -monochromatic. These two principles have been extensively studied, and constitute an important vein of contemporary research in the interface between combinatorics and (various branches of) logic. In order to mention some previous results, we proceed to briefly describe the systems involved. \mathnormal{\mathsf{RCA}}_{0} is a subsystem of Second-Order Arithmetic that, roughly speaking, has Peano Arithmetic as its first-order part, and includes closure under relative computability as its second-order part. \mathnormal{\mathsf{WKL}}_{0} is \mathnormal{\mathsf{RCA}}_{0} plus closure under taking an infinite branch of each binary tree (i.e. the statement of König’s Lemma, restricted to binary trees, holds), and \mathnormal{\mathsf{ACA}}_{0} is \mathnormal{\mathsf{RCA}}_{0} plus closure under taking Turing jumps. It is well-known that \mathnormal{\mathsf{ACA}}_{0} is strictly stronger than \mathnormal{\mathsf{WKL}}_{0} , which in turn is strictly stronger than \mathnormal{\mathsf{RCA}}_{0} . The reader might consult [ 14 ] for a thorough introduction to this area of research, or [ 9 ] for a treatment more readily oriented to the three systems that we just mentioned and their relationship to Ramsey theory in general. Nowadays, it is known that, if n\geq 3 , then \mathnormal{\mathsf{RT}}^{n} is equivalent to \mathnormal{\mathsf{ACA}}_{0} over \mathnormal{\mathsf{RCA}}_{0} ; somewhat surprisingly, \mathnormal{\mathsf{RT}}^{2} is a principle at the same time strictly weaker than \mathnormal{\mathsf{ACA}}_{0} and incomparable with than \mathnormal{\mathsf{WKL}}_{0} , whereas \mathnormal{\mathsf{RT}}^{1} is simply the pigeonhole principle (strictly stronger than plain \mathnormal{\mathsf{RCA}}_{0} but much weaker than \mathnormal{\mathsf{WKL}}_{0} ). These results are classical, although the interested reader can consult, e.g., [ 7 ] (especially Corollaries 8.2.6 and 8.6.2) for a more contemporary source. On the other hand, it is also known that, again over \mathnormal{\mathsf{RCA}}_{0} , \mathnormal{\mathsf{ACA}}_{0}^{+} implies \mathnormal{\mathsf{HT}} which in turn implies \mathnormal{\mathsf{ACA}}_{0} , where \mathnormal{\mathsf{ACA}}_{0}^{+} is essentially \mathnormal{\mathsf{ACA}}_{0} plus closure under the \omega -th Turing jump; these last results are due to Blass, Hirst and Simpson [ 1 ] . The precise strength of \mathnormal{\mathsf{HT}} in the hierarchy of reverse-mathematical principles is still unknown, and determining this strength is currently one of the important open problems in Reverse Mathematics. A good overview of the state of the art regarding this problem can be found in [ 3 ] . With the finer distinctions provided by Computability Theory, especially the theory of Turing reducibility, one can be more precise about the results just mentioned. For example, for Ramsey’s theorem, it is known [ 10 ] that for every instance c of the problem (that is, every colouring) there exists a solution (a set that is monochromatic for the colouring in question) X such that X\leq_{T}c^{(2n+2)} , the (2n+2) -fold Turing jump of c ; on the other hand, there is a computable instance c of Ramsey’s theorem such that every solution X satisfies \varnothing^{(n-2)}\leq_{T}X . In the case of Hindman’s theorem, it is known [ 1 ] that there are computable instances c to the theorem such that every monochromatic solution X satisfies \varnothing^{\prime}\leq_{T}X whereas every instance c of the theorem admits a solution X such that X\leq_{T}c^{(\omega+1)} . In this paper, we consider certain restrictions of Hindman’s theorem and of Ramsey’s theorem. On the front of Hindman’s theorem, we shall work with L. Carlucci’s Adjacent Hindman’s Theorem proposed in [ 2 ] , which results from restricting the monochromaticity requirement not to a full set \fs(X) but rather to the restricted set \afs(X) of adjacent finite sums, meaning those sums of finitely many consecutive elements of X when ordered increasingly, leaving no gaps. Carlucci showed that, over \mathnormal{\mathsf{RCA}}_{0} , \mathnormal{\mathsf{RT}}^{2} implies \mathnormal{\mathsf{AHT}} , even with an extra condition that we will also consider, called apartness . On the other hand, we will consider a restriction of Ramsey’s theorem that arises from restricting the allowable problems for which we require a solution —concretely, stating the theorem only for those colourings that are invariant under the translation action of \mathbb{Z} , obtaining what we will call the \mathbb{Z} -Ramsey’s theorem . Although this principle has not been previously studied within Reverse Mathematics, the idea of restricting instances of Ramsey’s theorem only to translation-invariant colourings has already been used, e.g., by Petrenko and Protasov in their definition of \mathbb{Z} -Ramsey ultrafilters [ 13 ] . Many of the principles mentioned in the previous paragraph turn out to be equivalent to \mathnormal{\mathsf{ACA}}_{0} over \mathnormal{\mathsf{RCA}}_{0} , so for the most part the viewpoint of Reverse Mathematics will not be very informative in that respect. In view of this, we focus more on the Computability-theoretic aspect of the principles, thinking instead about the reducibility relation, by means of which an instance of one problem can be turned into an instance of a different problem and a solution to the latter gets turned back into a solution to the original instance. More concretely, we will work with Weihrauch reducibility 1 1 1 Some authors (e.g., [ 9 , p. 22] ) have called this notion uniform reducibility , but the name “Weihrauch reducibility” seems to be the most commonly used nowadays. We are grateful to two anonymous referees for this observation. . Recall [ 7 , Definition 4.3.1] that a problem P is Weihrauch reducible to another problem Q , denoted P\mathop{\leq_{\mathsf{W}}}Q , if there are Turing functionals \Phi,\Psi such that for every instance X of P , \Phi^{X} is an instance of Q , and for every solution Y to \Phi^{X} , \Psi^{X\oplus Y} is a solution to X . If we have the exact same situation, but with a Turing functional \Psi such that \Psi^{Y} is a solution to X (i.e. we may compute the solution to X just with information from Y without needing to use any information about X ), then we say that P is strongly Weihrauch reducible [ 7 , Definition 4.4.1] to Q and write P\mathop{\leq_{\mathrm{s}\mathsf{W}}}Q . If each of the problems P,Q is Weihrauch reducible (respectively, strongly Weihrauch reducible) to the other, then we say that P is Weihrauch equivalent (respectively, strongly Weihrauch equivalent ) to Q and we denote this by P\mathop{\equiv_{\mathsf{W}}}Q (respectively, P\mathop{\equiv_{\mathrm{s}\mathsf{W}}}Q ). So we will use this notion of reducibility to gauge the position of the Adjacent Hindman’s

Read the complete text