categories: Real interval halving

["Dr. P.T. Johnstone" <P.T.Johnstone@dpmms.cam.ac.uk>]

Apologies for going off at a tangent, but someone ought to pick up Vaughan's
throwaway remark that the `Conway' coalgebra structure on [-\infty,\infty]
is the unique `natural' structure that makes it a final coalgebra. There is
another one, which was (implicitly) pointed out by Simon Norton around the 
time (early 1970s) when Conway was developing the theory of surreal numbers.

Conway's definition is based on the idea that the simplest number between
0 and 1/2 is 1/4, the simplest between 1/4 and 1/2 is 3/8, and so on; thus
the simplest number in any nontrivial interval is always a dyadic rational
(i.e. one whose denominator is a power of 2). Suppose you want to regard all
rationals as simple, and use smallness of denominator as a measure of
simplicity; then you would say that the simplest number between 0 and 1/2 is
1/3, the simplest between 1/3 and 1/2 is 2/5, .... Norton observed that this
notion of simplicity can be encoded by the notion of continued fraction, as 
follows:

Define a bijection f: [0,1] --> [0,1] as follows: if x has binary expansion
.00...011...100...011...1..., where there are a (\geq 0) zeros in the first
block, then a block of b (\geq 1) 1's, then c (\geq 1) zeros, and so on, then 
f(x) is the continued fraction

            1
         --------------------
         (a+1) + 1
                 ------------
                 b + 1
                     ---------
                     c + ......

Thus, for example, if x = 1/4, its two binary expansions .0100000... and
.00111111... yield the two expressions

            1                                1
         --------------      and          ----------
         2 + 1                            3 + 1
             ----------                       ------
             1 + 1                            \infty
                 ------
                 \infty

for f(1/4) = 1/3. Extend f to a function R --> R by invariance under integer
translations, i.e. f(x + n) = f(x) + n if n is an integer (and set 
f(\infty) = \infty, f(-\infty) = -\infty, if you insist). Then if x is the 
Conway-simplest number in the interval (a,b), f(x) is the Norton-simplest
number in (f(a),f(b)). Similarly, one can conjugate the `Conway' coalgebra
structure on [-\infty,\infty] by the function f, to obtain a different
(but isomorphic, and hence also final) coalgebra structure which has an 
explicit definition in terms of operations on continued fractions.

I believe the function f appears in `Winning Ways' (I don't have my copy to
hand) in the context of a game called `Contorted Fractions' (`contorted' is
of course a Conwayesque conflation of `continued' and `Norton'). There are
many mysteries about it. It obviously maps the dyadic rationals bijectively 
to the set of all rationals (and the non-dyadic rationals to the quadratic
irrationals); it is strictly increasing, but it's not hard to see that its
inverse is differentiable at every rational with derivative zero. Whether
it's differentiable anywhere else is, I believe, an open problem (though
there are certainly points where it's not differentiable). If you sketch
its graph, you will see that (as well as fixing all half-integers) it has a
fixed point in the interval (0,1/2) -- it's somewhere around 0.42, in decimal
notation -- but we never managed to prove that this fixed point was unique,
let alone determine whether it is algebraic or transcendental.

Happy New Year,
Peter Johnstone