# Combinatorial Group Testing in Presence of Deletions

Venkata Gandikota
EECS, Syracuse University
Syracuse, NY
<EMAIL_ADDRESS>
&Nikita Polyanskii
IOTA Foundation
Berlin, Germany
<EMAIL_ADDRESS>&Haodong Yang
EECS, Syracuse University
Syracuse, NY
<EMAIL_ADDRESS>
###### Abstract

The study in group testing aims to develop strategies to identify a small set
of defective items among a large population using a few pooled tests. The
established techniques have been highly beneficial in a broad spectrum of
applications ranging from channel communication to identifying
COVID-19-infected individuals efficiently. Despite significant research on
group testing and its variants since the 1940s, testing strategies robust to
deletion noise have yet to be studied. Many practical systems exhibit deletion
errors, for instance, in wireless communication and data storage systems. Such
deletions of test outcomes lead to asynchrony between the tests, which the
current group testing strategies cannot handle. In this work, we initiate the
study of non-adaptive group testing strategies resilient to deletion noise. We
characterize the necessary and sufficient conditions to successfully identify
the defective items even after the adversarial deletion of certain test
outputs. We also provide constructions of testing matrices along with an
efficient recovery algorithm.

_K_ eywords Group Testing $\cdot$ Edit Distance $\cdot$ Deletion Distance
$\cdot$ Disjunct Matrix

##  1 Introduction

The central question in combinatorial group testing was initially proposed by
Dorfman [Dor43] to devise screening strategies for the identification of
syphilis-infected soldiers during World War II. The main observation that
fueled this area of research is that pooling blood samples from different
soldiers together can provide a significant reduction in the number of blood
tests required to identify a few infected individuals. A pooled test
containing blood samples from different individuals will be positive if and
only if it contains at least one infected sample. Hence, compared to
individual testing where a negative test just confirms a single healthy
person, a single pooled test would mark all the sampled individuals within the
test as healthy. Since then, group testing techniques have found applications
in a wide range of domains such as industrial quality assurance [SG59], DNA
sequencing [PL94], molecular biology [Mac99, STR03], wireless communication
[Wol85, Ber+84, LG08], data compression [HL02, EM14], pattern matching
[Cli+07], secure key distribution [SVW00], network tomography [Ma+14, Che+12],
efficient data analysis [ECS21, CM05] and more recently in COVID-19 testing
protocols [WGV23, Gho+21].

Formally, the goal in group testing is to identify a small unknown set $S^{*}$
of $k(\ll n)$ defective items among a population of $n$ using a few grouped
tests. The outcome of a pooled test corresponding to a subset $P\subseteq[n]$
of items is positive if it contains at least one defective element, i.e.,
$S^{*}\cap P\neq\emptyset$. Theoretical research in group testing has focused
on the following central problem: _How many pooled tests
$\\{P_{1},\ldots,P_{m}\\}\subseteq[n]$ are required to recover $S^{*}$ from
the test outcomes of the form $\mathbbm{1}_{S^{*}\cap P\neq\emptyset}$?_ The
algorithmic question is then to efficiently decode to recover the identities
of all the infected individuals, $S^{*}$ given all the test outcomes.

Decades of research have helped us answer these questions in group testing and
many of its variants such as _probabilistic group testing_ [Che+11, AJS+19],
where the possible set of defectives have an associated prior, _quantitative
testing_ [Hao90, Gar+92, Dya+13, Ina+19] where the test outcome is non-binary
such as $|S^{*}\cap P|$, and _constrained group testing_ [Che+12, Gan+19,
IKÖ19, Aga+20] where the allowable tests have some constraints on them. See
[Dya14, Mal13, AJS+19, ND00, CH08] for excellent surveys on established group
testing techniques.

Our focus in this work is on _combinatorial group testing_ (CGT), where the
set of defectives can be any arbitrary $k$-subset of $[n]$. This worst-case
model is known to be equivalent to probabilistic group testing with a uniform
prior [AJS+19]. Furthermore, we will restrict our attention to non-adaptive
tests, where the pooling strategy is fixed in advance. This is in contrast to
adaptive testing, where each subsequent test is designed after seeing the
previous test outcomes. Non-adaptive tests are important in practice as they
allow independent parallel testing thereby significantly speeding up the
detection process. It is, by now, folklore that $\Omega(k^{2}\log n/\log k)$
non-adaptive tests are required for the exact recovery of the defectives in
this model [Für96, Rus94]. Pooling strategies based on disjunct matrices
enable efficient recovery using $O(k^{2}\log n)$ non-adaptive tests in $O(mn)$
time [DHH00, DR82]. Several recent works have also devised super-efficient
sublinear time algorithms that run in $O(m)$ time [INR10, CN20].

In practice, we observe that the test outcomes are often noisy. This noise can
manifest in various forms, however, the most commonly encountered noise model
in group testing is the bit-fip noise, where the binary test outcome can be
flipped from a positive to a negative or vice-versa. The bit-flip noise model
in group testing has been well-understood in both random [AS12, Cha+11, AS09,
Maz16, Cai+13] and adversarial [Che09, NPR11, LW21] settings. In particular,
the results of [Che09] establish bounds on the maximum fraction of tolerable
false positives and false negatives in the test outcomes for exact and
approximate recovery, and also devise pooling strategies robust to such
errors.

Despite decades of intense research in group testing, other noise models such
as deletion noise are not well-understood. The problem is quite surprisingly
unexplored as deletion errors are known to be prevalent in many applications
such as wireless communications [CWH20], and data storage [CSS21, Che+20]
where group testing techniques are widely used. In the deletion noise model,
certain test outputs are deleted which shifts the outcomes, thereby causing
asynchrony between the devised tests and their results. Note that deletion
errors are in general more difficult to handle than bit-flip errors since even
one deletion out of $m$ tests can be equivalent to $O(m)$ bit flips in the
first $m-1$ tests. For instance, if the true output sequence of $m$ tests is
given by $(1,0,1,0,\ldots,1)$, where $1$ denotes a positive outcome, and $0$
denotes a negative output, then deleting the first test outcome will result in
an $m-1$ length test output sequence $(0,1,0,1,\ldots,1)$ which has a large
Hamming distance from the true outputs. The main difficulty in recovering
$S^{*}$ from deletion-inflicted test outputs stems from this mismatch between
the tests and their true outcomes. Through this work, our aim is to enhance
our understanding of noise-resilient group testing under such deletion errors.

Let us represent the set of $m$ tests as a binary testing matrix
$A\in\\{0,1\\}^{m\times n}$, where each row indicates the set of elements
pooled together in a particular test. We start by characterizing the necessary
and sufficient conditions on the testing matrix for recovery in the presence
of deletion noise. The necessary conditions are established by generalizing
the notion of separable matrices – the necessary conditions for exact recovery
in noiseless group testing. Specifically, to be able to distinguish between
any two distinct sets of defectives, we need their test outcomes to be
different even after some $\Delta$ deletions. This leads to the definition of
a _deletion-separable matrix_ that also provides a trivial lower bound on the
number of required tests. However, the best-known decoding algorithm given
test outcomes with respect to a deletion separable matrix, resorts to a brute
force search which is extremely inefficient. In search of an efficient
decoding algorithm, we define a sufficient condition on the testing matrix,
again taking inspiration from the noiseless group testing literature, called
_deletion-resilient disjunct matrices_. Furthermore, we provide randomized
construction of deletion-disjunct matrices, and also devise an efficient
decoding algorithm.

###  1.1 Related Work

Group testing and many of its variants are very well-studied and span a long
list of excellent works. Here we survey the most relevant works on non-
adaptive combinatorial group testing.

In the noiseless setting, an exact set of $k$ out of $n$ defectives can be
recovered using separable matrices [DHH00]. The columns of these matrices form
a binary superimposed code [Dya+13] that ensures that the OR -sum of any $k$
codewords are unique. It is well-known [Für96] that for $n$ such codewords to
exist, the code length has to be at least $m=\Omega(k^{2}\log n/\log k)$. A
disjunct matrix is another characterization of testing matrices that enables
efficient recovery of the defectives in the noiseless setting. The columns of
such matrices form a $k$-cover-free family. This property guarantees that the
OR  sum of any $k$ columns is not covered by any other column. Various
constructions of disjunct matrices have been proposed in the literature [KS64,
PR08, Ina+19]. A simple Bernoulli matrix with $m=O(k^{2}\log n)$ rows is known
to be $k$-disjunct with high probability [Dya14]. The first explicit
constructions based on Reed-Solomon codes were proposed by [KS64] that contain
$m=O(k^{2}\log^{2}n)$ rows. The construction is based on concatenated codes
that use Reed-Solomon codes (or any MDS code) of an appropriate rate as the
inner code and a disjunct matrix (in particular, the construction uses the
Identity matrix which is a trivial disjunct matrix) to obtain another disjunct
matrix with better parameters. This Kautz-Singleton construction paved the way
for further explicit constructions of disjunct matrices and some of their
variants using different inner code properties. For instance, [PR08] construct
disjunct matrices with $m=O(k^{2}\log n)$ with codes at Gilbert-Varshamov
bound, and [INR10] construct sublinear time decodable disjunct matrices with a
similar number of rows using list decodable codes.

The most notable of these constructions, closely related to this work include
the results of [Che09], which constructs explicit testing matrices resilient
to bit-flip errors. Their results are a blend of both positive and negative
notes. In particular, the author shows that it is impossible to exactly
recover the defectives set in the presence of large errors. However, a near-
exact recovery of the defectives can be done even with a large number of
false-positive outcomes. The construction again uses a Kautz-Singleton-like
construction with a slight variant of list recoverable codes as inner codes to
obtain noise-resilient testing matrices with $O(d\log n)$ rows.

In this work, we study the construction of testing matrices and exact recovery
algorithms that are resilient to deletion errors. To the best of our
knowledge, deletion errors have not yet been explored in the context of group
testing. However, some related areas of research such as channel communication
[HRS19, GL16, HS17], DNA storage [Che+20, DOS17, GSZ22], and compressive
sensing [YPT21, PWT21] have addressed such noise models.

Following the prior works on exact recovery in group testing, we require
superimposed codes that are also robust to deletion noise. The OR -sums of
these codewords while satisfying the distinctness conditions, should also be
uniquely identified from any of its $m-\Delta$ length subsequences to tolerate
$\Delta$ deletions. This latter condition can be enforced through the
application of deletion codes that have received significant attention in
coding theory literature since the seminal works of Levenshtein, Varshamov,
and Tenengolts [Lev+66, VT65]. Since then multiple works have generalized the
construction to obtain binary deletion codes of size $n$ and length $m$ such
that $n=\Theta(2^{m}/m^{k})$ and can tolerate up to some fixed constant $k$
bits of deletions [Slo00, SGB20, Mit09]. In the high-noise regime, almost
optimal constructions with $m$ approaching $O_{k}(\log n)$ are known [SZ99,
GL16, GW17]. These codes are defined over a slightly larger alphabet and then
converted to a binary alphabet by using the powerful technique of code
concatenation. More recently, codes using synchronization strings were
introduced by [HS17] that allow a black-box conversion of any error-correcting
code to deletion code by using efficient indexing schemes.

To design deletion-resilient superimposed codes, we will require a handle on
the edit distance between OR -sum of distinct sets of binary vectors. The main
challenge here arises from the shifts in vectors introduced by deletions which
makes deletion errors much harder to handle. We circumvent this issue by
defining a suitable sufficient condition on the testing matrix that is not
only satisfied by certain matrices with few rows but also facilitates
efficient decoding.

###  1.2 Notation

For any non-negative integer $n$, let $[n]:=\\{1,\ldots,n\\}$. For any vector
$v\in\mathbb{R}^{n}$, let $\textsc{supp}(v)\subseteq[n]$ denote the set of
indices of non-zero entries of $v$. Let $\textsc{wt}(v)$ denote the number of
non-zero entries in $v\in\mathbb{R}^{n}$, also called its Hamming weight. Let
$v[i]$ denote the $i$-th entry of $v$. For $a<b$, we let $v[a:b]$ to denote
the $b-a+1$-length vector $(v[a],v[a+1],\ldots,v[b])^{T}$ Also, for any set of
indices $S\subseteq[n]$, let $v_{\bar{S}}\in\mathbb{R}^{n-|S|}$ denote the
vector obtained by deleting the indices in $S$ from $v$. Let $0^{n}$ (and
respectively $1^{n}$) denote a length-$n$ vector with all $0$s (respectively
$1$s).

For any two binary vectors $u,v$ of length $n$, let us denote their
coordinate-wise OR by $u\vee v$. We will interchangeably use binary vectors
$v\in\\{0,1\\}^{n}$ as indicators of sets over $[n]$. Therefore, for any two
binary vectors, $u,v$ of length $n$, $u\cup v$ will denote the binary
indicator vector of the union of the sets indicated by $u$ and $v$, equivalent
to $u\vee v$. For binary vectors $a,b\in\\{0,1\\}^{n}$, we say $a\leq b$ if
$a_{i}\leq b_{i}$ for every $i\in[n]$.

For any matrix $A\in\mathbb{R}^{m\times n}$, let $A^{i}$ be its $i$-th row,
and let $A_{j}$ denote its $j$-th column. The $(i,j)$-th entry of $A$ is
represented as $A_{j}[i]$, $A^{i}[j]$, or $A[i,j]$ depending on context.

###  1.3 Setup

We consider the problem of designing pooling strategies that will enable the
recovery of all $k$ defective items from a population of $n$ items using a
small number of pooled tests in the presence of deletion noise.

Let $x^{*}\in\\{0,1\\}^{n}$ be the indicator of ground truth defectives such
that $\textsc{wt}(x^{*})\leq k$. A group test, denoted by
$\textsc{Test}(a,x^{*})$, corresponds to testing if the set of elements
indicated by the pooling vector $a\in\\{0,1\\}^{n}$ contains a defective or
not. The outcome of such a group test is $1$ if
$\textsc{supp}(a)\cap\textsc{supp}(x^{*})\neq\emptyset$, and $0$ otherwise.
Equivalently, the test outcome is given as
$\textsc{Test}(a,x^{*})=\bigvee_{i\in\textsc{supp}(x^{*})}a_{i}$. Let
$y:=\textsc{Test}(A,x^{*})\in\\{0,1\\}^{m}$ denote the outcomes of $m$ group
tests with pooling vectors represented as the rows of the binary matrix
$A\in\\{0,1\\}^{m\times n}$. In other words,
$y:=\bigvee_{i\in\textsc{supp}(x^{*})}A_{i}$ is the OR -sum of upto $k$
columns of $A$.

Our goal is to design a testing matrix $A\in\\{0,1\\}^{m\times n}$ with the
fewest possible rows that facilitates efficient recovery of $x^{*}$ given
$\tilde{y}\in\\{0,1\\}^{\tilde{m}}$ ($m-\tilde{m}\leq\Delta$) which is a
corrupted version of $y=\textsc{Test}(A,x^{*})$ after at most $\Delta$
arbitrary deletions. For shorthand, we use $\tilde{y}=\textsc{corr}(y,\Delta)$
to denote the deletion corrupted test outcomes. We will assume the knowledge
of both $k$, and $\Delta$. An upper bound on these quantities also suffices
for the purpose.

###  1.4 Preliminaries

The following matrices are used for the recovery of defectives in noiseless
group testing literature.

######  Definition 1 (Separable Matrix).

A binary matrix $A\in\\{0,1\\}^{m\times n}$ is a $k$-separable matrix if the
OR -sum of any two subsets $S_{1},S_{2}\subseteq[n]$ of up to $k$ columns is
distinct,

$\bigvee_{i\in T_{1}}A_{i}\neq\bigvee_{i\in T_{2}}A_{i}$

It is well-known that if the testing matrix $A$ is $k$ separable, then it can
identify up to $k$ defective elements. However, to enable an efficient
decoding algorithm, a $k$-disjunct matrix is used.

######  Definition 2 (Disjunct Matrix).

A binary matrix $A\in\\{0,1\\}^{m\times n}$ is a $k$-disjunct matrix if for
any set of $k+1$ columns, indexed by $\\{i_{0},i_{1},\ldots,i_{k}\\}$,
$A_{i_{0}}$ is not contained in the OR -sum of other columns,

$A_{i_{0}}\not\leq\bigvee_{j=1}^{k}A_{i_{j}}.$

The two above-defined types of matrices are known to be essentially
equivalent. It is trivial to see that a $k$-disjunct matrix is also a
$k$-separable matrix. However, a $k$-separable matrix is also a $k-1$-disjunct
matrix.

The decoding algorithm using a disjunct matrix is presented in Algorithm 1.
Here given access to $y=\textsc{Test}(A,x^{*})$, the algorithm runs in $O(mn)$
time to recover $x^{*}$ exactly.

Input: Binary vector $y=\textsc{Test}(A,x^{*})\in\\{0,1\\}^{m}$

1:$\hat{x}=[n]$

2:for each test $i\in[m]$ do

3: if $y_{i}==0$ then

4: $\hat{x}\rightarrow\hat{y}\setminus\\{j\in[n]|A_{i,j}=1\\}$

5: end if

6:end for

7:Return $\hat{x}$

Algorithm 1 Disjunct Matrix Decoding

##  2 Our Results

We start by extending the techniques from noiseless group testing. Our first
result establishes a necessary condition on the testing matrix $A$ for the
recovery of $x^{*}$ from group tests with at most $\Delta$ deletions. To state
the result, we first need the following definitions:

######  Definition 3.

(Deletion distance) The deletion distance $d_{del}(x,y)$ between two strings
$x$ and $y$ of length $n$ is the maximum number of deletions $d$ such that any
$(n-d)$-length subsequences $x^{\prime}$ of $x$ and $y^{\prime}$ of $y$ are
distinct.

Note that deletion distance is equivalent to edit distance with only
deletions. Therefore, it follows that $d_{del}(x,y)=n-\text{lcs}(x,y)-1$,
where $\text{lcs}(x,y)$ is the length of a longest common subsequence of $x$
and $y$. For example, let $x,y\in\\{0,1\\}^{6}$, $x=[0,1,0,1,0,0]^{T}$ and
$y=[0,0,0,1,1,0]^{T}$. The deletion distance $d_{del}(x,y)=1$. The longest
common subsequence is $[0,0,0,0]^{T}$ or $[0,0,1,0]$ or $[0,1,1,0]^{T}$.

Similar to the noiseless group testing setting, we establish the necessary
conditions on $A$ based on separable matrices that ensure that the test
outcomes corresponding to any two distinct sets of defectives are different.

######  Definition 4 ($(k,\Delta)$-deletion separable matrix).

We call a matrix $A\in\\{0,1\\}^{m\times n}$ to be $(k,\Delta)$-deletion
separable matrix if the OR -sum of any two distinct subsets
$S_{1},S_{2}\subseteq[n]$ of up to $k$ of its columns has a deletion distance
of at least $\Delta$

$d_{del}(\bigvee_{i\in S_{1}}A_{i},\bigvee_{i\in S_{2}}A_{i})\geq\Delta.$

Note that $(k,\Delta)$ \- deletion separable matrices are necessary for the
unique recovery of the defective set after $\Delta$ deletions. Otherwise,
there will exist two distinct sets of defectives that will have the same test
outcomes after $\Delta$ deletions, and therefore we cannot distinguish between
them. This observation gives us a trivial lower bound established using a
lower bound on the number of rows in $k$-separable matrices.

######  Theorem 5.

Let $A\in\\{0,1\\}^{m\times n}$ be a $(k,\Delta)$ \- deletion separable
matrix, then

$m=\Omega(k^{2}\log n/\log k+\Delta)$.

The proof follows from a straightforward observation that $A$, even after the
deletion of any set of $\Delta$ rows is a $k$-separable matrix. Therefore, we
get a lower bound of $m-\Delta\geq\Omega(k^{2}\log n/\log k)$ from the results
of [Für96].

The deletion separable condition is also sufficient for recovery, albeit with
an inefficient brute-force decoder. In particular, an upper bound on the
number of tests sufficient for exact recovery can be obtained using a
randomized construction of $(k,\Delta)$ \- deletion separable matrix. However,
the decoding algorithm must do a brute-force search over all $O(\binom{n}{k})$
sets to recover the ground truth $x^{*}$. Instead, we show that a trivial
construction based on replicating $k$-disjunct matrices will give us a
$(k,\Delta)$-deletion separable matrix with an efficient decoder (Section 3).

######  Lemma 6.

There exists a $(k,\Delta)$ \- deletion separable matrix
$A\in\\{0,1\\}^{m\times n}$ with $m=O(\Delta\cdot k^{2}\log{n})$.

The repetition essentially ensures that the outcomes corresponding to the
underlying disjunct matrix can be recovered even after $\Delta$ deletions. The
decoding algorithm then simply uses these outcomes to recover the ground
truth. The algorithm described in Section 3 runs in time $O(mn/\Delta)$.

Note that the upper bound on the number of tests established in Lemma 6 is
significantly larger than the lower bound from Theorem 5. In pursuit of a
better upper bound, we will establish alternate sufficient conditions on $A$
for the exact recovery of $x^{*}$. We start by defining the following
asymmetric version of deletion distance.

######  Definition 7 (Asymmetric deletion distance).

The asymmetric deletion distance $d_{adel}(x,y)$ between two strings $x$ and
$y$ of length $n$ is the maximum number of deletions $d$ such that for any
$(n-d)$-length subsequences $x^{\prime}$ and $y^{\prime}$ of $x$ and $y$ there
exists a position $i$ such that $x^{\prime}_{i}=1$ and $y^{\prime}_{i}=0$.

Note that the asymmetric deletion distance is stronger than the notion of
deletion distance. It not only ensures that the deletion distance between $x$
and $y$ is larger than $\Delta$ but also guarantees the existence of a
position $i\in[n-\Delta]$ in every substring $x^{\prime}$ and $y^{\prime}$ of
$x$ and $y$ respectively where $x^{\prime}_{i}>y^{\prime}_{i}$. We will call
such an index $i$ the position of a $1-0$ match in $(x^{\prime},y^{\prime})$.
For example, let $x,y\in\\{0,1\\}^{7}$, $x=[1,0,1,1,0,1,1]^{T}$ and
$y=[0,0,0,0,1,0,0]^{T}$. The asymmetric deletion distance $d_{adel}(x,y)=2$.
Since for any 4-length subsequence, $x^{\prime}$ and $y^{\prime}$,
$x^{\prime}$ at least has two $1$, and $y^{\prime}$ at most has one $1$. For
3-length subsequence $x^{\prime}$ and $y^{\prime}$, both can be $[0,0,1]^{T}$
and there is no $1-0$ match in $(x^{\prime},y^{\prime})$.

Inspired by works on noiseless group testing, we now define the following
sufficient condition on $A$ that enables recovery of $x^{*}$ with
significantly fewer tests, thereby getting us closer to the known lower bound.

######  Definition 8 ($(k,\Delta)$-deletion disjunct matrix).

We call a matrix $A\in\\{0,1\\}^{m\times n}$ to be $(k,\Delta)$-deletion
disjunct matrix if for any set of $k+1$ columns
$A_{i_{0}},A_{i_{1}},\ldots,A_{i_{k}}$ the asymmetric deletion distance
between $A_{i_{0}}$ and $\vee_{s=1}^{k}A_{i_{s}}$ is at least $\Delta$,

$d_{adel}(A_{i_{0}},\bigvee_{s=1}^{k}A_{i_{s}})\geq\Delta.$

We remark that deletion disjunct matrices are sufficient for recovery since it
is also deletion separable matrix. This fact is formalized below.

######  Lemma 9.

A $(k,\Delta)$-deletion disjunct matrix is also a $(k,\Delta)$-deletion
separable matrix.

###### Proof.

Suppose the binary matrix $A\in\\{0,1\\}^{m\times n}$ is a
$(k,\Delta)$-deletion disjunct matrix but is not $(k,\Delta)$-deletion
separable. From the definition of a deletion separable matrix, there exist two
distinct subsets of $k$ columns $S_{1},S_{2}\in[n]$ of $A$ such that
$d_{del}(\vee_{i\in S_{1}}A_{i},\vee_{j\in S_{2}}A_{j})<\Delta$.

Therefore, for some sets of $\Delta$ deletions indexed by rows
$T_{1},T_{2}\subseteq[m]$ , $|T_{1}|=|T_{2}|=\Delta$, the vectors $\vee_{i\in
S_{1}}A_{i}$, and $\vee_{i\in S_{2}}A_{i}$ become indistinguishable after
deleting entries from $T_{1}$ and $T_{2}$ respectively, i.e.,

$(\bigvee_{i\in S_{1}}A_{i})_{\overline{T_{1}}}=(\bigvee_{j\in
S_{2}}A_{j})_{\overline{T_{2}}}.$

Therefore, $\forall i\in S_{1}$,
$\textsc{supp}((A_{i})_{\overline{T_{1}}})\subseteq\textsc{supp}((\bigvee_{j\in
S_{2}}A_{j})_{\overline{T_{2}}})$. In other words,
$(A_{i})_{\overline{T_{1}}}\leq(\bigvee_{j\in
S_{2}}A_{j})_{\overline{T_{2}}}$, and hence, there is no $1-0$ match between
$(A_{i})_{\overline{T}_{i}}$ and $(\vee_{j\in
S_{2}}A_{j})_{\overline{T}_{2}}$. Therefore, $d_{adel}(A_{i},\vee_{j\in
S_{2}}A_{j})\leq\Delta$, which gives a contradiction to the assumption that
$A$ is a $(k,\Delta)$-deletion disjunct matrix. ∎

We can show that a random Bernoulli matrix is deletion disjunct with high
probability if $m=O(k^{2}\log n+\Delta k)$, thereby proving the existence of
such matrices with an almost optimal number of rows provided $\Delta\leq
c\cdot k\log n$.

######  Theorem 10.

There exists a $(k,\Delta)$-deletion disjunct matrix with $m=O(k^{2}\log
n+\Delta k)$ rows.

We not only get closer to the established lower bound but also get an
efficient decoding algorithm to recover $x^{*}$. In particular, we show the
existence of a decoding algorithm that is better than the naive brute force
algorithm and runs in time $O(nm)$.

######  Theorem 11.

Let $A\in\\{0,1\\}^{m\times n}$ be a $(k,\Delta)$-deletion disjunct matrix.
There exists a decoding algorithm that runs in time $O(nm)$ and recovers
$x^{*}$ given $\tilde{y}=\textsc{corr}(\textsc{Test}(A,x^{*}),\Delta)$.

We first present a simple algorithm that does better than a naive brute force
algorithm and runs in time $O(nm^{\Delta+1})$ (see Algorithm 4). While this
algorithm can efficiently handle a small number of deletions
($\Delta=\Omega(1)$), the exponential dependence on $\Delta$ makes it
prohibitive for larger corruptions. We, therefore, improve upon the algorithm
using Algorithm 5 that reduces the runtime to $O(nm)$.

Organization:  We present the trivial construction of deletion separable
matrices (Lemma 6) and its associated efficient decoder in Section 3. The
results on deletion disjunct matrices (Theorem 10, Theorem 11) are presented
in Section 4.

##  3 Construction of $(k,\Delta)$ \- Deletion Separable Matrix & Decoding

We now present our construction of the deletion separable matrices. For this,
we use disjunct matrices that have been classically used in noiseless group
testing. Specifically, we replicate a disjunct matrix multiple times to make
the outcomes resilient to deletion noise.

###### Proof of Lemma 6.

Let $B\in\\{0,1\\}^{m^{\prime}\times n}$ be a $k$-disjunct matrix with
$m^{\prime}$ rows. Let $A$ be the matrix obtained by repeating each row of
$B$, $\Delta+1$ times. In particular, for each $j\in[m^{\prime}]$,

$A_{k}=B_{j}\text{ for all }k\in[(j-1)(\Delta+1)+1,j(\Delta+1)]$ (1)

Since constructions of $k$-disjunct matrices $B$ with $O(k^{2}\log n)$ rows
exist [PR08], we can obtain the matrix $A$ with $m=O(\Delta k^{2}\log n)$
rows.

We now show that the matrix $A$ obtained as described above is indeed a
$(k,\Delta)$-deletion separable matrix. First, note that the matrix $B$ is a
$k$-separable matrix since every disjunct matrix is also separable. Therefore,
for any two subsets $S_{1},S_{2}\subseteq[n]$ of $k$ columns of $B$,
$\vee_{i\in S_{1}}B_{i}\neq\vee_{i\in S_{2}}B_{i}$. In other words, without
loss of generality, there exists an index $\ell\in[m^{\prime}]$ such that
$(\vee_{i\in S_{1}}B_{i})[\ell]=0$ and $(\vee_{i\in S_{2}}B_{i})[\ell]=1$.
Therefore, by the construction of matrix $A$, the $\ell$-th block of the
vectors $y_{1}:=(\vee_{i\in S_{1}}A_{i})$, and $y_{2}:=(\vee_{i\in
S_{2}}A_{i})$ will satisfy

$y_{1}[(\ell-1)(\Delta+1)+1:\ell(\Delta+1)]=0^{\Delta+1}\qquad
y_{2}[(\ell-1)(\Delta+1)+1:\ell(\Delta+1)]=1^{\Delta+1}.$

So on deleting any set of at most $\Delta$ entries of $y_{1}$ and $y_{2}$,
there will exist at least one index from the $\ell$-th block of $y_{1}$ and
$y_{2}$ that aligns and, therefore, will be unequal. So, the deletion distance
between $y_{1}$ and $y_{2}$ will be at least $\Delta$. ∎

###  3.1 Decoding Algorithm

Let $\tilde{y}=\textsc{corr}(y,\Delta)\in\\{0,1\\}^{m-\Delta}$ be the output
of the group tests $y=\textsc{Test}(A,x^{*})$ after $\Delta$ deletions, where
$A$ is the deletion separable matrix constructed above in Lemma 6.

The decoding algorithm to recover the underlying sparse vector $x^{*}$ from
corrupted test outcomes is presented in Algorithm 3. The algorithm proceeds in
two steps. In the first step, using a greedy approach, we reconstruct the
actual test outcomes, $y$, from the deletion corrupted one, $\tilde{y}$
(Algorithm 2). This recovery is possible due to the specific repetition
structure of the deletion separable matrix $A$ designed in the previous
section. Once we obtain the true test outcomes, we can recover $x^{*}$ using
the decoding algorithm for the disjunct matrix $B$, presented in Algorithm 1
for completeness.

The procedure Greedy Complete, presented in Algorithm 2, corrects the vector
$\tilde{y}$ to recover the actual test outcome vector $y$. A run of symbol $b$
(either $0$ or $1$) in $\tilde{y}$, of length $\ell$, is a substring of length
$\ell$ of $\tilde{y}$ that contains only $b$. The procedure extends each run
of a particular symbol $b\in\\{0,1\\}$ of length $\ell$ to a complete multiple
of $(\Delta+1)$. We now show that the vector returned by Greedy Complete is
$y$ if there are at most $\Delta$ deletions.

Input: Binary vector $\tilde{y}\in\\{0,1\\}^{m-\Delta}$, Block size $\Delta+1$

1:$\hat{y}=()$

2:for each run of symbol $b\in\\{0,1\\}$ of length $\alpha(\Delta+1)+\beta$ in
$\tilde{y}$, ($\alpha,\beta\in\mathbb{Z}$, $0\leq\beta\leq\Delta$) do

3: if $\beta==0$ then

4: Append a run of symbol $b$ of length $\alpha(\Delta+1)$ to $\hat{y}$

5: else

6: Append a run of symbol $b$ of length $(\alpha+1)(\Delta+1)$ to $\hat{y}$

7: end if

8:end for

9:Return $\hat{y}$

Algorithm 2 Greedy Complete

######  Lemma 12.

Let $\hat{y}$ be the output of Greedy Complete on input
$\tilde{y}=\textsc{corr}(y,\Delta)$, then $\hat{y}=y$.

###### Proof.

We prove this lemma by induction on the blocks of identical rows in $A$ that
have one-one correspondence with individual rows in $B$,
$m^{\prime}(=m/(\Delta+1))$.

Base case: $m^{\prime}=1$: In this case, note that length of $y$ is
$\Delta+1$, and $\tilde{y}$, WLOG is of length $1$. We now show that
$\hat{y}[i]=y[i]$ for each $i\in[1,\Delta+1]$. Since the first row of $B$ is
repeated $\Delta+1$ times in $A$, the first $\Delta+1$ test outcomes in $y$
are identical. Therefore, even after $\Delta$ deletions, one of the true
outcomes with the first row of $B$ is preserved in $\tilde{y}$. The algorithm,
therefore, reconstructs and returns $\hat{y}=y$.

Induction Hypothesis:  Let us assume the correctness of the algorithm, Greedy
Complete for up to the $t$-th block of $A$, i.e., $m^{\prime}\leq t$.

Induction step: Consider the true test output vector $y$ until the $t+1$-th
block of $A$. Let $\tilde{y}$ be a vector of length
$\ell:=(t+1)(\Delta+1)-\Delta$ obtained by deleting arbitrary $\Delta$ entries
of $y$. Let $\Delta_{1}$ denote the number of deletions in the first
$t(\Delta+1)$ entries of $y$. Define $p:=t(\Delta+1)-\Delta_{1}$. Then,
$\tilde{y}_{1}:=\tilde{y}[1:p]$ denotes the test outcomes from the first $t$
blocks of $A$, and $\tilde{y}_{2}:=\tilde{y}[p+1:\ell]$ are the outcomes from
the $t+1$-th block.

By induction hypothesis, $\hat{y}_{1}=\textsc{Greedy Complete}(\tilde{y_{1}})$
will be correctly computed and we have $\hat{y}_{1}=y[1:t(\Delta+1)]$. Also,
since all rows in the $t+1$-th block of $A$ are identical,
$\tilde{y}[p+1:\ell]=0^{\ell-p}$(or, $1^{\ell-p}$). Greedy Complete will
extend this run of $\ell-p$ $0$s (or 1s) to a length of $\Delta+1$ elements.
So, $\hat{y}_{2}=y[t(\Delta+1)+1:(t+1)(\Delta+1)]$. Combining the two parts,
the correctness of Greedy Complete follows. ∎

Once the actual test outcome vector $y=\textsc{Test}(A,x^{*})$ is recovered,
we can reconstruct $\textsc{Test}(B,x^{*})$ by removing the redundancy. The
ground truth defective status $x^{*}$ can then be obtained using any decoding
algorithm for disjunct matrices. These steps are listed in Algorithm 3.

Input: $k$-disjunct matrix $B\in\\{0,1\\}^{m^{\prime}\times n}$,

Matrix $A\in\\{0,1\\}^{m\times n}$ generated from $B$ as described in Equation
1

Corrupted output $\tilde{\mathbf{y}}:=\textsc{corr}(\mathbf{y},\Delta)$, where
$\mathbf{y}=\textsc{Test}(A,x^{*})$.

1:Let $\hat{y}:=\textsc{Greedy Complete}(y^{\prime},\Delta)$ $\triangleright$
Fix deletions greedily to recover $\textsc{Test}(A,x^{*})$

2:Let $\mathbf{y}^{\prime}=0^{m^{\prime}}$

3:for each $j\in[m/(\Delta+1)]$ do

4: $\mathbf{y}^{\prime}[j]=\hat{y}[j(\Delta+1)]$

5:end for$\triangleright$ Construct $\textsc{Test}(B,x^{*})$

6:$\hat{x}:=\textsc{Disjunct Matrix Decoding}(B,y^{\prime})$ $\triangleright$
See Algorithm 1

7:return $\hat{\mathbf{x}}$

Algorithm 3 Algorithm to recover the set of defectives

######  Theorem 13.

Let $A\in\\{0,1\\}^{m\times n}$ be the deletion separable matrix constructed
from a $k$-disjunct matrix $B$ as described in Lemma 6. Given
$\tilde{y}=\textsc{corr}(\textsc{Test}(A,x^{*}),\Delta)$, Algorithm 3 recovers
$x^{*}$ exactly in time $O(mn/\Delta)$.

###### Proof.

The correctness of Algorithm 3 follows from the correctness of Lemma 12 and
the decoding algorithm for noiseless group testing. The latter follows from
construction since $B$ is a $k$-disjunct matrix.

For the run-time analysis, note that Algorithm 2 runs in time $O(m)$, and the
column matching algorithm takes $O(m^{\prime}n)$ time. Therefore, Algorithm 3
runs in time $O(m+mn/\Delta)$. ∎

##  4 Deletion disjunct matrix & decoding

To get closer to the lower bounds, we will construct deletion disjunct
matrices that enable recovery of $x^{*}$ from fewer measurements. We will
consider random designs to obtain a $(k,\Delta)$-deletion disjunct matrix with
high probability.

###### Proof of Theorem 10.

Let $A\in\\{0,1\\}^{m\times n}$ be a random Bernoulli matrix where each entry
is set to $1$ independently with some probability $p>0$. We show that for an
appropriate value of $p$, and large enough $m$, $A$ will be a $(k,\Delta)$ \-
deletion disjunct matrix with high probability.

Recall that for any two vectors $v_{1},v_{2}\in\\{0,1\\}^{m-\Delta}$, we say
that a $1-0$ match occurs if there exists an index $i$ such that $v_{1}[i]=1$,
but $v_{2}[i]=0$. For a fixed set of $k+1$ columns indexed by $T\subset[n]$,
$|T|=k$, and $j\in[n]\setminus T$, and any two sets of $\Delta$ deletions
indexed by $S_{1},S_{2}\subseteq[m]$, $|S_{1}|=|S_{2}|=\Delta$, define a bad
event $E(T,j,S_{1},S_{2})$ to occur if there is no $1-0$ match between
$(A_{j})_{\overline{S_{2}}}$ and $(\vee_{i\in T}A_{i})_{\overline{S_{1}}}$.
Note that $A$ is not $(k,\Delta)$-deletion disjunct matrix if
$E(T,j,S_{1},S_{2})$ occurs for any set $T,j,S_{1},S_{2}$ since then,
$d_{adel}(A_{j},\vee_{i\in T}A_{i})<\Delta$. We will now bound the probability
of such bad events from occurring.

Observe from the independence of the matrix entries that for a fixed row,
$w\in[m-\Delta]$, the probability that a $1-0$ match does not occur is given
by $(1-(1-p)^{k}\cdot p)$. Therefore, for a fixed set of $T,j,S_{1},S_{2}$,
the event $E(T,j,S_{1},S_{2})$ occurs with probability $(1-(1-p)^{k}\cdot
p)^{m-\Delta}$.

Taking a union bound over all possible $\binom{n}{k}(n-k)$ choices of $T,j$
and $\binom{m}{\Delta}^{2}$ choices of $S_{1},S_{2}$, we get that the failure
probability is

$(1-(1-p)^{k}\cdot p)^{m-\Delta}{m\choose\Delta}^{2}\binom{n}{k}(n-k).$

Setting $p=1/k$, we get that the probability that $A$ is not a
$(k,\Delta)$-deletion disjunct matrix is

$\displaystyle p_{\text{fail}}$ $\displaystyle:=(1-(1-p)^{k}\cdot
p)^{m-\Delta}{m\choose\Delta}^{2}\binom{n}{k}(n-k)$
$\displaystyle\leq\left(1-(1-\frac{1}{k})^{k}\frac{1}{k}\right)^{m-\Delta}\left(\frac{em}{\Delta}\right)^{2\Delta}\left(\frac{en}{k}\right)^{k}(n-k)\quad(\text{Since,
}\binom{m}{\Delta}\leq(em/\Delta)^{\Delta})$ $\displaystyle\leq
exp\left(-\frac{(m-\Delta)}{10k}+2\Delta\log\frac{em}{\Delta}+k\log\frac{en}{k}+\log(n-k)\right),$

where the last inequality follows from using the standard approximations for
$e^{-2x}\leq(1-x)\leq e^{-x}$ for any $x\in(0,1/2)$. Therefore, if we set
$m=\tilde{O}\left(k^{2}\cdot\log{n}+\Delta\cdot k\right)$, where
$\tilde{O}(\cdot)$ hides $\log\log n$ and $\log k$ terms will ensure that with
probability $1-1/n$, $A$ will be $(k,\Delta)$-deleltion disjunct.

###  4.1 Decoding Algorithm

In this section, we will give a decoding algorithm to recover $x^{*}$ from
$\tilde{y}=\textsc{corr}(y,\Delta)$ using a $(k,\Delta)$-deletion disjunct
matrix that runs in time $O(nm\Delta)$. We first present a simple algorithm
that has a slightly degraded running time, which we improve later.

Consider Algorithm 4. We show that Algorithm 4 correctly decodes $x^{*}$ from
$\tilde{y}$, but runs in time $O(nm^{\Delta+1})$.

Input: $\mathbf{A}\in\\{0,1\\}^{m\times n}$ – $(k,\Delta)$-deletion disjunct
matrix

$\tilde{\mathbf{y}}=\textsc{corr}(\textsc{Test}(A,x^{*}),\Delta)\in\\{0,1\\}^{(m-\Delta)}$

1:Let $\hat{x}=1^{n}$

2:for each $j\in[n]$ do

3: if $\forall T\subseteq[m]$ with $|T|=\Delta-1$, $\exists i\in[m]\setminus
T$ such that $(A_{j})_{\overline{T}}[i]=1$ and $\tilde{y}_{i}=0$ then

4: Set $\hat{x}_{j}=0$

5: end if

6:end for

7:Return $\hat{x}$

Algorithm 4 Decode with Deletion Disjunct Matrix

######  Lemma 14.

Let $A\in\\{0,1\\}^{m\times n}$ be a $(k,\Delta)$-deletion disjunct matrix.
Then, Algorithm 4 runs in time $O(nm^{\Delta+1})$ and recovers $x^{*}$ given
$\tilde{y}=\textsc{corr}(\textsc{Test}(A,x^{*}),\Delta)$.

###### Proof of Lemma 14.

The algorithm relies on the observation that for $S=\textsc{supp}(x^{*})$, and
any $j\in[n]\setminus S$, $d_{adel}(A_{j},\vee_{i\in S}A_{i})\geq\Delta$. The
observation follows directly from the definition of $(k,\Delta)$-deletion
disjunct matrix. Therefore, the algorithm iteratively checks and rejects those
columns of $A$ whose asymmetric deletion distance from
$y(=\textsc{Test}(A,x^{*})=\vee_{i\in S}A_{i})$ is larger than $\Delta$. For
the check, the algorithm does a brute-force search over all possible deletions
$T$ of size $\Delta$ to find one set of deletions that has no $1-0$ match with
$\tilde{y}$. The non-existence of $1-0$ some $T$-deletions gives a certificate
that $j\in\textsc{supp}(x)$.

To prove the correctness of the algorithm, we show both directions – 1) If
$i\in\textsc{supp}(x^{*})$, then $\hat{x}_{i}=1$, and 2) If
$i\notin\textsc{supp}(x^{*})$, then $\hat{x}_{i}=0$

#### Case 1: ($i\in\textsc{supp}(x^{*})$):

For each $i\in\textsc{supp}(x^{*})$, we show that there always exists some set
of deletions indexed by $T$ such that there is no $1-0$ match between
$(A_{i})_{\overline{T}}$, and $\tilde{y}$. Therefore, the condition within the
If statement (Line 3 of Algorithm 4) is not satisfied for all subsets of
$\Delta$ deletions, and $\hat{x}_{i}$ remains $1$ as initialized.

Let $T^{*}$ denote the true set of $\Delta$ deletions that produce $\tilde{y}$
from $y$, i.e., $\tilde{y}=y_{\overline{T}^{*}}$. Since
$y=\vee_{j\in\textsc{supp}(x^{*})}A_{j}$, we know that there is no $1-0$ match
between $A_{i}$ and $y$, for any $i\in\textsc{supp}(x^{*})$. Therefore, for
the true set of deletions, $T^{*}$, there will not exist any $1-0$ match
between $(A_{i})_{\overline{T}^{*}}$ and $y_{\overline{T}^{*}}=\tilde{y}$.

#### Case 2: ($i\notin\textsc{supp}(x^{*})$):

The second part of the proof follows from the definition of a $(k,\Delta)$
deletion disjunct matrix. Since $A$ is $(k,\Delta)$-deletion disjunct matrix,
for every $i\notin\textsc{supp}(x^{*})$, we know that
$d_{adel}(A_{i},y)\geq\Delta$. Therefore, by definition, for any set of
$\Delta$ deletions $T_{1},T_{2}$, there will be a $1-0$ match between
$(A_{i})_{\overline{T}_{1}}$ and $y_{\overline{T}_{2}}$. In particular, for
$T_{2}=T^{*}$, the true set of deletions that produce $\tilde{y}$, there will
be a $1-0$ match between $(A_{i})_{\overline{T}_{1}}$ and $\tilde{y}$ for
every $T_{1}$. Therefore, the condition in If statement is satisfied, and
$\hat{x}_{i}$ is set to $0$ for every $i\notin\textsc{supp}(x^{*})$.

For the run-time analysis, note that the condition in the If statement checks
every possible set of $\Delta$ deletions for the existence of a $1-0$ match
with $\tilde{y}$. This takes $O(\binom{m}{\Delta}(m-\Delta))$. The Algorithm
further iterates over all $j\in[n]$. Therefore, Algorithm 4 runs in time
$O(nm^{\Delta+1})$. ∎

∎

We now address the main bottleneck in Algorithm 4 that stems from the search
for the certificate for containment in Line 3 of the algorithm. We provide an
alternate mechanism to speed up this search process in time $O(m\Delta)$
instead of $O(m^{\Delta+1})$.

Algorithm 5 Check Coverage

1:Binary vectors $\mathbf{y}$, $\mathbf{z}$, and integer $t$

2:True if there exists a vector $\mathbf{x}$ (obtained from $\mathbf{z}$ by
deleting at most $t$ symbols) such that $\mathbf{x}$ is covered by
$\mathbf{y}$, otherwise False.

3:$i\leftarrow 0$

4:$j\leftarrow 0$

5:while $i<\text{length}(\mathbf{y})$ and $j<\text{length}(\mathbf{z})$ do

6: if $\mathbf{y}[i]\geq\mathbf{z}[j]$ then

7: $i\leftarrow i+1$

8: $j\leftarrow j+1$

9: else

10: $j\leftarrow j+1$

11: $t\leftarrow t-1$

12: end if

13: if $t<0$ then

14: return False

15: end if

16:end while

17:if $i==\text{length}(\mathbf{y})$ then

18: return True

19:end if

20:return False

######  Lemma 15.

Given two binary vectors $y\in\\{0,1\\}^{m-t}$, $z\in\\{0,1\\}^{m}$, Algorithm
5 decides in time $O(m)$ if there exist some set of $t$ deletions in $z$ such
that $x\leq y$, where $x\in\\{0,1\\}^{m-t}$ is the substring of $z$ obtained
after deletions.

###### Proof of Lemma 15.

The algorithm, at a high level, iteratively looks for a violation for
coverage, i.e., an index $i$ such that $z_{i}\geq y_{i}$. Every time it
encounters a violation, the algorithm will delete that index from $z$. Observe
that only the $1$ entries are deleted from $z$. The algorithm returns a False
if it finds more than $t$ violations.

To prove the correctness of Algorithm 5, we have to show that the algorithm
accepts if and only if there exists a $x$, obtained from $z$ after at most $t$
deletions that can be covered by $y$.

One side of the statement follows trivially. Note that if the algorithm
accepts, then there exists an $x$ that can be covered by $y$ since the
algorithm constructs one such vector from $z$ with at most $t$ deletions.

The other side of the proof is a little more intricate. We must show that if
there exists a $x$ that can be covered by $y$, then the algorithm returns
True.

From the hypothesis, we know that there exists an $x$ that can be obtained
from $z$ after $t$ deletions such that $y\geq x$. Let
$s_{1},s_{2},\ldots,s_{t}$ be the indices of deletions in $z$ that produces
$x$. Let $r_{1},\ldots,r_{t}$ be the indices of deletions in $z$ made by the
algorithm to obtain $x^{\prime}$. Let us denote by $z^{(i)}$ the snapshot of
$z$ after deletions $s_{1},\ldots s_{i}$. Analogously, let $z^{\prime(i)}$ be
the state of $z$ after deletions $r_{1},\ldots,r_{i}$.

Let $\ell\in[t]$ be the first position of mismatch in the deletion sets, i.e.,
$r_{\ell}\neq s_{\ell}$, and $r_{i}=s_{i}$ for all $i<\ell$. Therefore, for
the first $\ell-1$ deletions, both the snapshot of $z$, $z^{(i)}$ and
$z^{\prime(i)}$ looks exactly the same for all $i<\ell$. Now consider the
following two cases:

1) $r_{\ell}<s_{\ell}$: Since Algorithm 5 deletes an element only when it
detects a violation (i.e., $z^{\prime}_{r_{\ell}}=1$ and corresponding
$y_{r_{\ell}-\ell+1}=0$), the deletions $s_{\ell},\ldots,s_{t}$ will fail to
remove this violation if $s_{\ell}>r_{\ell}$. Therefore, $x=z^{(t)}$ is not
covered by $y$, thereby contradicting our hypothesis.

2) $r_{\ell}>s_{\ell}$: Consider the snapshots $z^{(\ell-1)}$ and
$z^{\prime(\ell-1)}$ of $z$ that look exactly the same before the $\ell$-th
deletion. Since the algorithm does not find any violations before
$z_{r_{\ell}}$, the sub-vector $z[s_{\ell}:r_{\ell}]$ satisfies
$z[s_{\ell},r_{\ell}]\leq y[s_{\ell}-\ell+1,r_{\ell}-\ell+1]$. Therefore, all
the deletions between $s_{\ell}$ and $r_{\ell}$ in $z^{(\ell-1)}$ can be moved
after $r_{\ell}$ without altering any violations. This gives us an equivalent
$z$ with $r_{\ell}=s_{\ell}$.

The proof can then be completed inductively. ∎

Equipped with both Lemma 14 and Lemma 15, we now prove Theorem 11.

###### Proof of Theorem 11.

The proof of Theorem 11 follows from the correctness of Algorithm 4 and
Algorithm 5 shown in Lemma 14 and Lemma 15 respectively.

Observe that if the asymmetric deletion distance between two vectors $x,y$ is
less than $\Delta$, then there exist some $\Delta$ deletions in both $x$ and
$y$ such that the substrings $x^{\prime}$ and $y^{\prime}$ of $x$ and $y$
respectively satisfy $x^{\prime}\leq y^{\prime}$. This condition is equivalent
to the non-existence of a $1-0$ match between $(x^{\prime},y^{\prime})$.
Algorithm 5 checks for this exact condition.

In particular, for a fixed $y^{\prime}=\tilde{y}$, and $t=\Delta$, Algorithm 5
can decide efficiently if there are some $\Delta$ deletions in a column
$A_{j}$ of $A$ such that $A_{j}^{\prime}\leq\tilde{y}$, where $A_{j}^{\prime}$
is the vector obtained by deleting some $\Delta$ entries of $A$. Thereby,
efficiently searching for a certificate for $i\in\textsc{supp}(x^{*})$.

Algorithm 4 can therefore be equivalently described as

Input: $\mathbf{A}\in\\{0,1\\}^{m\times n}$ – $(k,\Delta)$-deletion disjunct
matrix

$\tilde{\mathbf{y}}=\textsc{corr}(\textsc{Test}(A,x^{*}),\Delta)\in\\{0,1\\}^{(m-\Delta)}$

1:Let $\hat{x}=1^{n}$

2:for each $j\in[n]$ do

3: if $\textsc{Check Coverage}(\tilde{y},A_{j},\Delta)==\texttt{False}$ then

4: Set $\hat{x}_{j}=0$

5: end if

6:end for

7:Return $\hat{x}$

Algorithm 6 Decode with Deletion Disjunct Matrix

Since Algorithm 5 runs in time $O(m)$, we can guarantee that Algorithm 6
terminates in $O(nm)$ time. ∎

##  5 Conclusion and Open Problems

In this work, we initiate the study of non-adaptive combinatorial group
testing in the presence of deletions. We provide both necessary and sufficient
conditions for the exact recovery of the underlying set of defectives.
Furthermore, we also provide a randomized construction of testing matrices
that satisfy the necessary condition and give an efficient decoding algorithm.

While the construction falls slightly short of meeting the lower bounds for
larger values of $\Delta=\omega(k)$, we believe this first step is in the
right direction to achieve optimal and efficient deletion-resilient group
testing algorithms. Our conjecture is that the lower bound can be improved to
$m\geq\max\\{k^{2}\log n/\log k,\Delta k\\}$.

Furthermore, obtaining explicit constructions of deletion disjunct matrices is
left for future work. One viable approach is to use a Kautz-Singleton-like
construction by concatenating a deletion code over a larger alphabet with a
disjunct matrix such as an identity matrix. The main challenge here is to
obtain a tight bound on the asymmetric deletion distances of unions of
codewords.

## References

  * [Dor43] Robert Dorfman  “The detection of defective members of large populations”  In _The Annals of mathematical statistics_ 14.4 JSTOR, 1943, pp. 436–440
  * [SG59] Milton Sobel and Phyllis A Groll  “Group testing to eliminate efficiently all defectives in a binomial sample”  In _Bell System Technical Journal_ 38.5 Wiley Online Library, 1959, pp. 1179–1252
  * [KS64] William Kautz and Roy Singleton  “Nonrandom binary superimposed codes”  In _IEEE Transactions on Information Theory_ 10.4 IEEE, 1964, pp. 363–377
  * [VT65] RR Varshamov and GM Tenengolts  “Codes which correct single asymmetric errors (in Russian)”  In _Automatika i Telemkhanika_ 161.3, 1965, pp. 288–292
  * [Lev+66] Vladimir I Levenshtein  “Binary codes capable of correcting deletions, insertions, and reversals”  In _Soviet physics doklady_ 10.8, 1966, pp. 707–710  Soviet Union
  * [DR82] Arkadii Georgievich D’yachkov and Vladimir Vasil’evich Rykov  “Bounds on the length of disjunctive codes”  In _Problemy Peredachi Informatsii_ 18.3 Russian Academy of Sciences, Branch of Informatics, Computer Equipment and …, 1982, pp. 7–13
  * [Ber+84] Toby Berger, Nader Mehravari, Don Towsley and Jack Wolf  “Random multiple-access communication and group testing”  In _IEEE Transactions on Communications_ 32.7 IEEE, 1984, pp. 769–779
  * [Wol85] Jack Wolf  “Born again group testing: Multiaccess communications”  In _IEEE Transactions on Information Theory_ 31.2 IEEE, 1985, pp. 185–191
  * [Hao90] Fred H Hao  “The optimal procedures for quantitative group testing”  In _Discrete Applied Mathematics_ 26.1 Elsevier, 1990, pp. 79–86
  * [Gar+92] Luisa Gargano, V Montouri, G Setaro and Ugo Vaccaro  “An improved algorithm for quantitative group testing”  In _Discrete applied mathematics_ 36.3 Elsevier, 1992, pp. 299–306
  * [PL94] Pavel A Pevzner and Robert J Lipshutz  “Towards DNA sequencing chips”  In _International Symposium on Mathematical Foundations of Computer Science_ , 1994, pp. 143–158  Springer
  * [Rus94] Miklós Ruszinkó  “On the upper bound of the size of the r-cover-free families”  In _Journal of Combinatorial Theory, Series A_ 66.2 Elsevier, 1994, pp. 302–310
  * [Für96] Zoltán Füredi  “Onr-cover-free families”  In _Journal of Combinatorial Theory, Series A_ 73.1 Academic Press, 1996, pp. 172–173
  * [Mac99] Anthony J Macula  “Probabilistic nonadaptive group testing in the presence of errors and DNA library screening”  In _Annals of Combinatorics_ 3 Springer, 1999, pp. 61–69
  * [SZ99] Leonard J Schulman and David Zuckerman  “Asymptotically good codes correcting insertions, deletions, and transpositions”  In _IEEE transactions on information theory_ 45.7 IEEE, 1999, pp. 2552–2557
  * [DHH00] Dingzhu Du, Frank K Hwang and Frank Hwang  “Combinatorial group testing and its applications”  World Scientific, 2000
  * [ND00] Hung Q Ngo and Ding-Zhu Du  “A survey on combinatorial group testing algorithms with applications to DNA library screening”, 2000
  * [Slo00] Neil JA Sloane  “On single-deletion-correcting codes”  In _Codes and designs_ 10, 2000, pp. 273–291
  * [SVW00] Douglas R Stinson, Tran Van Trung and Ruizhong Wei  “Secure frameproof codes, key distribution patterns, group testing algorithms and related structures”  In _Journal of Statistical Planning and Inference_ 86.2 Elsevier, 2000, pp. 595–617
  * [HL02] Edwin S Hong and Richard E Ladner  “Group testing for image compression”  In _IEEE Transactions On image processing_ 11.8 IEEE, 2002, pp. 901–911
  * [STR03] Alexander Schliep, David C Torney and Sven Rahmann  “Group testing with DNA chips: generating designs and decoding experiments”  In _Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003_ , 2003, pp. 84–91  IEEE
  * [CM05] Graham Cormode and Shan Muthukrishnan  “What’s hot and what’s not: Tracking most frequent items dynamically”  In _ACM Transactions on Database Systems (TODS)_ 30.1 ACM New York, NY, USA, 2005, pp. 249–278
  * [Cli+07] Raphaël Clifford, Klim Efremenko, Ely Porat and Amir Rothschild  “k-mismatch with don’t cares”  In _European Symposium on Algorithms_ , 2007, pp. 151–162  Springer
  * [CH08] Hong-Bin Chen and Frank K Hwang  “A survey on nonadaptive group testing algorithms through the angle of decoding”  In _Journal of Combinatorial Optimization_ 15 Springer, 2008, pp. 49–59
  * [LG08] Jun Luo and Dongning Guo  “Neighbor discovery in wireless ad hoc networks based on group testing”  In _2008 46th Annual Allerton Conference on Communication, Control, and Computing_ , 2008, pp. 791–797  IEEE
  * [PR08] Ely Porat and Amir Rothschild  “Explicit non-adaptive combinatorial group testing schemes”  In _International Colloquium on Automata, Languages, and Programming_ , 2008, pp. 748–759  Springer
  * [AS09] George Atia and Venkatesh Saligrama  “Noisy group testing: An information theoretic perspective”  In _2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2009, pp. 355–362  IEEE
  * [Che09] Mahdi Cheraghchi  “Noise-resilient group testing: Limitations and constructions”  In _International Symposium on Fundamentals of Computation Theory_ , 2009, pp. 62–73  Springer
  * [Mit09] Michael Mitzenmacher  “A survey of results for deletion channels and related synchronization channels”, 2009
  * [INR10] Piotr Indyk, Hung Q Ngo and Atri Rudra  “Efficiently decodable non-adaptive group testing”  In _Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms_ , 2010, pp. 1126–1142  SIAM
  * [Cha+11] Chun Lam Chan, Pak Hou Che, Sidharth Jaggi and Venkatesh Saligrama  “Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms”  In _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2011, pp. 1832–1839  IEEE
  * [Che+11] Mahdi Cheraghchi, Ali Hormati, Amin Karbasi and Martin Vetterli  “Group testing with probabilistic tests: Theory, design and application”  In _IEEE Transactions on Information Theory_ 57.10 IEEE, 2011, pp. 7057–7067
  * [NPR11] Hung Q Ngo, Ely Porat and Atri Rudra  “Efficiently decodable error-correcting list disjunct matrices and applications”  In _Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I 38_ , 2011, pp. 557–568  Springer
  * [AS12] George K Atia and Venkatesh Saligrama  “Boolean compressed sensing and noisy group testing”  In _IEEE Transactions on Information Theory_ 58.3 IEEE, 2012, pp. 1880–1901
  * [Che+12] Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer and Venkatesh Saligrama  “Graph-constrained group testing”  In _IEEE Transactions on Information Theory_ 58.1 IEEE, 2012, pp. 248–262
  * [Cai+13] Sheng Cai, Mohammad Jahangoshahi, Mayank Bakshi and Sidharth Jaggi  “Grotesque: noisy group testing (quick and efficient)”  In _2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2013, pp. 1234–1241  IEEE
  * [Dya+13] Arkadii D’yachkov, Vyacheslav Rykov, Christian Deppe and Vladimir Lebedev  “Superimposed codes and threshold group testing”  In _Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede_ Springer, 2013, pp. 509–533
  * [Mal13] Mikhail Malyutov  “Search for sparse active inputs: A review”  In _Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede_ Springer, 2013, pp. 609–647
  * [Dya14] Arkadii G D’yachkov  “Lectures on designing screening experiments”  In _arXiv preprint arXiv:1401.7505_ , 2014
  * [EM14] Amin Emad and Olgica Milenkovic  “Poisson group testing: A probabilistic model for nonadaptive streaming boolean compressed sensing”  In _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2014, pp. 3335–3339  IEEE
  * [Ma+14] Liang Ma et al.  “Node failure localization via network tomography”  In _Proceedings of the 2014 Conference on Internet Measurement Conference_ , 2014, pp. 195–208
  * [GL16] Venkatesan Guruswami and Ray Li  “Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes”  In _2016 IEEE International Symposium on Information Theory (ISIT)_ , 2016, pp. 620–624  IEEE
  * [Maz16] Arya Mazumdar  “Nonadaptive group testing with random set of defectives”  In _IEEE Transactions on Information Theory_ 62.12 IEEE, 2016, pp. 7522–7531
  * [DOS17] Anindya De, Ryan O’Donnell and Rocco A Servedio  “Optimal mean-based algorithms for trace reconstruction”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , 2017, pp. 1047–1056
  * [GW17] Venkatesan Guruswami and Carol Wang  “Deletion codes in the high-noise and high-rate regimes”  In _IEEE Transactions on Information Theory_ 63.4 IEEE, 2017, pp. 1961–1970
  * [HS17] Bernhard Haeupler and Amirbehshad Shahrasbi  “Synchronization strings: codes for insertions and deletions approaching the singleton bound”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , 2017, pp. 33–46
  * [AJS+19] Matthew Aldridge, Oliver Johnson and Jonathan Scarlett  “Group testing: an information theory perspective”  In _Foundations and Trends® in Communications and Information Theory_ 15.3-4 Now Publishers, Inc., 2019, pp. 196–392
  * [Gan+19] Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi and Samson Zhou  “Nearly optimal sparse group testing”  In _IEEE Transactions on Information Theory_ 65.5 IEEE, 2019, pp. 2760–2773
  * [HRS19] Bernhard Haeupler, Aviad Rubinstein and Amirbehshad Shahrasbi  “Near-linear time insertion-deletion codes and (1+ $\varepsilon$)-approximating edit distance via indexing”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , 2019, pp. 697–708
  * [IKÖ19] Huseyin A Inan, Peter Kairouz and Ayfer Özgür  “Sparse combinatorial group testing”  In _IEEE Transactions on Information Theory_ 66.5 IEEE, 2019, pp. 2729–2742
  * [Ina+19] Huseyin A Inan, Peter Kairouz, Mary Wootters and Ayfer Özgür  “On the optimality of the Kautz-Singleton construction in probabilistic group testing”  In _IEEE Transactions on Information Theory_ 65.9 IEEE, 2019, pp. 5592–5603
  * [Aga+20] Abhishek Agarwal, Olgica Milenkovic, Srilakshmi Pattabiraman and João Ribeiro  “Group testing with runlength constraints for topological molecular storage”  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 132–137  IEEE
  * [CWH20] Weigang Chen, Lixia Wang and Changcai Han  “Correcting insertions/deletions in DPPM using hidden Markov model”  In _IEEE Access_ 8 IEEE, 2020, pp. 46417–46426
  * [CN20] Mahdi Cheraghchi and Vasileios Nakos  “Combinatorial group testing and sparse recovery schemes with near-optimal decoding time”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 1203–1213  IEEE
  * [Che+20] Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic and Joao Ribeiro  “Coded trace reconstruction”  In _IEEE Transactions on Information Theory_ 66.10 IEEE, 2020, pp. 6084–6103
  * [SGB20] Jin Sima, Ryan Gabrys and Jehoshua Bruck  “Optimal systematic t-deletion correcting codes”  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 769–774  IEEE
  * [CSS21] Devansh Chauhan, Aditya Saxena and Shilpi Sharma  “Portable and Error-Free DNA-Based Data Storage”  In _2021 4th International Conference on Recent Developments in Control, Automation & Power Engineering (RDCAPE)_, 2021, pp. 418–421  IEEE
  * [ECS21] Joshua Engels, Benjamin Coleman and Anshumali Shrivastava  “Practical near neighbor search via group testing”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 9950–9962
  * [Gho+21] Sabyasachi Ghosh et al.  “A compressed sensing approach to pooled RT-PCR testing for COVID-19 detection”  In _IEEE Open Journal of Signal Processing_ 2 IEEE, 2021, pp. 248–264
  * [LW21] Yun-Han Li and I-Hsiang Wang  “Combinatorial quantitative group testing with adversarially perturbed measurements”  In _2020 IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–5  IEEE
  * [PWT21] Liangzu Peng, Boshi Wang and Manolis Tsakiris  “Homomorphic sensing: Sparsity and noise”  In _International Conference on Machine Learning_ , 2021, pp. 8464–8475  PMLR
  * [YPT21] Yunzhen Yao, Liangzu Peng and Manolis Tsakiris  “Unlabeled principal component analysis”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 30452–30464
  * [GSZ22] Elena Grigorescu, Madhu Sudan and Minshen Zhu  “Limitations of mean-based algorithms for trace reconstruction at small edit distance”  In _IEEE Transactions on Information Theory_ 68.10 IEEE, 2022, pp. 6790–6801
  * [WGV23] Hsin-Po Wang, Ryan Gabrys and Alexander Vardy  “Tropical group testing”  In _IEEE Transactions on Information Theory_ IEEE, 2023


# The Time-reversal Odd Side of a Jet

Xiaohui Liu<EMAIL_ADDRESS>Center of Advanced Quantum Studies, Department
of Physics, Beijing Normal University, Beijing 100875, China  Center for High
Energy Physics, Peking University, Beijing 100871, China  Hongxi Xing
<EMAIL_ADDRESS>Guangdong Provincial Key Laboratory of Nuclear Science,
Institute of Quantum Matter, South China Normal University, Guangzhou 510006,
China  Guangdong-Hong Kong Joint Laboratory of Quantum Matter, South China
Normal University, Guangzhou 510006, China

###### Abstract

We re-examine the jet probes of the nucleon spin and flavor structures. We
find for the first time the time-reversal odd (T-odd) component of a jet,
conventionally thought to vanish, can survive due to the non-perturbative
fragmentation and hadronization effects and could be testable. This additional
contribution of a jet will lead to novel jet phenomena relevant for unlocking
the access to several spin structures of the nucleon, which were thought to be
impossible by using jets. As examples, we show how the T-odd constituent can
couple to the proton transversity at the Electron Ion Collider (EIC) and can
give rise to the anisotropy in the jet production in $e^{+}e^{-}$
annihilations. We expect the T-odd contribution of the jet will have broad
applications in high energy nuclear physics.

Introduction. With the advent of the Electron Ion Colliders, EIC
AbdulKhalek:2021gbh  and EicC Anderle:2021wcy , the studies of the femtoscale
structure of the nucleon are entering a new era, which will portray the full
three-dimensional (3D) image of the nucleon with unprecedented precisions. To
effectively decipher the spin and flavor information from the experimental
data, the global QCD analysis of the unpolarized and polarized parton
distribution functions (PDFs) and their 3D counterparts such as the transverse
momentum distributions (TMDs) is required. The global analysis will
simultaneously utilize all possible hard probes including inclusive cross
sections, semi-inclusive hadron productions and jets, from all available
programs such as the COMPASS, HERMES and the Relativistic Heavy Ion Collider
(RHIC). Each probe has its own advantage and complements to the others.

The idea of the jets, which originally emerged as a primary technique for
studying the strong interactions, now further demonstrates its power in
probing the fundamental properties of the nucleon and the nuclear medium
through the measurements at the LHC and RHIC Aschenauer:2016our ;
Adamczyk:2017wld ; Boer:2014lka ; Connors:2017ptx ; Cao:2020wlm . The high
luminosity of the future EIC considerably boosts the studies of the jets and
the jet substructures for exploring the nucleon spin structures and great
progress has been made. The jets have been showed the ability to access the
unpolarized TMDs as well as the transversally polarized Sivers functions
Kang:2011jw ; Liu:2018trl ; Arratia:2020nxw ; Liu:2020dct ; Aschenauer:2019uex
; Arratia:2019vju ; Arratia:2020ssx ; Kang:2020xyq ; Aschenauer:2017jsk ;
Zheng:2018ssm . Recently proposed jet charge measurements even allow the jets
to realize the direct flavor separation of the nucleon spin structure at the
EIC Kang:2020fka , which strengthens the power of the jet probes. The jet
substructure studies, like soft-drop grooming Larkoski:2014wba  and hadron in
jets Kang:2017glf ; Kang:2017btw , as well as newly developed jet construction
schemes, such as the “winner-take-all” (WTA) scheme Gutierrez-Reyes:2018qez ,
further enrich the content of the jet probes.

However, due to the unpolarized and mainly the perturbative nature of an
energetic jet, the species of the initial polarized structure functions
accessible by direct jet probes are quite limited. The initial spin
distributions, such as the proton transversity which is crucial for extracting
the least known tensor charge of the nucleon Ralston:1979ys ; Jaffe:1991kp ;
Jaffe:1991ra ; Cortes:1991ja ; Gamberg:2001qc , are regarded as unreachable
directly by the jets.

Figure 1: Origin of the jet T-odd contributions. The WTA jet axis lies outside
the plane by the spin $S$ and $P_{in}$, to allow for the asymmetry due to the
quantum correlation between parton’s spin and its hadronization about the
plane.

In this work, contrary to the conventional wisdom, we notice that the jets can
acquire the time-reversal odd (T-odd) contributions due to its non-
perturbative ingredients, especially in the ${\cal O}(\sim 1\,{\rm GeV})$
region where the interesting nuclear Femtography usually happens qiutalk . The
basic idea goes as the follows: the spin direction $S$ of the fragmenting
parton generates a preference in its hadronization or an asymmetry, in one
side of the plane determined by the parton momentum $P_{in}$ and its spin
direction $S$, than the other side. Similar to the Collins effect
Collins:1992kk , as long as the jet axis is not aligned with the fragmenting
parton, this asymmetry will be non-vanishing due to the nontrivial phases
induced by non-perturbative final state interactions. This is generically true
for the WTA jets as sketched in fig. 1 as well as the groomed jets, where the
jet axis does not fall into the plane spanned by $P_{in}$ and $S$. The
situation also holds even for the standard jets due to the soft radiations
outside the jet cone Cal:2019gxa . This small imbalance between the jet axis
and the parton momentum direction in the $\sim{\cal O}(1\,{\rm GeV})$ region,
where indeed roots the focus of many nucleon spin programs, could thus probe
the asymmetry. One can further enhance the net asymmetry by measuring the jet
charge to separate the fragmenting parton species Kang:2020fka . Therefore, we
expect this non-perturbative T-odd side of a jet to have testable effects.

The possible existence of the T-odd jets opens up many new opportunities for
probing the nucleon intrinsic spin dynamics by using jets, which were thought
impossible. As concrete examples, we demonstrate its feasibility to the proton
transversity in transversely polarized DIS by extending the factorization of
the conventional unpolarized jet production to the T-odd case. We also show
the T-odd jets can generate the azimuthal angle asymmetry in $e^{+}e^{-}$
annihilations, which in turn can be used to extract T-odd ingredients of a jet
with currently available experimental data.

Time-reversal odd jet function. To introduce T-odd jet function, we consider
the jet $J$ production in the collision between an unpolarized electron $e$
and a transversely polarized proton $p$ with spin $s_{T}$ and momentum $P$,
$l\,p(P,s_{T})\to\gamma^{\ast}(q)\to l^{\prime}\,J(P_{J})+X$, where we assume
$P^{\mu}=\frac{Q}{2}(1,0,0,1)=\frac{Q}{2}n^{\mu}$. We construct the jet out of
the WTA scheme Gutierrez-Reyes:2018qez  with radius $R$. We emphasize that the
use of the WTA jet is for illustration but not mandatory. Our conclusion holds
generically for jet productions. We are particularly interested in the case
that $q_{T}\ll Q$, especially for $q_{T}\sim\Lambda_{\rm QCD}$ to probe the
intrinsic dynamics of the proton. Here $q_{T}=q-\frac{n\cdot
q}{2}{\bar{n}}-\frac{{\bar{n}}\cdot q}{2}n$ is the transverse momentum of the
virtual photon in the frame that the jet axis defines the conjugate direction
${\bar{n}}=(1,0,0,-1)$. In the frame that the virtual photon and the proton
develop no transverse momenta (the $\gamma$-$p$ frame),
$q_{T}=-\frac{P_{J\perp}}{z}$ up to $1/Q^{2}$ corrections where $z=n\cdot
P_{J}/Q$.

We follow Gutierrez-Reyes:2018qez  to derive the factorization theorem for the
cross section using Soft Collinear Effective Theory (SCET) Bauer:2000yr ;
Bauer:2001ct ; Bauer:2001yt ; Bauer:2002nz

$\displaystyle\sigma$ $\displaystyle=$
$\displaystyle\frac{1}{2s}\int\frac{d^{4}q}{(2\pi)^{4}}\int[dl^{\prime}]\frac{e^{4}e_{q}^{2}}{Q^{4}}\frac{1}{2}L^{\mu\nu}(2\pi)^{4}\delta^{(4)}(l^{\prime}+q-l)$
(1) $\displaystyle\times$
$\displaystyle\int[dP_{J}](2\pi)^{4}\delta(P+q-P_{J}-p_{X})$
$\displaystyle\times$ $\displaystyle\frac{1}{2N_{c}}\langle
P,s_{T}|\xi^{\dagger}_{n}\gamma_{\mu}\xi_{\bar{n}}|JX\rangle\langle
JX|\xi^{\dagger}_{\bar{n}}\gamma_{\nu}\xi_{n}|P,s_{T}\rangle\,,$

where $s$ is the center of mass energy squared and $L^{\mu\nu}$ is the lepton
tensor. The notation $[d\dots]$ denotes the phase space measure and $p_{X}$ is
the momentum of the final hadronic states not clustered into the jet.
$\xi_{n(\bar{n})}=W_{n({\bar{n}})}^{\dagger}\chi_{n({\bar{n}})}$ Bauer:2000yr
; Bauer:2001ct ; Bauer:2001yt ; Bauer:2002nz  is the SCET quark field encodes
both the $n({\bar{n}})$-collinear quark field $\chi_{n({\bar{n}})}$ and the
Wilson line $W_{n({\bar{n}})}$. Here $J$ reminds us that a jet is constructed
in the final state.

In the small $q_{T}$ limit, the $n$ and ${\bar{n}}$ collinear sectors can be
factorized and the cross section can be written as

$\displaystyle\sigma=\frac{1}{2s}\int[dl^{\prime}]\frac{e^{4}e_{q}^{2}}{Q^{4}}\frac{1}{2}L_{\mu\nu}\frac{1}{2N_{c}}\,\int
d^{2}x_{T}\,e^{iq_{T}\cdot
x_{T}}\gamma^{\mu}_{\alpha\beta}\gamma^{\nu}_{\beta^{\prime}\alpha^{\prime}}$
$\displaystyle\times$ $\displaystyle\int dx^{-}e^{iq^{+}x^{-}}\langle
P,s_{T}|\xi_{n}(0)\xi^{\dagger}_{n}(x^{-},x_{T})|P,s_{T}\rangle_{\alpha^{\prime}\alpha}$
$\displaystyle\times$ $\displaystyle\int[dP_{J}]\int
dx^{+}e^{iq^{-}x^{+}}\langle
0|\xi_{\bar{n}}(x^{+},x_{T})|JX_{\bar{n}}\rangle_{\beta}\langle
JX_{\bar{n}}|\xi^{\dagger}_{\bar{n}}(0)|0\rangle_{\beta^{\prime}}\,,\,$

To proceed, we introduce the proton structure function
$\Phi_{\alpha^{\prime}\alpha}$ and the jet function matrices ${\cal
J}^{q}_{\beta\beta^{\prime}}$, such that

$\displaystyle\langle
P,s_{T}|{\bar{\xi}}_{n}(0){\xi}_{n}(x^{-},x_{T})|P,s_{T}\rangle_{\alpha^{\prime}\alpha}$
(3) $\displaystyle=$ $\displaystyle P^{+}\int_{0}^{1}d\zeta\int
d^{2}p_{T}e^{i\zeta\,P^{+}x^{-}}e^{ip_{T}\cdot
x_{T}}\Phi_{\alpha^{\prime}\alpha}(\zeta,p_{T})\,,$

and

$\displaystyle\langle
0|{\bar{\xi}}_{{\bar{n}}}(x^{+},x_{T})|JX_{\bar{n}}\rangle_{\beta}\langle
JX_{\bar{n}}|{\xi}_{\bar{n}}(0)|0\rangle_{\beta^{\prime}}$ (4)
$\displaystyle=$ $\displaystyle 2P_{J}^{-}\int_{0}^{1}\frac{dz}{z}\int
d^{2}k_{T}e^{-i\frac{P_{J}^{-}}{z}x^{+}}e^{-ik_{T}\cdot x_{T}}{\cal
J}^{q}_{\beta\beta^{\prime}}(z,k_{T},R)\,,\,\quad$

to find the cross section arrive at the form in which

$\displaystyle\sigma=\frac{1}{2s}\int[dl^{\prime}]\frac{e^{4}e_{q}^{2}}{Q^{4}}\frac{1}{2}L_{\mu\nu}$
$\displaystyle\times\frac{1}{2N_{c}}\,2\,\int[dP_{J}]\,\int d^{2}p_{T}\int
d^{2}k_{T}(2\pi)^{4}\delta^{(2)}(q_{T}+p_{T}-k_{T})$
$\displaystyle\times\delta(1-z)\gamma^{\mu}_{\alpha\beta}\gamma^{\nu}_{\beta^{\prime}\alpha^{\prime}}\,{\mathfrak{J}}^{q}_{\beta\beta^{\prime}}(k_{T})\,\Phi_{\alpha^{\prime}\alpha}(\zeta,p_{T})\,,$
(5)

where $\zeta=Q/P^{+}$ and $z=P_{J}^{-}/Q$. Here we have used the property that
for the WTA jet, when $k_{T}\ll P_{J}R$, ${\cal
J}^{q}_{\beta\beta^{\prime}}(z,k_{T},R)=\delta(1-z){\mathfrak{J}}^{q}_{\beta\beta^{\prime}}(k_{T})+{\cal
O}\left(\frac{k_{T}^{2}}{p_{J}^{2}R^{2}}\right)$, independent of both $R$ and
$z$ Gutierrez-Reyes:2018qez . Till now, the derivation is standard and follows
Gutierrez-Reyes:2018qez .

According to spin structures, the matrix element
${\mathfrak{J}}^{q}_{\beta\beta^{\prime}}$ can take the general form that (see
for instance Bacchetta:2006tn )

$\displaystyle{\mathfrak{J}}^{q}(k_{T}^{2})=\frac{\bar{n}\\!\\!\\!/}{2}\,J^{q}(k_{T}^{2})+i\frac{k\\!\\!\\!/_{T}\bar{n}\\!\\!\\!/}{2}J^{q}_{T}(k_{T}^{2})\,,$
(6)

where $J^{q}(k_{T}^{2})$ is the conventional WTA jet function which has been
discussed extensively in the literature.

Conventionally, for jet productions, the second term is always discarded as
$J^{q}_{T}(k^{2}_{T})$ is T-odd and therefore regarded as vanishing due to the
time-reversal symmetry of perturbative QCD. However, in the scenario we
considered and also in many spin programs, since $k_{T}\sim\Lambda_{\rm QCD}$,
the jet function involved is intrinsically non-perturbative and sensitive to
the strong interaction fragmentation and hadronization, where there exist
nontrivial phases from final state interactions to prevent the T-odd jet
function $J^{q}_{T}$ from vanishing. Exactly the same mechanism results in the
Collins effect Collins:1992kk  in the single parton fragmentation and we
expect the similar consequence will happen to the jet, as explained in the
previous section. The recently proposed jet charge measurement which reweighs
the contributions from different quark species Kang:2020fka  will further
enhance the T-odd effects.

In many other nucleon structure studies, since the $P_{J}R$ is not too large,
around ${\cal O}(5{\rm GeV})$ or less, the non-perturbative contributions to
the jet are usually important and thus the T-odd component of the jet $J_{T}$
could still have a visible phenomenological impact, especially for machines
with relatively low center of mass energy such as 12 GeV CEBAF at Jefferson
Lab, EIC, EicC and etc..

Figure 2: Angular variables involved in Eq. (7) in DIS.

The non-vanishing T-odd jet function could open up many new opportunities for
probing the proton intrinsic dynamics, which were thought un-accessible by
using jets. Below we hightlight some of the possible applications to the
nuclear structure studies.

Transversely polarized deep-inelastic-scattering. From Eq. (The Time-reversal
Odd Side of a Jet) and Eq. (6) and compared with the hadron production
Bacchetta:2006tn , it is immediately to realize that the non-vanishing T-odd
component allows the jet to probe the proton transversity $h_{1}$ through the
azimuthal distribution

$\displaystyle
A(\zeta,y,\phi_{s},\phi_{J},P_{J\perp})=1+\epsilon|s_{\perp}|\sin(\phi_{J}+\phi_{s})\frac{F_{UT}}{F_{UU}}\,,$
(7)

where $F_{UU}$ is the conventional unpolarized jet production which can be
found in Gutierrez-Reyes:2018qez  and the azimuthal dependent part

$\displaystyle
F_{UT}=\sum_{q}\,e_{q}^{2}\,\int\frac{d^{2}b}{4\pi^{2}}e^{-iP_{J\perp}\cdot
b}i\frac{P_{J\perp}^{\alpha}}{P_{J\perp}}\,\,\zeta\,h^{q}_{1}(\zeta,b)\,\partial_{b^{\alpha}}J^{q}_{T}(b)\,.$

Here $h^{q}_{1}(\zeta,b)$ and $J^{q}_{T}(b)$ are the Fourier transformation of
the proton transversity $h^{q}_{1}(\zeta,p_{T})$ and the T-odd jet function
$J^{q}_{T}(k_{T})$, respectively.

The azimuthal distribution is measured in the $\gamma$-$p$ frame, where the
kinematics involved are illustrated in Fig. 2 with

$\displaystyle\epsilon=\frac{1-y-\frac{1}{4}\gamma^{2}y^{2}}{1-y+\frac{1}{2}y^{2}+\frac{1}{4}\gamma^{2}y^{2}}\,,\quad\quad
y=\frac{P\cdot q}{P\cdot l}\,,$ (9)

and $\gamma=2\zeta\frac{m_{P}}{Q}$ with $m_{P}$ the proton mass.

To access to this cross section, we construct jet using the WTA scheme and we
perform the measurements in the $\gamma$-$p$ frame and restrict us to the
region where $P_{J\perp}\sim\Lambda_{\rm QCD}\ll Q$. We can map out the
specific hadron species component to further separate the $u$\- and $d$-quark
flavors Kang:2020fka .

Compared with measuring final state hadron Collins effect, we see from Eq.
(The Time-reversal Odd Side of a Jet) that the advantage of the T-odd WTA jet
probe of the incoming proton transversity is that it reduces the non-
perturbative degrees freedom from two variables ($z_{H},k_{T}$) to only one
variable $k_{T}$, which allows for a cleaner extraction of the perturbative
transversity at HERA or future EIC and EicC.

Anisotropy in $e^{+}\,e^{-}$ annihilation. The T-odd jet function can also
generate the angular anisotropic distribution in the almost back-to-back jet
production in $e^{+}e^{-}$ annihilation. Such asymmetry allows a direct
extraction of the T-odd jet function via analysis of the BaBar or BELLE data.

Figure 3: Kinematics in the $e^{+}e^{-}$ annihilation.

Here again, we stick to the WTA jets with $q_{T}\ll\sqrt{s}R$, where
$\sqrt{s}$ is the center of mass energy and $q_{T}=-P_{J_{1},\perp}$. The
kinematics that we considered are depicted in Fig. 3

The azimuthal asymmetry takes the general form Kang:2014zza

$\displaystyle
R^{J_{1}J_{2}}=1+\cos(2\phi_{1})\frac{\sin^{2}\theta}{1+\cos^{2}\theta}\frac{F_{T}(q_{T})}{F_{U}(q_{T})}\,,$
(10)

where the angular information follows Fig. 3. $F_{U}$ is the contribution from
conventional WTA jet while $F_{T}$ from the T-odd component, respectively. The
$F_{U}$ is known and found to be Gutierrez-Reyes:2018qez

$\displaystyle
F_{U}=q_{T}\,\sum_{q}e_{q}^{2}\,\int\frac{\mathrm{d}b\,b}{2\pi}J_{0}(q_{T}b)J^{q}(b){\bar{J}}^{\bar{q}}(b)\,,$
(11)

where $J_{0}(q_{T}b)$ is the Bessel function, while the newly identified
$F_{T}$ is given by

$\displaystyle F_{T}$ $\displaystyle=$ $\displaystyle
q_{T}\,\sum_{q}\,e_{q}^{2}\,\int\frac{\mathrm{d}^{2}b}{(2\pi)^{2}}e^{-iq_{T}\cdot
b}\left(2\frac{q_{T}^{\alpha}}{q_{T}}\frac{q_{T}^{\beta}}{q_{T}}+g^{\alpha\beta}\right)$
(12)
$\displaystyle\times\partial_{b^{\alpha}}J^{q}_{T}(b)\partial_{b^{\beta}}{\bar{J}}^{\bar{q}}_{T}(b)\,.$

In Fig. 4, we present a prediction for the azimuthal asymmetry $R=2\int
d\cos\theta\,\frac{d\phi_{1}}{\pi}\cos(2\phi_{1})R^{J_{1}J_{2}}$ for the
center of mass energy $\sqrt{s}=\sqrt{110}\,{\rm GeV}$. We have included the
evolution in the prediction through

$\displaystyle J(b){\bar{J}}(b)=e^{-S_{pert.}-S^{J}_{NP}}\left(1+{\cal
O}(\alpha_{s})\right)r_{q}(Q_{J_{h_{1}}})r_{{\bar{q}}}(Q_{J_{h_{2}}})\,,$

for $F_{U}$, where the ${\cal O}(\alpha_{s})$ corrections can be extracted
from Gutierrez-Reyes:2018qez . Here we assumed that the jet charge
$Q_{J_{h}}=\sum_{h\in J}z_{h}^{\kappa}e_{h}$ measurement is applied to
separate the quark flavors, follows Kang:2020fka , with $h$ restricted to a
specific hadron species. Here $z_{h}$ is the momentum fraction carried by the
hadron $h$ and $\kappa>0$ is a free parameter. Thus the additional charge
fraction of the jet $r_{q}$ for a given initiating quark is multiplied into
the jet function, which depends on how the jet charge is measured. In this
study, we assume that the pion charge are used to construct the jet charge
with $\kappa=0.3$ following Kang:2020fka  and we require one of the jet charge
to be greater than $0.3$ and the other smaller than $-0.3$. For
$Q_{J_{\pi}}>0.3$, it is found in Kang:2020fka  that $r_{u}\approx
r_{\bar{d}}\approx 0.52=r_{fav.}$ and $r_{\bar{u}}\approx r_{d}\approx
0.15=r_{dis.}$ while for $Q_{J_{\pi}}<-0.3$, we have $r_{u}\approx
r_{\bar{d}}\approx r_{dis.}$ and $r_{\bar{u}}\approx r_{d}\approx r_{fav.}$.
In both cases, $r_{s}\approx r_{\bar{s}}\approx 0.3$.

The $S_{pert.}$ is the perturbative Sudakov factor

$\displaystyle
S_{pert.}=\int_{\mu_{b}^{2}}^{s}\frac{d\mu^{2}}{\mu^{2}}\left(A\log\frac{s}{\mu^{2}}+B\right)\,,$
(14)

with the anomalous dimension $A$ and $B$ can be found in Koike:2006fn . The
scale $\mu_{b}=c_{0}/b_{\ast}$ where $b_{\ast}=b/\sqrt{1+b^{2}/b_{max}^{2}}$
with $c_{0}\approx 1.22$ and $b_{max}=1.5\,{\rm GeV}^{-1}$. The
$b_{\ast}$-prescription introduces the non-perturbative Sudakov factor
$S_{NP}^{J}$, which, following Kang:2014zza , we parameterized as
$S^{J}_{NP}=g_{2}\ln(b/b_{\ast})\ln(\sqrt{s}/Q_{0})+2g_{h}b^{2}$ and set
$g_{2}=0.84$, $g_{h}=0.042\,{\rm GeV}^{-2}$ and $Q_{0}=2.4\,{\rm GeV}^{2}$.

Figure 4: Azimuthal asymmetry induced by the T-odd jet as a function of
$q_{T}$ in $e^{+}e^{-}$.

The T-odd jet function is non-perturbative and yet to be determined by future
experimental analysis. Here for the purpose of highlighting, we use a simple
model to parameterize its contribution as

$\displaystyle\partial_{b^{\alpha}}J_{T}^{q}\partial_{b^{\beta}}{\bar{J}}^{\bar{q}}_{T}=e^{-S_{pert.}-S_{NP}^{T}}\,\frac{b^{\alpha}b^{\beta}}{4}\,{\cal
N}^{h}_{q}(b){\cal N}^{h}_{\bar{q}}(b)\,.$ (15)

The model is motivated by the similarity between the T-odd jet function and
the Collins function Collins:1992kk ; Kang:2014zza . A detailed operator study
of the T-odd jet function following the strategy in Yuan:2009dw  will be given
elsewhere. The non-perturbative Sudakov factor is parameterized as
$S^{T}_{NP}=g_{2}\ln(b/b_{\ast})\ln(\sqrt{s}/Q_{0})+2(g_{h}-g_{c})b^{2}$ with
all parameters the same as $S^{J}_{NP}$ but the additional $g_{c}=0.0236\,{\rm
GeV}^{2}$ Kang:2014zza . ${\cal N}_{q}^{h}(b)$ determines the sign and the
magnitude of the T-odd jet function, which also depends on the quark flavors
that initiate the jet and how the jet charge is measured. Within the scenario
described previously, the $u({\bar{u}})$-quark contribution is expected to be
dominant due to its relatively large charge value Kang:2020fka , we thus only
consider the $u({\bar{u}})$ quark contribution and parameterize ${\cal
N}^{h}_{q}(b)$ as ${\cal N}^{\pi}_{u}(Q_{J_{\pi}}>0.3,b)={\cal
N}^{\pi}_{\bar{u}}(Q_{J_{\pi}}<-0.3,b)=-0.3\,r_{fav.}$ while ${\cal
N}^{\pi}_{u}(Q_{J_{\pi}}<-0.3,b)={\cal
N}^{\pi}_{\bar{u}}(Q_{J_{\pi}}>0.3,b)=0.1\,r_{dis.}$.

In Fig. 4, we can see a non-vanishing azimuthal asymmetry induced by the T-odd
jet. The actual magnitude and shape of this asymmetry should be determined by
upcoming experimental data analyses.

Conclusion. In this work, we re-examine the factorization theorem of the jet
production for nucleon spin studies. Unlike the jet physics at the LHC, for
nucleon dynamic studies, the typical scale of the focused region is much lower
$\sim{\cal O}(1\,{\rm GeV})$, and thus the jet involved could be intrinsically
non-perturbative. The non-perturbative part of the jet allows the existence of
a time-reversal odd component. We found that the T-odd contribution, which
were thought to vanish, gives rise to novel jet phenomena and endows the jets
the ability to probe many nucleon spin structures which were thought to be
inaccessible by jets. As direct demonstrations, we show how the proton
transversity can couple to the T-odd jet function in the $q_{T}$ distribution
of the WTA jets in transversely polarized DIS. We also show the T-odd jet
function can be directly measured via the induced anisotropy in the
$e^{+}e^{-}$ annihilations at Belle and BaBar.

Other possible signatures of the T-odd jet contributions could include the
azimuthal asymmetries for almost back-to-back jet production in the
unpolarized $pp$ collisions, In addition, it could provide an alternative
probe of the globally polarized quark gluon plasma in non-central nucleus-
nucleus collisions Liang:2004ph ; STAR:2017ckg . We left these to future
studies.

We emphasize that the T-odd feature of the jet is not limited to the WTA jet
discussed in the current work, but holds for generic jet productions once the
jet axis deviates from the fragmenting parton. In addition, along the similar
line, the T-odd asymmetries should also exist in many jet shape observables in
the non-perturbative regime, due to the correlation with the fragmenting
parton spin polarization. The deviation for different jet schemes and/or event
shapes will be sensitive differently to soft and collinear radiations and
weighs differently the non-perturbative interactions from the soft or the
collinear sectors. Therefore jets will offer us the flexibility to probe
differently the non-perturbative mechanisms to the T-odd asymmetries. From
this aspect, the T-odd side of a jet, on its own, will be interesting to
investigate with more details and could bring us new insights into the non-
perturbative QCD dynamics.

We thus expect the T-odd ingredient of a jet identified in this work to
maximize the power of the jet probes and bring new avenues to the spin program
at current and future facilities and complement other probes of the spin
information via the conventional hadron process.

###### Acknowledgements.

Acknowledgements. We thank Zhongbo Kang and Yuxiang Zhao for comments on the
manuscript. This work is supported by the Guangdong Major Project of Basic and
Applied Basic Research No. 2020B0301030008 and by the National Natural Science
Foundation of China under Grant No. 12022512, No. 12035007. (H.X.) and Grant
No. 11775023 (X.L.).

## References

  * (1) R. Abdul Khalek et al.,  (2021), arXiv:2103.05419.
  * (2) D. P. Anderle et al.,  (2021), arXiv:2102.09222.
  * (3) E.-C. Aschenauer et al.,  (2016), arXiv:1602.03922.
  * (4) STAR, L. Adamczyk et al.,  Phys. Rev. D 97, 032004 (2018), arXiv:1708.07080.
  * (5) D. Boer and C. Pisano,  Phys. Rev. D 91, 074024 (2015), arXiv:1412.5556.
  * (6) M. Connors, C. Nattrass, R. Reed, and S. Salur,  Rev. Mod. Phys. 90, 025005 (2018), arXiv:1705.01974.
  * (7) S. Cao and X.-N. Wang,  Rept. Prog. Phys. 84, 024301 (2021), arXiv:2002.04028.
  * (8) Z.-B. Kang, A. Metz, J.-W. Qiu, and J. Zhou,  Phys. Rev. D 84, 034046 (2011), arXiv:1106.3514.
  * (9) X. Liu, F. Ringer, W. Vogelsang, and F. Yuan,  Phys. Rev. Lett. 122, 192003 (2019), arXiv:1812.08077.
  * (10) M. Arratia, Z.-B. Kang, A. Prokudin, and F. Ringer,  (2020), arXiv:2007.07281.
  * (11) X. Liu, F. Ringer, W. Vogelsang, and F. Yuan,  (2020), arXiv:2007.12866.
  * (12) E.-C. Aschenauer, K. Lee, B. Page, and F. Ringer,  Phys. Rev. D 101, 054028 (2020), arXiv:1910.11460.
  * (13) M. Arratia, Y. Song, F. Ringer, and B. Jacak,  Phys. Rev. C 101, 065204 (2020), arXiv:1912.05931.
  * (14) M. Arratia, Y. Makris, D. Neill, F. Ringer, and N. Sato,  (2020), arXiv:2006.10751.
  * (15) Z.-B. Kang, K. Lee, and F. Zhao,  Phys. Lett. B 809, 135756 (2020), arXiv:2005.02398.
  * (16) E. Aschenauer et al.,  Rept. Prog. Phys. 82, 024301 (2019), arXiv:1708.01527.
  * (17) L. Zheng, E. Aschenauer, J. Lee, B.-W. Xiao, and Z.-B. Yin,  Phys. Rev. D 98, 034011 (2018), arXiv:1805.05290.
  * (18) Z.-B. Kang, X. Liu, S. Mantry, and D. Y. Shao,  Phys. Rev. Lett. 125, 242003 (2020), arXiv:2008.00655.
  * (19) A. J. Larkoski, S. Marzani, G. Soyez, and J. Thaler,  JHEP 05, 146 (2014), arXiv:1402.2657.
  * (20) Z.-B. Kang, X. Liu, F. Ringer, and H. Xing,  JHEP 11, 068 (2017), arXiv:1705.08443.
  * (21) Z.-B. Kang, A. Prokudin, F. Ringer, and F. Yuan,  Phys. Lett. B 774, 635 (2017), arXiv:1707.00913.
  * (22) D. Gutierrez-Reyes, I. Scimemi, W. J. Waalewijn, and L. Zoppi,  Phys. Rev. Lett. 121, 162001 (2018), arXiv:1807.07573.
  * (23) J. P. Ralston and D. E. Soper,  Nucl. Phys. B 152, 109 (1979).
  * (24) R. L. Jaffe and X.-D. Ji,  Phys. Rev. Lett. 67, 552 (1991).
  * (25) R. L. Jaffe and X.-D. Ji,  Nucl. Phys. B 375, 527 (1992).
  * (26) J. L. Cortes, B. Pire, and J. P. Ralston,  Z. Phys. C 55, 409 (1992).
  * (27) L. P. Gamberg and G. R. Goldstein,  Phys. Rev. Lett. 87, 242001 (2001), arXiv:hep-ph/0107176.
  * (28) J. Qiu,  Physics at the EIC: QCD at a Fermi scale,  presented at PHENO 2020, University of Pittsburgh (online), 4-6 May, 2020\.
  * (29) J. C. Collins,  Nucl. Phys. B396, 161 (1993), arXiv:hep-ph/9208213.
  * (30) P. Cal, D. Neill, F. Ringer, and W. J. Waalewijn,  JHEP 04, 211 (2020), arXiv:1911.06840.
  * (31) C. W. Bauer, S. Fleming, D. Pirjol, and I. W. Stewart,  Phys. Rev. D63, 114020 (2001), arXiv:hep-ph/0011336.
  * (32) C. W. Bauer and I. W. Stewart,  Phys. Lett. B516, 134 (2001), arXiv:hep-ph/0107001.
  * (33) C. W. Bauer, D. Pirjol, and I. W. Stewart,  Phys. Rev. D65, 054022 (2002), arXiv:hep-ph/0109045.
  * (34) C. W. Bauer, S. Fleming, D. Pirjol, I. Z. Rothstein, and I. W. Stewart,  Phys. Rev. D66, 014017 (2002), arXiv:hep-ph/0202088.
  * (35) A. Bacchetta et al.,  JHEP 02, 093 (2007), arXiv:hep-ph/0611265.
  * (36) Z.-B. Kang, A. Prokudin, P. Sun, and F. Yuan,  Phys. Rev. D 91, 071501 (2015), arXiv:1410.4877.
  * (37) Y. Koike, J. Nagashima, and W. Vogelsang,  Nucl. Phys. B 744, 59 (2006), arXiv:hep-ph/0602188.
  * (38) F. Yuan and J. Zhou,  Phys. Rev. Lett. 103, 052001 (2009), arXiv:0903.4680.
  * (39) Z.-T. Liang and X.-N. Wang,  Phys. Rev. Lett. 94, 102301 (2005), arXiv:nucl-th/0410079,  [Erratum: Phys.Rev.Lett. 96, 039901 (2006)].
  * (40) STAR, L. Adamczyk et al.,  Nature 548, 62 (2017), arXiv:1701.06657.