Polynomial Time Computable Structures

[JOSEPH SHIPMAN]

Thanks very much!

Sent from my iPhone

> On Dec 16, 2021, at 4:00 PM, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
> 
> 
> 
>> > 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/20211216/e947e104/attachment.html>