Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence

The cyclic complexity \(c_x(n)\) of an infinite word \(x\) was defined in [\textit{J. Cassaigne} et al., J. Comb. Theory, Ser. A 145, 36--56 (2017; Zbl 1369.68271)] as the number of length-\(n\) factors of \(x\), where factors that are the same, up to cyclic shift, are only counted once. Unlike the classical subword complexity, it is not obliged to be \(k\)-regular if the word is \(k\)-automatic. \textit{C. Krawchuk} and \textit{N. Rampersad} [Integers 18A, Paper A12, 13 p. (2018; Zbl 1429.68203)] proved that nevertheless, the cyclic complexity of the classical \(2\)-automatic Thue-Morse word \(t\) is \(2\)-regular and can be described by a bulky linear representation. That linear representation does not directly allow to establish the asymptotic upper and lower bounds for \(c_t(n)\) which were just conjectured in the initial paper: \N\[ \N\lim \sup c_t(n)/n = 2 \mbox{ and } \lim \inf c_t(n)/n = 4/ 3.\N\] \NHere, the author proves these bounds by induction, using both a careful case study and automated proofs with Walnut software.

Recommendations

Cites work

This page was built for publication: Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence

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