Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > A Square Root Map on Sturmian ...

A Square Root Map on Sturmian Words

Jarkko Peltomäki, Markus Whiteland, A Square Root Map on Sturmian Words. Electronic Journal of Combinatorics 24(1), 1–50, 2017.

Abstract:

We introduce a square root map on Sturmian words and study its properties. Given a Sturmian word of slope $\alpha$, there exists exactly six minimal squares in its language (a minimal square does not have a square as a proper prefix). A Sturmian word $s$ of slope $\alpha$ can be written as a product of these six minimal squares: $s = X_1^2 X_2^2 X_3^2 \cdots$. The square root of $s$ is defined to be the word $\sqrt{s} = X_1 X_2 X_3 \cdots$. The main result of this paper is that $\sqrt{s}$ is also a Sturmian word of slope $\alpha$. Further, we characterize the Sturmian fixed points of the square root map, and we describe how to find the intercept of $\sqrt{s}$ and an occurrence of any prefix of $\sqrt{s}$ in $s$. Related to the square root map, we characterize the solutions of the word equation $X_1^2 X_2^2 \cdots X_n^2 = (X_1 X_2 \cdots X_n)^2$ in the language of Sturmian words of slope $\alpha$ where the words $X_i^2$ are minimal squares of slope $\alpha$.

We also study the square root map in a more general setting. We explicitly construct an infinite set of non-Sturmian fixed points of the square root map. We show that the subshifts $\Omega$ generated by these words have a curious property: for all $w \in \Omega$ either $\sqrt{w} \in \Omega$ or $\sqrt{w}$ is periodic. In particular, the square root map can map an aperiodic word to a periodic word.

BibTeX entry:

@ARTICLE{jPeWh17a,
  title = {A Square Root Map on Sturmian Words},
  author = {Peltomäki, Jarkko and Whiteland, Markus},
  journal = {Electronic Journal of Combinatorics},
  volume = {24},
  number = {1},
  pages = {1–50},
  year = {2017},
  keywords = {sturmian word,standard word,optimal squareful word,word equation,continued fraction},
  ISSN = {1077-8926},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication