View source for Algebraic Diophantine equations

<!--
a1105001.png
$#A+1 = 84 n = 0
$#C+1 = 84 : ~/encyclopedia/old_files/data/A110/A.1100500 Algebraic Diophantine equations
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

The work of Yu.V. Matiyasevich [[#References|[a5]]], and J. Robinson [[#References|[a8]]], (cf. [[Diophantine equations, solvability problem of|Diophantine equations, solvability problem of]]) showed that in general there does not exist an [[Algorithm|algorithm]] by which it is possible to decide whether a given Diophantine equation over  $  \mathbf Z $
has integral solutions. Neither does a general decision procedure exist for finding solutions of systems of such Diophantine equations in the ring of integers of any number field of finite degree over  $  \mathbf Q $.

Let

$$ \tag{a1 }
f _ {i} ( X _ {1} \dots X _ {n} ) = 0,  1 \leq  i \leq  r,
$$

be a system of polynomial equations having integral coefficients. The ring of all algebraic integers,  $  {\widetilde{\mathbf Z}  } $, 
is defined to be the integral closure of  $  \mathbf Z $
in an algebraic closure of  $  \mathbf Q $(
cf. also [[Algebraically closed field|Algebraically closed field]]). In 1934, Th. Skolem suggested that the question:  "Does there exist a decision procedure for finding solutions x1…xn of a system of polynomial equations in Z?"  could be answered affirmatively.

More precisely, Skolem asked whether the [[Elementary theory|elementary theory]] of the ring of all algebraic integers  $  {\widetilde{\mathbf Z}  } $
is decidable.

==Diophantine question.==
In the early 1980s R. Rumely [[#References|[a9]]] positively answered the Diophantine question, thereby showing that Hilbert's 10th problem (cf. [[Diophantine set|Diophantine set]]) can be solved positively for  $  {\widetilde{\mathbf Z}  } $. 
His proof built on work by D. Cantor and P. Roquette, [[#References|[a1]]], who answered the corresponding question for systems of equations determining unirational varieties. The methods Rumely used for obtaining the general result are based on his capacity theory on algebraic curves over number fields.

The main point in the proof is the following Hasse local-global principle for Diophantine problems of the form (a1): Let  $  {\widetilde{\mathbf Q}  } _ {p} $
be the algebraic closure of the  $  p $-
adic numbers  $  \mathbf Q _ {p} $
and let  $  {\widetilde{\mathbf Z}  } _ {p} $
be the integral closure of the  $  p $-
adic integers  $  \mathbf Z _ {p} $
in  $  {\widetilde{\mathbf Q}  } _ {p} $. 
The local-global principle for the ring  $  {\widetilde{\mathbf Z}  } $
asserts that if (a1) has solutions in  $  {\widetilde{\mathbf Z}  } _ {p} $
for each  $  p $, 
then there is a solution in  $  {\widetilde{\mathbf Z}  } $.

==Decidability question.==
By the decidability of the elementary theory of algebraically closed valued fields (cf. [[Model theory of valued fields|Model theory of valued fields]]), it follows that the elementary theory of  $  {\widetilde{\mathbf Q}  } _ {p} $, 
with valuation coming from  $  {\widetilde{\mathbf Z}  } _ {p} $, 
is decidable. For the given Diophantine problem (a1), it is only necessary to check whether there are solutions for finitely many critical primes  $  p $
which are effectively computable from the coefficients of (a1). Hence the solvability of arbitrary algebraic Diophantine equations in  $  {\widetilde{\mathbf Z}  } $
is decidable and Hilbert's 10th problem over the ring  $  {\widetilde{\mathbf Z}  } $
has a positive answer.

The following steps go into the proof of the local-global principle: The result is first proved for curves, and then a Bertini-type induction argument is used to obtain the result for higher dimensions. For curves the proof is divided into two parts, a local/semi-local part and a local-to-global part. In each part a deep theorem is involved: For the local part it is the Rumely existence theorem for functions having prescribed poles and zeros lying in a given open subset of the set of all rational points of the curve over  $  {\widetilde{\mathbf Q}  } _ {p} $. 
The local-to-global part rests on Roquette's unit density approximation theorem. This theorem allows one to approximate arbitrarily closely at finitely many primes by an algebraic element which is a unit at all other primes in a suitable finite extension of  $  \mathbf Q $.

The results above also hold for algebraic Diophantine equations defined over rings of integers of a global field, and, moreover, one is able to admit Archimedian primes and include rationality conditions at a finite set of primes. This general result is precisely stated below.

Let  $  K $
be a [[Global field|global field]] and let  $  \mathfrak p $
be an arbitrary prime of  $  K $. 
An element  $  a \in {\widetilde{K}  } $, 
the algebraic closure, is called totally  $  \mathfrak p $-
adic over  $  K $
if for all embeddings  $  i : { {\widetilde{K}  } } \rightarrow { {{K _ {\mathfrak p} } tilde } } $, 
the image  $  i ( a ) $
lies in  $  K _ {\mathfrak p} $, 
i.e. the prime  $  \mathfrak p $
splits completely in  $  K ( a ) $. 
If  $  {\mathcal S} $
is a finite set of primes of  $  K $, 
then the set  $  K  ^  \prime  $
of totally  $  {\mathcal S} $-
adic elements over  $  K $
is the maximal extension in which all primes  $  \mathfrak p \in {\mathcal S} $
split completely. It is a Galois extension of  $  K $, 
and if  $  {\mathcal S} $
is empty it is taken to be the separable closure of  $  K $. 
For any prime  $  \mathfrak p $
one lets  $  {\widetilde {\mathcal O}   } _ {\mathfrak p} $
be the integral closure of the completed unit ball in the algebraic closure of  $  K _ {\mathfrak p} $. 
Given a set of primes  $  {\mathcal V} $
not containing all primes of  $  K $, 
one lets  $  {\mathcal O} _  {\mathcal V}  $
be the set of all  $  a \in K $
that are contained in  $  {\mathcal O} _ {\mathfrak p} $
for all  $  \mathfrak p \in {\mathcal V} $. 
The integral closure in  $  K  ^  \prime  $
is denoted by  $  {\mathcal O} _  {\mathcal V}   ^  \prime  $.

==The local-global principle with rationality conditions.==
Let  $  K $
be a global field, equipped with a set  $  {\mathcal V} $
of primes not containing all primes of  $  K $. 
In addition, let a finite subset  $  {\mathcal S} \subset  {\mathcal V} $
be given. Let  $  V $
be a geometrically integral variety defined over  $  K $, 
and let  $  \mathbf x = ( x _ {1} \dots x _ {n} ) $
be a finite family of rational functions on  $  V $
defined over  $  K $. 
Suppose that locally the set

$$ 
V _ {\mathbf x} ( {\mathcal O} _ {\mathfrak p} ) = \left \{ {P \in V ( K _ {\mathfrak p} ) } : {x _ {k} ( P ) \in {\mathcal O} _ {\mathfrak p} ,  1 \leq  k \leq  n } \right \}
$$

contains a non-singular point for each  $  \mathfrak p \in {\mathcal S} $, 
and that  $  V _ {\mathbf x} ( {\widetilde {\mathcal O}   } _ {\mathfrak p} ) $
is non-empty for  $  \mathfrak p \in {\mathcal V} \setminus  {\mathcal S} $. 
Then globally,  $  V _ {\mathbf x} ( {\mathcal O} _  {\mathcal V}   ^  \prime  ) $
is non-empty and it contains, moreover, non-singular points.

This theorem can be found in [[#References|[a4]]], where the proof is given using methods from classical algebraic number theory and the theory of constant reductions. A proof using geometric methods can be found in [[#References|[a6]]]. There, equivalent properties for separated schemes of finite type over appropriate Dedekind schemes are also given. Letting  $  K = \mathbf Q $
and letting  $  x _ {1} \dots x _ {n} $
be the coordinate functions for the variety determined by the system (a1) yields the local-global principle for algebraic Diophantine equations, whose variety is geometrically integral, with rationality conditions at a finite set of primes. The solvability of arbitrary systems of algebraic Diophantine equations whose variety is not geometrically integral can be effectively reduced to the geometrically integral case. An important question, which is still being investigated, concerns bounding the degree of integral solutions.

A direct geometric application of the local-global principle is to the existence of smooth curves of arbitrary genus over suitable number fields having good reduction everywhere. Another useful application is to the existence of finite morphisms to projective space. Let  $  S $
be the spectrum of a Dedekind ring of integers of a global field and let  $  X $
be a proper normal integral  $  S $-
scheme all fibres of which have dimension  $  d $. 
Then there exists a finite morphism  $  X \rightarrow \mathbf P _ {S}  ^ {d} $. 
Another application is to the algebraic theory of  $  {\widetilde{\mathbf Z}  } $.

==The algebraic theory of  $  {\widetilde{\mathbf Z}  } $.==
Using the local-global principle above, L. van den Dries [[#References|[a2]]], and A. Prestel, J. Schmidt [[#References|[a7]]], have independently shown that the elementary theory of the ring  $  {\widetilde{\mathbf Z}  } $
is decidable, answering the more general question posed by Skolem. In [[#References|[a2]]], van den Dries extended the work of Rumely to an effective [[Elimination of quantifiers|elimination of quantifiers]] for the elementary theory of  $  {\widetilde{\mathbf Z}  } $, 
thus proving decidability for this theory. In [[#References|[a7]]], this is done by studying the model theory of domains with radical extensions and proving model completeness of a certain class of such domains. Rumely's local-global principle is then used to show that  $  {\widetilde{\mathbf Z}  } $
satisfies the axioms of this class and so one obtains a complete effective axiomatization of the ring  $  {\widetilde{\mathbf Z}  } $, 
which then also gives decidability.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Cantor,   P. Roquette,   "On diophantine equations over the ring of all algebraic integers"  ''J. Number Th.'' , '''18'''  (1984)  pp. 1–26</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. van den Dries,   "Elimination theory for the ring of algebraic integers"  ''J. Reine Angew. Math.'' , '''388'''  (1988)  pp. 189–205</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. van den Dries,   A. Macintyre,   "The logic of Rumely's local-global principle"  ''J. Reine Angew. Math.'' , '''407'''  (1990)  pp. 33–56</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  B. Green,   F. Pop,   P. Roquette,   "On Rumely's local global principle"  ''Jahresber. Deutsch. Math.-Verein.'' , '''97'''  (1995)  pp. 43–74</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  Yu.V. Matiyasevich,   "Diophantine sets"  ''Russian Math. Surveys'' , '''27''' :  5  (1972)  pp. 124–164  ''Uspekhi Mat. Nauk'' , '''27''' :  5  (1972)  pp. 185–222</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  L. Moret-Bailly,   "Groupes de Picard et problèmes de Skolem I, II"  ''Ann. Sci. Ecole Normale Sup.'' , '''22'''  (1989)  pp. 161–179; 181–194</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Prestel,   J. Schmidt,   "Existentially closed domains with radical relations: An axiomatisation of the ring of algebraic integers"  ''J. Reine Angew. Math.'' , '''407'''  (1990)  pp. 178–201</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J. Robinson,   "Existential definability"  ''Trans. Amer. Math. Soc.'' , '''72''' :  3  (1952)  pp. 437–449</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  R. Rumely,   "Arithmetic over the ring of all algebraic integers"  ''J. Reine Angew. Math.'' , '''368'''  (1986)  pp. 127–133</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  R. Rumely,   "Capacity theory on algebraic curves" , ''Lecture Notes in Mathematics'' , '''1378''' , Springer  (1989)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  Th. Skolem,   "Lösung gewisser Gleichungen in ganzen algebraischen Zahlen, insbesondere in Einheiten"  ''Skrifter Norske Videnskap. Akad. Oslo I. Mat. Kl.'' , '''10'''  (1934)</TD></TR></table>