Subword enumeration up to stack-sorting equivalence
This work provides a new interdisciplinary link between stack-sorting of permutations and combinatorics on words, but the results are primarily theoretical and incremental.
The paper extends the stack-sorting map from permutations to finite words, introducing tortoise and hare operations that generalize abelian complexity functions for infinite sequences. Applied to the paperfolding and Thue-Morse words, it reveals structural properties and connects to prior work on special factors of the Thue-Morse word.
Defant and Kravitz introduced generalizations of West's stack-sorting map $s$ from permutations to finite words. This raises questions as to how such generalizations could be applied in the field of combinatorics on words. The Defant-Kravitz generalizations of $s$ depend on how repeated occurrences of the same character within a word may be repositioned, according to their $\textsf{tortoise}$ and $\textsf{hare}$ operations. As demonstrated in this paper, these operations provide a natural way of extending abelian complexity functions for infinite sequences, in a way that gives light to structural properties associated with infinite words. We apply these new ideas to two famous infinite words: the paperfolding word and the Thue-Morse word. In the case of the Thue-Morse word, we discover an interesting connection to the previous work of several authors, such as de Luca and Varricchio, on the ``special'' factors of the Thue-Morse word. This may be seen as providing a basis for a new and interdisciplinary area linking the combinatorics about the stack-sorting of permutations with the field of combinatorics on words.