Standard words and solutions of the word equation X₁^2 X_n^2=(X₁ X_n)^2

DOI10.1016/J.JCTA.2020.105340MaRDI QIDQ2221815zbMATH OpenOpenAlexFDO

Authors Ville Salo, Aleksi Saarela

Publication date 2 February 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.14657

zbMATH Keywords

optimal squareful wordstandard wordSturmian wordsymbolic square root mapword equation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Abstract: We consider solutions of the word equation $X_1^{2}dotsm{X}_n^2=(X_{1}dotsm{X}_n{)}^2$ such that the squares $X_i^2$ are minimal squares found in optimal squareful infinite words. We apply a method developed by the second author for studying word equations and prove that there are exactly two families of solutions: reversed standard words and words obtained from reversed standard words by a simple substitution scheme. A particular and remarkable consequence is that a word $w$ is a standard word if and only if its reversal is a solution to the word equation and $gcd(|w|,|w{|}_1)=1$. This result can be interpreted as a yet another characterization for standard Sturmian words. We apply our results to the symbolic square root map $sqrtcdot$ studied by the first author and M. A. Whiteland. We prove that if the language of a minimal subshift $Omega$ contains infinitely many solutions to the word equation, then either $Omega$ is Sturmian and $sqrtcdot$-invariant or $Omega$ is a so-called SL-subshift and not $sqrtcdot$-invariant. This result is progress towards proving the conjecture that a minimal and $sqrtcdot$-invariant subshift is necessarily Sturmian.

Review text

The paper deals with the solutions of the word equation \(X_1^2\cdots X_n^2=(X_1\cdots X_n)^2 \). The standard words that are considered in the article are a generalization of Fibonacci words. It is proved ``that there are exactly two families of solutions: reversed standard words and words obtained from reversed standard words by a simple substitution scheme. A particular and remarkable consequence is that a word \(w\) is a standard word if and only if its reversal is a solution to the word equation and \(\gcd(|w|, |w|_1) = 1.\) This result can be interpreted as a yet another characterization for standard Sturmian words. Based on these results, the authors make a ``progress towards proving the conjecture that a minimal and \(\sqrt{\cdot}\)-invariant subshift is necessarily Sturmian.

Recommendations

• A square root map on Sturmian words (extended abstract)
• A square root map on Sturmian words
• Two-variable word equations
• scientific article; zbMATH DE number 1577999
• More on the dynamics of the symbolic square root map (extended abstract)

Cites work

• A square root map on Sturmian words
• An optimal bound on the solution sets of one-variable word equations and its consequences
• Everywhere -repetitive sequences and Sturmian words
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Introducing privileged words: privileged complexity of Sturmian words
• More on the dynamics of the symbolic square root map
• One-variable word equations and three-variable constant-free word equations
• Studying word equations by a method of weighted frequencies
• Transcendence of Sturmian or morphic continued fractions
• Word equations where a power equals a product of powers
• Word equations with \(k\)th powers of variables

Cited in

(2)

• More on the dynamics of the symbolic square root map
• A square root map on Sturmian words (extended abstract)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Standard words and solutions of the word equation \(X_1^2\cdots X_n^2=(X_1\cdots X_n)^2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221815)