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

기술 요약: "힌드먼의 정리는 한 번의 적용으로 $\emptyset^{(\omega)}$를 코딩하지 않는다"

문제 정의
본 논문은 힌드먼의 정리(Hindman's Theorem, HT)의 계산 이론적 복잡성, 특히 입력 색상에 대해 생성되는 해(solution)의 상대적 강도에 관한 문제를 다룬다. 힌드먼의 정리는 모든 자연수 $\mathbb{N}$에 대한 유한 색칠(finite coloring)에 대하여, $H$의 모든 비어 있지 않은 유한 합들의 집합(이를 $FS(H)$라 표기함)이 단색(monochromatic)인 무한 집합 $H$가 존재함을 기술한다.

기존 연구는 다음과 같은 경계값을 확립했다:

1. 상한(Upper Bound): Blass, Hirst, Simpson (1987)은 모든 계산 가능한 색칠에 대하여, $\emptyset^{(\omega)}$로부터 계산 가능한 해가 존재함을 증명했다.
2. 하한(Lower Bound): 동일한 저자들이 어떤 계산 가능한 색칠에 대해서는 모든 해가 정지 문제 집합 $\emptyset'$를 계산함을 증명했다. 이후 Liao (2026)는 이를 개선하여, 어떤 계산 가능한 색칠의 경우 $\Pi^0_3$ 해가 존재하지 않음을 보였다.

본 논문이 다루는 핵심적인 미해결 문제는 단 한 번의 적용에 대해 $\emptyset^{(\omega)}$라는 상한이 최적인가 하는 점이다. 즉, 산술적(arithmetic)인 힌드먼의 정리의 모든 인스턴스가 $\emptyset^{(\omega)}$를 계산하지 않는 해를 갖는가?

방법론
저자들은 Towsner의 힌드먼의 정리의 조합론적 증명에서 채택한 포싱(forcing) 기법을 사용한다. 방법론은 다음 구성 요소들을 포함한다:

1. 재정식화(Reformulation): 문제는 HT와 계산적으로 동등한 유한 합 정리(Finite Union Theorem, FUT)의 언어로 번역된다. 이는 $\mathbb{N}$의 비어 있지 않은 유한 부분집합들의 집합 $P_{fin}(\mathbb{N})$에 대한 색칠을 다루며, $FU(H)$가 단색인 무한 블록 수열$H$를 찾는 것을 목표로 한다.
2. Towsner 트리와 매칭(Matching): 저자들은 Towsner의 "half-match"와 "full-match" 개념을 활용한다. 유한 집합 $F$가 무한 블록 수열 $X$와 half-match한다는 것은, $X$의 모든 유한 합 $b \in FU(X)$에 대하여, $f(a \cup b) = f(b)$를 만족하는 $a \in F$가 존재함을 의미한다. Full-match는 $f(a) = f(a \cup b) = f(b)$를 요구한다.
   • 저자들은 트리 구조를 유도하는 중첩된 half-match들의 순차적 구조인 "Towsner 수열"을 구축한다.
   • 산술적 색칠 $f$에 대하여, $f''$-계산 가능한 Towsner 수열이 존재함을 확립한다.
3. 포싱 개념(Forcing Notion): 새로운 포싱 개념이 "P-조건"을 사용하여 정의되는데, 이는 유한 블록 수열들의 집합 $I$와 무한 저장소(reservoir) $X$의 쌍이다. 조건이 특정 색칠과 관련된 확장 성질을 만족하면 이를 "f-matching"이라 한다.
4. 첫 번째 점프 제어(First-Jump Control): 이 논문의 핵심 혁신은 특정 정의 가능성을 가진 "포싱 질문(forcing question)"의 설계이다. 이를 통해 생성된 generic filter가 특정 비산술적 집합 $C$를 계산하지 않도록 하는 generic filter를 구성할 수 있다. 포싱 관계는 해의 첫 번째 점프를 제어하도록 설계되어, 해가 입력에 대한 특정 산술적 차수(degree) 내에 머물도록 하며 타겟 콘(cone)을 피하게 한다.
5. 대각선 논법(Diagonalization): $C \not\leq_T G$를 보장하기 위해 요구사항 $R^C_e: W^G_e \neq C$를 충족시킨다. $\Sigma^0_1$ 공식에 대한 포싱 질문을 분석함으로써, 어떤 비산술적 집합 $C$와 산술적 색칠에 대해서도 조건을 확장하여 $G$가 어떤 원소에서 $C$와 달라지도록 강제할 수 있음을 입증한다.

주요 기여 및 결과

1. 주요 정리 (콘 회피, Cone Avoidance): 주요 결과(주 정리 1.5)는 다음과 같다: $C$가 비산술적 차수의 집합일 때, $\ell \geq 1$인 모든 $\ell$과 산술적 차수의 모든 색칠 $f: \mathbb{N} \to \ell$ (또는 $P_{fin}(\mathbb{N}) \to \ell$)에 대하여, $FS(H)$가$f$-단색이고$C \not\leq_T H$를 만족하는 무한 집합$H$가 존재한다.

   • 따르는 정리(Corollary): $C = \emptyset^{(\omega)}$로 설정함으로써, 저자들은 모든 산술적 힌드먼의 정리 인스턴스가 $\emptyset^{(\omega)}$를 계산하지 않는 해를 가짐을 증명한다. 이는 단일 적용에 대해 힌드먼의 정리의 계산 이론적 상한인 $\emptyset^{(\omega)}$가 최적이 아님을 보여준다.

2. 반복의 한계: 저자들은 이 결과가 역수학(reverse mathematics)에서 힌드먼의 정리가 $\text{ACA}^+_0$보다 약하다는 것을 의미하지는 않는다고 명시한다. 콘 회피는 튜링 환원성($C \not\leq_T H$)에 대해서는 성립하지만, 산술적 환원성에 대해서는 반드시 성립하는 것은 아니다. 따라서 이 정리를 반복하여 $\emptyset^{(\omega)}$를 배제하는 힌드먼의 정리의 $\omega$-모델을 구축할 수는 없다.

3. 단순 색칠(Simple Colorings): 논문은 "단순 색칠"(합의 색상이 구성 요소들의 색상과 상대적 위치에만 의존하는 색칠)로 제한된 HT를 조사한다.

   • 저자들은 단순 색칠에 대한 유한 합 정리의 제한이 $\text{RCA}_0$ 위에서 $\text{ACA}_0$와 동치임을 증명한다.
   • Blass, Hirst, Simpson이 하한을 증명하기 위해 사용한 특정 색칠("매우 짧은 간격"에 기반한 색칠)이 단순 색칠임을 보여준다.

4. Towsner 트리의 복잡성: 저자들은 Blass, Hirst, Simpson이 구성한 특정 색칠에 대하여, 모든 Towsner 수열이 $\emptyset'$를 계산함을 증명한다(명제 2.24). 이는 Towsner 트리가 강력한 도구이지만, 특정 계산 가능한 색칠에 대한 그 존재 자체가 상당한 계산 능력을 인코딩하고 있음을 시사한다. 다만, 이것이 다른 증명이나 full-match의 존재를 배제하는 것은 아니다.

의의
본 논문은 힌드먼의 정리의 단일 적용에 대해 $\emptyset^{(\omega)}$ 상한이 타이트한가라는 질문을 해결한다. 비산술적 콘(non-arithmetic cones)을 회피할 수 있음을 증명함으로써, 저자들은 힌드먼의 정리가 산술적 입력을 위해 반드시 $\omega$-점프의 전체 강도를 필요로 하는 것은 아님을 보여준다. 이는 정리가 가지는 계산적 내용에 대한 이해를 정교화하며, 하나의 해를 찾는 데 필요한 복잡성과 특정 높은 차수의 집합을 계산하는 해를 찾는 데 필요한 복잡성을 구분한다. 또한, 조합론적 증명(Towsner의 방식)과 포싱 기법을 결합하여 튜링 차수의 해에 대해 정밀한 제어를 달성함으로써 이 분야를 연결한다.