#  Breakup corrections to spin asymmetries in the 3He beam polarization
measurement with the Polarized Atomic Hydrogen Gas Jet Target

A. A. Poblaguev<EMAIL_ADDRESS>Brookhaven National Laboratory, Upton, New
York 11973, USA

(August 2, 2023)

###### Abstract

The requirements for hadron polarimetry at the future Electron-Ion Collider
(EIC) include measurements of the absolute helion (3He, $h$) beam polarization
with systematic uncertainties better than $\sigma^{\text{syst}}_{P}/P\leq
1\%$. Recently, it was proposed that the Polarized Atomic Hydrogen Gas Jet
Target (HJET) be utilized for the precision measurement of the polarization of
the $\approx$100 GeV/n helion beam. At the Relativistic Heavy Ion Collider,
HJET serves to determine the absolute proton beam polarization with low
systematic uncertainties of about $\delta^{\text{syst}}P/P\lesssim 0.5\%$. To
adapt the HJET method for the EIC helion beam, the experimentally determined
ratio of the beam and target (jet) spin-correlated asymmetries should be
adjusted by the ratio of $p^{\uparrow}{h}$ and $h^{\uparrow}{p}$ analyzing
powers. A potential problem with the suggested method is that the breakup of
3He in polarization measurements could drastically affect the analyzing power
ratio. However, an analysis of the breakup corrections, presented in this
paper, reveals that while these corrections can be as substantial as
$\approx\\!4\%$, the effect cancels out to a negligible level in the measured
beam polarization.

##  I Introduction

The physics program requirements [1] for hadron polarimetry at the Electron-
Ion Collider (EIC) [2] include the precise determination of the 3He
($A_{h}\\!=\\!3$, $Z_{h}\\!=\\!2$) beam polarization,

$\sigma_{P}^{\text{syst}}/P\lesssim 1\%.$ (1)

It has been advocated [3, 4] that the Atomic Polarized Hydrogen Gas Jet Target
(HJET) [5] can be used for this purpose.

In the Relativistic Heavy Ion Collider, HJET is employed to measure the
absolute transverse (vertical) polarization of the proton beams with a low
systematic uncertainty of about $\sigma_{P}^{\text{syst}}/P\lesssim 0.5\%$
[6]. Recoil protons from the RHIC beam scattering off the jet target are
counted in left-right symmetric Si strip detectors. The HJET geometry
predetermines the detection of the recoil protons only in the Coulomb-nuclear
interference (CNI) scattering constrained by

$0.0013<-t<0.018\,\rm{GeV}^{2}.$ (2)

The Lorentz-invariant momentum transfer $t$ can be simply related to the
recoil proton energy $T_{R}$,

$-t=2m_{p}T_{R},$ (3)

where $m_{p}$ is the recoil particle (proton) mass.

The 3He beam polarization $P_{h}$ can be related [3] to the precisely known
jet target polarization, $P_{\text{jet}}\\!\approx\\!0.96\\!\pm\\!0.001$ [5],
as

$P_{\text{meas}}(T_{R})=P_{\text{jet}}\frac{a_{\text{beam}}(T_{R})}{a_{\text{jet}}(T_{R})}\times{\cal
R}_{h}(T_{R}),$ (4)

where $a_{\text{beam}}(T_{R})$ and $a_{\text{jet}}(T_{R})$ are experimentally
determined beam and target (jet) spin asymmetries [6], respectively. The ratio
of the proton ($p^{\uparrow}{}h$) and helion ($h^{\uparrow}{}p$) spin
analyzing powers [7] is denoted by

${\cal
R}_{h}(T_{R})=\frac{A_{\text{N}}^{ph}(T_{R})}{A_{\text{N}}^{hp}(T_{R})}=\frac{\kappa_{p}-2I_{5}^{ph}-2R_{5}^{ph}\,T_{R}/T_{c}}{\kappa_{h}-2I_{5}^{hp}-2R_{5}^{hp}\,T_{R}/T_{c}},$
(5)

where $\kappa_{p}\\!=\\!\mu_{p}\\!-\\!1\\!=\\!1.793$ and
$\kappa_{h}\\!=\\!\mu_{h}/Z_{h}\\!-\\!m_{p}/m_{h}\\!=\\!-1.398$ [8] are
derived from the magnetic moments of the proton and helion,
$T_{c}\\!=\\!4\pi\alpha{Z_{h}}/m_{p}\sigma_{\text{tot}}^{ph}\\!\approx\\!0.7\,\text{MeV}$,
and $\sigma_{\text{tot}}^{ph}$ is the total $\mathit{ph}$ cross section. The
hadronic spin-flip amplitude parameters $r_{5}\\!=\\!R_{5}\\!+\\!iI_{5}$ for
$p^{\uparrow}h$ and $h^{\uparrow}p$ can be calculated [9, 10, 4] with
sufficient accuracy, $r_{5}^{ph}\\!\approx\\!r_{5}^{pp}$ and
$r_{5}^{hp}\\!\approx\\!r_{5}^{pp}/3$, using the proton-proton value
$r_{5}^{pp}$ ($|r_{5}^{pp}|\\!\sim\\!0.02$) measured at HJET [11].

For the calculated beam polarization $P_{h}$, the systematic errors due to
possible uncertainties in values of $R_{5}$ and $T_{c}$ can be eliminated if
the measured polarization $P_{\text{meas}}(T_{R})$ is extrapolated to
$T_{R}\\!\to\\!0$,

$\displaystyle P_{\text{meas}}(T_{R})$
$\displaystyle=P_{h}\times\left[1+\xi(T_{R})\right],$ (6)
$\displaystyle\xi(T_{R})$ $\displaystyle=\xi_{0}+\xi_{1}T_{R}/T_{c}+\ldots.$
(7)

The right-hand side of Eq. (5) displays only the leading-order approximation
of the interference terms in the numerator of the CNI elastic analyzing power
expression [7]:

$A_{\text{N}}(t)\\!\;{=}\\!\;\frac{-2\operatorname{Im}\left[\phi_{5}^{\text{em}}\phi_{+}^{\text{had\,*}}\\!+\phi_{5}^{\text{had}}\phi_{+}^{\text{em\,*}}\\!+\phi_{5}^{\text{had}}\phi_{+}^{\text{had\,*}}\right]}{|\phi_{+}^{\text{had}}\\!+\\!\phi_{+}^{\text{em}}|^{2}}.$
(8)

Here, $\phi_{5}$ and $\phi_{+}$ are spin-flip and nonflip helicity amplitudes,
the hadronic and electromagnetic parts of which are denoted by “had” and “em”.

3He breakup in the scattering can effectively alter the (elastic) interference
terms

$\left\\{\operatorname{Im}\phi_{5}\phi_{+}^{*}\right\\}_{I}\to\left\\{\operatorname{Im}\phi_{5}\phi_{+}^{*}\right\\}_{I}\times\left[1+\omega_{I}(T_{R})\right]$
(9)

(schematically discriminated by index $I$) and, consequently, results in a
systematic error in the measured $P_{h}$.

A breakup correction,

$\left|\phi_{+}^{\text{had}}\right|^{2}\
\to\left|\phi_{+}^{\text{had}}\right|^{2}\times[1\\!+\\!\omega(t)],$ (10)

to the $pd$ cross section was evaluated in Ref. [4], using experimental data
obtained in the unpolarized deuteron ($d$) beam measurements in HJET.
Extrapolating the result obtained to the 3He beam scattering, the breakup
related systematic error in measured $P_{h}$ was found to be negligible.

However, it was underlined in Ref. [4] that an oversimplified and unjustified
theoretical model was used to interpret the deuteron data and to make the
extrapolation. Additionally, some assumptions used in the data analysis were
not reliably verified.

Although the conclusion drawn in Ref. [4] was found to be stable against
possible variations of the model used, a more comprehensive analysis is
necessary for considering HJET in precision ${}3$He polarimetry at EIC.

In this paper, the breakup fraction estimated in Ref. [4] is compared with the
${dp}$ and ${hp}$ scattering study results in the hydrogen bubble-chamber
experiment [12, 13]. The HJET and bubble-chamber results were found to be in
fair consistency within the experimental accuracy of the measurements. No
evidence was found that the breakup fraction given in Ref. [4] was
underestimated therein.

Following basic principles of the Glauber theory [14, *Glauber:1959], it can
be readily shown that for high-energy polarized proton scattering off a
nucleus target, both elastic and breakup, the ratio of hadronic spin-flip and
nonflip amplitudes is the same as for $p^{\uparrow}p$ scattering. It also was
found that for high-energy forward $p^{\uparrow}h$ and $h^{\uparrow}p$
scattering, breakup corrections $\omega_{I}(t)$ to the interference terms
$\phi_{5}^{\text{em}}\phi_{+}^{\text{had\,*}}$,
$\phi_{5}^{\text{had}}\phi_{+}^{\text{em\,*}}$,
$\phi_{5}^{\text{had}}\phi_{+}^{\text{had\,*}}$ are the same, within a
relative accuracy of about 10 – 20%, as the correction $\omega(t)$ to the
cross-section term $|\phi_{+}^{\text{had}}|^{2}$.

The analysis carried out here improves the confidence of the conclusion
reached in Ref. [4] that the EIC 3He beam polarization can be measured by HJET
with low systematic uncertainty (1).

##  II The Breakup Fraction in the HJET 2H and 3He Beam Elastic Data

###  II.1 A Model Used to Isolate the Breakup Events

Considering the breakup $A(p,p)X$ reaction as elastic scattering of a nucleon
cluster in the nucleus off the jet proton, one can relate [4] the missing mass
excess $\Delta=m_{X}-m_{A}$ to the recoil proton energy:

$\Delta=\left(1-\frac{m^{*}}{m_{A}}\right)T_{R}+p_{x}\sqrt{\frac{2T_{R}}{m_{p}}},$
(11)

where $m^{*}$ is the nucleon cluster mass and $p_{x}$ is the internal motion’s
transverse momentum of the cluster in the direction of the detector. Since
only low-energy recoil protons ($T_{R}\lesssim 10\,\text{MeV}$) can be
detected at HJET, $\Delta$ is much less than $m_{A}$. This indicates that the
breakup event rate for this process would be strongly suppressed by the phase-
space factor.

Obviously, for the deuteron beam, $m^{*}\\!=\\!m_{p}$. Assuming that the
$p_{x}$ distribution in a deuteron is given by a unity integral normalized
Breit – Wigner function

$f_{\text{BW}}(p_{x},\sigma_{p})=\frac{\pi^{-1}\,\sqrt{2}\sigma_{p}}{p_{x}^{2}+2\sigma_{p}^{2}},$
(12)

the $d\to pn$ breakup fraction $\omega(T_{R},\Delta)$ can be found [4] as a
convolution of the $\Delta$ distribution, calculated in accordance with Eq.
(11), and the phase-space integral (calculated as a function of $\Delta$),

$\displaystyle\omega(T_{R},\Delta)=\frac{d^{2}\sigma_{\text{brk}}(T_{R},\Delta)}{d\sigma_{\text{el}}(T_{R})\,d\Delta}=\frac{\sqrt{2m_{p}m_{n}}}{4\pi
m_{d}}$
$\displaystyle\qquad\times|\bar{\psi}(T_{R},\Delta)|^{2}f_{\text{BW}}(\Delta\\!-\\!\Delta_{0},\sigma_{\Delta})\sqrt{\frac{\Delta\\!-\\!\Delta^{d}_{\text{thr}}}{m_{d}}},$
(13)
$\displaystyle\Delta_{0}=(1-m_{p}/m_{d})T_{R},\qquad\sigma^{2}_{\Delta}=2\sigma_{p}^{2}T_{R}/m_{p}.$
(14)

Since the key dependence of the breakup amplitude on $T_{R}$ and $\Delta$ is
allocated in the function $f_{\text{BW}}$, $\bar{\psi}(T_{R},\Delta)$ should
be interpreted as a reduced ratio of the breakup to elastic amplitudes.
Therefore, for HJET measurements, i.e., for low $T_{R}$ and $\Delta$,
$\bar{\psi}(T_{R},\Delta)$ can be substituted by a constant
$\bar{\psi}\\!\equiv\\!\bar{\psi}(0,0)$. For the $d\\!\to\\!pn$ breakup, the
threshold is
$\Delta^{d}_{\text{thr}}\\!=\\!m_{p}\\!+\\!m_{n}\\!-\\!m_{d}\\!=\\!2.2\,\text{MeV}$.

Integrating over $\Delta$, one can calculate the breakup fraction
$\omega(T_{R})$, as a function of the recoil proton energy, in the elastic
data.

###  II.2 The Deuteron Beam Breakup in HJET

In RHIC Run 16 deuteron – gold collisions were studied at several beam
energies. Since HJET operated in this unpolarized ion Run, the deuteron beam
breakup fraction was experimentally evaluated. The measurements had been done
in the recoil proton kinetic-energy range
$2.8\\!<\\!T_{R}\\!<\\!4.2\,\text{MeV}$, and in the data fit, it was estimated
[4]:

$\sigma_{p}\approx 35\,\text{MeV},\qquad|\bar{\psi}|\approx 5.7.$ (15)

The value of $\sigma_{p}$ leads, within the model used, to the following slope
of the diffraction cone in the elastic $\mathit{pd}$ scattering

$B^{pd}=(1-m_{p}/m_{d})^{2}/8\sigma_{p}^{2}+B=37\,\text{GeV}^{-2}$ (16)

where $B\\!=\\!11\,\text{GeV}^{-2}$ [16, *Bartenev:1973kk] is the elastic
$\mathit{pp}$ slope. The calculation is in reasonable agreement with the
experimental values for $B^{pd}$ [18, 19].

Figure 1:  Differential cross section for the $pd\\!\to\\!ppn$ breakup
scattering. The experimental data ($\bullet$) and theoretical calculation
(solid line) are taken from Ref. [12]. The result evaluated in the HJET
measurement [4] is marked $\blacksquare$. The filled area indicates part of
the distribution available for measurement at HJET.

In the HJET measurements, the breakup fraction in the elastic $\mathit{pd}$
data was estimated [4] as

$\big{\langle}\omega_{d}(T_{R})\big{\rangle}_{\text{2.8\>\\!--\>\\!4.2\,MeV}}=5.0\pm
1.4\%.$ (17)

The value found can be compared with the $pd$ $\to$ $ppn$ differential
cross-section (Fig. 1) measured in 1.8 GeV/nucleon deuteron beam scattering in
a hydrogen bubble chamber [12]. Using, for normalization, elastic $pd$
differential cross section [18], Eq. (17) can be rewritten as

$d\sigma/dt\big{|}_{-t=0.0066\,\text{GeV}^{2}}=14\pm 4\,\text{mb/GeV}^{2}.$
(18)

The result is in good agreement with the final-state interaction model
calculation [12], $\approx$ $15\,\text{mb/GeV}^{2}$, and in fair consistency
with the value, $8\pm 2\,\text{mb/GeV}^{2}$, interpolated from experimental
points in Fig. 1. It should also be pointed out that only a small fraction,
$\approx$ $1.5\%$, of all $pd\to ppn$ events can be detected in HJET.

###  II.3 The Helion Beam Breakup in HJET

Applying the breakup model and using parametrization (15) for the 3He beam,
one can evaluate [4] the breakup fraction for the HJET momentum transfer range

$\big{\langle}\omega(T_{R})\big{\rangle}_{\text{1\>\\!--\>\\!10\,MeV}}=2.4\pm
0.4\,\%,$ (19)

while disregarding the detector acceptance and assuming that, for low $t$,
only two-body breakup $h\\!\to\\!pd$ is taken into account, as three-body
breakup $h\\!\to\\!ppn$ is strongly suppressed by a phase-space factor. This
result was obtained by substituting $m_{d}\\!\to\\!m_{h}$,
$m_{n}\\!\to\\!m_{d}$, and
$\Delta_{\text{thr}}^{d}\\!\to\\!\Delta_{\text{thr}}^{h}\\!=\\!5.5\,\text{MeV}$
in Eqs. (13) and (14).

Figure 2:  An estimate of the breakup fractions $\omega(T_{R})$, corresponding
to $m^{*}\\!=\\!m_{p}$ and $m^{*}\\!=\\!2m_{p}$, for 100 GeV/nucleon 3He beam
polarization measurement with HJET. For calculations, the function
$f_{\text{BW}}$ parametrization (15) found in the deuteron beam data analysis
[4] was used.

Breakup fraction $\omega_{m}(T_{R})$, calculated for the 100 GeV/nucleon
helion beam and $m^{*}\\!=\\!m_{p}$, is depicted in Fig. 2. The nonsmooth
dependence of the calculated points on $T_{R}$ reflects the discrete changes
in the event selection efficiency attributed to the Si strip width. Near 7
MeV, the linear dependence on $T_{R}$ is broken due to the finite size of the
detector.

Figure 3:  Scattered mass excess $\Delta$ versus momentum transfer plots for
helion 4.6 GeV/nucleon charge-retention breakup scattering, $ph\\!\to\\!pppn$
and $ph\\!\to\\!ppd$, measured in the hydrogen bubble-chamber experiment [20].
The filled areas indicate part of the distribution that can be studied at
HJET.

Since, for forward $h\\!\to\\!pd$ breakup scattering, the 3He approximation by
a bound state of proton and deuteron cannot be excluded a priori, the breakup
fraction $\omega_{2m}(T_{R})$ (corresponding to a coherent scattering off two
nucleons) should also be considered. Furthermore, the $m^{*}\\!=\\!2m_{p}$
approximation may be relevant, due to the long-distance nature of the Coulomb
interaction, for the $\phi_{+}^{\text{em}}$ breakup amplitudes.

In further analysis, it will be assumed that all of the 3He functions
$\omega(T_{R})$ and $\omega_{I}(T_{R})$ are constrained by $\omega_{m}(T_{R})$
and $\omega_{2m}(T_{R})$. To tolerate a possible discrepancy between 3He
breakup corrections, the following function

$\Delta\omega(T_{R})=\omega_{m}(T_{R})-\omega_{2m}(T_{R})$ (20)

will be used.

For a 4.6 GeV/nucleon $hp$ scattering, the elastic, $\sigma_{h\to
h}\\!=\\!24.2\\!\pm\\!1.0\,\text{mb}$, and breakup, $\sigma_{h\to
pd}\\!=\\!7.29\\!\pm\\!0.14$ mb and $\sigma_{h\to
ppn}\\!=\\!6.90\\!\pm\\!0.14$ mb, cross sections were determined in the
hydrogen bubble-chamber measurements [13]. For the HJET momentum transfer
range (2), the effective elastic cross section can be derived from the
measured $\sigma_{h\to h}$:

$\sigma_{h\to h}^{\text{HJET}}\approx 11\,\text{mb}.$ (21)

The scattered mass $M_{X}$ versus momentum transfer $t$ plots (see Fig. 3) for
the breakup scattering were presented in Ref. [20]. It may be pointed out that
the correlation seen is in a qualitative agreement with Eq. (11). It was
underlined [20] that the breakup events band is spread around the line

$M_{X}^{2}=m_{h}^{2}-2t,$ (22)

which is the same as that followed from Eq. (11) if $m^{*}\\!=\\!m_{p}$ and
$p_{x}\\!=\\!0$.

Each event in Fig. 3 plots contributes nearly 0.003 mb to the corresponding
cross section. For $h\\!\to\\!ppn$, the breakup band events can be counted in
the HJET momentum transfer range. After applying corrections due to the recoil
proton detection efficiency at low $t$ [21], one arrives at

$\sigma_{h\to ppn}^{\text{HJET}}<0.02\,\text{mb}.$ (23)

Since it is not unreasonable that mainly background events were counted, the
result obtained should be interpreted as an upper limit.

Assuming that $h\\!\to\\!pd$ breakup has a flat $d\sigma/dt$ distribution in
the $0<-t<0.45\,\text{GeV}^{2}$ momentum transfer range, one immediately finds
$\sigma_{h\to pd}^{\text{HJET}}/\sigma_{h\to pd}\approx 0.04$. However, since
$\omega(t)\to 0$ if $t\to 0$, a correction is needed. Guessing that the
correction is the same as for the $h\to pd$ distribution in Fig. 1, the
effective cross-section can be estimated as

$\sigma_{h\to pd}^{\text{HJET}}\sim 0.15\,\text{mb}.$ (24)

For comparison, the result displayed in Eq. (19) corresponds to 0.22 – 0.25
mb depending of value of $m^{*}$ used.

Thus, the following conclusion comes after Ref. [20]:
– the helion beam breakup events which can be detected at HJET are mostly
$h\to pd$;
– $\omega_{m}(T_{R})$ depicted in Fig. 2 should be interpreted as an upper
limit for the helion beam breakup in HJET.

Figure 4:  Light output spectrum of scattered protons obtained by the NaI(Tl)
scintillator at $\theta_{\text{lab}}\\!=\\!70^{\circ}$ in the 65 MeV
$p\,{}^{3}\text{He}$ elastic-scattering study [22]. The hatched region
indicates the background contribution. Estimates (done here) for the
$h\\!\to\\!{pd}$ and $h\\!\to\\!{ppn}$ breakup components are shown by solid
and dashed red lines, respectively. The calculations were normalized by the
total number of the breakup protons with energy above 20 MeV
($\Delta\\!<\\!24\,\text{MeV}$).

Another evidence of the $h\\!\to\\!ppn$ breakup suppression for low $\Delta$
follows from the scattered proton energy spectrum (Fig. 4) measured in the 65
MeV proton scattering off the 3He target [22]. The elastic events are centered
at $T_{\text{el}}\\!=\\!40.8\,\text{MeV}$. Since energy measured in the
breakup scattering can be roughly approached by
$T_{\text{brk}}\\!\approx\\!T_{\text{el}}\\!-\\!\Delta$, an evident square
root dependence on $T$ at the breakup endpoint should be attributed to the
phase space integral, $\propto$
$(\Delta\\!-\\!\Delta_{\text{thr}}^{h})^{1/2}$, in the two-body breakup event
rate in Eq. (13).

Applying Eqs. (13) and (14) to the $h\\!\to\\!pd$ breakup and using
$\sigma_{p}\\!=\\!90\,\text{MeV}$, one can fairly well approximate the
experimental spectrum in Fig. 4. Since low energy, 65 MeV, scattering is
considered, the effective values of $\sigma_{p}$ and $|\bar{\psi}|$ may differ
from those (15) evaluated in the high energy, 10 – 31 GeV, $pd$ scattering.

For the three-body breakup, $h\\!\to\\!ppn$, phase space integral dependence
in the event rate (13) is proportional to
$(\Delta\\!-\\!\Delta_{\text{thr}}^{h})^{2}$ which makes the calculated
spectrum inconsistent with the experimental one. So, there is no evidence of
the $h\\!\to\\!ppn$ events in Fig. 4.

##  III Hadronic Spin-Flip Amplitudes in High-Energy Proton-Nucleus Scattering

In Ref. [9], it was shown that, at high energy, to a very good approximation,
the ratio of the spin-flip to the nonflip parts of the elastic proton-nucleus
amplitude is the same as for proton-nucleon scattering. In terms of the
hadronic spin-flip amplitude parameter $r_{5}$, the result can be written as

$r_{5}^{pA}=\frac{i+\rho^{pA}}{i+\rho^{pp}}r_{5}\approx r_{5},$ (25)

where $\rho^{pA}$ and $\rho^{pp}$ are the real-to-imaginary ratio for the
elastic $pA$ and $\mathit{pp}$ scattering, respectively. This result can be
readily derived considering the polarized proton scattering off an unpolarized
nucleus in Glauber (diffraction) approximation [14, *Glauber:1959].

In this approach, the elastic ($f\\!=\\!i$) and/or breakup ($f\\!\neq\\!i$)
proton-nucleus amplitude can be presented [23] using the following integral
over the impact vector $\bm{b}$:

$\displaystyle F_{fi}(\bm{q})$
$\displaystyle=\frac{ik}{2\pi}\int{d^{2}\bm{b}\,e^{i\bm{qb}}}\,\prod_{j=1}^{A}{d^{3}\bm{r}_{j}}$
$\displaystyle\qquad\qquad\Psi_{f}^{*}(\\{r_{j}\\})\Gamma(\bm{b},\bm{s}_{1}\ldots\bm{s}_{A})\Psi_{i}(\\{r_{j}\\})$
(26)

where $\bm{k}$ is the momentum of the incident proton, $\Psi_{i}$ and
$\Psi_{f}$ are the nucleus’s initial and final state wave functions, and
$\Gamma(\bm{b},\bm{s}_{1}\ldots\bm{s}_{A})$ is the profile function. The
positions of the $A$ nucleons in the nucleus were defined by the vectors
$\bm{r}_{j},~{}j\\!=\\!1,\ldots,A$, and $\bm{s}_{j}$ are the projections of
these vectors on the plane perpendicular to $\bm{k}$.

For a proton-deuteron small angle scattering, the elastic $pd$ amplitude
$F_{ii}$ can be approximated [24] by combining the proton-proton $f_{p}$ and
proton-neutron $f_{n}$ ones as

$\displaystyle F_{ii}(\bm{q})$
$\displaystyle=S(\bm{q}/2)f_{n}(\bm{q})+S(\bm{q}/2)f_{p}(\bm{q})$
$\displaystyle+\frac{i}{2\pi
k}\int{S(\bm{q}^{\prime})f_{n}(\bm{q}/2\\!+\\!\bm{q}^{\prime})f_{p}(\bm{q}/2\\!-\\!\bm{q}^{\prime})d^{2}\bf{q}^{\prime}},$
(27)

where $S(\bm{q})$ can be interpreted as a deuteron form factor.

To calculate the $p^{\uparrow}d$ spin-flip amplitude $F_{ii}^{\text{sf}}$, one
can utilize the proton-nucleon one, $f_{N}^{\text{sf}}(\bm{q})$, which,
according to the definition of $r_{5}$ [7], is

$f_{N}^{\text{sf}}(\bm{q})=\frac{\bm{qn}}{m_{p}}\,\frac{r_{5}^{pp}}{i+\rho^{pp}}\,f_{N}(\bm{q})=\bm{qn}\,\hat{r}_{5}^{pp}f(\bm{q}).$
(28)

Since $|r_{5}^{pp}|\,q/m_{p}\lesssim 0.003$ in the HJET measurements, only one
nonflip amplitude $f_{N}$ in each term of Eq. 27 should be replaced by its
spin-flip counterpart $f_{N}^{\text{sf}}$. In particular,

$\displaystyle f_{p}f_{n}$
$\displaystyle\to\left[(\bm{q}/2\\!+\\!\bm{q}^{\prime})\bm{n}f_{p}\,f_{n}+f_{p}\,(\bm{q}/2\\!-\\!\bm{q}^{\prime})\bm{n}f_{n}\right]\,\hat{r}_{5}^{pp}$
$\displaystyle=\bm{qn}\,\hat{r}_{5}^{pp}\,f_{p}f_{n}.$ (29)

Because each term on the right side of Eq. (27) acquired a factor
$\bm{qn}\,\hat{r}_{5}$, one can readily reach Eq. (25).

Generally, elastic $pA$ amplitude can be displayed as

$\displaystyle F_{ii}(\bm{q})$ $\displaystyle=\sum_{i}{\\{{\cal
S}_{i}f_{i}\\}}+\sum_{i,j}{\\{{\cal S}_{ij}f_{i}f_{j}\\}}$
$\displaystyle+\sum_{i,j,k}{\\{{\cal S}_{ijk}f_{i}f_{j}f_{k}\\}}+\ldots,$ (30)

where, e.g., for the 3-amplitude terms,

$\displaystyle\\{{\cal S}_{ijk}f_{i}f_{j}f_{k}\\}$ $\displaystyle=\int{{\cal
S}_{ijk}(\bm{q}_{i}^{\prime},\bm{q}_{j}^{\prime},\bm{q}_{k}^{\prime})\,f_{i}(\bm{q}_{i}^{\prime})f_{j}(\bm{q}_{j}^{\prime})f_{j}(\bm{q}_{k}^{\prime})}$
$\displaystyle\times\delta(\bm{q}-\bm{q}_{i}^{\prime}-\bm{q}_{j}^{\prime}-\bm{q}_{k}^{\prime})d^{2}\bm{q}_{i}^{\prime}d^{2}\bm{q}_{j}^{\prime}d^{2}\bm{q}_{k}^{\prime}.$
(31)

And similarly for other terms. Thus, no detailed knowledge of the form factor
functions ${\cal S}_{i{\ldots}j}$ is needed to prove Eq. (25).

Figure 5:  A polarized 3He spin structure in the ground ${}^{1}S_{0}$ state.
Due to the Pauli principle, the protons are in a spin singlet state. A bound
state of the neutron and proton with parallel spins can be approximated by a
deuteron.

In the case of unpolarized proton scattering of a fully polarized nucleus with
all nucleons having the same polarization $P$, one can easily find
$r_{5}^{Ap}\\!\cong\\!r_{5}^{pp}P$. In the case of a space-symmetric
distribution of the nucleons, the result is proportional to the average
polarization of the nucleons, $r_{5}^{pA}\\!\cong\\!r_{5}\sum{P_{i}}/A$.
Assuming that 3He nuclei are in a space-symmetric ${}^{1}S_{0}$ state (Fig.
5), in which the helion spin is carried by the neutron (i.e., $P_{n}\\!=\\!1$
and $P_{p}\\!=\\!0$), one can find $r_{5}^{hp}\\!=\\!r_{5}^{pp}/A_{h}$ [10].
Small corrections to $P_{n,p}$ due to the ${}^{3}S_{1}$ and ${}^{3}D_{1}$
partial waves were evaluated in Ref. [25].

Considering a breakup scattering, e.g., $hp\\!\to\\!dp\>\\!p$, one can define
the non-flip and spin-flip amplitudes as

$\displaystyle\\!\\!F_{fi}(\bm{q})$
$\displaystyle=\psi_{fi}(\bm{q})F_{ii}(\bm{q}),\quad\psi_{fi}(\bm{q})=|\psi_{fi}(\bm{q})|e^{i\varphi_{fi}(\bm{q})},$
(32) $\displaystyle\\!\\!F_{fi}^{\text{sf}}(\bm{q})$
$\displaystyle=\frac{\bm{qn}}{m_{p}}\,\frac{\widetilde{r}_{5}}{i+\rho^{pA}}F_{fi}(\bm{q}).$
(33)

Here, $F_{fi}(\bm{q})$ and $F_{fi}^{\text{sf}}(\bm{q})$ are effective breakup
amplitudes (for a given value of $\bm{q}$), i.e., sums of all amplitudes over
all internal states of the breakup. Therefore, the calculation of
probabilities, such as $|F_{fi}|^{2}$, $|F_{fi}^{\text{sf}}|^{2}$, and
$\text{Im}\\{F_{fi}^{\text{sf}}F_{fi}^{*}\\}$ assumes summation over these
states.

Since, the only difference between elastic and breakup scattering is given
[see Eq. (26)] by the final-state wave function $\Psi_{f}$, the amplitude
expansion (30) should be also valid (with some other set of functions ${\cal
S}_{i{\ldots}j}$) for the breakup scattering. Thus,

$\widetilde{r}_{5}^{ph}=r_{5}^{pp}\frac{i+\rho^{ph}}{i+\rho^{pp}},\quad\widetilde{r}_{5}^{hp}=(1/3+\delta_{pd})\,r_{5}^{pp}\frac{i+\rho^{ph}}{i+\rho^{pp}}.$
(34)

Considering a single nucleon scattering of an unpolarized proton from the
fully polarized helion $h^{\uparrow}$ in the ground state (see Fig. 5) and
assuming that $\bm{q}$ is sufficiently large to knock out the target nucleon,
one should conclude that the $h\to pd$ helion breakup can occur only if the
beam proton was scattered off the oppositely polarized proton,
$p^{\downarrow}$, in 3He. Such a speculation suggests that
$\widetilde{r}_{5}^{hp}=-r_{5}^{pp}$ (or $1/3\\!+\\!\delta_{pd}\\!=\\!-1$).

Even for the relatively large value of $|\delta_{pd}|\\!=\\!4/3$, the breakup
correction to the measured $P_{h}$ is small [26]. Moreover, since the
accordance between the $h\to pd$ breakup and the beam scattering off the
$p^{\downarrow}$ nucleon should be diluted at low $\bm{q}$, the effect must be
much smaller in the HJET measurements. Following discussion in the next
section, one can find $\delta_{pd}\\!=\\!0$ (if $t\\!\to\\!0$) and

$\left|\delta_{pd}/r_{5}^{hp}\right|\lesssim{\cal O}(1\%)$ (35)

in the momentum transfer range (2).

##  IV Evaluation of Breakup Corrections in Helion Beam Polarization
Measurements

A basic assumption of the Glauber theory approach that a high energy beam
proton crosses a target nucleus before any changes in the nucleus structure
caused by the proton occur, suggests that an electromagnetic interaction is
the same for the elastic and breakup scattering. However, to compare the
electromagnetic amplitudes for the elastic and breakup scattering, the
interaction, in accordance with Eq. (26), should be projected to the final-
state wave functions $\Psi_{h}$ and $\Psi_{pd}$, respectively. Assuming that
the helion disturbance, ${}^{3}\text{He}\to{{}^{3}\text{He}}^{*}(\bm{q})$, in
the scatterings is small, one finds that the reduced breakup to the elastic
ratio (13) is the same for the electromagnetic and hadronic as well as for the
spin-flip and nonflip amplitudes.

$\frac{\langle\bar{\Psi}_{pd}|{{}^{3}\text{He}}^{*}(\bm{q})\rangle_{\text{em}}}{\langle{\Psi}_{h}|{{}^{3}\text{He}}^{*}(\bm{q})\rangle_{\text{em}}}\approx\frac{\langle\bar{\Psi}_{pd}|{{}^{3}\text{He}}\rangle_{\text{em}}}{\langle{\Psi}_{h}|{{}^{3}\text{He}}\rangle_{\text{em}}}=\frac{\langle\bar{\Psi}_{pd}|{{}^{3}\text{He}}\rangle_{\text{had}}}{\langle{\Psi}_{h}|{{}^{3}\text{He}}\rangle_{\text{had}}}=\bar{\psi}.$
(36)

For example, since function
$f_{\text{BW}}(\Delta\\!-\\!\Delta_{0},\sigma_{\Delta})$ [Eq. (13)] must be
the same for the $p^{\uparrow}h$ hadronic spin-flip and nonflip amplitudes,
Eq. (36) immediately leads to $\widetilde{r}_{5}^{ph}\\!=\\!r_{5}^{ph}$ in
agreement with Eqs. (25) and (34).

Would $f_{\text{BW}}(\Delta\\!-\\!\Delta_{0},\sigma_{\Delta})$ be the same for
all amplitudes considered in ratio (5), the breakup correction factors
$1\\!+\\!\omega_{I}(T_{R})$ will cancel in each interference ($I$) term in
${\cal R}_{h}(T_{R})$. In other words, the breakup corrections cannot affect
the 3He beam polarization measurements in such an approach.

In the more general case, the breakup corrections can be modified (diluted)
using the median breakup fraction
$\omega^{*}(T_{R})\\!=\\!\left[\omega_{m}(T_{R})+\omega_{2m}(T_{R})\right]/2$:

$1+\omega_{I}(T_{R})\to\frac{1+\omega_{I}(T_{R})}{1+\omega^{*}(T_{R})}=1+\omega_{I}^{\prime}(T_{R}),$
(37)

Since $\omega_{I}^{\prime}(T_{R})$ is small, of the order of 1%,

$\left|\omega_{I}^{\prime}(T_{R})\right|\leq\Delta\omega(T_{R})/2.$ (38)

Replacing the real and imaginary parts of $r_{5}^{pp}$ in Eq. (5) by the
absolute value $|r_{5}^{pp}|\\!\approx\\!0.02$ and using the above inequality
(38), one can find conservative estimates for the breakup corrections
$\xi(T_{R})$ to the measured polarization separately for each interference
term:

$\displaystyle\phi_{5}^{\text{em}}\phi_{+}^{\text{had}}\\!:\quad$
$\displaystyle\xi^{\kappa}(T_{R})<\Delta\omega(T_{R})$ (39)
$\displaystyle\qquad\quad\approx-0.11\%+0.13\%\,\frac{T_{R}}{T_{c}},$ (40)
$\displaystyle\phi_{5}^{\text{had}}\phi_{+}^{\text{em}}\\!:\quad$
$\displaystyle\xi^{I_{5}}(T_{R})<\left(\frac{1}{\kappa_{p}}\\!-\\!\frac{1}{3\kappa_{h}}\right)|r_{5}^{pp}|\,\Delta\omega(T_{R})$
(41) $\displaystyle\qquad\quad\approx-0.002\%+0.002\%\,\frac{T_{R}}{T_{c}},$
(42) $\displaystyle\phi_{5}^{\text{had}}\phi_{+}^{\text{had}}\\!:\quad$
$\displaystyle\xi^{R_{5}}(T_{R})<\left(\frac{1}{\kappa_{p}}\\!-\\!\frac{1}{3\kappa_{h}}\right)|r_{5}^{pp}|\,\Delta\omega(T_{R})\frac{T_{R}}{T_{c}}$
(43) $\displaystyle\qquad\quad\approx-0.08\%+0.03\%\,\frac{T_{R}}{T_{c}}.$
(44)

For numerical estimates, a linear fit was done in the recoil proton energy
range $2\\!<\\!T_{R}\\!<\\!10\,\text{MeV}$ [27].

Relatively loose constraints, $\left|\xi_{0}^{R_{5}}\right|\\!=\\!0.08\%$, on
possible systematic errors in Eqs. (43), (44) can be explained by the
essential nonlinearity of the $\Delta\omega(T_{R})T_{R}/T_{c}$ function. To
improve this, a parabolic function

$\xi(T_{R})\approx\xi_{0}+\xi_{1}\>\\!T_{R}/T_{c}+\xi_{2}(T_{R}/T_{c})^{2}$
(45)

can be considered to fit (with $\xi_{0}\\!\equiv\\!0$)
$P_{\text{beam}}(T_{R})$ in the $2\\!<\\!T_{R}\\!<\\!7\,\text{GeV}$ energy
range. In this case, $\left|\xi_{0}^{R_{5}}\right|\\!\approx\\!0.02\%$.

##  V Summary

In this paper, possible 3He breakup related corrections to the EIC 3He beam
polarization measurements with HJET were reviewed.

The breakup fraction in the HJET measurements, evaluated [4] using the
deuteron data, was found to be consistent with a value obtained in the
hydrogen bubble-chamber experiment [12]. This result proves that, within the
experimental accuracy of the measurements [4], (i) the model used to describe
the breakup event rate, $dN/dT_{R}d\Delta$, adequately simulates the
experimental data and (ii) the breakup event fraction can be reliably
monitored in the HJET measurements using 5 – 20 GeV 3He beams.

In Ref. [4], the breakup fraction in the future 3He beam polarization
measurement at EIC was estimated by extrapolation of the $d\\!\to\\!pn$
results to the two-body $h\\!\to\\!pd$ breakup and neglecting the three-body
$h\\!\to\\!ppn$ one. Analyzing experimental distributions displayed in Refs.
[20, 22], it was confirmed that the $h\\!\to\\!ppn$ rate is very small in the
HJET measurements.

The evaluated [4] 3He breakup rate was compared with the results of the 3He
beam scattering in the hydrogen bubble chamber [13, 20]. It was found that the
functions $\omega(T_{R})$ displayed in Fig. 2 should be interpreted as an
upper limit for the breakup fraction in the EIC 3He beam scattering in HJET.

It was shown that, within the applicability of the Glauber theory, the ratio
of the high-energy proton-nucleus $p^{\uparrow}A$ breakup spin-flip and
nonflip amplitudes is the same as for elastic proton-proton scattering. Both
for $p^{\uparrow}h$ and $h^{\uparrow}p$ scattering in the HJET momentum
transfer range, the ratio of the spin-flip to nonflip amplitude is the same,
with a percent accuracy, for the elastic and breakup amplitudes.

It was also found that the breakup corrections to the interference terms
$\omega_{I}(T_{R})$ and the cross section $\omega(T_{R})$ are about the same
within 10 – 20% accuracy, which significantly limits possible alteration of
the analyzing power ratio (5). Although the corrections, $\omega_{I}(T_{R})$,
may be as large as 4% (relative), they do not exceed 1% in the analyzing power
ratio ${\cal R}_{h}(T_{R})$ and are reduced to a negligible level if
$P_{\text{meas}}(T_{R})$ is extrapolated to $T_{R}\\!\to\\!0$.

Considering the breakup correction cancellation in Eq. (8), it should be
concluded that the breakup corrections alter the effective analyzing powers,
$A_{\text{N}}^{ph}(t)$ and $A_{\text{N}}^{hp}$, in the HJET 3He beam
measurement by no more than 1%. This estimate is also expected to be
applicable for the $p^{\uparrow}A$ analyzing power study [28] at HJET.

Estimates given in Eqs. (39) – (44) verify that the breakup corrections are
negligible in the 3He beam polarization measurements at HJET [4].

###### Acknowledgements.

The author would like to thank B. Z. Kopeliovich for useful discussions and
acknowledges support from the Office of Nuclear Physics in the Office of
Science of the US Department of Energy. This work is authored by an employee
of Brookhaven Science Associates, LLC under Contract No. DE-SC0012704 with the
U.S. Department of Energy.

## References

  * Abdul Khalek  _et al._ [2022] R. Abdul Khalek _et al._ , Science Requirements and Detector Concepts for the Electron-Ion Collider: EIC Yellow Report, Nucl. Phys. A 1026, 122447 (2022), arXiv:2103.05419 [physics.ins-det] .
  * Accardi  _et al._ [2016] A. Accardi, L. Albacete, J., M. Anselmino, _et al._ , Electron Ion Collider: The Next QCD Frontier, Eur. Phys. J. A 52, 268 (2016), arXiv:1212.1701 [nucl-ex] .
  * Poblaguev [2022a] A. A. Poblaguev, Feasibility study for precisely measuring the EIC 3He beam polarization with the Polarized Atomic Hydrogen Gas Jet Target polarimeter at RHIC, Phys. Rev. C 106, 065202 (2022a), arXiv:2207.09420 [hep-ph] .
  * Poblaguev [2022b] A. A. Poblaguev, Breakup corrections to the 3He beam polarization measurements at the future BNL Electron Ion Collider, Phys. Rev. C 106, 065203 (2022b), arXiv:2207.06999 [hep-ph] .
  * Zelenski  _et al._ [2005] A. Zelenski, A. Bravar, D. Graham, W. Haeberli, S. Kokhanovski, Y. Makdisi, G. Mahler, A. Nass, J. Ritter, T. Wise, and V. Zubets, Absolute polarized H-jet polarimeter development, for RHIC, Nucl. Instrum. Meth. A 536, 248 (2005).
  * Poblaguev  _et al._ [2020a] A. A. Poblaguev, A. Zelenski, G. Atoian, Y. Makdisi, and J. Ritter, Systematic error analysis in the absolute hydrogen gas jet polarimeter at RHIC, Nucl. Instrum. Meth. A 976, 164261 (2020a), arXiv:2006.08393 [physics.ins-det] .
  * Buttimore  _et al._ [1999] N. H. Buttimore, B. Z. Kopeliovich, E. Leader, J. Soffer, and T. L. Trueman, The spin dependence of high-energy proton scattering, Phys. Rev. D 59, 114010 (1999), arXiv:hep-ph/9901339 .
  * Buttimore [2009] N. H. Buttimore, Forward helion scattering and neutron polarization, AIP Conf. Proc. 1105, 189 (2009).
  * Kopeliovich and Trueman [2001] B. Z. Kopeliovich and T. L. Trueman, Polarized proton nucleus scattering, Phys. Rev. D 64, 034004 (2001), arXiv:hep-ph/0012091 .
  * Buttimore  _et al._ [2001] N. H. Buttimore, E. Leader, and T. L. Trueman, An absolute polarimeter for high-energy protons, Phys. Rev. D 64, 094021 (2001), arXiv:hep-ph/0107013 .
  * Poblaguev  _et al._ [2019] A. A. Poblaguev, A. Zelenski, E. Aschenauer, G. Atoian, K. O. Eyser, H. Huang, Y. Makdisi, W. B. Schmidke, I. Alekseev, D. Svirida, and N. H. Buttimore, Precision Small Scattering Angle Measurements of Elastic Proton-Proton Single and Double Spin Analyzing Powers at the RHIC Hydrogen Jet Polarimeter, Phys. Rev. Lett. 123, 162001 (2019), arXiv:1909.11135 [hep-ex] .
  * Aladashvili  _et al._ [1977] B. S. Aladashvili, J. F. Germond, V. V. Glagolev, M. S. Nioradze, T. Siemiarczuk, J. Stepaniak, V. N. Streltsov, C. Wilkin, and P. Zielinski, Final State Interactions in the High-Energy Proton-Deuteron Charge Exchange Reaction, J. Phys. G 3, 1225 (1977).
  * Glagolev  _et al._ [1993] V. V. Glagolev _et al._ (Dubna-Kosice-Moscow-Strasbourg-Tbilisi-Warsaw), Cross sections of the interactions of He nuclei with protons, Z. Phys. C 60, 421 (1993).
  * Glauber [1955] R. J. Glauber, Cross Sections in Deuterium at High Energies, Phys. Rev. 100, 242 (1955).
  * Glauber [1959] R. J. Glauber, High Energy Collision Theory, in  _Lectures in Theoretical Physics_ , Vol. 1, edited by W. E. Brittin and L. C. Dunham (Interscience Publishers, New York, 1959) pp. 315 – 414.
  * Bartenev  _et al._ [1973a] V. Bartenev _et al._ , Measurement of the Slope of the Diffraction Peak for Elastic $p$-$p$ Scattering from 8 to 400 GeV, Phys. Rev. Lett. 31, 1088 (1973a).
  * Bartenev  _et al._ [1973b] V. Bartenev _et al._ , Real Part of the Proton-Proton Forward-Scattering Amplitude from 50 to 400 GeV, Phys. Rev. Lett. 31, 1367 (1973b).
  * Beznogikh  _et al._ [1973] G. G. Beznogikh _et al._ , Differential cross-sections of elastic $pd$ scattering in the energy range 10–70 GeV, Nucl. Phys. B 54, 97 (1973).
  * Akimov  _et al._ [1975] Y. Akimov _et al._ , Proton-deuteron elastic scattering at small momentum transfer from 50 to 400 GeV/c, Phys. Rev. D 12, 3399 (1975), [Erratum: 15, 2040 (1977)].
  * [20] J. Stepaniak, Pion production in the 3He–proton interactions, in  _Production properties and interaction of mesons. Proceedings, Workshop, Meson’96, Cracow, Poland, May 10–14, 1996_ , edited by E. Grosse, H. Machner, A. Magiera, and Z. Rudy, Acta Phys. Polon. B 27, 2971 (1996).
  * Aladashvili  _et al._ [1975] B. S. Aladashvili _et al._ (Dubna–Warsaw), Use of the deuteron beam for studying the $dp$ interactions, Nucl. Instrum. Meth. 129, 109 (1975).
  * Watanabe  _et al._ [2021] A. Watanabe _et al._ , Proton-3He elastic scattering at intermediate energies, Phys. Rev. C 103, 044001 (2021), arXiv:2103.14271 [nucl-ex] .
  * Glauber and Matthiae [1970] R. Glauber and G. Matthiae, High-energy scattering of protons by nuclei, Nucl. Phys. B 21, 135 (1970).
  * Franco and Glauber [1966] V. Franco and R. J. Glauber, High-energy deuteron cross-sections, Phys. Rev. 142, 1195 (1966).
  * Friar  _et al._ [1990] J. L. Friar, B. F. Gibson, G. L. Payne, A. M. Bernstein, and T. E. Chupp, Neutron polarization in polarized 3He targets, Phys. Rev. C 42, 2310 (1990).
  * Poblaguev [2023] A. A. Poblaguev, Improved analysis of the breakup corrections to the high energy 3He beam polarization measurements with HJET (2023), arXiv:2303.00677 [hep-ph] .
  * Poblaguev  _et al._ [2020b] A. A. Poblaguev, A. Zelenski, and G. Atoian, The prospects on the absolute proton beam polarimetry at EIC, PoS PSTP2019, 007 (2020b).
  * [28] A. A. Poblaguev, A. Zelenski, E. Aschenauer, G. Atoian, K. O. Eyser, H. Huang, W. B. Schmidke, I. Alekseev, D. Svirida, and N. H. Buttimore, Precision small scattering angle measurements of proton-proton and proton-nucleus analyzing powers at the RHIC hydrogen jet polarimeter, arXiv:2211.17146 [hep-ex] .


11institutetext: DAIS, Ca’ Foscari University of Venice, Italy
11email<EMAIL_ADDRESS>22institutetext: Centre for
Biotechnology and Bioengineering, Chile 33institutetext: Department of
Computer Science, University of Chile, Chile
33email<EMAIL_ADDRESS>
# On Computing the Smallest Suffixient Set

Davide Cenzato Funded by the European Union (ERC, REGINDEX, 101039208). Views
and opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union or the European Research
Council. Neither the European Union nor the granting authority can be held
responsible for them.11 0000-0002-0098-3620 Francisco Olivares Funded by Ph.D
Scholarship 21210579, ANID, Chile.2233 0000-0001-7881-9794 Nicola Prezza⋆ 11
0000-0003-3553-4953

###### Abstract

Let $T\in\Sigma^{n}$ be a text over alphabet $\Sigma$. A _suffixient set_
$\mathcal{S}\subseteq[n]$ for $T$ is a set of positions such that, for every
one-character right-extension $T[i,j]$ of every right-maximal substring
$T[i,j-1]$ of $T$, there exists $x\in S$ such that $T[i,j]$ is a suffix of
$T[1,x]$. It was recently shown that, given a suffixient set of cardinality
$q$ and an oracle offering fast random access on $T$ (for example, a straight-
line program), there is a data structure of $O(q)$ words (on top of the
oracle) that can quickly find all Maximal Exact Matches (MEMs) of any query
pattern $P$ in $T$ with high probability. The paper introducing suffixient
sets left open the problem of computing the smallest such set; in this paper,
we solve this problem by describing a simple quadratic-time algorithm, a
$O(n+\bar{r}|\Sigma|)$-time algorithm running in compressed working space
($\bar{r}$ is the number of runs in the Burrows-Wheeler transform of $T$
reversed), and an optimal $O(n)$-time algorithm computing the smallest
suffixient set. We present an implementation of our compressed-space algorithm
and show experimentally that it uses a small memory footprint on repetitive
text collections.

###### Keywords:

Suffixient sets Right-maximal substrings Text indexing Compressed-space
algorithms

##  1 Introduction

In [4], Depuydt et al. described a new compressed index based on the following
principle. Let $T\in\Sigma^{n}$ be a text of length $n$. Choose a set
$S\subseteq[n]$ such that, for every one-character right-extension $T[i,j]$ of
every right-maximal substring $T[i,j-1]$ of $T$, there exists $x\in S$ such
that $T[i,j]$ is a suffix of $T[1,x]$ ($\alpha$ is said to be _right-maximal_
if both $\alpha\cdot a$ and $\alpha\cdot b$ appear in $T$ for some characters
$a\neq b$ or if $\alpha$ is a suffix of $T$). The idea behind the index is
that the set of prefixes $\\{T[1,x]\ :\ x\in S\\}$, together with random
access on $T$, can be used to locate one occurrence of any pattern $P$ in $T$
via the following strategy. Assuming that $P$ occurs in $T$ and that the
prefix $P[1,j]$ is right-maximal in $T$: (i) we find one of the selected
prefixes $T[1,x]$, for $x\in S$, suffixed by $P[1,j+1]$, and (ii) we right-
extend the match by comparing $T[x+1,\dots]$ and $P[j+2,\dots]$. This way, we
either match until the end of $P$ or we find a mismatch $T[x+1+t]\neq
P[j+2+t]$, for some $t\geq 0$. In the former case, we are done. In the latter
case, we know that $P[j+1+t]$ is right-maximal in $T$ so we can repeat steps
(i) and (ii). Starting with the empty prefix of $P$, this procedure yields one
occurrence of $P$ in $T$ and can be easily extended to return all Maximal
Exact Matches (MEMs) of $P$ in $T$. Depuydt et al. [4] called _suffixient_ a
set $S$ with the property above outlined. They moreover exhibited a suffixient
set of cardinality $2\bar{r}$, where $\bar{r}$ is the number of runs in the
Burrows-Wheeler transform of $T$ reversed. To conclude, they observed that the
set $\\{T[1,x]\ :\ x\in S\\}$ can be stored in $O(|S|)$ words of space using
z-fast tries while supporting fast suffix searches (thereby supporting step
(i)), and that the right-extension at step (ii) can be performed in
logarithmic time and compressed space using a straight-line program of size
$g$ on $T$. As a result, they obtained an index of $O(\bar{r}+g)$ words able
to efficiently locate all MEMs of $P$ in $T$.

This new indexing strategy raises a natural question: how to compute the
smallest suffixient set, of size $\chi$? Observe that $\chi$ is independent on
the alphabet ordering, while $\bar{r}$ is. Since re-ordering the alphabet may
reduce asymptotically $\bar{r}$ [1], from the bound $\chi\leq 2\bar{r}$ we
immediately obtain that there exist string families on which
$\chi=o(\bar{r})$. In other words, $\chi$ is a better repetitiveness measure
than $\bar{r}$, even though the problem of determining whether $\chi$ is
_reachable_ (i.e. if $O(\chi)$ words are always sufficient to store the text)
is still open. In this respect, Depuydt et al. [4] prove that any suffixient
set is a string attractor [5], entailing in particular that $T$ can be
compressed in $O(\chi\log(n/\chi))$ words of space.

In this paper, we start by characterizing the smallest suffixient set. Our
main contribution is to show that the smallest suffixient set can be computed
efficiently. We describe three algorithms solving the problem, all based on
the Burrows-Wheeler transform ($\mathrm{BWT}$), the Longest Common Prefix
array ($\mathrm{LCP}$), and the Suffix Array ($\mathrm{SA}$) of $T$ reversed.
The first algorithm runs in quadratic time and is conceptually very simple.
The other two algorithms are optimizations of the first one. The second
algorithm runs in $O(n+\bar{r}\sigma)$ time (which can be easily reduced to
$O(n+\bar{r}\log\sigma)$) and requires only one pass on those three arrays.
The third algorithm requires random access on those arrays and runs in optimal
$O(n)$ time. While being slower, the one-pass property of the second algorithm
makes it ideal to be combined with Prefix Free Parsing (PFP) [2], a technique
able to stream those three arrays in compressed space. We show experimentally
that this combination of PFP with our one-pass algorithm can quickly compute
the smallest suffixient set in compressed space on repetitive text
collections.

##  2 Preliminaries

Let $\Sigma$ be a finite ordered alphabet of size $\sigma$. We use the
following notation: $[i,j]$ for an interval indicating all values
$\\{i,i+1,\dots,j\\}$ (if $j<i$, then $[i,j]=\emptyset$), $[n]$ for $[1,n]$,
$T=T[1,n]$ for a string $T$ of length $n$ over $\Sigma$, $T[i]$ for the $i$th
character of $T$, $T[i,j]$ for the substring $T[i]\cdots T[j]$ of $T$, where
$1\leq i,j\leq n$, $|T|$ for the length of $T$, and $\epsilon$ for the empty
string. We assume that $T$ begins with an end-of-string character $T[1]=\$$
being smaller than all the other characters in $\Sigma$ and appearing only in
$T[1]$. We moreover assume $n=|T|\geq 2$, so $T$ contains at least two
distinct characters, and that $\sigma\leq n$, since the alphabet can always be
re-mapped to $[n]$ without changing the solutions to the problems considered
in this paper. A run for a string $T$ is a maximal substring $T[i,j]$
containing only one distinct character; we denote by $\text{runs}(T)$ the
number of runs of $T$. We refer to $T^{\text{rev}}=T[n]T[n-1]\cdots T[1]$ as
the reverse of the string $T$.

A _right-maximal substring_ (or _repeat_) $T[i,j]$ ($j\geq i-1$) of a string
$T[1,n]$ is a substring of $T$ such that either $j=n$ or for which there exist
at least two distinct characters $a,b\in\Sigma$ such that both $T[i,j]\cdot a$
and $T[i,j]\cdot b$ are substrings of $T$. Note that the empty string
$\epsilon$ is right-maximal.

Given two strings $T$ and $S$, we define the lexicographic order on
$\Sigma^{*}$ as follows: $S<_{lex}T$ if $S$ is a proper prefix of $T$, or if
there exists an index $j$ s.t. $S[j]<T[j]$ and for all $i<j$, $S[i]=T[i]$.
Given a $\$$-terminated string $T=T[1,n]$, the _suffix array_ of $T$,
$\mathrm{SA}$, is the permutation of $[n]$ such that
$T[\mathrm{SA}[i],n]<_{\text{lex}}T[\mathrm{SA}[j],n]$ holds for any $1\leq
i<j\leq n$. The _longest common prefix_ array of $T$, $\mathrm{LCP}[2,n]$ is
the length-$(n-1)$ array (indexed from $2$) such that $\mathrm{LCP}[i]$ stores
the length of the longest common prefix between $T[\mathrm{SA}[i],n]$ and
$T[\mathrm{SA}[i-1],n]$, for all $2\leq i\leq n$. Given a set $B\subseteq[n]$,
$\mathrm{LCP}[B]$ indicates the set $\\{\mathrm{LCP}[i]\ :\ i\in B\\}$.

Given a $\$$-terminated string $T=T[1..n]$, the Burrows-Wheeler Transform of
$T$ [3], $\mathrm{BWT}(T)$, is a permutation of the characters of $T$ defined
by concatenating the characters following the lexicographically-sorted
suffixes of $T$. We indicate with $\bar{r}$ the number of runs in
$\mathrm{BWT}(T^{\text{rev}})$. For example, if $T={\tt\$BANANA}$,
$\text{BWT}(T^{\text{rev}})={\tt BNN\$AAA}$, and ${\bar{r}}=4$.

We say that position $1<i\leq n$ is a _$c$ -run break_, for $c\in\Sigma$, if
$\mathrm{BWT}[i-1,i]=ac$ or $\mathrm{BWT}[i-1,i]=ca$, with $a\in\Sigma$ and
$a\neq c$. Note that, if $i$ is a $c$-run break, then it is also an $a$-run
break for some $a\neq c$.

##  3 The Smallest Suffixient Set

We start from the definition of _suffixient set_ [4]:

######  Definition 1 (Suffixient set [4])

A set $S\subseteq[n]$ is _suffixient_ for a string $T$ if, for every one-
character right-extension $T[i,j]$ ($j\geq i$) of every right-maximal string
$T[i,j-1]$, there exists $x\in S$ such that $T[i,j]$ is a suffix of $T[1,x]$.

Next, we characterize the smallest suffixient set. We first define the concept
of _supermaximal extensions_ (Definition 2). Then, in Definition 3 we define a
set (actually, a family of sets) $\mathcal{S}$ containing all positions in $T$
“capturing” all (and only the) supermaximal extensions of $T$. Finally, in
Lemma 1 we prove that $\mathcal{S}$ is a suffixient set of minimum
cardinality.

###### Definition 2

We say that $T[i,j]$ (with $j\geq i$) is a _supermaximal extension_ if
$T[i,j-1]$ is right-maximal and, for each right-maximal
$T[i^{\prime},j^{\prime}-1]\neq T[i,j-1]$ (with $i^{\prime}\leq
j^{\prime}<n$), $T[i,j]$ is not a suffix of $T[i^{\prime},j^{\prime}]$.

The following definition depends on a particular total order $<_{t}$ on $[n]$.
We use $<_{t}$ to break ties between equivalent candidate positions of the
suffixient set, choosing the position of maximum rank according to $<_{t}$ in
case of a tie. In order to make notation lighter, we do not parameterize the
set on the particular tie-breaking strategy ($<_{t}$ will always be clear from
the context).

###### Definition 3

Let $<_{t}$ be any total order on $[n]$. We define a set
$\mathcal{S}\subseteq[n]$ as follows: $x\in\mathcal{S}$ if and only if there
exists a supermaximal extension $T[i,j]$ such that (i) $T[i,j]$ is a suffix of
$T[1,x]$, and (ii) for all prefixes $T[1,y]$ suffixed by $T[i,j]$, if $y\neq
x$ then $y<_{t}x$.

In Appendix 0.A we prove:

######  Lemma 1 ()

For any tie-breaking strategy (total order) $<_{t}$, $\mathcal{S}$ is a
suffixient set of minimum cardinality for $T$.

From now on, we denote with $\chi=|\mathcal{S}|$ the cardinality of a
suffixient set of minimum size. Note that, by Lemma 1, Definition 3 yields a
suffixient set of cardinality $\chi$ for _any_ tie-breaking strategy (total
order) $<_{t}$.

##  4 Computing the smallest suffixient set

In this section, we present three algorithms for computing a suffixient set of
smallest cardinality. We start in Subsection 4.1 by giving an “operative”
version of Definition 3. This “operative” definition will automatically yield
a simple quadratic-time algorithm for computing a smallest suffixient set. In
the next subsections, we will optimize this algorithm and reach compressed
working space (Subsection 4.2) and optimal linear time (Subsection 4.3).

###  4.1 A simple quadratic-time algorithm

For brevity, in the rest of the paper $\mathrm{LCP}$, $\mathrm{BWT}$,
$\mathrm{SA}$ denote $\mathrm{LCP}(T^{\text{rev}})$,
$\mathrm{BWT}(T^{\text{rev}})$, and $\mathrm{SA}(T^{\text{rev}})$,
respectively.

###### Definition 4

Given a position $i\in[n]$, we define $box(i)=[\ell,r]$ to be the maximal
interval such that $i\in[\ell,r]$ and $\mathrm{LCP}[j]\geq\mathrm{LCP}[i]$ for
all $j\in[\ell,r]$.

###### Example 1

See Figure 1: $box(10)=[3,13]$ (shown with a blue box), because
$\mathrm{LCP}[3,13]\geq\mathrm{LCP}[10]=1$, and $box(19)=[17,20]$ (shown with
an orange box).

Next, we define the set of $c$-run breaks in $box(i)$. Recall that when we say
that $i$ is a $c$-run break, we mean that either $\mathrm{BWT}[i-1,i]=ac$ or
$\mathrm{BWT}[i-1,i]=ca$, for some $a\neq c$.

###### Definition 5

Given $i\in[n]$ and $c\in\Sigma$, we define

$B_{i,c}=\\{j\ :\ j\ \mathrm{is\ a\ }c\mathrm{-run\ break\ in\
}\mathrm{BWT}(T^{\text{rev}})\mathrm{\ and\ }j\in box(i)\\}.$

###### Example 2

In Figure 1, we have $B_{10,A}=\\{3,6,7,10,11,12\\}$.

We indicate with $text(i)=n-\mathrm{SA}[i]+2$ the position in $T$
corresponding to character $\mathrm{BWT}[i]$, and with
$bwt(j)=\mathrm{SA}^{-1}[n+2-j]$ the inverse of function $text()$, i.e. the
position in $\mathrm{BWT}$ corresponding to character $T[j]$.

The following property, which we prove in Appendix 0.A, stands at the core of
all our algorithms for computing a smallest suffixient set:

######  Lemma 2 ()

The following hold:

  1. 1.

Let $i$ be a $c$-run break and $i^{\prime}\in\\{i,i-1\\}$ be such that
$\mathrm{BWT}[i^{\prime}]=c$. Let $j^{\prime}=text(i^{\prime})$, and let
$\ell=\mathrm{LCP}[i]$. If $\ell=\max\mathrm{LCP}[B_{i,c}]$, then the string
$T[j^{\prime}-\ell,j^{\prime}]$ is a supermaximal extension, and

  2. 2.

conversely, for any supermaximal extension $\alpha\cdot c$ there exists an
occurrence $\alpha\cdot c=T[j^{\prime}-\ell,j^{\prime}]$ and a $c$-run break
$i\in[n]$ such that $\mathrm{BWT}[i^{\prime}]=c$, with
$i^{\prime}=bwt(j^{\prime})\in\\{i,i-1\\}$ and
$\ell=\mathrm{LCP}[i]=\max\mathrm{LCP}[B_{i,c}]$.

Intuitively, Lemma 2 states that supermaximal extensions can be identified by
looking at local maxima among $c$-run breaks contained in $\mathrm{LCP}$
ranges of the form $\mathrm{LCP}[box(i)]$. Since, by Definition 3,
supermaximal extensions are those characterizing suffixient sets of smallest
cardinality, Lemma 2 gives us a tool for computing such a set using the arrays
$\mathrm{BWT}$, $\mathrm{LCP}$, and $\mathrm{SA}$. See Figure 1.

Figure 1:  The figure shows how to construct a smallest suffixient set
$\mathcal{S}$ for a string $T[1,n]$ with $n=20$ following Lemma 2. _To the
left of the black arrows_ : all supermaximal extensions $\alpha\cdot a$ of $T$
and their selected ending positions in $T$, forming a suffixient set. _To the
right of the black arrows_ : $\mathrm{SA}$, $\mathrm{LCP}$, $\mathrm{BWT}$ and
the sorted suffixes of $T^{\text{rev}}$. In column $\mathrm{SA}[i]$, we
highlight in red all positions that are selected to be included in
$\mathcal{S}$. In columns _Suffixes_ and $\mathrm{BWT}[i]$, we highlight in
green the (reverses of) the supermaximal extensions of $T$. Black arrows show
how the selected $\mathrm{SA}$ positions are converted to positions in $T$
using the formula $n-\mathrm{SA}[i]+2$. _How to identify positions of
$\mathcal{S}$_: for each $c$-run break $i$, we decide if the two ranks
$i^{\prime}\in\\{i-1,i\\}$ should contribute to $\mathcal{S}$ (i.e. if they
correspond to a supermaximal extension) as described in Lemma 2. For brevity,
we show this decisional procedure only on two run breaks. Consider the $\tt
A$-run break at position $i=10$ (highlighted in blue in column $i$). The blue
box depicts the corresponding $\mathrm{LCP}$ interval,
$\mathrm{LCP}[box(10)]=\mathrm{LCP}[3,13]$. We observe that in $[3,13]$ there
are other $\tt A$-run breaks $i^{\prime\prime}$, such that
$\mathrm{LCP}[i^{\prime\prime}]>\mathrm{LCP}[10]$: those are
$i^{\prime\prime}=6,7,11,12$. We conclude that text position
$n-\mathrm{SA}[10]+2=6$ should not be included in $\mathcal{S}$. Consider now
the $\tt A$-run break $i=20$, highlighted in orange in column $i$. Position
$i^{\prime}=20-1=19$ is such that $\mathrm{BWT}[i^{\prime}]=\tt A$. The orange
box depicts the corresponding $\mathrm{LCP}$ interval,
$\mathrm{LCP}[box(20)]=\mathrm{LCP}[17,20]$. In this case, there is no other
$\tt A$-run break in $[17,20]$ with an $\mathrm{LCP}$ value larger than
$\mathrm{LCP}[20]=2$. We therefore insert text position
$n-SA[i^{\prime}]+2=n-SA[19]+2=13$ in $\mathcal{S}$. Notice that $i=20$ is
also a $\tt G$-run break; repeating the above reasoning, one can verify that
position $i^{\prime}=20$ is indeed associated with the supermaximal extension
$\tt AT\cdot G$ ending in text position $10$.

We immediately obtain a simple quadratic algorithm computing a suffixient set
of smallest cardinality: see Algorithm 1. Note that, in Lemma 2, if
$i^{\prime\prime}\in B_{i,c}$ and
$\mathrm{LCP}[i^{\prime\prime}]=\mathrm{LCP}[i]$, then
$box(i)=box(i^{\prime\prime})$. Since there could be multiple $c$-run breaks
$i^{\prime\prime}\in B_{i,c}$ such that
$\mathrm{LCP}[i^{\prime\prime}]=\mathrm{LCP}[i]$, if
$\mathrm{LCP}[i]=\mathrm{LCP}[i^{\prime\prime}]=\max\mathrm{LCP}[B_{i,c}]$
then we have to break ties and insert only one of the corresponding text
positions in the suffixient set. In Line 1 of Algorithm 1 we choose the
largest such $c$-run break: as a matter of fact, this defines a particular
tie-breaking strategy $<_{t}$ between positions $[n]$ (as required by
Definition 3).

input : A string $T[1,n]\in\Sigma^{n}$

output : A suffixient set $\mathcal{S}$ of smallest cardinality for $T$.

1 $\mathrm{BWT}\leftarrow\mathrm{BWT}(T^{\text{rev}})$;
$\mathrm{LCP}\leftarrow\mathrm{LCP}(T^{\text{rev}})$;
$\mathrm{SA}\leftarrow\mathrm{SA}(T^{\text{rev}})$;

2 $\mathcal{S}\leftarrow\emptyset$;

3 for  _$i=2,\dots,n$_ do

4 if  _$\mathrm{BWT}[i-1]\neq\mathrm{BWT}[i]$_ then

5 for  _$i^{\prime}\in\\{i-1,i\\}$_ do

$c\leftarrow\mathrm{BWT}[i^{\prime}]$ ;

/* $i$ is a $c$-run break */

6 if  _$i=\max\\{i^{\prime\prime}\ :\ i^{\prime\prime}\in
B_{i,c}\wedge\mathrm{LCP}[i^{\prime\prime}]=\max\mathrm{LCP}[B_{i,c}]\\}$_
then

7 $\mathcal{S}\leftarrow\mathcal{S}\cup\\{n-\mathrm{SA}[i^{\prime}]+2\\}\;$

8 end if

9

10 end for

11

12 end if

13

14 end for

15return $\mathcal{S}$;

Algorithm 1 Quadratic algorithm to compute a smallest suffixient set

Computing $\mathrm{BWT}$, $\mathrm{LCP}$, and $\mathrm{SA}$ in Line 1 takes
$O(n)$ time. Additionally, for each $i=2,\dots,n$, Algorithm 1 computes the
set $B_{i,c}$ in line 1 by scanning $\mathrm{LCP}[\dots,i-1,i,i+1,\dots]$ in
order to identify $\mathrm{LCP}[box(i)]$ ($O(n)$ time for each such scan). It
follows that the total running time is bounded by $O(n^{2})$. Correctness
follows immediately from Lemma 2, Definition 3, and Lemma 1.

###  4.2 A one-pass algorithm working in compressed space

In this section, we speed up the simple quadratic algorithm provided in the
previous section. We will refer to this version as "one-pass" since it only
requires one scan of the $\mathrm{BWT}$, $\mathrm{SA}$, and $\mathrm{LCP}$
arrays. The algorithm is summarized in Algorithms 2 and 3. See below for a
description.

input : A string $T[1..n]$ over a finite alphabet $\Sigma$.

output : A suffixient set $\mathcal{S}$ of smallest cardinality for $T$.

$\mathcal{S}\leftarrow\emptyset$ ;

/* initialize the empty suffixient set $\mathcal{S}$ */

1 $\mathrm{BWT}\ \leftarrow\textrm{BWT}(T^{\text{rev}})$; $\mathrm{LCP}\
\leftarrow\textrm{LCP}(T^{\text{rev}})$; $\mathrm{SA}\
\leftarrow\textrm{SA}(T^{\text{rev}})$;

$R[1,\sigma]\leftarrow((-1,0,false),\dots,(-1,0,false))$ ;

/* $\mathrm{LCP}$ local maxima */

$m\leftarrow\infty$;

/* $\mathrm{LCP}$ minimum inside current BWT run */

2

3for  _$i=2,\dots,n$_ do

4

5 $m\leftarrow\min\\{m,\mathrm{LCP}[i]\\}$;

6

7 if  _$\mathrm{BWT}[i]\neq\mathrm{BWT}[i-1]$_ then

8 $eval(\Sigma,m,R,\mathcal{S})$;

9 for  _$i^{\prime}\in\\{i-1,i\\}$_ do

10 if  _$\mathrm{LCP}[i] >R[\mathrm{BWT}[i^{\prime}]].len$_ then

11
$R[\mathrm{BWT}[i^{\prime}]]\leftarrow(\mathrm{LCP}[i],n-\mathrm{SA}[i^{\prime}]+2,true)$;

12

13 end if

14

15 end for

16 $m\leftarrow\infty$;

17

18 end if

19

20 end for

21

$eval(\Sigma,-1,R,\mathcal{S})$ ;

/* evaluate last active candidates */

22 return $\mathcal{S}$;

Algorithm 2 One-pass algorithm

input : A set of characters $C$, a LCP value $l$, the candidate’s list $R$ and
the suffixient set $\mathcal{S}$.

output : The updated suffixient set $\mathcal{S}$.

1

2foreach  _$c\in C$_ do

3 if  _$l <R[c].len$_ then

4 if  _$R[c].active$_ then

5 $\mathcal{S}\leftarrow\mathcal{S}\cup\\{R[c].pos\\}$;

6

7 end if

8 $R[c]\leftarrow\\{l,0,false\\}$;

9

10 end if

11

12 end foreach

13

Algorithm 3 Procedure $eval(C,l,R,\mathcal{S})$

Observe that Algorithm 1 runs in quadratic time due to the fact that it needs
to scan $\mathrm{LCP}[box(i)]$ for each run break $i$, and those boxes
overlap. Intuitively, Algorithm 2 avoids this inefficiency by storing
information about local LCP maxima on $c$-run breaks (for each $c\in\Sigma$)
in a data structure $R$ (Line 3). Intuitively, this allows us to detect if a
previous box $box(j)$, with $j<i$, ends in position $i$ by simply checking if
$\mathrm{LCP}[j]$ drops below the current LCP maxima associated with each
character $c$.

Assume we scanned the arrays $\mathrm{BWT}$, $\mathrm{SA}$, and $\mathrm{LCP}$
up to position $i$. $R$ is a map associating each $c\in\Sigma$ with
information related with some $c$-run break $j\leq i$ corresponding to a
candidate supermaximal extension $\alpha\cdot c$. Each entry
$R[c]=(len,pos,active)$ is composed of three values:
$R[c].len=\mathrm{LCP}[j]$ (i.e., the length of the right-maximal string
$\alpha$), $R[c].pos=text(j^{\prime})=n-\mathrm{SA}[j^{\prime}]-2$, where
$j^{\prime}\in\\{j-1,j\\}$ is such that $\mathrm{BWT}[j^{\prime}]=c$ (i.e. the
position of the last character of the supermaximal extension $\alpha\cdot c$
in $T$), and a boolean flag $R[c].active$ which is set to $true$ if and only
if $R[c].len$ is the maximum value in $\mathrm{LCP}[B_{j,c}\cap[i]]$ (breaking
ties by smaller $j$: we keep the first encountered such maximum). Depending on
the value of flag $active$, we will distinguish between active and inactive
candidates.

###### Example 3

See Figure 1 and assume we scanned $\mathrm{BWT}$ up to position $j=4$. The
candidate associated with letter $\tt T$ is $R[{\tt T}]=(2,3,true)$, where
$R[{\tt T}].len=\mathrm{LCP}[4]=2$. This candidate is active since
$\mathrm{LCP}[4]$ is the largest value in $\mathrm{LCP}[B_{4,{\tt T}}$
$\cap[4]]=\\{2\\}$. When processing position $j=6$, we find another $\tt
T$-run break. Here we update $R[{\tt T}]=(5,7,true)$ since $6\in B_{4,{\tt
T}}\cap[6]$, and $5=\mathrm{LCP}[6]>\mathrm{LCP}[4]$.

Algorithm 2 works as follows. We scan the $\mathrm{BWT}$ left-to-right:
$\mathrm{BWT}[2]$, $\dots$, $\mathrm{BWT}[i]$ (for $i=2,\dots,n$). For
$c\in\Sigma$, let $j<i$ be the $c$-run break whose information is stored in
$R[c]$, i.e. such that $\mathrm{LCP}[j]=R[c].len$. If
$\mathrm{LCP}[i]<R[c].len$, then $i\notin box(j)$. But then, if
$R[c].active=true$, position $R[c].pos$ must belong to the output set so we
have to insert it in $\mathcal{S}$. We also set $R[c].active=false$ in order
to record that the maximum in $\mathrm{LCP}[B_{j,c}]$ has been found (if
$R[c].active$ is already equal to $false$, $\mathcal{S}$ does not need to be
updated since the maximum in $\mathrm{LCP}[B_{j,c}]$ had already been found).
Observe that these operations, performed by the call to
$eval(\Sigma,m,R,\mathcal{S})$ (lines 8,17) (see below for the meaning of
variable $m$), have to be repeated for each $c\in\Sigma$; however, since $i$
can possibly replace the candidate in $R[c]$ only if $i$ is a $c$-run break,
we can avoid calling $eval(\cdot)$ inside equal-letter $\mathrm{BWT}$ runs as
follows: we compute the minimum $\mathrm{LCP}$ value $m$ inside $\mathrm{LCP}$
intervals corresponding to $\mathrm{BWT}$ equal-letter runs (line 6), and
perform the check $m<R[c].len$ for each $c\in\Sigma$ by calling procedure
$eval(\Sigma,m,R,\mathcal{S})$ (costing time $O(\sigma)$) only when the
current position $i$ is a run break. This ultimately reduces the algorithm’s
running time from $O(n\cdot\sigma)$ to $O(n+\bar{r}\cdot\sigma)$.

On the other hand, if $i$ is a $c$-run break and $\mathrm{LCP}[i]>R[c].len$,
then $i\in B_{j,c}\cap[i]$ and $R[c].len$ is not a local maximum in
$\mathrm{LCP}[B_{j,c}]$ (line 10). In this case, we have to replace the
candidate stored in $R[c]$ with the information associated with the new
candidate $i$: letting $i^{\prime}\in\\{i-1,i\\}$ be such that
$\mathrm{BWT}[i^{\prime}]=c$, we replace
$R[c]\leftarrow(\mathrm{LCP}[i],n-\mathrm{SA}[i^{\prime}]+2,true)$ (line 11).

###### Example 4

Continuing Example 3. When processing the $\tt T$-run break $j=7$, we see that
$\mathrm{LCP}[7]<R[{\tt T}].len$. Thus, we reached the end of $box(6)=[6,6]$,
where max $\mathrm{LCP}[B_{6,{\tt T}}]=R[{\tt T}].len=5$, and insert $R[{\tt
T}].pos$ in $\mathcal{S}$. Next, we update $R[{\tt T}]=(4,0,false)$. On $j=8$,
we again update $R[{\tt T}]=(1,0,false)$. Finally, on $j=9$, we get
$\mathrm{LCP}[9]>R[{\tt T}].len$ since $box(6)$ and $box(9)$ are now disjoint.
We update $R[{\tt T}]=(\mathrm{LCP}[9],12,true)$ to the active state.

We obtain (see Appendix 0.A for a more detailed proof):

######  Lemma 3 ()

Given a text $T[1,n]$ over alphabet of size $\sigma$, Algorithm 2 computes the
smallest suffixient set $\mathcal{S}$ in $O(n+\bar{r}\cdot\sigma)$ time and
$O(n)$ words of space.

Observe that in Algorithm 3 (procedure $eval(\cdot)$), only entries such that
$l<R[c].len$ are possibly modified. This suggests that $R$ could be sorted in
order to speed up operations. Indeed, it turns out that $R$ can be replaced
with a data structure based on dynamic partial sums, such that operation
$eval(\Sigma,m,R,\mathcal{S})$ at Line 2 of Algorithm 2 costs amortized time
$O(\log\sigma)$. With this modification, Algorithm 2 runs in
$O(n+\bar{r}\log\sigma)$ time. We do not enter into the details of this
solution, since (i) in the next section we will present an optimal $O(n)$-time
solution, and (ii) our one-pass algorithm is mainly of practical interest (see
also next paragraph) and in practice the map $R$ fits in cache ($\sigma$ is
small).

#### One-pass algorithm in compressed space

One important feature of our algorithm is that we only need one scan of the
$\mathrm{BWT}$, $\mathrm{SA}$, and $\mathrm{LCP}$ to compute $\mathcal{S}$.
This means that our algorithm also works in the streaming scenario where these
arrays are provided one element at a time, from first to last. We now show
that this feature can be exploited to run the algorithm in compressed working
space.

Prefix-free parsing (PFP) is a technique introduced by Boucher et al. [2] to
ease the computational burden of computing the $\mathrm{BWT}$ of large and
repetitive texts. Briefly, with one linear-time scan, PFP divides the input
$T$ into overlapping segments, called phrases, of variable length, which are
then used to construct what is referred to as the dictionary $D$ and parse $P$
of the text. Then, with a separate linear-time algorithm, the $\mathrm{BWT}$
of $T$ is directly computed from $D$ and $P$; thus using space proportional to
the combined size of the two data structures. In [6, 7], it was shown how to
modify PFP in order to compute also the $\mathrm{SA}$ and the $\mathrm{LCP}$
arrays. This version streams the three arrays $\mathrm{BWT}$, $\mathrm{LCP}$,
and $\mathrm{SA}$ in $O(|D|+|P|)$ compressed space, from their first to last
entry; this is sufficient for running Algorithm 2 in compressed space, without
affecting its running time. The only major change consists in modifying PFP to
compute the dictionary and parse of $T^{\text{rev}}$ instead of $T$. This can
actually be achieved very easily with a left-to-right scan of $T$; see
Appendix 0.B.1 for more details. In Section 5 we present an implementation of
this PFP-based algorithm.

###  4.3 Linear-time algorithm

In this section, we further speed up the one-pass algorithm provided in the
previous section and achieve linear time. Our new algorithm is summarized in
Algorithm 4.

As previously discussed, in Algorithm 2, for the one-character extension of
every $\mathrm{BWT}$ equal-letter $\mathrm{BWT}[i^{*},i]=cc\dots ccx$ (with
$x\neq c$) we run procedure eval (Algorithm 3) to check if
$\min\mathrm{LCP}[i^{*}+1,i]$ drops below the current $\mathrm{LCP}$ maxima
associated to $y$-run breaks, for all $y\in\Sigma$. In the end, this step
charges an additional $O(\bar{r}\sigma)$ term (which we mentioned can be
reduced to $O(\bar{r}\log\sigma)$ by using opportune data structures).
Intuitively, Algorithm 4 avoids this cost by calling the _eval_ procedure only
on the two candidates $R[c^{\prime}]$, where
$c^{\prime}\in\mathrm{BWT}[i-1,i]$. We achieve this by introducing a new
vector $\mathrm{LF}[1,\sigma]$ updated on-the-fly, implementing the _LF-
mapping_ property of the Burrows-Wheeler transform. More formally: assume we
have scanned the $\mathrm{BWT}$ up to the $c$-run break $i$, and let
$i^{\prime}\in\\{i-1,i\\}$ be such that $\mathrm{BWT}[i^{\prime}]=c$. Then,
$\mathrm{LF}$ is such that
$\mathrm{LF}[\mathrm{BWT}[i^{\prime}]]=\mathrm{LF}[c]=j$, with
$\mathrm{SA}[j]=\mathrm{SA}[i^{\prime}]+1$. In other words, $\mathrm{BWT}[j]$
is the character preceding $\mathrm{BWT}[i^{\prime}]$ in $T^{\text{rev}}$. Our
linear-time algorithm is based on the following idea. Assume for simplicity
that $i$ is not the first $c$-run break. Let $i^{*}<i$ be the largest integer
such that $i^{*}$ is a $c$-run break as well (i.e. $i^{*}$ is the $c$-run
break immediately preceding $i$). As in Algorithm 2, our new Algorithm 4
stores in entry $R[c].len$ the value $R[c].len=\mathrm{LCP}[i^{*}]$. By Lemma
2, we have to discover if $i\in B_{i^{*},c}$; if this is the case, then we
compare $\mathrm{LCP}[i]$ and $\mathrm{LCP}[i^{*}]$ and decide if
$\mathrm{LCP}[i]$ is the new maximum in $B_{i^{*},c}\cap[i]$ (i.e.
$\mathrm{LCP}[i]>\mathrm{LCP}[i^{*}]$) or if the local maximum among $c$-run
breaks in $B_{i^{*},c}\cap[i]$ had already been found (i.e.
$\mathrm{LCP}[i]\leq\mathrm{LCP}[i^{*}]$). If, on the other hand, $i\notin
B_{i^{*},c}$, then we insert in $\mathcal{S}$ the local maximum $R[c].pos$
relative to $B_{i^{*},c}$ if and only if $R[c].active=true$ (if
$R[c].active=false$, then the suffixient position corresponding to the local
maximum of $B_{i^{*},c}$ had already been stored in $\mathcal{S}$).

In order to discover if $i\in B_{i^{*},c}$, we distinguish two cases.

(i) If $\mathrm{BWT}[i-1]=c$ then, since $i^{*}$ is the previous $c$-run
break, it must be the case that
$\mathrm{BWT}[i^{*}-1,i^{*},\dots,i-1,i]=ycc\dots ccx$, for some $x\neq c$ and
$y\neq c$. It follows that $i\in B_{i^{*},c}$ if and only if
$\min\mathrm{LCP}[i^{*},i]\geq R[c].len=\mathrm{LCP}[i^{*}]$. Algorithm 4
computes $\min\mathrm{LCP}[i^{*},i]$ analogously as Algorithm 2, i.e. by
updating a variable $m$ storing the minimum $\mathrm{LCP}$ inside intervals
corresponding to $\mathrm{BWT}$ equal-letter runs.

(ii) If, on the other hand, $\mathrm{BWT}[i-1]=x\neq c$, then since $i^{*}$ is
the previous $c$-run break, it must be that
$\mathrm{BWT}[i^{*}-1,i^{*},\ldots,i-1,i]=cy...xc$, for some $x\neq c$ and
$y\neq c$ (and there are no other occurrences of $c$ between
$\mathrm{BWT}[i^{*}-1]$ and $\mathrm{BWT}[i]$). As in the previous case, the
goal is to compute $\min\mathrm{LCP}[i^{*},i]$. We achieve this by using the
$\mathrm{LF}$ array. Due to the way the array $\mathrm{LF}$ is defined and
constructed, we know that
$\min\mathrm{LCP}[i^{*},i]=\mathrm{LCP}[\mathrm{LF}[c]]-1$. As a result, we
have that $i\in B_{i^{*},c}$ if and only if
$\mathrm{LCP}[\mathrm{LF}[c]]-1\geq R[c].len=\mathrm{LCP}[i^{*}]$.

In Appendix 0.A we provide all the details behind the above intuition and
prove:

######  Lemma 4 ()

Given a text $T[1,n]$ over $\Sigma$, Algorithm 4 computes the smallest
suffixient set $\mathcal{S}$ in $O(n)$ time and $O(n)$ words of space.

##  5 Experimental results

We implemented the one-pass and linear-time algorithms in C++ and made them
publicly available at https://github.com/regindex/suffixient. The one-pass
algorithm uses Prefix Free Parsing (PFP) as discussed in Section 4.2 and runs
in compressed working space. We divide our experimental evaluation into two
parts: first, we empirically study the new repetitiveness measure $\chi$ by
comparing it with $\bar{r}$ using different alphabet orderings; then, we
assess the performance of our PFP-based one-pass algorithm on massive genomics
datasets (see Appendix 0.C.1 for more details on the experimental setup). We
do not provide comparisons with our linear-time algorithm since the necessary
data structures would not fit in the internal memory for such large datasets.

#### The repetitiveness measure $\chi$

In this experiment, we used nine biological datasets divided into two corpora.
The first corpus contains six datasets containing DNA sequences from the
Pizza&Chilli collection111 https://pizzachili.dcc.uchile.cl, while the second
contains three datasets made by concatenating genomic sequences of different
types. The three datasets of the second corpus are formed by 3,600 SARS-CoV-2
assembled viral genomes, 220 Salmonella enterica assembled bacterial genomes,
and 17 copies of the human Chromosome 19, respectively. We downloaded data
from different sources: the viral genomes from the COVID-19 Data
Portal222https://www.covid19dataportal.org, the bacterial genomes from NCBI
333https://www.ncbi.nlm.nih.gov/assembly/?term=Salmonella+enterica, while the
Chromosome 19 sequences belong to the 1,000 Genome
project444https://github.com/koeppl/phoni. All datasets were filtered in order
to keep only nucleotide characters ${\tt A,C,G,T}$, in addition to the string
terminator $\$$. As a consequence, the alphabet size in our experiments was
$\sigma=5$.

input : A string $T[1..n]$ over a finite alphabet $\Sigma$.

output : A smallest suffixient set for $T$.

$\mathcal{S}\leftarrow\emptyset$ ;

/* initialize the empty suffixient set $\mathcal{S}$ */

1 $\mathrm{BWT}\ \leftarrow\textrm{BWT}(T^{\text{rev}})$; $\mathrm{LCP}\
\leftarrow\textrm{LCP}(T^{\text{rev}})$; $\mathrm{SA}\
\leftarrow\textrm{SA}(T^{\text{rev}})$;

$R[1,\sigma]\leftarrow((-1,0,false),\dots,(-1,0,false))$ ;

/* $\mathrm{LCP}$ local maxima */

$\mathrm{LF}[1,\sigma]\leftarrow(0,\dots,0)$;

/* LF mapping */

$m\leftarrow\infty$;

/* $\mathrm{LCP}$ minimum inside current BWT run */

2

3for all $c=2,\dots,\sigma$:
$\mathrm{LF}[c]\leftarrow\mathrm{LF}[c-1]+occ(T,c-1)$;

4

5$\mathrm{LF}[\mathrm{BWT}[1]]\leftarrow\mathrm{LF}[\mathrm{BWT}[1]]+1$;

6

7for  _$i=2,\dots,n$_ do

8

9 $\mathrm{LF}[\mathrm{BWT}[i]]\leftarrow\mathrm{LF}[\mathrm{BWT}[i]]+1$;

10 $m\leftarrow\min\\{m,\mathrm{LCP}[i]\\}$;

11

12 if  _$\mathrm{BWT}[i]\neq\mathrm{BWT}[i-1]$_ then

13

14 for  _$i^{\prime}\in\\{i-1,i\\}$_ do

15

16 if $i^{\prime}=i-1$ then
$eval(\\{\mathrm{BWT}[i^{\prime}]\\},m,R,\mathcal{S})$;

17 else if  _$R[\mathrm{BWT}[i^{\prime}]].len\neq-1$_ then

18
$eval(\\{\mathrm{BWT}[i^{\prime}]\\},\mathrm{LCP}[\mathrm{LF}[\mathrm{BWT}[i^{\prime}]]]-1,R,\mathcal{S})$;

19 end if

20

21

22 if  _$\mathrm{LCP}[i] >R[\mathrm{BWT}[i^{\prime}]].len$_ then

23
$R[\mathrm{BWT}[i^{\prime}]]\leftarrow(\mathrm{LCP}[i],n-\mathrm{SA}[i^{\prime}]+2,true)$;

24

25 end if

26

27 end for

28

29 $m\leftarrow\infty$;

30

31 end if

32

33 end for

34

$eval(\Sigma,-1,R,\mathcal{S})$ ;

/* evaluate last active candidates */

35 return $\mathcal{S}$;

Algorithm 4 Linear-time algorithm

We compared the behavior of our new measure $\chi$ with the well-known measure
$\bar{r}$: the number of equal-letter runs in the BWT of the reversed text.
Since, unlike $\chi$, measure $\bar{r}$ depends on a specific alphabet
ordering, we explicitly computed $\bar{r}$ for all $(\sigma-1)!=24$ possible
orderings (character $\$$ is always required to be the lexicographically-
smallest one). Table 1 shows our results. Among all possible alphabet
orderings, we only show the default one ${\tt A<C<G<T}$, and the ones yielding
the largest and smallest $\bar{r}$.

corpus dataset dataset length $\chi$ default $\bar{r}$ min. $\bar{r}$ max.
$\bar{r}$ Pizza&Chili Cere 428,111,842 9,945,553 11,556,075 11,512,279
11,578,575 E. Coli 112,682,447 13,126,726 15,041,926 14,974,687 15,043,686
Influenza 154,795,431 2,234,085 3,015,173 2,979,820 3,023,774 Para 412,279,605
13,399,378 15,581,823 15,475,176 15,635,533 dna 403,919,018 215,201,641
243,480,086 243,179,189 243,574,132 dna.001.1 104,857,499 1,414,711 1,717,155
1,715,622 1,718,418 Chrom. 19 1,005,131,693 28,224,334 32,442,979 32,355,166
32,457,646 biological Salmonella 1,043,921,849 19,071,791 22,408,284
22,255,198 22,417,175 SarsCov2 949,959,504 1,068,951 1,351,234 1,347,182
1,352,671

Table 1: Summary of the results on the nine datasets. From left to right, we
report the corpus name, the dataset name, the dataset length (number of
characters), the size of the smallest suffixient set ($\chi$), and the number
of runs of the BWT of the reversed text ($\bar{r}$) for three different
alphabet ordering: the default lexicographic order, and the two orderings
leading to the minimum and maximum $\bar{r}$.

We observe that, in practice, $\chi$ is very close to (and always smaller
than) $\bar{r}$ under any alphabet ordering; notice that theory only predicts
$\chi\leq 2\bar{r}$ (see [4] and the end of Section 4.1). In this experiment,
the minimum of $\bar{r}$ was always between 1.13 (dna) and 1.33 (Influenza)
times larger than $\chi$. We also observe that, while the alphabet ordering
does not have a big influence on $\bar{r}$, the default alphabet ordering
never yields the smallest $\bar{r}$. This suggests experimentally that $\chi$
is a better repetitiveness measure than $\bar{r}$, since it is not affected by
the alphabet order (while always being close to $\bar{r}$).

#### Smallest suffixient set of massive datasets

In this experiment, we tested our PFP-based one-pass algorithm on two large
genomic datasets: the first dataset is formed by 1,000 human Chromosome 19
copies (59GB), while the second contains 2,005,773 Sars-CoV-2 viral sequences
(60GB). Both input and output were streamed from/to disk, keeping in RAM only
the PFP data structures. In both cases, our algorithm performed very well with
a maximum resident set size of 20.6 GB and 29.5 GB and a wall clock time of
55:55 (min:sec) and 2:16:48 (h:min:sec), respectively.

## References

  * [1] Bentley, J.W., Gibney, D., Thankachan, S.V.: On the complexity of BWT-runs minimization via alphabet reordering. In: Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020). LIPIcs, vol. 173, pp. 15:1–15:13 (2020). https://doi.org/10.4230/LIPICS.ESA.2020.15
  * [2] Boucher, C., Gagie, T., Kuhnle, A., Langmead, B., Manzini, G., Mun, T.: Prefix-free parsing for building big BWTs. Algorithms Mol. Biol. 14(1), 13:1–13:15 (2019). https://doi.org/10.1186/S13015-019-0148-5
  * [3] Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation (1994)
  * [4] Depuydt, L., Gagie, T., Langmead, B., Manzini, G., Prezza, N.: Suffixient sets (2024), https://arxiv.org/abs/2312.01359
  * [5] Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). p. 827–840. STOC 2018, Association for Computing Machinery, New York, NY, USA (2018). https://doi.org/10.1145/3188745.3188814, https://doi.org/10.1145/3188745.3188814
  * [6] Kuhnle, A., Mun, T., Boucher, C., Gagie, T., Langmead, B., Manzini, G.: Efficient construction of a complete index for pan-genomics read alignment. J. Comput. Biol. 27(4), 500–513 (2020). https://doi.org/10.1089/CMB.2019.0309
  * [7] Rossi, M., Oliva, M., Langmead, B., Gagie, T., Boucher, C.: MONI: A pangenomic index for finding maximal exact matches. J. Comput. Biol. 29(2), 169–187 (2022). https://doi.org/10.1089/CMB.2021.0290

##  Appendix 0.A Deferred proofs

See 1

###### Proof

To see that $\mathcal{S}$ is suffixient, consider any right-maximal substring
$T[i,j-1]$ ($i\leq j\leq n$). We want to prove that there exists
$x\in\mathcal{S}$ such that $T[i,j]$ is a suffix of $T[1,x]$. Let $T[1,x]$ be
a prefix of $T$ being suffixed by $T[i,j]$, breaking ties (on its endpoint
$x$) by $<_{t}$. If $T[i,j]$ is a supermaximal extension, then by Definition 3
it holds $x\in\mathcal{S}$ and we are done. Otherwise, let
$T[i^{\prime},j^{\prime}]\neq T[i,j]$ be a one-character extension of a right-
maximal string $T[i^{\prime},j^{\prime}-1]$ such that $T[i,j]$ is a suffix of
$T[i^{\prime},j^{\prime}]$. Without loss of generality, let
$T[i^{\prime},j^{\prime}]$ be the string of maximum length
$|T[i^{\prime},j^{\prime}]|=j^{\prime}-i^{\prime}+1$ with this property.
Observe that there cannot be a right-extension
$T[i^{\prime\prime},j^{\prime\prime}]\neq T[i^{\prime},j^{\prime}]$ of a
right-maximal string $T[i^{\prime\prime},j^{\prime\prime}-1]$ such that
$T[i^{\prime},j^{\prime}]$ is a suffix of
$T[i^{\prime\prime},j^{\prime\prime}]$, otherwise $T[i,j]$ would be a suffix
of $T[i^{\prime\prime},j^{\prime\prime}]$ and
$|T[i^{\prime\prime},j^{\prime\prime}]|>|T[i^{\prime},j^{\prime}]|$,
contradicting the fact that $T[i^{\prime},j^{\prime}]$ is the longest such
string. It follows that $T[i^{\prime},j^{\prime}]$ is a supermaximal
extension. Let $T[1,y]$ be a prefix of $T$ being suffixed by
$T[i^{\prime},j^{\prime}]$, breaking ties (on $y$) by $<_{t}$. Then, by
Definition 3, $y\in\mathcal{S}$. Also in this case we are done, since $T[i,j]$
suffixes $T[i^{\prime},j^{\prime}]$ and $T[i^{\prime},j^{\prime}]$ suffixes
$T[1,y]$, so by transitivity of the suffix relation, $T[i,j]$ suffixes
$T[1,y]$.

To see that $\mathcal{S}$ is of minimum cardinality, let $S$ be a suffixient
set. We prove $|\mathcal{S}|\leq|S|$ by exhibiting an injective function from
$\mathcal{S}$ to $S$.

Let $SE\subseteq\Sigma^{+}$ be the set of all supermaximal extensions. By
definition of supermaximal extension, note that any prefix $T[1,j]$ can be
suffixed by at most _one_ supermaximal extension $T[i,j]$: assume, for a
contradiction, that $T[1,j]$ is suffixed by two distinct supermaximal
extensions $T[i,j]\neq T[i^{\prime},j]$. Without loss of generality,
$i^{\prime}<i$. But then, $T[i,j]$ is a suffix of $T[i^{\prime},j]$, hence
$T[i,j]$ cannot be a supermaximal extension, a contradiction.

We first define a relation $h:\mathcal{S}\rightarrow SE$ mapping every
$x\in\mathcal{S}$ to a supermaximal extension $h(x)=T[i,j]$ such that $T[i,j]$
is a suffix of $T[1,x]$. From the observation above, there is at most one such
string $T[i,j]$. From Definition 3, there exists one such $T[i,j]$. We
conclude that $h$ is a function. We now prove that $h$ is injective.

To see that $h$ is injective, assume for a contradiction $h(x)=h(y)$ for some
$x\neq y$ with $x,y\in\mathcal{S}$. Let $h(x)=h(y)=T[i,j]$. By Definition 3,
there exists a supermaximal extension $T[i_{x},x]$ such that $T[1,x]$ is the
prefix of $T$ being suffixed by $T[i_{x},x]$ with largest endpoint $x$,
according to the total order $<_{t}$. Following the same reasoning on position
$y$, we can associate an analogous supermaximal extension $T[i_{y},y]$ to $y$.
On the other hand, by the definition of $h$, also string $h(x)=h(y)=T[i,j]$ is
a supermaximal extension that suffixes both $T[1,x]$ and $T[1,y]$. Since
$T[i,j]$ and $T[i_{x},x]$ are supermaximal extensions that suffix $T[1,x]$ and
(as proved above) there can exist at most one supermaximal extensions
suffixing $T[1,x]$, we conclude that $T[i,j]=T[i_{x},x]$. Similarly, we
conclude $T[i,j]=T[i_{y},y]$, hence $T[i_{x},x]=T[i_{y},y]$. We obtained a
contradiction, since Definition 3 requires both $x<_{t}y$ and $y<_{t}x$ and
$<_{t}$ is a total order. We conclude that $h$ is an injective function.

Next, we define a relation $g:SE\rightarrow S$ from the set $SE$ of
supermaximal extensions to positions in $S$. For any supermaximal extension
$T[i,j]\in SE$, we define $g(T[i,j])=x$ to be the largest element of $S$
(according to the standard order between integers) such that $T[1,x]$ is
suffixed by $T[i,j]$. Such a position must exist since $S$ is a suffixient
set, so $g$ is a function. To see that $g$ is also injective, assume for a
contradiction $g(T[i,j])=g(T[i^{\prime},j^{\prime}])=x$, for $T[i,j]\neq
T[i^{\prime},j^{\prime}]$ (both supermaximal extensions). By the definition of
$g$, both $T[i,j]$ and $T[i^{\prime},j^{\prime}]$ are suffixes of $T[1,x]$.
But then, since $T[i,j]\neq T[i^{\prime},j^{\prime}]$, either $T[i,j]$ is a
suffix of $T[i^{\prime},j^{\prime}]$ (so $T[i,j]$ is not a supermaximal
extension) or the other way round (so $T[i^{\prime},j^{\prime}]$ is not a
supermaximal extension). In both cases we get a contradiction, so we conclude
that $g$ is injective.

We conclude the proof by observing that $g\circ h:\mathcal{S}\rightarrow S$ is
the composition of two injective functions and is therefore injective. ∎

See 2

###### Proof

_(1)_ Let $i$ be a $c$-run break. Let
$i^{\prime},i^{\prime\prime}\in\\{i,i-1\\}$ be such that
$\mathrm{BWT}[i^{\prime}]=c$ and $\mathrm{BWT}[i^{\prime\prime}]=a\neq c$. Let
$j^{\prime}=text(i^{\prime})$ and $j^{\prime\prime}=text(i^{\prime\prime})$.
Let moreover $\ell=\mathrm{LCP}[i]$, and assume
$\ell=\max\mathrm{LCP}[B_{i,c}]$.

Note that $T[j^{\prime}-\ell,j^{\prime}-1]$ is right-maximal:
$\ell=\mathrm{LCP}[i]$ implies that
$T[j^{\prime}-\ell,j^{\prime}-1]=T[j^{\prime\prime}-\ell,j^{\prime\prime}-1]$
and, by definition of $i^{\prime},i^{\prime\prime},j^{\prime}$, and
$j^{\prime\prime}$ we have that
$T[j^{\prime}]=\mathrm{BWT}[i^{\prime}]\neq\mathrm{BWT}[i^{\prime\prime}]=T[j^{\prime\prime}]$.

Assume, for a contradiction, that $T[j^{\prime}-\ell,j^{\prime}]$ is not a
supermaximal extension. Then, since $T[j^{\prime}-\ell,j^{\prime}-1]$ is
right-maximal, it must be the case that $T[j^{\prime}-\ell,j^{\prime}]$ is a
suffix of some string $T[\hat{j}-\hat{\ell},\hat{j}]$ with $\hat{\ell}>\ell$
and such that $T[\hat{j}-\hat{\ell},\hat{j}-1]$ is right-maximal. Let
$\hat{i}=bwt(\hat{j})$. Since $T[j^{\prime}-\ell,j^{\prime}]$ is a suffix of
$T[\hat{j}-\hat{\ell},\hat{j}]$ we have that $T[j^{\prime}-\ell,j^{\prime}-1]$
is a suffix of $T[\hat{j}-\hat{\ell},\hat{j}-1]$, hence it must be the case
that $\hat{i}\in box(i)$. Since $T[\hat{j}-\hat{\ell},\hat{j}-1]$ is right-
maximal and $T[\hat{j}]=c$, without loss of generality we can assume that
$\hat{i}\in\\{k-1,k\\}$, where $k$ is a $c$-run break (such a $c$-run break
must exist in $box(i)$) and $\mathrm{LCP}[k]\geq\hat{\ell}$. In particular,
$k\in box(i)$. Then, $\mathrm{LCP}[k]\geq\hat{\ell}>\ell$ and $k\in box(i)$
yield $\max\mathrm{LCP}[B_{i,c}]\geq\hat{\ell}>\ell$, a contradiction.

_(2)_ Let $T[j^{\prime}-\ell,j^{\prime}]$ be a supermaximal extension and let
$c=T[j^{\prime}]$. Let $i^{\prime}=bwt(j^{\prime})$. Since
$T[j^{\prime}-\ell,j^{\prime}-1]$ is right-maximal, we can assume without loss
of generality that either
$\mathrm{BWT}[i^{\prime}]\neq\mathrm{BWT}[i^{\prime}-1]$ or
$\mathrm{BWT}[i^{\prime}]\neq\mathrm{BWT}[i^{\prime}+1]$. Let therefore
$i^{\prime}\in\\{i,i-1\\}$, where $i$ is a $c$-run break. By definition of
$T[j^{\prime}-\ell,j^{\prime}]$, it holds $\ell=\mathrm{LCP}[i]$ (because
$T[j^{\prime}-\ell,j^{\prime}-1]$ is the longest right-maximal string
suffixing $T[1,j^{\prime}-1]$). We need to prove that
$\ell=\max\mathrm{LCP}[B_{i,c}]$. Assume, for a contradiction, that
$\ell<\hat{\ell}=\max\mathrm{LCP}[B_{i,c}]$. This means that there exists a
supermaximal extension $T[\hat{j}-\hat{\ell},\hat{j}]$ with (i)
$T[\hat{j}]=c$, (ii) $\hat{i}\in\\{k-1,k\\}$, where $\hat{i}=bwt(\hat{j})$ and
$k\in B_{i,c}$ is a $c$-run break in $box(i)$, and (iii)
$\mathrm{LCP}[k]=\hat{\ell}$. But then, since $k\in box(i)$ and
$T[\hat{j}-\hat{\ell},\hat{j}-1]$ is a right-maximal string of length
$\hat{\ell}>\ell$, we have that $T[j^{\prime}-\ell,j^{\prime}-1]$ is a
(proper) suffix of $T[\hat{j}-\hat{\ell},\hat{j}-1]$. This fact and
$T[\hat{j}]=c$ contradict the fact that $T[j^{\prime}-\ell,j^{\prime}]$ is a
supermaximal extension. ∎

See 3

###### Proof

Algorithm 2 scans the $\mathrm{BWT}$, $\mathrm{LCP}$, and $\mathrm{SA}$
exactly once and, for each run-break, checks if any of the $\sigma$ candidates
is a supermaximal extension using Algorithm 3. Since Algorithm 3 performs a
constant number of operations for each $c\in\Sigma$, the whole algorithm runs
in $O(n+\bar{r}\cdot\sigma)$ time. In addition, the only supplementary data
structure we need is $R$, which takes $O(\sigma)$ words of space; thus if
$\sigma<n$, altogether, we take $O(n)$ words of space.

We prove the correctness of Algorithm 2 by showing it computes the same output
of Algorithm 1. In particular, given $\mathcal{S^{\prime}}$, the output of
Algorithm 2, and $\mathcal{S}$, the output of Algorithm 1, we show that given
any value $s=n-\mathrm{SA}[i]+2$, where $i\in[n]$, _(1)_
$s\in\mathcal{S}\implies s\in\mathcal{S^{\prime}}$ and _(2)_
$s\notin\mathcal{S}\implies s\notin\mathcal{S^{\prime}}$.

_(1)_ let $(n-\mathrm{SA}[i^{\prime}]+2)\in\mathcal{S}$, where $i$ is a
$c$-run break, such that $i^{\prime}\in\\{i-1,i\\}$ and
$\mathrm{BWT}[i^{\prime}]=c$. By Lemma 2, it follows that
$\max\mathrm{LCP}[B_{i,c}]=\mathrm{LCP}[i]$. Assume we scanned the
$\mathrm{BWT}$ up to position $i$, there are three cases: $i^{\prime}$ is the
position of the first occurrence of $c$ in the $\mathrm{BWT}$, or there exists
another $c$-run break at position $j<i$, such that either $i\in B_{j,c}$ and
$\mathrm{LCP}[i]>\mathrm{LCP}[j]$, or $box(i)\cap box(j)=\emptyset$. For all
these three cases, $\mathrm{LCP}[i]>R[c].len$; thus, $i$ is set as the new
active $c$ candidate in $R$ (lines 10-12). Now, if $i^{\prime}$ is the
position of the last occurrence of $c$ in the $\mathrm{BWT}$, $R[c].pos$ is
inserted in $\mathcal{S}$ at the end of the algorithm (line 17); otherwise,
let $box(i)=[b,e]$, where $b\leq i\leq e$, we have $\forall
s\in\mathrm{LCP}[b,e],s\geq\mathrm{LCP}[i]$ and no $j^{\prime}\in[i+1,b]$ is a
$c$-run break such that $\mathrm{LCP}[j^{\prime}]>\mathrm{LCP}[i]$. Thus,
$R[c]$ is not updated until we scan $\mathrm{LCP}[e+1]$. At this point,
$R[c].len>\mathrm{LCP}[e+1]$ and since $R[c]$ is an active candidate; thus,
Algorithm 2 insert $R[c].pos=(n-\mathrm{SA}[i]+2)$ in $\mathcal{S^{\prime}}$
(Algorithm 3, line 4).

_(2)_ now let $(n-\mathrm{SA}[i^{\prime}]+2)\notin\mathcal{S}$, it follows by
Lemma 2, that $\exists j\in B_{i,c}$ such that
$\mathrm{LCP}[j]>\mathrm{LCP}[i]$ (for simplicity we consider the smallest
$j$). Assume we scanned the $\mathrm{BWT}$ up to position $i$; we need to
consider two cases: _(i)_ $j>i$ and _(ii)_ $j<i$. _(i)_ If $j>i$, let
$R[c].len=\mathrm{LCP}[i]$, then $\forall l\in\mathrm{LCP}[i+1,j],l\geq
R[c].len$; thus, $(n-\mathrm{SA}[i^{\prime}]+2)$ is not inserted in
$\mathcal{S}$ (lines 2-6, Algorithm 3) until position $j$. Here, we get
$\mathrm{LCP}[j]>R[c].len$ and, update
$R[c].pos=(n-\mathrm{SA}[j^{\prime}]+2)$ (lines 10-12), where
$j^{\prime}\in\\{j-1,j\\}$ and $\mathrm{BWT}[j^{\prime}]=c$. Due to this,
$(n-\mathrm{SA}[i^{\prime}]+2)$ is dropped and not inserted in
$\mathcal{S^{\prime}}$. _(ii)_ If $j<i$, then $\exists
l\in\mathrm{LCP}[j+1,i],l<\mathrm{LCP}[j]$; thus when we read $l$, $R[c]$ is
updated to the inactive state (line 6, Algorithm 3). However, since $\forall
s\in B_{i,c}\cap[j+1,i],\mathrm{LCP}[s]<\mathrm{LCP}[j]$ it means that $R[c]$
is never updated to the active state for any position in $[j+1,i]$ (we skip
lines 10-12), so also in this case $(n-\mathrm{SA}[i^{\prime}]+2)$ is not
inserted in $\mathcal{S^{\prime}}$.

See 4

###### Proof

Algorithm 4 scans the $\mathrm{BWT}$ exactly once and, for each position of
it, performs $O(1)$ accesses to the $\mathrm{SA}$ and the $\mathrm{LCP}$ and
calls Algorithm 3 at most once for each run break. Since Algorithm 3 performs
a constant number of operations and the $LF$-mapping array can be computed in
$O(n)$ time, the whole algorithm runs in $O(n)$ time. In addition, the only
supplementary data structure we need is $R$, which consumes $O(\sigma)$ words
of space; thus, altogether, we take $O(n+\sigma)$ words of space. Since we
assumed $\sigma\leq n$, the space consumption of Algorithm 4 is $O(n)$ words.

We prove the correctness of Algorithm 4 by showing it computes the same output
as the output computed by Algorithm 1. In particular, given
$\mathcal{S^{\prime}}$, the output of Algorithm 4, and $\mathcal{S}$, the
output of Algorithm 1, we show that for any value $s=n-\mathrm{SA}[i]+2$,
where $i\in[n]$, _(1)_ $s\in\mathcal{S}\implies s\in\mathcal{S^{\prime}}$ and
_(2)_ $s\notin\mathcal{S}\implies s\notin\mathcal{S^{\prime}}$.

_(1)_ let $(n-\mathrm{SA}[i^{\prime}]+2)\in\mathcal{S}$, where $i$ is a
$c$-run break, such that $i^{\prime}\in\\{i-1,i\\}$ and
$\mathrm{BWT}[i^{\prime}]=c$. By Lemma 2, we have
$\max\mathrm{LCP}[B_{i,c}]=\mathrm{LCP}[i]$. Assume we have scanned the
$\mathrm{BWT}$ up to position $i$. There are three cases: $i^{\prime}$ is the
position of the first occurrence of $c$ in the $\mathrm{BWT}$, or there exists
another $c$-run break at position $j<i$, such that either $i\in B_{j,c}$ or
$box(i)\cap box(j)=\emptyset$. In all three cases, since
$(n-\mathrm{SA}[i^{\prime}]+2)\in\mathcal{S}$, we have
$\mathrm{LCP}[i]>R[c].len$; thus, $i$ is set as the new active $c$ candidate
in $R$ (lines 17-19). If $i^{\prime}$ is the position of the last occurrence
of $\mathrm{BWT}[i^{\prime}]$, since $R[c].active=true$, after traversing the
whole $\mathrm{BWT}$, Algorithm 4 inserts $R[c].pos=(n-\mathrm{SA}[i]+2)$ in
$\mathcal{S^{\prime}}$ (line 4, Algorithm 3). Otherwise, let $i<k^{\prime}$ be
the position of the next occurrence of $c$ in the $\mathrm{BWT}$, such that
$k^{\prime}\in\\{k-1,k\\}$. Due to
$\max\mathrm{LCP}[B_{i,c}]=\mathrm{LCP}[i]$, it must hold
$\mathrm{LCP}[k]<\mathrm{LCP}[i]$ or $k\not\in box(i)$. Here either,
$\mathrm{BWT}[i-1,k^{\prime}]=xcc...ccy$ where $x\neq c$ and $y\neq c$; thus,
$\exists l\in\mathrm{LCP}[i+1,k^{\prime}]$ such that $l<R[c].len$, or
$\mathrm{LCP}[\mathrm{LF}[c]]-1<R[c].len$. Again, since $R[c].active=true$,
then Algorithm 4 insert $R[c].pos=(n-\mathrm{SA}[i]+2)$ in
$\mathcal{S^{\prime}}$ (line 4, Algorithm 3).

_(2)_ now let $(n-\mathrm{SA}[i^{\prime}]+2)\notin\mathcal{S}$, this means
that $\exists j\in B_{i,c}$ such that $\mathrm{LCP}[j]>\mathrm{LCP}[i]$ and
$j$ is a $c$-run break. We need to consider two cases: _(i)_ $j>i$ and _(ii)_
$j<i$. _(i)_ If $j>i$, $\forall l\in\mathrm{LCP}[i+1,j]$,
$l\geq\mathrm{LCP}[i]$, which implies
$\mathrm{LCP}[\mathrm{LF}[c]]-1\geq\mathrm{LCP}[i]$ for all $c$-run breaks in
$[i+1,j]$; thus, we never update $R[c]$ to the inactive state (lines 2-6,
Algorithm 3) until we scan position $j$. Here, we get
$\mathrm{LCP}[j]>R[c].len$ and update $R[c].pos=(n-\mathrm{SA}[j^{\prime}]+2)$
(lines 17-19), where $j^{\prime}\in\\{j-1,j\\}$ and
$\mathrm{BWT}[j^{\prime}]=c$. Due to this, $(n-\mathrm{SA}[i^{\prime}]+2)$ is
dropped and not inserted in $\mathcal{S^{\prime}}$. _(ii)_ If $j<i$, then
$\exists l\in[j+1,i]$ such that $\mathrm{LCP}[\mathrm{LF}[c]]-1<R[c].len$ or
$\mathrm{LCP}[l]<\mathrm{LCP}[i]$;thus, when we read $l$, $R[c]$ is updated to
the inactive state (line 6, Algorithm 3). However, since $\forall s\in
B_{i,c}\cap[j+1,i]$, $\mathrm{LCP}[s]<\mathrm{LCP}[j]$ it means that $R[c]$ is
never updated to the active state for any position in $[j+1,i]$ (we skip lines
17-19), so also in this case $(n-\mathrm{SA}[i^{\prime}]+2)$ is not inserted
in $\mathcal{S^{\prime}}$. ∎

##  Appendix 0.B Deferred material for Section 4

###  0.B.1 Details on the one-pass algorithm in compressed space

Our one-pass algorithm can run in compressed space by using PFP algorithm to
read the $\mathrm{BWT}$, $\mathrm{LCP}$ and $\mathrm{SA}$ vectors, in one pass
from the first to the last position. The only major adaptation we need
consists of modifying PFP to compute the dictionary and parse of
$T^{\text{rev}}$ instead of $T$. Assuming the scenario where we read $T$ from
a stream, we have two options: (1) reading the whole stream and inverting $T$
explicitly before running PFP, (2) or adapting the PFP algorithm to compute
the dictionary and parse of $T^{\text{rev}}$ even if reading $T$. While the
first option is not feasible for large inputs since it requires $O(n)$ space,
we depict how to implement _(2)_.

PFP uses a rolling hash function to identify a set of small substrings of
length $w$ called trigger strings, which are then used to identify the
phrases. In particular, it selects a trigger string $T[i,i+w]$ if its Karp-
Rabin fingerprint $F(T[i,i+w])=\sum_{j=1}^{w}(T[i+j-1]\cdot\sigma^{w-j})\mod
q$ is congruent 0 modulo a parameter $p$. The key idea consists of inverting
the way we compute and update the fingerprints to identify the trigger strings
of $T^{\text{rev}}$ while reading $T$. In particular, we define a new hash
function $F^{\prime}(T[i,i+w])=\sum_{j=1}^{w}(T[i+j-1]\cdot\sigma^{j-1})\mod
q$, and given a new character $T[i+w+1]$, we update the fingerprint with the
following operations on $F^{\prime}(T[i,i+w])$: subtract
$T[i]\cdot\sigma^{0}$, divide by $\sigma$, and finally sum
$T[i+w+1]\cdot\sigma^{w-1}$.

##  Appendix 0.C Deferred material for Section 5

###  0.C.1 Details on the experimental setup

We ran all experiments in Section 5 on a workstation with Intel(R) Xeon(R)
W-2245 CPU @ 3.90GHz with 8 cores and 128 gigabytes of RAM running Ubuntu
18.04 LTS 64-bit. We recorded the runtime and memory usage of our software
using the wall clock time and maximum resident set size from /usr/bin/time.

As for the experiments on our one-pass algorithm working in compressed space,
since we did not yet implement the changes needed to compute the dictionary
and parse of $T^{\text{rev}}$ (see Section 0.B.1), we inverted the input texts
$T$ explicitly before running $\mathrm{PFP}$. We employed the PFP
implementation provided in the pscan.cpp file contained in Big-BWT
(https://github.com/alshai/Big-BWT) and ran it using 16 threads. Last, since
there are no competitors, we ran our software on two large biological datasets
to show it is practical in a real scenario.