×

Exchange of three intervals: substitutions and palindromicity. (English) Zbl 1368.68276

An exchange of \(k\geq2\) intervals with permutation \(\pi\) is a bijection \(T:J\rightarrow J\), where \(J\) is a semi-closed interval, there is a partition \(J=J_{0}\cup\cdots\cup J_{k-1}\) of \(J\) into a disjoint union of semi-closed subintervals satisfying \(J_{0}<J_{1}<\cdots<J_{k-1}\) (i.e., each value in \(J_{i-1}\) is smaller than each value in \(J_{i}\)), and there exist numbers \(c_{0},\ldots,c_{k-1}\) such that \(T( x) =x+c_{i}\) for \(x\in J_{i}\); \(\pi\) is a permutation of \(\{0,1,\ldots,k-1\}\) such that \(T(J_{i})<T(J_{i^{\prime}})\) for \(\pi( i) <\pi( i^{\prime }) \) (determined by the order of the intervals \(T( J_{i}) \)). \(T\) is a symmetric interval exchange if \(\pi\) is the permutation \(i\mapsto k-i-1\). The orbit \(\rho,T( \rho) ,T^{2}( \rho) ,\ldots\) of a point \(\rho\in J\) can be coded by an infinite word \(u_{\rho }=u_{0}u_{1}u_{2}\cdots\) over the alphabet \(\{0,1,\dots,k-1\}\) where \(u_{n}=i\) if \(T^{n}( \rho) \in J_{i}\). If for every \(\rho\in J\) and for every \(n\in N\) the word \(u_{\rho}\) contains the maximum possible number \((k-1)n+1\) of distinct factors of length \(n,\) then the transformation \(T\) and the word \(u_{\rho}\) are said to be non-degenerate.
The paper deals with the so-called class-\(P\) conjecture with respect to purely morphic words coding symmetric non-degenerate 3-interval exchange transformations. Such words are known to contain infinitely many palindromes. The class \(P\) consists of all morphisms \(\varphi\) such that there exists a palindrome \(p\) such that for every \(a\in A\) one has \(\varphi( a) =pp_{a}\) for some palindrome \(p_{a}\). The main result states that if an infinite word \(u\) coding a non-degenerate 3-interval exchange transformation \(T\) with permutation \((321)\) is a fixed point of a primitive morphism \(\xi\) then \(\xi\) or \(\xi^{2}\) is a conjugate of a morphism from the class \(P\).
A morphism \(\varphi\) is primitive if, for some \(k\geq1\), for any pair of symbols \(a\), \(b\), \(\varphi^{k}( a) \) contains \(b\). The morphisms \(\varphi\), \(\psi\) are conjugates if there exists a word \(w\) such that, for all letters \(a\), \(w\varphi( a) =\psi( a) w\) or, for all \(a\), \(\varphi( a) w=w\psi( a) \).

MSC:

68R15 Combinatorics on words
37B10 Symbolic dynamics
Full Text: DOI

References:

[1] Adamczewski, B., Codages de rotations et phénomènes d’autosimilarité, J. Théor. Nombres Bordeaux, 14, 351-386 (2002) · Zbl 1113.37003
[2] P. Ambrož, L. Háková, E. Pelantová, Properties of 3iet preserving morphisms and their matrices, in Proceedings WORDS 2007, 2007, pp. 18-24.; P. Ambrož, L. Háková, E. Pelantová, Properties of 3iet preserving morphisms and their matrices, in Proceedings WORDS 2007, 2007, pp. 18-24.
[3] Ambrož, P.; Masáková, Z.; Pelantová, E., Morphisms fixing words associated with exchange of three intervals, RAIRO-Theor. Inform. Appl., 44, 3-17 (2010) · Zbl 1186.68342
[4] Arnoux, P.; Berthé, V.; Masáková, Z.; Pelantová, E., Sturm numbers and substitution invariance of 3iet words, Integers, 8 (2008), Article A14 · Zbl 1202.11021
[5] Baláži, P.; Masáková, Z.; Pelantová, E., Characterization of substitution invariant words coding exchange of three intervals, Integers, 8 (2008), Article A20 · Zbl 1210.68078
[6] A. Blondin Massé, S. Brlek, S. Labbé, Palindromic lacunas of the Thue-Morse word, in Proc. GASCom 2008, 2008, pp. 53-67.; A. Blondin Massé, S. Brlek, S. Labbé, Palindromic lacunas of the Thue-Morse word, in Proc. GASCom 2008, 2008, pp. 53-67.
[7] Blondin Massé, A.; Brlek, S.; Labbé, S.; Vuillon, L., Palindromic complexity of codings of rotations, Theoret. Comput. Sci., 412, 6455-6463 (2011) · Zbl 1227.68084
[8] Ferenczi, S.; Holton, C.; Zamboni, L. Q., Structure of three-interval exchange transformations II: a combinatorial description of the tranjectories, J. Anal. Math., 89, 239-276 (2003) · Zbl 1130.37324
[9] Ferenczi, S.; Zamboni, L. Q., Languages of \(k\)-interval exchange transformations, Bull. Lond. Math. Soc., 40, 705-741 (2008) · Zbl 1147.37008
[10] Fogg, N. P., (Substitutions in Arithmetics, Dynamics and Combinatorics. Substitutions in Arithmetics, Dynamics and Combinatorics, Lecture notes in mathematics, vol. 1794 (2002), Springer) · Zbl 1014.11015
[11] Hof, A.; Knill, O.; Simon, B., Singular continuous spectrum for palindromic Schrödinger operators, Comm. Math. Phys., 174, 149-159 (1995) · Zbl 0839.11009
[12] Keane, M., Interval exchange transformations, Math. Z., 141, 25-31 (1975) · Zbl 0278.28010
[13] Labbé, S., A counterexample to a question of Hof, Knill and Simon, Electron. J. Combin., 21 (2014) · Zbl 1299.68045
[14] Labbé, S.; Pelantová, E., Palindromic sequences generated from marked morphisms, European J. Combin., 51, 200-214 (2016) · Zbl 1321.05006
[15] Lothaire, M., (Combinatorics on Words. Combinatorics on Words, Encyclopaedia of Mathematics and its Applications, vol. 17 (1983), Addison-Wesley: Addison-Wesley Reading, Mass), Reprinted in the Cambridge Mathematical Library, Cambridge University Press, Cambridge UK, 1997 · Zbl 0514.20045
[16] Lothaire, M., (Algebraic Combinatorics on Words. Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, no. 90 (2002), Cambridge University Press) · Zbl 1001.68093
[17] Masáková, Z.; Pelantová, E.; Starosta, Š., Interval exchange words and the question of Hof, Knill, and Simon, (Proceedings of DLT 2015, Liverpool. Proceedings of DLT 2015, Liverpool, LNCS, vol. 9168 (2015)), 377-388 · Zbl 1434.68386
[18] Masáková, Z.; Pelantová, E.; Starosta, Š., Itineraries induced by exchange of three intervals, Acta Polytech., 56, 462-471 (2016)
[19] Mignosi, F.; Séébold, P., Morphismes sturmiens et règles de Rauzy, J. Théor. Nombres Bordeaux, 5, 221-233 (1993) · Zbl 0797.11029
[20] Peng, L.; Tan, B., Sturmian sequences and invertible substitutions, Discrete Math. Theor. Comput. Sci., 13, 63-68 (2011) · Zbl 1283.68276
[21] Queffélec, M., (Substitution Dynamical Systems—Spectral Analysis. Substitution Dynamical Systems—Spectral Analysis, Lecture Notes in Mathematics, vol. 1294 (2010), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1225.11001
[22] G. Rauzy, Une généralisation du développement en fraction continue, in Séminaire Delange-Pisot-Poitou, 18e année: 1976/77, Théorie des nombres, Fasc. 1, Secrétariat Math., Paris, 1977, Exp. No. 15, 16.; G. Rauzy, Une généralisation du développement en fraction continue, in Séminaire Delange-Pisot-Poitou, 18e année: 1976/77, Théorie des nombres, Fasc. 1, Secrétariat Math., Paris, 1977, Exp. No. 15, 16. · Zbl 0369.28015
[23] Rauzy, G., Échanges d’intervalles et transformations induites, Acta Arith., 34, 315-328 (1979) · Zbl 0414.28018
[24] Rigo, M.; Salimov, P.; Vandomme, E., Some properties of abelian return words, J. Integer Seq., 16, 21 (2013), Article 13.2.5 · Zbl 1297.68195
[25] Séébold, P., On the conjugation of standard morphisms, Theoret. Comput. Sci., 195, 91-109 (1998) · Zbl 0981.68104
[26] Sinai, Y. G., Introduction to Ergodic Theory (Russian) (1973), Erevan State University, English translation: Mathematical Notes, Princeton Univ. Press, 1977
[27] Tan, B., Mirror substitutions and palindromic sequences, Theoret. Comput. Sci., 389, 118-124 (2007) · Zbl 1143.68063
[28] Veech, W. A., Topological dynamics, Bull. Amer. Math. Soc., 83, 775-830 (1977) · Zbl 0384.28018
[29] Veech, W. A., Interval exchange transformations, J. Anal. Math., 33, 222-272 (1978) · Zbl 0455.28006
[30] Vuillon, L., A characterization of Sturmian words by return words, European J. Combin., 22, 263-275 (2001) · Zbl 0968.68124
[31] Vuillon, L., On the number of return words in infinite words constructed by interval exchange transformations, Pure Math. Appl. (PU.M.A.), 18, 345-355 (2007) · Zbl 1224.68069
[32] Yasutomi, S.-I., On Sturmian sequences which are invariant under some substitutions, (Number Theory and its Applications (Kyoto, 1997). Number Theory and its Applications (Kyoto, 1997), Dev. Math., vol. 2 (1999), Kluwer Acad. Publ: Kluwer Acad. Publ Dordrecht), 347-373 · Zbl 0971.11007
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.