Polynomial Time Computable Structures

[Yves Bertot]

Just dropping off pointers: you may want to look at the litterature 
around Stern-Brocot trees, for instance on Wikipedia.

The following paper is probably also useful:

"Recounting the rationals", Calkin and Wilf, American Mathematical 
Monthly, 107(4):360-363, 2000 is probably also useful.  (it maybe the 
same as this: https://www2.math.upenn.edu/~wilf/website/recounting.pdf)

In my own studies of the topic, and in work with Milad Niqui, we came up 
with the following bijection between positive integers and positive 
rational numbers:

  f (1) |-> 1

  f (2 * n) -> f(n) + 1  = p + q / q  if f(n) = p/q

f (2 * n + 1) -> 1 / (1 + 1/(f n)) = f(n) / (1 + f(n)) = p / (p + q) if 
f(n) = p/q

This is an enumeration without repetition, I don't understand what you 
mean by "Nth rational number computable in time polynomial in the length 
of N".  Here, the computation is logarithmic in N (because of the use of 
binary representation, if you consider addition to have a cost of 1, and 
if the computation has to give the numerator and denominator), but what 
is the length of N?  and how do you measure the computation time?

For what it's worth, you may want to consider that a rational number is 
a sequence of bits.  Comparison ( <, >, and =) can be tested in linear 
time in the length of this sequence of bits, without ever needing to 
compute their numerators and denominators.  On the downside, the integer 
n is represented by a sequence of length n, and addition and 
multiplication are more complex to write (in experiments, we discovered 
that computing the numerator and denominator, and then performing the 
gcd algorithm was a reasonable way to perform the computation: the 
sequence of bits can be constructed while computing the gcd).

To explain the last sentence, when you have a rational number p / q, you 
construct the inverse image in the following manner):

f^-1(p / q) = 1 if p = q

f^-1(p / q) = 2 * f^-1( (p - q) / q) if p > q

f^-1(p / q) = 2 * f^-1 ( p / (q - p)) if q > p

testing whether p = q and computing (p - q) or (q - p) depending on 
which is positive are the operations you perform when computing the gcd.

Seen directly as a function from rational numbers to integers, you have :

f^-1(x) = 1 if x = 1

f^-1(x) = 2 * f(x -1) if x > 1

f^-1(x) = 2 * f(1/(1 - x)) +1 if x < 1

A paper describing the bijection and its representation in a theorem 
prover (Coq) is available here:

https://www.sciencedirect.com/science/article/pii/S1571066104807540

unfortunately, at the time I was not aware of previous work on 
enumerating the rational numbers, the pointers to existing litterature 
were not imposed on me by referees, and I learned about existing work 
when presenting the paper at a conference, thanks to oral discussion.  
This lead to collaborations with Milad Niqui.

If you skip the part about Coq encodings, you will have a summary of the 
naive mathematical properties.

Formal proof about these representation are available here:

https://github.com/coq-community/qarith-stern-brocot


Yves

On 12/9/21 12:51 AM, JOSEPH SHIPMAN wrote:
> I would like to have an enumeration without repetitions of the 
> rationals in which the “Nth rational number” is computable in time 
> polynomial in the length of N, rather than time polynomial in N.
>
> If this has a negative answer, then the definition of “polynomial time 
> computable structure” becomes problematic.
>
> The standard enumerations of the rationals, where you enumerate the 
> fractions and cross off the ones not in reduced form, aren’t 
> computable in polynomial time in this sense unless factoring integers 
> is polynomial time.
>
> If the “Nth prime” function were computable in time polynomial in the 
> length of N, then I could make an enumeration of the rationals 
> (without repetitions) which is fast enough.
>
> If there is no such enumeration, then, even though the canonical form 
> of rationals as finite strings over an alphabet consisting of finitely 
> many numerals, “-“, and “/“is polynomial time computable and the 
> arithmetic operations on such canonical forms are polynomial time 
> computable, there doesn’t seem to be a presentation in terms of 
> “polynomial time computable functions on the natural numbers”, so that 
> the structure of rationals is somehow essentially more computationally 
> complex than the structure of natural numbers or the structure of 
> integers.
>
> Of course, there’s no problem if you don’t insist on having a 
> polynomial time bijection with the natural numbers. For the rationals 
> we don’t care so much, because the “reduced forms” are so dense in the 
> space of “fractions” that we aren’t sacrificing anything significant 
> in terms of time complexity. But for a structure with a notation 
> system whose reduced or canonical forms are sparse, it makes a difference.
>
> — JS
>
> Sent from my iPhone
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211209/8b009e86/attachment-0001.html>