Group testing is a classic problem where you want to find "defective" items (like infected people in a disease screening) by testing groups at once rather than one at a time. This paper focuses on a specific version: there are exactly two defective items, and each test tells you not just whether a group contains any defectives, but exactly how many (zero, one, or two). The goal is to identify which pair of items is defective using as few tests as possible. The structure of which pairs are possible is modeled as a "star forest," meaning the possible defective pairs look like a collection of stars, where each star has one central item connected to several others.
A mathematician named Aigner previously studied this problem and found a necessary condition for when a given star forest configuration can be searched within a fixed number of tests. This condition is expressed using "majorization," a mathematical way of comparing sequences by looking at how evenly or unevenly their values are distributed. Aigner proved that if a configuration is searchable, it must satisfy this majorization condition, and he conjectured that the reverse is also true: satisfying the condition would guarantee searchability. This paper disproves that conjecture. The authors construct an explicit example with six tests that satisfies Aigner's condition but cannot actually be solved within six tests, along with an infinite family of similar counterexamples for any larger test budget.
The key insight behind the failure is that two constraints on early test outcomes can become mutually incompatible, even though each looks fine individually. The authors also verify computationally, with supporting analytical arguments, that Aigner's conjecture does hold for five or fewer tests. So six is the precise threshold where majorization stops being a reliable guide. The counterexamples are clean and self-contained, independent of the computer verification, making the mathematical obstruction transparent.