PreprintarXiv licencearXiv
The Tight Upper Bound on the Number of Distinct Squares in Circular Words
Abstract
A square is a word xx, where x is nonempty. We show that a circular word of length n contains at most ⌊ 3n/2 ⌋ distinct squares of length at most n. The proof combines known results relating squares to circuits in Rauzy graphs. The coefficient 3/2 agrees with the known lower bound.
Related
- Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
- Tiling circular n-boards with squares and (1,1)-fences
- Tight upper bound on dGH(S1,S2k+1): GPT's short proof
- Bounds on the number of squares in recurrence sequences: y0=b2 (II)
- An elementary proof of a tight Δ+1 bound for the additive chromatic number
BibTeX
@misc{hamai2026tight,
title = {{The Tight Upper Bound on the Number of Distinct Squares in Circular Words}},
author = {Rikuya Hamai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.32084},
eprint = {2609.32084},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32084},
}
RIS
TY - UNPB
TI - The Tight Upper Bound on the Number of Distinct Squares in Circular Words
AU - Rikuya Hamai
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.32084
UR - https://arxiv.org/abs/2609.32084
AB - A square is a word xx, where x is nonempty. We show that a circular word of length n contains at most ⌊ 3n/2 ⌋ distinct squares of length at most n. The proof combines known results relating squares to circuits in Rauzy graphs. The coefficient 3/2 agrees with the known lower bound.
ER -