An abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain at most Θ(n2) distinct factors, and there exist words of length n containing Θ(n2) distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length n grows quadratically with n. More precisely, we say that an infinite word w is abelian-square-rich if, for every n, every factor of w of length n contains, on average, a number of distinct abelian-square factors that is quadratic in n; and uniformly abelian-square-rich if every factor of w contains a number of distinct abelian-square factors that is proportional to the square of its length. Of course, if a word is uniformly abelian-square-rich, then it is abelian-square-rich, but we show that the converse is not true in general. We prove that the Thue-Morse word is uniformly abelian-square-rich and that the function counting the number of distinct abelian-square factors of length 2. n of the Thue-Morse word is 2-regular. As for Sturmian words, we prove that a Sturmian word sα of angle α is uniformly abelian-square-rich if and only if the irrational α has bounded partial quotients, that is, if and only if sα has bounded exponent.

### Abelian-square-rich words

#### Abstract

An abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain at most Θ(n2) distinct factors, and there exist words of length n containing Θ(n2) distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length n grows quadratically with n. More precisely, we say that an infinite word w is abelian-square-rich if, for every n, every factor of w of length n contains, on average, a number of distinct abelian-square factors that is quadratic in n; and uniformly abelian-square-rich if every factor of w contains a number of distinct abelian-square factors that is proportional to the square of its length. Of course, if a word is uniformly abelian-square-rich, then it is abelian-square-rich, but we show that the converse is not true in general. We prove that the Thue-Morse word is uniformly abelian-square-rich and that the function counting the number of distinct abelian-square factors of length 2. n of the Thue-Morse word is 2-regular. As for Sturmian words, we prove that a Sturmian word sα of angle α is uniformly abelian-square-rich if and only if the irrational α has bounded partial quotients, that is, if and only if sα has bounded exponent.
##### Scheda breve Scheda completa Scheda completa (DC)
2017
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11697/112347`
• ND
• 6
• 5