Distinct Squares in Circular Words
Abstract
A circular word, or a necklace, is an equivalence class under conjugation of a word. A fundamental question concerning regularities in standard words is bounding the number of distinct squares in a word of length $n$. The famous conjecture attributed to Fraenkel and Simpson is that there are at most $n$ such distinct squares, yet the best known upper bound is $1.84n$ by Deza et al. [Discr. Appl. Math. 180, 52-69 (2015)]. We consider a natural generalization of this question to circular words: how many distinct squares can there be in all cyclic rotations of a word of length $n$? We prove an upper bound of $3.14n$. This is complemented with an infinite family of words implying a lower bound of $1.25n$.
- Publication:
-
arXiv e-prints
- Pub Date:
- August 2017
- DOI:
- arXiv:
- arXiv:1708.00639
- Bibcode:
- 2017arXiv170800639A
- Keywords:
-
- Computer Science - Formal Languages and Automata Theory
- E-Print:
- to appear in SPIRE 2017