Polynomial Time Computable Structures

[Vaughan Pratt]

If I've correctly understood Joseph Shipman's "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." dated Wed, 8 Dec 2021 18:51:46 -0500, then I would
expect a number of people to point out that the Farey fractions accomplish
this very neatly.

With parallel computing one can do even better, generating 2ᵐ + 1 rationals
in the interval [0,1] without repetition in m steps.  At step m = 0,
initialize the process with the 2⁰ + 1 = 2 rationals 0/1 and 1/1.  At each
subsequent step, between consecutive rationals a/c and b/d, interpolate
(a+b)/(c+d).  So at step m = 1 we have 1/2, bringing the count to 2¹ + 1 =
3, then at the second step 1/3 and 2/3 bringing the count to 4 + 1 = 5,
then at the third step 1/4, 2/5, 3/5, and 3/4 (so 8 + 1 = 9 rationals), and
so on.

It is well known that this process enumerates all reduced rationals without
repetition (use the fact that consecutive rationals viewed as a 2x2 matrix
always have determinant -1, preserved by elementary column operations).
Better yet, at every step those enumerated so far are in increasing order.
And it should be obvious that after step m there are 2ᵐ gaps, which step
m+1 splits into two gaps for the obvious proof by induction.

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