DMMay 28

On abelian periodicity of purely morphic words

arXiv:2605.3030629.6
AI Analysis

This solves a natural variant of a classical problem in combinatorics on words for binary morphisms, extending known results to the abelian setting.

The paper characterizes binary morphisms that generate abelian periodic infinite words, providing a necessary and sufficient condition and an algorithmic bound for the purely abelian periodic case.

Deciding periodicity of infinite words generated by morphisms is a classical result in combinatorics on words from 80's by Harju, Linna and Pansiot. In this paper, we are interested in this question in the abelian setting. Two words are called \textit{abelian equivalent} if they contain the same numbers of occurrences of each letter. An infinite word $s$ is called \emph{ultimately abelian periodic} if it can be factorized as $s=uv_1v_2v_3\cdots$, where $v_i$'s are abelian equivalent words. If $u$ is empty, then $s$ is called \emph{purely abelian periodic}. We provide the following characterization of binary morphisms generating abelian periodic words: A word generated by a binary morphism $f$ is abelian periodic if and only if either it is periodic or there exist an integer $K$ and words $u$, $v$, $u'$, $v'$ such that $f^K(a) = uv$, $f^K(b) = u'v'$, $u\sim_{ab} u'$, and $vu$ and $v'u'$ are abelian periodic with abelian equivalent periods. For the case of the purely abelian periodic words, we also provide an upper bound on $K$ which makes the obtained characterization algorithmic.

Foundations

The foundational work for this paper's niche, ranked by how specifically the neighbourhood builds on it — not by global fame.

Your Notes