The Tight Upper Bound on the Number of Distinct Squares in Circular Words
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32084
curl -X POST /api/v1/records/arxiv/2609.32084/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32084/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'