Another Way to Lower the Bound for Distinct Squares
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918362994442240 |
|---|---|
| author | Tomita, Eitatsu I, Tomohiro |
| author_facet | Tomita, Eitatsu I, Tomohiro |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12711 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Another Way to Lower the Bound for Distinct Squares Tomita, Eitatsu I, Tomohiro Discrete Mathematics 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)$. |
| title | Another Way to Lower the Bound for Distinct Squares |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2602.12711 |