The group testing problem was originally studied in the context of testing blood samples for a rare disease [1] , with the key idea being to reduce the required number of tests by pooling samples. Group testing has since found applications in communications [2] , information retrieval [3] , compressed sensing [4] , and most recently, COVID-19 testing [5] - [7] .
The problem is formally defined as follows: There are n items [n] = {1, 2, . . . , n}, a subset S ⊆ [n] of which are defective, with |S|= k. We are interested in the minimum number of tests needed to determine S, where each test takes as input a subset of items, and returns positive if and only if the subset contains at least one defective item. A group testing algorithm specifies the number of tests T , the items included in each test, and a decoder that returns an estimateŜ of the defective set given the test outcomes.
We focus on the non-adaptive setting, in which all tests must be specified prior to observing any outcomes (e.g., to permit parallel implementation). In this case, the tests can be represented as a test matrix X ∈ {0, 1} T ×n , where the (i, j)-entry is 1 if and only if the i-th test contains the j-th item. The test outcomes are then given by the element-wise "OR" of the k columns corresponding to defective items.
The number of tests required depends on the recovery criterion adopted. For exact recovery, we re-quireŜ = S, i.e., the error probability is given by P e = P[Ŝ = S]. For approximate recovery, following [8] , [9] , we consider the case that up to αk false positives and false negatives are allowed for some approximation parameter α > 0, yielding
We are interested in algorithms that attain P e → 0 as n → ∞ with as few tests as possible. A common evaluation metric is the rate, 1 given by nH2(p) T nats/test (or nH2(p)
T ln 2 bits/test) [11] , [12] , where H 2 (·) denotes the binary entropy function in nats.
While the prevailing regime in the literature has been the sublinear regime k = o(n) [8] , [13] -[19], our focus is on the linear regime k = Θ(n), which is often the most natural scaling in practice. Specifically, we assume that each item is independently defective with probability p, for some prevalence p ∈ (0, 1). By binomial concentration, we have k = np(1 + o(1)) with probability approaching one.
A trivial group testing algorithm involves placing each item in its own test, yielding T = n. It was shown by Aldridge [20] that this is in fact optimal for exact recovery in the linear regime, i.e., any algorithm using fewer than n tests cannot attain P e → 0. This negative result raises the following questions:
• Can we use significantly fewer than n tests while attaining a given non-vanishing target error probability P e ∈ (0, 1), such as 0.05 or 0.5? • Can we use significantly fewer than n tests under the approximate recovery criterion while attaining asymptotically vanishing error probability? We answer the first question in the negative, and show that for any > 0, if fewer than (1 − )n tests are used, the error probability tends to one, i.e., the strong converse holds. In contrast, we answer the second question in the positive, showing that the simple COMP algorithm [11, Sec. 2.3] improves on individual testing for broad ranges of the prevalence p and approximate recovery parameter α, as well as providing an algorithm-independent converse.
Recently, another route to providing positive results in the linear regime was proposed, namely, two-stage adaptive testing [21] . See also [12] for the adaptive setting with no bound on the number of stages.
In the sublinear sparsity regime, the typical scaling considered is k = Θ(n θ ) for some θ ∈ (0, 1) [8] , [11] . A line of works studying this regime [8] , [15] - [19] showed that the optimal number of tests is (k log 2 n k )(1 + o(1)) for θ ≤ 1/3 [8] , [22] and then θ 0.43 [17] , [18] . Most recently, [19] closed several open problems regarding first-order asymptotics, establishing the precise rates for all θ ∈ (0, 1), and achieving them with an efficient algorithm.
The approximate recovery criterion has also seen progress in the sublinear regime, with near-matching achievability and converse bounds. It was shown in [8] that if k = o(n), then k log 2 n k (1 + o(1)) tests are sufficient and (1 − α) k log 2 n k (1 − o(1)) tests are necessary. It was shown in [23] that the latter bound is tight, and can be matched by ignoring roughly a fraction α of the items and applying the achievability result of [8] to the remaining items.
In this section, we state the main results of the paper, deferring the proofs to Section III. Our first result is the strong converse bound for exact recovery, which strengthens the weak converse of [20] .
Theorem 1. For non-adaptive group testing with a constant prevalence p ∈ (0, 1) and exact recovery, if T ≤ (1 − )n for some constant > 0, then the error probability of any algorithm tends to one as n → ∞.
Our remaining results concern the approximate recovery criterion in (1) . We note that declaring every item to be defective independently with probability p attains P e → 0 with no tests when α > 1 − p, so we assume without loss of generality that α < 1 − p.
We start with a simple converse based on a known rate-distortion expression for sparse sources [24] . Theorem 2. Consider the non-adaptive group testing problem with a constant prevalence p ∈ (0, 1), and the approximate recovery criterion with a constant parameter α ∈ (0, 1 − p). Then, for any > 0, the number of tests T must be at least
in order to attain vanishing error probability.
We note that the scaling in (2) is linear in n, and coefficient is strictly positive for all α < 1 − p. We will shortly provide numerical examples.
Our first upper bound is based on a standard analysis using i.i.d. Bernoulli testing and the COMP algorithm [11] , [25] . Given a test matrix and the corresponding test results, COMP declares all items that are present in at least one negative test to be non-defective, and declares the rest of the items to be defective.
Theorem 3. Consider the non-adaptive group testing problem with a constant prevalence p ∈ (0, 1), and the approximate recovery criterion with a constant parameter α ∈ (0, 1 − p). Then, under i.i.d. Bernoulli testing with inclusion probability 1 np , the COMP algorithm attains asymptotically vanishing error probability using
tests, where > 0 is arbitrarily small.
The second upper bound is based on a more sophisticated variant -we ignore roughly a fraction α of the items [23] , and test those remaining using a near-constant test-per-item design [17] , [18] .
Theorem 4. Consider the non-adaptive group testing problem with a constant prevalence p ∈ (0, 1), and the approximate recovery criterion with a constant parameter α ∈ (0, 1 − p). Then, there exists a test design such that the COMP algorithm attains asymptotically vanishing error probability using
tests, where > 0 is arbitrarily small.
Next, we simplify the bound (4) in the limit as p → 0. To do this, we reparametrize the bound by equating (
. Substituting into (4) yields that the argument to the minimization equals
p ) scaling implies that the integer constraint on L has a negligible impact as p → 0, and we can choose ψ to maximize ln ψ · ln(1 − ψ). This is easily shown to take a maximum value of (ln 2) 2 when ψ = 1 2 . Since α ∈ (0, 1) is constant, we can additionally simplify ln 0.531 to 0.693 comes from the near-constant test-peritem design [17] , and the increase of 1 1−α comes from the approach of ignoring some items [23, Thm. 7] .
To further illustrate our findings, we provide rate plots for α = 0.1 and α = 0.001; see Figure 1 . We see that Theorem 4 provides a strict improvement over Theorem 3, and outperforms individual testing provided that p is not too high. As α decreases, the threshold on p associated with this statement moves closer to zero, consistent with the fact that individual testing is optimal for α = 0 [11] .
Proof of Theorem 1 (Strong Converse). Our analysis builds on the ideas of [19], [20] , both of which identify totally disguised items (see Definition 1 below) whose defectivity status can be flipped without changing the test outcomes. In [20] , one such item suffices for attaining the weak converse in the linear regime, whereas in [19] many such items are sought in order to handle the sublinear regime. While the analysis of [19] introduces terms that are negligible for k = o(n) but not k = Θ(n), we can still exploit the key idea of identifying items that are disguised independently of one another. We then apply an auxiliary result of [20] (Lemma 1 below) along with some "clean-up" steps to ensure that its assumptions remain valid each time it is invoked.
In the following, we let q = 1 − p for convenience. The following definition and theorem are from [20] . Definition 1. [20] We say that an item i is disguised in test t if at least one of the other items in the test is defective. We say that an item is totally disguised if it is disguised in every test it is included in. Let D i denote the event that item i is totally disguised.
It is noted in [20] that if an item is totally disguised, then we cannot distinguish between S and S {i}, where denotes symmetric difference. Hence, the best we can do is to choose the more likely between the two, and succeed with probability max {p, 1 − p} < 1.
[20, Eq. (1)] Define L(p) = min x=2,3,...,n x ln(1 − q x−1 ). If the test design X has no tests with 0 or 1 items, then
Hence, there exists an item i with ln P[D i ] ≥ T n ·L(p). Since L(p) = Θ(1) (and L(p) < 0), this result yields the weak converse after removing all tests with 0 or 1 items [20] . It is then natural to ask whether there are, in fact, many items i with ln P[D i ] close to the average. If we can find a set W of ω(1) such items, such that these items are totally disguised independently from each other, then we may apply standard binomial distribution concentration bounds to get ω(1) totally disguised items. Conditioned on this event, any algorithm can succeed with probability at most max {p, 1 − p} ω(1) = o(1).
, we construct a bipartite graph G X in which there is a vertex v i for each item i and a vertex v t for each test t, with an edge between v i and v t if item i is placed in test t. Before constructing the desired set W , we present two lemmas and two subroutines that will be useful.
Lemma 2. Let z = 2 ln 1 q , and suppose that T ≤ (1 − )n. The probability that there exists a negative test containing more than z ln n items is at most 1 n . Proof. Recalling that q = 1−p, each test containing at least z ln n items is negative with probability at most q z ln n = e z ln q ln n = 1 n 2
by the definition of z. Since T ≤ (1 − )n ≤ n, a union bound yields the desired result.
Subroutine 1: Clean(X).
1. Identify the set of tests T ≤1 containing 0 or 1 items, and the set of items I contained in at least one test in T ≤1 2. Return X ≥2 , defined to be X with the rows and columns indexed by T ≤1 and I removed.
Subroutine 2: Extract(X, W ).
1. Let E i be the event that i is totally disguised with respect to X. Let the item with the highest P[E i ] be denoted by i 0 , and add i 0 to W . 2. Let T close and I close denote the sets of tests and items within distance at most 4 from i 0 in G X . 3. Return X pruned , defined to be X with the rows and columns indexed by T close and I close removed.
We henceforth assume that no test contains more than z ln n items, since Lemma 2 implies that we may declare all such tests to be positive without increasing the error probability by more than 1 n → 0. Lemma 3. Define an item to be very-present if it appears in more than n 0.25 tests. If T < n and no test contains more than z ln n items, then there are no more than zn 0.75 ln n = o(n) very-present items.
Proof. We count the number P of pairs (i, t) such that item i is in test t. By assumption, P ≤ T z ln n < nz ln n. Letting n vp be the number of very-present items, we obtain n vp n 0.25 ≤ P < nz ln n, and rearranging yields the result.
We now introduce Subroutines 1 and 2. Clean removes all tests with 0 or 1 items, allowing us to apply Lemma 1, and Extract adds an item to W . Both will be called multiple times in the construction of W , and their calls will reduce the effective T and/or n (but we do not re-index items upon doing so).
The full procedure for constructing W is described in Procedure 1. For step 1, assume that there exists a genie that tells us the identity of the very-present items. Let the test results for G 0 and G 1 be y 0 and y 1 respectively; then, knowing X, we see that y 0 can be derived from y 1 and the genie information. If we can prove that the error probability tends to one even with the genie (and y 1 ), then it certainly tends to one without it, so step 1 is justified. After step 1, each item is contained in at most n 0.25 tests.
Let w i denote the i-th item placed in W . Let D wi be the event that w i is totally disguised w.r.t. X 1 , and E wi be the event that w i is totally disguised w.r.t. X tmp,i (see Procedure 1 for the relevant definitions).
Procedure 1: ConstructSet(X).
Repeat steps 3 and 4 until there are fewer than n/2 items in G i .
Since the events D wi only depends on the 2neighborhood of w i in G 1 , and the 2-neighborhoods of items in W are pairwise disjoint by construction (due to the Extract subroutine), the events {D w : w ∈ W } are independent (this independence for 4-separated nodes was also used in [19] ).
Next, we claim that P[D wi ] ≥ P[E wi ]. This is because in each Clean/Extract step, whenever we remove a test, we remove all of its items. It follows that w i is contained in the same tests in X 1 and X tmp,i , except that each such test in X tmp,i has fewer items, so E wi implies D wi . In addition, by the stopping condition of Procedure 1, each X tmp,i has at least n/2 items and fewer than n tests, i.e., the ratio of tests to items is at most 2 . Hence, the second part of Lemma 1 yields ln P[E wi ] ≥ 2 · L(p) =: L * .
It follows that P[D wi ] ≥ e L * , which is a constant less than one (since L * < 0). Hence, in accordance with the discussion following Lemma 1, it only remains to show that |W |= ω(1). To see this, it is useful to count the number of removed items:
• No more than T ≤ (1 − )n items alone in some test are removed by Clean; • Lemma 3 implies that we removed at most zn 0.75 ln n very-present items; • By the assumption stated following Lemma 2 and removal of very-present items, each call to Extract removes at most z 2 n 0.5 ln n items. Hence, the final number of items n final after line 5 of Procedure 1 satisfies n 2 > n final
≥ n − (1 − )n − zn 0.75 ln n − |W |z 2 n 0.5 ln 2 n (8)
≥ n − zn 0.75 ln n − |W |z 2 n 0.5 ln 2 n,
and rearranging yields |W | > n − 2zn 0.75 ln n 2z 2 n 0.5 ln 2 n = ω(1)
since z and are constant. This completes the proof. , we place each item in an ignore set I 0 independently with probability (1 − 0 )α for some arbitrarily small 0 ∈ (0, 1). Each item in I 0 is declared to be non-defective. We then adopt a near-constant column weight test-design, also used in [17] , [18] , i.e., we select with replacement, for each item i in I c 0 = [n]\I 0 , L tests to place i in, for a constant L to be chosen later. Equivalently, let {T i,l : i ∈ [n] \ L, 1 ≤ l ≤ L} be i.i.d. random variables following the uniform distribution over the set of tests: Item i is in test t whenever T i,l = t for some l. We again use COMP decoding; the only misclassified defectives will be those in the ignore set, and we have |S ∩ I 0 |≤ αk w.h.p. by the choice of probability of inclusion in I 0 .
A test t is negative if and only if, for all i ∈ S \ I 0 and all 1 ≤ l ≤ L, we have T i,l = t. Letting k = |S \ I 0 |, the probability (given S and I 0 ) that test t is negative is then 1 − 1 T k L , and we have
Changing a single value of T i,l changes the number of positive tests T + by at most one, so we can apply McDiarmid's inequality [27] to obtain w.h.p. that |T + − E[T + ]| = o(n). By comparison, E[T + ] = Θ(n) whenever T = Θ(n) and L = Θ(1), which can be assumed for the purposes of proving Theorem 4.
Conditioned on S, I 0 , and T + , a non-defective item i is classified incorrectly if and only if test T i,l is positive for all l; this happens independently from the other non-defective items, with probability (T + /T ) L . The expected number of misclassified items is thus E[|Ŝ \ S| | S, I 0 , T +] = |S c ∩ I 0 |·(T + /T ) L (12)
From the above, and the concentration of binomial variables, we get that w.h.p., the random variables |S \Ŝ|= |I ∩ S|, |([n] \ I) ∩ S|, T + and |Ŝ \ S| are within a (1 ± δ) factor of their means (for any δ > 0 and sufficiently large n), and furthermore, by applying the union bound to the complement events, they are simultaneously close to their means. Hence, using (11), (12) , and E[k ] = np(1−(1− 0 )α) ≤ np(1−α)(1+δ) (for sufficiently small 0 )), we have w.h.p. that
To simplify (13), we consider T = (1 − α)(1 + δ) 2 np · M (1+o(1)), for M to be chosen shortly, and a 1+o(1) term matching that in the expression 1− 1 T = e − 1+o (1) T . Then, (13) is upper bounded by αk provided that
Since L is an arbitrary integer, we can take the minimum over all possible values, and select M such that (14) holds with equality. Substituting into T = (1 − α)(1 + δ) 2 np · M (1 + o(1)) and noting that δ may be arbitrarily small, this completes the proof.
While our strong converse for exact recovery has a trivial matching achievability scheme (namely, individual testing [20] ), more significant gaps remain under the approximate recovery criterion. It is possible to adapt the analysis from [8] and [23, Thm. 7 ] to prove that a rate approaching 1 1−α as p → 0 is information-theoretically possible, but we found that the rate obtained via this approach drops to nearzero for extremely small p. It may be interesting to determine the extent to which the DD algorithm [16] , [17] or the spatial coupling type approach of [19] could attain stronger bounds.