Shallit's factor-complexity conjecture for Thue-Morse-like sequences
Shallit's factor-complexity conjecture for Thue-Morse-like sequences
Let , and let be the Thue-Morse-like sequence obtained from the family described in the source. For a binary sequence, its factor complexity is the number of distinct factors of length ; its first difference is . Shallit's factor-complexity conjecture. For sufficiently large , the first difference of the factor complexity of takes only the values
This conjecture extends the known cases for the Thue-Morse sequence, the Fibonacci-Thue-Morse sequence, and the Allouche--Johnson sequence. The source gives no resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Lubomíra Dvořáková, Savinien Kreczman and Edita Pelantová, “On two conjectures of Shallit about Thue-Morse-like sequences”, arXiv:2506.04407 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.