over rings of algebraic integers
Tim B. Herbstrith
15 June 2018
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers.
– Hilbert (1900)
A Turing machine A on the alphabet A={§,_,0,1} is a tuple (S,δ), where sstart,shalt∈S is a finite non-empty set, called set of states, and
δ:S×A→S×A×{−1,0,1}
is called transition function. If δ(s,a)=(s′,b,m), one demands that the following axioms are satisfied
I write A(x) for the output of Turing machine A on input x if A halts on x.
A decision problem is a subset of the set of finite 0-1-strings ω={0,1}∗ including the empty string λ.
The set of all connected graphs can be encoded as the set of the respective adjacency matrices written as a string
b00b01…b0nb10…bnn
of length (n+1)2.
Let Q⊆ω be a problem. The following are equivalent.
The halting set is the set of all codes of Turing machines A that halt upon receiving their code as input i.e.
K:={┌A┐∣A halts on ┌A┐}
The halting set is semi-decidable but not decidable.
Assume B decides the halting set i.e.
B(┌A┐)={10if A halts on ┌A┐otherwise.
Consider B′ defined by
B′(┌A┐)={1↑if B(┌A┐)=0otherwise.
What is B′(┌B′┐)?
I will use without hesitation:
The class of intuitively computable functions coincides with the class of all Turing computable functions.
A number field K is a finite extension of the rationals Q.
An element α∈C is called algebraic integer if there exists a monic polynomial p∈Z[X] such that
p(α)=αn+cn−1αn−1+…+c0=0
Let R be a commutative ring with unit. A set S⊆Rn is called purely Diophantine if there exists a polynomial p∈Z[X1,…,Xn,Y1,…,Ym] such that
(α1,…,αn)∈S⇔∃y1,…,ym∈Rm:p(α1,…,αn,y1,…,ym)=0
Let R be a commutative ring with unit. Then divisibility is purely Diophantine over R.
We have a∣b iff ∃y∈R:ay=b. Choose p(a,b,y)=ay−b and obtain
a∣b⇔∃y∈R:p(a,b,y)=0.
The language of rings with unit is Lring={+,−,⋅,0,1}.
A set S⊆Rn is purely Diophantine over the ring structure R=⟨R;+R,−R,⋅R;0R,1R⟩ iff
(α1,…,αn)∈S⇔R⊨∃y1,…,ym:φ(α1,…,αn,y1,…,ym)
holds for an atomic Lring-formula φ.
Let R be a commutative ring with unit. A set S⊆Rn is called Diophantine if there exists a polynomial p∈R[X1,…,Xn,Y1,…,Ym] such that
(α1,…,αn)∈S⇔∃y1,…,ym∈Rm:p(α1,…,αn,y1,…,ym)=0
Let R be an integral domain. Then every finite set S⊂R is Diophantine.
Take
p(X)=a∈S∏(X−a).
The set of natural numbers N is Diophantine over Z.
Using Minkowski’s theorem on convex bodies one can prove that
x∈N⇔∃y1,y2,y3,y4∈Z:x=y12+y22+y32+y42.
Let K be a number field and OK its ring of algebraic integers. Then OK∖{0} is Diophantine over OK.
Using the Chinese remainder theorem one can prove that
α≠0⇔∃β,γ∈OK:αβ=(2γ−1)(3γ−1).
Let R be an at most countable commutative ring with unit. The R-language is LR=Lring∪{cr∣r∈R}.
A set S⊆Rn is Diophantine over R iff
(α1,…,αn)∈S⇔R⊨∃y1,…,ym:φ(α1,…,αn,y1,…,ym)
holds for an atomic LR-formula φ.
Given a commutative ring with unit R we consider 4 theories.
Lring-theories | LR-theories | |
---|---|---|
∃-quantified | purely Diophantine H10∗(R) | Diophantine H10(R) |
∃- or ∀-quantified | full theory Th(R) | complete diagram Dc(R) |
Which sets are Diophantine?
The full theory Th(N) is undecidable.
The full theory Th(Z) is undecidable.
The full first order theories Th(K) and Th(OK) are undecidable for every number field K.
The full theory Th(C) is decidable. Thus, H10∗(C) is decidable.
The theories H10(O) and Dc(O) are decidable.
A subset of Z is semi-decidable if and only if it is Diophantine over Z.
H10(Z) is undecidable.
H10(OK) is undecidable if
Let K be a number field. Then Hilbert’s tenth problem over OK is semi-decidable.
Let p∈OK[X1,…,Xn] be a polynomial. Interpret p:OKn→OK, then p is computable.
Deciding whether p has roots in OK is equivalent to deciding
∃x1,…,xn:p(x1,…,xn)≐0,
which is semi-decidable.
If S1 and S2 are Diophantine over OK, so are
S1∪S2andS1∩S2.
The resp. polynomial identities can be found effectively.
Let p1(X,Y),p2(X,Y)∈OK[X,Y] give Diophantine definitions of S1 and S2.
We have S1∪S2={α∣∃y∈OK:p1(α,y)p2(α,y)=0}.
To prove the claim for intersections of Diophantine sets, let
h(T)=amTm+…+a1T+a0∈OK[T]
be a polynomial of degree m>0 without roots in QuotOK=K. Then h(T)=Tmh(T−1) does not have roots in K either.
Set
H(X,Y1,Y2)=i=0∑maip1(X,Y1)ip2(X,Y2)m−i,
then
∃y1,y2∈OK:H(α,y1,y2)=0⇔ ∃y1∈OK:p1(α,y1)=0 and ∃y2∈OK:p2(α,y2)=0
Let L/K be an extension of algebraic number fields. If H10 is undecidable over OK and OK is Diophantine over OL, then H10 is undecidable over OL.
Assume otherwise and let pK∈OL[X,Y] give a Diophantine definition of OK over OL.
If q∈OK[X1,…,Xn], then q has a root in OK if and only if
∃x1,…,xn∈OL∃y1,…,yn∈OL:q(x1,…,xn)=0∧i=1⋀npK(xi,yi)=0
Every semi-decidable subset of OK is Diophantine if and only if Z is Diophantine over OK.
Let L/K be an extension of number fields and n=[L:Q]. If x,y∈OL and α∈OK satisfy
where σ1,…,σn denote the embeddings of L into C and c∈N is a fixed, then
x=α∈OK.
Let K be totally real and a∈OK. We set
If δ(a)∉K, we define xm(a),ym(a) by
xm(a)+δ(a)ym(a)=ε(a)m
View this as an analogue to
cos(m)+isin(m)=eim
X2−(a2−1)Y2=1
(±xm(a),±ym(a))m∈N are all solutions to Pell’s equation with parameter a in OK.
View this as an analogue to
cos(m)2−i2sin(m)2=1
Let K be number field of degree n=[K:Q] and let σ1,…,σn denote all embeddings of K into C. For all α∈K we set
αi:=σi(α)for all 1≤i≤n
Let K≠Q be a totally real number field of degree n=[K:Q] and let a∈OK satisfy
a1≥22n,∣ai∣≤81 for all 2≤i≤n.
Define S⊆OK by ξ∈S⇔∃x,y,w,z,u,v,s,t,b∈OK:
x2−(a2−1)y2w2−(a2−1)z2u2−(a2−1)v2s2−(b2−1)t2vz2=1=1=1=1≠0∣v
b1∣bi∣∣ui∣∣zi∣b≥22n≤21for 2≤i≤n≥21for 2≤i≤n≥21for 2≤i≤n≡1mod(z)
bst22n+1≡amod(u)≡xmod(u)≡ξmod(z)i=0∏n−1(ξ+i)nj=0∏n−1(x+j)n∣∣z
Then N⊆S⊆Z.
Let K≠Q be a totally real number field of degree n=[K:Q] and let a∈OK satisfy
a1≥22n,∣ai∣≤81 for all 2≤i≤n.
Define S⊆OK by ξ∈S⇔∃x,y,w,z,u,v,s,t,b∈OK:
x=±xk(a),w=±xh(a),u=±xm(a),s=±xj(b),vz2y=±yk(a)z=±yh(a)v=±ym(a)t=±yk(b)≠0∣v
b1∣bi∣∣ui∣∣zi∣b≥22n≤21for 2≤i≤n≥21for 2≤i≤n≥21for 2≤i≤n≡1mod(z)
bst22n+1≡amod(u)≡xmod(u)≡ξmod(z)i=0∏n−1(ξ+i)nj=0∏n−1(x+j)n∣∣z
Then N⊆S⊆Z.
Let K be a totally real number field. Then Z is Diophantine over OK.
Use Minkowski’s theorem on convex bodies to find an a∈OK satisfying the estimates in the previous lemma.
Then N⊆S⊆Z is Diophantine over OK, and {−1,1} is Diophantine as well. Now
α∈Z⇔∃s,ξ:α=sξ∧(s−1)(s+1)=0∧ξ∈S
Denef, J. 1980. “Diophantine Sets over Algebraic Integer Rings. II.” Trans. Amer. Math. Soc. 257 (1): 227–36. https://doi.org/10.2307/1998133.
Denef, J., and L. Lipshitz. 1978. “Diophantine Sets over Some Rings of Algebraic Integers.” J. London Math. Soc. (2) 18 (3): 385–91. https://doi.org/10.1112/jlms/s2-18.3.385.
Gödel, Kurt. 1931. “Über Formal Unentscheidbare Sätze Der Principia Mathematica Und Verwandter Systeme I.” Monatsh. Math. Phys. 38 (1): 173–98. https://doi.org/10.1007/BF01700692.
Hilbert, David. 1900. “Mathematische Probleme. Vortrag, Gehalten Auf Dem Internationalen Mathematiker-Kongreß Zu Paris 1900.” Nachrichten von Der Königl. Gesellschaft Der Wissenschaften Zu Göttingen., 253–79.
Matijasevič, Ju. V. 1970. “The Diophantineness of Enumerable Sets.” Doklady Akademii Nauk SSSR 191: 279–82.
Pheidas, Thanases. 1988. “Hilbert’s Tenth Problem for a Class of Rings of Algebraic Integers.” Proc. Amer. Math. Soc. 104 (2): 611–20. https://doi.org/10.2307/2047021.
Robinson, Julia. 1959. “The Undecidability of Algebraic Rings and Fields.” Proc. Amer. Math. Soc. 10: 950–57. https://doi.org/10.2307/2033628.
Rosser, Barkley. 1936. “Extensions of Some Theorems of Gödel and Church.” Journal of Symbolic Logic 1 (3): 87–91. https://doi.org/10.2307/2269028.
Rumely, Robert S. 1986. “Arithmetic over the Ring of All Algebraic Integers.” J. Reine Angew. Math. 368: 127–33. https://doi.org/10.1515/crll.1986.368.127.
Shapiro, Harold N., and Alexandra Shlapentokh. 1989. “Diophantine Relationships Between Algebraic Number Fields.” Comm. Pure Appl. Math. 42 (8): 1113–22. https://doi.org/10.1002/cpa.3160420805.
Shlapentokh, Alexandra. 1989. “Extension of Hilbert’s Tenth Problem to Some Algebraic Number Fields.” Comm. Pure Appl. Math. 42 (7): 939–62. https://doi.org/10.1002/cpa.3160420703.
van den Dries, Lou. 1988. “Elimination Theory for the Ring of Algebraic Integers.” J. Reine Angew. Math. 388: 189–205. https://doi.org/10.1515/crll.1988.388.189.