×

Substitution invariant Sturmian bisequences. (English) Zbl 0978.11005

A doubly infinite word over the two-element alphabet \(\{0,1\}\) is called Sturmian if on its position we have either \(\lfloor (n+1+k)\alpha+\rho\rfloor-\lfloor (n+k)\alpha+\rho\rfloor- \lfloor \alpha\rfloor\) or \(\lceil (n+1+k)\alpha+\rho\rceil-\lceil (n+k)\alpha+\rho\rceil- \lceil\alpha\rceil\) for each \(n\in{\mathbb{Z}}\) and some \(k\in{\mathbb{Z}}\), where \(\alpha\) is irrational and \(\rho\) real. A right-sided infinite word \(y\) is Sturmian if there exists a left-sided infinite word \(y^\prime\) such that \(y^\prime y\) is Sturmian. A substitution \(f\) (i.e. a map over the free monoid over \(\{0,1\}\) preserving concatenation) is Sturmian if \(f(w)\) is a right-sided infinite Sturmian whenever \(w\) is. The author proves a condition on \(\alpha\) and \(\rho\) equivalent to the fact that a Sturmian bisequence is fixed (up to a shift of the indices of its terms) by a Sturmian substitution.

MSC:

11B83 Special sequences and polynomials
11B85 Automata sequences
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML EMIS

References:

[1] Bang, T., On the sequence [nα], Math. Scand.5 (1957), 69-76. · Zbl 0084.04401
[2] Beatty, S., Problem 3173, Amer. Math. Monthly33 (1926) 159. Solutions, ibid., 34 (1927) 159. · JFM 53.0198.06
[3] Berstel, J., Recent results on Sturmian words, in: J. Dassow (Ed.), Proc. DLT’95, World Scientific, Singapore (1996). · Zbl 1096.68689
[4] Berstel, J. and Séébold, P., A characterization of Sturmian morphisms, (1993), 281-290. · Zbl 0925.11026
[5] Berstel, J. et Séébold, P., Morphismes de Sturm, Bull. Belg. Math. Soc.1 (1994), 175-189. · Zbl 0803.68095
[6] Borwein, J.M. and Borwein, P.B., On the generating function of the integer part [nα + γ], J. Number Theory43 (1993), 293-318. · Zbl 0778.11039
[7] Bowman, D., Approximation of [nα + s and the zero of {nα + s}, J. Number Theory50 (1995), 128-144. · Zbl 0823.11037
[8] Brown, T.C., Descriptions of the characteristic sequence of an irrational, Canad. Math. Bull.36 (1993), 15-21. · Zbl 0804.11021
[9] Connell, I.G., Some properties of Beatty sequences I, Canad. Math. Bull.2 (1959), 190-197. · Zbl 0092.27801
[10] Connell, I.G., Some properties of Beatty sequences II, Canad. Math. Bull.3 (1960), 17-22. · Zbl 0090.03203
[11] Coven, E. and Hedlund, G.A., Sequences with minimal block growth, Math. Systems Theory7 (1973), 138-153. · Zbl 0256.54028
[12] Crisp, D., Moran, W., Pollington, A. and Shiue, P., Substitution invariant cutting sequences, J. Théorie des Nombres de Bordeaux5 (1993), 123-137. · Zbl 0786.11041
[13] Fraenkel, A.S., Complementary systems of integers, Amer. Math. Monthly84 (1977), 114-115. · Zbl 0359.10048
[14] Fraenkel, A.S., Levitt, J. and Shimshoni, M., Characterization of the set of values f(n) = [nα], Discrete Math.2 (1972), 335-345. · Zbl 0246.10005
[15] Fraenkel, A.S., Mushkin, M. and Tassa, U., Determination of nθby its sequence of differences, Canad. Math. Bull.21 (1978), 441-446. · Zbl 0401.10018
[16] Fraenkel, A.S. and Holzman, R., Gap problems for integer part and fractional part sequences, J. Number Theory50 (1995), 66-86. · Zbl 0822.11021
[17] Graham, R.L., Covering the positive integers by disjoint sets of the form {nα + β]: n = 1, 2, ... }, J. Comb. Theor. Ser. A 15 (1973), 354-358. · Zbl 0279.10042
[18] Ito, S., On a dynamical system related to sequences nx + y - L(n - 1)x + y], Dynamical Systems and Related Topics, Nagoya (1990), 192-197.
[19] Ito, S. and Yasutomi, S., On continued fractions, substitutions and characteristic sequences, Japan. J. Math.16 (1990), 287-306. · Zbl 0721.11009
[20] Komatsu, T., On the characteristic word of the inhomogeneous Beatty sequence, Bull. Aust. Math. Soc.51 (1995), 337-351. · Zbl 0829.11012
[21] Komatsu, T., The fractional part of nθ + ϕ and Beatty sequences, J. Théorie des Nombres de Bordeaux7 (1995), 387-406. · Zbl 0849.11027
[22] Komatsu, T., A certain power series associated with a Beatty sequence, Acta Arith.LXXVI (1996),109-129. · Zbl 0858.11013
[23] Komatsu, T. and Poorten, A. J. van der, Substitution invariant Beatty sequences, Japan. J. Math.22 (1996), 349-354. · Zbl 0868.11015
[24] Mignosi, F. et Séébold, P., Morphismes sturmiens et règles de Rauzy, J. Théorie des Nombres de Bordeaux5 (1993), 221-233. · Zbl 0797.11029
[25] Morse, M. and Hedlund, G.A., Symbolic Dynamics, Amer. J. Math.60 (1938), 815-866. · JFM 64.0798.04
[26] Morse, M. and Hedlund, G.A., Symbolic Dynamics II. Sturmian trajectories, Amer. J. Math.62 (1940), 1-42. · JFM 66.0188.03
[27] Parvaix, B., Propriétés d’invariance des mots sturmiens, J. Théorie des Nombres de Bordeaux9 (1997), 351-369. · Zbl 0904.11008
[28] Rosenblatt, J., The sequence of greatest integers of an arithmetic progression, J. Lond. Math. Soc.17 (1978), 213-218. · Zbl 0383.10036
[29] Stolarsky, K.B., Beatty sequences, continued fractions and certain shift operators, Canad. Math. Bull.19 (1976), 473-482. · Zbl 0359.10028
[30] Tijdeman, R., On disjoint pairs of Sturmian bisequences, Mathematical Institute, Leiden University, Report W96-02 (1996). · Zbl 0862.68085
[31] Tijdeman, R., On complementary triples of Sturmian bisequences, Indag. Math.7 (1996), 419-424. · Zbl 0862.68085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.