arXiv:2609.32084 · v3

An Asymptotically Tight Bound on the Number of Distinct Squares in Circular Words

首次提交 2026-09-26 07:44

版本更新 2026-11-12 06:01

雷达观测 2026-11-13 14:16

摘要

A square is a word $xx$ with $x$ nonempty. We study the maximum number of distinct squares occurring in the rotations of a word of length $n$. Amit and Gawrychowski (SPIRE 2017) obtained an upper bound of $3.14n$. Charalampopoulos et al. (CPM 2026) improved the upper bound to $\lceil9n/5\rceil$ and gave a binary construction with at least $3n/2-O(\sqrt n)$ distinct squares for infinitely many $n$. They conjectured an upper bound of $3n/2$. Li and Song subsequently reported an improved upper bound of $5n/3$. We prove that a circular word of length $n$ containing $σ$ distinct letters has at most $\lfloor3(n-σ)/2\rfloor$ distinct squares. This settles the conjecture and establishes that the leading coefficient $3/2$ is optimal even for binary words. Our proof groups squares by their Lyndon roots and, for primitive words, uses a weighted count of circuits in the Rauzy graphs of the bi-infinite repetition of the word.

作者备注：13 pages, 2 figures. Revised title and exposition, clarified proofs, and updated references. The main theorem gives the alphabet-sensitive upper bound $\lfloor 3(n-σ)/2\rfloor$, where $σ$ is the number of distinct letters