🔢 mathematics

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

This paper presents an AI-generated proof that the solvability of Diophantine equations over the Gaussian integers is undecidable with only 18 variables, improving upon the previous 20-variable bound by Matiyasevich and Sun through optimized variable-saving techniques.

Original authors: Yuchen Ding, Junfeng Li

Published 2026-06-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuchen Ding, Junfeng Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Unsolvable Puzzle"

Imagine you have a giant, magical puzzle box. Inside, there is a complex equation (a math problem) with many unknown numbers (variables). Your goal is to figure out: "Does this equation have a solution?"

For a long time, mathematicians knew that if you have enough variables, this question becomes impossible to answer with a computer program. It's like trying to write a rulebook that can tell you if every possible maze has an exit; eventually, the mazes get so twisted that no rulebook can cover them all.

This paper is about a specific type of puzzle box called Gaussian Integers (numbers that look like $a + bi$, where $i$ is the square root of -1). The authors, Yuchen Ding and Junfeng Li, used an AI to prove that if your puzzle box has 18 unknowns, there is no computer program that can always tell you if a solution exists.

The Previous Record: 20 Variables

Before this paper, the best known result (by mathematicians Matiyasevich and Sun) was that you needed 20 unknowns to make the puzzle unsolvable. They had a specific recipe to build these impossible puzzles.

The authors of this paper said, "We can do it with fewer pieces." They managed to shrink the recipe from 20 pieces down to 18.

How They Did It: Two Clever Tricks

To understand how they saved two variables, imagine you are building a machine to test if a number is "real" (an integer) inside a world of complex numbers.

Trick 1: The "No-Extra-Cup" Strategy

The Old Way:
Imagine you have a recipe that requires mixing ingredients, but the instructions involve fractions. To make the math work on a computer, you usually need an extra cup (a new variable) to clear away the denominators (the bottom numbers of fractions) so everything becomes a whole number. This extra cup takes up space in your 20-variable limit.

The New Way:
The authors realized they didn't need that extra cup. Instead of adding a new variable to clean up the fractions, they simply added two strict rules to the existing ingredients.

Analogy: Instead of bringing a new bucket to catch the spill, they just tightened the lid on the existing buckets so nothing could spill.
Result: They saved one variable by forcing the math to stay "clean" without needing a helper variable.

Trick 2: The "Magic Key" Gadget

The Old Way:
In the old recipe, to make sure a specific number wasn't zero (which is crucial for the puzzle to work), they needed two separate variables acting as a "safety check." It was like using two different keys to unlock a door just to make sure it wasn't jammed.

The New Way:
The authors invented a special "Magic Key" gadget. They created a specific formula: $(2R + 1)(3R + 1)$ .

The Magic: This formula never equals zero, no matter what number you plug in. However, if you have any non-zero number you want to "check," you can find a value for $R$ that makes this formula divisible by your number.
The Savings: Because this single formula does the job of two separate safety checks, they only needed one variable ( $R$ ) instead of two.
Result: They saved the second variable.

The Final Count

By combining these two tricks, they reduced the total number of unknowns needed to prove the puzzle is unsolvable:

10 variables for the main puzzle (from previous work).
3 variables for the first "integer test" (checking if numbers are whole).
3 variables for the second "integer test."
1 variable for the "combining" step.
1 variable for the "Magic Key" gadget.
Total: 18 variables.

What This Means

The paper proves that for any computer program, there is a limit to how many variables it can handle before the problem becomes impossible to solve.

Before: The limit was known to be 20.
Now: The limit is proven to be 18 (or perhaps even lower, but 18 is the new confirmed floor).

The authors emphasize that they haven't found the absolute lowest possible number (maybe it's 17 or 16), but they have successfully lowered the bar from 20 to 18 using these two specific "space-saving" tricks.

Summary

Think of it like packing for a trip. The old rule said, "You need 20 suitcases to carry all your clothes." These authors looked at the clothes, realized they could fold them tighter (Trick 1) and use a compression bag (Trick 2), and proved, "Actually, you only need 18 suitcases."

This doesn't mean the trip is easier; it just means the "impossible" threshold is reached with fewer resources than we thought.

Technical Summary: An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb{Z}[i]$

Problem Statement
This paper addresses Hilbert's Tenth Problem over the ring of Gaussian integers, $\mathbb{Z}[i]$ . The problem asks for an algorithm to decide whether an arbitrary polynomial equation over a given ring has a solution. While the undecidability of this problem over the integers $\mathbb{Z}$ was established by the theorem of Matiyasevich, Davis, Putnam, and Robinson, a natural refinement concerns the minimum number of unknowns required to maintain undecidability. Previous work by Matiyasevich and Sun established that undecidability holds for equations with 20 unknowns over $\mathbb{Z}[i]$ . This paper presents a proof reducing this bound to 18 unknowns.

Methodology and Framework
The proof retains the general framework established by Matiyasevich and Sun, which relies on three core components:

Sun's Fixed-Variable Theorem: Utilizing a recursively enumerable but nonrecursive set $A \subseteq \mathbb{N}$ and a polynomial $P(Z_0, \dots, Z_{10})$ such that membership in $A$ is equivalent to the existence of integer solutions to $P(a, z_1, \dots, z_{10}) = 0$ with $z_{10} \neq 0$ .
Diophantine Test for Rational Integers: Using a specific polynomial test (Lemma 3) to determine if elements in $\mathbb{Z}[i]$ are actually rational integers.
Rationality Criterion: Applying a criterion (Lemma 4) over $\mathbb{Q}(i)$ to force variables to be rational integers based on the rationality of a specific constructed sum.

The authors achieve the reduction from 20 to 18 variables by introducing two specific modifications to the previous construction:

Key Contributions and Technical Modifications

Elimination of the Clearing-Denominator Variable:
In the 20-variable construction, an auxiliary variable was introduced to clear denominators when applying the rationality criterion. The authors replace this with two direct integer conditions imposed on the variables $Z_1, \dots, Z_{10}$ .
Let $Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$ . Instead of adding a variable to clear denominators, the proof imposes the conditions:
$Y^{10} \in \mathbb{Z} \quad \text{and} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$
Since $Y \neq 0$ , these conditions ensure that the quantity $Y + \sum Z_k Y^{-k}$ is a rational number. By the rationality criterion, this forces all $Z_k$ to be rational integers. This modification saves one variable.
Absorption of the Nonzero Condition via a One-Variable Gadget:
The previous construction required two variables to enforce a nonzero condition (specifically for the product $Z_{10}V_0V_1$ ). The authors introduce a one-variable polynomial gadget $Q(R) = (2R + 1)(3R + 1)$ .
- Properties: $Q(R)$ never vanishes on $\mathbb{Z}[i]$ . Furthermore, for every nonzero integer $n$ , there exists an integer $R$ such that $n \mid Q(R)$ .
- Application: This gadget is integrated into the "relation-combining lemma" (Lemma 2). Instead of a separate equation to enforce non-vanishing, the condition is absorbed into the single equation $f(C_0, C_1, N, Q(R), M) = 0$ . If $N=0$ , the equation reduces to $Q(R)^4 = 0$ , which is impossible. Thus, the equation implicitly forces $N \neq 0$ without requiring an extra variable. This modification saves a second variable.

Variable Count Breakdown
The resulting system utilizes exactly 18 variables:

$Z_1, \dots, Z_{10}$ : The 10 variables from Sun's fixed-variable input.
$V_0, X_0, Y_0$ and $V_1, X_1, Y_1$ : Two sets of 3 variables used for the integer tests on $U_0 = Y^{10}$ and $U_1 = W$ (where $W$ is derived from the sum).
$M$ : The combining variable from the relation-combining lemma.
$R$ : The single variable from the nonzero gadget.
Total: $10 + 3 + 3 + 1 + 1 = 18$ .

Main Result
The paper proves Theorem 1: There is no algorithm to decide whether an arbitrary polynomial equation $F(X_1, \dots, X_{18}) = 0$ with coefficients in $\mathbb{Z}$ has a solution in $\mathbb{Z}[i]^{18}$ .

The proof demonstrates that membership in the nonrecursive set $A$ can be represented by a single polynomial equation over $\mathbb{Z}[i]$ in 18 unknowns. By Lemma 1, the finite system of equations derived from the construction can be combined into a single polynomial equation without introducing new variables, preserving the integer coefficients.

Significance and Claims
The authors state that this result improves the 20-unknown theorem of Matiyasevich and Sun by reducing the variable count by two. The paper explicitly notes that it does not claim absolute optimality; lowering the count further (e.g., to 17) would require additional improvements, such as a smaller integer test, a shared witness for the integer conditions, a stronger fixed-variable input, or a different combining mechanism. The work serves as a technical refinement within the established framework of Diophantine undecidability over Gaussian integers.