Sturmian numeration systems and decompositions to palindromes

DOI10.1016/J.EJC.2018.04.003MaRDI QIDQ1750221zbMATH OpenOpenAlexWikidataFDO

Authors Anna Frid

Publication date 18 May 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Ostrowski numeration system palindrome palindromic length Sturmian word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We extend the classical Ostrowski numeration systems, closely related to Sturmian words, by allowing a wider range of coefficients, so that possible representations of a number

n

better reflect the structure of the associated Sturmian word. In particular, this extended numeration system helps to catch occurrences of palindromes in a characteristic Sturmian word and thus to prove for Sturmian words the following conjecture stated in 2013 by Puzynina, Zamboni and the author: If a word is not periodic, then for every

Q > 0

it has a prefix which cannot be decomposed to a concatenation of at most

Q

palindromes.

Review text

Given a finite word \(w\), one can always find a decomposition of \(w\) in factors that are all palindromes. Indeed, since the single letters are palindromes, a word of length \(n\) has a palindromic decomposition into at most \(n\) palindormes. If one takes an infinite word \(x\), a natural question is to determine if there exists an integer \(k\) such that every finite prefix of \(x\) can be decomposed in at most \(k\) palindromes. The author, together with \textit{S. Puzynina} and \textit{L. Zamboni}, conjectured in [Adv. Appl. Math. 50, No. 5, 737--748 (2013; Zbl 1285.68133)] that if an infinite word \(x\) is not periodic, then for every integer \(k\) there exists a prefix of \(x\) that cannot be decomposed in at most \(k\) palindromes. In the same paper, it was proved that this conjecture holds true for words that do not contain powers of arbitrary order as factors. This class includes Sturmian words whose slope has bounded partial quotients, and it is therefore natural to ask if the conjecture holds true for all Sturmian words. Using an extension of the classical Ostrowski numeration systems, the author answers this question in the affirmative.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Sturmian numeration systems and decompositions to palindromes

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