Polynomial Time Computable Structures

[Vaughan Pratt]

> > From:\ JOSEPH SHIPMAN <joeshipman at aol.com>
> > Sent: Thursday, December 9, 2021 8:12 PM
> > Subject: Re: Polynomial Time Computable Structures
> >
> > It’s not clear to me that that gives a bijection between natural numbers
> and rationals which is polynomial time in both directions (although one of
> the earlier answers did give one).
>
>
Sorry, Joe, I hadn't realized you wanted a polynomial-time bijection in the
sense that *both *directions are polynomial time.

Exercise 1.3.2-18 of Volume I of Knuth AoCP gives a recurrence based on
Euclid's algorithm that should give one direction.  However to get both
directions in polynomial time I used the following structure of the Farey
sequence of rationals in [0,1), involving less arithmetic than Euclid's
algorithm.

The following tabulates the first 16 numbers in the Farey sequence,
organized into five rows each containing 2^L numbers where L+1 is the
length in binary of the binary numerals indexing the sequence.  The first
two rows contain 0/1 and 1/2 respectively.  Next is 1/3 and 2/3 with L = 1,
then 1/4, 2/5, 3/5, 3/4 with L = 2, etc. The corresponding natural numbers
indexing the Farey sequence are 0, 1, 2-3, 4-7, and 8-15, that is, the
first 16 Farey fractions.  As binary numerals the L-th row from L = -1 to L
= 3 contains all the numerals of length L+1, e.g. 0/1 is 0 which is special
because its binary representation doesn't start with 1, 1/2 is 1 which has
length 1 so L = 0, 3/5 is 6th in the sequence = 110 in binary so length 3
so L = 2 etc.

0
1

1
2

 1  2
 3  3

 1  2  3  3
 4  5  5  4

 1  2  3  3  4  5  5  4
 5  7  8  7  7  8  7  5

1.   The map from ℕ to Q' where Q' is the set of rationals in the interval
[0,1).

The following represents natural numbers as binary strings, with the empty
string ϵ denoting 0, followed by 1, 10, 11, 100, 101, 110, 111, and so on.
>From 10 onward, every binary numeral has the form 10w or 11w where w is
some string of bits.   The following inductively defines integer-valued
functions num and den mapping the empty string to the rational 0/1 and each
string w starting with 1 to the rational num(w)/den(w).

num(ϵ) = 0, den(ϵ) = 1.
num(1) = 1, den(1) = 2.
num(10w) = num(1w), den(10w) = num(1w) + den(1w).
num(11w) = den(1w), den(11w) = den(1(1w)') where w' is the 1's complement
negation of w (and only of w, not of bits to its left).

It should be straightforward to see how this works by reference to the
above list of the first 16 Farey fractions.   den(1(1w)') in the last line
exploits the fact that every line of denominators is a palindrome.

--------------------------

2.  The map from Q' to ℕ:

The above inductive definition can be inverted yielding another inductive
definition.  r(n/d) yields the rank r(n/d) of n/d in the Farey sequence.
L(n/d) is an auxiliary function that determines the level of n/d, e.g.
L(4/7) = 3 because 4/7 is at level 3 (the level of 0/1 is -1 by convention
but is not used.  Unlike the map in AoCP based on Euclid's algorithm, no
division is required and the only multiplications are left shifts.

r(0/1) = 0 (and L(0/1) = -1 for totality but unused)
r(1/2) = 1, L(1/2) = 0  (the only case where 2n = d)
2n < d:  r(n/d) = r(n/(d-n)) + 2^L(n/(d-n)), L(n/d) = L(n/(d-n)) + 1.
2n > d: r(n/d) = 3*2^L(n/d) - (r((d-n)/d) +1), L(n/d) = L((d-n)/d).

As with the other map, the last line exploits the fact that the 2^L
denominators at level L form a palindrome.

That both directions take polynomial time (linear depending on how you
count) follows from the fact that both recursions stay at the same level
for at most one step (the cases 11w and 2n > d respectively) before going
down to the next level.

Since the set Q of all rationals is in bijection with ℤ×Q' (it helps that
Q' is half-open), the above bijection is easily extended to a bijection
between the natural numbers and all the rationals.

Vaughan Pratt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211213/1bcd885a/attachment-0001.html>