Back to title page.
Left |
Adjust your browser window |
Right |
We will investigate only a special (the simplest!) case of Fermat's equation - where D=a2-1 for some natural number a>1:
x2 - (a2-1)y2 = 1.
No problems to prove the existence of non-trivial solutions for this equation: you can simply take x=a, y=1. After this, all the other natural solutions we can calculate by using the following smart idea. Let us note that
x2 - (a2-1)y2 = (x+y*sqrt(a2-1)) * (x-y*sqrt(a2-1)) = 1.
Take our first non-trivial solution x=a, y=1:
a2 - (a2-1) = (a+sqrt(a2-1)) * (a-sqrt(a2-1)) = 1.
Consider the n-th power:
(a+sqrt(a2-1))n * (a-sqrt(a2-1)) n = 1.
Now let us apply the Newton's binomial formula to the expression (a+sqrt(a2-1))n. For example, if n=2, then �
(a+sqrt(a2-1)) 2 = a2 + 2a*sqrt(a2-1) + (a2-1).
I.e. some of the items contain sqrt(a2-1), and some do not. Let us sum up either kind of the items:
(a+sqrt(a2-1)) n = xn(a) + yn (a)sqrt(a2-1), -----------(1)
where xn (a), yn (a) are natural numbers. For example, x2(a)=2a2-1, y2 (a)=2a. Still, in this way we can obtain also
(a-sqrt(a2-1)) n = xn (a) - yn (a)sqrt(a2-1) ----------(2)
with the same xn (a) and yn (a) (verify!). Now multiply (1) by (2):
(a2-a2+1) n = xn2 - (a2-1)yn2,
x n2 - (a2-1)y n2 =1.
Hence, for any number n>=0 the pair �
x = xn(a),
y = yn (a)
is a solution of the equation x2-(a2-1)y2=1. The values n=0, 1 yield the solutions that we already know: x=1, y=0, and x=1, y=1. Still, n=2 yields a new solution; x=2a2-1, y=2a.
From our definition of the numbers xn (a), yn (a) the following recurrent identities can be derived (m, n>=0):
xm+n(a) = xm(a)*xn(a) + ym(a)*yn(a)*(a2-1),
ym+n(a) = xm(a)*yn(a) + ym(a)*xn(a).
For m=1 this means:
xn+1(a) = a*xn(a) + (a2-1)*yn(a),
yn+1 (a) = xn(a) + a*ym(a).
Exercise 4.8. Prove these identities. Verify also that xn (a) and yn (a) are increasing functions of n (i.e. that they really yield an infinite set of solutions of the equation x2-(a2-1)y2=1).
It appears that the sequence {(xn(a), yn(a) | n>=0} covers all natural solutions of Fermat's equation.
Lemma 1. If a>1, then
x2-(a2-1)y2=1 <-> En(x=xn(a) & y=yn(a)).
Proof. 1) Leftwards. This we already have proved.
2) Rightwards. Let x, y be a solution of our equation. If x<=1, then x=1 and y=0, i.e. x=x0(a), y=y0(a). Now let x>1. Then y>0. If x, y would be xn (a), yn (a), and u, v would be xn-1(a), yn-1(a), then we would have:
x = au+(a2-1)v, -----------(3)
y = u+av.
Let us express u, v from these equations:
u = ax-(a2-1)y, -----------(3a)
v = -x+ay.
Now forget about xn, yn, xn-1, yn-1: the numbers u, v are simply calculated from x, y by formulas (3a).
Exercise 4.9. Verify that u2-(a2-1)v2=1, i.e. that (u, v) is a solution. Verify also that 0<u<x and v>=0.
Thus, if (x, y) is a solution of our equation, x>1, then these numbers can be expressed by formulas (3) through another solution (u, v) such that u<x. If u>1, again, we can express (u, v) through another solution (u', v') such that u'<u, etc. until we reach the solution (1, 0). If n is the number of these downward steps, then x=xn(a) and y=yn(a). Q.E.D.
Thus we have an elegant (more than 300 years old) algorithm allowing to calculate the sequence of all natural solutions of the equation x2-(a2-1)y2=1. What makes this algorithm important in the context of Hilbert's 10th problem?
Lemma 2. If a>1 and n>=0, then
an <= xn (a) <= (a+sqrt(a2-1)) n.
Proof.
xn(a)+yn(a)*sqrt(a2-1) = (a+sqrt(a2-1))n,
xn(a) =a* xn-1(a)+(a2-1)yn(a) >= a* xn-1(a).
Q.E.D.
Hence, as function of n, xn(a) is growing exponentially. And this is achieved by a Diophantine condition F on x:
F(x) <-> Ey(x2-(a2-1)y2=1).
Not bad as the first step - if we wish to find, among others, a polynomial P(x, z1, ..., zm) such that
Ey(x=2y) <-> Ez1...Ezm P(x, z1, ..., zm).
(These considerations were proposed by J.Robinson in her 1952 paper.)
Now let us follow the idea due to Matiyasevich: let us investigate the remainders from dividing the numbers xn(a), yn(a) by each other.
First, let n be fixed, n>0, and let us observe the remainders from dividing xN(a) and yN(a) by xn(a) as N = 0, 1, 2, .... For this purpose we will consider mod xn(a) the above recurrent identities for xm+n, ym+n. I.e. we will ignore items divisible by xn (a):
xm+n(a) = xm(a)*xn(a) + ym(a)*yn(a)*(a2-1) = ymyn*(a2-1) mod xn,
ym+n(a) = xm(a)*yn(a) + ym(a)*xn(a) = xmyn mod xn.
Substitute m+n for m:
xm+2n = (a2-1)ym+nyn = (a2-1)xmyn2 mod xn,
ym+2n = xm+nyn = (a2-1)ymyn2 mod xn.
Now let us note that xn2-(a2-1)yn2=1, hence (a2-1)y n2 = x n2-1 = -1 mod x n. Thus, we can replace (a2-1)y n2 by -1:
xm+2n = -xm mod xn, -----------(4)
ym+2n = -ym mod xn.
Substitute m+2n for m:
xm+4n = -xm+2n = xm mod xn,
ym+4n = -ym+2n = ym mod xn.
Thus, the remainders of xN(a) and yN(a) mod xn(a) are changing by the period 4n, and we can concentrate on investigating these remainders for N = 0, 1, 2, ..., 4n-1.
According to (4) we have (mod xn):
x0 = x0, x1 = x1, ..., x2n-1 = x2n-1,
x2n = - x0, x2n+1 = - x1, ..., x4n-1 = - x2n-1,
y0 = y0, y1 = y1, ..., y2n-1 = y2n-1,
y2n = - y0, y2n+1 = - y1, ..., y4n-1 = - y2n-1.
Since the numbers xn+1, ..., x2n-1 exceed the divisor xn, our analysis is not yet complete. To complete it, let us consider the recurrent identities expressing x2n, y2n through x2n-m, y2n-m and xm, ym:
x2n = x2n-mxm + (a2-1)y2n-mym,
y2n = x2n-m ym + y2n-m xm.
Let us express x2n-m, y2n-m from these equations:
x2n-m = x2n xm - (a2-1)y2n ym,
y2n-m = y2n xm - x2n ym.
By mod xn: x2n = -x0 = -1 and y2n = -y0 = 0, thus we obtain:
x2n-m = -xm mod xn,
y2n-m = ym mod xn.
Now we can complete our analysis by mod xn:
x0 = x0, x1 = x1, ..., xn-1 = xn-1,
xn = - xn, xn+1 = - xn-1, ..., x2n-1 = - x1,
x2n = - x0, x2n+1 = - x1, ..., x3n-1 = - xn-1,
x3n = x n, x3n+1 = x n-1, ..., x 4n-1= x1,
y0 = y0, y1 = y1, ..., yn-1 = yn-1,
yn = yn, yn+1 = yn-1, ..., y2n-1 = y1,
y2n = - y0, y2n+1 = - y1, ..., y3n-1 = - yn-1.
y3n = - yn, y3n+1 = - yn-1, ..., y4n-1 = - y1.
This result allows proving of the following lemma (due to Matiyasevich):
Lemma 3. Let a>=3, n>=1, 0<m<n. Then for all N:
xN(a) = xm(a) mod xn(a) <-> (N=+m mod 4n) v (N=-m mod 4n).
Note. Thanks to Milos Puzovic, who discovered an error in the previous version of this text.
Proof. 1) Leftwards. If N=4kn+m or N=4kn-m, then xN=xm mod xn follows from the results of the above analysis.
2) Rightwards. Let xN=xm mod xn, where 0<m<n. Let us divide N by 4n: N=4kn+m', where 0<=m'<4n.
If m'<n, then (according to the results of the above analysis) m'=m, and N=4kn+m - Q.E.D.
If 3n<m', then (according to the results of the above analysis) m'=4n-m, and N=4(k+1)n-m - Q.E.D.
If m'=0, m'=n, m'=2n, or m'=3n, then (according to the results of the above analysis) m=0 or m=n. This is impossible.
Exercise 4.10. Verify that the remaining alternatives n<m'<2n, 2n<m'<3n also are impossible. (Hint: see the results of the above analysis, and note that if a>2 and i<n, then xi(a) < xn(a)/2.)
End of proof.
Now we must perform a similar investigation of remainders from dividing yN(a) by yn(a) (n is fixed, n>=1, N = 0, 1, 2, ...).
Exercise 4.11. Perform this investigation yourself. You will obtain that yN(a) mod yn(a) is changing with the period 2n, and (mod yn):
y0 = y0, y1 = y1, ..., yn-1 = yn-1,
yn = - yn, yn+1 = - yn-1, ..., y2n-1 = - y1.
From this result we can derive another lemma (due to Matiyasevich):
Lemma 4. Let a>=2, n>=1. Then yN(a) is divisible by yn(a), iff N is divisible by n.
Proof. Immediately from the results of Exercise 4.11.
The following very important (see below) lemma also is due to Matiyasevich:
Lemma 5. Let a>=2, n>=1. Then yN(a) is divisible by yn2(a), iff N is divisible by n*yn(a).
Proof. You can easily verify (induction by k) that:
xkn = xnk mod yn2,
ykn = kxnk-1yn mod yn2.
1) Rightwards. If yN (a) is divisible by yn2(a), then by lemma 4: N=kn. If ykn is divisible by yn2, then kxnk-1yn also is divisible by yn2, i.e. kxnk-1 is divisible by yn. Since xn2-(a2-1)yn2=1, the number xn cannot have common divisors with yn, hence, k is divisible by yn. And since N=kn, N is divisible by nyn.
2) Leftwards. If N is divisible by nyn, then N=kn, where k is divisible by yn. Hence, kxnk-1yn is divisible by yn2, i.e. yN=ykn also is divisible by yn2.
Q.E.D.
We will need also the following three lemmas (Lemma 6 is from the 1952 paper by J.Robinson):
Lemma 6. Let a>=2, n>=1. Then:
xn (a) = 1 mod(a-1),
yn (a) = n mod(a-1).
Lemma 7. Let a, a' >=2, b>==1. Then, if a=a' mod b, then for all n:
xn(a) = xn(a') mod b,
yn(a) = yn(a') mod b.
Lemma 8. Let a>=2, k>=0. Then:
x2k(a) = 1 mod 2, x2k+1(a) = a mod 2,
y2k (a) = 0 mod 2, x2k+1(a) = 1 mod 2.
Exercise 4.12. Prove these lemmas by induction.
Now, following Matiyasevich, we must build a Diophantine representation of the predicate
F(a, x, y, n) <-> a>=3 & x=xn(a) & y = yn(a).
I.e. we must put on x, y some "Diophantine conditions" forcing x equal to xn(a), and y - equal to yn(a). Of course, we will begin with the condition
F1: x2-(a2-1)y2=1.
Hence, there is m such that x=xm(a) and y = ym(a), and we must force m equal to n.
By Lemma 6, ym (a) = m mod(a-1), hence, we could try putting the second condition y=n mod(a-1), then we would have m=n mod(a-1). Unfortunately, if n>=a-1, then we will not be able to conclude that m=n.
To avoid this difficulty, a turning movement (literally!) is necessary. Let us introduce another Fermat's equation with a free parameter A:
F2: X2-(A2-1)Y2=1.
And now we will require not y=n mod(a-1), but
F3: Y = n mod(A-1).
(Since A is free, we may hope to ensure n<A-1). Since, for some M, X=xM(A) and Y=yM(A), then by Lemma 6, Y=M mod(A-1), hence,
M = n mod(A-1). -----------(1)
This conclusion will be useful only, if we will be able to connect the new numbers (X, Y) with our initial numbers (x, y). So, let us introduce an additional module U, and let us require
F4: A = a mod U & X = x mod U.
By Lemma 7, A = a mod U implies
x = xm(a) = xm(A) mod U,
X = xM(A) = xM(a) mod U.
From F4 we have X = x mod U, hence
xM(a) = xm(a) mod U. ----------(2)
We could apply here Lemma 3, yet then U must be a solution of Fermat's equation with the same parameter a. So, let us introduce another number V, and let us require
F5: U2-(a2-1)V2=1.
Hence, for some N: U=xN(a) and V=yN(a), and we can rewrite (2) as
xM(a) = xm(a) mod xN(a).
To apply Lemma 3, we must ensure that 0<m<N. This can be achieved by putting the condition
F6: 0<x<U
(since xi(a) is increasing by i, 0<xm(a)=x<U=xN(a) means 0<m<N). Finally, we can apply Lemma 3:
(M = m mod 4N) v (M = -m mod 4N). ----------(3)
Now we are at the end of our turning movement. Let us compare (3) with (1):
M = n mod(A-1).
Our intention was to force m=n. We would have achieved this, if 4N would exceed M and m (then (3) would yield M=m or M=-m), and if A-1 would exceed M and n (this would yield M=n, i.e. m=n). The way to ensure both "exceed-s" would be to force a large common divisor of A-1 and 4N. Still, we do not know the number N, how could we find a large divisor of 4N? On the other hand, we have Lemma 5: yN(a) is divisible by ym2(a), iff N is divisible by mym(a). Or simply, V is divisible by y2, iff N is divisible by my. Hence, if we will put the condition
F7: V is divisible by y2,
then 4y will be a divisor of 4N (we omit m as an unknown number that we could not force to divide A-1). Now we must put the condition
F8: A-1 is divisible by 4y
to force 4y to be a common divisor of 4N and A-1. After this, (1) and (3) yield:
(M = n mod 4y) & ((M = m mod 4y) v (M = -m mod 4y)).
Hence,
(n = m mod 4y) v (n = -m mod 4y).
Since y=ym(a) is increasing by m, we have y>=m. On the other hand, we may put the condition
F9: n<=y.
Finally, we must consider two possibilities:
1) n = m mod 4y, i.e. n-m is divisible by 4y. Since |n-m|<=y, this is possible, iff n=m. Q.E.D.
2) n = -m mod 4y, i.e. n+m is divisible by 4y. Since n+m<=2y, this is possible, iff n=m=0. Q.E.D.
Thus we have established that the condition
a>=3 & EAEXEYEUEV(F1 & F2 & F3 & F4 & F5 & F6 & F7 & F8 & F9) ----------(4)
implies that x=xn(a) and y=yn(a), i.e. F(a, x, y, n).
Our task will be completed, if we will show that F(a, x, y, n) also implies (4). So, having a>=3 & x=xn(a) & y=yn(a), we must find the numbers A, X, Y, U, V such that Fi are satisfied for all i=1, 2, ..., 9.
F1: x2-(a2-1)y2=1 is satisfied by Lemma 1.
F9: n<=y is satisfied, since yn(a) is increasing by n.
The numbers U, V (a solution of the same equation as x, y) we can choose in the following way: let N be the least even (see below!) multiple of ny, such that xN(a)>=x (see F6!), and let U=xN(a), V=yN(a). Then:
F6: x<=U is satisfied.
F5: U2-(a2-1)V2=1 is satisfied.
And by Lemma 5, V is divisible by y2, i.e. F7 is satisfied.
It remains to determine the parameter A of our auxiliary equation and its solution X, Y. The following conditions must be satisfied:
F2: X2-(A2-1)Y2=1,
F3: Y = n mod(A-1),
F4: A = a mod U & X = x mod U,
F8: A-1 is divisible by 4y.
1) Case n=0. Then x=1, y=0. F4 is satisfied, since U=1. F8 will be satisfied, iff we take A=1. After this, F2 will be satisfied, iff we take X=1, and F3 - iff we take Y=0. Q.E.D.
2) Case n>0. Then y>0. As the first step, let us use F4 and F8 to choose A. If the numbers U and 4y would have no common divisors, then we could obtain A from Chinese remainder theorem (see Section 3.3) - as a number A>1 that satisfies simultaneously A = a mod U and A = 1 mod 4y. Then F8 and the first part of F4 would be satisfied.
So, let us prove that U and 4y have no common divisors. On the one hand, U is an odd number (by Lemma 8, since N is even number, see above). On the other hand, V is divisible by y2, and U2-(a2-1)V2=1, hence, U and y have no common divisors.
It remains to choose X, Y. Let us choose X=xn(A) and Y=yn(A). Then F2 is satisfied. By Lemma 6, F3 also is satisfied. And finally, since x=xn(a) and A = a mod U, by Lemma 7 we obtain xn(A) = xn(a) mod U, and X = x mod U, i.e. the second part of F4 also is satisfied. Q.E.D.
Thus, we have established the equivalence of F(a, x, y, n) and (4).
Exercise 4.13. Transform (4) into a Diophantine representation E(P=0). Determine the number of quantifiers E, the degree and the sum of coefficient modules of the polynomial P.
��
Now we will use the Diophantine representation of "Fermat's" predicate F(a, x, y, n) from the previous section to obtain a Diophantine representation of the exponential function, i.e. of the predicate
E(u, v, n) <-> u=vn & v>=3
(assuming that 00=1).
Let us start with our fundamental equality
(a+sqrt(a2-1))n = xn(a) + yn(a)*sqrt(a2-1).
Let us denote v = a+sqrt(a2-1). Then we will have simply vn on the left hand side. On the right hand side we can replace sqrt(a2-1) by v-a:
vn-xn(a)-yn(a)(v-a)=0.
Hence, this equation has the solution v1=a+sqrt(a2-1). Since all the coefficients of it are rational numbers, the number v2=a-sqrt(a2-1) also is its solution. On the other hand, v1, v2 are solutions of the equation
v2-2av+1=0.
Hence, the polynomial vn-xn(a)-yn(a)(v-a) is divisible by v2-2av+1 in the field of rational numbers. Moreover, the coefficients of this fraction polynomial are integer numbers (because the leading coefficient of the divisor is 1). Thus, if v is integer, then the number vn-xn(a)-yn(a)(v-a) is divisible by the number v2-2av+1. This is the main lemma from the 1952 paper by Julia Robinson:
Lemma 9. If a>=1 and n>=0, then
vn = xn(a)+yn (a)(v-a) mod(v2-2av+1).
Exercise 4.14. a) Verify Lemma 9 for n=0 and n=1 (the above argument is working only for n>=2).
b) Verify that
vn-xn(a)-yn(a)(v-a) = (v2-2av+1) (y1vn-2+y2vn-3+...+yn-2v+yn-1).
(This will be a direct proof of Lemma 9 - without the above "smart" algebraic considerations.)
Lemma 9 allows to connect the power vn with the numbers xn(a), yn(a) by using polynomials of restricted degree (v-a and v2-2av+1). Having this result, we can easily obtain a Diophantine representation of u=vn.
Indeed, having the variables u, v, n, we must put some Diophantine conditions that will force u=vn. As the first step, let us take some numbers a, x, y, n under the condition
E1: F(a, x, y, n).
Then x=xn(a) and y=yn(a), and by Lemma 9:
vn = x+y(v-a) mod(v2-2av+1).
In order to "bind" u and vn, let us put the condition
E2: u = x+y(v-a) mod(v2-2av+1).
Then
u = vn mod(v2-2av+1). --------(1)
We could derive u=vn from this congruence, if the module v2-2av+1 would be greater than both u and vn. This can be achieved by increasing the free parameter a - then |v2-2av+1| will grow as 2av-v2-1. Thus the condition
E3: u < 2av-v2-1
ensures one half of the necessary. Still, how to ensure vn<2av-v2-1 - by using Diophantine conditions? I.e. we must force the parameter a to grow exponentially by n. We know already from Lemma 2, that xn(v) is growing exponentially by n: xn(v)>=vn. Hence, we can try to force xn(v)<2av-v2-1 instead of vn<2av-v2-1. So, let us introduce the numbers X, Y such that
E4: F(v, X, Y, n),
i.e. X=xn(v) and Y=yn(v). If we add also
E5: X < 2av-v2-1,
then vn <= xn(v) = X < 2av-v2-1. Having this result plus E3 and (1) we obtain u=vn.
Thus, we have succeeded in deriving u=vn from the condition
EaExEyEXEY(E1 & E2 & E3 & E4 & E5). --------(2)
Since, v>=3 is included in E4, we have derived also E(u, v, n) from (2).
Exercise 4.15. a) To complete the proof, derive (2) from E(u, v, n).
b) Transform (2) into a Diophantine representation E(P=0). Determine the number of quantifiers E, the degree and the sum of coefficient modules of the polynomial P.
Thus, following the work by Matiyasevich and Julia Robinson, we have obtained for the predicate u=vn & v>=3 a Diophantine representation
Ez1...Ezk P(u, v, n, z1, ..., zk)=0.
If we substitute v=3 and add the quantifier En, we obtain a Diophantine representation
Ev1...Evs P1 (u, v1, ..., vs)=0
of the predicate "u is power of 3". Hence, the equation P1 (u, v1, ..., vs)=0 has natural solutions, iff the parameter u is 3n. This result was qualified as unexpected by some (anonymous?) number-theorists.
Cyz denotes the coefficient at pz in the Newton's binomial formula for (1+p)y.
The factorial function y! is defined as follows: 0!=0, and if y>0, then y!=1*2*...*y.
Julia Robinson showed in 1952 how the predicates z<=y & x= Cyz and x=y! can be "Diophantine expressed" through the predicate x=yz. Now, using these methods, we can obtain Diophantine representations of these predicates.
Matiyasevich improved the first method in the following way. Let us start with the Newton's binomial formula for (1+p) y:
(1+p)y = sum { Cyz pz | for z=0 to y}. --------(1)
For p=1 we would have
2y = sum { Cyz | for z=0 to y}.
Thus, Cyz <=2y for all z<=y.
From (1) we can obtain also:
(1+p)y = u + (Cyz + vp)pz,
where
u = sum {Cyi pi | for i=0 to z-1},
v = sum {Cyipi-z-1 | for i=z+1 to y}.
If we had u<pz, then we could compute u as (1+p)y mod pz. And if we had also Cyz <p, then we could compute Cyz as ((1+p)y-u)/pz mod p, i.e. we had reduced computing of Cyz to computing of the exponential function.
Of course, if p would be large enough (for example, p=3y+1), then Cyz <p would be ensured. Still, how about u<pz? Fortunately, for such a large p:
u<= sum {2ypi | for i=0 to z-1} = 2ysum {pi | for i=0 to z-1} = 2y(pz-1)/(p-1) = (2/3)y(pz-1) < pz.
Hence, if we wish to force x= Cyz & z<=y by putting Diophantine conditions, we may try to put
z<=y & EpEuEv (p=3y+1 & (1+p)y = u + (x + vp)pz & x<p & u<pz). --------(2)
We have already established, x= Cyz & z<=y implies (2). The converse also is true. Indeed, according to (2), we can compute the value of u as (1+p)y mod pz, and the value of x - as ((1+p)y-u)/pz mod p. This is the way Cyz is computed (see above), hence x= Cyz.
Exercise 4.16. Transform (2) into a Diophantine representation E(P=0). Determine the number of quantifiers E, the degree and the sum of coefficient modules of the polynomial P.
Now let follow another idea due to Julia Robinson to obtain a Diophantine representation of the predicate x=y!. As you may know:
Cwy = w(w-1)...(w-y+1)/y!.
If w would be much greater than y, then the product w(w-1)...(w-y+1) would be "approximately" wy, and hence, y! would be "approximately" wy/Cwy. Let us examine this fraction more closely:
wy/Cwy = y! (w/w) (w/(w-1)) ... (w/(w-y+1)).
Let us replace w, w-1, ..., w-y+1 by w-y, then we will have:
y! <= wy/Cwy <= y!(w/(w-y)) y = y!(1+y/(w-y)) y.
Now, take w=y+yt:
y! <= wy/Cwy <= y!(1+1/t) y = y!(1+sum{ Cyi t -i | for i=1 to y}).
Since Cyi <= 2y, let us take t=u2y, then
y! <= wy/Cwy <= y!(1+y/u).
And finally, by taking u=2yyy we will have (since y!<=yy):
y! <= wy/Cwy <= y!+1/2.
Hence, if w=y+2y22yyy, then y! can be computed as the integer part of the fraction wy/Cwy, and we can represent the predicate x=y! as
Ew(w=y+2y22yyy & x=integer(wy/Cwy)). --------(3)
Exercise 4.17. Transform (3) into a Diophantine representation E(P=0). Determine the number of quantifiers E, the degree and the sum of coefficient modules of the polynomial P.
Exercise 4.18. Build a Diophantine representation of the predicate "x is prime number". Hint (J.Robinson, 1952): x is prime, iff x and (x-1)! do not have common divisors. You can use also Wilson's theorem: x is prime number <-> x>1 & (x-1)!+1 is divisible by x. Which way is better?
Putnam's idea (Exercise 4.3) allows to obtain from this representation a polynomial Q(x1, ..., xn) such that the set of positive values of Q is exactly the set of all prime numbers. Hence, despite the current number-theoretic intuition of 1969 some kind of a "formula for prime numbers" does exist!
Now we have arrived at our target - producing a method that will allow converting any formula
(Az<U)Ex1...Exn P(b1, ..., bk, z, x1, ..., xn)=0, --------(1)
where U is a linear function of b1, ..., bk with natural coefficients, into an equivalent formula
Ey1...Eyq Q(b1, ..., bk, y1, ..., yq)=0.
We will follow mainly the 1961 paper by Davis, Putnam and Julia Robinson with some later improvements proposed by Matiyasevich and Julia Robinson.
For any fixed values of b1, ..., bk the formula (1) is an existential assertion (despite the universal quantifier Az<U) - it asserts the existence of U*n numbers: the values of x1, ..., xn for each z = 0, 1, ..., U-1. Let us denote these U*n numbers by xi(z):
for z=0: x1(0), x2(0),..., xn(0),
for z=1: x1(1), x2(1),..., xn(1),
...
for z=U-1: x1(U-1), x2(U-1),..., xn(U-1).
We could eliminate the universal quantifier Az<U, if we could find some coding that allowed to represent this table by a sequence of m natural numbers y1, ..., ym (where m does not depend on U). Then we could try to replace Az<U by Ey1...Eym (plus solving, of course, all the other remaining technical problems).
For example, let us try to code each of the n columns of our table by a single number using the Chinese Remainder theorem. If we had numbers u0, u1, ..., uU-1 such that two of them never had common divisors, then we could obtain n numbers w1, ..., wn such that each xi(z) would be wi mod uz, i.e.
xi(z)<uz & wi = xi(z) mod uz --------(2)
for all z<U and i = 1, ..., n. Of course, the numbers uz must be large enough to serve this purpose.
Still, even if we will succeed in finding u0, u1, ..., uU-1, then how to force the remainders x1(z), ..., xn(z) to satisfy the equation of (1) for all z = 0, 1, ..., U-1? Let us simply try to substitute the numbers w1, ..., wn for x1, ..., xn into the equation of (1). For z let us substitute some number Z to be determined later. What could we say about the value of P(b1, ..., bk, Z, w1, ..., wn)? If we added to (2) the condition
Z = z mod uz for all z = 0, 1, ..., U-1, ---------(3)
then we could conclude that
P(b1, ..., bk, Z, w1, ..., wn) = P(b1, ..., bk, z, x1(z), ..., xn(z)) mod uz.
Since all the right hand side values of P are 0, we obtain that
P(b1, ..., bk, Z, w1, ..., wn) = 0 mod uz
for all z<U, i.e. the left hand side number is divisible by all the numbers yz. Since two of these numbers never have common divisors, the left hand side number is divisible also by the product of them, i.e.
P(b1, ..., bk, Z, w1, ..., wn) = 0 mod u0u1...uU-1. ----------(4)
Now let us view (4) not as a consequence of some assumptions, but as a condition that is put on the numbers w1, ..., wn. If the numbers xi(z) are defined as wi mod uz, then from (2), (3) and (4) we obtain that for all z<U:
P(b1, ..., bk, z, x1(z), ..., xn(z)) = 0 mod uz.
We would like to force an "absolute" 0 on the right hand side instead of 0 mod uz. This would be achieved, if the left hand side number would be less than uz.
Exercise 4.19. Let N be the degree of the polynomial P, M - the sum of its coefficient modules, z<U, and let X exceed all xi(z). Verify that
|P(b1, ..., bk, z, x1(z), ..., xn(z))| <= T,
where T = M((b1+1)...(bk+1)U(X+1))N.
Hence, we must produce a (possibly simple) generator of divisors uz (z = 0, 1, ..., U-1) such that:
a) uz > T for all z<U.
b) The module of (4), i.e. the product u0u1...uU-1 is a possibly simple (i.e. "Diophantine") function. Otherwise we will have problems with finding a Diophantine representation of u0u1...uU-1.
c) Two of the numbers uz never have common divisors.
The following idea of producing uz is due to Matiyasevich and Julia Robinson. Let V be a large number (to start let U<=V), then we can generate uz in such a way that u0u1...uU-1 = CVU (i.e. b) will be satisfied). Indeed,
CVU = V(V-1)...(V-U+1)/U! = ((V+1)/1-1)((V+1)/2-1)...((V+1)/U-1).
Let us take
uz = (V+1)/(z+1)-1.
If we put the condition "V+1 is divisible by U!", then all uz will be integer numbers. If we put a stronger condition "V+1 is divisible by (U!)2", then two of these numbers never have common divisors (i.e. c) is satisfied).
Exercise 4.20. Verify that this is the case. (Hint: let d be a common prime divisor of ui and uj, consider ui and ui-uj.)
If we put also the condition uU-1>T (note that uU-1 is the least of all uz), i.e.
uU-1 > M((b1+1)...(bk+1)U(X+1))N,
then a) also is satisfied.
Now let us sum up all the conditions we have put on the numbers we have introduced, i.e. w1, ..., wn, Z, X, V:
G1: P(b1, ..., bk, Z, w1, ..., wn) = 0 mod CVU,
G2: (Az<U) Z = z mod uz,
G3i: (Az<U) wi mod uz < X for each i = 1, ..., n,
G4: uU-1 > M((b1+1)...(bk+1)U(X+1))N,
G5: V+1 is divisible by (U!)2,
where, of course, uz = (V+1)/(z+1)-1.
About G3i: since T depends on X, we must ensure also: wi mod uz < X for all z<U and i = 1, ..., n (otherwise the estimate of the exercise 4.19 will not hold).
Exercise 4.21. Verify that (1) is equivalent to the following formula:
EZEXEVEw1...Ewn G1 & G2 & G4 & G5 & G31 & ... & G3n. -------(5)
(Hints. Rightwards: first choose X to satisfy G3i's, then choose V to satisfy G5 and G4, generate the divisors uz, obtain the number Z by using Chinese Remainder theorem to satisfy G2, obtain the numbers w1, ..., wn by using Chinese Remainder theorem to satisfy (2), and finally, derive G1. Leftwards: having the numbers w1, ..., wn, Z, X, V take for each z<U: xi(z) = wi mod uz, etc.)
Why should we view (5) as a step forward from (1), when G2 and G3i contain the same quantifier Az<U? In (1) this quantifier stands over an arbitrary Diophantine representation, but in G2 and G3i it stands over simple specific formulas!
First, we need not to eliminate Az<U from G2, we can eliminate the entire G2. Indeed, we can take Z equal to V: since V-z is divisible by
uz = (V+1)/(z+1)-1 = (V-z)/(z+1)
(the fraction is equal to z+1), we have V = z mod uz for all z<U.
So, we can delete G2 from our list of conditions, replace G1 by
G1': P(b1, ..., bk, V, w1, ..., wn) = 0 mod CVU,
and delete the quantifier EZ from (5).
Now let us set to eliminating Az<U from G3i. If wi mod uz < X, then one of the numbers wi, wi-1, ..., wi-X+1 is divisible by uz, i.e. their product
wi (wi-1)...(wi-X+1) = wi!/(wi-X)! --------(6)
also is divisible by uz for all z<U. Since two of the numbers uz never have common divisors, the number wi!/(wi-X)! is divisible by their product u0u1...uU-1 = CVU. Hence, if G3i, then
G3i': wi!/(wi-X)! is divisible by CVU.
Thus we have got rid of the quantifier Az<U by introducing well-known functions! Still, unfortunately, G3i' does not imply G3i, i.e. these conditions are not equivalent! Indeed, if we know only that the product (6) is divisible by another product CVU, then we cannot guarantee that for each z<U the factor uz will divide one of the factors wi, wi-1, ..., wi-X+1.
If the number R divides the product P1P2...Pk, then R=R1R2...Rk, where each factor Ri divides the corresponding Pi. If Rj is maximum among the factors Ri, then Rjk>=R, i.e. Rj>=rootk(R). Hence, if R divides the product P1P2...Pk, then R and one of the factors Pj have a common divisor >= rootk(R). This is maximum we can guarantee!
Thus, if we replace G3i by G3i', then we can guarantee only that some wi-j (where 0<=j<X) and uz have a common divisor >= rootX(uz). Fortunately, this is enough to solve our problem completely!
Indeed, for a fixed z<U let us proceed from w1 to wn in the following way. We know that the product w1(w1-1)...(w1-X+1) always is divisible by uz. Then, first, for some number x1(z)<X the difference w1- x1(z) is divisible by some divisor S1>=rootX(uz) of the number uz. Of course, the product w2(w2-1)...(w2-X+1) also is divisible by S1. Hence, next, for some number x2(z)<X the difference w2- x2(z) is divisible by some divisor S2>=rootX(S1)>=rootX2(uz) of the number S1 (and of uz). Etc., finally, for some number xn(z)<X the difference wn-xn(z) is divisible by some divisor Sn>=rootX(Sn-1)>=rootXn(uz) of the number Sn-1 (and of uz).
Hence, for all i = 1, ..., n:
wi = xi(z) mod Sn, -------(7)
where Sn divides uz (and hence, CVU), and Sn>=rootXn(uz). From G1' we have:
P(b1, ..., bk, V, w1, ..., wn) = 0 mod Sn,
hence, by (7) and, since V = z mod uz,
P(b1, ..., bk, z, x1(z), ..., xn(z)) = 0 mod Sn.
Since z<U and all xi(z)<X, the left hand side value of P does not exceed
T = M((b1+1)...(bk+1)U(X+1))N.
Hence, this value of P will be forced to be an "absolute" 0, if rootXn(uz) will be greater than T. Thus, we must replace G4 by a stronger condition
G4': rootXn(uU-1) > M((b1+1)...(bk+1)U(X+1))N,
and our problem finally is 100% solved!
Exercise 4.22. Verify once more that (1) is equivalent to the formula
EXEVEw1...Ewn G1' & G4' & G5 & G31' & ... & G3n'.
Transform this formula into a Diophantine representation.
Q.E.D.
Further reading:
Hilbert's 10th problem database�in St. Petersburg
Hilbert's 10th Problem. By Yuri Matiyasevich. MIT Press, 1993, 288 pp. For details see http://logic.pdmi.ras.ru/~yumat/H10Pbook/ (Russian original available).
Yuri Matiyasevich. A direct method for simulating partial recursive functions by Diophantine equations. Annals of Pure and Applied Logic, 67(1-3): 325-348, 17 May 1994
Yuri Matiyasevich. Elimination of Quantifiers from Arithmetical Formulas Defining Recursively Enumerable Sets. ACA'2002: 8th International Conference on Applications of Computer Algebra. Volos, Greece, June 25-28, 2002. (See online Abstract.)
Jones, J.P. Universal diophantine equation. Journal of Symbolic Logic, 47 (1982), 549-571. MR 84e:10070.
For the 1982 state of art, see online Abstract of this paper, for example:
Theorem (Matiyasevich, 1977). Every recursively
enumerable set A is diophantine definable in 9
unknowns, degree 1.6*1045:
x in A <=> E x1 x2,...,
x9 [P(x, x1, x2,...,
x9) = 0].
Theorem. Every recursively enumerable set A
is diophantine definable in 26 unknowns, degree 24:
x in A <=> E x1 x2,...,
x26 [P(x, x1, x2,...,
x26) = 0].
Theorem. Every recursively enumerable set A
is diophantine definable in 58 unknowns, degree 4:
x in A <=> E x1 x2,...,
x58 [P(x, x1, x2,...,
x58) = 0].
etc.
Section 6.5 (about "Diophantine incompleteness theorem")
Back to title page.