Subject: Re: [HM] Minkowski's ? function and a certain number sequence
From: Thomas Bartlow (thomas.bartlow@villanova.edu)
Date: Tue May 30 2000 - 14:43:49 EDT
The article is Neil Calkin and Herbert S. Wilf, Recounting the Rationals,
American Mathematical Monthly 107 (April 2000), 360-363. As is usual with
Wilf, it is a marvelous exposition.
John Conway wrote:
> The current Amer. Math. Monthly has a nice article by Herb Wilf et al.,
> or more probably Al. et Wilf (I'm afraid I don't have it with me and can't
> recall the names, but "Wilf" is unlikely to be the first of them!) which
> pleased me very much, because it led me to a relation between two things
> I've long been interested in.
>
> The first is the number-sequence defined by
>
> f(1) = 1, f(2n) = f(n), f(2n+1) = f(n) + f(n+1)
>
> and the second is the function I called [x] (x in a box) in ONAG,
> but later learned from someone that it was discovered by Minkowski,
> who called either it or its inverse the question-mark function.
>
> Since I've been very interested in both of them, I was both pleased
> and surprised to discover how closely they're related, a discovery
> that led me to find many new properties of the sequence. It now seems
> important enough to deserve a fixed name and notation, and one of the
> reasons I'm sending this to historia-mathematica is the hope that one
> of the members of that group will be able to find some early references.
>
> AletWilf define a certain enumeration of the non-negative rationals;
> say
> rat_0, rat_1, ... and in general rat_N = num_N/den_N,
>
> which I'll abbreviate here to rN = nN/dN, and use the formal names
>
> "the Nth rational (numerator,denominator)" for rN (nN,dN).
>
> Here is a table of numerators
>
> N = 0 1 2 3 4 5 6 7 8 9 11 13 15 17 19 21 23 25 27 29 31 33
> nN = 0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6
>
> The denominators form the same sequence, since den_N = num_N+1, but a
> certain symmetry between them makes it a good idea to use both notations
> (much as we define two functions sin and cos, despite the fact that
> one is a translate of the other).
>
> It's a good idea to work think of the arguments of num and den as
> given in binary. Then the equations
>
> num_2N = num_N and den_2N+1 = den_N
>
> say that num (resp. den) is unaffected by adjoining trailing 0s
> (resp. 1s) to its argument, so we need only study arguments of the
> form
>
> 1^a, 1^a O^b 1^c, 1^a 0^b 1^c 0^d 1^e, ... for num
> and
> (empty), 1^a 0^b, 1^a 0^b 1^c 0^d, ... for den.
>
> Their values at these places are the well-known functions
>
> [a] [a,b,c] [a,b,c,d,e] ...
>
> [] [a,b] [a,b,c,d] ...
>
> called continuants, the general one being definable either as
> a determinant, for example
>
> | a -1 |
> | 1 b -1 |
> [a,b,c,d,e] = | 1 c -1 |
> | 1 d -1 |
> | 1 e |
>
> or by an equivalent recurrence relation, for example
>
> [a,b,c,d,e] = a[b,c,d,e] + [c,d,e].
>
> The first few of these polynomials are
>
> [] = 1,
> [a] = a
> [a,b] = ab + 1
> [a,b,c] = abc + a + c
> [a,b,c,d] = abcd + ab + ad + cd + 1
>
> the general one being the sum of all subproducts of its
> arguments for which the omitted terms can be grouped into
> adjacent pairs.
>
> Among the properties I found are the "palindromy assertions"
>
> num_S' = num_S and den_S' = den_S~
>
> where S' denotes the reverse of S and S~ the complemement
> of S (switch 0s and 1s), and the "addition laws"
>
> nST' = nS.dT + dS.nT and dST' = dS.dT~ + nS.nT~.
>
> Let me ask the historians if they can find the earliest
> occurence of this wonderful sequence.
>
> The Minkowski function is the map from reals to reals
> which may be defined as the simplest one that takes the
> "binary" notion of simplicity used in ONAG to the one
> based on size of denominator. Let me temporarily call it
> ?(x) - then
>
> ?(.0^a 1^b 0^c ... ) = 1/a + 1/b + 1/c + ... ,
>
> where the thing on the right is a continued fraction.
>
> The wonderful relation is the fact that
>
> ?(x) = num(x)/num(1+x),
>
> so that Minkowski's function is just the AletWilf enumeration
> extended to fractional values! (The extension is the obvious
> one, via the relation num(x) = num(2x).)
>
> I hope one of the historians can find the Minkowski reference,
> and so tell us whether this is indeed his function or its inverse,
> and exactly what was his notation for it.
>
> I'd like to write more, but have to leave now.
>
> Regards, John Conway
Thomas L Bartlow
Assistant Professor
Department of Mathematical Sciences
Villanova University
800 Lancaster Avenue
Villanova PA 19085
fax: 610-519-6928
work: 610-519-7331
http://www66.homepage.villanova.edu/thomas.bartlow
Thomas.Bartlow@villanova.edu
This archive was generated by hypermail 2b28 : Tue May 30 2000 - 18:18:40 EDT