Real interval halving

Real interval halving

[Dr. P.T. Johnstone]

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

Re: Real interval halving

[Vaughan Pratt]

Thanks, Peter.  One of these days I'll learn to stop sending email after
midnight.  Continued fractions provide equally good coalgebraic structure
for both our product-with-omega functor (it's one of the examples in
our paper) and Peter F.'s X v X functor.  Either midnight madness or
sheer forgetfulness must have possessed me to malign its applicability
to the latter.

While I have that excuse handy let me also repair my description (in
the same message) of halving nonzero reals as right-shifting with sign
extension: following the shift the second bit must then be complemented.
Thus + (1/2) halves to +- (1/2 - 1/4 = 1/4) while +++ (1/2 + 1/4 + 1/8
= 7/8) halves to +-++ (1/2 - 1/4 + 1/8 + 1/16 = 7/16).  In the special
case of 1 as ++++... forever, +-+++... equals + (1/2), and dually for -1.

Contorted fractions make an earlier appearance in Conway's On Numbers
and Games (1976) (Winning Ways is 1983).  I hadn't realized Norton was
involved there: Conway credits several things to Norton in ONAG but I
guess he must have forgotten that one.

At the risk of turning this thread into a complete tangent space, yet
another construction of the group of reals is as the quotient G/H of the
pointwise-additive group G of bounded integer sequences by the subgroup H
consisting of those sequences b of the form b_0 = a_0, b_{i+1} = a_{i+1}
- 2a_i for some a in G.  This definition, which avoids detouring through
the rationals, resulted from my mulling over a talk at MIT by Gian-Carlo
Rota in the early 1970's on representing reals as sequences of bits.
I mentioned it at a recent theory lunch talk and Don Knuth mulled it
over and came up with the idea of modifying the boundedness condition
to allow G to be a ring thus making G/H a field (as an alternative to
taking product to be the unique bilinear operation * satisfying 1*1 =
1), see Problem 10689, American Mathematical Monthly, 105(1998), p.769.

I would love to know whether this construction can exploited in a
coalgebraic setting.

Vaughan Pratt

Re: Real interval halving

[Michael Barr]

Perhaps Vaughan is unfamiliar with the following definition of the reals.
I got it from Steve Schanuel.  I believe that he got it from Serge Lang
and he probably got it from Emil Artin.  Anyway, Let S be the ring of
functions s: N --> N such that the function of two variables (m,n) |-->
s(m+n) - s(m) - s(n) is bounded.  Addition is element-wise and
multiplication is functional composition.  Let I consist of the bounded
sequences.  Then R = S/I.  Interestingly, S is not commutative.

We now have a real tangent line.

Michael

Re: Schanuel's reals

[Ross Street]

Mike Barr writes:
>Perhaps Vaughan is unfamiliar with the following definition of the reals.
>I got it from Steve Schanuel.  I believe that he got it from Serge Lang
>and he probably got it from Emil Artin.

I believe the idea *came* from Artin but I don't believe Artin was 
thinking of it as a *construction* of the reals.  I was so taken by 
the construction that I thought it should be better known by tertiary 
teachers.  I wrote a little note

	An efficient construction of the real numbers,
	Gazette Australian Math. Soc. 12 (1985) 57-58

on the construction (giving credit to Schanuel and reporting that 
Peter Johnstone told me Richard Lewis from Sussex had also come up 
with it).
[Warning and Challenge: Steve pointed out that my note messes up the 
construction of the sup operation.]

Happy 2000 plus.

Ross

Re: Real interval halving

[Vaughan Pratt]

It's true I only learned about the Artin(?)-Schanuel construction
recently---Peter Freyd mentioned it to Phil Scott and me at lunch one
day at LL'96 in Tokyo, albeit with yet another attribution, Conway.
I thought it was very cute.

There is some sort of duality that I don't understand between this
construction and the Knuth-Pratt construction.  The former puts
the bounded sequences in the denominator and does the work in the
numerator, namely requiring that s(m+n) = s(m) + s(n) to within a
constant independent of m and n.  The latter puts the bounded sequences
in the numerator and does the work in the denominator, namely modding
out by the equation x/2 + x/2 = x, where x/2 is defined as right shift
(prepend zero).

Artin-Schanuel can be related to Dedekind as follows.  For Dedekind,
the unreduced rationals m/n together with all m/0 constitute Z^2,
the lattice points of the plane, whose nonempty rays are then the
reduced rationals.  The irrationals along with infinity (thinking of
the real line projectively) are then obtained as the empty rays, all
of which make distinct Dedekind cuts in the rationals, qua rays *or*
qua irreduced rationals (actually two cuts are needed in the projective
line, infinity supplies the other).  Artin-Schanuel identifies all but
the ray at infinity in terms of their neighborhoods instead of cuts,
specifying one point of the neighborhood per column.

Moving the bounded sequences from the denominator to the numerator
doesn't seem to be compatible with this picture.  What picture if any
is it compatible with?  And is there a categorical duality that goes
along with this inversion?  A passage from algebra to coalgebra perhaps?
Or is it the duality of addition and multiplication---we have
s(m+n) = s(m) + s(n) doing the work above and x/2 + x/2 = x at work
underneath, albeit with addition also party to the latter.

Vaughan

Re: Real interval halving

[Vaughan Pratt]

(That bit about + being in x/2 + x/2 = x was silly, 2(x/2) = x is of
course fine.  -Vaughan)

A couple of Y2K glitches

[Vaughan Pratt]

For a short while in the wee small hours of this morning, the US Naval
Observatory was reporting the year as 19100.  This is exactly 19 millennia
after Peter Johnstone's distinctly post-Boadicean message on continued
fractions, whose dateline reads

	Date: Sat, 1 Jan 100 11:37:15 +0000 (GMT)

Granted the point of Y2K compliance was to avoid rolling back to the
year 1900 by carrying a 1 into the hundreds position, but in hindsight
that can be taken in various ways.

Vaughan