# Reply to ”Comment on ’Detecting Non-Abelian Geometric Phases with Three-
Level $\Lambda$ Atoms’ ”

Yan-Xiong Du  Zheng-Yuan Xue  Xin-Ding Zhang  Hui Yan<EMAIL_ADDRESS>Laboratory of Quantum Information Technology, School of Physics and
Telecommunication Engineering, South China Normal University, Guangzhou
510006, China

###### Abstract

In this reply, we address the comment by Ericsson and Sjoqvist on our paper
[Phys. Rev. A 84, 034103 (2011)]. We point out that the zero gauge field is
not the evidence of trivial geometric phase for a non-Abelian SU(2) gauge
field. Furthermore, the recalculation shows that the non-Abelian geometric
phase we proposed in the three-level $\Lambda$ system is indeed experimentally
detectable.

###### pacs:

03.65.Vf, 03.67.Lx, 32.90.+a

There are three points in the preceding comment Ericsson : (i) the sign in
Eq.(7) in the original paperdu  is wrong; (ii) non-Abelian geometrical
phase(GP) of a large-detuned $\Lambda$ system ( $\sin\gamma\approx 0$ with
$\gamma$ defined below) in the adiabatic approximation is trivial since the
corresponding gauge field vanishes; (iii) the GP is still small in the general
case with relatively large $\gamma$ and cannot be separated from the dynamical
phase .

In this reply, we address the above comments. We agree with point (i).
However, this mistake doesn’t influence the validity of the main result. We
re-calculate the population difference induced by the geometric phase after
correcting this sign error and find that the maximum population difference can
still reach $20\%$. Such big population difference can be easily detected in a
typical experiment.

We focus on the large-detuning case, where
$\tan\gamma=(\sqrt{\Delta^{2}+\Omega^{2}}-\Delta)/\Omega\approx 0$ with
$\Delta$ $(\Omega)$ the detuning (effective Rabi frequency). The large
detuning can be easily realized through choosing proper parameters, i.e.
$\Delta=1$ GHz and $\Omega=1$ MHz. As corrected in the commentEricsson , the
gauge potentials in the large detuning case can be written as

$\displaystyle A_{\theta}$ $\displaystyle\approx$ $\displaystyle
i\cos{\varphi}\sigma_{y}+i\sin{\varphi}\sigma_{x},$ (1) $\displaystyle
A_{\varphi}$ $\displaystyle\approx$
$\displaystyle-i\sin^{2}{\theta}\sigma_{z}+i\sin{\theta}\cos{\theta}\cos{\varphi}\sigma_{x}$
$\displaystyle-i\sin{\theta}\cos{\theta}\sin{\varphi}\sigma_{y}.$

Then we also agree that the corresponding gauge field $F_{\theta\varphi}$ must
vanish.

One will think of such potentials like Eq.(1) and (2) may not bring any
physical observable effects because of the vanished field strength. In the
following we will illustrate with some examples that this granted judgement is
wrong for non-Abelian gauge fields. The first example is about the vacuum
solution in a Yang-Mills theory demonstrated in detail in Ref.Jackiw . Jackiw
and Rebbi demonstrated thatJackiw , a type of gauge potentials in the Yang-
Mills theory are gauge equivalent to the potential $A=0$ and thus the field
strengths are vanished; however, the potentials should not be removed from the
integrations over the field configurations by the gauge fixing procedure, and
they argued that physical effects are associated with them. The second example
we will address in detail is the well-known case that spin $1/2$ behavior in a
time-dependent magnetic field $\mathbf{B}=(B_{x}(t),B_{y}(t),B_{z}(t))$Berry ;
Bliokh . The interacting Hamiltonian is

$H=\hbar\chi\mathbf{\sigma}\mathbf{B},$ (3)

here $\sigma$ is the Pauli Matrixes and $\chi$ is the coupling constant. This
Hamiltonian can be diagonalized through $H_{dg}=U^{-1}HU$ with the unitary
matrix

$U=\frac{1}{\sqrt{2B}}\left(\begin{array}[]{cc}\sqrt{B+B_{z}}&\sqrt{B-B_{z}}\\\
\frac{B_{x}+iB_{y}}{\sqrt{B+B_{z}}}&-\frac{B_{x}+iB_{y}}{\sqrt{B-B_{z}}}\\\
\end{array}\right),$ (4)

here the corresponding eigenvalues are $E_{\pm}=\pm\hbar\chi B$,
$B=|\mathbf{B}|$. For a pure gauge potential with the unitary matrix (4) as

$\mathbf{A}(\mathbf{m})=iU^{-1}\frac{\partial
U}{\partial\mathbf{m}},\mathbf{m}=(B_{x},B_{y},B_{z}),$ (5)

the non-Abelian gauge field $\mathbf{F}$ is vanishing Bliokh . To recover the
non-trivialness of such potential, one should choose a specific closed loop in
this parameter space, i.e. , a loop with large enough $B$ to maintain the
adiabatic approximation. In this case, the off-diagonal elements of
$\mathbf{A}(\mathbf{m})$ are rejected and the adiabatic gauge potentials
$\mathbf{A}^{(ad)}$ are given by

$\mathbf{A}^{(ad)}=(\frac{B_{y}}{2B(B\pm B_{z})},-\frac{B_{x}}{2B(B\pm
B_{z})},0),$ (6)

where different signs correspond to two eigenvalue $E_{\pm}$. The
corresponding field tensors are given by

$F_{ij}^{(ad)}=\frac{\partial A_{j}^{(ad)}}{\partial m_{i}}-\frac{\partial
A_{i}^{(ad)}}{\partial m_{j}}=\mp\varepsilon_{ijk}\frac{B_{k}}{2B^{3}},$ (7)

$\varepsilon_{ijk}$ is the three order antisymmetric tensor. It can be seen
that the closed path integral $\oint\mathbf{A}^{(ad)}d\mathbf{l}$ in these
monopole field strength is just the case of Berry phase. This integral is non-
zero and will bring physical observable effects. Furthermore, the integral
should hold when we shrink the curve by decreasing $B$ linearly, then we
return to the case of full matrix $\mathbf{A}(\mathbf{m})$. Therefore,
$\oint\mathbf{A}(\mathbf{m})d\mathbf{l}$ also contains a flux and will bring
physical observable effects. Namely, the non-vanishing
$\oint\mathbf{A}(\mathbf{m})d\mathbf{l}$ is guaranteed by
$\oint\mathbf{A}^{(ad)}d\mathbf{l}$ in the Abelian case. And hence, we show
with the second exampe that the gauge potential with a zero gauge field will
also have observable effects for its non-vanishing closed path integral in the
non-Abelian case.

Figure 1: (color online).(a) The new result of population difference after two
composed path with different orders. (b) The population difference $P_{d}$
versus parameter $\alpha$ when $\beta=0.5$. The parameters $\alpha$ and
$\beta$ represent the relative amplitude and the time delay of Raman pulses in
the stimulated Raman adiabatic transitions as the same in the origin paper du
.

The situation of three-level $\Lambda$ atoms interacting with lasers is
similar with the above analyzation. The unitary matrix diagonalize Hamiltonian
(1) in du  reads as

$\Gamma=\left(\begin{array}[]{ccc}\cos{\theta}&-\sin{\theta}e^{-i\varphi}&0\\\
\sin{\theta}\cos{\gamma}e^{i\varphi}&\cos{\theta}\cos{}\gamma&-\sin{\gamma}\\\
\sin{\theta}\sin{\gamma}e^{i\varphi}&\cos{\theta}\sin{\gamma}&\cos{\gamma}\end{array}\right),$
(8)

and $\gamma$ is given by
$\tan{\gamma}=(\sqrt{\Delta^{2}+\Omega^{2}}-\Delta)/\Omega$. One can set large
detuning $\Delta$ to achieve the non-Abelian geometric phase Eqs. (1,2). The
corresponding gauge field is zero. To recover the non-trivialness of Eqs.
(1,2), suitable $\Delta$ and $\Omega$ should be chose to reject the non-
diagonal elements. Then we return to the Abelian case of which the gauge
potential is $A^{\pm}_{\varphi}=\mp\sin^{2}{\theta}$ is observable Zhu . The
non-zero closed path integral of $A^{\pm}_{\varphi}$ can be extended to the
non-Abelian case just as the above analyzation. For example, we choose a
closed loop of
$\mathbf{A}=(A^{\prime}_{\theta},A^{\prime}_{\varphi})=i(A_{\theta},A_{\varphi})$
along $C$ with $\theta=\theta_{0}$, $\varphi\in[0,2\pi]$, and then the
integral can be derived as

$\oint\mathbf{A}d\mathbf{R}=\int_{0}^{2\pi}A^{\prime}_{\varphi}d\varphi=\pi(1-\cos
2\theta_{0})\sigma_{z}=\frac{1}{2}\Omega(C)\sigma_{z},$ (9)

where $\Omega(C)$ is the solid angle spanned by $C$ which shows the geometric
feature of the evolution. Clearly this integral is generally non-vanishing and
then the corresponding geometric phase is non-trivial.

The result of a vanishing gauge field brings physical effects is
counterintuitive. Indeed, this comes from the fact that the Stroke theorem in
the non-Abelian case is not a direct generalization of the Abelian case. It
has been realized that the surface integral in the non-Abelian case should
depend on the gauge field $F_{\theta\varphi}$ as well as the gauge potential
$\mathbf{A}$niu ; Barrett . Actually, the phase factor given as

$U=\hat{P}\exp\left(i\oint\mathbf{A}\cdot d\mathbf{l}\right)$ (10)

with $\hat{P}$ being the operator of chronological ordering, which is called
the Wilson loopWilson , is of particular important for a non-Abelian field.
This phase factor is transformed covariantly and may results in the observable
physical effects even with zero field strengthBliokh ; Yang .

We re-calculate the possibly observed effects based on Eqs.(1) and (2). The
new results are show in Fig.1, which should replace the results of Fig.2 in du
. The procedure and parameters are the same with those in our original paperdu
, but the gauge potentials are replaced with those in Eqs(1) and (2). We can
find from Fig.1 that the maximum population difference can still reach almost
$20\%$. Such big population difference can be easily detected in a typical
experiment. Since $\gamma\approx 0.001$ for $\Gamma/\Delta=0.001$, we know
that the effects induced by the dynamical phase could be neglected in the
above calculation, as shown in the commentEricsson . Therefore, the population
differences in Fig.1 are indeed induced by the non-Abelian gauge potential.
Moreover, we directly calculate the Schrodinger equation
$i\hbar\partial_{t}|\psi\rangle=H|\psi\rangle$ with the Hamiltonian given by
Eq.(1) in Ref.Ericsson . We find that the results are the same with those in
Fig.1 when the parameters are the same for the two different methods. It
further confirms that the population difference is indeed caused by the non-
vanished phase factor defined by the Wilson loop.

In summary, the main point that the authors used to defend in the comment is
that the induced gauge field is zero and thus the GP is trivial. However, we
have shown that this causality doesn’t hold for an SU(2) gauge field.
Furthermore, we have shown that the non-Abelian GP in our proposal is non-
trivial for its non-vanishing closed loop integral and can be detected through
the induced significant population difference.

Acknowledge: The authors thank Z. B. Li, D. W. Zhang and S. L. Zhu for helpful
discussions. This work was supported by the NSF of China(No. 11104085, No.
11125417, and No. 91121023 ), the SKPBR of China(No. 2011CB922104) and PCSIRT.
Du was aslo supported by the SRFGS of SCNU.

## References

  * (1) M. Ericsson and E. Sjoqvist, comment (to be published in Phys. Rev. A).
  * (2) Y. X. Du, Z. Y. Xue, X. D. Zhang and H. Yan, Phys. Rev. A 84, 034103 (2011).
  * (3) R. Jackiw and C. Rebbi, Phys. Rev. Lett. 37, 172 (1976).
  * (4) M. V. Berry, Proc. R. Soc. Lond. A 392, 45 (1984).
  * (5) K. Yu. Bliokh and Yu. P. Bliokh, Anna. of Phys. 319, 13 (2005).
  * (6) S. L. Zhu, H. Fu, C. J. Wu, S. C. Zhang and L. M. Duan, Phys. Rev. Lett. 97, 240401 (2006).
  * (7) A. Bohm, A. Mostafazadeh, H. Koizumi, Q. Niu, J. Zwanziger, The Geometric Phase in Quantum Systems (Springer, New York, 2003).
  * (8) T. Barrett and D. Grimes, Advanced Electromagnetism: Foundations, Theory, and application (World Scientific Publishing Co. Pte. Ltd., Singapore, 1995).
  * (9) K.G. Wilson, Phys. Rev. D 10 (1974) 2445.
  * (10) T. T. Wu and C. N. Yang, Phys. Rev. D 12, 3845 (1975); ibid. 12, 3843 (1975).


{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ Figure 2: The scheme
generating $a_{p}$ via $\mathop{\mathsf{vbit}}$ reductions. If a node
$\hat{t}$ has ingoing edges labeled with
$\tilde{t},\tilde{t}_{1},\tilde{t}_{2},\ldots,\tilde{t}_{r}$ (from left to
right), then $\hat{t}$ encodes a tuple
$\langle\tilde{w}_{1},\tilde{w}_{2},\ldots,\tilde{w}_{\ell}\rangle$ such that,
for $j\in[1..r]$,
$\tilde{w}_{j}=\mathop{\mathsf{vbit}}(\tilde{t},\tilde{t}_{j})$ and, for
$j\in(r..\ell]$, $\tilde{w}_{j}=\infty$. In the figure, the numbers
$t,t_{1},t_{2},\ldots,t_{m+5}$ correspond to consecutive positions
$p,p_{1},p_{2},\ldots,p_{m+5}$ in the set $S^{\prime}$, respectively. By
looking at which of the ingoing edges are present and which are not, one can
deduce that here we have
$S^{\prime}\cap(p..p{+}\tau/2^{5}]=\\{p_{1},\ldots,p_{m}\\}$,
$S^{\prime}\cap(p_{1}..p_{1}{+}\tau/2^{5}]=\\{p_{2},\ldots,p_{m}\\}$,
$S^{\prime}\cap(p_{2}..p_{2}{+}\tau/2^{5}]=\\{p_{3},\ldots,p_{m},p_{m+1}\\}$,
$S^{\prime}\cap(p_{m}..p_{m}{+}\tau/2^{5}]=\\{p_{m+1}\\}$,
$S^{\prime}\cap(p_{m+1}..p_{m+1}{+}\tau/2^{5}]=\\{p_{m+2},p_{m+3}\\}$,
$S^{\prime}\cap(p_{m+2}..p_{m+2}{+}\tau/2^{5}]=\\{p_{m+3}\\}$,
$S^{\prime}\cap(p_{m+3}..p_{m+3}{+}\tau/2^{5}]=\\{p_{m+4},p_{m+5}\\}$.

The numbers $\bar{t},\bar{t}_{1},\bar{t}_{2},\ldots,\bar{t}_{m}$, like the
numbers $t,t_{1},t_{2},\ldots,t_{m}$, could have been used, in principle, as
letters for the string $R$ but they still are too large. We therefore repeat
the same $\mathop{\mathsf{vbit}}$ reduction but now for the numbers
$\bar{t},\bar{t}_{1},\bar{t}_{2},\ldots,\bar{t}_{m}$ in place of
$t,t_{1},t_{2},\ldots,t_{m}$ thus generating a tuple $\langle
w^{\prime\prime}_{1},w^{\prime\prime}_{2},\ldots,w^{\prime\prime}_{\ell}\rangle$:
for $j\in[1..\ell]$,
$w^{\prime\prime}_{j}=\mathop{\mathsf{vbit}}(\bar{t},\bar{t}_{j})$ if $j\leq
m$, and $w^{\prime\prime}_{j}=\infty$ otherwise. The computation of
$\mathop{\mathsf{vbit}}(\bar{t},\bar{t}_{j})$ takes $\mathcal{O}(\ell)$ time
since $\bar{t}$ occupies $\ell$ machine words of size $\mathcal{O}(\log n)$
bits. It follows from Lemma 5 that the tuple $\langle
w^{\prime\prime}_{1},w^{\prime\prime}_{2},\ldots,w^{\prime\prime}_{\ell}\rangle$
can be packed into a chunk $\bar{\bar{t}}$ of
$\ell\lceil\log\ell+\log\lceil\log w+\log\tau+1\rceil+1\rceil$ bits (i.e.,
$\mathcal{O}(\log^{(3)}n\cdot\log\log n)$ bits), which already fits into one
machine word. We perform analogous reductions for the positions
$p_{1},p_{2},\ldots,p_{m}$ generating $m$ tuples $\langle
w^{\prime\prime}_{i,1},w^{\prime\prime}_{i,2},\ldots,w^{\prime\prime}_{i,\ell}\rangle$,
for $i\in[1..m]$, packed into new chunks
$\bar{\bar{t}}_{1},\bar{\bar{t}}_{2},\ldots,\bar{\bar{t}}_{m}$, respectively.
Note that, in order to produce a tuple $\langle
w^{\prime\prime}_{i,1},w^{\prime\prime}_{i,2},\ldots,w^{\prime\prime}_{i,\ell}\rangle$,
for $i\in[1..m]$, that is packed into $\bar{\bar{t}}_{i}$, we use not only the
numbers $\bar{t}_{i},\bar{t}_{i+1},\ldots,\bar{t}_{m}$ corresponding to
positions $p_{i},p_{i+1},\ldots,p_{m}$ but also similarly computed numbers at
other positions from $S^{\prime}\cap(p_{i}..p_{i}{+}\tau/2^{5}]$, if any. See
Figure 2 for a clarification: it can be seen that the “top” numbers include
not only $t,t_{1},\ldots,t_{m}$ precisely because of this.

By the same argument that proved the distinctness of
$\bar{t},\bar{t}_{1},\bar{t}_{2},\ldots,\bar{t}_{m}$, one can easily show that
$\bar{\bar{t}},\bar{\bar{t}}_{1},\bar{\bar{t}}_{2},\ldots,\bar{\bar{t}}_{m}$
are pairwise distinct. But they are still too larger to be used as letters of
$R$. Then again, we repeat the same reductions at positions
$p,p_{1},p_{2},\ldots,p_{m}$ but now for the numbers
$\bar{\bar{t}},\bar{\bar{t}}_{1},\bar{\bar{t}}_{2},\ldots,\bar{\bar{t}}_{m}$
in place of $\bar{t},\bar{t}_{1},\bar{t}_{2},\ldots,\bar{t}_{m}$, thus
generating new chunks
$\bar{\bar{\bar{t}}},\bar{\bar{\bar{t}}}_{1},\bar{\bar{\bar{t}}}_{2},\ldots,\bar{\bar{\bar{t}}}_{m}$.
Finally, once more, we do the $\mathop{\mathsf{vbit}}$ reduction for the
numbers
$\bar{\bar{\bar{t}}},\bar{\bar{\bar{t}}}_{1},\bar{\bar{\bar{t}}}_{2},\ldots,\bar{\bar{\bar{t}}}_{m}$
generating a tuple $\langle w_{1},w_{2},\ldots,w_{\ell}\rangle$ such that, for
$j\in[1..\ell]$,
$w_{j}=\mathop{\mathsf{vbit}}(\bar{\bar{\bar{t}}},\bar{\bar{\bar{t}}}_{j})$ if
$j\leq m$, and $w^{\prime}_{j}=\infty$ otherwise.

Using the same reasoning as in the proof of Lemma 7, one can deduce from Lemma
5 that the tuple $\langle w_{1},w_{2},\ldots,w_{\ell}\rangle$ fits into a
chunk of $\ell\cdot 2\log\log^{(3)}n\leq 2^{6}\lceil\log^{(3)}n\rceil^{2}$
bits (the inequality holds provided $n>2^{16}$) encoding each value $w_{j}$
into $\lceil\log^{(3)}n\rceil$ bits and representing $\infty$ by setting all
$\lceil\log^{(3)}n\rceil$ bits to $1$. Denote by $a_{p}$ this chunk of
$2^{6}\lceil\log^{(3)}n\rceil^{2}$ bits that encodes the tuple. We treat
$a_{p}$ as a new letter of $R$ that corresponds to the position $p$ and we
append $a_{p}$ to the end of $R$. Lemma 13 follows then straightforwardly by
construction.

For a given $p\in S^{\prime}$, the calculation of the numbers
$\bar{t},\bar{\bar{\bar{t}}},a_{p}$ takes $\mathcal{O}(\ell^{2})$ time. The
calculation of the number $\bar{\bar{t}}$ requires $\mathcal{O}(\ell^{3})$
time since each $\mathop{\mathsf{vbit}}$ reduction
$\mathop{\mathsf{vbit}}(\bar{t},\bar{t}_{j})$ for it takes $\mathcal{O}(\ell)$
time. Therefore, the total time for the computation of the string $R$ is
$\mathcal{O}(|S^{\prime}|\ell^{3})=\mathcal{O}(\frac{n}{\tau}(\log^{(3)}n)^{4})$,
which is $\mathcal{O}(n)$ since $\tau\geq(\log^{(3)}n)^{4}$.

######  Lemma 14.

If $s[p..p{+}\frac{7}{8}\tau]=s[q..q{+}\frac{7}{8}\tau]$, for $p,q\in
S^{\prime}$, then $a_{p}=a_{q}$.

###### Proof.

Since $S^{\prime}$ is an almost $\frac{3}{4}\tau$-partitioning set, as stated
in Lemma 12, it follows from property (b) for $S^{\prime}$ that the positions
$p$ and $q$ have a common “right context” of length $\tau/8$: more formally,
for any $d\in[0..\tau/8]$, we have
$s[p{+}d..p{+}d{+}\tau/2]=s[q{+}d..q{+}d{+}\tau/2]$, and $p+d\in S^{\prime}$
iff $q+d\in S^{\prime}$. In order to produce $a_{p}$, our algorithm first
consecutively computed numbers $\bar{t},\bar{\bar{t}},\bar{\bar{\bar{t}}}$ for
$p$. Denote by $p_{1},p_{2},\ldots,p_{m}$ all positions of
$S^{\prime}\cap(p..p{+}\tau/2^{5}]$ in the increasing order. By construction,
the number $\bar{t}$ depends on a “right context” of $p$ of length
$\tau/2^{5}$: $\bar{t}$ is produced by comparing $s[p..p{+}\tau/2]$ to all
strings $s[p_{1}..p_{1}{+}\tau/2],\ldots,$ $s[p_{m}..p_{m}{+}\tau/2]$ and,
thus, $\bar{t}$ coincides with analogously computed numbers at any other
positions $r$ such that, for all $d\in[0..\tau/2^{5}]$,
$s[p{+}d..p{+}d{+}\tau/2]=s[r{+}d..r{+}d{+}\tau/2]$ and $p+d\in S^{\prime}$
iff $r+d\in S^{\prime}$. It remains to show that the numbers
$\bar{\bar{t}},\bar{\bar{\bar{t}}},a_{p}$ in the same sense depend on “right
contexts” of $p$ of lengths $2\tau/2^{5},3\tau/2^{5},4\tau/2^{5}=\tau/8$,
respectively. The proof is similar for all three cases. Consider, for
instance, the number $\bar{\bar{\bar{t}}}$, assuming that the claim holds for
$\bar{\bar{t}}$. We obtain $\bar{\bar{\bar{t}}}$ by comparing $\bar{\bar{t}}$
to numbers $\bar{\bar{t}}_{1},\bar{\bar{t}}_{2},\ldots,\bar{\bar{t}}_{m}$
computed for $p_{1},p_{2},\ldots,p_{m}$, respectively. By the assumption, the
number $\bar{\bar{t}}_{m}$ corresponding to the rightmost of the positions,
$p_{m}$, depends on a “right context” of $p_{m}$ of length $2\tau/2^{5}$.
Therefore, since $p_{m}-p\leq\tau/2^{5}$, we obtain the claimed dependency of
$\bar{\bar{\bar{t}}}$ on a “right context” of $p$ with length
$\tau/2^{5}+2\tau/2^{5}=3\tau/2^{5}$. ∎

### Recompression.

If the distance between any pair of adjacent positions of $S^{\prime}$ is at
least $\tau/2^{6}$, then the size of $S^{\prime}$ is at most $2^{6}n/\tau$
and, due to Lemma 12, $S^{\prime}$ can be used as the resulting
$\tau$-partitioning set of size $\mathcal{O}(n/\tau)$. Unfortunately, this
might not be the case and, in general, we have to “sparsify” $S^{\prime}$.

There is a natural one-to-one correspondence between $S^{\prime}$ and
positions of $R$. Using a technique of Jeż [25] called _recompression_ (see
also [23]), we can remove in $\mathcal{O}(|R|)$ time some letters of $R$
reducing by a fraction $\frac{4}{3}$ the number of pairs of adjacent letters
$R[i],R[i{+}1]$ whose corresponding positions in $S^{\prime}$ are at a
distance at most $\tau/2^{6}$ (see below how the information about distances
is stored). We perform such reductions until the length of $R$ becomes at most
$2^{14}\cdot n/\tau$. The positions of $S^{\prime}$ corresponding to remained
letters will constitute a $\tau$-partitioning set of size
$\mathcal{O}(n/\tau)$. In order to guarantee that this subset of $S^{\prime}$
is $\tau$-partitioning, we have to execute the recompression reductions
gradually increasing the distances that are of interest for us: first, we get
rid of adjacent pairs with distances at most $\tau/\log^{(3)}n$ between them,
then the threshold is increased to $2\tau/\log^{(3)}n$, then
$2^{2}\tau/\log^{(3)}n$, $2^{3}\tau/\log^{(3)}n$, and so on until (most)
adjacent pairs with distances at most
$2^{\log^{(4)}n-6}\tau/\log^{(3)}n=\tau/2^{6}$ between them are removed in
last recompression reductions. The details follow.

Since it is impossible to store in $\mathcal{O}(n/\tau)$ space the precise
distances between positions of $S^{\prime}$, the information about distances
needed for recompression is encoded as follows. For each $i\in[0..|R|)$ and a
position $p\in S^{\prime}$ corresponding to the letter $R[i]$, we store an
array of numbers $M_{i}[0..\lceil\log^{(4)}n\rceil]$ such that, for
$j\in[0..\lceil\log^{(4)}n\rceil]$, $M_{i}[j]$ is equal to the size of the set
$S^{\prime}\cap(p..p{+}\tau/2^{j}]$. By Lemma 9, we have
$|S^{\prime}\cap(p..p{+}\tau]|\leq\mathcal{O}(\log^{(3)}n)$ and, hence, each
number $M_{i}[j]$ occupies $\mathcal{O}(\log^{(4)}n)$ bits. Therefore, all the
arrays $M_{i}$ can be stored in
$\mathcal{O}(|R|(\log^{(4)}n)^{2})\leq\mathcal{O}(\frac{n}{\tau}\log^{(3)}n\cdot(\log^{(4)}n)^{2})$
bits, which fits into $\mathcal{O}(\frac{n}{\tau})$ machine words of size
$\mathcal{O}(\log n)$ bits. All arrays $M_{i}$ are constructed in a
straightforward way in
$\mathcal{O}(|R|\log^{(3)}n)=\mathcal{O}(\frac{n}{\tau}(\log^{(3)}n)^{2})$
time (which is $\mathcal{O}(n)$ since $\tau\geq(\log^{(3)}n)^{4}$) during the
left-to-right pass over $S^{\prime}$ that generated the string $R$.

Our algorithm consecutively considers all numbers
$j\in[6..\lceil\log^{(4)}n\rceil]$ in decreasing order (i.e., starting with
$j=\lceil\log^{(4)}n\rceil$). For each $j$, the algorithm iteratively performs
a recompression procedure reducing the number of adjacent pairs of letters
$R[i],R[i{+}1]$ whose corresponding positions from $S^{\prime}$ are at a
distance at most $\tau/2^{j}$, until $R$ shrinks to a length at most
$2^{j+10}\cdot\frac{n}{\tau}$. Thus, $|R|\leq 2^{16}\cdot\frac{n}{\tau}$ after
last recompression reductions for $j=6$. Let us describe the recompression
procedure; for completeness, we repeat with proofs some key observations of
Jeż [25] for our adaptation of recompression.

Fix $j\in[6..\lceil\log^{(4)}n\rceil]$. To preserve property (c) of the
$\tau$-partitioning set $S^{\prime}$ during the sparsifications, we impose an
additional restriction: a letter $R[i]$ cannot be removed if either $i=0$ or
the distance between the position $p\in S^{\prime}$ corresponding to $R[i]$
and the predecessor of $p$ in $S^{\prime}$ is larger than $\tau/2^{5}$, i.e.,
if $M_{i-1}[5]=0$. The rationale is as follows: the position $p$ might be the
right boundary of a gap in $S^{\prime}$ of length $>\tau$ and it is dangerous
to break the gap since, once $p$ is removed, the gap might not satisfy
property (c) (the range of the string $s$ corresponding to the gap should have
a period that is at most $\tau/4$).

The processing of the number $j$ starts with checking whether $|R|\leq
2^{j+10}\cdot\frac{n}{\tau}$. If so, we skip the processing of $j$ and move to
$j-1$ (provided $j>6$). Suppose that $|R|>2^{j+10}\cdot\frac{n}{\tau}$. Denote
$\sigma=2^{2^{6}\lceil\log^{(3)}n\rceil^{2}}$, the size of the alphabet
$[0..\sigma)$ of $R$. Then, the algorithm creates an array
$P[0..\sigma{-}1][0..\sigma{-}1]$ filled with zeros, which occupies
$\mathcal{O}(\sigma^{2})=\mathcal{O}(2^{2^{7}(\log^{(3)}n)^{2}})=o(\log n)$
space, and collects in $P$ statistics on pairs of adjacent letters of $R$
whose corresponding positions in $S^{\prime}$ are at a distance at most
$\tau/2^{j}$ and whose first letter may be removed: namely, we traverse all
$i\in[1..|R|)$ and, if $M_{i}[j]\neq 0$ and $M_{i-1}[5]\neq 0$, then we
increase by one the number $P[R[i]][R[i{+}1]]$. It follows from Lemma 13 that
$R[i]\neq R[i+1]$ when $M_{i}[j]\neq 0$ (this is the only place where this
lemma is used but this observation is critical for the analysis in Lemma 15
that follows).

The idea proposed by Jeż is to view $P$ as an adjacency matrix of a weighted
digraph with $\sigma$ vertices and to construct an (approximately) maximal
directed cut for it; then, the set $[0..\sigma)$ is split into two disjoint
subsets $\acute{\Sigma}$ and $\grave{\Sigma}$ according to this cut and we
mark for removal from $R$ all indices $i\in[1..|R|{-}1)$ for which the
following conditions hold: $M_{i}[j]\neq 0$, $M_{i-1}[5]\neq 0$,
$R[i]\in\acute{\Sigma}$, and $R[i{+}1]\in\grave{\Sigma}$. Clearly, once the
sets $\acute{\Sigma}$ and $\grave{\Sigma}$ are computed (see below), the
marking procedure takes $\mathcal{O}(|R|)$ time. The marking can be organized
using a bit array of length $|R|$. The larger the cut the more pairs
$R[i],R[i{+}1]$ such that $M_{i}[j]\neq 0$ and $M_{i-1}[5]\neq 0$ are marked
for removal. Let us describe how the sets $\acute{\Sigma}$ and
$\grave{\Sigma}$ are built.

The splitting on $\acute{\Sigma}$ and $\grave{\Sigma}$ is performed
consecutively for the letters $0,1,\ldots,\sigma-1$ by the following standard
greedy algorithm. We start with empty sets $\acute{\Sigma}$ and
$\grave{\Sigma}$. Consider a letter $a\in[0..\sigma)$ assuming that the
letters $0,1,\ldots,a{-}1$ were already distributed among $\acute{\Sigma}$ and
$\grave{\Sigma}$. Consider two numbers
$c_{0}=\sum_{b\in\grave{\Sigma}}(P[a][b]+P[b][a])$ and
$c_{1}=\sum_{b\in\acute{\Sigma}}(P[b][a]+P[a][b])$: $c_{0}$ is the total
weight of edges that will be added to the (undirected) cut in case
$a\in\acute{\Sigma}$, for the current assignment, and $c_{1}$ is the weight
that will be added to the (undirected) cut in case $a\in\grave{\Sigma}$. We
put $a$ into $\acute{\Sigma}$ if $c_{0}\geq c_{1}$, and into $\grave{\Sigma}$
otherwise. In the end we check whether
$\sum_{a\in\acute{\Sigma},b\in\grave{\Sigma}}P[a][b]<\sum_{a\in\grave{\Sigma},b\in\acute{\Sigma}}P[a][b]$
and, if so, switch $\acute{\Sigma}$ and $\grave{\Sigma}$. Thus, the
initialization of $\acute{\Sigma}$ and $\grave{\Sigma}$ takes
$\mathcal{O}(\sigma^{2})=o(\log^{2}n)$ time.

In one right to left pass, we update values in all arrays $M_{i}$ according to
removal marks: for each $i\in[0..|R|)$ and
$j^{\prime}\in[0..\lceil\log^{(4)}n\rceil]$, a new value for
$M_{i}[j^{\prime}]$ is the number of indices
$i+1,i+2,\ldots,i+M_{i}[j^{\prime}]$ that were not marked for removal, i.e.,
$M_{i}[j^{\prime}]$ is the number of positions in the set
$S^{\prime}\cap(p..p{+}\tau/2^{j^{\prime}}]$ whose corresponding letters
$R[i^{\prime}]$ will remain in $R$, where $p\in S^{\prime}$ is the position
corresponding to $R[i]$. Since $M_{i}[j^{\prime}]\leq M_{i+1}[j^{\prime}]+1$,
for $i\in[0..|R|{-}1)$, the pass updating $M$ can be executed in
$\mathcal{O}(|R|\log^{(4)}n)$ time.

Finally, we delete letters $R[i]$ and arrays $M_{i}$, for all indices $i$
marked for removal, thus shrinking the length of $R$ and the storage used for
$M_{i}$. We call all this procedure, which marks letters of $R$ and removes
them and their corresponding arrays $M_{i}$, the recompression. One iteration
of the recompression overall takes $\mathcal{O}(|R|\log^{(4)}n)$ time, where
$|R|$ is the length of $R$ before the shrinking.

######  Lemma 15.

If, for $j\in[6..\lceil\log^{(4)}n\rceil]$, before the recompression procedure
there were $d$ non-zero numbers $M_{i}[j]$ with $i\in[1..|R|)$ such that
$M_{i-1}[5]\neq 0$, then the arrays $M_{i}$ modified by the procedure, for all
$i$ corresponding to unremoved positions of $R$, contain at most
$\frac{3}{4}d$ non-zero numbers $M_{i}[j]$ such that $M_{i-1}[5]{\neq}0$.

###### Proof.

The proof repeats an argument from [25] and [23, Lemma 7]. Consider an
undirected weighted graph $G$ corresponding to the digraph encoded in the
adjacency matrix $P$. By construction of $P$, we have $d=\sum_{a\neq
b}P[a][b]$, which follows from Lemma 13 that guarantees $R[i]\neq R[i+1]$ when
$M_{i}[j]\neq 0$. Thus, $d$ is the sum of weights of all edges in $G$. Putting
a letter $a$ into either $\acute{\Sigma}$ or $\grave{\Sigma}$, we add to the
cut at least half of the total weight of all edges connecting $a$ to the
letters $0,1,\ldots,a{-}1$. Therefore, the cut of $G$ induced by
$\acute{\Sigma}$ and $\grave{\Sigma}$ has a weight at least $\frac{1}{2}d$.
The edges in the cut might be directed both from $\acute{\Sigma}$ to
$\grave{\Sigma}$ and in the other direction. Switching $\acute{\Sigma}$ and
$\grave{\Sigma}$, if needed, we ensure that the direction from
$\acute{\Sigma}$ to $\grave{\Sigma}$ has a maximal total weight, which is
obviously at least $\frac{1}{4}d$. According to this cut, we mark for removal
from $R$ at least $\frac{1}{4}d$ letters $R[i]$ such that $M_{i}[j]\neq 0$.
Hence, the number of non-zero values $M_{i}[j]$ such that $M_{i-1}[5]\neq 0$
is reduced by $\frac{1}{4}d$, which gives the result of the lemma since new
non-zero values could not appear after the deletes. ∎

Suppose, for a fixed $j\in[6..\lceil\log^{(4)}n\rceil]$, the algorithm has
performed one iteration of the recompression. Denote by $S^{\prime\prime}$ the
set of all positions from $S^{\prime}$ that “survived” the recompression for
$j\in[6..\lceil\log^{(4)}n\rceil]$ and, thus, have a corresponding letter in
the updated string $R$. There is a one-to-one correspondence between
$S^{\prime\prime}$ and letters of $R$. For each $i\in[0..|R|)$ and
$j^{\prime}\in[0..\lceil\log^{(4)}n\rceil]$, the number $M_{i}[j^{\prime}]$ in
the modified arrays $M_{i}$ is the size of the set
$S^{\prime\prime}\cap(p..p{+}\tau/2^{j^{\prime}}]$, for a position $p\in
S^{\prime\prime}$ corresponding to $i$. We therefore can again apply the
recompression procedure thus further shrinking the length of $R$. The
algorithm first again checks whether $|R|>2^{j+10}\cdot\frac{n}{\tau}$ and, if
so, repeats the recompression. For the given fixed $j$, we do this iteratively
until $|R|\leq 2^{j+10}\cdot\frac{n}{\tau}$. During this process, the number
of zero values $M_{i}[j]$ in the arrays $M_{i}$ is always at most
$2^{j}\cdot\frac{n}{\tau}$ since the equality $M_{i}[j]=0$ implies that
$S^{\prime\prime\prime}\cap(p..p{+}\tau/2^{j}]=\emptyset$, for a set
$S^{\prime\prime\prime}\subseteq S^{\prime}$ of size $|R|$ defined by analogy
to the definition of $S^{\prime\prime}$ and for a position $p\in
S^{\prime\prime\prime}$ corresponding to $i$. Therefore, due to Lemma 15, the
condition $|R|\leq 2^{j+10}\cdot\frac{n}{\tau}$ eventually should be
satisfied. Furthermore, we are to show that, for each $j$, the condition
$|R|\leq 2^{j+10}\cdot\frac{n}{\tau}$ holds after at most three iterations of
the recompression.

Given $j\in[6..\lceil\log^{(4)}n\rceil)$, the length of $R$ before the first
iteration of the recompression for $j$ is at most
$2^{j+11}\cdot\frac{n}{\tau}$ since this is a condition under which shrinking
iterations stopped for $j+1$. The same bound holds for
$j=\lceil\log^{(4)}n\rceil$: the initial length of $R$ is at most
$2^{11}\cdot\frac{n}{\tau}\log^{(3)}n$ (which is upper-bounded by
$2^{j+11}\cdot\frac{n}{\tau}$) since $S^{\prime}\subseteq S$ and $S$ is
produced by the $k$th phase of the procedure of Section 3, for
$k=\lfloor\log\frac{\tau}{2^{4}\log^{(3)}n}\rfloor$, so that the size of $S$,
by Lemma 9, is at most $2^{6}\lceil n/2^{k}\rceil\leq
2^{6}n/\frac{\tau}{2\cdot 2^{4}\log^{(3)}n}=2^{11}\frac{n}{\tau}\log^{(3)}n$.
Fix $j\in[6..\lceil\log^{(4)}n\rceil]$. Since the number of zero values
$M_{i}[j]$ is always at most $2^{j}\cdot n/\tau$ and the number of zero values
$M_{i-1}[5]=0$ is at most $2^{5}\cdot\frac{n}{\tau}$, three iterations of the
recompression for $j$ performed on a string $R$ with initial length $r$ shrink
the length of $R$ to a length at most
$(\frac{3}{4})^{3}r+2^{j}\cdot\frac{n}{\tau}+2^{5}\cdot\frac{n}{\tau}\leq(\frac{3}{4})^{3}r+2\cdot
2^{j}\cdot\frac{n}{\tau}$, by Lemma 15. Putting
$r=2^{j+11}\cdot\frac{n}{\tau}$, we estimate the length of $R$ after three
iterations for $j$ from above by
$((\frac{3}{4})^{3}2^{11}+2)2^{j}\cdot\frac{n}{\tau}<2^{j+10}\cdot\frac{n}{\tau}$.
That is, for each $j$, three iterations are enough to reduce the length of $R$
to at most $2^{j+10}\cdot\frac{n}{\tau}$.

Thus, the total running time of all recompression procedures is
$\mathcal{O}(\sum_{j=\lceil\log^{(4)}n\rceil}^{6}2^{j+11}\cdot\frac{n}{\tau}\log^{(4)}n)=\mathcal{O}(\frac{n}{\tau}\log^{(4)}n)$,
which is $\mathcal{O}(n)$ since $\tau\geq(\log^{(3)}n)^{4}$. Observe that the
most time consuming part is in recalculations of the arrays $M_{i}$, each
taking $\mathcal{O}(|R|\log^{(4)}n)$ time, all other parts take
$\mathcal{O}(|R|)$ time, i.e.,
$\mathcal{O}(\sum_{j=\lceil\log^{(4)}n\rceil}^{6}2^{j+11}\cdot\frac{n}{\tau})=\mathcal{O}(\frac{n}{\tau})$
time is needed for everything without the recalculations. The length of $R$ in
the end is at most $2^{16}\cdot n/\tau$, which is a condition under which
shrinking iterations stopped for $j=6$.

Finally, we create a bit array $E$ of the same length as the original string
$R$ that marks by $1$ those letters that survived all the iterations.
Additional navigational data structures that allow us to produce the array $E$
in linear time are straightforward. We then again perform the whole “semi-
online” algorithm that generates the set $S^{\prime}$ (from which the string
$R$ was constructed) but, in this time, we discard all positions of
$S^{\prime}$ that correspond to unmarked indices in $E$ (i.e., their
corresponding letters in the original string $R$ did not survive the
recompression iterations) and we store all positions corresponding to marked
indices of $E$ explicitly in an array $S^{*}$. Since at most $2^{16}\cdot
n/\tau$ indices in $E$ are marked by $1$, the size of $S^{*}$ is
$\mathcal{O}(n/\tau)$.

######  Lemma 16.

The set $S^{*}$ is $\tau$-partitioning; also a converse of property (c) holds
for $S^{*}$: if a substring $s[i..j]$ has a period at most $\tau/4$, then
$S^{*}\cap[i+\tau..j-\tau]=\emptyset$.

###### Proof.

Since $S^{*}\subseteq S^{\prime}$, the converse of property (c) is inherited
from the set $S^{\prime}$ that satisfies it by Lemma 12; we relax the
condition $S^{*}\cap[i+\frac{3}{4}\tau..j-\frac{3}{4}\tau]=\emptyset$
slightly, for aesthetical reasons.

For $h\in[5..\lceil\log^{(4)}n\rceil]$, denote by $S_{h}$ the set of positions
from $S^{\prime}$ whose corresponding letters remained in $R$ after the
algorithm has performed all recompression procedures for all $j>h$. In
particular, $S_{\lceil\log^{(4)}n\rceil}=S^{\prime}$ and $S_{5}=S^{*}$. Note
that the size of each set $S_{h}$ is at most $2^{h+11}\cdot\frac{n}{\tau}$.

For property (a) of $S^{*}$, consider $p$ and $q$ such that
$s[p{-}\tau..p{+}\tau]=s[q{-}\tau..q{+}\tau]$. Let us show by induction that,
for each $h\in[5..\lceil\log^{(4)}n\rceil]$ and each $d$ such that
$|d|\leq\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$, we have $p+d\in S_{h}$ iff
$q+d\in S_{h}$. In particular, for $h=5$, $p\in S^{*}$ iff $q\in S^{*}$, which
is precisely the claim of property (a). The base of the induction is
$h=\lceil\log^{(4)}n\rceil$: since, as stated in Lemma 12, $S^{\prime}$ is an
almost $\frac{3}{4}\tau$-partitioning set, we have $p+d\in S^{\prime}$ iff
$q+d\in S^{\prime}$, for any $d$ such that $|d|\leq\frac{1}{8}\tau$. By Lemma
14, letters of $R$ corresponding to positions $p+d$ and $q+d$ such that
$p+d\in S^{\prime}$ and $q+d\in S^{\prime}$ coincide provided
$|d|\leq\frac{1}{8}\tau$ since
$s[p{+}d..p{+}d{+}\frac{7}{8}\tau]=s[q{+}d..q{+}d{+}\frac{7}{8}\tau]$.

Fix $h\in[6..\lceil\log^{(4)}n\rceil]$ and suppose, by the inductive
hypothesis, that $p+d\in S_{h}$ iff $q+d\in S_{h}$, for any $d$ such that
$|d|\leq\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$. We are to prove the inductive
step: $p+d\in S_{h-1}$ iff $q+d\in S_{h-1}$, for any $d$ such that
$|d|\leq\frac{1}{8}\tau-\frac{8}{2^{h}}\tau$. Let $R$ be a string obtained by
the algorithm after performing all recompression procedures for all $j>h$.
Thus, there is a one-to-one correspondence between the positions $S_{h}$ and
letters of the string $R$. Consider a (contiguous) sequence of letters
$a_{i}a_{{i}+1}\cdots a_{m}$ of $R$ corresponding to all positions $p+d\in
S_{h}$ such that $|d|\leq\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$, and,
analogously, a sequence $a_{{i}^{\prime}}a_{{i}^{\prime}+1}\cdots
a_{m^{\prime}}$ corresponding to positions $q+d\in S_{h}$. By the inductive
hypothesis and due to Lemma 14, the sequences coincide. The algorithm performs
on the string $R$ at most three recompression reductions removing some of the
letters until the positions of $S_{h}$ corresponding to the remained letters
constitute the set $S_{h-1}$. Denote by $r$ and $r^{\prime}$ the positions of
$S_{h}$ corresponding to the letters $a_{m}$ and $a_{m^{\prime}}$,
respectively. A discrepancy in the processing of the sequences by the first
iteration of recompression may occur only in their last letters: for instance,
the letter $a_{m}$ will be removed whereas $a_{m^{\prime}}$ will be retained
(see an example in Figure 3). Let us analyze this particular case (other cases
are similar). This may happen only if $a_{m}\in\acute{\Sigma}$ and $a_{m}$ is
followed in $R$ by a letter $a\in\grave{\Sigma}$ and the distance between $r$
and the position of $S_{h}$ corresponding to $a$ is at most $\tau/2^{h}$; at
the same time, either $a_{m^{\prime}}$ ($=a_{m}$) is followed by a different
letter $b\in\acute{\Sigma}$ ($\neq a$) or the distance between $r^{\prime}$
and the position of $S_{h}$ corresponding to this following letter is larger
than $\tau/2^{h}$. We therefore deduce that the distance from $r$ to
$p+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$ is less than $\tau/2^{h}$ (for
otherwise the letter $a$ following $a_{m}$ must be a part of the sequence
$a_{i}a_{{i}+1}\cdots a_{m}$), which implies that
$r-p>\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau-\frac{1}{2^{h}}\tau=\frac{1}{8}\tau-\frac{5}{2^{h}}\tau$.

Thus, we have shown that two sequences resulting from $a_{i}a_{{i}+1}\cdots
a_{m}$ and $a_{{i}^{\prime}}a_{{i}^{\prime}+1}\cdots a_{m^{\prime}}$ after the
recompression coincide in all letters whose corresponding positions from
$S_{h}$ are at a distance at most $\frac{1}{8}\tau-\frac{5}{2^{h}}\tau$ from
$p$ and $q$, respectively. Exactly the same argument can be applied for the
second recompression. A discrepancy in the processing of the resulting
sequences by the second iteration of recompression (if any) may again occur
only in last letters of the sequences: for instance, the last letter $c$ of
the first sequence (the letter $a_{m-1}$ in the example of Figure 3) will be
retained whereas the corresponding letter $c$ of the second sequence (the
letter $a_{m^{\prime}-1}$ in the example) will be removed. Denote by
$r^{\prime\prime}$ the position of $S_{h}$ corresponding to the removed letter
$c$. By analogy to the argument used for the first iteration, we deduce that
the distance between $r^{\prime\prime}$ and $r^{\prime}$ is at most
$\tau/2^{h}$. Observe that $r-p=r^{\prime}-q$. Therefore,
$r^{\prime\prime}-q\geq
r^{\prime}-q-\frac{1}{2^{h}}\tau>\frac{1}{8}\tau-\frac{5}{2^{h}}\tau-\frac{1}{2^{h}}\tau=\frac{1}{8}\tau-\frac{6}{2^{h}}\tau$.
Thus, two sequences resulting from the second recompression coincide in all
letters whose corresponding positions from $S_{h}$ are at a distance at most
$\frac{1}{8}\tau-\frac{6}{2^{h}}\tau$ from $p$ and $q$, respectively.
Analogously, we deduce that two sequences resulting from the third
recompression (if any) coincide in all letters whose corresponding positions
from $S_{h}$ are at a distance at most
$\frac{1}{8}\tau-\frac{6}{2^{h}}\tau-\frac{1}{2^{h}}\tau=\frac{1}{8}\tau-\frac{7}{2^{h}}\tau$
from $p$ and $q$, respectively. This proves the inductive claim since
$\frac{1}{8}\tau-\frac{7}{2^{h}}\tau\geq\frac{1}{8}\tau-\frac{8}{2^{h}}\tau$
and the set $S_{h-1}$ consists of all positions from $S_{h}$ that correspond
to the letters of $R$ remained after the (at most) three recompressions.

$\begin{array}[]{rlcl}\text{before 1st recompression:}&\cdots
a_{m-5}a_{m-4}{a_{m-3}}a_{m-2}\leavevmode\hbox to14.87pt{\vbox
to6.11pt{\pgfpicture\makeatletter\hbox{\hskip 7.43471pt\lower-3.055pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-7.43471pt}{-1.25055pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$a_{m-1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}a_{m}~{}a&{}\hfil&\cdots
a_{m^{\prime}-5}a_{m^{\prime}-4}{a_{m^{\prime}-3}}a_{m^{\prime}-2}\leavevmode\hbox
to15.75pt{\vbox to6.11pt{\pgfpicture\makeatletter\hbox{\hskip
7.87471pt\lower-3.055pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-7.87471pt}{-1.25055pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$a_{m^{\prime}-1}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}a_{m^{\prime}}~{}b\\\
\text{after 1st
recompression:}&\cdots{a_{m-5}}a_{m-4}\phantom{a_{m-3}}a_{m-2}a_{m-1}\phantom{a_{m}}~{}a&{}\hfil&\cdots{a_{m^{\prime}-5}}a_{m^{\prime}-4}\phantom{a_{m^{\prime}-3}}a_{m^{\prime}-2}{a_{m^{\prime}-1}}a_{m^{\prime}}~{}b\\\
\text{after 2nd
recompression:}&\cdots\phantom{a_{m-5}}a_{m-4}\phantom{a_{m-3}}a_{m-2}a_{m-1}\phantom{a_{m}}~{}a&{}\hfil&\cdots\phantom{a_{m^{\prime}-5}}a_{m^{\prime}-4}\phantom{a_{m^{\prime}-3}}a_{m^{\prime}-2}\phantom{a_{m^{\prime}-1}}a_{m^{\prime}}~{}b\\\
\text{after 3rd
recompression:}&\cdots\phantom{a_{m-5}}a_{m-4}\phantom{a_{m-3}}\phantom{a_{m-2}}a_{m-1}\phantom{a_{m}}~{}a&{}\hfil&\cdots\phantom{a_{m^{\prime}-5}}a_{m^{\prime}-4}\phantom{a_{m^{\prime}-3}}a_{m^{\prime}-2}\phantom{a_{m^{\prime}-1}}a_{m^{\prime}}~{}b\end{array}$

$\overbrace{\phantom{aa}}^{{\leq}\frac{\tau}{2^{h}}}~{}\overbrace{\phantom{aa}}^{{\leq}\frac{\tau}{2^{h}}}~{}\overbrace{\phantom{aa}}^{{\leq}\frac{\tau}{2^{h}}}$$\overbrace{\phantom{aa}}^{{\leq}\frac{\tau}{2^{h}}}~{}\overbrace{\phantom{aa}}^{{\leq}\frac{\tau}{2^{h}}}~{}\overbrace{\phantom{aa}}^{~{}}$

Figure 3: A schematic example of three iterations of recompression on equal
sequences $a_{{i}}a_{{i}+1}\cdots a_{m}$ and
$a_{{i}^{\prime}}a_{{i}^{\prime}+1}\cdots a_{m^{\prime}}$
($m-{i}=m^{\prime}-{i}^{\prime}$ and $a_{{i}+t}=a_{{i}^{\prime}+t}$, for any
$t\in[0..m{-}{i}]$). The overbraces designate restrictions on distances
between positions of $S_{h}$ corresponding to letters.

For property (b) of $S^{*}$, consider $p,q\in S^{*}$ such that
$s[p..p{+}\ell]=s[q..q{+}\ell]$, for some $\ell\geq 0$. Clearly, only the case
$\ell>\tau$ is interesting. Denote $\tilde{\ell}=\ell-\tau$. It suffices to
prove that, for each $h\in[5..\lceil\log^{(4)}n\rceil]$ and each $d$ such that
$0\leq d<\tilde{\ell}+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$, we have $p+d\in
S_{h}$ iff $q+d\in S_{h}$. In particular, for $h=5$, it is precisely the claim
of property (b): for any $d\in[0..\tilde{\ell})=[0..\ell{-}\tau)$, $p+d\in
S^{*}$ iff $q+d\in S^{*}$. The proof is essentially by the same inductive
argument as for property (a). The base of the induction,
$h=\lceil\log^{(4)}n\rceil$, follows from Lemma 12 where it is stated that
$S^{\prime}$ ($=S_{\lceil\log^{(4)}n\rceil}$) is an almost
$\frac{3}{4}\tau$-partitioning set. By Lemma 14, the letters of $R$
corresponding to positions $p+d$ and $q+d$ such that $p+d\in S^{\prime}$ and
$q+d\in S^{\prime}$ coincide provided $0\leq d<\tilde{\ell}+\frac{1}{8}\tau$
since $s[p{+}d..p{+}d{+}\frac{7}{8}\tau]=s[q{+}d..q{+}d{+}\frac{7}{8}\tau]$.
The proof of the inductive step is very similar to the proof for property (a)
above; we therefore only briefly sketch it without diving into details.

Fix $h\in[6..\lceil\log^{(4)}n\rceil]$ and suppose, by the inductive
hypothesis, that $p+d\in S_{h}$ iff $q+d\in S_{h}$, for any $d$ such that
$0\leq d<\tilde{\ell}+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$. Let $R$ be a
string produced by the algorithm after performing all recompression procedures
for all $j>h$. There is a one-to-one correspondence between $S_{h}$ and
letters of $R$. Consider a (contiguous) sequence of letters
$a_{i}a_{i+1}\cdots a_{m}$ of $R$ corresponding to all positions $p+d\in
S_{h}$ such that $0\leq d<\tilde{\ell}+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$,
and, analogously, a sequence $a_{i^{\prime}}a_{i^{\prime}+1}\cdots
a_{m^{\prime}}$ corresponding to positions $q+d\in S_{h}$. By the inductive
hypothesis and due to Lemma 14, the sequences coincide. The algorithm performs
on $R$ at most three recompressions removing some letters until the positions
of $S_{h}$ corresponding to the remained letters constitute the set $S_{h-1}$.
Discrepancies occurring in the two sequences after the recompressions may
affect only last positions that are close—at a distance at most
$3\tau/2^{h}$—to the “right borders”,
$p+\tilde{\ell}+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$ and
$q+\tilde{\ell}+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau$, of the sequences,
respectively. Therefore, all positions from $S_{h}\cap[p..\infty)$ and
$S_{h}\cap[q..\infty)$ that were at a distance at least $3\tau/2^{h}$ to the
left of the “right borders” are “synchronized”, i.e., such a position $p+d\in
S_{h}$ is removed from $S_{h}$ iff $q+d\in S_{h}$ is removed too. The
“synchronized” positions are exactly $p+d\in S_{h}$ and $q+d\in S_{h}$ such
that $0\leq
d<\tilde{\ell}+\frac{1}{8}\tau-\frac{8}{2^{h+1}}\tau-\frac{3}{2^{h}}\tau=\tilde{\ell}+\frac{1}{8}\tau-\frac{7}{2^{h}}\tau$,
so that $p+d\in S_{h-1}$ iff $q+d\in S_{h-1}$. Since
$\frac{1}{8}\tau-\frac{7}{2^{h}}\tau\geq\frac{1}{8}\tau-\frac{8}{2^{h}}\tau$
and the set $S_{h-1}$ is formed by remained positions of $R$ after the (at
most) three recompressions, this proves the inductive step.

For property (c) of $S^{*}$, consider $p,q\in S^{*}$ such that $q-p>\tau$ and
$S^{*}\cap(p..q)=\emptyset$. By construction, a recompression procedure
performed on a string $R$ may delete a letter $R[i]$ only if the distance from
the position $r$ corresponding to $R[i]$ to the positions $r^{\prime}$ and
$r^{\prime\prime}$ of $S^{\prime}$ corresponding to the letters $R[i{-}1]$ and
$R[i{+}1]$ is at most $\tau/2^{5}$. Further, if $R[i]$ is removed, then
neither $R[i{-}1]$ nor $R[i{+}1]$ can be removed in the same iteration of
recompression. The distance between $r^{\prime}$ and $r^{\prime\prime}$ is at
most $\tau/2^{4}$. Therefore, it is impossible that there was a position of
$S^{\prime}$ from $(p..q)$ that got removed. Thus,
$S^{\prime}\cap(p..q)=\emptyset$. Since $S^{\prime}$ is a $\tau$-partitioning
set, we deduce that the substring $s[p..q]$ has a period at most $\tau/4$ by
property (c) of $S^{\prime}$. ∎

##  6 Small $\tau$

Assume that $\tau<(\log^{(3)}n)^{4}$. If $\tau\geq 2^{5}\log^{(3)}n$, we
perform the procedure of Sections 3–4 generating a
$\frac{\tau}{2}$-partitioning set $S$ of size
$\mathcal{O}(\frac{n}{\tau}\log^{(3)}n)$. If $\tau<2^{5}\log^{(3)}n$, we put
$S=[0..n)$, which is a $\frac{\tau}{2}$-partitioning set of size
$\mathcal{O}(\frac{n}{\tau}\log^{(3)}n)$ in this case. All this is done in
$\mathcal{O}(n)$ time and $\mathcal{O}(\frac{n}{\tau})$ space (provided the
set $S$ is not stored explicitly), which are the time and space bounds we aim
for. The problem is in the remaining stages of the algorithm. Specifically, it
is in the following “slow” parts:

  1. (i)

the generation of the subset $S^{\prime}\subseteq S$ requires
$\mathcal{O}(n+|S|\log^{(3)}n)$ time;

  2. (ii)

the construction of the string $R$ takes
$\mathcal{O}(n+|S^{\prime}|(\log^{(3)}n)^{3})$ time;

  3. (iii)

the initialization of the arrays $M_{i}$, for all $i\in[0..|S^{\prime}|)$,
requires $\mathcal{O}(|S^{\prime}|\log^{(3)}n)$ time;

  4. (iv)

each update of the arrays $M_{i}$ before shrinking the string $R$ takes
$\mathcal{O}(|R|\log^{(4)}n)$ time.

If we optimize all these four bottlenecks to run, respectively, in
$\mathcal{O}(n)$, $\mathcal{O}(n)$, $\mathcal{O}(|S^{\prime}|)$, and
$\mathcal{O}(|R|)$ time, then the running time of the whole algorithm will be
$\mathcal{O}(n)$. We do all four optimizations by the four russians’ trick
[2]. The idea of the trick is that if one has to perform complicated queries
on chunks of $c$ bits, then instead of computing the queries explicitly each
time, we can precalculate a table of size $2^{c}$ with answers for every
possible chunk. What are the “chunks” and the “queries” in our case? The
easiest is to analyze (iv) to give an example. Let us describe how one can
update the arrays $M_{i}$ in $\mathcal{O}(|R|)$ time before shrinking $R$.

#### Part (iv).

Suppose that we have marked some letters of $R$ for removal using a bit array
$A[0..|R|{-}1]$ of length $R$: $R[i]$ is marked iff $A[i]=1$. Every array
$M_{i}[0..\lceil\log^{(4)}n\rceil]$ occupies $\mathcal{O}((\log^{(4)}n)^{2})$
bits (each entry is of size $\mathcal{O}(\log^{(4)}n)$ bits). The naïve
updating procedure considers every entry $M_{i}[j]$ and counts which of the
letters $R[i{+}1],R[i{+}2],\ldots,R[i{+}M_{i}[j]]$ were not marked for
removal, assigning the result to $M_{i}[j]$. Recall that each number
$M_{i}[j]$, for $j\in[0..\lceil\log^{(4)}n\rceil]$, is at most
$\mathcal{O}(\log^{(3)}n)$. Therefore, the new value for $M_{i}[j]$ is
determined by the old value $M_{i}[j]$ and the subarray
$A[i..i{+}\mathcal{O}(\log^{(3)}n)]$, for an appropriate constant under the
big-O. By storing the bit array $A$ in a sequence of $\mathcal{O}(1+|R|/\log
n)$ machine words of size $\Theta(\log n)$ bits, we can retrieve and pack the
subarray $A[i..i{+}\mathcal{O}(\log^{(3)}n)]$ in $\mathcal{O}(1)$ time into
one machine word and can concatenate the subarray to the bit representation of
the whole $M_{i}$. The bit representation of $M_{i}$ takes
$\mathcal{O}((\log^{(4)}n)^{2})$ and, thus, the resulting chunk after the
concatenation occupies
$\mathcal{O}((\log^{(4)}n)^{2})+\mathcal{O}(\log^{(3)}n)=\mathcal{O}(\log^{(3)}n)$
bits. We view this chunk storing the concatenated bit representations of
$M_{i}[0..\lceil\log^{(4)}n\rceil]$ and $A[i..i{+}\mathcal{O}(\log^{(3)}n)]$
as an integer number $x$ with $\mathcal{O}(\log^{(3)}n)$ bits. It is clear
that the chunk determines the state of the updated array $M_{i}$. Therefore,
we can in advance before the start of the whole algorithm consider all
possible valid chunks that encode in the same way arrays
$M[0..\lceil\log^{(4)}n\rceil]$ with entries of size
$\mathcal{O}(\log^{(4)}n)$ bits concatenated with bit arrays of length
$\mathcal{O}(\log^{(3)}n)$ and we can precalculate the updated arrays $M$ in a
table $B$ so that the updated array $M_{i}$ is already stored in the entry
$B[x]$. Thus, we simply read $B[x]$, which contains a bit representation for
the updated array $M_{i}$ occupying $\mathcal{O}((\log^{(4)}n)^{2})$ bits, and
we rewrite $M_{i}$ with the content of $B[x]$. All is done $\mathcal{O}(1)$
time since all the bit representations take only $\mathcal{O}(1)$ machine
words. The size of the table $B$ is
$\mathcal{O}(2^{\mathcal{O}(\log^{(3)}n)}\cdot(\log^{(4)}n)^{2})=o(\log n)$
bits and, hence, all precalculations can be performed in $o(n)$ time with
$\mathcal{O}(1)$ space (the space is measured in $\mathcal{O}(\log n)$-bit
machine words).

#### Part (i).

Let us describe how the set $S^{\prime}$ is produced in $\mathcal{O}(n)$ time
from the set $S$, which is fed to our algorithm from left to right in an
online fashion. The naïve procedure, for each position $p\in S$, collects all
positions from the set $S\cap(p..p{+}\tau/4]$ and compares $s[p..p{+}\tau/2]$
to each of the substrings $s[q..q{+}\tau/2]$ with $q\in S\cap(p..p{+}\tau/4]$;
if $s[p..p{+}\tau/2]=s[q..q{+}\tau/2]$, then all the positions $S\cap(p..q]$
are marked for removal and, thus, will not be reported into $S^{\prime}$. The
idea of a faster solution is that all the comparisons in this algorithm, for
the given $p$, are performed inside a very short substring
$s[p..p{+}\tau/4+\tau/2]$ (recall that $\tau<(\log^{(3)}n)^{4}$); we therefore
can pack all this string into one small chunk that fits into one machine word
specifying which of its positions are from $S$ and, then, we perform the
marking for removal in $\mathcal{O}(1)$ time using a precomputed answer. The
issue with this idea is that the alphabet can be quite large so that the
packing is impossible.

A solution is to “reduce” the alphabet for the substring
$s[p..p{+}\tau/4+\tau/2]$ by sorting all letters and substituting them by
their ordering numbers. The sorting can be performed in linear time using
fusion trees [16, 35]. More precisely, during the left-to-right processing of
$S$, we consecutively consider (overlapping) substrings
$s[i\tau..(i{+}2)\tau]$, for $i\in[0..n/\tau-2]$. Using the fusion tree, we
can sort all letters of a given substring $s[i\tau..(i{+}2)\tau]$ in
$\mathcal{O}(\tau)$ time assigning to them their ordering numbers, i.e.,
reducing the alphabet to $[0..2\tau]$ (see [16, 35]; note that we have
$\Omega(n/\tau)=\Omega(n/\log n)$ space). Denote by $\hat{s}_{i}$ the string
$s[i\tau..(i{+}2)\tau]$ with letters substituted by the ordering numbers (so
that all new letters are from $[0..2\tau]$). The string $\hat{s}$ occupies
$\mathcal{O}(\tau\log\tau)=o((\log^{(3)}n)^{5})$ bits and, thus, can be packed
into one machine word. Now in order to process $p\in S$, we first check
whether the substring $s[p..p{+}\tau/4{+}\tau/2]$ is contained in the last
preprocessed substring $\hat{s}_{i}$. If not, we set $i=\lfloor p/\tau\rfloor$
and preprocess $s[i\tau..(i{+}2)\tau]$ in $\mathcal{O}(\tau)$ time generating
$\hat{s}_{i}$. Note that in this way we never preprocess the same substring
$s[i\tau..(i{+}2)\tau]$ twice since the positions $p\in S$ are fed to our
algorithm from left to right. Next, using standard bit operations on the
machine word containing $\hat{s}_{i}$, we retrieve the substring
$s[p..p{+}\tau/4{+}\tau/2]$ from the string $s[i\tau..(i{+}2)\tau]$ encoded in
$\hat{s}_{i}$ in which the alphabet is “reduced”, i.e., all letters are
substituted with numbers from $[0..2\tau]$. The retrieved substring occupies
$\mathcal{O}(\tau\log\tau)$ bits and is stored in one machine word. We
concatenate to the bit representation of this substring a bit array $a$ of
length $\tau/4$ that indicates which of the positions
$i+1,i+2,\ldots,i+\tau/4$ belong to $S$: for $h\in(0..\tau/4]$, we have
$i+h\in S$ iff $a[h-1]=1$. The bit array $a$ is easy to maintain in one
machine word during the execution of the algorithm using the bit shift
operations. Thus, we obtain a chunk of
$\mathcal{O}(\tau\log\tau)+\tau/4=o((\log^{(3)}n)^{5})$ bits that encodes the
concatenated bit representations of the substring $s[p..p{+}\tau/4{+}\tau/2]$,
with a “reduced” alphabet, and of the bit array $a$, indicating all positions
from $S\cap(p..p{+}\tau/4]$. We view this chunk as an integer number $x$ with
$o((\log^{(3)}n)^{5})$ bits.

Clearly, the chunk $x$ determines which of the positions from
$S\cap(p..p{+}\tau/4]$ should be marked for removal during the processing of
$p$. Therefore, we can in advance before the start of the whole algorithm
consider all possible valid chunks that encode in the same way strings
$t[0..\tau/2+\tau/4]$ over the alphabet $[0..2\tau]$ concatenated with bit
arrays of length $\tau/4$ and we can precalculate which of the positions from
$S\cap(p..p{+}\tau/4]$ will be marked for removal in a table $C$ so that the
entry $C[x]$ stores a bit array $c$ of length $\tau/4$ that “masks” positions
for removal: for $h\in(0..\tau/4]$, $c[h-1]=0$ iff the position $q\in
S\cap(p..p{+}\tau/4]$ such that $|S\cap(p..q]|=h$ must be marked for removal
because there exists $q^{\prime}\in S\cap[q..p{+}\tau/4]$ such that
$s[p..p{+}\tau/2]=s[q^{\prime}..q^{\prime}{+}\tau/2]$. Thus, we simply read
$C[x]$ and apply the masking array stored in $C[x]$ to mark for removal some
positions from $S$ after $p$.

Thus, the processing of $p\in S$ is done in $\mathcal{O}(1)$ time since all
the bit representations take only $\mathcal{O}(1)$ machine words. The total
time for processing all substrings $s[i\tau..(i{+}2)\tau]$, for
$i\in[0..n/\tau-2]$, is $\mathcal{O}(\frac{n}{\tau}\tau)=\mathcal{O}(n)$. The
size of the table $C$ is
$\mathcal{O}(2^{o((\log^{(3)}n)^{5})}\cdot\tau)=o(\log n)$ bits and, hence,
all precalculations can be performed in $o(n)$ time with $\mathcal{O}(1)$
space. As in the original algorithm from Section 5, the computation of
$S^{\prime}$ is executed in an online manner reporting its positions from left
to right without storing them (only few are stored for internal purposes).

#### Part (ii).

Let us describe now how the string $R$ can be computed from the set
$S^{\prime}$, which is fed to our algorithm from left to right in an online
fashion. The idea is very similar to what was done for Part (i) to produce the
set $S^{\prime}$ from $S$. The algorithm starts with an empty string $R$ and
considers all $p\in S^{\prime}$ from left to right generating, for each $p\in
S^{\prime}$, a letter $a_{p}$ that is then appended to the end of the string
$R$. As is evident from Lemma 14, the construction of $a_{p}$ requires only
the substring $s[p..p{+}\frac{7}{8}\tau]$ and the positions
$S^{\prime}\cap(p..p{+}\frac{7}{8}\tau]$. At first glance, the same trick can
be applied as in Part (i): we consecutively consider substrings
$s[i\tau..(i{+}2)\tau]$, for $i\in[0..n/\tau-2]$, reducing their alphabets to
$[0..2\tau]$ and encoding them into chunks $\hat{s}_{i}$ of
$\mathcal{O}(\tau\log\tau)$ bits; when a position $p\in S^{\prime}$ arrives,
we retrieve the substring $s[p..p{+}\frac{7}{8}\tau]$ with a reduced alphabet
from the chunk $\hat{s}_{i}$ with $i=\lfloor p/\tau\rfloor$, constructing
$\hat{s}_{i}$ from scratch if it was not built previously, and then, we
concatenate to the chunk a bit array of length $\mathcal{O}(\tau)$ indicating
which of the positions from $(p..p{+}\frac{7}{8}\tau]$ belong to $S^{\prime}$.
Unfortunately, this scheme does not work since the alphabet reductions loose
some essential information required to construct the letters $a_{p}$.
Precalculations therefore are more involved.

Denote by $p_{1},p_{2},\ldots,p_{m}$ the set of all positions from
$S^{\prime}\cap(p..p{+}\tau/2^{5}]$ in increasing order. Recall that the
procedure of Section 5 first generates for $p$ a tuple of numbers $\langle
w^{\prime}_{1},w^{\prime}_{2},\ldots,w^{\prime}_{\ell}\rangle$: for
$j\in[1..\ell]$, $w^{\prime}_{j}=\mathop{\mathsf{vbit}}(t,t_{j})$ if $j\leq
m$, and $w^{\prime}_{j}=\infty$ otherwise, where
$t=\sum_{i=0}^{\tau/2}s[p{+}i]2^{wi}$ and
$t_{j}=\sum_{i=0}^{\tau/2}s[p_{j}{+}i]2^{wi}$, for $j\in[1..m]$. The numbers
$t$ and $t_{j}$ simply represent the substrings $s[p..p{+}\tau/2]$ and
$s[p_{j}..p_{j}{+}\tau/2]$. In order to compute
$\mathop{\mathsf{vbit}}(t,t_{j})$, it suffices to find the length $L$ of the
longest common prefix of $s[p..p{+}\tau/2]$ and $s[p_{j}..p_{j}{+}\tau/2]$
and, then, compute the lowest bit at which the numbers $s[p{+}L]$ and
$s[p_{j}{+}L]$ differ and which of these numbers has 0 and 1 in this differing
bit. While the length $L$ can be computed on the substring
$s[p..p{+}\frac{7}{8}\tau]$ with a reduced alphabet, the information about the
bits at which the numbers $s[p{+}L]$ and $s[p_{j}{+}L]$ differ is lost after
the alphabet reduction. However, it turns out that this information can be
stored too in small space without the need to preserve the numbers $s[p{+}L]$
and $s[p_{j}{+}L]$ themselves.

Consider the procedure reducing the alphabet for a substring
$s[i\tau..(i{+}2)\tau]$ with $i\in[0..n/\tau-2]$. The procedure sorts all
letters assigning to them ordering numbers from $[0..2\tau]$. Denote by
$b_{0},b_{1},\ldots,b_{k-1}$ all distinct letters of $s[i\tau..(i{+}2)\tau]$
in increasing order before the reduction. Each letter $b_{i}$ is an
$\mathcal{O}(\log n)$-bit number that is mapped by the reduction to its index
$i$. Each number $b_{i}$ can be represented as a bit string $\bar{b}_{i}$ of
length $\mathcal{O}(\log n)$ in which the bits are written from the lowest to
the highest. We can construct a compacted trie on the strings $\bar{b}_{i}$.
Since $k\leq 2\tau+1$, the compacted trie can be stored in
$\mathcal{O}(\tau\log\log n)$ bits: every edge in the trie stores the length
of the bit string written on it (which takes $\mathcal{O}(\log\log n)$ bits),
each internal node contains pointers to its children (taking
$\mathcal{O}(\log\tau)$ bits since the number of nodes is
$\mathcal{O}(\tau)$), and each leaf stores the index $i$ of the corresponding
number $b_{i}$ (taking $\mathcal{O}(\log\tau)$ bits). The compacted trie can
be built in $\mathcal{O}(k)$ time using a fusion tree [16]; in fact, the
fusion tree on the numbers $b_{0},b_{1},\ldots,b_{k-1}$ implicitly constructs
precisely this trie (see also [9, 21] where this is emphasized more
explicitly). Our idea is that we do not have to store the numbers
$b_{0},b_{0},\ldots,b_{k-1}$ in addition to the trie in order to find the
lowest bit at which two numbers $b_{i}$ and $b_{i^{\prime}}$ differ: the bit
corresponds precisely to the position in the compacted trie at which the
corresponding strings $\bar{b}_{i}$ and $\bar{b}_{i^{\prime}}$ diverge.

By analogy to the solution for Part (i), when processing $p\in S^{\prime}$, we
first retrieve the substring $s[p..p{+}\frac{7}{8}\tau]$ with a reduced
alphabet from the string $s[i\tau..(i{+}2)\tau]$ with $i=\lfloor
p/\tau\rfloor$ encoded in $\hat{s}_{i}$. Then, we concatenate to the bit
representation of this substring a bit array $a$ of length
$\lfloor\frac{7}{8}\tau\rfloor$ that indicates which of the positions
$i+1,i+2,\ldots,i+\lfloor\frac{7}{8}\tau\rfloor$ belong to $S^{\prime}$: for
$h\in(0..\frac{7}{8}\tau]$, we have $i+h\in S^{\prime}$ iff $a[h-1]=1$. The
bit array $a$ is easy to maintain in one machine word during the execution of
the algorithm using the bit shift operation. Next, we concatenate to the
resulting bit chunk a bit representation of the compacted trie on the bit
strings $\bar{b}_{0},\bar{b}_{1},\ldots,\bar{b}_{k-1}$ (without storing the
letters $b_{0},b_{0},\ldots,b_{k-1}$ themselves), which adds more
$\mathcal{O}(\tau\log\log n)$ bits. Thus, we obtain a chunk of
$\mathcal{O}(\tau\log\tau)+\frac{7}{8}\tau+\mathcal{O}(\tau\log\log
n)=\mathcal{O}((\log^{(3)}n)^{4}\log\log n)$ bits that encodes the
concatenated bit representations of the substring $s[p..p{+}\frac{7}{8}\tau]$
with a reduced alphabet, of the bit array $a$ indicating all positions from
$S^{\prime}\cap(p..p{+}\frac{7}{8}\tau]$, and of the compacted trie. We view
this chunk as an integer number $x$ with
$\mathcal{O}((\log^{(3)}n)^{4}\log\log n)$ bits.

The chunk $x$ determines the letter $a_{p}$. Indeed, in order to compute the
letter, we first have to compute the numbers
$w^{\prime}_{j}=\mathop{\mathsf{vbit}}(t,t_{j})$: this can be done by first
computing the length $L$ of the longest common prefix of the corresponding
substrings of $s[p..p{+}\frac{7}{8}\tau]$ at positions $p$ and $p_{j}$ and,
then, by finding the lowest differing bit of the numbers $s[p{+}L]$ and
$s[p_{j}{+}L]$, which can be performed using the compacted trie; similar
computations should be executed for other positions from
$S^{\prime}\cap(p..p{+}\frac{7}{8}]$ but all of them involve only substrings
of the string $s[p..p{+}\frac{7}{8}\tau]$, due to Lemma 14. All further
computations can be executed as described in Section 5. Instead of performing
all this from scratch, we can in advance consider all possible valid chunks
that encode in the same way strings $t[0..\frac{7}{8}\tau]$ over the alphabet
$[0..2\tau]$ concatenated with bit arrays of length $\frac{7}{8}\tau$ and with
compacted tries on $\mathcal{O}(\tau)$ bit strings of length $\mathcal{O}(\log
n)$ (without storing the $\mathcal{O}(\tau)$ strings themselves); for each
such chunk, we precalculate the resulting letter in a table $D$ so that the
entry $D[x]$ stores $a_{p}$. Thus, we simply read $D[x]$ and append it to $R$.

The processing of $p\in S$ is done in $\mathcal{O}(1)$ time since all the bit
representations take only $\mathcal{O}(1)$ machine words. The total time for
processing all substrings $s[i\tau..(i{+}2)\tau]$, for $i\in[0..n/\tau-2]$, is
$\mathcal{O}(\frac{n}{\tau}\tau)=\mathcal{O}(n)$. The size of the table $D$ is
$\mathcal{O}(2^{\mathcal{O}((\log^{(3)}n)^{4}\log\log
n)}\cdot(\log^{(3)}n)^{2})$ bits, which fits into $\mathcal{O}(n/\tau)$ space
provided $\tau<(\log^{(3)}n)^{4}$ as can be easily seen since
$\log(n/\tau)=\Theta(\log n)$ whereas the logarithm of the space for $D$ is
$o(\log\log n)$. Hence, all precalculations can be performed in $o(n)$ time
within $\mathcal{O}(n/\tau)$ space.

#### Part (iii).

It remains to describe how all the arrays $M_{i}[0..\lceil\log^{(4)}n\rceil]$
can be initialized in $\mathcal{O}(|S^{\prime}|)$ time. Given a letter $R[i]$
and a position $p\in S^{\prime}$ corresponding to it, recall that $M_{i}[j]$,
for $j\in[0..\lceil\log^{(4)}n\rceil]$, is equal to the size of the set
$S^{\prime}\cap(p..p{+}\tau/2^{j}]$. We receive positions $p$ of $S^{\prime}$
from left to right and, using the bit shift operation, maintain along the way
a bit array $a$ of length $\tau$ that is stored in a machine word $x$ of size
$\mathcal{O}(\log n)$ bits such that $a$ indicates which of the positions of
$(p..p{+}\tau]$ are from $S^{\prime}$, i.e., for $h\in(0..\tau]$, we have
$p+h\in S^{\prime}$ iff $a[h-1]=1$. Obviously, the array $a$ determines the
content of $M_{i}$. The array $M_{i}$ occupies
$\mathcal{O}((\log^{(4)}n)^{2})$ bits and, therefore, its bit representation
can be stored into one machine word. We hence can precompute a table $F$ of
size $\mathcal{O}(2^{\tau}\cdot(\log^{(4)}n)^{2})=o(\log n)$ bits such that
$F[x]$ stores the bit representation of the array $M_{i}$. The content of
$F[x]$ is then copied in $\mathcal{O}(1)$ time in place of $M_{i}$. The table
$F$ can be straightforwardly precalculated in $o(n)$ time and $\mathcal{O}(1)$
space.

## References

  * [1] S. Alstrup, G. S. Brodal, T. Rauhe, Pattern matching in dynamic texts, in: Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2000.
  * [2] V. Arlazarov, E. Dinic, M. Kronrod, I. Faradzev, On economical construction of the transitive closure of a directed graph, Dokl. Akad. Nauk. 194 (11) (1970) 1209–1210.
  * [3] J. L. Bentley, R. Sedgewick, Fast algorithms for sorting and searching strings, in: Proc. the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 1997\.
  * [4] P. Bille, J. Fischer, I. Gørtz, T. Kopelowitz, B. Sach, H. W. Vildhøj, Sparse text indexing in small space, ACM Transactions on Algorithms 12 (3) (2016) 1–19.
  * [5] P. Bille, I. L. Gørtz, M. B. T. Knudsen, M. Lewenstein, H. W. Vildhøj, Longest common extensions in sublinear space, in: Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM), vol. 9133 of LNCS, Springer, 2015.
  * [6] P. Bille, I. L. Gørtz, B. Sach, H. W. Vildhøj, Time-space trade-offs for longest common extensions, Journal of Discrete Algorithms 25 (2014) 42–50.
  * [7] O. Birenzwige, S. Golan, E. Porat, Locally consistent parsing for text indexing in small space, in: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2020.
  * [8] G. S. Brodal, P. Davoodi, S. S. Rao, On space efficient two dimensional range minimum data structures, in: Proc. 18th Annual European Symposium on Algorithms (ESA), vol. 6347 of LNCS, Springer, 2010.
  * [9] T. M. Chan, K. G. Larsen, M. Pătraşcu, Orthogonal range searching on the RAM, revisited, in: Proc. 27th Annual Symposium on Computational Geometry (SoCG), ACM, 2011.
  * [10] R. Cole, U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control 70 (1) (1986) 32–53.
  * [11] M. Crochemore, W. Rytter, Squares, cubes, and time-space efficient string searching, Algorithmica 13 (5) (1995) 405–425.
  * [12] P. Dinklage, J. Fischer, A. Herlez, T. Kociumaka, F. Kurpicz, Practical performance of space efficient data structures for longest common extensions, in: Proc. 28th Annual European Symposium on Algorithms (ESA), vol. 173 of LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020.
  * [13] M. Farach, Optimal suffix tree construction with large alphabets, in: Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 1997.
  * [14] N. J. Fine, H. S. Wilf, Uniqueness theorems for periodic functions, Proc. American Mathematical Society (AMS) 16 (1) (1965) 109–114.
  * [15] J. Fischer, T. I, D. Köppl, Deterministic sparse suffix sorting on rewritable texts, in: Proc. 12th Latin American Symposium on Theoretical Informatics (LATIN), vol. 9644 of LNCS, Springer, 2016.
  * [16] M. L. Fredman, D. E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences 47 (3) (1993) 424–436.
  * [17] M. Gańczorz, P. Gawrychowski, A. Jeż, T. Kociumaka, Edit distance with block operations, in: Proc. 26th Annual European Symposium on Algorithms (ESA), vol. 112 of LIPIcs, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018\.
  * [18] P. Gawrychowski, A. Karczmarz, T. Kociumaka, J. Łącki, P. Sankowski, Optimal dynamic strings, in: Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2018.
  * [19] P. Gawrychowski, T. Kociumaka, Sparse suffix tree construction in optimal time and space, in: Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2017.
  * [20] A. Goldberg, S. Plotkin, G. Shannon, Parallel symmetry-breaking in sparse graphs, in: Proc. 19th Annual ACM Symposium on Theory of Computing (STOC), ACM, 1987.
  * [21] R. Grossi, A. Orlandi, R. Raman, S. S. Rao, More haste, less waste: Lowering the redundancy in fully indexable dictionaries, in: 26th International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 3 of LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2009\.
  * [22] D. Harel, R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing 13 (2) (1984) 338–355.
  * [23] T. I, Longest common extensions with recompression, in: Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM), vol. 78 of LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017.
  * [24] T. I, J. Kärkkäinen, D. Kempa, Faster sparse suffix sorting, in: Proc. 31st International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 25 of LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2014.
  * [25] A. Jeż, Approximation of grammar-based compression via recompression, Theoretical Computer Science 592 (2015) 115–134.
  * [26] A. Jeż, Faster fully compressed pattern matching by recompression, ACM Transactions on Algorithms 11 (3) (2015) 20.
  * [27] A. Jeż, A really simple approximation of smallest grammar, Theoretical Computer Science 616 (2016) 141–150.
  * [28] A. Jeż, Recompression: a simple and powerful technique for word equations, Journal of the ACM 63 (1) (2016) 4.
  * [29] J. Kärkkäinen, P. Sanders, S. Burkhardt, Linear work suffix array construction, Journal of the ACM 53 (6) (2006) 918–936.
  * [30] J. Kärkkäinen, E. Ukkonen, Lempel–Ziv parsing and sublinear-size index structures for string matching, in: Proc. 3rd South American Workshop on String Processing (WSP), Carleton University Press, 1996.
  * [31] D. Kempa, T. Kociumaka, String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure, in: Proc. 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), ACM, 2019.
  * [32] D. Kosolobov, Tight lower bounds for the longest common extension problem, Information Processing Letters 125 (2017) 26–29.
  * [33] K. Mehlhorn, R. Sundar, C. Uhrig, Maintaining dynamic sequences under equality tests in polylogarithmic time, Algorithmica 17 (2) (1997) 183–198.
  * [34] T. Nishimoto, T. I, S. Inenaga, H. Bannai, M. Takeda, Dynamic index and LZ factorization in compressed space, Discrete Applied Mathematics 274 (2020) 116–129.
  * [35] M. Patrascu, M. Thorup, Dynamic integer sets with optimal rank, select, and predecessor search, in: Proc. 55th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2014.
  * [36] N. Prezza, Optimal substring equality queries with applications to sparse text indexing, ACM Transactions on Algorithms 17 (1) (2020) 1–23.
  * [37] M. Roberts, W. Hayes, B. R. Hunt, S. M. Mount, J. A. Yorke, Reducing storage requirements for biological sequence comparison, Bioinformatics 20 (18) (2004) 3363–3369.
  * [38] S. C. Sahinalp, U. Vishkin, Symmetry breaking for suffix tree construction, in: Proc. 26th Annual ACM Symposium on Theory of Computing (STOC), ACM, 1994.
  * [39] S. Schleimer, D. S. Wilkerson, A. Aiken, Winnowing: local algorithms for document fingerprinting, in: Proc. ACM SIGMOD International Conference on Management of Data, 2003.
  * [40] Y. Tanimura, T. I, H. Bannai, S. Inenaga, S. Puglisi, M. Takeda, Deterministic sub-linear space LCE data structures with efficient construction, in: Proc. 27th Annual Symposium on Combinatorial Pattern Matching (CPM), vol. 54 of LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2016\.
  * [41] Y. Tanimura, T. Nishimoto, H. Bannai, S. Inenaga, M. Takeda, Small-Space LCE Data Structure with Constant-Time Queries, in: Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), vol. 83 of LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017\.
  * [42] D. E. Willard, Log-logarithmic worst-case range queries are possible in space $\Theta$(N), Information Processing Letters 17 (2) (1983) 81–84.