Upper limit found for repeating patterns in circular sequences
The Tight Upper Bound on the Number of Distinct Squares in Circular Words
Data Structures and Algorithms
Summary
This paper studies patterns called squares, which are repeated sections like "xx" in circular strings that loop around. The authors found the exact maximum number of different squares you can have in a string of length n arranged in a circle—up to one and a half times the string length. They used known mathematical connections involving graph structures to prove this limit. Their result matches the best known examples, showing the bound is tight.
What this means in practice
- •For software engineers: Optimize string algorithms by understanding the maximum repetition complexity in circular data structures.
- •For bioinformatics teams: Estimate repetitive pattern limits in circular DNA sequences for genome analysis.
A theory result. No direct application yet.
Authors
Rikuya Hamai
Abstract
A square is a word $xx$, where $x$ is nonempty. We show that a circular word of length $n$ contains at most $\lfloor 3n/2 \rfloor$ 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.