Upper bound for the number of privileged words

Abstract

A non-empty word $w$ is a \emph{border} of a word $u$ if $|w|<|u|$ and $w$ is both a prefix and a suffix of $u$. A word $u$ is \emph{privileged} if $|u|\le 1$ or if $u$ has a privileged border $w$ that appears exactly twice in $u$. Peltomäki (2016) presented the following open problem: ``Give a nontrivial upper bound for $B(n)$'', where $B(n)$ denotes the number of privileged words of length $n$. Let ${\ln }^{[0]}(n)=n$ and let ${\ln }^{[j]}(n)=\ln ({\ln }^{[j-1]}(n))$, where $j,n$ are positive integers. We show that if $q>1$ is a size of the alphabet and $j\ge 3$ is an integer then there are constants ${\alpha }_j$ and $n_j$ such that \[B(n)\leq α_j\frac{q^{n}\sqrt{\ln{n}}}{\sqrt{n}}\ln^{[j]}{(n)}\prod_{i=2}^{j-1}\sqrt{\ln^{[i]}(n)}\mbox{, where }n\geq n_j\mbox{.}\] This result improves the upper bound of Rukavicka (2020).

13 pages, 0 figures

References in corpus (1)

• Upper bound for the number of closed and privileged words