Optimal non-adaptive probabilistic group testing in general sparsity regimes

In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that in the case of n items among which k are defective, the smallest possible number of tests equals min{C(k,n)k log n, n} up to lower-order asymptotic terms, where C-k,C-n is a uniformly bounded constant (varying depending on the scaling of k with respect to n) with a simple explicit expression. The algorithmic upper bound follows from a minor adaptation of an existing analysis of the Definite Defectives algorithm, and the algorithm-independent lower bound builds on existing works for the regimes k <= n(1-Omega(1)) and k = circle minus(n). In sufficiently sparse regimes (including k = o(n/lg n)),our main result generalizes that of Coja-Oghlan et al. (2020) by avoiding the assumption k <= n(1-Omega(1)), whereas in sufficiently dense regimes (including k = omega(n/log n)), our main result shows that individual testing is asymptotically optimal for any non-zero target success probability, thus strengthening an existing result of Aldridge (2019, IEEE Trans. Inf. Theory, 65, 2058-2061) in terms of both the error probability and the assumed scaling of k.