Improved Lower Bound for Estimating the Number of Defective Items

Let X be a set of items of size n that contains some defective items, denoted by I, where \(I \subseteq X\) . In group testing, a test refers to a subset of items \(Q \subset X\) . The outcome of a test is 1 if Q contains at least one defective item, i.e., \(Q\cap I \ne \emptyset \) , and 0 otherwise. We give a novel approach to obtaining lower bounds in non-adaptive randomized group testing. The technique produced lower bounds that are within a factor of \(1/{\log \log {\mathop {\cdots }\limits ^{k}}\log n}\) of the existing upper bounds for any constant k. Employing this new method, we can prove the following result. For any fixed constants k, any non-adaptive randomized algorithm that, for any set of defective items I, with probability at least 2/3, returns an estimate of the number of defective items |I| to within a constant factor requires at least \(\varOmega \left( \frac{\log n}{\log \log {\mathop {\cdots }\limits ^{k}}\log n}\right) \) tests. Our result almost matches the upper bound of \(O(\log n)\) and solves the open problem posed by Damaschke and Sheikh Muhammad in [8, 9]. Additionally, it improves upon the lower bound of \(\varOmega (\log n/\log \log n)\) previously established by Ron and Tsur [21] and independently by Bshouty [2].