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