Improved Bounds on the Maximum Number of Distinct Squares in Circular Words

Charalampopoulos, Panagiotis; Mohamed, Manal; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz; Zuba, Wiktor

doi:10.4230/LIPIcs.CPM.2026.6

Improved Bounds on the Maximum Number of Distinct Squares in Circular Words

Panagiotis Charalampopoulos

King’s College London, UK Manal Mohamed

King’s College London, UK Jakub Radoszewski

University of Warsaw, Poland Wojciech Rytter

University of Warsaw, Poland Tomasz Waleń

University of Warsaw, Poland Wiktor Zuba

University of Warsaw, Poland

Abstract

We investigate the asymptotic growth of function $\mathsf{CS}(n)$ , which maps $n$ to the maximum number of distinct squares in a circular word of length $n$ (that is, the maximum number of distinct squares of length at most $n$ in a word $w w$ of length $2n$ ). We improve upon the lower bound of $1.25n$ established by Amit and Gawrychowski [SPIRE 2017] and the straightforward upper bound of $2n$ , which follows from the recent result of Brlek and Li [Comb. Theory, 2025] stating that there are fewer than $n$ squares in standard (i.e., non-circular) words of length $n$ . (Previously, Amit and Gawrychowski gave an upper bound of $3\frac{2}{15}n$ using a weaker upper bound on squares in standard words.) Specifically, we show that $\mathsf{CS}(n)\,\leq\,\left\lceil\,1.8n\,\right\rceil$ and that, for infinitely many $n$ , $\mathsf{CS}(n)\,\geq\,1.5n-\mathcal{O}(\sqrt{n})$ .

For the lower bound, we exploit the combinatorial structure of Fibonacci words to construct a family of square-rich circular words. For the upper bound, we exploit density properties of the starting positions of long squares, adapting an approach of Amit and Gawrychowski.

Keywords and phrases:

circular words, squares, repetitions

Funding:

Jakub Radoszewski: Supported by the Polish National Science Center, grant no. 2022/46/E/ST6/00463.

Copyright and License:

© Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter,
Tomasz Waleń, and Wiktor Zuba; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatorics on words

DOI:

10.4230/LIPIcs.CPM.2026.6

Event:

37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Editors:

Philip Bille and Nicola Prezza

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The study of square and symmetric fragments of words is central in combinatorics and algorithms on words. A square is a word of the form $u u$ for a word $u$ . Here, we focus on square fragments of circular words. That is, for a standard word $w$ , we study the square fragments that occur in any rotation of $w$ or, equivalently, the square fragments of $w w$ that are of length at most $|w|$ .

The earliest result concerning squares in words is the construction of square-free ternary words of all lengths by Thue [19]. The analogue of this problem for circular words is more intricate. Currie [4] showed that square-free circular words over the ternary alphabet exist for all lengths except for 5, 7, 9, 10, 14, and 17 using a computer-aided proof. Shur [16] later gave a computer-free proof that also implied an exponential (in the length) lower bound on the number of such words of any fixed length.

Let $\mathsf{SQ}(n)$ be the maximum number of distinct squares in a (standard) word of length $n$ . Fraenkel and Simpson [7] proved that $\mathsf{SQ}(n)<2n$ and conjectured that $\mathsf{SQ}(n)<n$ . The resolution of this conjecture took more than two decades. Milestone results include the upper bound of $2n-\log n$ due to Ilie [9], the upper bound of $\frac{11}{6}n$ due to Deza, Franek, and Thierry [5], and the upper bound of $1.5n$ due to Thierry [18]. Finally, Brlek and Li [3] confirmed the Fraenkel-Simpson conjecture using a graph-theoretic approach, establishing that $\mathsf{SQ}(n)<n$ .

Let $\mathsf{CS}(n)$ denote the maximum number of distinct squares in a circular word of length $n$ . The growth of $\mathsf{CS}(n)$ was first studied by Amit and Gawrychowski [1] who showed an upper bound of $3\frac{2}{15}n$ and a lower bound of $1.25n$ (for infinitely many $n$ ). Note that this work was published when the best known upper bound for standard squares was $\mathsf{SQ}(n)\leq\frac{11}{6}n$ . Further, observe that the number of squares of length at most $n$ in a word $w w$ is at most $\mathsf{SQ}(2|w|)$ . The result of Brlek and Li [3] thus implies that $\mathsf{CS}(n)\leq\mathsf{SQ}(2n)<2n$ .

Our results.

Here, we improve upon both the upper bound of $2n$ that follows from [3] and the lower bound of $1.25n$ from [1] for $\mathsf{CS}(n)$ . Specifically, we show that $\mathsf{CS}(n)\leq\left\lceil 1.8n\right\rceil$ for all $n$ and that $\mathsf{CS}(n)\geq 1.5n-\mathcal{O}(\sqrt{n})$ for infinitely many $n$ .

Our lower and upper bounds are presented in Section 3 and Section 4, respectively. Then, Section 5 discusses the limitations of our approach.

Discussion.

As we remark at the end of Section 4, the proof of the $3\frac{2}{15}n$ upper bound of Amit and Gawrychowski could be modified to yield an upper bound of $\left\lceil\frac{13}{7}n\right\rceil$ by incorporating the upper bound of $n$ for standard squares. However, the resulting argument remains technically involved. We establish a stronger upper bound of $\left\lceil 1.8n\right\rceil$ and also a (still stronger) upper bound of $\left\lceil\frac{11}{6}n\right\rceil$ which is considerably simpler.

2 Preliminaries

A word $u=u[0]\cdots u[n-1]$ is a sequence of length $|u|=n$ of letters from some alphabet. For any two integers $i,j\in[0\mathinner{.\,.}|u|)$ , $u[i\mathinner{.\,.}j]$ and $u[i\mathinner{.\,.}j+1)$ denote the fragment $u[i]\cdots u[j]$ if $i\leq j$ and the empty word otherwise. A fragment $u[0\mathinner{.\,.}j]$ is called a prefix of $u$ . A prefix of $u$ is called a proper prefix of $u$ if its length is smaller than $n$ . A fragment $u[i\mathinner{.\,.}n-1]$ is called a suffix of $u$ .

We say that integer $p\in[1\mathinner{.\,.}|u|]$ is a period of a word $u$ if $u[i]=u[i+p]$ for all $i\in[0\mathinner{.\,.}|u|-p)$ . We denote the smallest period of $u$ by $\mathrm{per}(u)$ . We say that $u$ is periodic if $\mathrm{per}(u)\leq\frac{1}{2}|u|$ ; otherwise $u$ is called non-periodic.

Lemma 1 (Periodicity Lemma [6]).

If a word $u$ has periods $p$ and $q$ such that $p+q\leq|u|+\gcd(p,q)$ , then $\gcd(p,q)$ is also a period of $u$ .

A word $u$ is called primitive if the equality $u=v^{k}$ for a positive integer $k$ implies that $k=1$ . Primitive words satisfy the following synchronization property that follows from the periodicity lemma: a primitive word $u$ occurs in $u^{2}$ only as a prefix and as a suffix.

For a word $u$ , for any integer $i\in[0\mathinner{.\,.}|u|)$ , we call $u[i\mathinner{.\,.}|u|)u[0\mathinner{.\,.}i)$ a rotation of $u$ .

For a word $w$ , we denote by $\mathbf{S}_{n}(w)$ the set of squares of length at most $n$ that occur $w$ . Thus, the set of squares of a circular word $w$ equals $\mathbf{S}_{n}(w^{2})$ , where $n=|w|$ .

Fibonacci words are defined by the recurrence

F_{0}=b,\quad F_{1}=a,\quad F_{t}=F_{t-1}F_{t-2}\text{ for }t\geq 2.

The number of distinct squares in the (standard) word $F_{n}$ is equal to $2|F_{n-2}|-2$ ; see [8]. As a warm-up, we show an exact bound on the number of squares in circular Fibonacci words.

Fact 2.

If $n\geq 2$ , $|\mathbf{S}_{|F_{n}|}(F_{n}F_{n})|=|F_{n}|-2$ .

Proof.

Every square in $F_{n}$ is a square of a rotation of some shorter Fibonacci word; see [10, Theorem 2.3]. The same holds for $F_{n}^{2}$ since $F_{n}^{2}$ is a prefix of the infinite Fibonacci word for $n\geq 3$ , and for $n\leq 2$ it can be easily verified.

For $n=2$ , we have $\mathbf{S}_{|F_{n}|}(F_{n}F_{n})=\emptyset$ as expected. Assume $n\geq 3$ . The set $\mathbf{S}_{|F_{n}|}(F_{n}^{2})$ does not contain $F_{0}^{2}=bb$ and $F_{n-1}^{2}$ (because $2|F_{n-1}|>|F_{n}|$ ). Let us show by induction that for all $k\in[1\mathinner{.\,.}n-2]$ , each rotation of $F_{k}^{2}$ occurs in $F_{n}^{2}$ . Correctness in the base cases of $n\in\{3,4\}$ can be easily checked. Assume that $n\geq 5$ and the property holds for $n-1$ . By the hypothesis, $F_{n-1}^{2}$ contains all rotations of $F_{k}^{2}$ for $k\in[1\mathinner{.\,.}n-3]$ . Since $n\geq 4$ , $F_{n-1}^{2}$ is a prefix of $F_{n}^{2}$ , so all these squares are also in $\mathbf{S}_{|F_{n}|}(F^{2}_{n})$ . Moreover, $F_{n}$ has a suffix $F_{n-2}$ and a prefix $F_{n-2}^{2}$ (since $n-2\geq 3$ ). Hence, $F_{n}^{2}$ has a fragment $F_{n-2}^{3}$ , so each rotation of $F_{n-2}^{2}$ occurs in $F_{n}^{2}$ .

In total, we obtain $|F_{1}|+|F_{2}|+\cdots+|F_{n-2}|=|F_{n}|-2$ squares. All these squares are different because each Fibonacci word is primitive. $\hfill\blacktriangleleft$

Example 3.

We have

\ F_{2}\,=\,{a\;b},\ F_{3}\,=\,{ab\;a},\ F_{4}\,=\,{aba\;ab},\ F_{5}\,=\,{% abaab\;aba},\ F_{6}\,=\,{abaababa\;abaab}.

For $F_{6}$ , we have

\mathbf{S}_{13}(F_{6})\,=\,\{a^{2},\,(ab)^{2},\,(ba)^{2},\,(aba)^{2},\,(aab)^{% 2},\,(baa)^{2},\ (abaab)^{2},\,(baaba)^{2}\},

and

\mathbf{S}_{13}(F_{6}^{2})\,=\,\mathbf{S}_{n}(F_{6})\cup\{(aabab)^{2},\,(ababa% )^{2},\,(babaa)^{2}\}.

In particular, $F_{6}$ has $8=2\,|F_{3}|-2$ distinct squares, while the circular $F_{6}$ contains $11=|F_{6}|-2$ distinct squares in total.

3 Lower Bound

We use Fibonacci words as building blocks. For any word $v$ of length at least two, let $\,\mathbf{cut}(v):=v[0\mathinner{.\,.}|v|-2)$ be the word obtained from $v$ by deleting its two last letters. Let $\mathbf{ex}(v)$ denote the word $v$ with the last two letter exchanged, that is, $\mathbf{ex}(v):=\,\mathbf{cut}(v)v[|v|-1]v[|v|-2]$ .

Example 4.

$\,\mathbf{cut}(abcde)=abc$ and $\mathbf{ex}(abcd)=abdc$ .

The following (folklore) property of Fibonacci words follows by a straightforward inductive argument.

Observation 5.

For $t\geq 2$ , we have $\,\mathbf{cut}(F_{t})\,=\,\,\mathbf{cut}(F_{t-2}F_{t-1})$ and $\mathbf{ex}(F_{t})\,=\,F_{t-2}F_{t-1}$ .

The next observation follows directly from the synchronization property of primitive words; see Figure 1.

Figure 1: Illustration of Observation 6(a). For the primitive word

u=\texttt{abcd}

and its proper prefix

u^{\prime}=\texttt{ab}

, the word

u^{2}u^{\prime}

contains

|u^{\prime}|+1

distinct squares of length

|u^{2}|

:

(\texttt{abcd})^{2}

,

(\texttt{bcda})^{2}

,

(\texttt{cdab})^{2}

.

Figure 2: The structure of

\mathcal{W}_{k,t}

for

k=2

and

t\geq 2

:

\mathcal{W}_{k,t}=A^{2}\,B\,A^{3}\,B\,A^{4}\,B

, where

A=F_{t}

and

B=F_{t-1}

. We have

\mathcal{W}_{k,t}=(AABA)^{2}\,AABA^{\prime}

, where

A^{\prime}=\mathbf{ex}(A)

. We have

\alpha=|F_{t}^{k}|=2|A|

and

|\mathcal{W}_{2,t}|=3\alpha+3|AB|

.

Observation 6 (Squares in periodic fragments).

(a)

If $u^{\prime}$ is a proper prefix of a primitive word $u$ , then $uuu^{\prime}$ contains $|u^{\prime}|+1$ distinct squares of length $|uu|$ .
(b)

$u^{k}$ contains at least $\lfloor\frac{k-1}{2}\rfloor|u|$ words that are rotations of words in $\{u^{2j}\mid 1\leq j\leq\frac{1}{2}k\}$ and are pairwise distinct.

Before describing our construction, we first identify the primitive roots of the squares under consideration. These roots correspond to rotations of squares of words of the following types.

Observation 7 (Primitive words).

For any $i>0$ and $t\geq 1$ , the words $F_{t-1},\,F_{t}^{i}F_{t-1}$ , and $F_{t}^{i}F_{t-1}F_{t}$ are primitive.

Proof.

For any $t\geq 1$ , words $F_{t-1}$ and $F_{t}^{k}F_{t-1}$ are standard Sturmian words for $k\geq 1$ . Since every standard Sturmian word is primitive (cf. [15]), it follows that all words of the form $F_{t-1}$ and $F_{t}^{i}F_{t-1}$ are primitive. Moreover, since any rotation of a primitive word is primitive, the word $F_{t}^{i}F_{t-1}F_{t}$ is primitive as its rotation $F_{t}^{i+1}F_{t-1}$ is primitive. $\hfill\blacktriangleleft$

The construction.

We define an infinite family of words. For any $k,t\in\mathbb{Z}_{+}$ , let

\mathcal{W}_{k,t}:=F_{t}^{k}F_{t-1}F_{t}^{k+1}F_{t-1}F_{t}^{k+2}F_{t-1}.

Note that $\mathcal{W}_{k,t}$ is parametrized by both $k$ and $t$ (eventually, we will set $k:=|F_{t}|$ ), and let $n:=|\mathcal{W}_{k,t}|$ . For convenience, we express bounds on the lengths of fragments and the number of square fragments in terms of

\alpha:=|F_{t}^{k}|=k|F_{t}|.

Note that we have

|\mathcal{W}_{k,t}|\,=\,(3k+3)|F_{t}|+3|F_{t-1}|\,=\,3\alpha\,+\,3\,|F_{t+1}|.

(1)

Squares in $\mathcal{W}_{k,t}$ and $\mathcal{W}_{k,t}^{2}$ .

We show that the words $\mathcal{W}_{k,t}$ are almost cubes (except the last two letters); see Figure 2 for an illustration.

Lemma 8.

For all $k,t\in\mathbb{Z}_{+}$ , we have that $\,\mathbf{cut}(\mathcal{W}_{k,t})=\,\mathbf{cut}((F_{t}^{k}F_{t-1}F_{t})^{3})$ . Further, $\mathcal{W}_{k,t}$ contains at least $\alpha$ distinct squares which are rotations of $(F_{t}^{k+1}F_{t-1})^{2}$ .

Proof.

We have

\mathcal{W}_{k,t}\;=\;F_{t}^{k}F_{t-1}F_{t}^{k+1}F_{t-1}F_{t}^{k+2}F_{t-1}\;=% \;(F_{t}^{k}F_{t-1}F_{t})(F_{t}^{k}F_{t-1}F_{t})F_{t}^{k}F_{t}F_{t-1}.

By Observation 5,

\,\mathbf{cut}(\mathcal{W}_{k,t})\,=\,(F_{t}^{k}F_{t-1}F_{t})(F_{t}^{k}F_{t-1}% F_{t})(F_{t}^{k}\,\,\mathbf{cut}(F_{t-1}F_{t}))\,=\,\,\mathbf{cut}((F_{t}^{k}F% _{t-1}F_{t})^{3}).

Hence, $\,\mathbf{cut}((F_{t}^{k}F_{t-1}F_{t})^{3})$ is a prefix of $\mathcal{W}_{k,t}$ . Now, $F_{t}^{k}F_{t-1}F_{t}$ is primitive due to Observation 7 and the second part of the statement follows by a direct application of Observation 6. $\hfill\blacktriangleleft$

Lemma 9.

If $t\geq 2$ and $k>0$ , $\mathcal{W}_{k,t}^{2}$ contains more than $2\alpha$ distinct squares that are rotations of $(F_{t}^{k}F_{t-1})^{2}$ and $(F_{t}^{k+2}F_{t-1})^{2}$ .

Proof.

We denote $\mathcal{R}_{1}:=(F_{t}^{k}F_{t-1})^{3}$ and $\mathcal{R}_{2}:=(F_{t}^{k+1}F_{t-1}F_{t})^{2}F_{t}^{k}$ . We show that both $\mathcal{R}_{1}$ and $\mathcal{R}_{2}$ occur in $\mathcal{W}_{k,t}^{2}$ ; see Figure 3. Then we obtain the statement using Observation 7 and Observation 6.

Figure 3: Illustration of Lemma 9: Structure of

\mathcal{W}_{k,t}^{2}

for

k=3

. The upper periodic fragment

\mathcal{R}_{1}=(F_{t}^{k}F_{t-1})^{3}

in

\mathcal{W}_{3,t}^{2}

does not occur in

\mathcal{W}_{3,t}

. The lower periodic fragment is

\mathcal{R}_{2}=(F_{t}^{k+1}F_{t-1}F_{t})^{2}F_{t}^{k}

. Together, these two periodic fragments contain at least

2\alpha

distinct squares of length at most

n

.

We first show that $\mathcal{R}_{1}$ occurs in $\mathcal{W}_{k,t}^{2}$ . The word

\mathcal{W}_{k,t}^{2}\,=\,F_{t}^{k}F_{t-1}F_{t}^{k+1}F_{t-1}\;\framebox{ {$F_{t}^{k+2}F_{t-1}\ F_{t}^{k}F_{t-1}F_{t}^{k+1}$}}\;F_{t-1}F_{t}^{k+2}F_{t-1}

has a fragment equal to $F_{t}^{k+2}F_{t-1}F_{t}^{k}F_{t-1}F_{t}^{k+1}$ , which in turn has a fragment equal to $(F_{t}^{k}F_{t-1})(F_{t}^{k}F_{t-1})F_{t}^{k}F_{t-1}=\mathcal{R}_{1}$ . Thus, $\mathcal{W}_{k,t}^{2}$ contains more than $\alpha$ distinct squares which are rotations of $(F_{t}^{k}F_{t-1})^{2}$ .

Next, we show that $\mathcal{R}_{2}$ occurs in $\mathcal{W}_{k,t}^{2}$ . The word

\mathcal{W}_{k,t}^{2}\,=\,F_{t}^{k}F_{t-1}\;\framebox{ {$F_{t}^{k+1}F_{t-1}F_{t}^{k+2}F_{t-1}\ F_{t}^{k}F_{t-1}F_{t}^{k+1}$}}\;F_{t-1% }F_{t}^{k+2}F_{t-1}

contains a fragment equal to

F_{t}^{k+1}F_{t-1}F_{t}\ F_{t}^{k+1}F_{t-1}F_{t}\ F_{t}^{k-1}F_{t-1}F_{t}^{k+1}

which itself has a fragment equal to

(F_{t}^{k+1}F_{t-1}F_{t})\ (F_{t}^{k+1}F_{t-1}F_{t})\ F_{t}^{k-1}F_{t-1}F_{t}

which is equal to $\mathbf{ex}((F_{t}^{k+1}F_{t-1}F_{t})^{2}\,F_{t}^{k}F_{t-1})$ , since $F_{t-1}F_{t}=\mathbf{ex}(F_{t}F_{t-1})$ . Now, observe that $\mathcal{R}_{2}=(F_{t}^{k+1}F_{t-1}F_{t})^{2}\,F_{t}^{k}$ is a prefix of this fragment. Thus $\mathcal{W}_{k,t}^{2}$ contains $|F_{t}^{k}|+1=\alpha+1$ distinct squares which are rotations of $(F_{t}^{k+1}F_{t-1}F_{t})^{2}$ .

Since $F_{t}^{k}F_{t-1}$ and $F_{t}^{k+2}F_{t-1}$ have different lengths, all considered square fragments are distinct and this concludes the proof. $\hfill\blacktriangleleft$

Lemma 10.

If $k\leq|F_{t}|$ then $\mathcal{W}_{k,t}$ contains at least $\alpha-\mathcal{O}(|F_{t}|)$ distinct squares which are rotations of $(F_{t}^{j}F_{t-1})^{2}$ for $0<j<k$ .

Proof.

The word $\mathcal{W}_{k,t}$ contains the fragment $F_{t}^{k+1}F_{t-1}F_{t}^{k+2}$ ; see Figure 4. For each $j\leq{k}$ it contains the fragment

F_{t}^{j}F_{t-1}F_{t}^{j+2}=\framebox{ {$F_{t}^{j}F_{t-1}F_{t}^{j}F_{t-1}\,F_{t-2}F_{t-1}$}}\,F_{t-2}=F_{t}^{j}F_{t-1% }F_{t}^{j}F_{t-1}\,\mathbf{ex}(F_{t-1}F_{t-2})\,F_{t-2},

which contains the fragment $(F_{t}^{j}F_{t-1})^{2}\,\,\mathbf{cut}(F_{t})$ .

By Observations 6 and 7, each such fragment, $(F_{t}^{j}F_{t-1})^{2}\,\,\mathbf{cut}(F_{t})$ , contains $|\,\mathbf{cut}(F_{t})|+1=|F_{t}|-1$ distinct squares that are rotations of $(F_{t}^{j}F_{t-1})^{2}$ .

Summing over all $0<j<k$ , we obtain at least $(|F_{t}|-1)\cdot(k-1)=\alpha-\mathcal{O}(|F_{t}|)$ distinct squares of the claimed form. $\hfill\blacktriangleleft$

Figure 4: Illustration of Lemma 10. For

k=4,\,t=4

, let

A=F_{t}=abaab,\,B=F_{t-1}=aba,

and

C=\,\mathbf{cut}(F_{t})=aba

. Then

\mathcal{W}_{k,t}

contains the fragment

F_{t}^{k}F_{t-1}F_{t}^{k+2}

, which in turn contains the fragments

(A^{j}\,B)^{2}\,C

, for

1\leq j\leq k

. Each of these fragments implies

|C|+1=|F_{t}|-1

squares. Altogether (including the case

j=0

), they contain

(|F_{t}|-1)\cdot k+|F_{t-1}|

squares, but Lemma 10 excludes the squares generated for

j=0

and

j=k

to avoid double counting.

The fact that $F_{t}^{k+2}$ occurs in $\mathcal{W}_{k,t}$ and Observations 6 and 7 imply the following:

Lemma 11.

$\mathcal{W}_{k,t}$ contains at least $\frac{1}{2}\alpha$ distinct squares that are rotations of the words in $\{F_{t}^{2j}\mid 1\leq j\leq\frac{k+2}{2}\}$ .

We are now ready to prove the main result of this section.

Theorem 12.

There are infinitely many integers $n$ for which $\mathsf{CS}(n)\geq 1.5n-\mathcal{O}(\sqrt{n})$ .

Proof.

Let us set $k:=|F_{t}|$ . Then $\alpha=k^{2}$ and $|F_{t}|=\mathcal{O}(\sqrt{n})$ . From Equation 1, the length of $\mathcal{W}_{k,t}$ is $n=3\alpha+\mathcal{O}(\sqrt{n})$ and hence $\alpha=\frac{1}{3}n-\mathcal{O}(\sqrt{n})$ .

By Lemmas 8, 9, 10, and 11, the word $\mathcal{W}_{k,t}^{2}$ contains at least $4.5\alpha-\Theta(|F_{t}|)$ squares (of length at most $n$ ). They are all distinct. Indeed, the squares from Lemmas 8, 9, and 10 are rotations of $(F_{t}^{j}F_{t-1})^{2}$ , for different $j\in[1\mathinner{.\,.}k+2]$ , so they have different lengths for different $j$ . The squares from Lemma 11 are of the form $(F_{t}^{j})^{2}$ for $j\leq k$ , and we have $|F_{t}^{j-1}F_{t-1}|<|F_{t}^{j}|<|F_{t}^{j}F_{t-1}|$ .

Therefore, the circular word $\mathcal{W}_{k,t}$ contains

4.5\cdot(\tfrac{1}{3}n-\mathcal{O}(\sqrt{n}))\,=\,1.5n-\mathcal{O}(\sqrt{n})

distinct squares, as required. $\hfill\blacktriangleleft$

4 Upper Bound

Let us fix a word $w$ of length $n$ . We denote $\widetilde{w}=ww$ . Our aim is to show that $|\mathbf{S}_{n}(\widetilde{w})|\leq\left\lceil 1.8n\right\rceil$ .

High-level idea of the proof.

If there exists a fragment (a $\delta$ -window) of $w^{\infty}$ of (small) length $\delta$ that contains no starting position of a long square, then it is easy to show that there are at most $2n-\delta$ distinct squares in the circular word $w$ . If no such fragment exists, we call $w$ $\delta$ -dense. Hence, we reduce the problem to showing that primitive $\delta$ -dense words do not exist – a simple upper bound of $1.5n$ can be shown for non-primitive words. We view a square $u u$ as a “transporter” which shifts long fragments of $w$ by $|u|$ positions (from the first copy of $u$ to the second one). By choosing a long non-periodic fragment (called a sample) $s$ , we consider only those distances $|u|$ that correspond to the distances between occurrences of the sample in $w w$ which start in the first copy of $w$ . The number of these occurrences is very small (bounded by a constant). Then, using samples, we show that if $w$ is primitive, then $w$ is not $\delta$ -dense.

Observation 13.

If $w^{\prime}$ is a rotation of $w$ , then $\mathbf{S}_{n}(ww)=\mathbf{S}_{n}(w^{\prime}w^{\prime})$ .

Lemma 14.

If $w^{\prime}$ is a rotation of $w$ that is not primitive, then $|\mathbf{S}_{n}(\widetilde{w})|\leq 1.5n$ .

Proof.

Suppose $w^{\prime}=u^{k}$ for some integer $k\geq 2$ . Then $\mathbf{S}_{n}(\widetilde{w})=\mathbf{S}_{n}(w^{\prime}w^{\prime})=\mathbf{S}_% {n}(uw^{\prime})$ . Consequently, due to [3], we have $|\mathbf{S}_{n}(\widetilde{w})|=|\mathbf{S}_{n}(uw^{\prime})|\leq|u|+|w|=(1+% \frac{1}{k})n$ . Since $k\geq 2$ , it follows that $|\mathbf{S}_{n}(\widetilde{w})|\leq 1.5n$ . $\hfill\blacktriangleleft$

Corollary 15.

If $\widetilde{w}$ contains a square of length exactly $n$ , then $|\mathbf{S}_{n}(\widetilde{w})|\leq 1.5n$ .

By the above corollary, we may henceforth assume that $w$ is primitive and $\widetilde{w}$ does not contain any square of length $n$ .

$\blacktriangleright$ Remark 16.

Circular words that are themselves squares can still contain many squares. It was shown in [1] that there exists an infinite family of words $w_{k}$ , each of which is a square, such that $\mathbf{S}_{n}(w_{k}w_{k})\geq 1.25|w_{k}|-o(|w_{k}|)$ .

Definition 17.

Let $w$ be a word of length $n$ . A square fragment $u u$ starting at position $j$ in $w^{\infty}$ is called a ${\delta}$ -square fragment with respect to an interval $[i\mathinner{.\,.}i+\delta)$ if

i\leq j<i+\delta\ \mbox{and}\ n-(j-i)<|uu|<n.

(2)

Observe that if $j<\delta$ is the last occurrence in $w w$ of a square $u u$ , then $u u$ is a $\delta$ -square with respect to the interval $I=[0\mathinner{.\,.}\delta)$ .

Definition 18.

A word $w$ is called $\mathbf{\delta}$ -dense if, for every length- $\delta$ fragment $I$ of $w^{\infty}$ , there exists a ${\delta}$ -square fragment with respect to $I$ . (See Figure 5.)

Figure 5: Illustration of the notion of

\delta

-density. The shown word is a prefix of

w^{\infty}[i\mathinner{.\,.}\infty)

. Here,

u u

is a

{\delta}

-square fragment with respect to the interval

I=[i\mathinner{.\,.}i+\delta)

(shown in blue): there exists a position

j

in the interval

I

where a square

u u

starts and satisfies

|uu|+(j-i)>n

. The word

w

is

\delta

-dense if such a square

u u

exists for each interval

[i\mathinner{.\,.}i+\delta)

with

i\in\mathbb{Z}_{+}

.

We first consider the easy case when $\widetilde{w}$ is not $\delta$ -dense.

Lemma 19 (Upper bound for words that are not $\delta$ -dense).

If $\widetilde{w}$ is not $\delta$ -dense, where $0<\delta\leq\frac{1}{2}n$ , then $|\mathbf{S}_{n}(\widetilde{w})|\leq 2n-\delta$ .

Proof.

By Corollary 15, if $\widetilde{w}$ contains a square fragment of length exactly $n$ , $|\mathbf{S}_{n}(\widetilde{w})|\leq 1.5n$ . Henceforth we assume that $\widetilde{w}$ does not have such a fragment. Since $\widetilde{w}$ is not $\delta$ -dense, by the definition, there exists an interval $I=[i\mathinner{.\,.}i+\delta)$ in $w^{\infty}$ such that no $\delta$ -square fragment exists with respect to $I$ . That is, for every square fragment $u u$ starting at some position $j\in I$ , $|uu|<n-(j-i)$ . Equivalently, the longest square starting at any position $q\in I$ has length at most $n-(q-i)$ . After a rotation (cf. Observation 13), we may assume that $i=0$ , so that $I=[0\mathinner{.\,.}\delta)$ . Now, let us consider the suffix $\widetilde{w}^{\prime}$ of $\widetilde{w}$ of length $2n-\delta$ . Every square fragment of $\widetilde{w}$ occurs entirely within $\widetilde{w}^{\prime}$ . Therefore, all distinct squares appear in a fragment of length $2n-\delta$ . The combination of this fact and the result of [3] implies that $|\mathbf{S}_{n}(\widetilde{w})|\leq 2n-\delta$ . $\hfill\blacktriangleleft$

Our aim is to show that no $\delta$ -dense words exist when $w$ is primitive and $\delta$ is sufficiently small.

The next lemma states that each fragment of $\widetilde{w}$ of length $\frac{1}{2}n-\delta$ has a copy to its right at a well-specified distance $d$ . See Figure 6 for an illustration.

Lemma 20 (Transporting Lemma).

Assume $w$ is $\delta$ -dense with positive integer $\delta\leq\frac{1}{2}n$ . Let $F$ be a fragment of length at most $\frac{1}{2}n-\delta$ that occurs at some position $i\geq n$ in $w^{\infty}$ . Then, $F$ also occurs in $w^{\infty}$ at position $i+\ell$ for some $\ell\in(\frac{1}{2}(n-\delta)\mathinner{.\,.}\frac{1}{2}n)$ .

Proof.

Since $w$ is $\delta$ -dense, there exists a position $j$ in $(i-\delta\mathinner{.\,.}i]$ where a $\delta$ -square fragment $x=uu$ occurs in $w^{\infty}$ . By the definition of a $\delta$ -square, its total length satisfies $n-(j-(i-\delta))<|uu|<n$ . It follows that the half-length $|u|$ satisfies $\frac{1}{2}(n-\delta)<|u|<\frac{1}{2}n$ .

By Equation 2, the square $x=uu$ ends at a position $z\geq i-\delta+n$ , so the first half $u$ of the square ends at a position $z^{\prime}\geq i-\delta+\frac{1}{2}n\geq i+|F|$ . Therefore the fragment $F$ is completely contained within $u$ . The second half of $x$ also contains a copy of $F$ shifted by a distance $|u|$ . Therefore, $F$ also occurs at position $i+|u|$ . $\hfill\blacktriangleleft$

Figure 6: Illustration of the Transporting Lemma (Lemma 20). The sample is shown in blue, and the

\delta

-length interval with respect to which the

\delta

-square occurs is shown in red.

We use the following fact from [1], whose proof relies on the periodicity lemma.

Fact 21 ([1, Lemma 4]).

Let $w$ be a word and let $a$ and $b$ be letters. If both $a w$ and $w b$ are periodic, then they have the same period.

Corollary 22.

If $w$ is primitive and $\ell\in[1\mathinner{.\,.}n]$ , then $\widetilde{w}$ contains a non-periodic fragment $\mathbf{s}$ of length $\ell$ . We refer to this as an $\ell$ -sample.

Proof.

Let us assume that $\widetilde{w}$ does not contain a non-periodic fragment of length $\ell$ . Then, by Fact 21, all length- $\ell$ fragments of $w w$ are periodic with the same period, i.e., the whole $\widetilde{w}$ has a period at most $\frac{1}{2}\ell$ . By the periodicity lemma (Lemma 1), $\widetilde{w}=ww$ has a period $p$ such that $p\leq\frac{1}{2}n$ and $p$ divides $n$ . Hence, $w$ is non-primitive. $\hfill\blacktriangleleft$

We show that, for every primitive word $w$ , $\widetilde{w}$ is not $\delta$ -dense for a certain parameter $\delta\leq 0.5n$ . Together with Lemmas 14 and 19, this implies that $|\mathbf{S}_{n}(\widetilde{w})|\leq 2n-\delta$ .

Simple Upper Bound

First we give a simple and intuitive proof for $\delta=\left\lfloor\frac{1}{6}n\right\rfloor$ .

Lemma 23.

If $w$ is primitive and $n=|w|\geq 6$ , then $\widetilde{w}$ is not $\left\lfloor\frac{1}{6}n\right\rfloor$ -dense.

Proof.

We prove this by contradiction. Assume that $\widetilde{w}$ is $\left\lfloor\frac{1}{6}n\right\rfloor$ -dense. Let $\mathbf{s}$ be a $\left\lfloor\frac{1}{3}n\right\rfloor$ -sample that is non-periodic (as guaranteed by Corollary 22). After a suitable rotation of $w w$ , we can assume that $\mathbf{s}$ occurs at positions $0$ and $n$ . Due to Lemma 20, $\mathbf{s}$ also occurs at position $i=d+d^{\prime}$ , where $d,d^{\prime}\in(\frac{1}{2}\cdot\frac{5}{6}n\mathinner{.\,.}\frac{1}{2}n)$ ; see Figure 7. Consequently, $\mathbf{s}$ occurs at distinct positions $n$ and $i$ that are at distance at most $\left\lfloor\frac{1}{6}n\right\rfloor\leq|\mathbf{s}|/2$ . Hence, $\mathbf{s}$ is periodic, a contradiction. $\hfill\blacktriangleleft$

Figure 7: Illustration of the proof of Lemma 23.

Lemmas 14, 19, and 23 imply that $\mathsf{CS}(n)\leq 2n-\left\lfloor\frac{1}{6}n\right\rfloor=\left\lceil\frac{1% 1}{6}n\right\rceil$ , after a trivial verification of the cases when $n<6$ .

Stronger Upper Bound

Next, we strengthen the upper bound using a more refined argument.

Lemma 24.

If $w$ is primitive, with $n=|w|\geq 5$ , then $\widetilde{w}$ is not $\left\lfloor 0.2n\right\rfloor$ -dense.

Proof.

We prove this by contradiction. Assume that $\widetilde{w}$ is $\delta$ -dense for $\delta=\left\lfloor 0.2n\right\rfloor$ . Let $\mathbf{s}$ be a non-periodic sample of length $\ell=\left\lfloor 0.3n\right\rfloor$ , (as guaranteed by Corollary 22, since $\ell\geq 1$ for $n\geq 4$ ). Let $\mathbf{A}$ denote the set of starting positions of $\mathbf{s}$ in $w w$ .

After a suitable rotation of $w w$ , we may assume that positions $0$ and $n$ belong to $\mathbf{A}$ . Let $\mathbf{A}^{\prime}=\mathbf{A}\cap[0\mathinner{.\,.}n)$ , $\mathbf{A}^{\prime}=\{a_{0},\ldots,a_{|\mathbf{A}^{\prime}|-1}\}$ with $a_{0}<\cdots<a_{|\mathbf{A}^{\prime}|-1}$ and define $\ell_{i}=a_{(i+1)\bmod|\mathbf{A}^{\prime}|}-a_{i}$ for $i\in[0\mathinner{.\,.}|\mathbf{A}^{\prime}|)$ .

For each occurrence at position $a_{i}$ , let $d_{i}$ be the shift distance given by the Transporting-Lemma (Lemma 20). This lemma applies since $\ell+\delta\leq\frac{1}{2}n$ , and it ensures that $d_{i}\in(\tfrac{1}{2}\cdot\left\lceil 0.8n\right\rceil\mathinner{.\,.}0.5n)$ .

Then, there exists some $i^{\prime}\in[0\mathinner{.\,.}|\mathbf{A}^{\prime}|)$ such that $(a_{i}+d_{i})\bmod n=a_{i^{\prime}}$ . We denote $\mathsf{succ}(i):=i^{\prime}$ , we define $\mathsf{succ}(i):=\mathsf{succ}(i\bmod|\mathbf{A}^{\prime}|)$ .

Claim 25.

For each $i\in[0\mathinner{.\,.}|\mathbf{A}^{\prime}|)$ , $\mathsf{succ}(\mathsf{succ}(i))=(i-1)\bmod n$ and $\ell_{i}\in(0.15n\mathinner{.\,.}\left\lfloor 0.2n\right\rfloor)$ .

Proof.

Let $\mathsf{succ}(i)=i^{\prime}$ and $\mathsf{succ}(i^{\prime})=i^{\prime\prime}$ . The sum of two consecutive shift distances $d_{i}+d_{i^{\prime}}\in(\left\lceil 0.8n\right\rceil\mathinner{.\,.}n)$ . Hence, $a_{i}+d_{i}+d_{i^{\prime}}<a_{i}+n$ , and there is no occurrence of $\mathbf{s}$ in $w^{\infty}$ between $a_{i}+d_{i}+d_{i^{\prime}}$ and $a_{i}+n$ ; otherwise, $\mathbf{s}$ would be periodic. Therefore, $\mathsf{succ}(\mathsf{succ}(i))=(i-1)\bmod n$ . Moreover,

\ell_{(i-1)\bmod n}\leq n-(\left\lceil 0.8n\right\rceil+1)<\left\lfloor 0.2n% \right\rfloor,\text{as claimed}.\

$\hfill\vartriangleleft$

Claim 26.

For each $i\in[0\mathinner{.\,.}|\mathbf{A}^{\prime}|)$ , $\mathsf{succ}(i)=(i+3)\bmod n$ .

Proof.

Each shift $d_{i}$ from the Transporting-Lemma lies in $(0.4n\mathinner{.\,.}0.5n)$ (as $\frac{1}{2}\cdot\left\lceil 0.8n\right\rceil\geq\frac{1}{2}\cdot 0.8n$ ), while each $\ell_{i}$ lies in interval $(0.15n\mathinner{.\,.}\left\lfloor 0.2n\right\rfloor)$ by Claim 25.

Since $2\cdot\left\lfloor 0.2n\right\rfloor\leq 0.4n<d_{i}<0.5n<4\cdot 0.15n$ , each shift spans exactly three intervals. Hence, $\mathsf{succ}(i)=(i+3)\bmod n$ . $\hfill\vartriangleleft$

The interval bounds from Claim 25 imply that $|\mathbf{A}^{\prime}|=6$ . But then, by Claim 26, $\mathsf{succ}(\mathsf{succ}(0))\neq|\mathbf{A}^{\prime}|-1$ , contradicting Claim 25. This completes the proof. $\hfill\blacktriangleleft$

By Lemmas 14, 19, and 24, we obtain the upper bound $\mathsf{CS}(n)\leq 2n-\left\lfloor 0.2n\right\rfloor=\left\lceil 1.8n\right\rceil$ , after a trivial verification of the cases when $n<5$ .

Theorem 27.

$\mathsf{CS}(n)\leq\left\lceil 1.8n\right\rceil$ .

$\blacktriangleright$ Remark 28.

If we used the sample size $\left\lfloor 0.25n\right\rfloor$ as in [1], we would obtain a weaker upper bound of $\left\lceil\frac{13}{7}n\right\rceil$ .

5 Limitations of our Approach

It appears that by taking larger values of $\delta$ , one could possibly strengthen Lemma 24, showing that every primitive word is not $\delta$ -dense, and thereby obtaining a stronger upper bound of $2n-\delta$ . However, we show that for $\delta=\frac{1}{3}n+4$ this approach no longer works.

We say that a square $u u$ kills a position $i$ in $w^{\infty}$ if $u u$ is a ${\delta}$ -square fragment with respect to the interval $[i\mathinner{.\,.}i+\delta)$ .

Observation 29.

(a)

A square $u u$ such that $n-(\delta-1)<|uu|<n$ starting at position $j$ in $w^{\infty}$ kills all positions contained modulo $n$ in the interval $[j-(\delta-1)\mathinner{.\,.}j+|uu|-n)$ .
(b)

For a periodic fragment $R$ with $n-(\delta-1)<2\cdot\mathrm{per}(R)<n$ starting at position $j$ in $w^{\infty}$ , all positions contained modulo $n$ in the interval

$I_{R}\,=\,[j-(\delta-1)\mathinner{.\,.}j+|R|-n-1]$ (3)

are killed by the $|R|-2\cdot\mathrm{per}(R)+1$ squares of length $2\cdot\mathrm{per}(R)$ that are induced by $R$ ; see Figure 8.

Figure 8: Let

w=a^{4}ba^{5}ba^{6}b

(fragment shown in brown) and

\delta=10

. The figure shows a word

(w^{\prime})^{2}

for a rotation

w^{\prime}

of

w

. The square fragments in

w^{\infty}

induced by the periodic fragment

R

(shown in red) together kill all positions contained modulo

n

in the interval

I_{R}

indicated by the yellow rectangle.

Fact 30.

There exist arbitrarily long primitive words $w$ that are $\delta$ -dense for $\delta=\frac{1}{3}|w|+4$ .

Proof.

Let us take $\mathcal{W}_{k,1}=a^{k}\,b\,a^{k+1}\,b\,a^{k+2}\,b$ of length $n=3k+6$ and $\delta\,=\,k+6=\tfrac{1}{3}n+4.$ Using Equation 3, it is easy to see that each position of $\mathcal{W}_{k,1}$ is killed by one of the following three periodic fragments:

$\blacksquare$

The fragment $R_{1}=(a^{k}ba)^{2}a^{k}$ occurring at position 0 kills positions in the interval

$[0-(k+5)\,\mathinner{.\,.}\,0+(3k+4)-n-1]\equiv_{\bmod n}[2k+1\mathinner{.\,.}% n-3].$
$\blacksquare$

The fragment $R_{2}=(a^{k+1}ba)^{2}a^{k-1}$ occurring at position $k+1$ kills positions in the interval

$[(k+1)-(k+5)\,\mathinner{.\,.}\,(k+1)+(3k+5)-n-1]\,\equiv_{\bmod n}\,[n-4% \mathinner{.\,.}n-1]\cup[0\mathinner{.\,.}k-1];$

cf. Figure 8.
$\blacksquare$

The fragment $R_{3}=(a^{k}b)^{2}a^{k}$ occurring at position $2k+5$ kills positions in the interval

$[(2k+5)-(k+5)\,\mathinner{.\,.}\,(2k+5)+(3k+2)-n-1]\,\equiv_{\bmod n}\,[k% \mathinner{.\,.}2k].$

The union of the intervals $[0\mathinner{.\,.}k-1]$ , $[k\mathinner{.\,.}2k]$ , $[2k+1\mathinner{.\,.}n-3]$ , and $[n-4\mathinner{.\,.}n-1]$ covers all positions in $\mathcal{W}_{k,1}$ . This implies that every position is killed by a suitable $\delta$ -square fragment. Hence, ${\mathbf{\mathcal{W}}_{k,1}}$ is $\delta$ -dense. $\hfill\blacktriangleleft$

6 Final Remarks

We have shown that $1.5n-\mathcal{O}(\sqrt{n})\,\leq\,\mathsf{CS}(n)\,\leq\,\left\lceil 1.8n\right\rceil$ , where the lower bound holds for infinitely many $n$ . We conjecture that the lower bound is tight, that is, that $\mathsf{CS}(n)\leq 1.5n$ .

Tight bounds related to repetitions and symmetries are usually non-trivial. This was, for instance, the case for bounds on standard squares (see [7, 9, 12, 5, 18, 3]) and powers ([11, 13, 14]), runs (the “runs theorem”; see [2] and references therein), and palindromes in circular words ([17]). For example, the abstract of [17] states: “In this paper we show, with a very complicated proof, …”).

Possibly, the elegant graph-theoretic proof of the recent upper bound for standard squares in [3] can be adapted to establish an $1.5n$ upper bound for distinct squares in circular words.

References

[1] Mika Amit and Pawel Gawrychowski. Distinct squares in circular words. In String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, volume 10508 of Lecture Notes in Computer Science, pages 27–37. Springer, 2017. doi:10.1007/978-3-319-67428-5_3.
[2] Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM Journal on Computing, 46(5):1501–1514, 2017. doi:10.1137/15M1011032.
[3] Srecko Brlek and Shuo Li. On the number of squares in a finite word. Combinatorial Theory, 5(1), 2025. doi:10.5070/C65165014.
[4] James D. Currie. There are ternary circular square-free words of length n for n >= 18. Electronic Journal of Combinatorics, 9(1), 2002. doi:10.37236/1671.
[5] Antoine Deza, Frantisek Franek, and Adrien Thierry. How many double squares can a string contain? Discrete Applied Mathematics, 180:52–69, 2015. doi:10.1016/J.DAM.2014.08.016.
[6] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109–114, 1965. doi:10.2307/2034009.
[7] Aviezri S. Fraenkel and Jamie Simpson. How many squares can a string contain? Journal of Combinatorial Theory, Series A, 82(1):112–120, 1998. doi:10.1006/JCTA.1997.2843.
[8] Aviezri S. Fraenkel and Jamie Simpson. The exact number of squares in Fibonacci words. Theoretical Computer Science, 218(1):95–106, 1999. doi:10.1016/S0304-3975(98)00252-7.
[9] Lucian Ilie. A note on the number of squares in a word. Theoretical Computer Science, 380(3):373–376, 2007. doi:10.1016/J.TCS.2007.03.025.
[10] Costas S. Iliopoulos, Dennis W. G. Moore, and William F. Smyth. A characterization of the squares in a Fibonacci string. Theoretical Computer Science, 172(1-2):281–291, 1997. doi:10.1016/S0304-3975(96)00141-7.
[11] Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. On the maximum number of cubic subwords in a word. European Journal of Combinatorics, 34(1):27–37, 2013. doi:10.1016/J.EJC.2012.07.012.
[12] Nguyen Huong Lam. On the number of squares in a string. AdvOL-Report, 2, 2013.
[13] Shuo Li. On the number of k-powers in a finite word. Advances in Applied Mathematics, 139:102371, 2022. doi:10.1016/J.AAM.2022.102371.
[14] Shuo Li, Jakub Pachocki, and Jakub Radoszewski. A note on the maximum number of k-powers in a finite word. Electronic Journal of Combinatorics, 31(3), 2024. doi:10.37236/11270.
[15] Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Standard factors of Sturmian words. RAIRO - Theoretical Informatics and Applications, 44(1):159–174, 2010. doi:10.1051/ITA/2010011.
[16] Arseny M. Shur. On ternary square-free circular words. Electronic Journal of Combinatorics, 17(1), 2010. doi:10.37236/412.
[17] Jamie Simpson. Palindromes in circular words. Theoretical Computer Science, 550:66–78, 2014. doi:10.1016/J.TCS.2014.07.012.
[18] Adrien Thierry. A proof that a word of length n has less than 1.5n distinct squares, 2020. arXiv:2001.02996.
[19] Axel Thue. Über unendliche Zeichenreihen. Norske Videnskabers Selskabs Skrifter Mat.-Nat. Kl., 7:1–22, 1906.

[bib.bib1] [1] Mika Amit and Pawel Gawrychowski. Distinct squares in circular words. In String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, volume 10508 of Lecture Notes in Computer Science, pages 27–37. Springer, 2017. doi:10.1007/978-3-319-67428-5_3.

[bib.bib2] [2] Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. SIAM Journal on Computing, 46(5):1501–1514, 2017. doi:10.1137/15M1011032.

[bib.bib3] [3] Srecko Brlek and Shuo Li. On the number of squares in a finite word. Combinatorial Theory, 5(1), 2025. doi:10.5070/C65165014.

[bib.bib4] [4] James D. Currie. There are ternary circular square-free words of length n for n >= 18. Electronic Journal of Combinatorics, 9(1), 2002. doi:10.37236/1671.

[bib.bib5] [5] Antoine Deza, Frantisek Franek, and Adrien Thierry. How many double squares can a string contain? Discrete Applied Mathematics, 180:52–69, 2015. doi:10.1016/J.DAM.2014.08.016.

[bib.bib6] [6] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109–114, 1965. doi:10.2307/2034009.

[bib.bib7] [7] Aviezri S. Fraenkel and Jamie Simpson. How many squares can a string contain? Journal of Combinatorial Theory, Series A, 82(1):112–120, 1998. doi:10.1006/JCTA.1997.2843.

[bib.bib8] [8] Aviezri S. Fraenkel and Jamie Simpson. The exact number of squares in Fibonacci words. Theoretical Computer Science, 218(1):95–106, 1999. doi:10.1016/S0304-3975(98)00252-7.

[bib.bib9] [9] Lucian Ilie. A note on the number of squares in a word. Theoretical Computer Science, 380(3):373–376, 2007. doi:10.1016/J.TCS.2007.03.025.

[bib.bib10] [10] Costas S. Iliopoulos, Dennis W. G. Moore, and William F. Smyth. A characterization of the squares in a Fibonacci string. Theoretical Computer Science, 172(1-2):281–291, 1997. doi:10.1016/S0304-3975(96)00141-7.

[bib.bib11] [11] Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. On the maximum number of cubic subwords in a word. European Journal of Combinatorics, 34(1):27–37, 2013. doi:10.1016/J.EJC.2012.07.012.

[bib.bib12] [12] Nguyen Huong Lam. On the number of squares in a string. AdvOL-Report, 2, 2013.

[bib.bib13] [13] Shuo Li. On the number of k-powers in a finite word. Advances in Applied Mathematics, 139:102371, 2022. doi:10.1016/J.AAM.2022.102371.

[bib.bib14] [14] Shuo Li, Jakub Pachocki, and Jakub Radoszewski. A note on the maximum number of k-powers in a finite word. Electronic Journal of Combinatorics, 31(3), 2024. doi:10.37236/11270.

[bib.bib15] [15] Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Standard factors of Sturmian words. RAIRO - Theoretical Informatics and Applications, 44(1):159–174, 2010. doi:10.1051/ITA/2010011.

[bib.bib16] [16] Arseny M. Shur. On ternary square-free circular words. Electronic Journal of Combinatorics, 17(1), 2010. doi:10.37236/412.

[bib.bib17] [17] Jamie Simpson. Palindromes in circular words. Theoretical Computer Science, 550:66–78, 2014. doi:10.1016/J.TCS.2014.07.012.

[bib.bib18] [18] Adrien Thierry. A proof that a word of length n has less than 1.5n distinct squares, 2020. arXiv:2001.02996.

[bib.bib19] [19] Axel Thue. Über unendliche Zeichenreihen. Norske Videnskabers Selskabs Skrifter Mat.-Nat. Kl., 7:1–22, 1906.

Improved Bounds on the Maximum Number of Distinct Squares in Circular Words

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our results.

Discussion.

2 Preliminaries

Lemma 1 (Periodicity Lemma [6]).

Fact 2.

Proof.

Example 3.

3 Lower Bound

Example 4.

Observation 5.

Observation 6 (Squares in periodic fragments).

Observation 7 (Primitive words).

Proof.

The construction.

Squares in 𝓦𝒌,𝒕 and 𝓦𝒌,𝒕𝟐.

Lemma 8.

Proof.

Lemma 9.

Proof.

Lemma 10.

Proof.

Lemma 11.

Theorem 12.

Proof.

4 Upper Bound

High-level idea of the proof.

Observation 13.

Lemma 14.

Proof.

Corollary 15.

▶ Remark 16.

Definition 17.

Definition 18.

Lemma 19 (Upper bound for words that are not δ-dense).

Proof.

Lemma 20 (Transporting Lemma).

Proof.

Fact 21 ([1, Lemma 4]).

Corollary 22.

Proof.

Simple Upper Bound

Lemma 23.

Proof.

Stronger Upper Bound

Lemma 24.

Proof.

Claim 25.

Proof.

Claim 26.

Proof.

Theorem 27.

▶ Remark 28.

5 Limitations of our Approach

Observation 29.

Fact 30.

Proof.

6 Final Remarks

References

Squares in $\mathcal{W}_{k,t}$ and $\mathcal{W}_{k,t}^{2}$ .

$\blacktriangleright$ Remark 16.

Lemma 19 (Upper bound for words that are not $\delta$ -dense).

$\blacktriangleright$ Remark 28.