Improved lower bound for estimating the number of defective items

Abstract Consider a set of items, X , with a total of n items, among which a subset, denoted as $$I\subseteq X$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>I</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> , consists of defective items. In the context of group testing, a test is conducted on a subset of items Q , where $$Q \subset X$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>⊂</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> . The result of this test is positive, yielding 1, if Q includes at least one defective item, that is if $$Q \cap I \ne \emptyset $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Q</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>I</mml:mi> <mml:mo>≠</mml:mo> <mml:mi>∅</mml:mi> </mml:mrow> </mml:math> . It is negative, yielding 0, if no defective items are present in Q . We introduce a novel method for deriving lower bounds in the context of non-adaptive randomized group testing. For any given constant j , any non-adaptive randomized algorithm that, with probability at least 2/3, estimates the number of defective items | I | within a constant factor requires at least $$\Omega \left( \dfrac{\log n}{\log \log {\mathop {\cdots }\limits ^{j}}\log n}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mfenced> <mml:mstyle> <mml:mfrac> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mover> <mml:mo>⋯</mml:mo> <mml:mi>j</mml:mi> </mml:mover> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:mfrac> </mml:mstyle> </mml:mfenced> </mml:mrow> </mml:math> tests. Our result almost matches the upper bound of $$O(\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and addresses the open problem posed by Damaschke and Sheikh Muhammad in (Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, pp 117–130, 2010; Discrete Math Alg Appl 2(3):291–312, 2010). Furthermore, it enhances the previously established lower bound of $$\Omega (\log n/\log \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> by Ron and Tsur (ACM Trans Comput Theory 8(4): 15:1–15:19, 2016), and independently by Bshouty (30th International Symposium on Algorithms and Computation, ISAAC 2019, LIPIcs, vol 149, pp 2:1–2:9, 2019). For estimation within a non-constant factor $$\alpha (n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , we show: If a constant j exists such that $$\alpha &gt;{\log \log {\mathop {\cdots }\limits ^{j}}\log n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mover> <mml:mo>⋯</mml:mo> <mml:mi>j</mml:mi> </mml:mover> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:mrow> </mml:math> , then any non-adaptive randomized algorithm that, with probability at least 2/3, estimates the number of defective items | I | to within a factor $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> requires at least $$\Omega \left( \dfrac{\log n}{\log \alpha }\right) .$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mfenced> <mml:mstyle> <mml:mfrac> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>α</mml:mi> </mml:mrow> </mml:mfrac> </mml:mstyle> </mml:mfenced> <mml:mo>.</mml:mo> </mml:mrow> </mml:math> In this case, the lower bound is tight.