Korean, Edit

Hilbert’s Tenth Problem

Recommended reading: 【Modern Mathematics】 Table of Contents of Modern Mathematics

1. Hilbert’s Tenth Problem over the Integers

2. Hilbert’s Tenth Problem over the Rational Numbers

1. Hilbert’s Tenth Problem over the Integers $H10(\mathbb{Z})$

⑴ Overview

① Diophantine equation: An equation involving a polynomial with integer coefficients, for which integer solutions (or rational solutions) are sought

○ Example: $x^2+y^2+z^2=xyz$ (ref)

② Nonexistence of an algorithm for deciding the existence of integer solutions (DPRM)

③ 1900: Hilbert posed the problem of finding an algorithm that determines whether an arbitrary Diophantine equation has an integer solution

④ 1936: Turing proved the undecidability of the halting problem

⑤ 1950s–1960s: Davis, Putnam, and Robinson developed the connection between Diophantine equations and computability

⑥ 1970: Matiyasevich resolved the final crucial step, completing the DPRM theorem. Consequently, the existence of integer solutions cannot be decided in general

⑵ Proof

① Step 1. Assume that there exists an algorithm that determines whether an arbitrary polynomial with integer coefficients has an integer solution

② Step 2. Undecidability of the halting problem

○ Define the set of indices $e$ for which the Turing machine $M_e$ halts when given its own index $e$ as input

○ This set is recursively enumerable

○ If $e\in S$, the program halts within a finite amount of time and outputs YES when given $e$ as input

○ If $e\notin S$, the program may run forever without halting when given $e$ as input

○ This set is not decidable

○ Halting cases can be recognized, but no algorithm can always determine whether a program halts or runs forever

③ Step 3. Davis–Putnam–Robinson–Matiyasevich (DPRM) theorem

○ Summary: Recursively enumerable sets $\Leftrightarrow$ Diophantine sets. Since the reverse implication is straightforward, only the forward implication will be considered

○ 3-1. Finiteness of computation records: If a program halts, its entire computation can be represented as a finite sequence of configurations $C_0\to C_1\to\cdots\to C_t$

○ $e$: Input given to the program

○ $t$: Number of computation steps required for the program to halt

○ 3-2. Encoding computation records : For $0\le C_i\ll B$, the entire computation record can be encoded as a single natural number using $H=\sum_{i=0}^{t}C_iB^i$

○ 3-3. Davis–Putnam–Robinson (1961)

○ Exponential operations and number-theoretic encoding are used to extract arbitrary configurations from the computation record and express the condition that every computation step is valid

○ For example, the condition that the $i$-th digit of $H$ is $c$ can be expressed as follows: $H=qB^{i+1}+cB^i+r$, where $0\le c<B$, $0\le r<B^i$, and $B\ge2$

○ Consequently, every recursively enumerable set (i.e., a set of indices $e$ for which the corresponding computation halts in finite time whenever it halts) can be represented by an exponential Diophantine equation (where $E$ is an exponential polynomial allowing variable exponents of the form $x^y$)

○ 3-4. Matiyasevich (1970)

○ For example, given a solution of the Pell-type equation $x^2-5y^2=4$, we can determine that $y$ is a term of the Fibonacci sequence, but it is not yet clear whether it is precisely $F_{2n}\sim\frac{1}{\sqrt5}\left(\frac{3+\sqrt5}{2}\right)^n$, that is, whether its index is $2n$

○ Example 1. The positive integer solutions of the Pell equation $x^2-2y^2=1$ can be expressed as $x_n+y_n\sqrt2=(3+2\sqrt2)^n$

○ Example 2. For the Pell-type equation $x^2-5y^2=4$, let $F_n$ and $L_n$ denote the Fibonacci and Lucas sequences, respectively. Then $L_n^2-5F_n^2=4(-1)^n$

○ Example 3. $x^2+y^2+z^2=xyz$ (ref)

○ Matiyasevich established a Diophantine representation of the relation $v=F_{2n}$ by exploiting the exponential growth of the Fibonacci sequence and its divisibility and congruence properties (i.e., using number-theoretic tricks involving some laborious calculations)

○ Combining this result with Julia Robinson’s work, he proved that the exponentiation relation $z=x^y$ can also be represented by a polynomial equation with integer coefficients

○ 3-5. Completion of the DPRM theorem

○ Replace every exponentiation appearing in the exponential Diophantine representation from 3-3 with the polynomial representation established in 3-4

○ A finite system of equations can be combined into a single equation by taking the sum of squares: For example, if $b=a+1$ and $c=2b$, we can define the Diophantine equation $(b-a-1)^2+(c-2b)^2=0$

○ Therefore, every recursively enumerable set is a Diophantine set

④ Step 4. Lagrange’s Four-Square Theorem

○ Every nonnegative integer $n$ can be expressed as the sum of the squares of four integers: $n=x_1^2+x_2^2+x_3^2+x_4^2$

○ Using this theorem, each natural-number variable $y_i$ can be represented in terms of integer variables, allowing the existence of natural-number solutions to a Diophantine equation to be converted into the existence of purely integer solutions

⑤ Step 5. Use the assumed algorithm to decide the halting problem

○ For an arbitrary $e$, construct the polynomial obtained in Steps 3–4 and feed it into algorithm $A$

○ This would make it possible to decide the halting problem in every case

⑥ Step 6. Derive a contradiction: This contradicts Turing’s theorem that the halting problem is undecidable

2. Hilbert’s Tenth Problem over the Rational Numbers $H10(\mathbb{Q})$

⑴ Overview

① Hilbert’s Tenth Problem over the Rational Numbers: The claim that no algorithm exists that can always determine whether an arbitrary polynomial with integer coefficients has a rational solution

② One might argue that, since there are far more rational numbers than integers, it could be possible to determine the existence of rational solutions in every case

⑵ Proof: OpenAI’s proof claims undecidability using elliptic curves.

① Step 1. Assume that an algorithm exists for deciding the existence of rational solutions

② Step 2. Encode integers using points $nP$ on an elliptic curve, and relate the existence of integer solutions to the success of finitely many rational-solvability tests

○ Associate each candidate solution $x_i$ of $f(x_1,\cdots,x_n)=0$ with a point $\eta(a_i)P$ on an elliptic curve: $\eta$ is an integer index indicating how many times the point $P$ is added to itself

③ Step 3. Shimura curves, Galois representations, modularity $\Rightarrow$ five-point height estimate $\Rightarrow$ obtain a linear upper bound $O(B)$ (not yet verified)

○ Arithmetic size (height) of a rational number: $h(a/b)=\log\max(\left|a\right|,\left|b\right|)$

○ $B=\max(1,\left|\eta(a_1)\right|,\cdots,\left|\eta(a_n)\right|)$

○ Five-point height estimate: A theorem stating that an upper bound on height can be obtained from knowledge of the product $M(s)$ of certain primes. Through the modularity of elliptic curves (proved by Wiles), the numerators and denominators of rational numbers can be restricted to products of certain primes, thereby obtaining an upper bound on height, which measures how complicated the numerators and denominators of rational numbers can become. In other words, Step 3 is essentially about focusing on more manageable rational numbers rather than all rational numbers

○ Summary: Modularity + local prime conditions $\Rightarrow h(x(nP))\le CB=O(B)$

④ Step 4. Canonical height on elliptic curves $\Rightarrow$ obtain quadratic growth $O(B^2)$ (verified)

○ Canonical height on elliptic curves: $h(x(P)),\ h(x(2P)),\ h(x(3P)),\cdots$

○ Néron–Tate canonical height: $\hat{h}(nP)=n^2\hat{h}(P)$

○ The quadratic nature of the canonical height originates from the elliptic-curve property $E[n]\simeq(\mathbb{Z}/n\mathbb{Z})^2$

○ Summary: Elliptic-curve group law and canonical height $\Rightarrow h(x(nP))=n^2\hat{h}(P)+O(1)$

⑤ Step 5. Derive a contradiction: Since $cB^2-C\le h(x(nP))\le C’B+C$, the index $B$ is bounded $\Rightarrow$ actual integer solvability becomes decidable $\Rightarrow$ contradiction with the DPRM theorem

⑥ Comparison with Fermat’s Last Theorem: FLT derives a nonexistent modular form through the modularity of the Frey curve and level-lowering, whereas $H10(\mathbb{Q})$ uses modularity for height estimates and exploits the conflict between a linear upper bound and quadratic growth

⑶ Suggestions

① The key lies in Step 3, and tasks requiring extensive computation, such as searching for counterexamples in the Navier–Stokes problem, are areas where AI is particularly strong

Entered: 2026.10.18 14:09