Def: characteristic, Sturmian word The characteristic of a real number x is the binary string c1c2c3..., where c(k) = [(k+1)*x] - [k*x] - [x], k=1,2,3,... , and []=floor. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit) Newsgroups: sci.math.research Subject: Re: Efficient computation of [(n+1)r] - [nr]? Date: Sat, 23 Aug 1997 11:10:41 GMT Mark Hopkins wrote: >Is there an efficient algorithm to compute: > > [(n+1)r] - [nr], n = 0, 1, 2, ... > >where r is an algebraic number, and [x] is the greatest integer not exceeding >x. By efficient, I mean the computation of this expression should take on the >order of log(n) additions and multiplications, or maybe on the order of some >low power of log(n). I think it should be possible to show some power of log(n), yes. Here is a sketch of how to do it; some details need to be filled in. The only potential difficulty comes where [nr] (or [(n+1)r]) is very very close to an integer. However, Roth's theorem says that, for algebraic numbers, the approximation cannot be too good. So one can simply calculate a decimal approximation to r (being given, I assume, the polynomial p of which r is a root, and an interval containing only one of the roots of p), and then compute [(n+1)r] - [nr]. It is known how to efficiently compute good approximations to algebraic numbers -- see papers of Brent and others. If the number of digits you've chosen is insufficient to determine [(n+1)r] and [nr] with confidence, double it. You are guaranteed by Roth's theorem not to have to use too many. >Example answer: if r is the square-root of 2, one can generate the sequence >( [(n+1)r] - [nr]: n = 0, 1, 2, ... ) by starting out with 1 and repeatedly >expanding the sequence by simultaneously converting its elements to >subsequences as follows: > > 1 -> 11212, 2 -> 1121212 It is known that not every algebraic number can be expanded in such a simple way -- that is, as a fixed point of a homomorphism. First, r must be a quadratic irrational, but even that is not sufficient. There are three papers that give a complete characterization of the quadratics that can be expanded as fixed points. See @article{Crisp&Moran&Pollington&Shiue:1993, key = "Crisp, Moran, Pollington, and Shiue 1993", author = "D. Crisp and W. Moran and A. Pollington and P. Shiue", title = "Substitution invariant cutting sequences", journal = JTNB, volume = 5, year = 1993, pages = "123-137"} @article{Komatsu&vanderPoorten:1996, key = "Komatsu and van der Poorten 1996", author = "T. Komatsu and Poorten, A. J. van der", title = "Substitution invariant {Beatty} sequences", journal = JJM, volume = 22, year = 1996, pages = "349-354"} @incollection{Berstel&Seebold:1993b, key = "Berstel and {S\'e\'ebold} 1993b", author = "J. Berstel and P. {S\'e\'ebold}", title = "A characterization of {Sturmian} morphisms", booktitle = MFCS93, editor = "A. Borzyszkowski and S. Soko{\l}owski", publisher = SV, year = "{\noopsort{1993b}}1993", series = LNICS, volume = 711, pages = "281-290"} Here JTNB = "Journal de Theorie des Nombres de Bordeaux" and JJM = "Japanese J. Math.". Hopefully the other abbreviations are clear. By the way, if you are doing literature search, the infinite words of the form [(n+1)r] - [nr] are often called 'characteristic sequences', 'characteristic words', 'Christoffel words', 'mots de Christoffel', 'Sturmian words', and 'cutting sequences' in the literature. >All solutions to quadratic equations (over integer polynomials) should expand >in a similar way. I haven't yet figured out how roots to cubics or higher >order polynomial equations expand, since that's the essential key to the >question. In general, the expansion for *any* real number r is intimately related to r's continued fraction expansion. This idea goes back to Bernoulli. There are *many* papers that have described this expansion, some without knowing of previous work. Just a few of the papers given below. With the result(s) in these papers, one may easily compute the n'th term of [(n+1)r] - [nr] given the continued fraction for r. (By this I envision an oracle that gives you the first j characters in [a_0,a_1,a_2,...] with cost proportional to some power of j. You might worry about huge partial quotients, but huge partial quotients mean that a previous segment of the Sturmian word is repeated a huge number of times, so no problem.) @article{Christoffel:1888, key = "Christoffel 1888", author = "Christoffel, E. B.", title = "{Lehrs\"atze} {\"uber} arithmetische {Eigenschaften} der {Irrationalzahlen}", journal = "Annali di Matematica Pura ed Applicata, Series II", volume = 15 , year = 1888, pages = "253-276"} /u/shallit/AS/sturm.bib: @article{Christoffel:1875, key = "Christoffel 1875", author = "E. B. Christoffel", title = "Observatio arithmetica", journal = "Annali di Matematica", volume = 6, year = 1875, pages = "145-152"} /u/shallit/AS/bernoulli.bib: @article{Smith:1876, key = "Smith 1876", author = "Smith, H. J. S.", title = "Note on Continued Fractions", journal = MESSM, volume = 6, year = 1876, pages = "1-14"} More modern references are @article{Szusz:1985, key = "{Sz\"usz} 1985", author = "P. {Sz\"usz}", title = "On a theorem of {Fraenkel}, {Levitt}, and {Shimshoni}", journal = DM, volume = 56, year = 1985, pages = "75-77"} @article{Fraenkel&Levitt&Shimshoni:1972, key = "Fraenkel, Levitt, and Shimshoni 1972", author = "A. S. Fraenkel and J. Levitt and M. Shimshoni", title = "Characterization of the set of values $f(n) = [n \alpha], n = 1,2,\ldots$", journal = DM, volume = 2, year = 1972, pages = "335-345"} @article{Fraenkel&Mushkin&Tassa:1978, key = "Fraenkel, Mushkin, and Tassa 1978", author = "A. S. Fraenkel and M. Mushkin and U. Tassa", title = "Determination of $[n\theta]$ by its sequences of differences", journal = CMB, volume = 21, year = 1978, pages = "441-446"} @article{BrownT:1991, key = "T. Brown 1991", author = "T. C. Brown", title = "A characterisation of the quadratic irrationals", journal = CMB, volume = 34, year = 1991, pages = "36-41"} @article{BrownT:1993, key = "T. Brown 1993", author = "T. C. Brown", title = "Descriptions of the characteristic sequence of an irrational", journal = CMB, volume = 36, year = 1993, pages = "15-21"} Here CMB = "Canad. math. Bulletin", and DM = "Discrete Math.". Hope this helps. Allouche and I are writing a book on number theory and formal languages which will cover this topic, and many others, in detail. Jeffrey Shallit, Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada shallit@graceland.uwaterloo.ca URL = http://math.uwaterloo.ca/~shallit/ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - From: Chris Hillman Newsgroups: sci.math.research Subject: Re: "initial periodicity" in characteristics? Date: 5 Mar 1999 03:30:09 -0600 On Sun, 28 Feb 1999, TwoBirds wrote: > I've noticed by numerical calculation that, to more than 33,000 digits, > the characteristic of pi is > c1c2c3... = SSSSSSSSS... (at least 293 S's) > where S=00000010000001...000000100000001 (113 digits), > i.e., each S is 15 repetitions of 0000001, followed by 00000001. > > (The characteristic of a real number x is the binary string c1c2c3..., > where ck = [(k+1)*x] - [k*x] - [x], k=1,2,3,... , and []=floor.) I see David Madore has already pointed out the continued fraction connection. I thought I'd just add that in slides from a talk, "Empires of Sturmian Shifts", available at my page http://www.math.washington.edu/~hillman/talks.html I sketch a connection between the phenomenon you mentioned and the so-called "chain codes" which arise in drawing "pixel approximations" to line segments on a computer screen, and to the "empire" phenomenon discovered by John H. Conway in connection with Penrose tilings. In the case at hand, you are looking at a hierarchical "natural parsing" of "Sturmian sequences" into long and short words (at each level of parsing). You drew attention above to the long and short words which occur at one level of the parsing for this particular slope, which as others have already noted, happen to give a particularly good rational approximation. These long and short words determine the periodic approximations, word frequences, chain codes, kingdoms and just about everything else one can ask about Sturmian sequences! (The empire of a word w in a shift space X is the configuration of words which are forced by the occurrence of w in the sense that every sequence from X in which w appears also contains the entire empire of w. The empires of X are in galois duality with its cylinder sets, for which see my expository page "What is a Concept?" In the case of Sturmian shifts, the empire of w consists (with a trivial exception) of the smallest kingdom (a special word) containing w, surrounded by an infinite quasiperiodic pattern of strictly smaller kingdoms. This is in strong contrast to shifts of finite type or "topological Markov chains", where the empires are always finite.) There is much more which can be said, e.g. Sturmian shifts equipped with a "substitution rule" arising from a "composition" of a related periodic tiling called the oblique tiling are exactly the shifts which are defined by some line with quadratic irrational slope, and "noble" slopes have the slowest growth in the length of the words arising from the natural parsing, etc., etc. This whole subject can be summed up by saying the number theory and geometry of the classical "slow" continued fraction algorithm and the dynamical and combinatorial theory of Sturmian shifts is essentially the same thing. (See another talk, "Multidimensional Continued Fractions I", on the page cited above.) This subject has many beautiful and unexpected connections with apparently related ideas. On of my favorites is Conway's "rational tangles" and the "cutting sequence" for geodesics on the hyperbolic plane (they "cut across" the boundaries of a certain tiling; put another way, they define a sort of billiards game in a moduli space related to the moduli space of elliptic curves), for which see a recent thread on sci.physics.research. Monstrous moonshine (Conway again!) might come in somewhere about here... I should mention that things quickly get more complicated even in two dimensions (finding rational approximations to lines in R^3)-- this is connected to the well known difficulty of constructing a really good multidimensional analogue of the classical continued fraction algorithm. Nonetheless many (but by no means all) features of the above picture carry over. And the golden ratio and its well known connection to the Penrose tilings are highly relevant! (You used the word "characteristic", which leads me to guess you might already know about the papers by de Bruijn and others developing some of the one dimensional theory as an analogue to the algebraic and geometric theory of Penrose tilings.) See http://www-igm.univ-mlv.fr/~berstel for a recent review paper on the combinatorics of Sturmian words which surveys ideas part of the literature on Sturmian sequences. I can provide some additional references upon request. Chris Hillman