On primary and secondary repetitions in words

NEW

Problem: For a word $w$ of length $n$, let $R(w)$ be its set of runs/maximal repetitions. In Kolpakov’s definition, a run $r$ is secondary if it is generated by two cognate non-separated runs $r',r''$ of common minimal period $p$ and satisfies

$$p(r)\ge 3p.$$

The conjecture asks whether, for every fixed integer $k\ge 3$, replacing this condition by

$$p(r)\ge kp$$

leaves the analogues of Kolpakov’s Theorems 17–19 true: namely

$$|R^{(k)}_{p,\lambda}(w)|=O_k(n/\lambda),$$ $$\operatorname{exp}^{(k)}_\lambda(w)+\operatorname{exs}^{(k)}_\lambda(w)=O_k(n/\lambda),$$

and

$$\operatorname{clp}^{(k)}_\lambda(w)=O_k(\log(n/\lambda)).$$

Here $R^{(k)}_{p,\lambda}(w)$ is the set of $k$-primary runs of period at least $\lambda$, $\operatorname{exp}^{(k)}_\lambda$ is the sum of their exponents, $\operatorname{exs}^{(k)}_\lambda$ is the sum of exponents of $k$-secondary runs generated by them, and $\operatorname{clp}^{(k)}_\lambda$ is the maximum number of such $k$-primary runs containing one position. The arXiv version numbers these as Theorems 17–19; the “22–24” numbering in the metadata is a numbering mismatch.

Result: The conjecture is true.

Let “3-primary/secondary” denote Kolpakov’s original definition. For fixed $k\ge3$, every $k$-secondary run is automatically 3-secondary, hence by Kolpakov’s Corollary 11 it is generated by 3-primary runs.

Let $\mu=\lceil \lambda/k\rceil$. If a $k$-primary run $r$ with $p(r)\ge\lambda$ is not 3-primary, then it is 3-secondary, generated by 3-primary runs of period $q$, and since it is not $k$-secondary we have

$$p(r)<kq.$$

Thus $q>p(r)/k\ge\lambda/k$, so $q\ge\mu$. Therefore every $k$-primary run of period at least $\lambda$ is either a 3-primary run of period at least $\mu$, or a 3-secondary run generated by 3-primary runs of period at least $\mu$. Kolpakov’s Theorem 18 for the original $3$-definition gives

$$\sum e(r)=O(n/\mu)=O_k(n/\lambda),$$

over all such runs. Since each run has exponent at least $2$, this also gives

$$|R^{(k)}_{p,\lambda}(w)|=O_k(n/\lambda).$$

The same inclusion gives the exponent bound. The $k$-primary runs of period at least $\lambda$, together with the $k$-secondary runs generated by them, are contained among the 3-primary runs of period at least $\mu$ and the 3-secondary runs generated by those. Hence Kolpakov’s original exponent theorem yields

$$\operatorname{exp}^{(k)}_\lambda(w)+\operatorname{exs}^{(k)}_\lambda(w) =O_k(n/\lambda).$$

It remains to check the local bound. Fix a position $i$. The 3-primary runs of period at least $\mu$ containing $i$ are $O(\log(n/\mu))$ by Kolpakov’s Theorem 19. Any additional $k$-primary run containing $i$ is a 3-secondary run generated by a pair of 3-primary runs of common period $q\ge\mu$, and it is not $k$-secondary, so its generated period has the form

$$p(r)=\alpha q+\sigma,\qquad 3\le \alpha<k,$$

as in Kolpakov’s Lemma 10. For a fixed generating run and a fixed side there are therefore at most $k-3$ such generated runs. A run has at most one cognate non-separated neighbour on each side, so each 3-primary run containing $i$ accounts for at most $2(k-3)$ additional $k$-primary runs containing $i$. Hence

$$\operatorname{clp}^{(k)}_\lambda(w) \le (1+2(k-3))\,O(\log(n/\mu)) =O_k(\log(n/\lambda)).$$

Thus all three asserted analogues remain valid for every fixed natural $k\ge3$.

Citation: The base case $k=3$, including Corollary 11, Lemma 10, and Theorems 17–19, is due to Roman Kolpakov, “On primary and secondary repetitions in words,” arXiv:1103.5230. The extension to arbitrary fixed $k\ge3$ follows by the reduction above.