# Quantum Chromodynamics Resolution of the ATOMKI Anomaly in ${\rm{{}^{4}He}}$
Nuclear Transitions

Valery Kubarovsky  Thomas Jefferson National Accelerator Laboratory, Newport
News, VA 23606, USA  Jennifer Rittenhouse West  Lawrence Berkeley National
Laboratory, Berkeley, CA 94720, USA  EIC Center at Thomas Jefferson National
Accelerator Laboratory, Newport News, VA 23606, USA  Stanley J. Brodsky  SLAC
National Accelerator Laboratory, Stanford University, Stanford, CA 94309, USA

###### Abstract

Observations of anomalous angular correlations in electron-positron pairs
produced from excited states of 4He, 8Be and 12C nuclei have been suggested as
due to the creation and subsequent decay of a new light particle of mass
$\sim$17 MeV. In this work, we investigate the possibility that the source of
the observed signals is a set of new excitation channels created by the
12-quark hidden-color Fock state within the ${\rm{{}^{4}He}}$ nuclear
wavefunction dubbed the “hexadiquark.” We calculate the invariant $e^{+}e^{-}$
mass spectrum for the electromagnetic transition from a new excitation of 4He,
estimating its differential and total decay width. We find that we can fit the
shape of the anomalous signal with the QCD Fock state at excitation energy
$\rm E^{*}=17.9\pm 1$ MeV and a Gaussian form factor for the electromagnetic
decay. We address the physical issues with the fit parameters using properties
of the hexadiquark state, in particular the three weakly repulsive $\rm 6_{C}$
interactions of $\rm SU(3)_{C}$ between diquark pairs. Experimental tests of
our model are described in detail. In light of this work, we emphasize the
need for independent experimental confirmation or refutation of the ATOMKI
results as well as dedicated experiments to search for the proposed new
excitations of ${\rm{}^{4}He}$ and other $\alpha$-cluster nuclei.

††preprint: SLAC-PUB-17683

##  I Introduction

Observations by the ATOMKI collaboration of anomalous angular correlations in
electron-positron pairs produced in the nuclear decays
${\rm{}^{4}He}^{*}\to{\rm{}^{4}He}+e^{+}e^{-}$ [1, 2],
${\rm{}^{8}Be}^{*}\to{\rm{}^{8}Be}+e^{+}e^{-}$ [3] and
${\rm{}^{12}C}^{*}\to{\rm{}^{12}C}+e^{+}e^{-}$ [4] have been attributed to the
creation and subsequent decay of a new light particle of mass of $\sim 17$
MeV, dubbed the X17. The same group has reported observations of the lepton
pair in the off-resonance region of $\rm{{}^{7}Li}(p,e^{+}e^{-}){{}^{8}Be}$
direct proton-capture reactions [5]. The signals have generated a great deal
of theoretical interest in both the particle and nuclear physics communities
[6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29]. In this work, we focus on the $\rm{}^{4}He$ experiment in
which the observed invariant mass $m_{e^{+}e^{-}}$ of the lepton pair was
found to be $m_{\mathrm{X}}=16.94\pm 0.12(\text{stat.})\pm 0.21\text{ (syst.)
}\mathrm{MeV}$. We show that excitation and decay of the recently proposed QCD
hidden-color Fock state within the ${}^{4}\rm He$ nuclear wavefunction [30]
provides a viable and compelling explanation of the ATOMKI phenomenon as well
as a clear set of experimental predictions. The model acts in all A$\geq$4
nuclei and explains why the X17 signal has only been observed in
$\alpha$-nuclei.

The light-front Fock state expansion of QCD has led to new perspectives for
the nonperturbative eigenstructure of hadrons. The $[ud]$ scalar diquark in
the $\bar{3}_{C}$ representation of $\rm SU(3)_{C}$, for example, is a
configuration that appears to play a fundamental role in hadron spectroscopy
such as the $|u[ud]\rangle$ Fock state in the proton wavefunction and baryonic
Regge trajectories [31, 32]. Tetraquarks are very likely bound states of
diquarks and anti-diquarks [33, 34, 35, 36]. Quark-antiquark, quark-diquark,
and diquark-antidiquark bound states all have an identical $3_{C}-\bar{3}_{C}$
color-confining interaction and therefore matching spectroscopy in QCD [37].

The 12-quark (6-diquark) hidden-color state $|[ud][ud][ud][ud][ud][ud]\rangle$
dubbed the “hexadiquark” is a novel color-singlet of QCD [30]. Such hidden-
color states are predictions of the $\rm SU(3)_{C}$ group theory basis of QCD
and have been studied for over four decades [38, 39, 40, 41, 42, 43]. In
general, a hadronic or nuclear eigenstate of the QCD Hamiltonian is a sum over
all color-singlet Fock states which match its quantum numbers. This has a
special impact for the ${}^{4}\rm He$ nucleus, since the hexadiquark Fock
state is an unusually low mass state with the same quantum numbers as the
nuclear Fock state $|nnpp\rangle$. Nuclear wavefunctions are typically
dominated by the neutron and proton Fock state, i.e., the multiple (A) 3-quark
color-singlet Fock state. In the ${}^{4}\rm He$ nuclear wavefunction, this is
the $|nnpp\rangle$ state containing A=4 color singlets (2 protons and 2
neutrons). In addition to this state, every 12-quark combination with the same
quantum numbers of ${}^{4}\rm He$ is also in the wavefunction - including the
single color-singlet hexadiquark. The hexadiquark is a special hidden-color
state because it is an unusually low mass combination of quarks - all spin-0,
isospin-0 and S-wave combinations - that obeys the spin-statistics theorem at
every stage of the build. This means it has the opportunity to have a larger
effect on nuclear physics than is typical. The six scalar diquarks within the
hexadiquark hidden-color state have predicted experimental signatures in
diffractive dissociation of ${}^{4}\rm He$ nuclei, as recently published [44].

QCD also predicts orbital and radial excitations between the $[ud]$ diquark
components of the hexadiquark and therefore new excitations of $\rm{}^{4}He$
beyond the standard excitations predicted by nucleonic degrees of freedom. The
excitation energy of the hexadiquark can be below the energy required to
produce nuclear decays such as $\rm{}^{4}He\rightarrow p+\rm^{3}H$ and have
evaded detection thus far while containing new experimental predictions as
will be demonstrated. The first hints of an excited state of 4He were
discovered over 80 years ago [45, 46] and the question of how a new
subdominant excited state could have been missed must be addressed. Hidden-
color states cannot decay through conventional nuclear channels as all of the
constituents have color charge (specifically quarks, diquarks and duo-
diquarks). The weakly repulsive QCD bonds between diquarks, utilizing the
symmetric sextet $\rm 6_{C}$ channel of $\rm SU(3)_{C}$, allow for low
(nuclear) energy excitations and require dedicated searches for their
signatures. An exhaustive list of QCD decay channels and experimental
signatures is presented in Section IV.

##  II Fitting the nuclear decay amplitude for
${\rm{}^{4}He}^{*}\rightarrow{\rm{}^{4}He}+e^{+}e^{-}$

The signal template we use to match the ATOMKI $e^{+}e^{-}$ angular
correlation is a narrow Gaussian peak in the electron-positron invariant mass
with a mean value $\sim 17$ MeV and width $\sigma\sim 0.7$ MeV (see Figure 1)
based on unpublished work by the ATOMKI collaboration [2] and cross-checked
with the NA64 X17 invariant mass simulation [26]. We calculate the invariant
mass $m_{e^{+}e^{-}}$ spectrum in the electromagnetic transition of an excited
state of $\rm{}^{4}He$, ${\rm{}^{4}He}^{*}({\rm
E^{*})}\to{\rm{}^{4}He}+e^{+}e^{-}$, where $\rm E^{*}$ is the excited state
energy. The mass difference between the first known excited state and the
ground state of the helium nucleus is $20.21$ MeV [47] and $\rm E^{*}$ is
initially fixed to this value. Its decay to the $\rm{}^{4}He$ ground state via
a virtual photon cannot explain the narrow width of the observed X17 signal.
The value of $\rm E^{*}$ is subsequently allowed to float to a different value
corresponding to the proposed excitation of the 12-quark color-singlet
hexadiquark Fock state in the $\rm{}^{4}He$ nuclear wavefunction [30].

Figure 1: Fit to the ATOMKI data (in red) by a Gaussian function and
background distribution (in black) of the $m_{e^{+}e^{-}}$ invariant mass
distribution based on [2] and cross-checked with [26]. The mean value of the
fitted mass is $\sim 17$ MeV with width $\sigma\sim 0.7$ MeV. The signal alone
is shown in blue.

The invariant mass distribution of the lepton pair $m_{e^{+}e^{-}}$ from the
decay of excited states of $\rm{}^{4}He$ has not been calculated until now.
The result of our calculation shows that decay due to an excitation of the
hexadiquark Fock state in the eigensolution of $\rm{}^{4}He$ can describe the
signal and its narrow width; in fact, this signal is to be expected from the
existence of the new hidden-color QCD state.

We begin with the square of the amplitude for the electromagnetic decay
${\rm{}^{4}He^{*}}\to{\rm{}^{4}He}+e^{+}e^{-}$, given by [15]

$\left|\mathcal{M}\right|^{2}=\sum_{\text{spin}}\left|{M}\right|^{2}=\frac{e^{4}\,C_{\text{E0}}^{2}}{\Lambda^{4}}\left[2(p_{+}\cdot
p_{0})(p_{-}\cdot p_{0})-m_{0}^{2}(p_{+}\cdot
p_{-})-m_{e}^{2}m_{0}^{2}\right],$ (1)

where $p_{+}$ and $p_{-}$ are the 4-momenta of the positron and electron
respectively, $p_{0}$ and $m_{0}$ are the 4-momentum and mass of the ground
state of $\rm{}^{4}He$ and $m_{e}$ is the electron mass. Final state spins
have been summed over. The definitions of $\Lambda$ as the nuclear energy
scale and $C^{2}_{E0}$ as the Wilson coefficient of the decay operator are
contained in [15]. These constants are not relevant for the analysis carried
out in this work as they affect only the normalization which we match to the
signal.

The matrix element depends on only two kinematical variables, $q^{2}$ and
$\cos{\theta^{*}}$, where $q=p_{+}+p_{-}$ is the 4-momentum of the virtual
photon, $q^{2}=m^{2}_{e^{+}e^{-}}$ is the $e^{+}e^{-}$ invariant mass squared
and $\theta^{*}$ is the electron angle in the virtual photon center of mass
system. Rewriting Eq.1 in terms of these variables gives

$\begin{split}\left|\mathcal{M}(q^{2},\cos{\theta^{*}})\right|^{2}=\frac{\alpha^{2}C^{2}_{E0}}{\Lambda^{4}}\frac{(4\pi)^{2}}{8q^{2}}\left[q^{2}-\cos^{2}{\theta^{*}}(q^{2}-4m_{e}^{2})\right]\left[m^{4}+(m^{2}_{0}-q^{2})^{2}-2m(m_{0}^{2}+q^{2})\right]\end{split}$
(2)

where $m$ is the mass of the excited ${\rm{}^{4}He^{*}}$ state.

The differential width $d\Gamma$ for the three body decay is given by

$\begin{split}d\Gamma=\frac{1}{(2\pi)^{5}}\frac{1}{16m^{2}}\left|\mathcal{M}\right|^{2}|p_{e}^{*}||p_{0}|dm_{e^{+}e^{-}}d\Omega^{*}_{e}d\Omega_{0}\end{split}$
(3)

where $d\Omega=d\phi~{}d\cos{\theta}$,
$(\left|p^{*}_{e}\right|,\Omega^{*}_{e})$ is the electron momentum in the
center of mass of the electron-positron pair,
$(\left|p_{0}\right|,\Omega_{0})$ is the ${\rm{}^{4}He}$ momentum in the rest
frame of the ${\rm{}^{4}He}^{*}.$ The minimum value of the $m_{e^{+}e^{-}}$
invariant mass is $2m_{e}$ and maximum value is determined by the mass
difference between the excited and ground ${\rm{}^{4}He}$ states, $\Delta
m=$20.21 MeV.

The integration of the matrix element
$\left|\mathcal{M}(q^{2},\cos{\theta^{*}})\right|^{2}$ over angles
$d\Omega^{*}_{e}\Omega_{0}$ gives

$\left|\mathcal{M}_{q}(q^{2})\right|^{2}=\int\left|\mathcal{M}(q^{2},\cos{\theta^{*}})\right|^{2}d\Omega^{*}_{e}d\Omega_{0}=\frac{\alpha^{2}C^{2}_{E0}}{\Lambda^{4}}\frac{(4\pi)^{4}}{12q^{2}}(q^{2}+2m^{2}_{e})\left[m^{4}+(m_{0}^{2}-q^{2})^{2}-2m^{2}(m_{0}^{2}+q^{2})\right].$
(4)

The matrix element $\left|\mathcal{M}_{q}(q^{2})\right|^{2}$ simplifies in the
limit $m_{e}=0$, to

$\begin{split}\left|\mathcal{M}_{q}(q^{2})\right|^{2}=\frac{\alpha^{2}C^{2}_{E0}}{\Lambda^{4}}\frac{(4\pi)^{4}}{12}\left[m^{4}+(m_{0}^{2}-q^{2})^{2}-2m^{2}(m_{0}^{2}+q^{2})\right].\end{split}$
(5)

There is only one variable left, the invariant electron-positron mass
$m_{e^{+}e^{-}}=\sqrt{q^{2}}=\sqrt{(p_{+}+p_{-})^{2}}$, and we find

$\begin{split}d\Gamma=\frac{1}{(2\pi)^{5}}\frac{1}{16m^{2}}\left|\mathcal{M}_{q}\right|^{2}|p_{e}^{*}||p_{0}|dm_{e^{+}e^{-}}.\end{split}$
(6)

The numerical integration over the three-body phase space is

$\Gamma_{E0}=\int_{2m_{e}}^{m-m_{0}}dm_{e^{+}e^{-}}\left|\mathcal{M}_{q}(q^{2})\right|^{2}|p_{e}^{*}||p_{He}|=\frac{\alpha^{2}C^{2}_{E0}}{\Lambda^{4}}~{}\frac{\Delta
m^{5}}{60\pi}0.982,$ (7)

which coincides with the approximate solution (Eq. 9, below) to an accuracy of
$2\%$.

In the approximation $q^{2}/m^{2}<\Delta m^{2}/m^{2}=3\cdot 10^{-5}\ll 1$ and
negligible electron mass, the differential width $d\Gamma/dm_{e^{+}e^{-}}$ is

$\begin{split}\frac{d\Gamma}{dm_{e^{+}e^{-}}}=\frac{\alpha^{2}C^{2}_{E0}}{12\pi\Lambda^{4}}~{}~{}m_{e^{+}e^{-}}\left(\Delta
m^{2}-m^{2}_{e^{+}e^{-}}\right)^{\frac{3}{2}}\end{split}.$ (8)

The full width has an analytic solution in this case,

$\begin{split}\Gamma_{E0}&=\frac{\alpha^{2}C^{2}_{E0}}{12\pi\Lambda^{4}}~{}\int_{2m_{e}}^{m-m_{0}}m_{e^{+}e^{-}}\left(\Delta
m^{2}-m^{2}_{e^{+}e^{-}}\right)^{\frac{3}{2}}dm_{e^{+}e^{-}}\\\
&=\frac{\alpha^{2}C^{2}_{E0}}{\Lambda^{4}}~{}\frac{\left(\Delta
m^{2}-4m_{e}^{2}\right)^{\frac{5}{2}}}{60\pi}\approx\frac{\alpha^{2}C^{2}_{E0}}{\Lambda^{4}}\frac{\Delta
m^{5}}{60\pi}\end{split}$ (9)

that with 2% accuracy corresponds to the exact solution of Eq. 7.

The differential width $d\Gamma/dm_{e^{+}e^{-}}$ from Eq. 2, integrated over
$\cos{\theta^{*}}$ and normalized to one (shown as the blue curve on the left
panel of Figure 2) is very smooth from the minimum value of
$m_{e^{+}e^{-}}=2m_{e}$ up to the maximum of $\Delta m=$20.21 MeV. The ATOMKI
signal cannot arise from the straightforward analysis carried out in this
section.

##  III Electromagnetic transition form factors $F(q^{2})$ in the nuclear
decay ${\rm{}^{4}He}^{*}\to{\rm{}^{4}He}+e^{+}e^{-}$

The analysis carried out in the previous section implicitly assumed a form
factor $F(q^{2})$ equal to unity. A more realistic form factor significantly
changes the $m_{e^{+}e^{-}}$ invariant mass distribution in the nuclear decay
${\rm{}^{4}He}^{*}\to{\rm{}^{4}He}+e^{+}e^{-}$

$\begin{split}\frac{d\Gamma}{dm_{e^{+}e^{-}}}=\frac{\alpha^{2}C^{2}_{E0}}{12\pi\Lambda^{4}}~{}~{}m_{e^{+}e^{-}}\left(\Delta
m^{2}-m^{2}_{e^{+}e^{-}}\right)^{\frac{3}{2}}|F(q^{2})|^{2}\end{split}.$ (10)

We show the best fit form factor and its failure to describe the signal in
this section, as well as the successful fit for a new excitation energy near
$18$ MeV.

The experimental $m_{e^{+}e^{-}}$ distribution is not given in the ATOMKI
work. In order to compare the theoretical analysis in this section to the
signal, we first extract the ATOMKI data from [2], graph them and confirm that
we can replicate their plot. We then use this as a template to fit our signal,
noting that it is based on the unpublished ATOMKI work [2] and cross-checked
with the invariant mass plot in the NA64 Collaboration X17 simulations [26].
In the next step, we use the extracted signal and background distributions
from the template and make a fit with two functions to describe both
distributions. Figure 1 presents our fit of ATOMKI data (shown in red). The
background (shown in black) was fitted independently because the experiment
measured the background distribution with much higher accuracy than the
signal. We used a third-degree polynomial to fit the background. The fit
result is $f_{\rm bg}(x)=1584-306x+20x^{2}-0.434x^{3}$ (where
$x=m_{e^{+}e^{-}}$) with $\chi^{2}/ndf=0.99$. The same function was used in
all fits in Figure 1, Figure 2 and Figure 3. The signal in Figure 1 was
described by a Gaussian function with 3 parameters: the mass value of the peak
position ($16.8\pm 0.23~{}\rm MeV$), the width ($\sigma=0.70\pm 0.17~{}\rm
MeV$) and overall normalization. This fit is very close to the signal
template. We now begin to model the results theoretically.

Several realistic form factor models are tested in our attempt to model the
data template. We compare the shape of the differential width
$d\Gamma/dm_{e^{+}e^{-}}$ for the electromagnetic transition with form factor
$F(q^{2})\propto\exp{(q^{2}/\lambda^{2})}$ with $\lambda=14.5$ MeV (see Eq.
10) with a maximum near $17$ MeV and ATOMKI anomaly shown on the left panel of
Figure 2 and including $F(q^{2})=1$ for comparison. We find the width of the
distribution to be too large to obtain a satisfactory description of the
experimental distribution. The signal template is too narrow in comparison
with the theoretical curve as shown in Figure 2, comparing the red curve
(theoretical curve) and black curve (signal template). On the right panel of
Figure2 we present the attempt to fit the signal template, again with
electromagnetic transition form factors
$F(q^{2})\propto\exp{(q^{2}/\lambda^{2})}$. The background function is the
same as in Figure 1. This fit has only two parameters, $\lambda$ and the
normalization of the theoretical function Eq. 10. The fit is not satisfactory.
A form factor of $F(q^{2})\propto q^{2}$ also failed to describe the signal
due to its large width.

Figure 2: Left panel: Differential width $d\Gamma/dm_{e^{+}e^{-}}$ (in
arbitrary units) for the transition
${\rm{}^{4}He^{*}(20.21)}\to{\rm{}^{4}He}+e^{+}e^{-}$ as a function of the
electron-positron invariant mass $m_{e^{+}e^{-}}$. Blue curve has form factor
$F(q^{2})=1$ (see Eq. 10). The black curve is the Gaussian distribution of the
ATOMKI anomaly with $m=$17 MeV and $\sigma=$0.7 MeV. Red curve has form factor
$F(q^{2})\propto\exp{(q^{2}/\lambda^{2})}$ with $\lambda=14.5$ MeV. With this
value of the $\lambda$ parameter, the distribution maximum is at $m=$17 MeV.
The functions are normalized such that the peak values are the same for all
curves. Neither curve fits the signal. Right panel: Fit to signal template
(event counts vs. invariant mass distribution) for the transition
${\rm{}^{4}He^{*}}(20.21)\to{\rm{}^{4}He}+e^{+}e^{-}$. The fit is an
electromagnetic transition with form factor
$F(q^{2})\propto\exp{(q^{2}/\lambda^{2})}$ (in red). The background
distribution is shown in black, the signal alone is shown in blue. The fit is
not satisfactory.

We now introduce a new parameter, the mass of a new excited $\rm{}^{4}He^{*}$
state, into our model. We motivate this state physically by the 12-quark color
singlet Fock state model of $\rm{}^{4}He$ nucleus in which the $\rm{}^{4}He$
wavefunction is dominated by a linear combination of $|nnpp\rangle$ and the
12-quark hexadiquark QCD state [30]. The result of the fit with form factor
$F(q^{2})\propto\exp{(q^{2}/\lambda^{2})}$ is presented in Figure 3. There are
three parameters of the fit, the excitation energy of the new
$\rm{{}^{4}He^{*}}$ state $\rm E^{*}=17.9\pm 1$ MeV ($=\Delta m$ in Eq. 10),
the form factor parameter $\lambda=6.2\pm 0.5$ MeV and the overall
normalization. The model describes the data template very well. Our parameter
$\lambda$ is close to the momentum scale found in earlier work on nuclear
transitions [16].

We have reproduced the ATOMKI signal with the introduction of a new excitation
of $\rm{}^{4}He$ but there are serious physical issues that must be addressed.
First, the energy of the electron-positron pair in this case has to be close
to $17.9~{}\rm MeV$. This is at the lower limit of the selection of the
positrons and electrons with total energy in the region ($18,22$) MeV and
$2.6\sigma$ from the central excitation energy $20.49~{}\rm MeV$ created by
the $900~{}\rm keV$ proton beam. There are no error bars given by ATOMKI but a
reasonable visual estimate is $0.9~{}\rm MeV$ which would reduce our $\sigma$
values. These are not prohibitively large deviations and we do not discuss
them further but they must be noted. More importantly, this is an excitation
energy that has never been observed in a decay to a conventional hadronic or
nuclear final state. In addition, the form factor parameter $\lambda$ is an
order of magnitude smaller than expected for a typical nuclear transition. We
address both of the latter points in the following section.

Figure 3: Fit to signal template (event counts vs. invariant mass
distribution) for the electromagnetic transition
$\rm{HdQ^{*}}(17.9)\to{\rm{}^{4}He}+(e^{+}e^{-})$. The fit assumes a form
factor $F(q^{2})\propto\exp{(q^{2}/\lambda^{2})}$ with the form factor
parameter $\lambda$ = 6.2 MeV (in red). The background distribution is shown
in black, and the signal alone is shown in blue (see Eq. 10 with $\Delta
m=17.9$ MeV).

##  IV QCD Hexadiquark excitations

The hexadiquark (HdQ) is a hidden-color QCD state [38, 39, 40, 41, 42, 43] in
the $\rm{}^{4}He$ nuclear wavefunction consisting of six scalar $[ud]$
diquarks [48, 49] in a color singlet configuration [30]. Excitation of a
subset of diquarks, either radial or angular momentum excitations, gives rise
to nuclear transitions with unconventional decays. In conventional nuclear
physics, for example, the electron scattering experiment $e+{\rm{{}^{4}He}}\to
e^{\prime}+X$ will produce hadronic excitations of $\rm{}^{4}He$. In contrast,
if an electron (or proton) scatters on the hexadiquark Fock state of
$\rm{}^{4}He$, it can produce orbital or radial excitations between any two of
the [ud] diquarks. Typically such excitations would be at energies near
$300~{}\rm MeV$ above the ground state, in analogy to the $N^{*}$ and $\Delta$
excited states of nucleons. Excitations of single diquarks from spin-0
isospin-0 to spin-1 isospin-1 states have energies of approximately $200~{}\rm
MeV$ [49, 48].

However, the HdQ is an unusual QCD eigenstate because, in addition to being a
low mass spin-0 isospin-0 S-wave hidden-color state, the wavefunction contains
three symmetric and repulsive
$\bar{3}_{C}\times\bar{3}_{C}\rightarrow\bar{6}_{C}$ interactions. These
interactions are required by the spin-statistics constraints upon clustering
pairs of $[ud]$ diquarks into each of the three $[ud][ud]$ duo-diquarks
contained within the 12-quark color-singlet wavefunction. While the final
construction of the three duo-diquarks into the HdQ is strongly bound with
color factor $C_{F}=-5$, the QCD interaction between diquarks in a duo-diquark
is repulsive which significantly lowers the excitation energies of the HdQ and
increases the size of the HdQ.

There are two ways to excite the $\rm 6_{C}$ bond between diquarks: an orbital
angular momentum $\rm L=1$ excitation and an $\rm L=0$ radial excitation.
These are color-singlet excitations, they do not break the strongly bound HdQ
state apart, and therefore cannot decay to a conventional nuclear physics
state such as $p+{\rm{}^{3}H}$ or $n+{\rm{}^{3}He}$. However, since the $\rm
L=1$ excitation has $J^{P}=1^{-}$, the HdQ excitation can decay to the
$\rm{}^{4}He$ ground state by the emission of a virtual photon which makes an
$e^{+}e^{-}$ pair:
$\rm{{}^{4}He^{*}(17.9)\to{\rm{}^{4}He}}+\gamma^{*}\to{\rm{}^{4}He}+e^{+}e^{-}$.
This state can also emit a $17.9\pm 1~{}\rm MeV$ real photon. The $\rm L=0$
radial excitation between diquarks has $J^{P}=0^{+}$ and can only decay via
virtual photon which creates the $e^{+}e^{-}$ pair. Thus the three decay modes
of the HdQ predict an $e^{+}e^{-}$ pair of invariant mass $17.9\pm 1~{}\rm
MeV$ and/or a $17.9\pm 1~{}\rm MeV$ gamma ray photon.

In the case of an excitation of the 4He nucleus to a known excited state,
there are two additional decay modes with distinct signatures. In the first
scenario, the transition is described by the 2-stage process

${\rm
p+^{3}H}\rightarrow{\rm{}^{4}He^{*}}(20.21)~{}\mathrm{MeV}\rightarrow{\rm{}^{4}He^{*}}(17.9)~{}\mathrm{MeV}+\gamma(2.31\pm
1~{}\mathrm{MeV})\rightarrow{\rm{}^{4}He}+\left(e^{+}e^{-}\right)+\gamma(2.31\pm
1~{}\mathrm{MeV})$ (11)

for the first excited state of $\rm{}^{4}He$ at $20.21~{}\rm MeV$
($\Gamma=0.50~{}\mathrm{MeV}$). The second scenario occurs for the second
excited state of 4He at $21.01$ MeV $(\Gamma=0.84~{}\mathrm{MeV})$,

${\rm
p+^{3}H}\rightarrow{\rm{}^{4}He^{*}}(21.01)~{}\mathrm{MeV}\rightarrow{\rm{}^{4}He^{*}}(17.9)~{}\mathrm{MeV}+\gamma(3.11\pm
1~{}\mathrm{MeV})\rightarrow{\rm{}^{4}He}+\left(e^{+}e^{-}\right)+\gamma(3.11\pm
1~{}\mathrm{MeV})$ (12)

It is important to note that multiple processes can excite the HdQ state,
including direct proton capture in the initial $p+\rm^{3}H$ collision creating
$\gamma+{\rm HdQ^{*}}$ and then decaying down to $e^{+}e^{-}+{\rm{}^{4}He}$,
i.e.,

$p+{\rm{}^{3}H}\rightarrow\gamma+{\rm{}^{4}He^{*}}(17.9)\rightarrow{\rm{}^{4}He}+e^{+}e^{-}+\gamma.$
(13)

A low energy photon will also be present in the final state, however, the
signature of this decay is the $e^{+}e^{-}$ pair of invariant mass $17.9\pm
1~{}\rm MeV$. In addition to the decay signatures outlined above (summarized
in Tables 1 and 2), a key method for confirmation of the hexadiquark solution
to the ATOMKI puzzle is an investigation of the first excited state of 4He to
identify a secondary “shoulder” peak within the range of $17.9\pm 1~{}\rm
MeV$. Since the hexadiquark contains three sets of duo-diquarks, the $17.9\pm
1~{}\rm MeV$ excitation will be accompanied by excitations at $\sim 36$ MeV
and $\sim 54$ MeV. Larger $\alpha$-nuclei, including 8Be and 12C, will have
even higher multiples of the $17.9\pm 1~{}\rm MeV$ excitation for each
additional hexadiquark state within the nuclear wavefunction.

We propose that the HdQ is the origin of a previously missed subdominant
$\rm{}^{4}He^{*}(17.9)$ excited state. It can be observed in the interaction
$e+{\rm{{}^{4}He}}\to e^{\prime}+{\rm{{}^{4}He^{*}}}(17.9)\to
e^{\prime}+{\rm{{}^{4}He}}+[e^{+}e^{-}]$. The characteristic mass scale of the
transition form factor $F(q^{2})$ producing the timelike lepton pair in the
$\rm HdQ^{*}\to HdQ+\gamma^{*}$ process can be significantly lighter than the
standard QCD mass scale because it reflects the large size structure of the
HdQ due to the repulsive interactions within each of the three duo-diquarks.
This can cause a $\lambda$ parameter of order $10$ MeV in the transition $\rm
HdQ^{*}\to HdQ$ form factor as required by our fit. The conclusion from these
arguments is that an excitation of the HdQ Fock state of $\rm{}^{4}He$ can
account for the excellent fit and parameters in Figure 3 to the ATOMKI signal
template.

We note that the hexadiquark state is predicted to exist as a hidden-color QCD
Fock state within every nucleus containing an alpha particle. Each such
nucleus will also have HdQ hidden color excitations; the resulting $\rm
HdQ^{*}$ decays should therefore also be observed in lepton pair decays from
excitations of $\rm{}^{8}Be$ and $\rm{}^{12}C$. All nuclei containing at least
one $\alpha$-particle will have this excitation and the strength of the signal
is predicted to increase with each additional $\alpha$-particle. HdQ
transitions cannot occur in $A=3$ nuclei, in deuterium, or in nucleons (all of
which contain less than 12 quarks) and therefore will not be observed in
experiments that use these targets. However, other hidden-color Fock states in
$A<4$ nuclei that use the repulsive $6_{C}$ representation of $\rm SU(3)_{C}$
also allow for new lower energy excitations with unconventional decays.

There are important complementary tests for the hexadiquark solution. The HdQ
component of $\rm{}^{4}He$ should be observed as a peak in the missing mass in
$e+{\rm{{}^{4}He}}\to e^{\prime}+X$. The diquark composition of the
${\rm{{}^{4}He}}$ nucleus may be observed via $e+{\rm{{}^{4}He}}\to
e^{\prime}+[ud]+X$ where the $[ud]$-diquark jet [50] is produced opposite to
the scattered electron.

New Hexadiquark excitation ${}^{4}\rm He^{*}(17.9\pm 1)$ | Decay from ${}^{4}\rm He^{*}(17.9\pm 1)\rightarrow$ | Experimental signature
---|---|---
L=0 radial excitations $[ud]\leftrightarrow[ud]$ |  4He $+\gamma^{*}$ $\rightarrow$ 4He + $e^{+}e^{-}$ | $e^{+}e^{-}(17.9\pm 1)$
L=1 orbital excitations $[ud]\circlearrowright[ud]$ |  4He + $\gamma$ | $\gamma(17.9\pm 1)$
|  4He + $\gamma\rightarrow$ 4He + $e^{+}e^{-}$ | $e^{+}e^{-}(17.9\pm 1)$
Table 1: Experimental signatures for direct excitations of the QCD hexadiquark Fock state in units of MeV. Each hexadiquark contains 3 diquark-diquark correlations and therefore subdominant nuclear excitations near 36 MeV and 54 MeV are predicted in 4He. 8Be, 12C and all higher A $\alpha$-cluster nuclei will have additional excitations at multiples of $17.9\pm 1$ MeV, exactly 3 additional excitations per $\alpha$.  Excitation energy of ${}^{4}\rm He$ | Decay channel ${}^{4}\rm He^{*}(E^{*})\rightarrow$ | Experimental signature
---|---|---
${}^{4}\rm He^{*}(20.21)$ |  ${\rm{}^{4}He}^{*}(17.9\pm 1)$\+ $\gamma(2.31\pm 1)$ $\rightarrow{\rm{}^{4}He}+\gamma(2.31\pm 1)+e^{+}e^{-}$ |  $e^{+}e^{-}(17.9\pm 1)$, $\gamma(2.31\pm 1)$
| ${\rm{}^{4}He}^{*}(17.9\pm 1)+\gamma(2.31\pm 1)\rightarrow{\rm{}^{4}He}+\gamma(17.9\pm 1)$ |  $\gamma(17.9\pm 1)$, $\gamma(2.31\pm 1)$
${}^{4}\rm He^{*}(21.01)$ |  ${\rm{}^{4}He}^{*}(17.9\pm 1)$\+ $\gamma(3.11\pm 1)$ $\rightarrow{\rm{}^{4}He}+\gamma(3.11\pm 1)+e^{+}e^{-}$ |  $e^{+}e^{-}(17.9\pm 1)$, $\gamma(3.11\pm 1)$
|  ${\rm{}^{4}He}^{*}(17.9\pm 1)$\+ $\gamma(3.11\pm 1)$ $\rightarrow{\rm{}^{4}He}+\gamma(3.11\pm 1)+\gamma(17.9\pm 1)$ |  $\gamma(17.9\pm 1)$, $\gamma(3.11)$
Table 2: Experimental signatures for 2-stage excitations in which excitation
of a known ${\rm{}^{4}He}$ excited state is followed by a decay to the
proposed new hexadiquark excitation, ${}^{4}\rm He^{*}\rightarrow{\rm
He^{*}(17.9)}\rightarrow X$, in units of MeV.

##  V Summary

We have presented a QCD-based solution to the ATOMKI anomalies that utilizes
the predicted hexadiquark hidden-color Fock state in the $\rm{}^{4}He$ nuclear
wavefunction [30]. The hexadiquark state mixes with the conventional
$|nnpp\rangle$ nuclear physics state of $\rm{}^{4}He$ and offers a hidden-
color explanation of its anomalously large binding energy. Our calculation of
the $m_{e^{+}e^{-}}$ invariant mass spectrum in the electromagnetic transition
${\rm{}^{4}He}^{*}({\rm E^{*}})\to{\rm{}^{4}He}+e^{+}e^{-}$ as well as the
observed differential and total width of the decay are fit to an
electromagnetic decay of a new excitation of $\rm{}^{4}He$ of energy $\rm
E^{*}=17.9\pm 1~{}\rm MeV$ above the ground state. The cause of
$\rm{}^{4}He^{*}(17.9)$ is proposed to be low energy diquark-diquark pair
excitations within the hidden-color hexadiquark component of the nuclear
wavefunction, enabled by the novel spin-statistics mandated use of weakly
repulsive $\rm 6_{C}$ interactions of $\rm SU(3)_{C}$ between diquark pairs.

We have shown that it is possible to reproduce the ATOMKI signal with ${\rm
J^{P}}=0^{+}$ and ${\rm J^{P}}=1^{-}$ excitations between the diquark
constituents of the hexadiquark Fock state. In one production scenario, the
proton $+$ tritium collision first produces the conventional first nuclear
excited state $\rm{}^{4}He^{*}$ which decays by photon emission to an
excitation of the QCD Fock state. The hexadiquark excitation may be produced
by direct proton capture as well. All experimental signatures and decay
channels are summarized in Tables 1 and 2.

This work is both timely and important due to the negative searches for the
new X17 boson carried out thus far [51, 52, 26] and planned searches at
Jefferson Lab [29], in Italy with the Positron Annihilation to Dark Matter
Experiment (PADME [53, 54]) and elsewhere. Our QCD-based solution of the
ATOMKI results, which must occur in all $A\geq 4$ nuclei including the
${}^{4}\rm He$, ${}^{8}\rm Be$, ${}^{12}\rm C$ nuclei in the ATOMKI
experiments, is in contrast to the new particle explanation.

## Acknowledgements

J.R.W. acknowledges support by the LDRD program of LBNL, the EIC Center at
Jefferson Lab and the U.S. Department of Energy, Office of Science, Office of
Nuclear Physics, under contract number DE-AC02-05CH11231. V.K. acknowledges
support by the U.S. Department of Energy, Office of Science, and Office of
Nuclear Physics under contracts DE-AC05-06OR23177. JLAB-PHY-22-3641. The work
of S.J.B. was supported in part by the Department of Energy under Contract No.
DE-AC02- 76SF00515. SLAC-PUB-17683.

## References

  * Krasznahorkay et al. [2021] A. J. Krasznahorkay, M. Csatlós, L. Csige, J. Gulyás, A. Krasznahorkay, B. M. Nyakó, I. Rajta, J. Timár, I. Vajda, N. J. Sas,  New anomaly observed in He4 supports the existence of the hypothetical X17 particle,  Phys. Rev. C 104 (2021) 044003. doi:10.1103/PhysRevC.104.044003. arXiv:2104.10075.
  * Krasznahorkay et al. [2019] A. J. Krasznahorkay, et al.,  New evidence supporting the existence of the hypothetic X17 particle (2019). arXiv:1910.10459.
  * Krasznahorkay et al. [2016] A. J. Krasznahorkay, et al.,  Observation of Anomalous Internal Pair Creation in Be8 : A Possible Indication of a Light, Neutral Boson,  Phys. Rev. Lett. 116 (2016) 042501. doi:10.1103/PhysRevLett.116.042501. arXiv:1504.01527.
  * Krasznahorkay et al. [2022] A. J. Krasznahorkay, et al.,  New anomaly observed in C12 supports the existence and the vector character of the hypothetical X17 boson,  Phys. Rev. C 106 (2022) L061601. doi:10.1103/PhysRevC.106.L061601. arXiv:2209.10795.
  * Sas et al. [2022] N. J. Sas, et al.,  Observation of the X17 anomaly in the 7Li($p$,$e^{+}e^{-}$)8Be direct proton-capture reaction (2022). arXiv:2205.07744.
  * Battaglieri et al. [2017] M. Battaglieri, et al.,  US Cosmic Visions: New Ideas in Dark Matter 2017: Community Report,  in: U.S. Cosmic Visions: New Ideas in Dark Matter, 2017. arXiv:1707.04591.
  * Backens and Vanderhaeghen [2022] J. Backens, M. Vanderhaeghen,  X17 Discovery Potential in the $\gamma$N→e+e-N Process at Electron Scattering Facilities,  Phys. Rev. Lett. 128 (2022) 091802. doi:10.1103/PhysRevLett.128.091802. arXiv:2110.06055.
  * Fornal [2017] B. Fornal,  Is There a Sign of New Physics in Beryllium Transitions?,  Int. J. Mod. Phys. A 32 (2017) 1730020. doi:10.1142/S0217751X17300204. arXiv:1707.09749.
  * Feng et al. [2017] J. L. Feng, B. Fornal, I. Galon, S. Gardner, J. Smolinsky, T. M. P. Tait, P. Tanedo,  Particle physics models for the 17 MeV anomaly in beryllium nuclear decays,  Phys. Rev. D 95 (2017) 035017. doi:10.1103/PhysRevD.95.035017. arXiv:1608.03591.
  * Viviani et al. [2022] M. Viviani, E. Filandri, L. Girlanda, C. Gustavino, A. Kievsky, L. E. Marcucci, R. Schiavilla,  X17 boson and the H3(p,e+e$-$)He4 and He3(n,e+e$-$)He4 processes: A theoretical analysis,  Phys. Rev. C 105 (2022) 014001. doi:10.1103/PhysRevC.105.014001. arXiv:2104.07808.
  * Agrawal et al. [2021] P. Agrawal, et al.,  Feebly-interacting particles: FIPs 2020 workshop report,  Eur. Phys. J. C 81 (2021) 1015. doi:10.1140/epjc/s10052-021-09703-7. arXiv:2102.12143.
  * Alexander et al. [2016] J. Alexander, et al.,  Dark Sectors 2016 Workshop: Community Report,  2016\. arXiv:1608.08632.
  * Kozaczuk et al. [2017] J. Kozaczuk, D. E. Morrissey, S. R. Stroberg,  Light axial vector bosons, nuclear transitions, and the 8Be anomaly,  Phys. Rev. D 95 (2017) 115024. doi:10.1103/PhysRevD.95.115024. arXiv:1612.01525.
  * Kitahara and Yamamoto [2017] T. Kitahara, Y. Yamamoto,  Protophobic Light Vector Boson as a Mediator to the Dark Sector,  Phys. Rev. D 95 (2017) 015008. doi:10.1103/PhysRevD.95.015008. arXiv:1609.01605.
  * Feng et al. [2020] J. L. Feng, T. M. P. Tait, C. B. Verhaaren,  Dynamical Evidence For a Fifth Force Explanation of the ATOMKI Nuclear Anomalies,  Phys. Rev. D 102 (2020) 036016. doi:10.1103/PhysRevD.102.036016. arXiv:2006.01151.
  * Zhang and Miller [2017] X. Zhang, G. A. Miller,  Can nuclear physics explain the anomaly observed in the internal pair production in the Beryllium-8 nucleus?,  Phys. Lett. B 773 (2017) 159–165. doi:10.1016/j.physletb.2017.08.013. arXiv:1703.04588.
  * Zhang and Miller [2021] X. Zhang, G. A. Miller,  Can a protophobic vector boson explain the ATOMKI anomaly?,  Phys. Lett. B 813 (2021) 136061. doi:10.1016/j.physletb.2021.136061. arXiv:2008.11288.
  * Frugiuele et al. [2017] C. Frugiuele, E. Fuchs, G. Perez, M. Schlaffer,  Constraining New Physics Models with Isotope Shift Spectroscopy,  Phys. Rev. D 96 (2017) 015011. doi:10.1103/PhysRevD.96.015011. arXiv:1602.04822.
  * Banerjee et al. [2018] D. Banerjee, et al. (NA64),  Search for a Hypothetical 16.7 MeV Gauge Boson and Dark Photons in the NA64 Experiment at CERN,  Phys. Rev. Lett. 120 (2018) 231802. doi:10.1103/PhysRevLett.120.231802. arXiv:1803.07748.
  * Castro and Quintero [2021] G. L. Castro, N. Quintero,  Tests of the Atomki anomaly in lepton pair decays of heavy mesons,  Phys. Rev. D 103 (2021) 093002. doi:10.1103/PhysRevD.103.093002. arXiv:2101.01865.
  * Dror et al. [2017] J. A. Dror, R. Lasenby, M. Pospelov,  New constraints on light vectors coupled to anomalous currents,  Phys. Rev. Lett. 119 (2017) 141803. doi:10.1103/PhysRevLett.119.141803. arXiv:1705.06726.
  * Alves and Weiner [2018] D. S. M. Alves, N. Weiner,  A viable QCD axion in the MeV mass range,  JHEP 07 (2018) 092\. doi:10.1007/JHEP07(2018)092. arXiv:1710.03764.
  * Ariga et al. [2019] A. Ariga, et al. (FASER),  FASER’s physics reach for long-lived particles,  Phys. Rev. D 99 (2019) 095011. doi:10.1103/PhysRevD.99.095011. arXiv:1811.12522.
  * Delle Rose et al. [2019] L. Delle Rose, S. Khalil, S. J. D. King, S. Moretti,  New Physics Suggested by Atomki Anomaly,  Front. in Phys. 7 (2019) 73. doi:10.3389/fphy.2019.00073. arXiv:1812.05497.
  * Hayes et al. [2022] A. C. Hayes, J. L. Friar, G. M. Hale, G. T. Garvey,  Angular correlations in the e+e$-$ decay of excited states in Be8,  Phys. Rev. C 105 (2022) 055502. doi:10.1103/PhysRevC.105.055502. arXiv:2106.06834.
  * Depero et al. [2020] E. Depero, et al. (NA64),  Hunting down the X17 boson at the CERN SPS,  Eur. Phys. J. C 80 (2020) 1159. doi:10.1140/epjc/s10052-020-08725-x. arXiv:2009.02756.
  * Seto and Shimomura [2017] O. Seto, T. Shimomura,  Atomki anomaly and dark matter in a radiative seesaw model with gauged $B-L$ symmetry,  Phys. Rev. D 95 (2017) 095032. doi:10.1103/PhysRevD.95.095032. arXiv:1610.08112.
  * Seto and Shimomura [2021] O. Seto, T. Shimomura,  Atomki anomaly in gauged U(1)R symmetric model,  JHEP 04 (2021) 025\. doi:10.1007/JHEP04(2021)025. arXiv:2006.05497.
  * Ahmidouch et al. [2021] A. Ahmidouch, et al.,  A Direct Detection Search for Hidden Sector New Particles in the 3-60 MeV Mass Range (2021). arXiv:2108.13276.
  * Rittenhouse West et al. [2021] J. Rittenhouse West, S. J. Brodsky, G. F. de Teramond, A. S. Goldhaber, I. Schmidt,  QCD hidden-color hexadiquark in the core of nuclei,  Nucl. Phys. A 1007 (2021) 122134. doi:10.1016/j.nuclphysa.2020.122134. arXiv:2004.14659.
  * Dosch et al. [2015] H. G. Dosch, G. F. de Teramond, S. J. Brodsky,  Superconformal Baryon-Meson Symmetry and Light-Front Holographic QCD,  Phys. Rev. D 91 (2015) 085016. doi:10.1103/PhysRevD.91.085016. arXiv:1501.00959.
  * de Teramond et al. [2015] G. F. de Teramond, H. G. Dosch, S. J. Brodsky,  Baryon Spectrum from Superconformal Quantum Mechanics and its Light-Front Holographic Embedding,  Phys. Rev. D 91 (2015) 045040. doi:10.1103/PhysRevD.91.045040. arXiv:1411.5243.
  * ’t Hooft et al. [2008] G. ’t Hooft, G. Isidori, L. Maiani, A. D. Polosa, V. Riquer,  A Theory of Scalar Mesons,  Phys. Lett. B 662 (2008) 424–430. doi:10.1016/j.physletb.2008.03.036. arXiv:0801.2288.
  * Masjuan and Ruiz Arriola [2017] P. Masjuan, E. Ruiz Arriola,  Regge trajectories of Excited Baryons, quark-diquark models and quark-hadron duality,  Phys. Rev. D 96 (2017) 054006. doi:10.1103/PhysRevD.96.054006. arXiv:1707.05650.
  * Anselmino et al. [1993] M. Anselmino, E. Predazzi, S. Ekelin, S. Fredriksson, D. B. Lichtenberg,  Diquarks,  Rev. Mod. Phys. 65 (1993) 1199–1234. doi:10.1103/RevModPhys.65.1199.
  * Nielsen and Brodsky [2018] M. Nielsen, S. J. Brodsky,  Hadronic superpartners from a superconformal and supersymmetric algebra,  Phys. Rev. D 97 (2018) 114001. doi:10.1103/PhysRevD.97.114001. arXiv:1802.09652.
  * Brodsky et al. [2015] S. J. Brodsky, G. F. de Teramond, H. G. Dosch, J. Erlich,  Light-Front Holographic QCD and Emerging Confinement,  Phys. Rept. 584 (2015) 1–105. doi:10.1016/j.physrep.2015.05.001. arXiv:1407.8131.
  * Brodsky and Chertok [1976] S. J. Brodsky, B. T. Chertok,  The Asymptotic Form-Factors of Hadrons and Nuclei and the Continuity of Particle and Nuclear Dynamics,  Phys. Rev. D 14 (1976) 3003–3020. doi:10.1103/PhysRevD.14.3003.
  * Harvey [1981] M. Harvey,  Effective nuclear forces in the quark model with Delta and hidden color channel coupling,  Nucl. Phys. A 352 (1981) 326–342. doi:10.1016/0375-9474(81)90413-9.
  * Brodsky et al. [1983] S. J. Brodsky, C.-R. Ji, G. P. Lepage,  Quantum Chromodynamic Predictions for the Deuteron Form-Factor,  Phys. Rev. Lett. 51 (1983) 83. doi:10.1103/PhysRevLett.51.83.
  * Harvey [1981] M. Harvey,  On the Fractional Parentage Expansions of Color Singlet Six Quark States in a Cluster Model,  Nucl. Phys. A 352 (1981) 301. doi:10.1016/0375-9474(81)90412-7, [Erratum: Nucl.Phys.A 481, 834 (1988)].
  * Bashkanov et al. [2013] M. Bashkanov, S. J. Brodsky, H. Clement,  Novel Six-Quark Hidden-Color Dibaryon States in QCD,  Phys. Lett. B 727 (2013) 438–442. doi:10.1016/j.physletb.2013.10.059. arXiv:1308.6404.
  * Miller [2014] G. A. Miller,  Pionic and Hidden-Color, Six-Quark Contributions to the Deuteron b1 Structure Function,  Phys. Rev. C 89 (2014) 045203. doi:10.1103/PhysRevC.89.045203. arXiv:1311.4561.
  * Rittenhouse West et al. [2020] J. Rittenhouse West, S. J. Brodsky, G. F. de Téramond, I. Schmidt,  Diffractive dissociation of alpha particles as a test of isophobic short-range correlations inside nuclei,  Phys. Lett. B 805 (2020) 135423. doi:10.1016/j.physletb.2020.135423. arXiv:1912.11288.
  * Jarmie and Allen [1959] N. Jarmie, R. C. Allen,  T (p, p) T Scattering near the T (p, n) He-3 Threshold,  Phys. Rev. 114 (1959) 176–178. doi:10.1103/PhysRev.114.176.
  * Jarmie et al. [1963] N. Jarmie, M. G. Silbert, D. B. Smith, J. S. Loos,  Proton-Triton Elastic Scattering below 1 MeV,  Phys. Rev. 130 (1963) 1987–1989. doi:10.1103/PhysRev.130.1987.
  * Walcher [1970] T. Walcher,  Excitation of 4 He by inelastic electron scattering at low momentum transfer,  Phys. Lett. B 31 (1970) 442–444. doi:10.1016/0370-2693(70)90148-6.
  * Jaffe [2005] R. L. Jaffe,  Exotica,  Phys. Rept. 409 (2005) 1–45. doi:10.1016/j.physrep.2004.11.005. arXiv:hep-ph/0409065.
  * West [2023] J. R. West,  Diquark Induced Short-Range Nucleon-Nucleon Correlations & the EMC Effect,  Nuc.Phys.A (2023). arXiv:2009.06968.
  * Ilgenfritz et al. [1978] E.-M. Ilgenfritz, J. Kripfganz, A. Schiller,  Fragmentation of Quark and Diquark Jets,  Acta Phys. Polon. B 9 (1978) 881.
  * Batley et al. [2015] J. R. Batley, et al. (NA48/2),  Search for the dark photon in $\pi^{0}$ decays,  Phys. Lett. B 746 (2015) 178–185. doi:10.1016/j.physletb.2015.04.068. arXiv:1504.00607.
  * Banerjee et al. [2020] D. Banerjee, et al. (NA64),  Improved limits on a hypothetical X(16.7) boson and a dark photon decaying into $e^{+}e^{-}$ pairs,  Phys. Rev. D 101 (2020) 071101. doi:10.1103/PhysRevD.101.071101. arXiv:1912.11389.
  * Bossi et al. [2023] F. Bossi, et al. (PADME),  Cross-section measurement of two-photon in-flight annihilation of positrons at s=20 MeV with the PADME detector,  Phys. Rev. D 107 (2023) 012008. doi:10.1103/PhysRevD.107.012008. arXiv:2210.14603.
  * Darmé et al. [2022] L. Darmé, M. Mancini, E. Nardi, M. Raggi,  Resonant search for the X17 boson at PADME,  Phys. Rev. D 106 (2022) 115036. doi:10.1103/PhysRevD.106.115036. arXiv:2209.09261.


problem2  Input: Output: 11institutetext: Department of Computer Science,
University of Helsinki, Finland 11email:
<EMAIL_ADDRESS>
# Computing all-vs-all MEMs in grammar-compressed text††thanks: Supported by
Academy of Finland (Grants 323233 and 339070), and by Basal Funds FB0001,
Chile (first author)

Diego Díaz-Domínguez  Leena Salmela

###### Abstract

We describe a compression-aware method to compute all-vs-all maximal exact
matches (MEM) among strings of a repetitive collection $\mathcal{T}$. The key
concept in our work is the construction of a fully-balanced grammar
$\mathcal{G}$ from $\mathcal{T}$ that meets a property that we call _fix-free_
: the expansions of the nonterminals that have the same height in the parse
tree form a fix-free set (i.e., prefix-free and suffix-free). The fix-free
property allows us to compute the MEMs of $\mathcal{T}$ incrementally over
$\mathcal{G}$ using a standard suffix-tree-based MEM algorithm, which runs on
a subset of grammar rules at a time and does not decompress nonterminals. By
modifying the locally-consistent grammar of Christiansen et al. [7], we show
how we can build $\mathcal{G}$ from $\mathcal{T}$ in linear time and space. We
also demonstrate that our MEM algorithm runs on top of $\mathcal{G}$ in
$O(G+occ)$ time and uses $O(\log G(G+occ))$ bits, where $G$ is the grammar
size, and $occ$ is the number of MEMs in $\mathcal{T}$. In the conclusions, we
discuss how our idea can be modified to implement approximate pattern matching
in compressed space.

###### Keywords:

MEMs Text Compression Context-free grammars.

##  1 Introduction

A _maximal exact match_ (MEM) between two strings is a match that cannot be
extended without introducing mismatches or reaching an end in one of the
strings. MEMs play an important role in biological sequence analyses [17, 19,
20] as they simplify finding long stretches of identical sequences. However,
the rapid pace at which biological data have grown in later years has made the
computation of MEMs intractable in these inputs.

Seed-and-extend heuristics is a popular solution to scale the problem of
approximate pattern matching in large collections [2, 15, 19, 20, 21]. One of
the aspects that impacts these heuristics’ performance is the seeding
mechanism. In this regard, using MEMs to seed alignments of near identical
sequences, like genomes or proteins, offers two important benefits. First, it
improves the accuracy of the result and reduces the cost of the heuristic’s
extension phase. The reason is because the result in an approximate alignment
of highly-similar strings is indeed a sequence of long MEMs separated by small
edits. Second, computing MEMs takes linear time [33, 24], and in small or
medium-sized collections, it does not impose a considerable overhead. The
problem, as mentioned before, is that genomic data have grown to a point where
fitting the necessary data structures to detect MEMs into main memory is
hardly possible.

State-of-the-art methods [31, 28, 30, 4, 29, 25] address the problem of
finding MEMs in large inputs by using compressed text indexes [13, 9] and
matching statistics [5]. Although these approaches have demonstrated that
string compression greatly reduces the overhead of computing MEMs in
repetitive collections, they need to build the full index first, which can be
expensive.

An efficient method that exploits text redundancies to compute all-vs-all MEMs
in massive string collections could have important implications in
Bioinformatics. Tasks like _de novo_ genome assembly, multiple genome
alignment, or protein clustering could become available for inputs that are
TBs in size. This result, in turn, could have a major impact on genomic
research.

Our contribution We present a method to compute all-vs-all MEMs in a
collection $\mathcal{T}$ of repetitive strings. Our idea consists of building
a context-free grammar $\mathcal{G}$ from $\mathcal{T}$, from which we compute
the MEMs. Our grammar algorithm ensures a property that we call _fix-free_ ,
which means that the expansions of nonterminals with the same height form a
set that is prefix-free and suffix-free. This idea enables the fast
computation of MEMs by incrementally indexing parts of the grammar with simple
data structures. Section 5 shows how we can build a fix-free grammar in linear
time and space using a variant of the locally-consistent grammar of
Christiansen et al. [7]. In Section 6, we describe how to compute a list
$\mathcal{L}$ with the MEM “precursors” (prMEMs) from $\mathcal{G}$ in
$O(G+|\mathcal{L}|)$ time and $O(\log G(G+|\mathcal{L}|))$ bits of space,
where $G$ is the grammar size. In Section 6, we show how to enumerate all the
$occ$ all-vs-all MEMs from $\mathcal{L}$ and $\mathcal{G}$, yielding thus an
algorithm that runs in $O(G+occ)$ time and uses $O(\log G(G+occ))$ bits.

##  2 Preliminaries

###  2.0.1 String data structures

Consider a string $T[1..n-1]$ over the alphabet $\Sigma[2,\sigma]$, and the
sentinel symbol $\Sigma[1]=\texttt{\$}$, which only occurs at $T[n]$. The
_suffix array_ [23] of $T$ is a permutation $S\\!A[1..n]$ that enumerates the
suffixes $T[i..n]$ of $T$ in increasing lexicographic order,
$T[S\\!A[i]..n]<T[S\\!A[i+1]..n]$, for $i\in[1..n-1]$. The _longest common
prefix_ array $LCP[1..n]$ [23] stores in $LCP[j]$ the longest common prefix
between $T[S\\!A[j-1]]$ and $T[S\\!A[j]]$. Given a vector $V[1..n]$ of
integers, a _minimum range query_ $rmq(V,j,j^{\prime})$, with $j<j^{\prime}$,
returns the minimum value in the arbitrary range $V[j..j^{\prime}]$. By
encoding $LCP$ with support for $rmq$ [12], one can obtain the length of the
prefix shared by two arbitrary suffixes $T[S\\!A[j]..n]$ and
$T[S\\!A[j^{\prime}]..n]$ by performing $rmq(LCP,j,j^{\prime})$.

###  2.0.2 Locally-consistent parsing

_Parsing_ consists in breaking a text $T[1..n]$ into a sequence of phrases.
The parsing is _locally-consistent_ [10] if, for any pattern $P$, its
occurrences in $T$ are largely partitioned in the same way. There is more than
one way to make a parsing locally consistent (see [32, 3, 7] for more
details), but this work focuses on those using _local minima_. A position
$T[j]$ is a local minimum if $T[j-1]>T[j]<T[j+1]$. A method that uses this
idea scans $T$, and for each pair of consecutive local minima $j$ and
$j^{\prime}$, it defines the phrase $T[j..j^{\prime}-1]$. The procedure to
compare adjacent positions in $T$ can vary. For instance, Christiansen et al.
[7] first create a new string $\hat{T}$ where they replace equal-symbol runs
by metasymbols. Then, they define a random permutation $\pi$ for the alphabet
of $\hat{T}$, and compute the breaks as
$\pi(\hat{T}[j-1])>\pi(\hat{T}[i])<\pi(\hat{T}[i+1])$. On the other hand,
Nogueira et al. [27] compare consecutive suffixes rather than positions.
Concretely, $T[j]$ is a local minimum if the suffix $T[j..n]$ is
lexicographically smaller than the suffixes $T[j-1..n]$ and $T[j+1..n]$. This
suffix-based local minimum was proposed by Nong et al. [26] in their linear-
time suffix array algorithm SAIS. They refer to it as an LMS-type position and
to the phrases covering consecutive LMS-type positions as LMS-substrings.

###  2.0.3 Grammar compression

Grammar compression [16, 6] is a form of lossless compression that encodes a
string $T[1..n]$ as a context-free grammar $\mathcal{G}$ that only generates
$T$. Formally, $\mathcal{G}=\\{\Sigma,V,\mathcal{R},S\\}$ is a tuple of four
elements, where $\Sigma$ is the set of terminals, $V$ is the set of
nonterminals, $\mathcal{R}$ is a set of derivation rules in the form
$X\rightarrow F$, with $X\in V$ being a nonterminal and $F\in(\Sigma\cup
V)^{*}$ being its replacement, and $S\in V$ is the start symbol. In grammar
compression, each nonterminal $X\in V$ appears only once on the left-hand
sides of $\mathcal{R}$, which ensures the unambiguous decompression of $T$.

The graphical sequence of derivations that transforms $S$ into $T$ is referred
to as the parse tree. The root of this tree is labelled $S$ and has $|A|$
children, with $S\rightarrow A$. The root’s children are labelled from left to
right according to $A$’s sequence. The subtrees for the root’s children are
recursively defined in the same way. The height of a nonterminal $X$ is the
longest path in the parse subtree induced by $X$’s recursive expansion. The
grammar is said to be fully-balanced if, for each nonterminal $X\in V$ at
height $i$, the symbols in the right-hand side of $X\rightarrow
A_{1}A_{2}{\cdots}A_{x}\in\mathcal{R}$ are at height $i-1$.

The _grammar tree_ is a pruned version of the parse tree that, for each $X\in
V$, keeps only the leftmost internal node labelled $X\in V$. The remaining
internal nodes labelled $X$ are transformed into leaves. The leaves of the
grammar tree induce a partition over $T$: for each grammar tree leaf $u$, its
corresponding phrase is the substring in $T$ mapping the terminal symbols
under the parse tree node from which $u$ was originated. One can classify the
occurrences in $T$ of a pattern $P\in\Sigma^{*}$ into primary and secondary. A
_primary occurrence_ of $P$ crosses two or more phrases in the partition
induced by the grammar tree. On the other hand, a _secondary occurrence_ of
$P$ is fully contained within a phrase.

###  2.0.4 Locally-consistent grammar

A grammar $\mathcal{G}$ generating $T[1..n]$ is locally consistent if the
occurrences of the same pattern are largely compressed in the same way [14,
7]. A mechanism to build $\mathcal{G}$ is by transforming $T$ in successive
rounds of locally-consistent parsing [7, 11, 27]. In every round $i$, the
construction algorithm receives as input a string $T^{i}[1..n^{i}]$ over an
alphabet $\Sigma^{i}$, which represents a partially-compressed version of $T$
(when $i=1$, $T^{1}=T$ and $\Sigma^{1}=\Sigma$). Then, it breaks $T^{i}$ using
its local minima and creates a set $\mathcal{S}^{i}$ with the distinct phrases
of the parsing. For every phrase $F\in\mathcal{S}^{i}$, the algorithm defines
a new metasymbol $X$ and appends the new rule $X\rightarrow F$ into
$\mathcal{R}$. The value of $X$ is the number of symbols in $\Sigma\cup V$
before the parsing round $i$ plus the rank of $F$ in an arbitrary order of
$\mathcal{S}^{i}$. After creating the new rules, the algorithm replaces the
phrases in $T^{i}$ with their corresponding metasymbols to produce another
string $T^{i+1}[1..n^{i+1}]$, which is the input for the next round $i+1$.
Notice that the alphabet $\Sigma^{i+1}\subset V$ for $T^{i+1}$ is the subset
of metasymbols that the algorithm assigned to the phrases in $T^{i}$. When
$T^{i+1}$ does not have local minima, the algorithm creates the final rule
$S\rightarrow T^{i+1}$ for the start symbol $S$ of $\mathcal{G}$ and finishes.
The whole process runs in $O(n)$ time and produces a fully-balanced grammar.
Christiansen at al. [7] showed that it is possible to obtain a locally-
consistent grammar of size $O(\gamma\log n/\gamma)$ in $O(n)$ expected time,
where $\gamma$ is the size of the smallest string attractor for $T$.

##  3 Definitions

Let $T[1..n]$ be a string of length $n$. We use the operator $T[1..j]$ to
denote the $jth$ prefix of $T$ and the operator $T[j..]=T[j..n]$ to denote its
$jth$ suffix.

###### Definition 1

MEM: let $T_{x}[1..n_{x}]$ and $T_{y}[1..n_{y}]$ be two strings over the
alphabet $\Sigma$. A maximal exact match
$T_{a}[a..b]=T_{y}[a^{\prime}..b^{\prime}]$ of length $\ell$, denoted
$M(T_{x},T_{y},a,a^{\prime},\ell)$, has the following properties: (i) $a=1$ or
$a^{\prime}=1$, or $T_{x}[a-1]\neq T_{y}[a^{\prime}-1]$. (ii) $b=n_{x}$ or
$b^{\prime}=n_{y}$, or $T_{x}[b+1]\neq T_{y}[b^{\prime}+1]$.

We formulate the problem we address in this work as follows:

We will refer to the parsing of Section 2.0.2 as LCPar, and the grammar
algorithm of Section 2.0.4 as LCGram. Let
$\mathcal{G}=(\Sigma,V,\mathcal{R},S)$ be the fully-balanced grammar
constructed by LCGram from $\mathcal{T}$ in $h$ rounds of parsing. We assume
for the moment that the definition of local minima is arbitrary, but sequence-
based. We denote the sum of the right-hand side lengths of $\mathcal{R}$ as
$G$ and the number of nonterminals as $g=|V|$. Additionally, we consider the
partition $V=\\{V^{1},\ldots,V^{h}\\}$ such that every $V^{i}$, with
$i\in[1..h]$, has the nonterminals generated during the parsing round $i$.
Similarly, the partition $\mathcal{R}=\\{\mathcal{R}^{1},\ldots,R^{h}\\}$
groups in $\mathcal{R}^{i}$ the rules generated during the parsing round $i$.
We denote as $G^{i}$ the sum of the right-hand side lengths of
$\mathcal{R}^{i}$ and $g^{i}=|V^{i}|$. We will refer to the sequence $[1..h]$
as the _levels_ of the grammar, which is read bottom-up in the parse tree.
$\mathcal{T}$ is at level $0$.

We assume LCGram compresses the strings of $\mathcal{T}$ independently but
collapses all the rules in one single grammar $\mathcal{G}$. Thus, the rule
$S\rightarrow A_{1}..A_{m^{\prime}}$ encodes the compressed strings of
$\mathcal{T}$ concatenated in the string $A_{1}\ldots A_{m^{\prime}}$.

The operator $exp(X)$ returns the string in $\Sigma^{*}$ resulting from the
recursive expansion of $X\in V$. The function $exp$ can also receive as input
the sequence $X_{1}{\cdots}X_{b}\in V^{*}$, in which case it returns the
concatenation $exp(X_{1}){\cdots}exp(X_{b})$. The operation $lcp^{i}(X,Y)$
receives two nonterminals $(X,Y)\in V^{i}$ and returns the longest common
prefix between $exp(X)$ and $exp(Y)$. Similarly, the operator $lcs^{i}(X,Y)$
returns the longest common suffix between $exp(X)$ and $exp(Y)$.

###### Definition 2

A set $\mathcal{S}$ of strings is fix-free iff, for any pair
$F,Q\in\mathcal{S}$, the string $F$ is not a suffix nor a prefix of $Q$, and
vice-versa.

###### Definition 3

A grammar $\mathcal{G}$ is fix-free iff it is fully balanced, and for any
level $i$, the set $\mathcal{S}^{i}=\\{exp(X_{1}),\ldots,exp(X_{g^{i}})\\}$,
with $X_{1},\ldots,X_{g^{i}}\in V^{i}$, is fix-free.

###### Definition 4

Primary MEM (prMEM): let $M(T_{x},T_{y},a,^{\prime}a,\ell)$, with
$T_{x},T_{y}\in\mathcal{T}$, be a MEM. $M(T_{x},T_{y},a,^{\prime}a,\ell)$ is
primary if both $T_{x}[a..a+\ell-1]$ and
$T_{y}[a^{\prime}..a^{\prime}+\ell-1]$ are primary occurrences of the pattern
$T_{x}[a..a+\ell-1]=T_{y}[a^{\prime}..a^{\prime}+\ell-1]$.

##  4 Overview of our algorithm

We solve $\textsc{AvAMem}(\mathcal{T},\tau)$ in three steps: (i) we build a
fix-free grammar from $\mathcal{T}$ using a modification of LCGram, (ii) we
compute a list $\mathcal{L}$ storing the prMEMs of $\mathcal{T}$, and (iii) we
use $\mathcal{L}$ and $\mathcal{G}$ to report the positions in $\mathcal{T}$
of all the MEMs.

The advantage of $\mathcal{G}$ being fix-free is that we can use the following
lemma:

###### Lemma 1

Let $\mathcal{G}$ be a fix-free grammar. Two rules $X\rightarrow AZB,\
Y\rightarrow CZD\in\mathcal{R}^{i}$, with $Z\in V^{i-1*}$ and $A,B,C,D\in
V^{i-1}$ yield a prMEM if $\ell=lcs^{i-1}(A,C)+exp(Z)+lcp^{i-1}(B,D)\geq\tau$.

###### Proof

Both $exp(X)$ and $exp(Y)$ contain $exp(Z)$ as a substring as the rules for
$X$ and $Y$ have occurrences of $Z$, and there is only one string $exp(Z)$ the
grammar can produce. Still, the strings $exp(A)$ and $exp(C)$ (respectively,
$exp(B)$ and $exp(D)$) could share a suffix (respectively, a prefix), meaning
that the prMEM extends to the left of $Z$ (respectively, the right of $Z$).
The fix-free property guarantees that the left boundary of the prMEM lies at
some index in the right-to-left comparison of $exp(A)$ and $exp(C)$, and that
the right boundary lies at some position within the left-to-right comparison
of $exp(B)$ and $exp(D)$.

Lemma 1 offers a simple solution to detect prMEMs as we do not have to look
into other parts of $\mathcal{G}$’s parse tree to check the boundaries of the
prMEM in $(X,Y)$. The only remaining aspects to consider are, first, how to
get a fix-free grammar, and then, how to compute $lcs(A,C)$, $lcp(B,D)$, and
$|exp(Z)|$ efficiently. Once we solve these problems, finding prMEMs reduces
to run a suffix-tree-based MEM algorithm over the right-hand sides of each
$\mathcal{R}^{i}$. On the other hand, getting the positions in $\mathcal{T}$
of the MEMs (step 3.) requires traversing the rules of $\mathcal{G}$, but it
is not necessary to perform any string comparison.

##  5 Building the fix-free grammar

We first describe the parsing we will use in our variant of LCGram. We refer
to this procedure as FFPar. The input is a string collection
$\mathcal{T}^{\prime}$ over the alphabet
$\Sigma^{\prime}=\\{\texttt{\$}\\}\cup\Sigma\cup\\{\texttt{\\#}\\}$, where
each string $T_{x}=\texttt{\$}T\texttt{\$}\texttt{\\#}\in\mathcal{T}^{\prime}$
is flanked by the symbols $\\{\texttt{\$},\texttt{\\#}\\}\notin\Sigma$ that do
not occur in the internal substring $T\in\Sigma^{*}$.

We choose a function $h:\Sigma^{\prime}\rightarrow[0..p+1]$ that maps symbols
in $\Sigma$ to integers in the range $[1..p]$ uniformly at random, where
$p>|\Sigma|$ is a large prime number. If $c\in\Sigma$, then $h(c)=(ac+b)\bmod
p$, where $a,b\in[1..p]$ are chosen uniformly at random. If
$c=\texttt{\$}\notin\Sigma$, then $h(c)=0$, and if $c=\texttt{\\#}$, then
$h(c)=p+1$.

We use $h$ to define the local minima in $\mathcal{T}^{\prime}$. The idea is
to combine $h$ with a scheme to classify symbols similar to that of SAIS [26].
Let $T_{x}[1..n_{x}]$ be a string in $\mathcal{T}^{\prime}$. A position
$T_{x}[j]$ with $j\in[2..n_{x}-1]$ has three possible classifications:

  * •

L-type : $h(T_{x}[j])>h(T_{x}[j+1])$ or $T_{x}[j]=T_{x}[j+1]$ and $T_{x}[j+1]$
is L-type.

  * •

S-type : $h(T_{x}[j])<h(T_{x}[j+1])$ or $T_{x}[j]=T_{x}[j+1]$ and $T_{x}[j+1]$
is S-type.

  * •

LMS-type : $T_{x}[j]$ is S-type and $T_{x}[j-1]$ is L-type.

The LMS-type positions are the local minima of $\mathcal{T}^{\prime}$.
Randomising the local minimum definition aims to protect us against
adversarial inputs. Notice that $h$ is not a random permutation $\pi$ like
Christiansen et al. [7], but it still defines a total order over $\Sigma$ as
it does not assign the same random value to two symbols, which is enough for
our purposes.

###### Lemma 2

FFPar: let $T_{x}[1..n_{x}]\in\mathcal{T}^{\prime}$ be a string in the
collection. For every pair of consecutive local minima $j>1$ and
$j^{\prime}<n_{x}$, we define the phrase $T_{x}[j-1..j^{\prime}+1]$. For the
leftmost local minimum $T_{x}[j]$, we define the phrase $T_{x}[1..j+1]$. For
the rightmost local minimum $T_{x}[j^{\prime}]$, we define
$T_{x}[j^{\prime}-1..n_{x}]$. The resulting set of parsing phrases is fix-
free.

###### Proof

Let us first consider the set $\mathcal{S}$ created by LCPar. We will say that
a phrase $T_{x}[j..j-1]$ in LCPar is an _instance_ of $F\in\mathcal{S}$ if
$T_{x}[j..j^{\prime}-1]$ matches $F$. When $F$ occurs in
$\mathcal{T}^{\prime}$ as a proper suffix or prefix of another phrase in
$\mathcal{S}$, it is not an instance, only an occurrence of $F$.

Let $\mathcal{W}\subset\mathcal{S}$ be a subset of phrases and let
$F\in\mathcal{S}\setminus\mathcal{W}$ be a phrase occurring as a proper prefix
in each element of $\mathcal{W}$. Consider any pair of instances
$F=T_{x}[j..j^{\prime}-1]$ and $Q=T_{y}[l..l^{\prime}-1]\in\mathcal{W}$ such
that $T_{x},T_{y}\in\mathcal{T}^{\prime}$, and $(l,l^{\prime})$ (respectively,
$(j,j^{\prime})$) are consecutive local minima. The substring
$T_{x}[j^{\prime}..j^{\prime}+1]$ following $F$’s instance cannot be equal to
the substring $T_{y}[l+|F|..l+|F|+1]$ following $F$’s occurrence within $Q$
because $T_{x}[j^{\prime}]$ is a local minimum while $T_{y}[l+|F|]$ is not. We
know that $T_{y}[l+|F|]$ is within $Q$ because $T_{y}[l..l+|F|-1]$ is an
occurrence of $F$ that is a proper prefix of $Q$. Therefore, if $T_{y}[l+|F|]$
were a local minimum, $Q$ would also be an instance of $F$. In conclusion,
running FFPar will right-extend every instance of $F$ in
$\mathcal{T}^{\prime}$ such that none of the resulting phrases is a proper
prefix in the right-extended phrases of $\mathcal{W}$.

We develop a similar argument for the left extension. Suppose, in this case,
$F\in\mathcal{S}\setminus\mathcal{W}$ is a proper suffix in
$\mathcal{W}\subset\mathcal{S}$. As before, we assume $\mathcal{S}$ was built
using LCPar and that $F=T_{x}[j..j^{\prime}-1]$ and
$Q=T_{y}[l..l^{\prime}-1]\in\mathcal{W}$ are phrase instances. The symbol
$T_{x}[j-1]$ preceding $F$’s instance cannot be equal to the symbol
$T_{y}[l^{\prime}-|F|-1]$ preceding the occurrence
$F=T_{y}[l^{\prime}-|F|..l^{\prime}-1]$ within $Q$. The reason is because
$F[1]=T_{x}[j]$ is a local minimum, while
$Q[|Q|-|F|+1]=T_{y}[l^{\prime}-|F|]=F[1]$ is not. In conclusion, FFPar left-
extends each occurrence of $F$ such that none of the resulting phrases is a
proper suffix in the left-extended elements of $\mathcal{W}$.

###  5.0.1 The FFGram algorithm

FFGram is our LCGram variant that builds a fix-free grammar by applying
successive rounds of FFPar (Definition 2). The input of FFGram is the
collection $\mathcal{T}^{1}$ built from $\mathcal{T}$ by adding the special
flanking symbols $\texttt{\$}T_{x}\texttt{\$}\texttt{\\#}$ in every
$T_{x}\in\mathcal{T}$. The alphabet of $\mathcal{T}^{1}$ is
$\Sigma^{1}=\\{\texttt{\$}\\}\cup\Sigma\cup\\{\texttt{\\#}\\}$.

In every round $i$, we create a random hash function
$h^{i}:\Sigma^{i}\rightarrow[0..p+1]$, with $p>|\Sigma^{i}|$, to define the
local minima of $\mathcal{T}^{i}$. Then, we run FFPar using $h^{i}$ and sort
the resulting set $\mathcal{S}^{i}$ of phrases in lexicographical order
starting from the leftmost proper suffix of each string. The relative order of
strings of $\mathcal{S}^{i}$ differing only in the leftmost symbol is
arbitrary. Let $c$ be the number of symbols in $\Sigma\cup V$ before parsing
round $i$ and let $r$ the rank of $F\in\mathcal{S}^{i}$ in the ordering we
just defined. We assign the metasymbol $X=c+r\in V^{i}$ to $F$ and append the
new rule $X\rightarrow F\in\mathcal{R}^{i}$. The last step in the round is to
create the collection $\mathcal{T}^{i+1}$ by replacing the phrases with their
corresponding metasymbols. Additionally, we define two special new symbols
$\\{\$,\\#\\}$, which we append at the ends of the strings in
$\mathcal{T}^{i+1}$. Thus, the alphabet of $\mathcal{T}^{i}$ becomes
$\Sigma^{i}=\\{\$\\}\cup V^{i}\cup\\{\\#\\}$. We assume the occurrences of the
special symbols $\\#,\$$ in the right-hand sides of $\mathcal{R}$ expand to
the empty string. FFGram stops after $h$ parsing rounds, when the input
$\mathcal{T}^{i}$ does not have local minima. Figure 1 shows an example.

Figure 1: Execution of FFGram on $gtaatagtagtacc$#. The left side shows the
parse tree up to level $2$, and the right side shows the corresponding rules
for those levels. The underlined symbols are local minima. The horizontal
lines in grey are MEMs of length $\geq\tau=3$. Each shape identifies a
specific MEM in Figures 3 and 4.

###### Lemma 3

The grammar $\mathcal{G}$ resulting from running FFGram over $\mathcal{T}$ is
fix-free.

###### Proof

Consider the execution of FFPar over $\mathcal{T}^{1}$ in the first round of
FFGram. The output set $\mathcal{S}^{1}$ is over the alphabet
$\\{\texttt{\$}\\}\cup\Sigma\cup\\{\texttt{\\#}\\}$ and is, by Lemma 2, fix-
free. Thus, the symbols of $V^{1}$ meet the fix-free property of Definition 3.
Now consider the parsing rounds $i-1$ and $i\geq 2$. Assume without loss of
generality that the nonterminals in $V^{i-1}$ meet Definition 3. The recursive
definition of FFGram implies that the phrases in $\mathcal{S}^{i}$ are over
the alphabet $V^{i-1}$. Thus, for any pair of different strings
$F,Q\in\mathcal{S}^{i}$ sharing a prefix $F[1..q]=Q[1..q]$, the symbols
$F[q+1]\neq E[q+1]$ expand to different sequences $exp(F[q+1])\neq
exp(Q[q+1])$ that are not prefix one of the other as $F[f+1],Q[q+1]$ belong to
$V^{i-1}$. Therefore, $exp(F)$ and $exp(Q)$ do not prefix one to the other
either. The same argument applies when $F$ and $Q$ share a prefix. We conclude
then that the metasymbols of $V^{i}$ also meet the fix-free property of
Definition 3.

###  5.0.2 Overlaps in the fix-free grammar

A relevant feature of FFGram is that consecutive nonterminals in the right-
hand sides of $\mathcal{R}$ cover overlapping substrings of $\mathcal{T}$.
This property allows us to compute prMEMs as described in Lemma 1. The
downside, however, is that expanding substrings of $\mathcal{T}$ from
$\mathcal{G}$ is now more difficult. However, the number of symbols
overlapping in every grammar level is constant (one to the left and two to the
right). Depending on the situation, we might want to decompress nonterminals
considering or skipping overlaps. Thus, we define the operations $efexp(X)$,
$lexp(X)$, and $rexp(X)$ that return different types of nonterminal
expansions. These functions only differ in the edges they skip in $X$’s
subtree during the decompression.

  * •

$efexp(X)$: recursively skips the leftmost and two rightmost edges.

  * •

$lexp(X)$: recursively skips the two rightmost edges, and the leftmost edges
when the parent node does not belong to the leftmost branch.

  * •

$rexp(X)$ recursively skips the leftmost edges, and the two rightmost edges
when the parent node does not belong to the rightmost branch.

Figure 2 shows examples of $efexp(X)$, $lexp(X)$ and $rexp(X)$. We also modify
the functions $lcs^{i}$ and $lcp^{i}$ described in Definitions 3. Let $X,Y\in
V^{i}$ be two nonterminals at level $i$. The function $lcs^{i}(X,Y)$ now
returns the longest common suffix between $lexp(X)$ and $lexp(Y)$; and
$lcp^{i}(X,Y)$ returns the longest common prefix between $rexp(X)$ and
$rexp(Y)$.

We remark that $efexp$, $lexp$, $rexp$, $lcs^{i}$, and $lcp^{i}$ are virtual
as our algorithm to find prMEMs never calls them directly. Instead, it
incrementally produces satellite data structures with precomputed answers to
solve them in $O(1)$ time.

##  6 Computing prMEMs in the fix-free grammar

Our MEM algorithm uses the grammar $\mathcal{G}=\\{\Sigma,V,\mathcal{R},S\\}$
resulted from running FFGram with $\mathcal{T}^{\prime}$, and produces the
list $\mathcal{L}$ of prMEMs in $\mathcal{T}$. We consider a set $\mathcal{O}$
of $g=|\mathcal{R}|$ rules storing the cumulative lengths of the $efexp$
expansions for the right-hand sides of $\mathcal{R}$. We also define a logical
partition for $\mathcal{O}$ according to the grammar levels. Let $X\rightarrow
A_{1}A_{2}{\cdots}A_{x}\in\mathcal{R}^{i}$ be a rule at level $i$. The rule
$X\rightarrow c_{1}\cdots c_{x}\in\mathcal{O}^{i}$ stores in $c_{j}$, with
$j\in[3..x-1]$, the value $c_{j}=efexp(A_{2})+\cdots+efexp(A_{j-1})$. To avoid
recursive overlaps, we set $c_{1}=0,c_{2}=0$, and
$c_{x-1}=c_{x-2},c_{x}=c_{x-2}$. The leftmost tree of Figure 2 shows an
example of a rule in $\mathcal{O}$. We assume FFGram already constructed
$\mathcal{O}$.

Figure 2: Expansions for nonterminal $6$ of Figure 1. Dashed lines are skipped
branches. The sequence of numbers below $efexp(6)$ corresponds to the rule
$6\rightarrow 0\ 0\ 3\ 6\ 6\in\mathcal{O}$.

#### prMEM encoding.

Every element of $\mathcal{L}$ is a tuple $(X,Y,o_{X},o_{Y},\ell)$ of four
elements. $X$ and $Y$ are the nonterminals labelling the lowest nodes in
$\mathcal{G}$’s grammar tree that encode the primary occurrences for the MEM’s
sequence. The fields $o_{X}$ and $o_{Y}$ are the number of terminal symbols
preceding the prMEM within $efexp(X)$ and $efexp(Y)$ (respectively), and
$\ell$ is the length of the prMEM.

#### Grammar encoding.

We encode every subset $\mathcal{R}^{i}\subset\mathcal{R}$ as an individual
string collection concatenated in one single array $R^{i}[1..G^{i}]$. We
create an equivalent array $O^{i}$ for the rules of
$\mathcal{O}^{i}\subset\mathcal{O}$. We also consider a function $map(X)=j$
that indicates that the right-hand side $F=R^{i}[a..a^{\prime}]$ of
$X\rightarrow F\in\mathcal{R}^{i}$ is the $jth$ string of $R^{i}$ from left to
right. Additionally, we define the function $parent(b)=X$ that returns $X$ for
each position $b\in[a..a^{\prime}]$. We assume $map$ and $parent$ are
implemented in $O(1)$ time and $G_{i}+o(G_{i})$ bits using bit vectors.

Our prMEM algorithm is an iterative process that, each step $i$, searches for
prMEMs in the rules of the grammar level $i$. Still, there is a slight
difference between the iteration $i=1$ and the others $i>1$, so we explain
them separately.

###  6.0.1 First iteration

The first step in iteration $i=1$ is to create a sparse suffix array $S\\!A$
for $R^{1}$ that discards each position $S\\!A[j]$ meeting one of the
following conditions: (i) $R^{i}[S\\!A[j]]$ is the start of a phrase,
$R^{i}[S\\!A[j]+1]$ is the end of a phrase, or (iii) $R^{i}[S\\!A[j]]$ is the
end of a phrase. We refer to the resulting sparse suffix array as $A$. The
next step is to produce the LCP array for $A$, which we name $GLCP$ for
convenience. We then run the suffix-tree-based MEM algorithm [33] using $A$
and $GLCP$. We implement this step by simulating with $GLCP$ a traversal over
the compact trie induced by the suffixes of $R^{i}$ in $A$ (see [18, 1] for
the traversal). Every time the MEM algorithm reports a triplet
$(A[u],A[u^{\prime}],l)$ for a MEM
$R^{i}[A[u]..A[u]+l-1]=R^{i}[A[u^{\prime}]..A[u^{\prime}]+l-1]$, we append the
tuple $(X=parent(A[u])$, $Y=parent(A[u^{\prime}])$, $o_{X}=O^{i}[A[u]]$,
$o_{Y}=O^{i}[A[u^{\prime}]]$, $\ell=l$) into $\mathcal{L}$. Figure 3
exemplifies this algorithm. Once we finish running the MEM algorithm, we
obtain satellite data structures for the next iteration $i+1$:

  * •

A vector $P^{1}[1..g^{1}]$ encoding the permutation of $R^{1}$ resulted from
sorting the $lexp$ expansions of the strings in colexicographical order.

  * •

A vector $LCS^{1}[1..g^{1}]$ storing LCS (longest common suffix) values
between the $lexp$ expansions of strings in $R^{i}$ that are consecutive in
the permutation $P^{1}$. We encode $LCS^{1}$ with support for range minimum
queries in $O(1)$ time. Thus, given two nonterminals $X,Y\in V^{1}$, we
implement $lcs^{1}(X,Y)$ as $rmq(LCS^{1},P^{1}[map(X)],P^{1}[map(Y)])$.

  * •

A vector $LCP^{1}[1..g^{1}]$ storing LCP values between the $rexp$ expansions
of consecutive strings of $R^{1}$. $LCP^{1}$ also supports $O(1)$-time $rmq$
queries so we implement $lcs^{1}(X,Y)$ as $rmq(LCP^{1},X,Y)$.

###  6.0.2 Next iterations

For $i>1$, we receive as input the tuple $(R^{i},O^{i})$ and the vectors
$P^{i-1}$, $LCS^{i-1}$, $LCP^{i-1}$. We assume $LCS^{i-1}$ and $LCP^{i-1}$
support $rmq$ queries in $O(1)$ time so we can implement $lcs^{i-1}$ and
$lcp^{i-1}$ in $O(1)$ time as well.

We compute $A$ and $GLCP$ for $R^{i}$ as in Section 6.0.1. However, we
transform $GLCP$ to store the LCP values of the $rexp$ expansions of the
suffixes of $R^{i}$ in $A$. Let $R^{i}[A[j]..]$ and $R^{i}[A[j+1]..]$ be two
consecutive suffixes in $A$ sharing a prefix of length $GLCP[j+1]=l$. We
update this value to
$GLCP[j+1]=O^{i}[A[j+1]+l]+lcp^{i-1}(R^{i}[A[j]+l]),R^{i}[A[j+1]+l])$.

We use $GLCP$ and $A$ to simulate a traversal over the compact trie induced by
the $rexp$ expansions of the $R^{i}$ suffixes in $A$. The purpose of the
traversal is, again, to run the suffix-tree-based MEM algorithm. Every time
this procedure reports a triplet $(A[u],A[u^{\prime}],l)$ as a MEM, we compute
$o=lcs(R^{i}[u-1],R^{i}[u^{\prime}-1])$, and insert the tuple
$(X=parent(A[u]),Y=parent(A[u^{\prime}])),o_{X}=O^{i}[A[u]]-o+1,o_{Y}=O^{i}[A[u^{\prime}]]-o+1,\ell=o+l)$
into $\mathcal{L}$. Figure 4 shows an example. The final step in the iteration
is to produce the satellite data structures:

  * •

$P^{i}[1..g^{i}]$: we sort the strings in $R^{i}$ colexicographically using
$P^{i-1}$. We define the relative order of any pair of strings $F,Q\in R^{i}$
by comparing their sequences $P^{i-1}[F[1]]{\cdots}P^{i-1}[F[|F|-2]]$ and
$P^{i-1}[Q[1]]{\cdots}P^{i-1}[Q[|Q|-2]]$ from right to left. The resulting
permutation $P^{i}$ has the following property: let $X,X^{\prime}\in V^{i}$ be
two nonterminals. If $P^{i}[map(X)]<P^{i}[map(X^{\prime})]$, it means
$lexp(X)$ is colexicographically equal or smaller than $lexp(X^{\prime})$.

  * •

$LCS^{i}[1..g^{i}]$: we scan the strings of $R^{i}$ in $P^{i}$ order. Let
$R^{i}[a..a^{\prime}]$ and $R^{i}[b..b^{\prime}]$ be two consecutive strings
in the permutation of $P^{i}$. That is, $X=parent(a)$ and
$X^{\prime}=parent(b)$ such that $P^{i}[map(X)]=j$ and
$P^{i}[map(X^{\prime})]=j+1$. Assume their prefixes $R^{i}[a..a^{\prime}-2]$
and $R^{i}[b..b^{\prime}-2]$ share a suffix of length $l\geq 0$. We set
$LCS^{i}[j+1]=O^{i}[a^{\prime}]-O^{i}[a^{\prime}-l-1]+lcs^{i-1}(R^{i}[a^{\prime}-l-2],R^{i}[b^{\prime}-l-2])$.

  * •

$LCP^{i}[1..g^{i}]$: we scan the strings of $R^{i}$ from left to right. Let
$R^{i}[a..a^{\prime}]$ and $R^{i}[b..b^{\prime}]$ be two strings in $R^{i}$
with $X=parent(a)$ and $X^{\prime}=parent(b)=X+1$. Assume their suffixes
$R^{i}[a+1..a^{\prime}]$ and $R^{i}[b+1..b^{\prime}]$ share a prefix of length
$l\geq 0$. We set
$LCS^{i}[map(X^{\prime})]=O^{i}[b+l+1]+lcp^{i-1}(R^{i}[a+1+l],R^{i}[b+1+l])$.

###### Theorem 6.1

Let $\mathcal{G}=\\{\Sigma,V,\mathcal{R},S\\}$ be a fix-free grammar of size
$G$ built with FFGram using the collection
$\mathcal{T}=\\{T_{1},\ldots,T_{u}\\}$. It is possible to obtain from
$\mathcal{G}$ the list $\mathcal{L}$ with the prMEMs of $\mathcal{T}$ in
$O(G+|\mathcal{L}|)$ time and $O(\log G(G+|\mathcal{L}|))$ bits.

###### Proof

In iteration $i=1$, constructing $A$ and $GLCP$ takes $O(G_{1})$ time and
$O(G^{1}\log G^{1})$ bits [26, 18]. Then, we implement the suffix-tree-based
algorithm to report MEMs in $R^{i}$ by combining the method of Abouelhoda et
al. [1], that visits the nodes of the compact trie induced by $GLCP$ in
$O(G^{i})$ time, with Lemma 11.4 of Mäkinen et al. [22], which reports the
MEMs of every internal node. These ideas combined take $O(G^{1}+e^{1})$ time
and $O(\log G^{1}(G^{1}+e^{1}))$ bits, where $e^{1}$ is the number of prMEMs
in the grammar level $1$. The final step is to build $LCP^{1},LCS^{1}$, and
$P^{1}$. FFGram sorted the strings of $R^{1}$ in lexicographical order
according to their $rexp$ expansions, so building $LCP^{1}$ reduces to scan
$R^{1}$ from left to right and compute LCP values between consecutive
elements. This process takes $O(G^{1})$ time and $O(G^{1}\log G^{1})$ bits.
Then, we obtain $P^{1}$ by running SAIS in the reversed strings of $R^{1}$,
which also takes $O(G^{1})$ time. We use the reversed strings to build
$LCS^{1}$ as we did with $LCP^{1}$. Finally, giving $rmq$ support to $LCP^{1}$
and $LCP^{1}$ takes $O(G^{1})$ time and $O(G^{1}\log G^{1})$ bits if we use
the data structure of Johannes Fisher [12]. Summing up, the iteration $i$ runs
in $O(G^{1}+e^{1})$ time and uses $O(\log G^{1}(G^{1}+e^{1}))$ bits. Each
iteration $i>1$ performs the same operations, but it also updates $GLCP$,
$LCP^{i}$, and $LCS^{i}$. These updates require linear scans of the arrays as
processing each position performs $O(1)$ access to $O^{i}$ and $O(1)$ calls to
$lcs^{i-1}$ or $lcp^{i-1}$, which we implement in $O(1)$ time. Thus, the cost
of iteration $i$ is $O(G^{i}+e^{i})$ time and $O(\log G^{i}(G^{i}+e^{i}))$
bits, where $e^{i}$ is the number prMEMs in the grammar level $i$. Combining
the $h$ grammar levels, the cost to compute $\mathcal{L}$ is
$O(G+|\mathcal{L}|)$ time and $O(\log G(G+|\mathcal{L}|))$ bits.

##  7 Positioning MEMs in the text

The last aspect we cover to solve $\textsc{AvAMEM}(\mathcal{T},\tau)$ is
computing from ($\mathcal{L},\mathcal{G}$) the positions in $\mathcal{T}$ of
the MEMs. We assume that the collections $\\{R^{1},\ldots,R^{h}\\}$ of Section
6 are concatenated in one single array $R[1..G]$, and that the collections
$\\{O^{1},\ldots,O^{h}\\}$ are concatenated in another array $O[1..G]$. We
define the function $stringid$, which takes as input an index $u$ within $R$
with $S=parent(u)$ (start symbol in $\mathcal{G}$), and returns the identifier
of the string of $\mathcal{T}$ where $R[u]$ lies.

We first simplify $\mathcal{G}$ to remove the unary paths in its parse tree
(see Section 0.B). This extra step is not strictly necessary, but it is
convenient to avoid redundant work. After the simplification, we create an
array $N[1..G]$, which we divide into $g$ buckets. Each bucket $b\in[1..g]$
stores in an arbitrary order the positions in $R$ for the occurrences of
$b\in\Sigma\cup V$. Additionally, we create a vector $C[1..g]$ that stores in
$C[b]$ the position in $N$ where the bucket for $b\in\Sigma\cup V$ starts.

We report MEMs as follows: we insert the tuples of $\mathcal{L}$ into a stack.
Then, we extract the tuple $(X,Y,o_{Y},o_{X},\ell)$ from the top of the stack
and compute $s_{X}=C[X],e_{X}=C[X+1]-1$ and $s_{Y}=C[Y],e_{Y}=C[Y+1]-1$. For
every pair of indexes $(u,u^{\prime})\in[s_{X},e_{X}]\times[s_{Y},e_{Y}]$, we
get $X^{\prime}=parent(N[u])$, and if $X^{\prime}=S$, we set
$X^{\prime}=stringid(N[u])$. We do the same with $N[u^{\prime}]$ and store the
result in a variable $Y^{\prime}$. Now we produce the new tuple
$(X^{\prime},Y^{\prime},o_{X^{\prime}}=O[N[u]]+o_{X},o_{Y^{\prime}}=O[N[u^{\prime}]]+o_{Y},\ell)$.
If both $X^{\prime}$ and $Y^{\prime}$ are strings identifiers, we report the
tuple $M(X^{\prime},Y^{\prime},o_{X^{\prime}},o_{Y^{\prime}},\ell)$ as an
output of AvAMEM, otherwise we insert the new tuple into the stack. If
$X^{\prime}$ or $Y^{\prime}$ is a string identifier rather than a nonterminal,
we flag the tuple to indicate that one of the elements is a string. Thus, when
we visit the tuple again, we avoid recomputing its values. The report of MEMs
ends when the stack becomes empty.

###### Theorem 7.1

Let $\mathcal{G}$ be a fix-free grammar of size $G$ constructed with FFGram
using the collection $\mathcal{T}=\\{T_{1},\ldots,T_{u}\\}$, and let
$\mathcal{L}$ be the list of prMEMs in $\mathcal{G}$ with length $>\tau$,
where $\tau$ is an input parameter. Given the simplified version of
$\mathcal{G}$ and $\mathcal{L}$, it is possible to report the positions in
$\mathcal{T}$ of the $occ$ MEMs of length $>\tau$ in $O(G+occ)$ time and
$O(\log G(G+occ))$ bits.

###### Proof

The $G$ term in the time complexity comes from the grammar simplification and
the construction of $N$ and $C$. Let $(X,Y,o_{X},o_{Y},\ell)\in\mathcal{L}$ be
a prMEM whose sequence in $\mathcal{T}$ is $L$, with $|L|=\ell$. Let us assume
$aLb$ is the primary occurrence of $L$ under $X$ and $xLz$ is the primary
occurrence under $Y$. In our algorithm, the access pattern in $N$ simulates a
bottom-up traversal of $\mathcal{G}$’s grammar tree that visits every node
labelled $X^{\prime}$ such that $exp(X^{\prime})$ has $aLb$, and every node
labelled $Y^{\prime}$ such that $exp(Y^{\prime})$ has $xLz$. Our idea is
similar to reporting secondary occurrences in the grammar self-index of Claude
and Navarro [8]. They showed that the cost of traversing the grammar to
enumerate the $occ_{P}$ occurrences of a pattern $P$ amortizes to $O(occ_{P})$
time. The argument is that, in a simplified $\mathcal{G}$, each node we visit
in the grammar tree yields at least one occurrence in $\mathcal{T}$. However,
our traversal processes two patterns at the same time ($aLb$ and $yLz$),
pairing each occurrence of one with each occurrence of the other. Thus, our
amortized time to process a prMEM tuple is $O(occ_{X}\times occ_{Y})$, where
$occ_{X}$ and $occ_{Y}$ are the numbers of occurrences in $\mathcal{T}$ for
$aLb$ and $yLz$, respectively. Summing up, the cost of processing all the
tuples in $\mathcal{L}$ is $O(occ)$ time.

###### Corollary 1

Let $\mathcal{T}$ be a string collection of $n$ symbols containing $occ$ MEMs
of length $\geq\tau$, $\tau$ being a parameter. We can solve
$\textsc{AvAMEM}(\mathcal{T},\tau)$ by building a fix-free grammar
$\mathcal{G}$ of size $G$ in $O(n)$ time and $O(G\log G)$ bits, and then
computing the $occ$ MEMs of $\mathcal{T}$ over $\mathcal{G}$ in $O(G+occ)$
time and $O(\log G(G+occ))$ bits.

##  8 Concluding remarks

We have presented a method to compute all-vs-all MEMs that rely on grammar
compression to reduce memory overhead and save redundant calculations. In
particular, given a collection $\mathcal{T}$ of $n$ symbols and $occ$ MEMs, we
can get a grammar $\mathcal{G}$ of size $G$ in $O(n)$ time and $O(G\log G)$
bits of space, and find the MEMs of $\mathcal{T}$ on top of $\mathcal{G}$ in
$O(G+occ)$ time and using $O(\log G(G+occ))$ bits. We believe our framework is
of practical interest as it uses mostly plain data structures that store
satellite data about the grammar. Besides, we can either compute the MEMs at
the same time we construct the grammar or do it later. However, it remains
open to check how far is $G$ from $O(\gamma\log\frac{n}{\gamma})$. The
comparison is reasonable as FFGram, our grammar algorithm, resembles the
locally-consistent grammar of Christiansen et al. [7], which achieves that
bound. Still, it is unclear to us how the overlap produced by FFGram affects
the bound. Overlapping phrases has an exponential effect on the grammar size
but also affects how the text is parsed. An interesting idea would be to find
a way to chain prMEMs as approximate matches and then report those in the last
step of our algorithm instead of the MEMs. An efficient implementation of such
a procedure could significantly reduce the cost of biological sequence
analyses in massive collections.

## References

  * [1] Mohamed Ibrahim Abouelhoda, Stefan Kurtz, and Enno Ohlebusch.  Replacing suffix trees with enhanced suffix arrays.  Journal of Discrete Algorithms, 2(1):53–86, 2004.
  * [2] Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, and David J. Lipman.  Basic local alignment search tool.  Journal of Molecular Biology, 215(3):403–410, 1990.
  * [3] Tugkan Batu, Funda Ergun, and Cenk Sahinalp.  Oblivious string embeddings and edit distance approximations.  In Proc. 17th Symposium on Discrete Algorithms (SODA), pages 792–801, 2006.
  * [4] Christina Boucher, Travis Gagie, Tomohiro I, Dominik Köppl, Ben Langmead, Giovanni Manzini, Gonzalo Navarro, Alejandro Pacheco, and Massimiliano Rossi.  PHONI: Streamed matching statistics with multi-genome references.  In Proc. 21st Data Compression Conference (DCC), pages 193–202, 2021.
  * [5] William I. Chang and Eugene L. Lawler.  Sublinear approximate string matching and biological applications.  Algorithmica, 12(4):327–344, 1994.
  * [6] Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat.  The smallest grammar problem.  IEEE Transactions on Information Theory, 51(7):2554–2576, 2005\.
  * [7] Anders Roy Christiansen, Mikko Berggren Ettienne, Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza.  Optimal-time dictionary-compressed indexes.  ACM Transactions on Algorithms, 17(1):1–39, 2020.
  * [8] Francisco Claude and Gonzalo Navarro.  Improved grammar-based compressed indexes.  In Proc. 19th SPIRE, pages 180–192, 2012.
  * [9] Francisco Claude, Gonzalo Navarro, and Alejandro Pacheco.  Grammar-compressed indexes with logarithmic search time.  Journal of Computer and System Sciences, 118:53–74, 2021.
  * [10] Richard Cole and Uzi Vishkin.  Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms.  In Proc. 18th Anual Symposium on Theory of Computing (STOC), pages 206–219, 1986.
  * [11] Diego Díaz-Domínguez and Gonzalo Navarro.  A grammar compressor for collections of reads with applications to the construction of the BWT.  In Proc. 31st Data Compression Conference (DCC), pages 83–92, 2021\.
  * [12] Johannes Fischer.  Optimal succinctness for range minimum queries.  In Proc. 9th Latin American Symposium, pages 158–169, 2010.
  * [13] Travis Gagie, Gonzalo Navarro, and Nicola Prezza.  Fully-functional suffix trees and optimal text searching in BWT-runs bounded space.  Journal of the ACM, 67(1):article 2, 2020.
  * [14] Artur Jeż.  Approximation of grammar-based compression via recompression.  Theoretical Computer Science, 592:115–134, 2015.
  * [15] W. James Kent.  BLAT—the BLAST-like alignment tool.  Genome Research, 12(4):656–664, 2002.
  * [16] John Kieffer and En-Hui Yang.  Grammar-based codes: a new class of universal lossless source codes.  IEEE Transactions on Information Theory, 46(3):737–754, 2000.
  * [17] Stefan Kurtz, Adam Phillippy, Arthur L. Delcher, Michael Smoot, Martin Shumway, Corina Antonescu, and Steven L. Salzberg.  Versatile and open software for comparing large genomes.  Genome Biology, 5:1–9, 2004.
  * [18] Gad M. Landau, Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park.  Linear-time longest-common-prefix computation in suffix arrays and its applications.  In Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 181–192, 2001.
  * [19] Ben Langmead and Steven L. Salzberg.  Fast gapped-read alignment with bowtie 2.  Nature Methods, 9(4):357–359, 2012.
  * [20] Heng Li.  Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM.  arXiv preprint arXiv:1303.3997, 2013.
  * [21] Heng Li.  Minimap2: pairwise alignment for nucleotide sequences.  Bioinformatics, 34(18):3094–3100, 2018.
  * [22] Veli Mäkinen, Djamal Belazzougui, Fabio Cunial, and Alexandru Tomescu.  Genome-Scale Algorithm Design.  Cambridge University Press, 2015.
  * [23] Udi Manber and Gene Myers.  Suffix arrays: a new method for on–line string searches.  SIAM Journal on Computing, 22(5):935–948, 1993.
  * [24] Edward M. McCreight.  A space-economical suffix tree construction algorithm.  Journal of the ACM, 23(2):262–272, 1976.
  * [25] Gonzalo Navarro.  Computing MEMs on repetitive text collections.  In Proc. 34th Annual Symposium on Combinatorial Pattern Matching (CPM), page article 22, 2023.
  * [26] Ge Nong, Sen Zhang, and Wai Hong Chan.  Linear suffix array construction by almost pure induced-sorting.  In Proc. 19th Data Compression Conference (DCC), pages 193–202, 2009.
  * [27] Daniel Saad Nogueira Nunes, Felipe A. Louza, Simon Gog, Mauricio Ayala-Rincón, and Gonzalo Navarro.  A grammar compression algorithm based on induced suffix sorting.  In Proc. 28th Data Compression Conference (DCC), pages 42–51, 2018\.
  * [28] Enno Ohlebusch, Johannes Fischer, and Simon Gog.  CST++.  In Proc. 17th International Symposium on String Processing and Information Retrieval (SPIRE), pages 322–333, 2010.
  * [29] Massimiliano Rossi, Marco Oliva, Paola Bonizzoni, Ben Langmead, Travis Gagie, and Christina Boucher.  Finding maximal exact matches using the r-index.  Journal of Computational Biology, 29(2):188–194, 2022.
  * [30] Massimiliano Rossi, Marco Oliva, Ben Langmead, Travis Gagie, and Christina Boucher.  MONI: A pangenomic index for finding maximal exact matches.  Journal of Computational Biology, 29(2):169–187, 2022.
  * [31] Kunihiko Sadakane.  Compressed suffix trees with full functionality.  Theory of Computing Systems, 41(4):589–607, 2007.
  * [32] Suleyman Cenk Sahinalp and Uzi Vishkin.  On a parallel-algorithms method for string matching problems (overview).  Algorithms and Complexity, pages 22–32, 1994.
  * [33] Peter Weiner.  Linear pattern matching algorithms.  In Proc. 14th Annual Symposium on Switching and Automata Theory (SWAT), pages 1–11, 1973.

## Appendix

##  Appendix 0.A Figures and Examples

Figure 3: First iteration to find prMEMs with $\tau=3$ in the grammar of
Figure 1. (A) The encoding of $\mathcal{R}^{i}$. Numbers between $R^{1}$ and
$O^{i}$ are indexes. Grey indexes denote the suffixes of $R^{i}$ that are not
included in the sparse suffix array $A$. (B) Detection of prMEMs in the
grammar level $1$. The dashed lines in $GLCP$ indicate the MEMs found by the
suffix-tree-based MEM algorithm, and the dashed arrows map the prMEMs to their
corresponding prMEM tuples. The $BWT$ shows the left context of the suffixes.
(C) The satellite data structures for the next iteration. The symbols in grey
are those that are ignored in the string sorting

###### Example 1

Computing prMEMs in level 1 (Figure 3) of the grammar of Figure 1. The
simulation of the suffix-tree-based algorithm reported the MEMs
$(A[8]=26,A[9]=15,3)$ and $(A[8]=26,A[10]=21,3)$ in $R^{1}$ (dashed lines in
$GLCP$). These pairs correspond to the occurrences $R^{1}[26]$, $R^{1}[15]$
and $R^{1}[21]$ of gta. The operation $parent$ gives the nonterminals
$5=parent(26)$, $3=parent(15)$ and $4=parent(21)$, which are stored in the
prMEM tuples and marked with dashed arrows. We compute the offsets $1,2$
within the left prMEM tuple $(5,3,1,2,3)$ by accessing the positions
$1=O[26]+1$ and $2=O[15]+1$, respectively. These offsets are the relative
positions of the MEM within $efexp(5)$ and $efexp(3)$, respectively. The last
element of the tuple, $3$, comes from the triplet reported by the suffix-tree-
based MEM algorithm and corresponds to the length $GLCP[9]=3=|\texttt{gta}|$
of the MEM. We compute the information of the right prMEM tuple $(5,4,1,2,3)$
in the same way but using its corresponding positions $A[8]=26$ and
$A[10]=21$.

Figure 4: Second iteration to find prMEMs with $\tau\geq 3$ in the grammar of
Figure 1. (A) Data structures to compute the prMEMs. The $GLCP$ values are
already transformed to encode the longest common prefixes between $rexp$
expansions of the $R^{i}$ suffixes in $A$. The $BWT$ column shows the left
context of each $R^{i}$ suffix in $A$. The dashed arrows indicate the steps to
get the left boundary of the prMEM. (B) Encoding of $R^{2}$ and $O^{2}$. The
indexes in grey indicate the suffixes of $R^{i}$ that are not in $A$. (C)
Offset sequence in $O$ for the nonterminals $6$ and $7$.

###### Example 2

Computing prMEMs in level 2 (Figure 4) of the grammar of Figure 1. The suffix-
tree-based algorithm reported the triplet $(A[3]=7,A[4]=3,4)$ as a MEM (dashed
line in $GLCP$). The corresponding suffixes $R^{i}[A[3]=7..]=32\$\\#$ and
$R^{i}[A[4]=3..]=432$ do not share a prefix, but $GLCP$ indicates their $rexp$
expansions $rexp(32\$\\#)=\texttt{agtacc\$\\#}$ and
$rexp(432)=\texttt{agtagtacc\$\\#}$ do share a prefix of length $GLCP[4]=4$.
Still, the MEM is incomplete as the match can be extended to the left. To find
the left-extension, we access the symbols $R^{2}[A[3]-1=6]=4$ and
$R^{2}[A[4]-1=2]=1$ and compute the longest common suffix of their $lexp$
expansions. This step require us to visit $P^{1}[4]=5$ and $P^{1}[1]=2$, and
compute $lcs^{1}(4,1)=rmq(LCS^{1},2,5)=1$ (underlined value in $LCS^{1}$). We
add $1$ to the current MEM length to get the final length $\ell=4+1=5$
(rightmost value in the prMEM tuple). We compute $6$ and $7$ in the prMEM
tuple as before, i.e., via $parent$. The values $3$ and $0$ indicate the
positions of the MEM within $efexp(6)$ and $efexp(7)$. As before, we use $O$
to get these values but also subtract the length of the left extension. Thus,
$3=O[A[3]]-1+1$ and $0=O[A[4]]-1+1$. Notice that the offset $0\leq 1$
indicates that the MEM starts before the relative position of $efexp(7)$
within $lexp(7)$. Figure 4C depicts this idea about the offset.

##  Appendix 0.B Simplifying the grammar

The simplification consists in recursively removing from $R$ each nonterminal
$X\in V$ that has one occurrence and leaving just its replacement. Suppose the
left-hand side of $X\rightarrow F$ occurs only once in $R$ in the string for
the rule $X^{\prime}\rightarrow AXZ$. Then, we remove $F$ from $R$ and
reinsert it in the area of $AXZ$ to replace the symbol $X$ (i.e., the right-
hand side for $X^{\prime}$ becomes $AFZ$). This process is recursive because
we also simplify the sequence of $F$. Additionally, we update the $efexp$
expansions stored in $O$. The idea is similar to what we did in $R$: the value
$e_{X}$ in $X^{\prime}\rightarrow e_{A}e_{X}e_{Z}\in\mathcal{O}$ associated
with $X$’s occurrence in $X^{\prime}\rightarrow AXZ$ is now replaced by the
offset sequence in $O$ for the string $F$. We also need to update $F$’s offset
sequence by adding $efexp(A)$ to its values. The simplification requires
renaming the nonterminals so they form a contiguous range of values again.

We keep track of the changes we made during the simplification to update the
values in $\mathcal{L}$. In particular, we create a vector $K[1..g]$ storing
for each $X\rightarrow F$ the nonterminal $K[X]=X^{\prime}\in V$ that now
encloses the simplified version of $F$. Let $X^{\prime}\rightarrow
A_{s}F_{s}Z_{s}$, with $A_{s},F_{s},Z_{s}\in(\Sigma\cup V)^{*}$ be the
simplified rule for $X^{\prime}$. Another vector $E$ stores in $E[X]=|A_{s}|$
the number of symbols in the prefix $A_{s}$ preceding $F_{s}$. Now we scan
$\mathcal{L}$, and for each tuple $(X,Y,o_{X},o_{Y},\ell)$, we update the
symbols $X=K[X],Y=K[Y]$, and their corresponding offsets
$(o_{X}=o_{X}+O[E[X]],o_{Y}=o_{Y}+O[E[Y]])$. After simplifying the grammar and
update $\mathcal{L}$, we get rid of $E$ and $K$.