ABSTRACT
 DIOPHANTINE GENERATION, GALOIS THEORY, AND HILBERT’S TENTH
 PROBLEM
 by
 Kendra Kennedy
 April, 2012
 Chair: Dr. Alexandra Shlapentokh
 Major Department: Mathematics
 Hilbert’s Tenth Problem was a question concerning existence of an algorithm to
 determine if there were integer solutions to arbitrary polynomial equations over Z.
 Building on the work by Martin Davis, Hilary Putnam, and Julia Robinson, in 1970
 Yuri Matiyasevich showed that such an algorithm does not exist. One can ask a similar
 question about polynomial equations with coe cients and solutions in the rings of
 algebraic integers. In this thesis, we survey some recent developments concerning
 this extension of Hilbert’s Tenth Problem. In particular we discuss how properties
 of Diophantine generation and Galois Theory combined with recent results of Bjorn
 Poonen, Barry Mazur, and Karl Rubin show that the Shafarevich-Tate conjecture
 implies that there is a negative answer to the extension of Hilbert’s Tenth Problem
 to the rings of integers of number  elds.

DIOPHANTINE GENERATION, GALOIS THEORY, AND HILBERT’S TENTH
 PROBLEM
 A Thesis
 Presented to
 The Faculty of the Department of Mathematics
 East Carolina University
 In Partial Ful llment
 of the Requirements for the Degree
 Master of Arts in Mathematics
 by
 Kendra Kennedy
 April, 2012
Copyright 2012, Kendra Kennedy
DIOPHANTINE GENERATION, GALOIS THEORY, AND HILBERT’S TENTH
 PROBLEM
 by
 Kendra Kennedy
 APPROVED BY:
 DIRECTOR OF THESIS:
 Dr. Alexandra Shlapentokh
 COMMITTEE MEMBER:
 Dr. M.S. Ravi
 COMMITTEE MEMBER:
 Dr. Chris Jantzen
 COMMITTEE MEMBER:
 Dr. Richard Ericson
 CHAIR OF THE DEPARTMENT
 OF MATHEMATICS:
 Dr. Johannes Hattingh
 DEAN OF THE
 GRADUATE SCHOOL:
 Dr. Paul Gemperline
ACKNOWLEDGEMENTS
 I would  rst like to express my deepest gratitude to my thesis advisor, Dr.
 Shlapentokh. It was not only a great pleasure, but an honor for me to work with her.
 I am thankful for her guidance, encouragement, and faith in me throughout the thesis
 process. Also, I appreciate the amount of time she spent making sure I understood
 the material fully, prompting its success.
 Next, I want to give a special thanks to Dr. Benson for his guidance, time,
 and support during my graduate studies at East Carolina University. I would like to
 recognize my teaching mentor, Dr. Ries, who has always provided excellent advice and
 words of encouragement. Additionally, I want to thank my undergraduate advisor,
 Dr. Poliakova, who inspired me to pursue mathematics.
 For encouraging me to pursue my dreams and believing that I am capable,
 I want to thank my family, especially my parents, for their unending support. I
 dedicate this thesis to them.
TABLE OF CONTENTS
 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
 2 Computability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
 2.1 Computable Sets and Functions . . . . . . . . . . . . . . . . . . . . . 2
 2.2 Some Examples of Computable and Non-computable Sets . . . . . . . 4
 2.3 Computable and Non-computable Rings and Fields . . . . . . . . . . 5
 3 Galois Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
 4 Diophantine Generation and Hilbert’s Tenth Problem . . . . . . . . . . . 26
 4.1 Diophantine De nitions and Field-Diophantine De nitions . . . . . . 26
 4.2 Coordinate Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 30
 4.3 Diophantine Generation . . . . . . . . . . . . . . . . . . . . . . . . . 34
 4.4 Rings of Integers of Number Fields . . . . . . . . . . . . . . . . . . . 46
 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
CHAPTER 1: Introduction
 In the 1900s, David Hilbert proposed a list of 23 problems that would greatly in-
  uence mathematics in the twentieth century. His tenth problem, known as Hilbert’s
 Tenth Problem (HTP), dealt with the solvability of Diophantine equations. In par-
 ticular, he wanted to know whether it was possible to create an algorithm that could
 tell whether a polynomial equation in many variables had solutions in the integers.
 After many years, it was discovered that no such algorithm existed. Yuri Matiya-
 sevich proved that Diophantine subsets of Z were the same as computably enumerable
 sets. His proof was based on the earlier work of Martin Davis, Hilary Putnam, and
 Julia Robinson. (See [4] for the details of the solution of the original problem.) The
 fact that Diophantine and recursively enumerable sets were the same implied that
 Hilbert’s Tenth Problem was unsolvable. The solution to Hilbert’s Problem gave rise
 to new questions; in particular, whether HTP was solvable over rings of integers of
 number  elds. In this thesis, we consider some of the developments which led to a
 partial answer to this question.
 This thesis is divided into the following sections: the  rst chapter presents the
 necessary background from Recursion Theory and explains the exact nature of the
 result by Yuri Matiyasevich, Martin Davis, Hilary Putnam, and Julia Robinson; the
 second chapter introduces the necessary material from Algebra and more speci cally,
 Galois Theory; the third section introduces the notion of Diophantine generation and
 explains the main results concerning rings of integers of number  elds.
CHAPTER 2: Computability
 This chapter contains some basic information on computable functions, sets, rings,
 and  elds. In this chapter and throughout, we will use the terms \computable,"
 \decidable," and \recursive" interchangeably.
 In addition, throughout this thesis we will use Z 0 to mean non-negative integers
 and Z>0 to mean positive integers.
 2.1 Computable Sets and Functions
 First we want to de ne computable sets. In order to do this, we must de ne the
 characteristic function of a set.
 De nition 2.1 (Characteristic Function). For A  Zm 0, the characteristic function
 is de ned in the following way:
  A : Zm 0 ! f0; 1g
  A(x1; :::; xm) =
 8
 >><
 >>:
 1 if (x1; :::; xm) 2 A
 0 if (x1; :::; xm) =2 A:
 We now de ne computable functions, computable sets, and computably enumer-
 able sets.
 De nition 2.2.
  If f : Zm 0  ! Z
 k
  0 for some positive integers m and k, then f is called com-
 putable if there exists a computer program or an algorithm to compute f .
  If A  Zm 0 and  A is computable, then we say the set is computable.
3
  If there is an algorithm or a computer program that can list the elements of a
 set, we say the set is computably enumerable.
 The following classical theorem laid the ground work for solving HTP. (See [7] for
 more details.)
 Theorem 2.3. There are computably enumerable sets that are not computable.
 In particular, the following famous set is computably enumerable but not com-
 putable.
 Example 2.4. Let ’n be the nth program in the listing of all possible programs and
 de ne the Halting Set as follows:
 K = fnj’n(n) terminates on input ng:
 Before we can state the main theorem that led to the solution of Hilbert’s Tenth
 Problem, we need to introduce the notion of Diophantine sets.
 De nition 2.5. Let R be an integral domain. Let m and n be positive integers. Let
 A  Rn. We say A has a Diophantine de nition over R if there exists a polynomial
 f(y1; :::; yn; x1; :::; xm) 2 R[y1; ::; yn; x1; :::; xm]
 such that for all (t1; :::; tn) 2 Rn, we have
 (t1; :::; tn) 2 A, 9x1; :::; xm 2 R; f(t1; :::; tn; x1; :::; xm) = 0:
 This set A is called Diophantine over R.
 Now we state an example of a Diophantine set over Z.
4
 Example 2.6. The set of even integers
 fy 2 Zj9x 2 Z : y = 2xg
 is a Diophantine set over Z.
 Yuri Matiyasevich, Martin Davis, Hilary Putnam, and Julia Robinson proved the
 following theorem that we will refer to as the MDPR Theorem.
 Theorem 2.7. Diophantine sets of tuples of nonnegative integers are the same as
 computably enumerable sets.
 There are two immediate corollaries of the MDPR Theorem.
 Corollary 2.8. There are Diophantine sets which are undecidable.
 Corollary 2.9. HTP is unsolvable.
 Proof. Indeed, suppose A  Z is a non-recursive Diophantine set with a Diophantine
 de nition P (T;X1; : : : ; Xk). Assume also that we have an algorithm to determine the
 existence of integer solutions for polynomials. Now, let a 2 Z and observe that a 2 A
 if and only if P (a;X1; : : : ; XK) = 0 has solutions in Zk. So if we can answer Hilbert’s
 question algorithmically, we can determine the membership in A algorithmically.
 2.2 Some Examples of Computable and Non-computable Sets
 An example of a decidable set is the set of all primes. The set of all primes is
 decidable because we can test algorithmically for primality. Now we consider whether
 a subset of all the primes is decidable or not.
 Claim 2.10. Let P = f2; 3; 5; :::g = fP1; P2; P3; :::g be the set of all primes. Let
 A = fPi1 ; :::; Pik ; ::g be a subset of primes. Let I = fi1; :::; ik; :::g be the indexes of the
 primes in A. In this case, A is decidable if and only if I is decidable.
5
 Proof. Suppose I is decidable. Let n 2 Z 0 and consider the following procedure for
 determining whether n 2 A.
 Procedure:
 1. Determine if n is a prime. If not, then n =2 A. If yes, proceed to step 2.
 2. Find i such that n = Pi. List P until n occurs.
 3. Check whether i 2 I. If yes, n 2 A. If no, n =2 A.
 Conversely, assume A is decidable. We will show I is decidable. Let i 2 Z>0 be given.
 Consider the procedure below to determine whether i 2 I.
 Procedure:
 1. Find Pi. That is, list P1; P2; :::; Pi until we reach Pi.
 2. Check whether Pi 2 A. If yes, i 2 I. If not, i =2 I.
 2.3 Computable and Non-computable Rings and Fields
 De nition 2.11. A ring R is recursive (computable) if there exists an injective map
 j : R! Z 0 such that
 1. j(R) is computable
 2. f(j(a); j(b); j(c))jc = a+ bg is computable.
 3. f(j(a); j(b); j(c))jc = abg is computable.
 We observe that Z and Q are recursive, since the set of all integers can be rep-
 resented as a pair of non-negative integers (a; b), where a = 0 if the integer is non-
 negative and a = 1 otherwise, and b is the absolute value of the integer. Similarly, Q
6
 can be represented by a triple of non-negative integers. Further, it is easy to describe
 addition, multiplication, and division using these codes.
 We continue with two examples which show that it is not hard to construct rings
 and  elds that are not computable.
 Example 2.12. Let I be an undecidable set and let A = fPiji 2 Ig be an undecidable
 set of primes. Then we have that F = Q(
 p
 Pi; i 2 I) is an undecidable  eld.
 Example 2.13. Let I be an undecidable set of primes and let S = fPiji 2 Ig. Then
 we have that OQ;S = fmn jm 2 Z; n 2 Z6=0; n is divisible by primes in S onlyg is an
 undecidable ring.
 In general we have the following result whose proof can be found in [8][Appendix
 A].
 Theorem 2.14. If R is a recursive integral domain and there is an algorithm to
 determine if an element of R has an inverse, then
 1. the fraction  eld of R is recursive,
 2. any  nite extension of the fraction  eld is recursive, and
 3. the integral closure of R in a  nite extension is recursive.
CHAPTER 3: Galois Theory
 Our goal in this chapter is to survey the results from Galois Theory that will be
 used to show the undecidability of Hilbert’s Tenth Problem over number  elds. As a
 general reference for this material we recommend [1] and [2]. All the  elds we consider
 below will be of characteristic zero. We start with the notion of  eld homomorphism.
 De nition 3.1 (Field Homomorphism). Let K and L be  elds and let  : K  ! L
 be such that  (0K) = 0L and  (1K) = 1L, and for any two elements x; y 2 K we have
 that  (x + y) =  (x) +  (y) and  (xy) =  (x) (y). In this case,  is called a  eld
 homomorphism. If  is a bijection, then  is called an isomorphism. If K = L and  
is a bijection, then  is called an automorphism.
 Remark 3.2. It is not hard to show that a  eld homomorphism sends multiplicative
 and additive inverses to multiplicative and additive inverses.
 We will now discuss several important properties of  elds and homomorphisms.
 Proposition 3.3. If  : Q! Q is a homomorphism, then  is the identity map.
 Proof. Since  is a homomorphism for both addition and multiplication, we have that
  (0) = 0 and  (1) = 1. By induction, for n 2 Z>0 we have
  (n) =  (1 + 1 + :::+ 1
 | {z }
 n times
 ) =  (1) +  (1) + :::+  (1)
 | {z }
 n times
 = 1 + 1 + :::+ 1
 | {z }
 n times
 = n:
 Since  ( x) =   (x) for all x 2 Q, we have that  ( n) =   (n) =  n for all
 n 2 Z>0. Similarly, for any x 2 Q ,  
 
1
 x
  
=
 1
  (x)
 , and therefore for any m 2 Z6=0
 we have  
 
1
 m
  
=
 1
  (m)
 =
 1
 m
 . Finally, let x = PQ be any non-zero element of Q with
 Q 6= 0, and observe that  (x) =  
 
P
 Q
  
=
  (P )
  (Q)
 =
 P
 Q
 .
8
 Corollary 3.4. The only automorphism of Q is the identity map.
 De nition 3.5. A  eld G is algebraically closed if every polynomial over G has a
 root in G.
 De nition 3.6. If F is a  eld, then the algebraic closure of F is the smallest alge-
 braically closed  eld containing F .
 De nition 3.7. Let E be an algebraic extension of a  eld F . In this case,  2 E
 and  2 E are called conjugate over F if irr( ; F ) = irr( ; F ), where irr( ; F ) is
 the monic irreducible polynomial for  over F and irr( ; F ) is the monic irreducible
 polynomial for  over F . In particular,  and  are zeros of the same irreducible
 monic polynomial over F .
 Proposition 3.8. Let G=F be a  nite extension generated by  2 G. Let 1;  ; :::;  n 1
 be the basis of G=F generated by powers of  . In this case,  j =
 Pn 1
 i=1 Ai;j 
i,
 where Ai;j depend only on i and j and the irreducible polynomial of  . More specif-
 ically, Ai;j is a  xed polynomial in the coe cients of irr( ; F ). In other words,
 Ai;j = Pi;j(B0; : : : ; Bn 1), where B0; : : : ; Bn 1 are the coe cients of the irreducible
 polynomial of  over F and each Pi;j(x0; : : : ; xn 1) 2 F [xo; :::; xn 1] is  xed.
 Proof. We proceed by induction.
 Base Case:
 For j = 0; :::; n 1, we have Pi;i = 1 for i = j and Pi;j = 0 for i 6= j.
 Induction Step:
 Assume for j  k, we have  j =
 Pn 1
 i=0 Ai;j 
i. We want to show  k+1 =
 Pn 1
 i=0 Ai;k+1 
i.
 We have  n +Bn 1 n 1 + :::+B0 = 0. Multiplying by  m, we obtain
  n+m +Bn 1 
n 1+m + :::+B0 
m = 0:
9
 Now assuming k + 1  n and k + 1 n = m, we obtain
  k+1 +Bn 1 
k + :::+B0 
m = 0:
 Thus,
  k+1 =  
n 1X
 r=1
 Bn r 
k r+1:
 By the induction hypothesis, we have
  k+1 =  
n 1X
 r=1
 Bn r
 n 1X
 i=0
 Ai;k r+1 
i:
 Thus,
  k+1 =
 n 1X
 i=0
 n 1X
 r=1
 Ai;k r+1Bn r 
i
 =
 n 1X
 i=0
  i
  
n 1X
 r=1
 Ai;k r+1Bn r
 !
 ;
 where
 Pn 1
 r=1 Ai;k r+1Bn r is a polynomial in B0; : : : ; Bn 1 depending only on i; k, and
 n.
 Theorem 3.9. Let F be a  eld and let  and  be conjugate over F with
 deg( ; F ) = deg( ; F ) = n;
 where deg( ; F ) is the degree of  over F and deg( ; F ) is the degree of  over F .
 In this case,
   ; : F ( )! F ( )
10
 de ned by
   ; (a0 + a1 + :::+ an 1 
n 1) = a0 + a1 + :::+ an 1 
n 1
 is an isomorphism of  elds.
 Proof. By de nition, we have
   ; (a0 + a1 + :::+ an 1 
n 1) = a0 + a1 + :::+ an 1 
n 1 2 F ( ):
 Thus, we have a well-de ned map whose domain is all of F ( ).
 We now show that   ; is a homomorphism of  elds. For addition, we have
   ; 
 
n 1X
 i=0
 ai 
i +
 n 1X
 i=0
 bi 
i
 !
 =   ; 
 
n 1X
 i=0
 (ai + bi) 
i
 !
 (by the distributive law)
 =
 n 1X
 i=0
 (ai + bi) 
i (by de nition)
 =
 n 1X
 i=0
 ai 
i +
 n 1X
 i=0
 bi 
i (by distributivity)
 =   ; 
 
n 1X
 i=0
 ai 
i
 !
 +   ; 
 
n 1X
 i=0
 bi 
i
 !
 (by de nition)
 For multiplication, we have the following equalities which hold in part by Proposi-
 tion 3.8 (we are using the same notation as in this proposition)
   ; 
  
n 1X
 i=0
 ai 
i
 ! 
n 1X
 j=0
 bj 
j
 !!
 =   ; 
 
n 1X
 i;j=0
 aibj 
i+j
 !
 =   ; 
  
n 1X
 i;j=0
 aibj
 ! 
n 1X
 k=0
 Ai+j;k 
k
 !!
 =   ; 
 
n 1X
 k=0
  
2n 2X
 m=0
 n 1X
 i+j=m;i;j=0
 Am;kaibj
 !
  k
 !
11
 =
 n 1X
 k=0
  
2n 2X
 m=0
 n 1X
 i+j=m;i;j=0
 Am;kaibj
 !
  k
 =
  
n 1X
 i;j=0
 aibj
 ! 
n 1X
 k=0
 Ai+j;k 
k
 !
 =
 n 1X
 i;j=0
 aibj 
i+j(since  and  are conjugates)
 =
  
n 1X
 i=0
 ai 
i
 ! 
n 1X
 j=0
 bj 
j
 !
 =   ; 
 
n 1X
 i=0
 ai 
i
 !
   ; 
 
n 1X
 j=0
 bj 
j
 !
 Now, we must show that   ; is a bijection. First note that   ; is onto since every
 element of F ( ) is of the form
 Pn 1
 i=0 ai 
i =   ; (
 Pn 1
 i=0 ai 
i). Now, let us show that
   ; is one-to-one. Suppose   ; (
 Pn 1
 i=0 ai 
i) =   ; (
 Pn 1
 i=0 bi 
i). In this case, we have
 (
 Pn 1
 i=0 ai 
i) = (
 Pn 1
 i=0 bi 
i). Thus, ai = bi for i = 0; 1; :::; n 1, since f1; : : : ;  n 1g is
 a basis of F ( ) over F . Hence,
 Pn 1
 i=0 ai 
i =
 Pn 1
 i=0 bi 
i.
 The following lemma is a generalization of the previous theorem.
 Lemma 3.10. Let F and F 0 be  elds and let  be algebraic over F and  be algebraic
 over F 0. Further, let p(x) =irr( ; F ) and q(x) =irr( ; F 0). Let  : F  ! F 0 be an
 isomorphism of  elds such that
  (p(x)) = q(x):
 Now extend
  : F ( )! F 0( )
12
 by setting
  
0
 @
 n 1=deg(p(x)) 1X
 i=0
 ai 
i
 1
 A =
 n 1=deg(p(x)) 1X
 i=0
  (ai) 
i
 for any n-tuple a0; : : : ; an 1 2 F . In this case, the extended  is an isomorphism of
  elds.
 Proof. First notice that we have p(x) is irreducible if and only if q(x) is irreducible.
 That is, deg(p(x)) = deg(q(x)). Thus, we have that the extended  is a bijection
 because f1;  ; ::;  n 1g and f1;  ; :::;  n 1g are bases of F ( ) over F and F 0( ) over
 F 0 respectively and because  is a bijection.
 Now it remains to show that the extended  is a homomorphism. Here we use the
 fact that we are working with  elds of characteristic zero. For any i 2 Z 0, we have
 that
  i =
 n 1X
 j=0
 Ai;j 
j =
 n 1X
 j=0
 Qi;j(a0; :::; an 1) 
j;
 where Ai;j = Qi;j(a0; :::; an 1), a0 + a1x+ : : :+xn = irr( ; F ); and Qi;j(x0; :::; xn 1) 2
 Q[x0; :::; xn 1] is a  xed polynomial over Q depending on i; j and n only by Proposition
 3.8. First we see that
  (Ai;j) =  (Qi;j(a0; :::; an 1)) = Qi;j( (a0); :::;  (an 1));
 since the coe cients of Qi;j are in Q and are not be moved by  by Proposition 3.3.
 Let x =
 Pn 1
 i=0 ci 
i and y =
 Pn 1
 i=0 bi 
i where ci 2 F and bi 2 F . For addition, we
 have
  (x+ y) =  
 
n 1X
 i=0
 ci 
i +
 n 1X
 i=0
 bi 
i
 !
 =  
 
n 1X
 i=0
 (ci + bi) 
i
 !
13
 =
 n 1X
 i=0
 (ci + bi) 
i
 =
 n 1X
 i=0
 ci 
i +
 n 1X
 i=0
 bi 
i
 =
 n 1X
 i=0
  (ci) 
i +
 n 1X
 i=0
  (bi) 
i:
 For multiplication, we have
  (xy) =  
  
n 1X
 i=0
 ci 
i
 ! 
n 1X
 j=0
 bj 
j
 !!
 =  
 
n 1X
 i;j=0
 cibj 
i+j
 !
 =  
 
n 2X
 k=0
  
X
 i+j=k
 cibj
 !
  k
 !
 =  
 
n 2X
 k=0
  
kX
 r=0
 crbk r
 ! 
n 1X
 i=0
 Qi;k(a0; :::; an 1) 
i
 !!
 =  
 
n 1X
 i=0
  
n 2X
 k=0
 kX
 r=0
 crbk rQi;k(a0; :::; an 1)
 !
  i
 !
 =
 n 1X
 i=0
  
n 2X
 k=0
 kX
 r=0
  (cr) (bk r)Qi;k ( (a0); :::;  (an 1))
 !
  i
 =
  
n 1X
 i=0
  (ci) 
i
 ! 
n 1X
 j=0
  (bj) 
i
 !
 =  (x) (y):
 Thus,  is a homomorphism.
 We continue with more properties of  eld homomorphisms.
 Proposition 3.11. Let F be a  eld and let  be algebraic over F . Let  F be the
 algebraic closure of F . Let  : F ( ) !  F with  jF = id. In this case,  ( ) is a
14
 conjugate of  over F in the algebraic closure.
 Proof. Let f(T ) = ao + a1T + ::: + T n be the irr( ; F ). We have that f( ) = 0.
 Furthermore, for ai 2 F , we have a0 + a1 + :::+  n. Thus, we have
 a0 + a1 ( ) + :::+ ( ( ))
 n = 0:
 De nition 3.12. If  is an isomorphism of F onto some  eld, then an element a of
 E is  xed by  if  (a) = a. Furthermore, a collection S of isomorphisms of E leaves
 a sub eld F of E  xed if each a 2 F is  xed by every  2 S. In addition, we say that
  leaves F  xed if S = f g leaves F  xed.
 Theorem 3.13. Let f i; i 2 Ig be a collection of isomorphisms of a  eld E. Then
 Ef ig = fa 2 Ej i(a) = a for all i 2 Ig is a sub eld of E.
 Proof. First note that f0; 1g 2 E by the de nition of isomorphism. Let a 2 Ef ig
 and b 2 Ef ig. Then we have that  i(a + b) =  i(a) +  i(b) = a + b and  i(a  b) =
  i(a)  i(b) = a b. In addition, we have  i(ab) =  i(a) i(b) = ab, and for b 6= 0 we
 have  i
  a
 b
  
=
  i(a)
  i(b)
 =
 a
 b
 .
 Theorem 3.14. The set of all automorphisms of a  eld E is a group under compo-
 sition.
 Proof. Let  : E ! E and  : E ! E be automorphisms. That is,  and  are
 bijections and isomorphisms. We must show that    is a bijection and that    is
 a homomorphism. First we know that a composition of two bijections is a bijection
 itself. Thus, it remains to show    is a homomorphism. Let x 2 E and y 2 E.
15
 Then we have
 (   )(x+ y) =  ( (x+ y))
 =  ( (x) +  (y)) since  is a homomorphism
 =  ( (x)) +  ( (y)) since  is a homomorphism
 = (   )(x) + (   )(y)
 and
 (   )(xy) =  ( (xy))
 =  ( (x) (y)) since  is a homomorphism
 =  ( (x)) ( (y)) since  is a homomorphism
 = ((   )(x))((   )(y)):
 Also, we have that the identity map is an automorphism of E and the inverse of an
 automorphism is also an automorphism of E. Thus, we have that E is a group under
 function composition.
 Theorem 3.15. Let E be a  eld and let F be a sub eld of E. Then the set G(E=F )
 of all automorphisms of E leaving F  xed is a group and F  EG(E=F ).
 Proof. Let  and  be automorphisms of E  xing F . We need to show that    
also  xes F . If x 2 F , then we have (   )(x) =  ( (x)) =  (x) = x. Also, note
 that the identity automorphism is in G(E=F ) and furthermore that   1 2 G(E=F ).
 Therefore, we now have that G(E=F ) is a subgroup of the group of all automorphisms
 of E.
 De nition 3.16. In Theorem 3.15, the groupG(E=F ) is the group of automorphisms
16
 of E  xing F is also called the group of E over F .
 To prove the Isomorphism Extension Theorem, we will need to use Zorn’s Lemma
 (an alternative to Axiom of Choice). The following de nition explains the necessary
 terms.
 De nition 3.17. A subset T of a partially ordered set S is a chain if every two
 elements a 2 T and b 2 T are comparable.
 Lemma 3.18 (Zorn’s Lemma). If a partially ordered set S is such that every chain
 in S has an upper bound in S, then S has at least one maximal element.
 We now prove the Isomorphism Extension Theorem.
 Theorem 3.19 (Isomorphism Extension Theorem). Let E=F be an algebraic exten-
 sion of  elds. Let  : F ! F 0 be an isomorphism. Furthermore, let  F 0 be the algebraic
 closure of F 0. In this case,  can be extended to an isomorphism  : E ! E 0   F 0
 such that  (a) =  (a) for all a 2 F .
 Proof. Consider the set of all pairs (L;  ) where L is a sub eld of E containing F ,
 F  L  E and  : L ! L0   F 0 is an isomorphism such that  jF =  . Observe
 that S is not empty since (F;  ) 2 S. So we can also de ne a partial ordering on S
 by setting (L1;  1)  (L2;  2) to mean F  L1  L2 and  2jL1 =  1.
 Let I be any index set. Let T = f(Hi;  i)ji 2 Ig be a chain in S. Let H = [i2IHi
 and note that H  E is a  eld. Indeed, let a 2 H and b 2 H. Since H = [i2IHi,
 then there exists i1 2 I and i2 2 I such that a 2 Hi1 and b 2 Hi2 . Since T is a chain,
 it is totally ordered, and we must have Hi1  Hi2 or Hi2  Hi1 . Without loss of
 generality, assume Hi1  Hi2 and observe that now a; b 2 Hi2 and a+b; a b;
 a
 b
 for b 6=
 0;
 b
 a
 for a 6= 0 are all in Hi2  H.
 Next de ne  : H ! H 0   F 0 by setting  (c) =  i(c), where ci 2 Hi. We need to
17
 show that  (c) does not depend on the choice of i. If c 2 Hj for j 6= i, then either
 (Hj;  j)  (Hi;  i) or (Hi;  i)  (Hj;  j). In the  rst case, we have  ijHj =  j and
 therefore  i(c) =  j(c) =  (c). In the second case, we have  jjHi =  i and therefore
  j(c) =  i(c) =  (c). Thus,  is well-de ned.
 Now we show that  is an injective homomorphism. First let us show that  is
 injective. Let a; b 2 H and assume  (a) =  (b). As above, there exists Hi such that
 a; b 2 Hi and  (a) =  (b) =  i(a) =  i(b), but a = b since  i is injective.
 Next, we show that  is a homomorphism. Let a; b 2 H and let Hi be such that
 a; b 2 Hi which implies that a + b 2 Hi and ab 2 Hi. In this case, since  i is a
 homomorphism we have
  (a+ b) =  i(a+ b)
 =  i(a) +  i(b)
 =  (a) +  (b);
 and we also have
  (ab) =  i(ab)
 = ( i(a))( i(b))
 = ( (a))( (b)):
 Thus, we have shown that (H; ) 2 S and (H; ) is an upper bound for T , Zorn’s
 Lemma applies, and S contains a maximal element ( ;K). Let  : K ! K 0   F 0.
 If K = E, we are done. If K 6= E, then since (K;  ) 2 S and K $ E, there exists
  2 E nK. Since  is algebraic over F ,  is algebraic over K. Let p(x) = irr( ;K)
 and furthermore let q(x) =  (p(x)). Let  2  F 0 be a root of q(x). By Lemma 3.10,
18
 there exists an isomorphism  0 : K( )!  (K( )), which contradicts the assumption
 that (K;  ) was a maximal element of S. Thus, K = E.
 De nition 3.20. Let F be a  eld with algebraic closure  F . Let ffi(x)ji 2 Ig  F [x].
 A  eld E   F is a splitting  eld of ffi(x)ji 2 Ig over F , if it is the smallest  eld
 containing F with all the zeros of fi(x) for each i. A  eld K   F is a splitting  eld
 if it is a splitting  eld of some collection of polynomials over F and F  K.
 Proposition 3.21. Let I be an index set. Let F be a  eld with algebraic closure
  F . Let A = f iji 2 Ig   F be the set of all roots of a collection of one-variable
 polynomials over F . Further, let B = f jjj 2 Jg where  j =
 Q
 i2I  
ai;j
 i and there are
 only  nitely many ai;j that are not zero. Let G = f kjk 2 Kg where  k =
 P
 xj;k j
 is a  nite linear combination with xj;k 2 F . Lastly, let D = f ljl 2 Lg where  l is a
 ratio of two elements from G with the denominator element not equal to zero. In this
 case, we have that D = f ljl 2 Lg is a  eld and is the smallest  eld containing F and
 A, and thus a splitting  eld of the collection of polynomials corresponding to A.
 Proof. First we see that 0; 1 2 D since 0; 1 2 F . Note also that sums and products
 of linear combinations in G are linear combinations in G. Thus, the sum and the
 product of two elements in D is in D. Therefore, D   F must be a  eld.
 Theorem 3.22. A  eld E with F  E   F is a splitting  eld over F if and only if
 for every  :  F !  F such that  jF = id, we have that  (E) = E.
 Proof. Assume E is a splitting  eld and  is an automorphism of  F  xing F . Let
 y 2 E. In this case, in the notation of Proposition 3.21, we have
 y =
  1
  2
 =
 Q1( 1; :::;  k)
 Q2( 1; :::;  k)
19
 where Q1; Q2 2 F [x1; :::; xk]. Now as  leaves F  xed, we have
  (y) =
 Q1( ( 1); :::;  ( k))
 Q2( ( 1); :::;  ( k))
 2 E
 since roots go to roots in  F .
 Conversely, suppose  (E) = E for any automorphism  of  F . We will show E is a
 splitting  eld. If E = F , this covers the polynomial case where deg(p(x)) = 1 and
 nothing else. So now assume E 6= F . We will show E contains all the roots of any
 irreducible over F polynomial with roots in E. If F $ E, let  2 E n F and g(x) =
 irr( ; F ). Let  : F ( )! F ( ) where  is conjugate of  over F . We have previously
 shown
 1.  is an isomorphism (by Theorem 3.9), and
 2. we can extend  to  F (by Lemma 3.10).
 Thus,  2 E.
 Next, we prove two lemmas and a theorem in order to state and prove the Main
 Theorem of Galois Theory.
 Lemma 3.23. Let F be a  eld and let  F be the algebraic closure. In characteristic
 zero, if g(x) is irreducible over F , then in  F all roots of g(x) are distinct.
 Proof. Assusme g(x) has a root a of multiplicity n > 1. In  F , factor g(x) =
 (x a)nh(x) and note that gcd(h(x); (x a)) = 1. Thus, we have that
 g0(x) = n(x a)n 1h(x) + h0(x)(x a)n 6= 0
 since n(x a)n 1h(x) 6= 0, and therefore g0 is divisible by at most n  1-st power
 of (x  a). At the same time, gcd(g(x); g0(x)) = (x a)n 1f(x) 6= g(x) for some
20
 f(x) 2 F [x] prime to (x  a). Hence, h(x) would have a non-trivial factor over F ,
 but this cannot be true. Thus, all roots are distinct.
 De nition 3.24. A  nite extension E=F is a separable extension if every irreducible
 polynomial over F does not have multiple roots in E.
 Theorem 3.25 (Primitive Element Theorem). If E=F is a  nite separable extension
 of in nite  elds, then E = F ( ) for some  2 E. In this case,  is called a primitive
 element and E=F is called a simple extension.
 Proof. Assume E = F ( ;  ). Let  1 =  ; :::;  n be all the conjugates of  over F and
  =  1; :::;  m be the conjugates of  over F . All conjugates are distinct since the
 extension is separable. Since F is in nite, we can  nd a 2 F such that a 6=
 ( i   )
 (   j)
 for i = 1; :::; n and j = 2; :::m. Thus, a(   j) 6= ( i   ).
 Now let  =  + a and f(x) = irr( ; F ). Let h(x) = f(  ax) 2 (F ( ))[x]. Then
 we have h( ) = f(  a ) = f( ) = 0, but h( j) = f(  a j) 6= f( i) for any i
 and for j 6= 1. Therefore, h( j) 6= 0 for j > 1. Indeed, we have  =  + a 6=  i ,
   a j =  + a  a j 6=  i for any i. The last non-equality holds because
  + a = a j +  i )    i = a( j   )
 but this contradicts the fact that a 6=
 ( i   )
 (   j)
 . Therefore, h(x) 6= 0 for any  2; :::;  m.
 Now let g(x) = irr( ; F ). In this case, h(x) and g(x) have a common root. Hence,
 h(x) has a linear factor (x  ) 2 (F ( ))[x]. Thus,  2 F ( ).
 Now since  2 F ( ), then for a 2 F we have a 2 F ( ). Additionally, we have that
  =   a 2 F ( ). Thus, (  a ) + (a ) 2 F ( ) and hence  2 F ( ).
 We have shown F ( ;  )  F ( ). Since  =   a , we have F ( )  F ( ;  ).
 Therefore, F ( ;  ) = F ( ). That is, if we have a  nite separable extension with two
21
 generators, then we can reduce the number of generators to one. By induction, any
 number of  nite generators can be reduced to one.
 Lemma 3.26. Let F be a  eld and  F be the algebraic closure of F . Further, let M
 be a  eld such that F  M   F and the extension M=F is  nite and separable. In
 this case, we have the number of injective homomorphisms  such that  : M !  F
 and  jF = id is the degree of the extension [M : F ].
 Proof. Since the extension M=F is  nite and separable, by the Primitive Element
 Theorem we have that it is simple. That is, the extension M=F is generated by a
 single element  . Any injective homomorphism  such that  : M !  F and  jF = id
 must send  to a conjugate over F by Proposition 3.11, and every conjugate of  
over F also generates an injective homomorphism  with the required properties by
 Theorem 3.9. Thus, the number of such injective homomorphisms is exactly the
 number of conjugates of  over F , which is the degree of the extension.
 Remark 3.27. In this thesis, we have assumed that the characteristic of all the  elds
 under consideration is zero. In this case, all the extensions are separable.
 We now de ne the Galois group and proceed to state the Main Theorem of Galois
 Theory.
 De nition 3.28. Let K be a separable splitting  eld over F and let K be a  nite
 extension of F . In this case, we say that K is a  nite normal extension of F .
 De nition 3.29. Let K be a  nite normal extension over F . In this case, we say
 G(K=F ), as de ned above, is the Galois group of K over F . Further, the extension
 K=F is called a Galois extension.
 Theorem 3.30 (Main Theorem of Galois Theory). Let K be a  nite normal extension
 of a  eld F with a Galois group G(K=F ). For a  eld E where F  E  K, let
22
  (E)  G(K=F ) be the subgroup containing all the elements of G(K=F )  xing E. In
 this case,
  : fintermediate  elds between K and Fg ! fsubgroups of G(K=F )g
 is one-to-one. Further,  has the following properties:
 1.  (E) = G(K=E).
 2. E = KG(K=E) = K (E), where KG(K=E) is the set of elements  xed by the Galois
 group of K over E and K (E) is the set of elements  xed by  (E).
 3. If H  G(K=E), then  (KH) = H, where KH is the set of elements  xed by H.
 4. [K : E] = j (E)j and [E : F ] = [G(K=F ) :  (E)] = the number of left cosets of
  (E) in G(K=F ).
 5. E is a normal extension of F if and only if  (E) is a normal subgroup of
 G(K=F ). Also if  (E) is a normal subgroup of G(K=F ), then
 G(E=F ) =
 G(K=F )
 G(K=E)
 :
 6. Sub elds of K containing F are in bijection with subgroups of G(K=F ).
 Proof. We will prove each property separately.
 1. First clearly we have  (E)  G(K=E) since  (E) is the subgroup of G(K=F )
 keeping E  xed. Now we must show G(K=E)   (E). If  2 G(K=E), then
  is an automorphism of K keeping E  xed and therefore F  xed. Thus,
  2 G(K=F ). Hence, G(K=E)   (E). Therefore,  (E) = G(K=E).
23
 2. Notice that we have E  KG(K=E) since KG(K=E) is a  xed  eld of G(K=E).
 Now we must show KG(K=E)  E. Let  2 K n E. Let f(x) = irr( ;E).
 There exists  : E( ) ! E( ), where  is a conjugate over  over E. By
 the Isomorphism Extension Theorem, we can extend  to  F . Note that  
keeps E  xed. Since K=F is normal,  is an automorphism of K. That is,
  2  (E) = G(K=E)  G(K=F ), and in particular, KG(K=E)  E. Thus,
 KG(K=E) = E. This shows  is one to one.
 3. We will show that  is onto. Clearly, H   (KH). We need to show equality.
 Suppose H $  (KH). By the Primitive Element Theorem, K = KH( ). Let
 n = [K : KH ] = jG(K=KH)j:
 If H $  (KH) = G(K=KH), then we have jHj < n. Let  1; ::;  jHj be all the
 elements of H, and consider f(x) =
 QjHj
 i=1(x  i( )) where deg(f(x)) = jHj < n.
 We claim that the coe cients of f(x) are in H. Indeed, since coe cients of f are
 symmetric functions of f 1( ); :::;  jHj( )g = A, where  1( ); :::;  jHj( ) 2 K
 and  (A) = A for any  2 H, we have [K : KH ] = [KH( ) : K]  jHj < n
 since  ( i( )) =    i( ) =  j( ) because H is a group. Thus, we arrive at a
 contradiction.
 4. We have already shown that for any intermediate  eld E it is the case that
 [K : E] = j (E)j. Thus, it remains to show [E : F ] = [G(K=F ) :  (E)]. First
 notice that we have [K : E] = G(K=E)  G(K=F ) and [K : F ] = jG(K=F )j
 and [K : E][E : F ] = [K : F ]. Thus,
 [E : F ] =
 [K : F ]
 [K : E]
 =
 jG(K=F )j
 jG(K=E)j
 =
24
 index of G(K=E) in G(K=F ) = number of left cosets:
 5. Assume G(K=E) B G(K=F ). To show that E is normal over F , it is enough to
 show that for any  : E !  F such that  F = id it is the case that  (E) = E.
 Any such  can be extended to  : K !  F and since K is normal over F , we
 have  (K) = K so that it is enough to consider  2 G(K=F ). We want to show
 for all  2 E and all  2 G(K=F ), we have  ( ) 2 E.
 By property 2, E is the  xed  eld of G(K=E). Thus, by de nition of  xed  eld,
  ( ) 2 E , 8 2 G(K=E);  ( ( )) =  ( )
 , 8 2 G(K=E);   1   ( ( )) =  
, 8~ 2 G(K=E); ~ ( ) =  ;
 where the last implication is true because G(K=E) is a normal subgroup in G(K=F )
 and conjugation is an automorphism of the group.
 Suppose now that E=F is a normal extension, let  2 G(K=F ),  2 G(K=E),  2 E
 and note that as above, we have  ( ) 2 E and  ( ( )) =  ( ) or   1( ( ( ))) =  .
 Thus,   1     2 G(K=E) or G(K=E) is normal in G(K=F ).
 We  nish with the de nitions of abelian and cyclic extensions and a corollary
 concerning abelian and cyclic Galois groups we will need later.
 De nition 3.31. A  nite normal extension K of a  eld F is abelian over F if G(K=F )
 is an abelian group.
 De nition 3.32. A  nite normal extension K of a  eld F is cyclic over F if G(K=F )
 is a cyclic group.
 Corollary 3.33 (Abelian and Cyclic Extensions).
25
 1. Any subgroup of an abelian group is normal and the quotient group is de ned
 and is also abelian.
 2. If F=K is an abelian extension, then if we have an intermediate  eld E with
 K  E  F , then E=K is Galois and abelian. In general, E=K is normal
 if and only if G(F=E) is normal in G(F=K), the Galois group of F over K.
 However, if G(F=K) is abelian, this is automatically true.
 3. If G is a cyclic group, H  G a subgroup, then H is cyclic and G=H is cyclic.
 4. If F=K is a cyclic extension, then if we have an intermediate  eld E with
 K  E  F , then E=K is Galois and abelian.
CHAPTER 4: Diophantine Generation and Hilbert’s Tenth Problem
 In this chapter we discuss the main results on extensions of Hilbert’s Tenth Prob-
 lem to the rings of integers of number  elds.
 4.1 Diophantine De nitions and Field-Diophantine De nitions
 In this section, we de ne the basic notions we need for the main results. First we
 prove a proposition which will allow us to substitute a single polynomial equation for
 a  nite system of equations.
 Proposition 4.1. Let K be a  eld which is not algebraically closed and let
 h(x) = xn + an 1x
 n 1 + :::+ a0
 be a polynomial without roots in K. Let f(x) 2 K[x] and g(x) 2 K[x]. In this case,
 for all x 2 K, we have
 a0g
 n(x) + a1g
 n 1(x)f(x) + :::+ anf
 n(x) = 0
 m
 f(x) = 0 and g(x) = 0:
 Proof. Assume f(x) = g(x) = 0. Using substitution, we obtain that
 a0g
 n(x) + a1g
 n 1(x)f(x) + :::+ anf
 n(x) = 0:
27
 Conversely, suppose
 a0g
 n(x) + a1g
 n 1(x)f(x) + :::+ anf
 n(x) = 0;
 and also suppose g(x) 6= 0. In this case, dividing
 a0g
 n(x) + a1g
 n 1(x)f(x) + :::+ anf
 n(x) = 0
 by gn(x), we obtain
 a0 + a1
  
f(x)
 g(x)
  
+ a2
  
f(x)
 g(x)
  2
 + :::+ an
  
f(x)
 g(x)
  n
 = 0:
 This implies that f(x)g(x) is a root of h in K.
 Now let
  h(y) = aoy
 n + a1y
 n 1 + :::+ an:
 We claim that  h(y) has no roots in K. Suppose  h(y) = 0 for some y 2 K. Since
 an 6= 0, we conclude that y 6= 0, and we can set x =
 1
 y
 6= 0 2 K. Now we have that
  h
  
1
 x
  
= ao
  
1
 x
  n
 + a1
  
1
 x
  n 1
 + :::+ an = 0:
 Multiplying both sides by xn, we obtain a0 + a1x+ :::+ anxn = 0, which is a contra-
 diction of our assumption on h.
 Now assume
 a0g
 n(x) + a1g
 n 1(x)f(x) + :::+ anf
 n(x) = 0;
28
 but f(x) 6= 0. Dividing the left side by fn(x), we obtain
 a0
  
gn(x)
 fn(x)
  
+ a1
  
gn 1(x)
 fn 1(x)
  
+ :::+ an = 0:
 This implies that  h
  
g(x)
 f(x)
  
= 0, which is a contradiction to the fact that  h(y) has
 no roots in K.
 Thus, if a0gn(x) + a1gn 1(x)f(x) + :::+ anfn(x) = 0, then f(x) = g(x) = 0.
 From this proposition we immediately conclude the following corollary.
 Corollary 4.2. If R is a recursive integral domain with a fraction  eld which is not
 integrally closed, then there exists an algorithm for determining if a single arbitrary
 polynomial equation has solutions in R if and only if there exists an algorithm to
 determine whether an arbitrary  nite system of polynomial equations has solutions in
 R.
 We now review the notions of Diophantine sets and Diophantine de nitions  rst
 discussed in the introduction.
 De nition 4.3. Let R be an integral domain. Let m and n be positive integers. Let
 A  Rn. We say A has a Diophantine de nition over R if there exists a polynomial
 f(y1; :::; yn; x1; :::; xm) 2 R[y1; ::; yn; x1; :::; xm]
 such that for all (t1; :::; tn) 2 Rn, we have
 (t1; :::; tn) 2 A, 9x1; :::; xm 2 R; f(t1; :::; tn; x1; :::; xm) = 0:
 This set A is called Diophantine over R.
29
 Now we will modify the notion of Diophantine de nition to establish the notion
 of  eld-Diophantine de nition.
 De nition 4.4. Let R be an integral domain with a quotient  eld F . Let k and m
 be positive integers. Let A  F k. Assume that there exists a polynomial
 f(a1; :::; ak; b; x1; :::; xm)
 with coe cents in R such that
 8a1; :::; ak; b; x1; :::; xm 2 R;
 f(a1; :::; ak; b; x1; :::; xm) = 0) b 6= 0
 and
 A = f(t1; :::; tk) 2 F
 k j 9a1; :::; ak; b; x1; :::; xm 2 R;
 bt1 = a1; :::; btk = ak; f(a1; :::; ak; b; x1; :::; xm) = 0g:
 In this case, we say that A is  eld-Diophantine over R and will call f a  eld-
 Diophantine de nition of A over R.
 Remark 4.5. It is not hard to see that if R is an integral domain with a quotient
  eld F , then a subset A of Rk has a Diophantine de nition over R if and only if A
 has a  eld-Diophantine de nition over R. Indeed, a Diophantine de nition is a  eld-
 Diophantine de nition with b as above set to 1. Conversely, if f(y1; :::; yk; z; x1; :::; xm)
 is a  eld-Diophantine of a set A  Rk, then
 g(y1; : : : ; yk; z; x1; : : : ; xm) = f(zy1; :::; zyk; z; x1; :::; xm)
30
 is a Diophantine de nition of A over Rk.
 4.2 Coordinate Polynomials
 We will now introduce coordinate polynomials in order to extend the notion of
 Diophantine de nition and the notion of  eld-Diophantine de nition to the notion of
 Diophantine generation.
 Lemma 4.6. Let F=G be a  nite  eld extension. Let  = f!1; :::; !ng be a basis of
 F over G. Then for l = 1; 2:::; n there exist
 Pl(x1; :::; xn; y1; :::; yn) 2 G[x1; :::; xn; y1; :::; yn]
 depending on  only such that for all a1; ::; an; b1; :::bn we have that
 nX
 i=1
 ai!i
 nX
 j=1
 bj!j =
 nX
 l=1
 Pl(a1; ::; an; b1; :::bn)!l:
 Proof. Let fAi;j;l 2 G j i; j; l = 1; :::; ng be a set of elements of G such that !i!j =
 Pn
 l=1Ai;j;l!l. First note this set exists because F is a  eld. By associativity, distribu-
 tivity, commutativity, and reordering, we have
 nX
 i=1
 ai!i
 nX
 j=1
 bj!j =
 nX
 i=1
 nX
 j=1
 ai!ibj!j
 =
 nX
 i=1
 nX
 j=1
 aibj!i!j
 =
 nX
 i;j=1
 aibj!i!j
 =
 nX
 i;j=1
 aibj
 nX
 l=1
 Ai;j;l!l
31
 =
 nX
 i;j=1
 nX
 l=1
 aibjAi;j;l!l
 =
 nX
 l=1
 nX
 i;j=1
 aibjAi;j;l!l
 =
 nX
 l=1
  
nX
 i;j=1
 aibjAi;j;l
 !
 !l
 =
 nX
 l=1
 Pl(a1; ::; an; b1; :::bn)!l
 where Pl(a1; :::; an; b1; :::; bn) =
 Pn
 i;j=1 aibjAi;j;l.
 In a similar manner, we can also prove the following lemma.
 Lemma 4.7. Let F=G be a  nite  eld extension and let  = f!1; :::; !ng be a basis
 of F over G. Let a1; :::; an 2 G. In this case, there exist
 P1; :::; Pn; Q 2 G[x1; :::; xn]
 depending only on F;G; and  such that
 nX
 i=1
 ai!i 6= 0,
 nX
 i=1
 Pi(a1; :::; an)
 Q(a1; :::; an)
 !i =
  
nX
 i=1
 ai!i
 ! 1
 where Q(a1; :::; an) 6= 0. That is,
  
nX
 i=1
 Pi(a1; :::; an)
 Q(a1; :::; an)
 !i
 ! 
nX
 i=1
 ai!i
 !
 = 1
 where Q(a1; :::; an) 6= 0.
 Proof. Let 1 =
 Pn
 i=1Bi!i; Bi 2 G. Let
 Pn
 i=1 bi!i; bi 2 G be the inverse of the given
32
 element and consider the following sequence of equalities:
 nX
 i=1
 ai!i
 nX
 i=1
 bi!i = 1;
 nX
 l=1
 Pl(a1; ::; an; b1; :::bn)!l =
 nX
 l=1
  
nX
 i;j=1
 aibjAi;j;l
 !
 !l =
 nX
 l=1
 Bl!l;
 nX
 i;j=1
 aibjAi;j;l = Bl; l = 1; : : : ; n; and
 nX
 j=1
  
nX
 i=1
 aiAi;j;l
 !
 bj = Bl; l = 1; : : : ; n:
 Thus, we have a linear system in b1; : : : ; bn with a unique solution. The matrix
 C = (cl;j) corresponding to this system has an entry
 Pn
 i=1 aiAi;j;l in the position
 corresponding to l-th row and j-th column, and each entry is a polynomial in the
 coordinates of the original element and the elements of the set fAi;j;lg, and this
 polynomial depends on indexes j, l, and n only. Now the conclusion follows from
 Cramer’s Rule and the fact that the determinant of a matrix is a  xed polynomial in
 its entries which depends on the matrix size only.
 Next we observe a formal property of sums.
 Remark 4.8. If A; ai;j are elements of a  eld, then
 A(a1;1 + :::+ a1;k)    (ab;1 + :::+ ab;k) =
 X
 Aa1;s1a2;s2 :::ab;sb
 where 1  si  k.
 Lemma 4.9. Let M=F be a  nite  eld extension of degree k. Let  = f!1; :::; !kg
33
 be a basis of M over F . If P (T1; :::; Tm) 2 F [T1; :::; Tm] then there exist polynomials
 P 1 (t1;1:::; tm;k); :::; P
  
k (t1;1:::; tm;k) such that
 1. P 1 ; :::; P
  
k depend only on  and
 2. P
  Pk
 j=1 t1;j!j; :::;
 Pk
 j=1 tm;j!j
  
=
 Pk
 j=1 Pj
  (t1;1; :::; tm;k)!j.
 Proof. First by Lemma 4.6, we have
 !i!j =
 kX
 r=1
 Ai;j;r!r
 where Ai;j;r 2 F depend only on  . Thus by induction, for c1; : : : ; ck 2 Z 0, we
 obtain
 kY
 i=1
 !cii =
 kX
 r=1
 Ac1;:::;ck;r!r: (4.1)
 Let deg(P ) = d and let
 P (T1; :::; Tm) =
 X
 j1+:::+jm d; ji 0
 Bj1;:::;jmT1
 j1T2
 j2    Tm
 jm
 =
 X
 j1+:::+jm d;ji 0
 Bj1;:::;jm
  
kX
 r=1
 t1;r!r
 !j1
    
 
kX
 r=1
 tm;r!r
 !jm
 :
 To expand
  Pk
 r=1 t1;r!r
  j1
    
 Pk
 r=1 tm;r!r
  jm
 , we note that we have a product of
34
 the form
 Qe
 u=1
 Pk
 r=1 aur where e  d and
 8
 >>>>>>>>>><
 >>>>>>>>>>:
 au;r = t1;rwr for u = 1; :::; j1
 au;r = t2;rwr for u = j1 + 1; :::; j1 + j2
 ...
 au;r = tm;rwr for u = j1 + j2 + :::+ jm 1 + 1; :::; j1 + j2 + :::+ jm = e:
 Now for e = j1 + :::+ jm, we have
 Bj1;:::;jm
  Pk
 r=1 t1;r!r
  j1
    
 Pk
 r=1 tm;r!r
  jm
 = Bj1;:::;jm
 Qe
 u=1
 Pk
 r=1 au;r
 = Bj1;:::;jm
 P
 s1;:::;se
 a1;s1 : : : ae;se ; 1  si  k (by Remark 4.8)
 = Bj1;:::;jm
 P
 r1;1;:::;rm;jm
 (t1;r1;1 : : : t1;r1;j1 : : : tm;rm;1 : : : tm;rm;jm )(!r1;1 : : : !r1;j1 : : : !rm;1 : : : !rm;jm )
 = Bj1;:::;jm
 P
 i=1;:::;m;j=1;:::;k;ai;j=1;:::;ji
 Ca1;1;:::;am;k;j1;:::;jm
 Q
 i=1;:::;m;j=1;:::;k t
 ai;j
 i;j
 Qk
 e=1 !
 be
 e
 = Bj1;:::;jm
 Q
 i=1;:::;d;j=1;:::;k t
 ai;j;j1;:::;jm
 i;j
 Pk
 r=1 Ab1;:::;bk;r!r (from (4.1)),
 where 1  ri;j  k; 1  e  k; 0  ai;j  ji; be =
 Pm
 i=1 ai;e.
 4.3 Diophantine Generation
 We are now ready to address the central notion of this chapter { the Diophantine
 generation. First we need a preliminary lemma.
 Lemma 4.10. Let R be an integral domain with quotient  eld F . For some positive
 integer k, let A  F k. Let m be a positive integer such that m  k. Assume that A
 has a  eld-Diophantine de nition over R. Let
 B = f(x1; :::; xr) 2 F
 rjxi = Pi(y1; :::; ym);
 (y1; :::; ym; Hm+1(y1; :::; ym); :::; Hk(y1; :::; ym)) 2 Ag;
35
 where P1; :::; Pr; Hm+1; :::; Hk 2 F [y1; :::; ym]. Then B also has a  eld-Diophantine
 de nition over R.
 Proof. Let f(u1; :::; uk; u; z1; :::; zs) be a  eld-Diophantine de nition of A over R. Now
 if we let yi =
 ui
 u
 for i = 1; :::;m we have
 B = f(x1; :::; xr) 2 F
 rj9u1; :::; uk; u; z1; :::; zs 2 R;
 xi = Pi
  u1
 u
 ; :::;
 um
 u
  
; i = 1; :::; r;
 Hm+1
  u1
 u
 ; :::;
 um
 u
  
; :::; Hk
  u1
 u
 ; :::;
 um
 u
  
; f(u1; :::; uk; u; z1; :::; zs) = 0g:
 Next if we let yj = Hj
  u1
 u
 ; :::;
 um
 u
  
for j = m + 1; :::; k and use yj =
 uj
 u
 for j =
 m+ 1; :::; k, we can substitute and see that
 yj =
 uj
 u
 = Hj
  u1
 u
 ; :::;
 um
 u
  
) uj = uHj
  u1
 u
 ; :::;
 um
 u
  
for j = m+ 1; :::; k. Now we obtain
 B = f(x1; :::; xr) 2 F
 rj9u1; :::; uk; u; z1; :::; zs 2 R;
 xi = Pi
  u1
 u
 ; :::;
 um
 u
  
; i = 1; :::; r;
 uj = uHj
  u1
 u
 ; :::;
 um
 u
  
; j = m+ 1; :::; k; f(u1; :::; uk; u; z1; :::; zs) = 0g:
 Let dH be the highest degree of Hm+1; :::; Hk. Let DH be a common denominator of
 all the coe cients of Hm+1; :::; Hk. Let
  Hj(u1; :::; um; u) = DHu
 dHHj
  u1
 u
 ; :::;
 um
 u
  
for j = m+ 1; :::; k. Here we used the fact that R is an integral domain with quotient
36
  eld F to eliminate our denominators. Also, note that udH eliminates the u’s in the
 denominators. Similarly, we let d be the highest degree of P1; :::; Pr, and let D be a
 common denominator of all the coe cients of P1; :::; Pr in R. Let
  Pi(u1; :::; um; u) = u
 dDPi
  u1
 u
 ; :::;
 um
 u
  
2 R[u1; :::; um; u]
 for i = 1; :::; r. Thus, we now obtain
 B = f(x1; :::; xr) 2 F
 rj9u1; :::; uk; u; z1; :::; zs 2 R;
 u  Hj(u1; :::; um; u) = DHu
 dHuj; j = m+ 1; :::; k;
 udDxi =  Pi(u1; :::; um; u); i = 1; :::; r; f(u1; :::; uk; u; z1; :::; zs) = 0g;
 and further obtain
 B = f(x1; :::; xr) 2 F
 rj9u1; :::; uk; u; z1; :::; zs 2 R;
 uxi = ui; u = Du
 d; ui =  Pi(u1; :::; um; u); i = 1; :::; r;
  Hj(u1; :::; um; u) = DHu
 dH 1uj; j = m+ 1; :::; k; f(u1; :::; uk; u; z1; :::; zs) = 0g:
 Thus, B has a  eld-Diophantine de nition over R.
 Next, we de ne the notion of Diophantine generation, generalizing further the
 notion of Diophantine de nition.
 De nition 4.11 (Diophantine Generation). Let R1 and R2 be two rings with quotient
  elds F1 and F2 respectively. Assume that neither F1 nor F2 is algebraically closed.
 Let F be a  nite extension of F1 such that F2  F . Also, assume that for some basis
  = f!1; :::; !kg of F over F1, there exists a polynomial f(a1; :::; ak; b; x1; :::; xm) with
37
 coe cients in R1 such that
 f(a1; :::; ak; b; x1; :::; xm) = 0) b 6= 0
 and
 R2 = f
 kX
 i=1
 ti!i j 9a1; :::; ak; b; x1; :::; xm 2 R1;
 bt1 = a1; :::; btk = ak; f(a1; :::; ak; b; x1; :::; xm) = 0g:
 In this case, we say that R2 is Dioph-generated over R1 and denote this as
 R2  Dioph R1:
 Further, we sayf(a1; :::; ak; b; x1; :::; xm) is a de ning polynomial of R2 over R1. Ad-
 ditionally, we say  = f!1; :::; !kg is a Diophantine basis of R2 over R1 and F is the
 de ning  eld for the basis  .
 We now state an example of Diophantine generation.
 Example 4.12. Let F=G be a  nite extension of degree k with basis  of F over G.
 Then we have that F  Dioph G since for each z 2 F we can write z =
 Pk
 i=1 ai!i.
 We now consider properties of Diophantine generation and prove that it is transi-
 tive. First we state a lemma which follows directly from the de nition of Diophantine
 generation.
 Lemma 4.13. Let R1 and R2 be integral domains with quotient  elds F1 and F2
 respectively. Let F be a  nite extension of F1 such that F2  F . In this case, we can
 conclude that R2  Dioph R1 if there exists a basis  = f!1; ::; !kg of F over F1 and a
38
 set A  F1
 k with a  eld-Diophantine de nition over R1 such that
 R2 =
 (
 kX
 i=1
 zi!ij(z1; :::; zk) 2 A 
)
 : (4.2)
 Conversely, if F is a de ning  eld and  is a corresponding Diophantine basis of
 R2 over R1, then R2 has a representation of the form 4.2, where A  F1
 k is  eld-
 Diophantine over R1.
 Notation 4.14. A will be called a de ning set for the basis  .
 Notation 4.15. Let G=F be a  nite  eld extension. Let  = f!1; :::; !kg be a basis
 of G over F . For some positive integer n, let B  Gn. Then de ne B  F kn to be
 the set such that
 (a1;1; :::; ak:n) 2 B
  ,
  
kX
 i=1
 ai;1!i; :::;
 kX
 i=1
 ai;n!i
 !
 2 B:
 Using this notation for rings R1 and R2 such that R2  Dioph R1 with a Diophantine
 basis  as above, we can conclude by Lemma 4.13 that R 2  F
 n
 1 is  eld Diophantine
 over R1, where F1 is the fraction  eld of R1.
 We now show that the notion of Diophantine generations is a proper extension of
 both the notion of  eld-Diophantine de nition and the notion of Diophantine de ni-
 tion.
 Proposition 4.16. Let R1 and R2 be integral domains with quotient  elds F1 and F2
 respectively such that R2  Dioph R1. Let F be a de ning  eld and let  = f!1; :::; !kg
 be a Diophantine basis of R2 over R1. Let B  F n2 have a  eld-Diophantine de nition
 over R2. Then B  F kn1 has a  eld-Diophantine de nition over R1.
39
 Proof. Let f(z1; :::; zn; y; x1; :::; xr) be a  eld-Diophantine de nition of B over R2. In
 this case, we have that
 B = f(t1; :::; tn) 2 F
 n
 2 j 9z1; :::; zn; y; x1; :::; xr 2 R2;
 yt1 = z1; :::; ytn = zn; f(z1; :::; zn; y; x1; :::; xr) = 0g
 and f(z1; :::; zn; y; x1; :::; xr) = 0 implies y 6= 0. As y; zi 2 R2 and R2 DiophR1, we
 have that
 y =
 kX
 i=1
 ui
 v
 !i and zi =
 kX
 j=1
 ui;j
 vi
 !j
 where ui; ui;j; v 2 R1, and for some  a 2 Rl1 and  bi 2 R
 l
 1; i = 1; : : : ; n we have that
 g(u1; :::; uk; v; a1; :::; al) = 0 and g(ui;1; :::; ui;k; vi; bi;1; :::; bi;l) = 0
 with g(x1; : : : ; xk; y; z1; : : : ; zl) being the de ning polynomial of R2 over R1.
 Now let r 2 f1; :::; ng. By substitution, we have that
  
kX
 i=1
 ui
 v
 !i
 !
 tr =
 kX
 j=1
 ur;j
 vr
 !j:
 By Lemma 4.7, we have that
 tr =
  
kX
 j=1
 ur;j
 vr
 !j
 !0
 @
 kX
 i=1
 Pi
  u1
 v
 ; :::;
 uk
 v
  
Q
  u1
 v
 ; :::;
 uk
 v
  !i
 1
 A ;
 where Q
  u1
 v
 ; :::;
 uk
 v
  
6= 0, Pi
  u1
 v
 ; :::;
 uk
 v
  
, and Q
  u1
 v
 ; :::;
 uk
 v
  
depend only on  .
40
 Further, by Lemma 4.6, we have
 tr =
 kX
 i=1
 Bi
  
ur;1
 vr
 ; :::;
 ur;k
 vr
 ;
 P1
  
u1
 v ; :::;
 uk
 v
  
Q
  
u1
 v ; :::;
 uk
 v
  ; :::;
 Pk
  
u1
 v ; :::;
 uk
 v
  
Q
  
u1
 v ; :::;
 uk
 v
  
!
 !i;
 where Bi is a  xed polynomial depending only on  . Now we will proceed to clear
 out our denominators. Let
 D1;r =
 h
 vrQ
  u1
 v
 ; :::;
 un
 v
  id1
 where d1 is the maximum of the degrees of B1; :::; Bk. Then let
  Bi;r = D1;rBi =  Bi
  
ur;1; :::; ur;k; vr; P1
  u1
 v
 ; :::;
 uk
 v
  
; :::; Pk
  u1
 v
 ; :::;
 uk
 v
  
; Q
  u1
 v
 ; :::;
 uk
 v
   
:
 Let
 D2 = v
 d2
 where d2 is the maximum of the degrees of  B1; :::;  Bk. Then let
  Bi;r = D2  Bi;r =  Bi;r (ur;1; ::; ur;k; vr; u1; ::; uk; v) :
 Let Dr(u1; : : : ; un; v; vr) = D1;rD2 and note that it is a  xed polynomial depending on
 the basis and the maximum values of the indexes only and for values of the variable
 satisfying the equations above, it is non-zero. Now we have
 Drtr =
 kX
 i=1
  Bi;r(ur;1; :::; ur;k; vr; u1; :::; uk; v)!i:
41
 We now rewrite f(z1; :::; zn; y; x1; :::; xl) = 0. We can rewrite this equation as follows:
 f
  
kX
 j=1
 u1;j
 v1
 !j; :::;
 kX
 j=1
 un;j
 vn
 !j;
 kX
 j=1
 uj
 v
 !j;
 kX
 j=1
 x1;j
 X1
 !j; ::;
 kX
 j=1
 xl;j
 Xl
 !j
 !
 = 0;
 where each ui;j; vi; uj; v; xi;j; Xi 2 R1. Now as g is the de ning polynomial of R2 over
 R1, for some  a1; : : : ;  an 2 Rm1 , we have that
 8
 >>>>>><
 >>>>>>:
 g(u1;1; :::; u1;k; v1; a1;1; :::; a1;m) = 0
 ...
 g(un;1; :::; un;k; vn; an;1; :::; an;m) = 0
 ensures that
 Pk
 j=1
 ur;j
 vr
 !j 2 R2 for r 2 f1; :::; ng, and also implies vr 6= 0.
 Additionally, if for some b1;1; : : : ; bl;m; X1; : : : ; Xl 2 R1 we have
 8
 >>>>>><
 >>>>>>:
 g(x1;1; :::; x1;k; X1; b1;1; :::; b1;m) = 0
 ...
 g(xl;1; :::; xl;k; Xl; bl;1; :::; bl;m) = 0
 then
 Pk
 j=1
 xs;j
 Xs
 !j 2 R2 for s 2 f1; :::; lg, and also Xs 6= 0. Lastly, if for some
 a1; : : : ; am 2 R1 we have
 g(u1; :::; uk; v; a1; :::; am) = 0;
 then
 Pk
 j=1
 uj
 v !j 2 R2 and v 6= 0.
42
 Finally we work with coordinate polynomials to rewrite
 f(z1; :::; zn; y; x1; :::; xl) = 0
 for z1; :::; zn; y; x1; :::; xl 2 R2  F in terms of  = f!1; :::; !ng, which is a basis of F
 over F1 and also a Diophantine basis of R2 over R1. We have
 f(z1; :::; zn; y; x1; :::; xl) = 0
 m
 f
  
kX
 j=1
 u1;j
 v1
 !j; :::;
 kX
 j=1
 un;j
 vn
 !j;
 kX
 j=1
 uj
 v
 !j;
 kX
 j=1
 x1;j
 X1
 !j; ::;
 kX
 j=1
 xl;j
 Xl
 !j
 !
 = 0
 m
 kX
 j=1
 fj
  
 
u1;1
 v1
 ; :::;
 u1;k
 v1
 ; :::;
 un;1
 vn
 ; :::;
 un;k
 vn
 ;
 u1
 v
 ; :::;
 uk
 v
 ;
 x1;1
 X1
 ; ::;
 x1;k
 X1
 ; :::;
 xl;1
 Xl
 ; :::;
 xl;k
 Xl
  
!j = 0;
 where we have k polynomials from F that have ratios in R1 and depend only on  .
 Let E = max(deg(fj
  )) and in addition let C = (v1    vnvX1    Xl)
 E. Now let
  f j = Cf
  
j
  
u1;1
 v1
 ; :::;
 u1;k
 v1
 ; :::;
 un;1
 vn
 ; :::;
 un;k
 vn
 ;
 u1
 v
 ; :::;
 uk
 v
 ;
 x1;1
 X1
 ; ::;
 x1;k
 X1
 ; :::;
 xl;1
 Xl
 ; :::;
 xl;k
 Xl
  
=  f j (u1;1; :::; u1;k; :::; un;1; :::; un;k; u1; :::; uk; x1;1; ::; x1;k; :::; xl;1; :::; xl;k) :
 In this case, we have
 B = f(t1; :::; tn) 2 F
 n
 2 j 9 ar 2 R
 m
 1 ; u1;1; : : : ; un;k;
 u1; : : : ; uk; v1; : : : ; vn; v; x1;1; : : : ; xl;k; X1; : : : ; Xl 2 R1
43
 Drtr =
 kX
 i=1
  Bi;r(ur;1; :::; ur;k; vr; u1; :::; uk; v)!i; r = 1; :::; n;
 g(ur;1; :::; ur;k; vr;  ar) = 0; r = 1; :::; k;
  f j (u1;1; :::; un;k; v1; :::; vn; u1; :::; uk; v; x1;1; :::; xl;k; X1; :::; Xl) = 0; j = 1; :::; kg:
 Then we have
 B = f(w1;1; :::; wk;n) 2 F
 kn
 1 j 9 ar 2 R
 m
 1 ; u1;1; : : : ; un;k;
 u1; : : : ; uk; v1; : : : ; vn; v; x1;1; : : : ; xl;k; X1; : : : ; Xl 2 R1
 Drwi;r =  Bi(ur;1; :::; ur;k; vr; u1; :::; uk; v); r = 1; :::; k; i = 1; : : : ; n
 g(ur;1; :::; ur;k; vr;  ar) = 0; r = 1; :::; k;
  f j (u1;1; :::; un;k; v1; :::; vn; u1; :::; uk; v; x1;1; :::; xl;k; X1; :::; Xl) = 0; j = 1; :::; kg:
 Thus, B  F kn1 has a  eld-Diophantine de nition over R1.
 We now state without proof a property of Diophantine generation. The proof can
 be found in Lemma 2.1.11 of [8].
 Proposition 4.17. Let R1; R2 be integral domains with fraction  elds F1; F2 respec-
 tively and R2  Dioph R1. Let F be any  eld containing both F1 and F2 and of  nite
 degree over F1 (by de nition of Diophantine generation, at least one such  eld exists),
 and let  be any basis of F over F1. In this case, F is a de ning  eld and  is a
 de ning basis.
 In view of Proposition 4.17, we can make the following observation.
 Remark 4.18. IfR2  F1, andR2 is  eld-Diophantine overR1, then clearlyR2  Dioph
 R1 with basis consisting of f1g. Also of R2  Dioph R1, then we can choose a power
44
 basis as a Diophantine basis for the de ning  eld over F1. Since R2 is a subset of F1,
 this is equivalent to using a basis consisting of f1g and the de ning polynomial for
 Diophantine generation becomes a  eld-Diophantine de nition.
 We now connect Diophantine generation to Hilbert’s Tenth Problem.
 Proposition 4.19. If R1 and R2 are recursive rings with R1  Dioph R2 and HTP is
 not solvable over R1, then it is not solvable over R2.
 Proof. If R1  Dioph R2, then given a polynomial equation over R1, we can algorith-
 mically construct a system of polynomial equations over R2 such that the system has
 solutions in R2 if and only if the original polynomial equation had solutions in R1.
 In view of the Corollary 4.2, we conclude that if there is no algorithm to tell whether
 a polynomial equation over R1 has solutions in R1, then there is no such algorithm
 over R2.
 Now we will prove transitivity of Dioph-generation.
 Theorem 4.20. Let R1, R2, and R3 be integral domains with quotient  elds F1, F2,
 and F3 respectively. Assume that F1, F2, and F3 are all sub elds of a  eld F, which
 is not algebraically closed. Further assume that all the extensions F=Fi for i = 1; 2; 3
 are  nite. Lastly assume that R2  Dioph R1 and R3  Dioph R2. In this case, we have
 R3  Dioph R1.
 Proof. Let F be the de ning  eld for both (R1; R2) and (R2; R3). We can make such
 a choice by Proposition 4.17. Let  = f!1; :::; !kg be a Diophantine basis for R2 over
 R1 such that F is the corresponding de ning  eld. Further, let  = f 1; :::;  ng be a
 Diophantine basis for R3 over R2 such that F is the corresponding de ning  eld as
45
 well. By Lemma 4.13, we can write
 R3 =
 (
 nX
 i=1
 zi ij(z1; :::; zn) 2 A  F
 n
 2
 )
 ;
 where A has a  eld-Diophantine de nition over R2. Further, by Proposition 4.16,
 A  has a  eld-Diophantine de nition over R1. Thus, we obtain
 R3 =
 (
 nX
 i=1
 zi ij(z1; :::; zn) 2 A  F
 n
 2
 )
 =
 (
 nX
 i=1
 kX
 j=1
 yi;j!j ij(y1;1; :::; yn;k) 2 A
  
  F
 nk
 1
 )
 =
 (
 nX
 i=1
 kX
 j=1
 yi;j i!jj(y1;1; :::; yn;k) 2 A
  
  F
 nk
 1
 )
 =
 (
 kX
 s=1
 kX
 j=1
 nX
 i=1
 (yi;jAi;j;s)!sj(y1;1; :::; yn;k) 2 A
  
 
)
 ;
 where
 zi =
 kX
 j=1
 yi;j!j,
 kX
 s=1
 Ai;j;s!s =  i!j, Ai;j;s 2 F1:
 Let
 B =
 (
 (t1; :::; tk) 2 F
 k
 1 jts =
 kX
 j=1
 nX
 i=1
 (yi;jAi;j;s) ; (y1;1; :::; yn;k) 2 A
  
 
)
 :
 By Lemma 4.10, we know that B has a  eld-Diophantine de nition over R1 and
 since we have
 R3 =
 (
 kX
 s=1
 ts!sj(t1; :::; tk) 2 B 
)
 ;
 by Lemma 4.13, R3  Dioph R1.
 We will now state and prove the  nite intersection property.
 Theorem 4.21. Let Ri  R for i = 1; :::;m be rings such that the quotient  eld of
46
 R is not algebraically closed and for all i = 1; :::;m we have that Ri  Dioph R. Then
 \mi=1Ri  Dioph R.
 Proof. We have that Ri has a Diophantine de nition fi(t; x1; :::; xni) over R since Ri  
R and Ri  Dioph R. Thus, for all x 2 R we have that there exist x1;1; :::; xm;nm 2 R
 with fi(x; xi;1; :::; xi;ni) = 0 for i = 1; :::;m if and only if x 2 \
 m
 i=1Ri.
 4.4 Rings of Integers of Number Fields
 First, we need to de ne the rings of integers of number  elds and discuss some of
 their properties.
 De nition 4.22 (Number Fields and Rings of Integers). If K is a  nite extension of
 Q, then K is called a number  eld. If x 2 K satis es a monic irreducible polynomial
 over Z, then x is called an algebraic integer.
 The following propositions are standard results from Number Theory. See [3] for
 more details.
 Proposition 4.23 (Properties of Integers of Number Fields).
  The set of all integers of a number  eld K is a ring. In the future we will denote
 this ring by OK.
  For any number  eld K there exists a basis  of K over Q such that OK =
 fx 2 Kjx =
 P
 ai!i; ai 2 Zg. (Such a basis is called an integral basis of K over
 Q.)
 In this section, we will use the following theorem due to Mazur, Poonen, and
 Rubin which could be stated as follows:
 Theorem 4.24. If F=K is a cyclic extension of prime degree p and if the Shafarevich-
 Tate conjecture is true for K, then OK  Dioph OF where OK and OF are the rings of
 integers over the number  elds K and F respectively.
47
 Our main goal to show Z  Dioph OE for any number  eld E, assuming a certain
 number-theoretic conjecture is true, can now be achieved. We will do this through a
 series of reductions. We will  rst show that if
 (1) for any cyclic extension F=K of a number  eld of prime degree p, we
 have that OK  Dioph OF ,
 then it follows that Z  Dioph OE, for any number  eld E. Then
 (2) we will apply Mazur, Rubin, and Poonen’s results to conclude if the
 Shafarevich-Tate conjecture holds then the previous statement holds.
 Before we proceed, we need to discuss more properties of the rings of integers of
 number  elds. As an immediate corollary to Proposition 4.23 we have the following
 fact.
 Corollary 4.25. For any number  eld K, we have OK  Dioph Z.
 One can also show the following proposition is true. (The proof can be found in
 Chapter 2 of [8].)
 Proposition 4.26. If M=K is a  nite extension of number  elds, then OM  Dioph
 OK.
 Proposition 4.27. Let L=M be a cyclic extension and assume statement (1) holds.
 In this case, we have OM  Dioph OL.
 Proof. We will do this by induction on [L : M ] = n. For the case, n = 1 is trivial
 because everything is  Dioph than itself. Assume for any cyclic extension of degree
 k < n the proposition holds. We will show it holds for n. Let  be a generator of
48
 G(L=M). Since n > 1, there exists a prime p dividing n. Let  =  
n
 p and note
 ord( ) = p. Let H = L< >. Then we have the following M  H  L, [H : M ] = np <
 n, and [L : H] = p. Further by Corollary 3.33, all the extensions are cyclic. Thus,
 OH  Dioph OL by (1). By the induction hypothesis, we have OM  Dioph OH . Lastly,
 by transitivity of Dioph-generations, we have OM  Dioph OL.
 Proposition 4.28. Let L=M be Galois and assume (1) holds, then OM  Dioph OL.
 Proof. Let f 1; :::;  ng = G(L=M). For each i 2 f1; :::; ng consider L< > and note
 that
 1. L=L< i> is cyclic and
 2.
 Tn
 i=1 L< i> = M .
 By Proposition 4.27, we have OL< i>  Dioph OL. By the intersection property of
 Dioph-generations, we have OM =
 Tn
 i=1 OL< i>  Dioph OL.
 Proposition 4.29. If (1) holds and L=M is any  nite extension of number  elds of
 degree n, then OL  Dioph OM .
 Proof. Let MG be any  eld Galois over OL and containing M . (In particular, if
 M = L( ), MG can be M( =  1; :::;  n) where  1; : : : ;  n are are all conjugates
 of  over L.) By Proposition 4.26, we have OMG  Dioph OM . By the previous
 proposition, we have OL  Dioph OMG . Lastly, by transitivity of Dioph-generations,
 we have OL  Dioph OM .
 We now state the main theorem of this section.
 Theorem 4.30. If the Shafarevich-Tate conjecture on elliptic curves is true, then
 Z  Dioph OK for any number  eld K, and thus Hilbert’s Tenth Problem is not decid-
 able over the ring of integers of any number  eld K.
49
 Proof. From a result of Poonen (see [6]) and a result of Mazur and Rubin (see [5]),
 it follows that assuming the Shafarevich-Tate conjecture for elliptic curves, for any
 prime degree cyclic extension of number  elds M=K we have OK  Dioph OM . Thus
 by Proposition 4.29, we have that Z  Dioph OK for any number  eld K.
REFERENCES
 [1] Fraleigh, J. B. (2003). A  rst course in abstract algebra. Addison-Wesley Pub-
 lishing Co., Reading, Mass.-London-Don Mills, Ont.
 [2] Herstein, I. N. (1996). Abstract algebra. Prentice Hall Inc., Upper Saddle River,
 NJ, third edition. With a preface by Barbara Cortzen and David J. Winter.
 [3] Janusz, G. J. (1996). Algebraic number  elds, volume 7 of Graduate Studies in
 Mathematics. American Mathematical Society, Providence, RI, second edition.
 [4] Matiyasevich, Y. V. (1993). Hilbert’s tenth problem. Foundations of Computing
 Series. MIT Press, Cambridge, MA. Translated from the 1993 Russian original by
 the author, With a foreword by Martin Davis.
 [5] Mazur, B. and Rubin, K. (2010). Ranks of twists of elliptic curves and Hilbert’s
 tenth problem. Invent. Math., 181(3):541{575.
 [6] Poonen, B. (2002). Using elliptic curves of rank one towards the undecidability
 of Hilbert’s tenth problem over rings of algebraic integers. In Algorithmic number
 theory (Sydney, 2002), volume 2369 of Lecture Notes in Comput. Sci., pages 33{42.
 Springer, Berlin.
 [7] Rogers, Jr., H. (1987). Theory of recursive functions and e ective computability.
 MIT Press, Cambridge, MA, second edition.
 [8] Shlapentokh, A. (2007). Hilbert’s tenth problem, volume 7 of New Mathematical
 Monographs. Cambridge University Press, Cambridge. Diophantine classes and
 extensions to global  elds.