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

Résumé technique : « Le théorème de Hindman ne code pas $\emptyset^{(\omega)}$ en une seule application »

Énoncé du problème
L'article traite de la complexité de la théorie de la calculabilité du théorème de Hindman (HT), plus précisément concernant la force des solutions qu'il produit par rapport à la coloration d'entrée. Le théorème de Hindman stipule que pour tout coloriage fini des entiers naturels $\mathbb{N}$, il existe un ensemble infini $H$ tel que l'ensemble de toutes les sommes finies non vides d'éléments distincts de $H$ (noté $FS(H)$) est monochromatique.

Les travaux antérieurs ont établi les bornes suivantes :

1. Borne supérieure : Blass, Hirst et Simpson (1987) ont prouvé que pour tout coloriage calculable, il existe une solution calculable à partir de la sur-saut $\omega$ de l'ensemble vide, $\emptyset^{(\omega)}$.
2. Borne inférieure : Les mêmes auteurs ont prouvé qu'il existe un coloriage calculable où chaque solution calcule l'ensemble de l'arrêt $\emptyset'$. Plus tard, Liao (2026) a amélioré cela en montrant que pour certains colorings calculables, aucune solution $\Pi^0_3$ n'existe.

La question ouverte centrale abordée par cet article est de savoir si la borne supérieure de $\emptyset^{(\omega)}$ est optimale pour une application unique du théorème. Plus précisément, est-ce que toute instance arithmétique du théorème de Hindman admet une solution qui ne calcule pas $\emptyset^{(\omega)}$ ?

Méthodologie
Les auteurs utilisent une technique de forcing adaptée de la preuve combinatoire de Hindman par Towsner. La méthodologie comprend les composantes suivantes :

1. Reformulation : Le problème est traduit dans le langage du théorème des unions finies (FUT), qui est calculablement équivalent à HT. Cela implique de colorier l'ensemble des sous-ensembles finis non vides de $\mathbb{N}$, $P_{fin}(\mathbb{N})$, et de chercher une suite de blocs infinie $H$ telle que l'ensemble des unions finies $FU(H)$ soit monochromatique.
2. Arbres de Towsner et correspondance (Matching) : Les auteurs utilisent les concepts de « demi-correspondance » (half-match) et de « pleine correspondance » (full-match) de Towsner. Un ensemble fini $F$ est en demi-correspondance avec une suite de blocs infinie $X$ si pour toute union finie $b \in FU(X)$, il existe un $a \in F$ tel que $f(a \cup b) = f(b)$. Une pleine correspondance exige que $f(a) = f(a \cup b) = f(b)$.
   • Ils construisent une « séquence de Towsner », une séquence imbriquée de demi-correspondances induisant une structure d'arbre (l'arbre de Towsner).
   • Ils établissent que pour un coloriage arithmétique $f$, une séquence de Towsner calculable par $f''$ existe.
3. Notion de forcing : Une nouvelle notion de forcing est définie à l'aide de « conditions-P », qui sont des paires $(I, X)$ où $I$ est un ensemble fini de suites de blocs et $X$ est un réservoir infini. Une condition est dite « de correspondance avec $f$ » si elle satisfait une propriété d'extension spécifique liée au coloriage.
4. Contrôle du premier saut (First-Jump Control) : L'innovation centrale est la conception d'une « question de forcing » dotée de propriétés de définissabilité spécifiques. Cela permet la construction d'un filtre générique où la solution $G$ résultante évite de calculer un ensemble non arithmétique spécifique $C$. La relation de forcing est conçue pour contrôler le premier saut de la solution, garantissant que la solution reste dans un degré arithmétique spécifique par rapport à l'entrée, tout en évitant le cône cible.
5. Diagonalisation : Pour garantir que $C \not\leq_T G$, les auteurs satisfont les exigences $R^C_e: W^G_e \neq C$. En analysant la question de forcing pour les formules $\Sigma^0_1$, ils démontrent que pour tout ensemble non arithmétique $C$ et tout coloriage arithmétique, on peut étendre les conditions pour forcer $G$ à différer de $C$ sur un élément.

Contributions clés et résultats

1. Théorème principal (Évitement de cône) : Le résultat principal (Théorème principal 1.5) stipule : Soit $C$ un ensemble de degré non arithmétique. Pour tout $\ell \geq 1$ et tout coloriage $f: \mathbb{N} \to \ell$ (ou $P_{fin}(\mathbb{N}) \to \ell$) de degré arithmétique, il existe un ensemble infini $H$ tel que $FS(H)$ est $f$-monochromatique et $C \not\leq_T H$.

   • Corollaire : En posant $C = \emptyset^{(\omega)}$, les auteurs prouvent que toute instance arithmétique du théorème de Hindman admet une solution qui ne calcule pas $\emptyset^{(\omega)}$. Cela démontre que la borne supérieure de calculabilité de $\emptyset^{(\omega)}$ n'est pas optimale pour une application unique de Hindman.

2. Limites de l'itération : Les auteurs précisent que ce résultat n'implique pas que le théorème de Hindman est plus faible que $\text{ACA}^+_0$ en mathématiques de l'existence (reverse mathematics). L'évitement de cône est valable pour la réductibilité de Turing ($C \not\leq_T H$) mais pas nécessairement pour la réductibilité arithmétique. Par conséquent, le théorème ne peut pas être itéré pour construire un modèle-$\omega$ de Hindman qui exclurait $\emptyset^{(\omega)}$.

3. Coloriages simples : L'article étudie les restrictions de HT aux « coloriages simples » (coloriages où la couleur d'une union dépend uniquement de la couleur des composantes et de leurs positions relatives).

   • Ils prouvent que la restriction du théorème des unions finies aux coloriages simples est équivalente à $\text{ACA}_0$ sur $\text{RCA}_0$.
   • Ils montrent que le coloriage spécifique utilisé par Blass, Hirst et Simpson pour prouver la borne inférieure est un coloriage simple.

4. Complexité des arbres de Towsner : Les auteurs prouvent (Proposition 2.24) que pour le coloriage spécifique construit par Blass, Hirst et Simpson, toute séquence de Towsner calcule $\emptyset'$. Cela suggère que, bien que les arbres de Towsner soient un outil puissant, leur existence pour certains colorings calculables encode intrinsèquement une puissance de calcul significative, bien que cela n'exclue pas l'existence d'autres preuves ou de pleines correspondances ne dépendant pas de tels arbres.

Signification
L'article résout la question de savoir si la borne supérieure de $\emptyset^{(\omega)}$ est serrée pour les applications uniques du théorème de Hindman. En prouvant que des cônes non arithmétiques peuvent être évités, les auteurs montrent que le théorème ne nécessite pas intrinsèquement toute la force du sur-saut $\omega$ pour produire une solution pour des entrées arithmétiques. Cela affine la compréhension du contenu computationnel du théorème, en distinguant la complexité requise pour trouver une solution de la complexité requise pour trouver une solution qui calcule des ensembles de haut degré spécifiques. Ce travail fait le pont entre les preuves combinatoires (Towsner) et les techniques de forcing pour obtenir un contrôle précis sur les degrés de Turing des solutions.