Tight bounds on the number of non-equivalent parameterized squares in a word

Abstract

Two words $x,y$ of the same length are said to be \emph{parameterized equivalent} if there exists a character bijection that transforms $x$ into $y$. A word $w$ is called a parameterized square if $w$ is a concatenation of two parameterized equivalent words. Kociumaka et al. [TCS 2016] showed that in a word of length $n$ that contains $\sigma$ distinct characters, the number of \emph{parameterized squares} that are non-equivalent with respect to parameterized equivalence is at most $2\sigma !n$. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than $\sigma n$, which significantly improves the best-known upper bound by Kociumaka et al. Moreover, we construct a family of words containing $\Omega (\sigma n)$ non-equivalent parameterized squares, which demonstrates that the upper bound is asymptotically tight.

arXiv commentExtended version of SPIRE 2024