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
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
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
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
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
(That bit about + being in x/2 + x/2 = x was silly, 2(x/2) = x is of course fine. -Vaughan)
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
participants (4)
-
Dr. P.T. Johnstone -
Michael Barr -
Ross Street -
Vaughan Pratt