The Other End of the Spectrum

In this section we would like to describe some work (still in progress) which approached HTP over big rings from the other end of the spectrum, i.e. from the point of view of Q. Before we can discuss these very new ideas we need to make a quick detour to review some basic notions of logic.

Definition 3.8 (Turing Reducibility) Let A c Zk, B c Zm for some positive integers k, m. Assume also that there is an effective procedure to determine membership in A using an oracle for membership in B. In this case we say that A is Turing reducible to B and write A B .If additionally we have B A, then we say that B is Turing-equivalent to A. The equivalence classes of Turing equivalence are called Turing degrees.

We now need to review a definition of a famous set.

Definition 3.9 Let {fi} be an effective enumeration of all computable functions and let

In this case we call H the Halting Set.

It is not hard to see that

  • (a) H is r.e. and
  • (b) every r.e. set is Turing reducible to H (so in some sense H is the “hardest” r.e. set),

Our next step is to convert the question of decidability of HTP of a recursive ring R into a question of the Turing degree of a subset of Z>0. (Here we remind the reader that by a recursive or computable ring we mean a ring which is recursive as a set and with operations corresponding to total recursive functions. A ring isomorphic to a recursive ring will be called computably presentable.) To that end let {pi (x)} be an effective enumeration of all polynomials over R and let HTP(R) denote the set of indices corresponding to polynomials having a root in R. Now given DPRM result we have that HTP(Z) =T H. Further, any recursive or computably presentable ring R with a Diophantine model of Z has HTP(R) =T H.

At the same time, by results of Friedberg [16] and Muchnik [27] we know that there are Turing degrees containing undecidable r.e. sets not as hard as H, i.e. H is not Turing equivalent to these sets. What if HTP(Q) is one of these sets? If this were the case, there would be neither an algorithm to solve HTP over Q nor a Diophantine model of Z over Q. So if HTP(Q) =T HTP(Z) it makes sense to see if there are big subrings R of Q, “infinitely” far away from Q with HTP(R) =T HTP(Q).

In order to explain how we get “far away” from Q we need to discuss the notion of being integral at a prime and reconsider results of J. Robinson we introduced

pa1 pam

before with a new spin. If x e Q, x = 0, then we can write x = m-, where

qi -q*

pi,..., pm, q1,...,qk are distinct prime numbers and ai ,...,am, b1,...,bk are positive integers. We define ordpix = ai, ordqjx = -bj, and for a prime number

we define ordtx = 0. If t is a prime and x is a rational number with ordtx > 0, we say that x is integral at t.

We nowgobacktoa result of Julia Robinson we used before: Theorem 3.3, proving that the set of all rational numbers integral at a given prime is Diophantine over Q, and examine more closely what was involved in a construction of this Diophantine definition. The construction of the definition is in fact uniform in p, i.e. given a p there is an effective procedure taking p as its input and constructing the existential definition of the valuation ring of p—the set of all rational numbers integral at p. Since we can effectively combine a finite number of Diophantine definitions into one over any subring of Q, we conclude that we have an algorithm for writing down Diophantine definitions of rings of rational numbers without a fixed finite set of primes dividing the denominators.

In the project still in progress (see [12]) K. Eisentrager, R. Miller, J. Park, and A. Shlapentokh have constructed families of computably presentable subrings R of Q with HTP(R) =T HTP(Q). The constructed rings consist of rational numbers where an infinite set of primes is allowed to divide the denominator, but the complement of this set of primes, that is the set of primes that are not allowed to divide the denominator is also infinite. Priority method was used to make the set of inverted primes c.e. (and thus the rings computably presentable). Further, the set of primes which can occur as divisors of the denominators of elements in the ring can be arranged to have the lower natural density equal to 0. So we are truly looking at a ring “in the middle”, “infinitely far away” from both Z and Q. These rings also have the property that the set of inverted primes, i.e. primes allowed to divide the denominators is computable from HTP(Q). So if HTP(Q) is decidable, these prime sets are also decidable and the rings in question are computable subrings of Q (not just computably presentable).

The co-authors have also obtained an analog of Theorem 3.5, though a weaker one. More specifically, for any positive integer k, one can partition the set of all prime numbers into k sets S1,..., SK, each of lower density 0, and construct rings R1Rk where the primes allowed to divide the denominators are precisely S1,..., SK respectively and such that HTP( Rt) =T HTP(Q). Unfortunately, these rings are not necessarily computably presentable and we can only say that each S is Turing reducible to HTP(Q), so that again if HTP(Q) is decidable, these prime sets are also decidable and the rings in question are computable subrings of Q.

Now if we combine the results above with results constructing big rings with HTP equivalent to the halting problem, then one can conclude that if HTP over Z is different from HTP over Q, in particular if HTP(Q) is decidable, then we have an extremely strange picture of tightly intermingled recursive rings inside Q with different levels of difficulty for HTP. Such a picture seems unlikely, though of course we cannot rule it out without a proof.

< Prev   CONTENTS   Source   Next >