Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application

Technical Summary: "Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application"

Problem Statement
The paper addresses the computability-theoretic complexity of Hindman's Theorem (HT), specifically concerning the strength of the solutions it produces relative to the input coloring. Hindman's Theorem states that for every finite coloring of the natural numbers $\mathbb{N}$, there exists an infinite set $H$ such that the set of all non-empty finite sums of distinct elements of $H$ (denoted $FS(H)$) is monochromatic.

Prior work established the following bounds:

1. Upper Bound: Blass, Hirst, and Simpson (1987) proved that for every computable coloring, there exists a solution computable from the $\omega$-jump of the empty set, $\emptyset^{(\omega)}$.
2. Lower Bound: The same authors proved that there exists a computable coloring where every solution computes the halting set $\emptyset'$. Later, Liao (2026) improved this to show that for some computable colorings, no $\Pi^0_3$ solution exists.

The central open question addressed by this paper is whether the upper bound of $\emptyset^{(\omega)}$ is optimal for a single application of the theorem. Specifically, does every arithmetic instance of Hindman's Theorem admit a solution that does not compute $\emptyset^{(\omega)}$?

Methodology
The authors employ a forcing technique adapted from Towsner's combinatorial proof of Hindman's Theorem. The methodology involves the following components:

1. Reformulation: The problem is translated into the language of the Finite Union Theorem (FUT), which is computably equivalent to HT. This involves coloring the set of non-empty finite subsets of $\mathbb{N}$, $P_{fin}(\mathbb{N})$, and seeking an infinite block sequence $H$ such that the set of finite unions $FU(H)$ is monochromatic.
2. Towsner Trees and Matching: The authors utilize Towsner's concepts of "half-match" and "full-match." A finite set $F$ half-matches an infinite block sequence $X$ if for every finite union $b \in FU(X)$, there is an $a \in F$ such that $f(a \cup b) = f(b)$. A full-match requires $f(a) = f(a \cup b) = f(b)$.
   • They construct a "Towsner sequence," a nested sequence of half-matches inducing a tree structure (the Towsner tree).
   • They establish that for an arithmetic coloring $f$, an $f''$-computable Towsner sequence exists.
3. Forcing Notion: A new notion of forcing is defined using "P-conditions," which are pairs $(I, X)$ where $I$ is a finite set of block sequences and $X$ is an infinite reservoir. A condition is "f-matching" if it satisfies a specific extension property related to the coloring.
4. First-Jump Control: The core innovation is the design of a "forcing question" with specific definability properties. This allows the construction of a generic filter where the resulting solution $G$ avoids computing a specific non-arithmetic set $C$. The forcing relation is designed to control the first jump of the solution, ensuring that the solution remains within a specific arithmetic degree relative to the input, while avoiding the target cone.
5. Diagonalization: To ensure $C \not\leq_T G$, the authors satisfy requirements $R^C_e: W^G_e \neq C$. By analyzing the forcing question for $\Sigma^0_1$ formulas, they demonstrate that for any non-arithmetic set $C$ and arithmetic coloring, one can extend conditions to force $G$ to differ from $C$ on some element.

Key Contributions and Results

1. Main Theorem (Cone Avoidance): The primary result (Main Theorem 1.5) states: Let $C$ be a set of non-arithmetic degree. For every $\ell \geq 1$ and every coloring $f: \mathbb{N} \to \ell$ (or $P_{fin}(\mathbb{N}) \to \ell$) of arithmetic degree, there exists an infinite set $H$ such that $FS(H)$ is $f$-monochromatic and $C \not\leq_T H$.

   • Corollary: By setting $C = \emptyset^{(\omega)}$, the authors prove that every arithmetic instance of Hindman's Theorem admits a solution that does not compute $\emptyset^{(\omega)}$. This demonstrates that the computability-theoretic upper bound of $\emptyset^{(\omega)}$ is not optimal for a single application.

2. Limitations of Iteration: The authors clarify that this result does not imply Hindman's Theorem is weaker than $\text{ACA}^+_0$ in reverse mathematics. The cone avoidance holds for Turing reducibility ($C \not\leq_T H$) but not necessarily for arithmetic reducibility. Therefore, the theorem cannot be iterated to build an $\omega$-model of Hindman's Theorem that excludes $\emptyset^{(\omega)}$.

3. Simple Colorings: The paper investigates restrictions of HT to "simple colorings" (colorings where the color of a union depends only on the color of the components and their relative positions).

   • They prove that the restriction of the Finite Union Theorem to simple colorings is equivalent to $\text{ACA}_0$ over $\text{RCA}_0$.
   • They show that the specific coloring used by Blass, Hirst, and Simpson to prove the lower bound (based on "very short gaps") is a simple coloring.

4. Complexity of Towsner Trees: The authors prove (Proposition 2.24) that for the specific coloring constructed by Blass, Hirst, and Simpson, every Towsner sequence computes $\emptyset'$. This suggests that while Towsner trees are a powerful tool, their existence for certain computable colorings inherently encodes significant computational power, though this does not preclude the existence of other proofs or full-matches that do not rely on such trees.

Significance
The paper resolves the question of whether the $\emptyset^{(\omega)}$ upper bound is tight for single applications of Hindman's Theorem. By proving that non-arithmetic cones can be avoided, the authors show that the theorem does not inherently require the full strength of the $\omega$-jump to produce a solution for arithmetic inputs. This refines the understanding of the theorem's computational content, distinguishing between the complexity required to find a solution versus the complexity required to find a solution that computes specific high-degree sets. The work also bridges combinatorial proofs (Towsner's) with forcing techniques to achieve precise control over the Turing degrees of the solutions.