An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb Z[i]$

기술적 요약: $\mathbb{Z}[i]$ 상의 디오판토스 방정식에 대한 18-변수 결정 불가능성에 관한 AI 증명

문제 정의
본 논문은 가우스 정수 고리 $\mathbb{Z}[i]$ 상에서의 힐베르트 제10번 문제(Hilbert's Tenth Problem)를 다룬다. 이 문제는 주어진 고리 위의 임의의 다항 방정식이 해를 갖는지 여부를 결정하는 알고리즘을 찾는 것을 목표로 한다. $\mathbb{Z}$ 상에서의 이 문제의 결정 불가능성은 마티야세비치(Matiyasevich), 데이비스(Davis), 퍼트넘(Putnam), 로빈슨(Robinson)의 정리에 의해 확립되었으나, 자연스러운 세분화 연구로서 결정 불가능성을 유지하기 위해 필요한 미지수의 최소 개수에 관한 논의가 이루어져 왔다. 마티야세비치와 선(Sun)의 선행 연구는 $\mathbb{Z}[i]$ 상에서 20개의 미지수를 가진 방정식에 대해 결정 불가능성이 성립함을 확립하였다. 본 논문은 이 경계치를 18개 미지수로 줄이는 증명을 제시한다.

방법론 및 프레임워크
본 증명은 마티야세비치와 선이 확립한 일반적인 프레임워크를 유지하며, 다음의 세 가지 핵심 구성 요소에 의존한다:

1. 선의 고정 변수 정리(Sun's Fixed-Variable Theorem): 재귀적으로 열거 가능하지만 비재귀적인 집합 $A \subseteq \mathbb{N}$과, $A$의 멤버십이 $z_{10} \neq 0$인 조건 하에서 $P(a, z_1, \dots, z_{10}) = 0$의 정수 해의 존재와 동치인 다항식 $P(Z_0, \dots, Z_{10})$을 활용한다.
2. 유리 정수에 대한 디오판토스 테스트: $\mathbb{Z}[i]$의 원소가 실제로 유리 정수인지를 판별하기 위한 특정 다항식 테스트(보조정리 3)를 사용한다.
3. 유리성 기준(Rationality Criterion): 특정 구성된 합의 유리성을 바탕으로 변수들이 유리 정수가 되도록 강제하는 $\mathbb{Q}(i)$ 상의 기준(보조정리 4)을 적용한다.

저자들은 다음의 두 가지 구체적인 수정을 통해 변수의 수를 20개에서 18개로 줄이는 데 성공하였다:

주요 기여 및 기술적 수정 사항

1. 분모 제거 변수의 제거:
   20-변수 구성에서는 유리성 기준을 적용할 때 분모를 제거하기 위한 보조 변수가 도입되었다. 저자들은 이를 변수 $Z_1, \dots, Z_{10}$에 부과되는 두 개의 직접적인 정수 조건으로 대체하였다.
   $Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$라고 하자. 분모를 제거하기 위해 변수를 추가하는 대신, 증명은 다음의 조건을 부과한다:
   $$Y^{10} \in \mathbb{Z} \quad \text{및} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$$
   $Y \neq 0$이므로, 이 조건들은 $Y + \sum Z_k Y^{-k}$라는 양이 유리수임을 보장한다. 이 수정을 통해 모든 $Z_k$가 유리 정수가 되도록 강제한다. 이 수정은 변수 하나를 절약한다.

2. 일변수 가젯을 통한 비제로(Nonzero) 조건의 흡수:
   기존의 구성에서는 비제로 조건(구체적으로 곱 $Z_{10}V_0V_1$에 대하여)을 강제하기 위해 두 개의 변수가 필요했다. 저자들은 하나의 일변수 다항식 가젯 $Q(R) = (2R + 1)(3R + 1)$을 도입하였다.

• 특성: $Q(R)$은 $\mathbb{Z}[i]$ 상에서 결코 0이 되지 않는다. 또한, 모든 0이 아닌 정수 $n$에 대하여, $n \mid Q(R)$을 만족하는 정수 $R$이 존재한다.
• 적용: 이 가젯은 "관계 결합 보조정리(Relation-combining lemma, 보조정리 2)"에 통합된다. 비제로 조건을 강제하기 위한 별도의 방정식 대신, 이 조건은 단일 방정식 $f(C_0, C_1, N, Q(R), M) = 0$에 흡수된다. 만약 $N=0$이라면, 방정식은 $Q(R)^4 = 0$으로 귀결되는데, 이는 불가능하다. 따라서 이 방정식은 추가적인 변수 없이도 $N \neq 0$임을 암시적으로 강제한다. 이 수정은 두 번째 변수를 절약한다.

변수 개수 분석
결과적인 시스템은 정확히 18개의 변수를 사용한다:

• $Z_1, \dots, Z_{10}$: 선의 고정 변수 입력으로부터 온 10개의 변수.
• $V_0, X_0, Y_0$ 및 $V_1, X_1, Y_1$: $U_0 = Y^{10}$ 및 $U_1 = W$($W$는 합으로부터 유도됨)에 대한 정수 테스트에 사용되는 두 세트의 3개 변수들.
• $M$: 관계 결합 보조정리의 결합 변수.
• $R$: 비제로 가젯의 단일 변수.
  총합: $10 + 3 + 3 + 1 + 1 = 18$.

주요 결과
본 논문은 정리 1을 증명한다: 계수가 $\mathbb{Z}$인 임의의 다항 방정식 $F(X_1, \dots, X_{18}) = 0$이 $\mathbb{Z}[i]^{18}$에서 해를 갖는지 결정하는 알고리즘은 존재하지 않는다.

증명은 비재귀적 집합 $A$의 멤버십이 18개의 미지수를 가진 $\mathbb{Z}[i]$ 상의 단일 다항 방정식으로 표현될 수 있음을 보여준다. 보조정리 1에 따라, 구성으로부터 유도된 유한 방정식 체계는 새로운 변수를 도입하지 않고도 하나의 다항 방정식으로 결합될 수 있으며, 이 과정에서 정수 계수가 보존된다.

의의 및 주장
저자들은 이 결과가 변수의 수를 2개 줄임으로써 마티야세비치와 선의 20-미지수 정리를 개선했다고 밝히고 있다. 본 논문은 이것이 절대적인 최적성을 주장하는 것은 아니라고 명시적으로 언급한다. 변수의 수를 더 낮추는 것(예: 17개로 감소)은 더 작은 정수 테스트, 공유된 증거(shared witness)를 가진 정수 조건, 더 강력한 고정 변수 입력, 또는 다른 결합 메커니즘과 같은 추가적인 개선이 필요할 것이다. 본 연구는 가우스 정수 상의 디오판토스 결정 불가능성이라는 확립된 프레임워크 내에서의 기술적 세분화 작업이다.