Another Way to Lower the Bound for Distinct Squares
Abstract
A square is a word of the form $xx$ for a non-empty word $x$. Brlek and Li [Comb. Theory, 2025] proved that the number of distinct squares in a word $w$ of length $n$ is at most $n - σ$, where $σ$ is the number of letters used in $w$. The same authors extended the proof to lower the upper bound to $n - Θ(\log n)$ in [WORDS, 2023]. In this paper, we present another proof to obtain the same bound $n - Θ(\log n)$.
Fields of Study & Subjects
semigroups and automata theory
Algorithms and Data Compression
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 13 February 2026
- Language
- EN
- Document type
- Preprint