The Davis-Putnam-Robinson theorem showed that every partially computable m-ary function f (a1; : : : ; am) = c on the natural numbers can be specied by means of an exponential Diophantine formula involving, along with parameters a1; : : : ; am; c, some number of existentially quantied variables. Yuri Matiyasevich improved this theorem in two ways: on the one hand, he proved that the same goal can be achieved with no recourse to exponentiation and, thereby, he provided a negative answer to Hilbert's 10th problem; on the other hand, he showed how to construct an exponential Diophantine equation specifying f which, once a1; : : : ; am have been xed, is solved by at most one tuple hv0; : : : v i of values for the remaining variables. This latter property is called single-foldness. Whether there exists a single- (or, at worst, nite-) fold polynomial Diophantine representation of any partially computable function on the natural numbers is as yet an open problem. This work surveys relevant results on this subject and tries to draw a route towards a hoped-for positive answer to the nite-fold-ness issue.
variables 9 x ) '( za1; : : : ; am; }c|; x1; : : : ; x { ) ; | para{mzeters } |unkn{ozwns} (y) for some formula ' that only involves: ? The authors acknowledge partial support from the INdAM-GNCS 2019 research project Logic Programming for early detection of pancreatic cancer and from Universit degli Studi di Catania, Piano della Ricerca 2016/2018 Linea di intervento 2. the shown (pairwise distinct) variables, positive integer constants, addition, multiplication, and exponentiation operators, 1 the logical connectives & , _, 9 v, = .
Two major improvements to this result were achieved by Yuri Matiyasevich.
In [
P 0 (a1; : : : ; am; c; x2 ; : : : ; x ) = 4x1 + x1 + P 00(a1; : : : ; am; c; x2 ; : : : ; x ); where > 0 and P 0 and P 00 are polynomials with coecients in occurrences of x1 , such that no two tuples
ha1; : : : ; am; v0; v1; : : : ; v i ; ha1; : : : ; am; u0; u1; : : : ; u i on N exist satisfying '( a1; : : : ; am ; v0; : : : ; v ) & '( a1; : : : ; am ; u0; : : : ; u ). Thus, every tuple ha1; : : : ; ami on N either admits no continuation hv0; : : : ; v i satisfying 'and then ha1; : : : ; ami does not belong to the domain of F or exactly one, and then v0 is precisely the value F (a1; : : : ; am).
By introducing a little terminologyrather common in recursion theory, cf.
[
Moreover, a representation of R in the form ( ) is said to be single-fold or univocal : when each tuple ha1; : : : ; ami of natural numbers has at most one continuation hv1; : : : ; v i such that '(a1; : : : ; am; v1; : : : ; v ); nite-fold : when each tuple ha1; : : : ; ami of natural numbers has only nitely many continuations hv1; : : : ; v i such that '(a1; : : : ; am; v1; : : : ; v ) holds.
Let us sum up, utilizing these notions, the important results mentioned above,
along with two open issues raised many years ago, which still motivate us here:
Dpr61 [
Mat74 [
The derivation of DPRM from DPR required that exponentiation itself were proved to be Diophantine. A result by Julia Robinson, which we recapitulate in Sect. 2, played historically a key role in this arduous task: she had reduced the task to the quest for a Diophantine relation of exponential growth (a notion to be recalled soon here); and, indeed, Matiyasevich found a polynomial Diophantine representation of a specic exponential-growth relation.
After Matiyasevich [
Concerning the latter goal, in order to convince ourselves (as well as our readers) that the sought reduction technique reminiscent of J. Robinson’s one does exist, and to get closer to it, we undertake in this paper a comparison among various published versions of Robinson’s technique, discussing how her idea evolved over the years from its original formulation of 1952 towards simpler implementations, one of which might t our needs.
In preparation for some conclusive answer to Mat10be it positive or negative, this paper brings together scattered notes on nite-fold Diophantine representability. The forthcoming material is organized as follows. 2 Notice that in the case of the relation 2p = q we could take and then p = w + 2, q = 2w+2. = = = =2 = 2 There exist integers > 1 ; > 0 ; > 0 ; > 0 such that to each w 2 N other than 0 there correspond p ; q such that M(p; q), p < w , and q > w hold.
Sect. 1 reports the construction of a univocal exponential Diophantine representation of any given r.e. set R. Out of a formally specied register machine that reaches termination on the tuples belonging to Rand only on those, the proposed construction technique generates a formula ' such that ( ) holds. By and large, singlefold-ness results from the determinism of the device emulated by the exponential constraints embodied into '.
Then Sect. 2 discusses two ways of reducing exponentiation to any exponentialgrowth dyadic relation J (p; q); both techniques are due to Julia Robinson, who proposed them in 1952 and 1969 respectively. They ensure that if a (polynomial) Diophantine representation for J is found, then it can be converted into a Diophantine representation of exponentiation, and hence of any given r.e. set. Appendix A expounds the original correctness proof regarding the result of 1969.
Sect. 3 reports three ways, devised by Davis, Matiyasevich, and J. Robinson, of reducing exponentiation to the sequence yi(a) i2N of solutions to the specialform Pell equation (a2 1) y2 + 1 = with a > 1.3 Appendices B and C dwell upon the techniques by which those three reductions were obtained. 1
Univocal exponential representation of any r.e. set
Where does singlefold-ness of the exponential representation of an r.e. set R
Nm whatsoever stem from? In [
Rj Rj
Rj + 1 Rj
1
STOP
IF Rj = 0 GOTO k
conditional branch
This format is very elegant, 4 but the proof of the associated representability
result less transparent than later single-fold-representability proofs where
exponentiation was employed more liberally. Various proofs referred to register
machines, a popular model of abstract computing device, to which James P.
Jones and Yu. V. Matiyasevich resorted in three papers (see, e.g., [
A register machine consists of a list =0; : : : ; =` of instructions ; any execution of begins with instruction =0 and, unless it goes on forever, it terminates with =`. Finitely many program variables, R0; R1; : : : ; Rm; : : : ; Rr, called registers, occur in ; of these, R0 will hold the result a0 of the computation upon termination, if execution does reach =`. At the outset, the registers R1; : : : ; Rm must hold the respective input values a1; : : : ; am, while the values of all remaining registers are supposed to be 0. Here, w.l.o.g., we shall require that a0 = 0.
There are instructions of ve types: Suitable programming rules enforce that: (0) STOP only appears at the end of , namely as =`; (1) the number k that follows GOTO in a branch instruction always belongs to the interval 0; : : : ; `; (2) it never happens that a decrement Rj Rj 1 is reached when the current value of its register Rj is 0; (3) whenif everthe instruction =` is reached, each one of ( R0,) R1; : : : ; Rr has value 0.
The behavior of when its execution is triggered with input values ai loaded in its input registers R1; : : : ; Rm should be readily grasped by any person familiar with procedural programming. In order to describe that functioning, we must specify by means of exponential Diophantine constraints how the values of the registers evolve over time and which instruction is about being eected at each of the discrete time instants beating the execution.
An unknown, s, representing the overall number of execution steps, will play
a crucial role; in fact, we are interested in the r.e. set R consisting of those tuples
ha1; : : : ; ami which, when fed into , lead to termination. Unless execution
terminates, no natural number s should be an acceptable value for s under the
constraints to be associated with ; on the other hand, when a tuple leads
to termination, an acceptable value s for s must exist and it must be unique,
because the abstract computing device which we are modeling is deterministic.
4 Notice that the polynomial y + (y + z)2 belongs to Kosovsk’is family of polynomials
x1 + (x1 + x2)2 + (x1 + x2 + x3)3 + + (x1 + + xn)n dening, for each n 2 N,
an injective function of Nn into Nsee [
increment decrement un conditional branch halt In the latter case, the course of values of each register Rj (j = 0; : : : ; r) can be modeled as the sequence hrj;0; : : : ; rj;si formed by its initial value rj;0 and by its subsequent values rj;t with t > 0, where rj;t is the value held by Rj right after the execution of the t-th step. Notice that if execution terminates in s computation steps, no register will ever hold a value exceeding the quantity a1 + + am + s; therefore we can represent the course of values of each Rj by a single unknown, rj , designating the amount Pts=0 rj;t Qt, where Q > a1 + + am + s is a base for the positional encoding of numbers large-enough in order that every rj;t acts as a digit. Since s is a priori unknown, Q must in its turn show as an unknown, Q, in the constraints specifying . Out of practical concerns, it turns out convenient to subject Q, along with a buddy unknown [, to the conditions so that I designates Ps t=0 Qt. Thus, with respect to the bases Q and 2, I reads 1 + (Q 1) I = Qs+1 =
` X li ; i=0 1 : : : 11 | s{+z1 } and 0 : : : 0 1 : : : 0 : : : 0 1 | {[z } | {[z } | } s{+z1 and the equation on the right reects the fact that exactly one instruction is executed at each step. Putting j;i =Def 0 when =i does not aect Rj , else 1 according to whether =i is Rj
Rj 1 ; we must then require, for j = 0; : : : ; r that rj = rj + P` i=0 j;i li
Q + aj if 0 < j 6 m ; 0 otherwise; to state how the course of values of each variable is ruled by the execution steps. 5 5 Rather than presupposing that the value a0 of the output register be 0 at the end, here we could have modied the condition associated with R0 into r0 = r0 + Pi`=0 0;i li Q Qs+1 a0 ; thus capturing the graph ha0; a1; : : : ; ami an r.e. set on its own rightof the function computed by instead of its domain.
To perfect the constraint-based description of the execution of , we shall resort to the dominance relation a v b that occurs between a = Pkh=0 ah 2h and b = Pkh=0 bh 2h, with a0; b0; : : : ; ak; bk 2 f0; 1g, if and only if ah 6 bh choonldgsrufeonrche =PP0khkh;==100;ab:hh:22:hh; k. SiQnckhe=010 abhh= (0maondd 12)=yie00lds=tha01t a=v11b,htohledsLiufcaans’ds only if ab is odd. Hence dominance is exponential Diophantine; in fact, thanks to the binomial theorem, a v b holds if and only if the remainder of the integer division of j 2b+1 + 1 b = 2b a+ak by 2b+1 is odd. The nal constraints needed are, for j = 0; 1; : : : ; r and i = 0; 1; : : : ; `: rj v bQ=2 1c I and li v I, 1 v l0, l` v Qs; Q li v li+1 when =i is an incre-/decre-ment instruction; Q li v lk when =i is an unconditional branch instruction GOTO k; Q li v li+1 + lk and Q li v li+1 + Q I 2 rj when =i is a conditional branch instruction IF Rj = 0 GOTO k.
Example 1 (Adapted from [
( p = u v _ q = u v ) =) ( u = 1 () v 6= 1 ) & a+a+4 = p+q :
Thanks to DPR, the conjecture can also be formulated with no quantier alternations, by means of a sentence of the form
:(9 x0 9 x ) ( 0 ; x0 ; x1; : : : ; x ) , where is a quantier-free exponential Diophantine formula enforcing that holds, where
G(a) = c () (9 x1
variables 9 x ) ( zc ; a ; x}1|; : : : ; x { ) ;
pa|r{azm}’s |unkn{ozwns} G(a) =Def
< such that a + a + 4 = p + q ; : 0 otherwise:
Such a can be built by conjoining together all constraints that specify the behavior of a register machine computing G , in the manner discussed above. 6 2
Two admirable ways of specifying exponentiation in
terms of a relation of exponential growth
In the seminal paper [
variables 9 x ) '( bz; n; c ; }x|1; : : : ; x { ) p|ar{azm}’s |unkn{ozwns} (z) closely analogous to ( y), with permission to employ in the construction of ', instead of exponentiation, a dyadic relation J which is of exponential growth in the following sense: i) ii)
The essence of such a specication is best explained in terms of a polynomial which, chronologically (see [12, p.531]), made its rst appearance long after 1952: Lemma 1. There is a polynomial Q in two variables with coecients in that (using = as a short for 9 q ( = q2 ) ):
Q(w; h) = =) h > ww; to every w, there correspond h’s such that Q(w; h) = .
Q(w; h) := (w + 2)3 (w + 4) (h + 1)2 + 1.
Theorem 1. Let Q be as in Lemma 1. The following bi-implication then holds if J meets the exponential-growth requirements i) and ii).
bn = c () (9 w ; h ; a ; d ; ` ; u ; v ; s ; q) (c 1)2 + b + n = 0 _ (c + b = 0 & n > 1) _ b > 1 & c > 1 & d > ` & J (a; d) This rule, if there exists a Diophantine relation J satisfying i) & ii), provides a Diophantine representation of exponentiation.
Proof. Proving the stated bi-implication is not a simple matter: we refer the interested reader to [2, Appendix A] for details on this.
Concerning the second part of the claim, we must show that certain relations are Diophantine; namely: x > y , 9 v (x = v + y), x > y , x > y + 1, x = y max z , (x = y > z _ x = z > y), x = by=zc , 9 q q z 6 y < (q+1) z . _ _ & & bn = c () (9 a ; d ; ` ; s ; x ; h) (c Theorem 2. Suppose that J is an exponential-growth relation such that J (p; q) implies p > 1, and let Q be as in the proof of Lemma 1. Then the bi-implication holds, which gives us a Diophantine repr. of exponentiation if J is Diophantine. Proof. A proof of the stated bi-implication is provided in Appendix A; clearly divisibility is Diophantine, since x j y , 9 v (y = v x). 3
Three ways of specifying exponentiation in terms of the sequence of solutions to a special-form Pell equation Pell equations of the special form x2 (a2 1) y2 = 1 , with a > 1, have peeped in in the preceding section. Through one such equation we enforced a relationship between ` and r := n + (a 1) s in Theorems 1 and 2. Constraints involving the tricky polynomial Q(w; h) have also shown up; as one sees, Q(w; h) = q2 can be put in the said Pell format, becoming q2 (w +3)2 1 (w +2) (h+1) 2 = 1.
Generally speaking, the Pell equation x2 d y2 = 1 in the unknowns x; y has innitely many solutions in N, provided that the parameter d (also in N) is not a perfect square. In the special case when d = a2 1 with a > 1, the increasing sequence hxi(a) ; yi(a)i i2N of its solutions satises the double recurrence y0(a) = 0 ; y1(a) = 1 = x0(a) ; a = x1(a) ; yi+2(a) = 2 a yi+1(a) yi(a) ; xi+2(a) = 2 a xi+1(a) xi(a) : We summarize in Fig. 2 the combinatorial interplay among items in this sequence yielded by their generating rules (see, e.g., [18, pp. 439440] and [12, pp. 527 528]).
Many of the facts in Fig. 2 are needed, of course, in order to detail the proofs
of Theorems 1 and 2. They also enter Davis’s proof [
What we are seeing here is, in essence, a singlefold representation of
exponentiation in terms of the triadic relation yi(a) = y.7 In fact, for any triple
n = c, the shown system in the unknowns a; `; r
b; n; c of natural numbers: if b 6
etc. has no solution; if bn = c, then it has exactly one solution. Matters change
if we specify the relation yi(a) = y by polynomial Diophantine means (which is
7 To see this more clearly, one should set aside various eliminable constructs. E.g.
‘j’, along with xb+n(b + n + 1), can be eliminated by rewriting the fourth line of
the above specication as a constraint involving a new unknown w, as: (b + n) w =
yb+n(b + n + 1) & (b + n + 1)2 1 (b + n) w 2 + 1 = a2. Likewise, ` = xn(a)
becomes (a2 1) r2 + 1 = `2, and three unknowns will result from elimination of
>; >, and .
_
_
&
&
doablesee, e.g., [
As stressed in [17, pp. 4344], all today known methods of constructing a polynomial Diophantine representation ( z) are in fact based on the study of the behavior of recurrent sequences like the famous Fibonacci progression h0; 1; 1; 2; 3; 5; 8; : : :i, or a sequence hy0(a) ; y1(a) ; y2(a) ; : : :i, taken some modulo; clearly, this behavior is periodic and as a consequence each known Diophantine representation of exponentiation is innite-fold.
The situation does not improve, as for the nitefold-ness issue, even if we
resort to the elegant specication of exponentiation proposed in [
mn+1(16 (n + 1) mn+1(2 b + 2))c b yn+1 8 b (n + 1) yn+1(b + 1) + 2 =
yn+1 8 (n + 1) yn+1(b + 1) c , (9 x ; y ; z ; r ; s) z = c y + r & 1 + r + s = y z = yn+1(b x + 2) y = yn+1(x) x = 8 (n + 1) yn+1(b + 1) hold, where x; y; z; r, and s are uniquely determined. This gives us a Diophantine representation of exponentiation, whichever way we manage to get a Diophantine representation of either one of the triadic relations mi(a) = m, yi(a) = y.
One slightly less slick, but nevertheless very elegant, reduction of exponentiation to the sequence yi(a) i2N also deserves being mentioned: Theorem 5 ([12, pp. 534535]). When b > 1 and n > 1, the bi-implication bn = c () (9 m ; k ; p ; q ) k + n + 1 = ym b(n + 1) holds (whence, trivially, the variable m can be eliminated). 8 An early reduction of exponentiation to an integer quotient that involves, besides Diophantine functions, only the triadic relation yi(a) = y, appears in [16, p. 308]. & & & & & & & : A striking consequence of the univocal exponential representability of any r.e. set was noted in [16, p. 300 and p. 310]. One can nd a concrete polynomial H(a; x0; x1; : : : ; x ; y; w) with integral coecients such that:
such that H(a; v0; v1; : : : ; v ; u; 2u) > 0 holds; 2) to any monadic totally computable function C, there correspond ha; v0; v1; : : : ; v ; ui of natural numbers such that
H(a; v0; v1; : : : ; v ; u; 2u) > 0 and max v0; v1; : : : ; v ; u + 2 tuple hv0; v1; : : : ; v ; ui + 3 tuples > C(a) :
To see this, refer to an explicit enumeration f 0; f 1; f 2; : : : of all monadic partially computable functions (see [7, p. 73 ]), so that both of
H = f ha1 ; a2i 2 N2 | f a1 (a1) = a2 g ;
K = f a 2 N | ha ; xi 2 H holds for some x g are r.e. sets, the complement N n K of the latter is not an r.e. set, and the former can be represented in the univocal form shown at the beginning of Sect. 1, namely f a1 (a1) = a2 () (9 x1
9 x 9 y 9 w) 2y = w & D( a1; a2 ; x1; : : : ; x ; y; w ) = 0 ; where D is a polynomial with integral coecients; then put
H(a; x0; x1; : : : ; x ; y; w) =Def 1
D2( a; x0 ; x1; : : : ; x ; y; w) ; so that H(a; x0; x1; : : : ; x ; y; 2y) > 0 holds if and only if f a(a) = x0, and hence H satises 1).
By way of contradiction, suppose that there is a monadic totally computable function C such that the inequalities v0 6 C (a); : : : ; v 6 C (a), and u 6 C (a) hold whenever a tuple ha; v0; v1; : : : ; v ; ui of natural numbers exists such that H(a; v0; v1; : : : ; v ; u; 2u) > 0 holds; that is, they hold when a pair ha ; v0i 2 H exists (this happens, e.g., for the innitely many a’s satisfying C = f a). In particular, the said inequalities must hold when a 2 K. But then this would oer us a criterion for checking whether or not a 2 K, by evaluating a bounded family of expressions of the form H(a; v0; v1; : : : ; v ; u; 2u); however, this would conict with the fact that N n K is not r.e. We conclude that H satises 2).
Summing up, we are in this situation: thanks to reductio ad absurdum , we have found that the course of values of the concrete arithmetic expression H(a; v0; v1; : : : ; v ; u; 2u) exceeds zero at most once for each value a of a; it is unconceivable, though, that one can put an eective bound on the search space for positive values of H(a; v0; v1; : : : ; v ; u; 2u).
A proof that every r.e. set admits a nite-fold Diophantine polynomial representation would yield analogous, equally striking consequences about ‘noneectivizable estimates’.
Discussions with Pietro Corvaja were very fruitful for the matters of this paper. A
A quick account of the reduction, as proposed in [
N N and S N
i) Q(w; u) implies u > ww , ii) w > 1 & u > w2 w implies Q(w; u) ; iii) S(p; q) implies p > 1 & q 6 pp , iv) for each k > 0, there are p and q such that S(p; q) and pk < q . Then, as we will prove: bn = c () (9 a ; d ; ` ; r ; v ; s ; t) (c Lemma 2. The above bi-implication (@) holds if i), ii), iii), and iv) hold. Proof. Assuming that n > 1 & b > 1, we must show that bn = c holds if and only if: there are natural numbers a; d; `; r, and v = 2 a b b2 1, such that the conditions S(a; d), d > `, `2 (a2 1) r2 = 1, Q(b + n + 1; v) hold and, moreover, n is the remainder of the integer division of r by a 1 and c is the remainder of the division of ` (a b) r by v.
(‘(=’): By means of i), we get v > (b + n + 1)b+n+1 > bn; by means of iii), a > 1 and ` < aa. Thus, since n > 1 implies r > 0, we get ` = xi(a) and r = yi(a) for some i such that 0 < i < a; thereforetaking the congruence yi(a) i (mod a 1) into account i n (mod a 1), and hence i = n is the remainder of the division of r by a 1. Since ` (a b) r bn (mod v)thanks to the congruence xj (a) (a b) yj (a) bj (mod 2 a b b2 1) holding for all jand, moreover, ` (a b) r c (mod v), c < v, bn < v, we conclude that c = bn as desired.
(‘=)’): Notice that iii) and iv) imply that for every k there exists an innite sequence
hp0 ; q0i ; hp1 ; q1i ; hp2 ; q2i ; : : : in N N such that S(pj ; qj ), qj > pjk, and pj+1 > pj hold for every j.9 Hence we can choose an a so large that: for some d, S(a; d) and d > a2 n holds; a > n + b; Q(b + n + 1 ; 2 a b b2 1) (to enforce this, by ii), it suces to pick an a such that 2 a b b2 1 > (b+n+1)2 (b+n+1)) and, in consequence of i), 2 a b b2 1 > bn. To satisfy all desired conditions, it will then suce to take ` = xn(a) and r = yn(a), thanks to the congruence xn(a) (a b) yn(a) bn (mod 2 a b b2 1).
In order for Q to behave as wanted, it suces to put: 10
Q(w; u) =Def (9 x ; y) u > w x x > 1
& & 1) (w x2 (w2 1)2 y2 = 1 : Lemma 3. As just dened, the Diophantine relation
Proof. Suppose rst that Q(w; u) holds. From x > 1 it follows that w 2= f0; 1g; hence x = xn(w) & (w 1) y = yn(w) holds for some n > 0. Since yi(w) i (mod w 1) holds for all i, we get n 0 (mod w 1); therefore n > w 1 and, hence, u > w xw 1(w) > ww. This proves i).
Suppose next that w > 1. By taking x = xw 1(w) and y = yw 1(w) =(w 1), we easily check that Q(w; u) holds for every u > w xw 1(w). Since xi(w) < (2 w)i 6 w2 i holds for every i > 0, we get w xw 1(w) < w w2 w 2 < w2 w; therefore, Q(w; u) holds for every u > w2 w. This proves ii). 9 To choose p0; q0 so that S(p0; q0) & q0 > p0k, just rely on iv). Inductively, assuming S(pj ; qj ) & qj > pjk, notice that pj 6= 0 & pjpj > qj holds by iii), hence pj > k follows; therefore, by choosing pj+1 and qj+1 so that S(pj+1; qj+1) & qj+1 > pjp+j1, we will enforce qj+1 > pj+1; on the other hand, pj+1 6= 0 & pjp+j+11 > qj+1, and k therefore pj+1 > pj . 10 Notice that for w > 2 the inequality x > 1 amounts to the same as y > 0.
From Lemma 3 and Thm 2, by taking the above implementation of Qwhere we replace y by h + 1into account, we get straightforwardly: Corollary 1. If S is a Diophantine relation satisfying iii) & iv), the following rule provides a Diophantine representation of exponentiation: (Besides a; d; `; s; x; h, one needs one additional existential variable in the righthand side of this bi-implication in order to eliminate each inequality, plus one more to eliminate the divisibility relator ‘ j’. Thanks to the inequality a b > 0, we can also get rid of `, thus reducing the number of existential variables to 12.) B
Davis’s reduction of bn = c to the relation r = yn(a)
The following crucial link between exponentiation and the sequence hyi(a)ii2N
was pointed out in [
t > n &
b2 b2
1 & 1 ) : c ` (a Specically, when b > 1 and bn = c, the constraints here appearing in the scope of 9 can be satised in innitely many ways: for, corresponding to any t > n max b, it suces to put a = xt 1(t) in order to be able to determine the values of ` ; r , and h uniquely (see Lemma 4 below).
In light of the above biimplication, if we now provided a Diophantine representation of the relation r = yn(a), we would readily get that the relation bn = c is also Diophantine.
Let us recall here the proof of the above-stated relationship between exponentiation and the Pell equation. We begin with the proposition: Lemma 4. If b > 1 and bn = c, then to each number of the form a = x(s+1) (t 1)(t) with t > b max n there correspond uniquely values `; r; h such that the following conditions are met: r = yn(a), ` = xn(a), c < 2 a b b2 1, c ` (a b) r (mod 2 a b b2 1), and a2 (t2 1) (t 1)2 (h + 1)2 = 1. Proof. Observe that, since t > b > 1, the Pell equation x2 (t2 1) y2 = 1 has the usual innite sequence hhxi(t) ; yi(t)iii2N of solutions; therefore, it makes sense to put a := x(s+1) (t 1)(t). In its turn a > 1 holds, because x(s+1) (t 1)(t) > x1(t) > 1; hence it makes sense to put r := yn(a) and ` := xn(a).
Plainly, a > xt 1(t) > tt 1 > bn; hence it is easy to see that the inequality bn < 2 a b b2 1 is satised 11 when n > 0. The same inequality holds when n = 0, as it follows from a > tt 1 > t > b > 1.
The last two conditions in the claim simply state well-known congruences that are satised (as recalled in Fig. 2) by the solutions of any Pell equation of the special form being considered here. In particular, states that c ` (a (a b) yn(a) ( mod 2 a b 1 ): ( ) As for a2 (t2 1) (t 1)2 (h + 1)2 = 1, it merely expresses that y(s+1) (t 1)(t) is a non-null multiple of t 1; recall, in fact, that a = x(s+1) (t 1)(t) and t 1 > 0, and that the congruence yi(t) i (mod t 1) holds in general, for every i.
We next come to the converse of Lemma 4: Lemma 5. Suppose that b > 1 and that the conditions c < 2 a b b2 1; c ` (a b) r ( mod 2 a b b2 `2 (a2 1) r2 = 1 a2 (t2 1) (t 1)2 (h + 1)2 = 1 t > b max n; are satised by a; `; r; t, and h, where n is the value ensuring that r = yn(a). Then bn = c holds. 11 Here, as we will again do in the proof of Lemma 5, we are making use of the following fact (which gets easily proven even for a real number b): If n > 0, b > 1, and a > bn (with a; n 2 N), then 2 a b b2 1 > bn.
Proof. Since t > b > 1, the Pell equation x2 (t2 1) y2 = 1 has the usual innite sequence hhxi(t) ; yi(t)iii2N of solutions; thus, since a2 (t2 1) y2 = 1 holds for some y > 0, we have a = xj(t) for some j, where j > 0since a > tand ` = xn(a), r = yn(a) holds for a suitable n. Consequently 2 a b b2 1 > 2; moreover, by the well-known congruence ( ) recalled above, we have c bn ( mod 2 a b b2 1 ); whence the sought equality will follow if we manage to prove that both sides of this congruence are smaller than 2 a b b2 1 (as for c, this is an explicit assumption). Since this is obvious when n = 0, we will assume n > 0.
To see that bn < 2 a b b2 1, we argue as follows. Clearly yj(t) = (t 1) (h+1) holds, whence (t 1) (h + 1) j (mod t 1), i.e. t 1 j j, follows. Since j 6= 0, we get j > t 1, and therefore a = xj(t) > tj > tt 1 > bn. The sought inequality follows, which completes the proof.
Corollary 2. Put Q(w; h) := (w + 2)3 (w + 4) (h + 1)2 + 1 : Then, bn = c () (9 a ; ` ; r ; h) (c
1)2 + b + n = 0 _ (n > 1 & c + b = 0) Proof. Suppose rst that there are a; `; r; h satisfying the conditions in the scope of ‘9’, and that b > 1. By putting t := b + n + 1, we obviously get t > b max n and a2 (t2 1) (t 1)2 (h + 1)2 = 1, so that bn = c holds by Lemma 5.
Conversely, suppose that bn = c holds, where b > 1. Put t := b + n + 1 and a := xt 1(t). Then, by Lemma 4, unique values `; r; h exist satisfying all conditions that appear in the third disjunct of the scope of ‘ 9’ in the claim. C
Representing exponentiation as an integer quotient In the ongoing, in order to prove that bn = c () c = $ yn+1 8 b (n + 1) yn+1(b + 1) + 2 % yn+1 8 (n + 1) yn+1(b + 1) ; we will proceed to show, for b and n natural numbers, that bn = limx!1
; b > 1 & r = yn(a) (*) where x is a natural number sucently large to reduce the distance between bn and yn+1(b x + 2) = yn+1(x) to an amount less than 1. We will carefully assess how to take the value of x big enough. Our treatment adheres closely to [13, pp. 3132].
We begin by recalling, from fact 1 of Fig. 2: Lemma 6. For a > 2 and i 2 N, the following inequalities hold: Here the increase on the left is strict when i > 0; on the other side, when i > 1.
> Assessment of a value of x which ts our needs (cf. [13, p. 32]): Thus (*) becomes true as soon as x > 8 (n + 1) (b + 1)n; we can, e.g., enforce it by putting x := 8 (n + 1) yn+1(b + 1), thus getting the formulation of bn = c shown at the beginning of this appendix.