On k-Maximal Submonoids, with Applications in Combinatorics on Words
share
We define the notion of a k-maximal submonoid. A submonoid M is k-maximal if there does not exist another submonoid generated by at most k words containing M. We prove that the intersection of two 2-maximal submonoids is either the empty word or a submonoid generated by one primitive word. As a consequence, for every submonoid M generated by two words that do not commute, there exists a unique 2-maximal submonoid containing M. We aim to show that this algebraic framework can be used to introduce a novel approach in combinatorics on words. We call primitive pairs those pairs of nonempty words that generate a 2-maximal submonoid. Primitive pairs therefore represent an algebraic generalization of the classical notion of a primitive word. As an immediate consequence of our results, we have that for every pair of nonempty words {x,y} such that xy≠ yx there exists a unique primitive pair {u,v} such that x and y can be written as concatenations of copies of u and v. We call the pair {u,v} the binary root of the pair {x,y}, in analogy with the classical notion of root of a single word. For a single word w, we say that {x,y} is a binary root of w if w can be written as a concatenation of copies of x and y and {x,y} is a primitive pair. We prove that every word w has at most one binary root {x,y} such that |x|+|y|<√(|w|). That is, the binary root of a word is unique provided the length of the word is sufficiently large with respect to the size of the root. Our results can also be compared to previous approaches that investigate pseudo-repetitions. Finally, we discuss the case of infinite words, where the notion of a binary root represents a new refinement in the classical dichotomy periodic/aperiodic.
READ FULL TEXT