Aigner's majorization conjecture in quantitative group testing: counterexamples and eventual sufficiency for star forests

arXiv:2609.38284 · math.CO · Submitted 2026-09-29 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Aigner's majorization conjecture in quantitative group testing".

Emmy: Here's the gist of the paper. In adaptive quantitative group testing with exactly two defective items, each test reports how many defectives lie in a chosen subset, this paper disproves Aigner’s conjecture by providing an explicit six-test counterexample and an analytic family of counterexamples for every test budget k ≥ 6.

Ada: The core problem and conjecture The study focuses on configurations in which the possible defective pairs form the edges of a star forest.

Emmy: Aigner proved a necessary majorization condition on the ordered star sizes for identifying the defective pair within a prescribed number of tests, and conjectured that this condition was sufficient.

Ada: Theorem 1.1 states that if M(F(a)) ≤ k, then a ⪯w N(k).

Title and authors: Ada: So what exactly is this paper saying about Aigner's work? It seems like they're not just finding a small counterexample, but proving something much bigger about the structure of these search problems.

Emmy: They are looking at configurations where the possible defective pairs form the edges of a star forest, and they are showing that even with that specific structure, Aigner's majorization condition isn't sufficient.

Kolya: It’s interesting because Aigner showed a necessary condition, which is like saying you have to have certain properties if you want to succeed in finding the pair within k tests. But this paper shows those properties can be met without actually being able to find the pair within that budget.

Ada: And they build on this by showing that for every test budget k greater than or equal to six, there's a partition of star sizes that meets Aigner's necessary condition but still fails the sufficiency requirement.

Emmy: They give us an explicit example for six tests and then they give us a way to generate all those other examples by changing some parts of the partition in a structured way.

The paper's summary: Ada: Let's look at the core argument they are making here. The paper is essentially disproving Aigner's conjecture by providing concrete counterexamples and then generalizing it to an infinite family of counterexamples for any test budget k greater than or equal to six.

Emmy: The core problem they tackle is that the way we organize the possible defective pairs, which they call a star forest, allows for certain combinations of those pairs to look good on paper according to Aigner's majorization condition, but in reality, it means you can't find the pair within k tests.

Kolya: They use this structure—the star forest—to build the obstruction. For example, they show that by looking at three contributions from certain rows in their setup, you get a bound that is six times something related to the total size of those components, which means no first test can leave all three children solvable in only five tests.

Ada: So what does this mean for the listener who just wants to know what's happening? It means that even if your structure looks promising according to a certain rule, it doesn't guarantee you can solve the problem within that budget of tests.

The paper's improvements: Ada: The authors suggest some things for future research or for clarifying this result. They point out that the simple prefix-sum capacity isn't enough to fully characterize solvable star-forest search because at a single tight rank, the child capacities can be compatible in ways that don't lead to a solution.

Emmy: They suggest that maybe we need some additional structural conditions beyond just the majorization condition to get a proper characterization of solvable forests. It implies that the structure itself needs more specific constraints than what Aigner initially provided was sufficient for.

Kolya: And they do provide a way to check if a state is solvable in five tests using analytic reductions and exhaustive computation, which is important because it separates the case where the conjecture fails from the cases where it holds up to five tests.

Ada: That computational part with five tests is really interesting because it's not just theory; they actually ran a massive census of partitions, over one point four billion such partitions, just to confirm that for k less than six, the conjecture actually does hold.

Conclusion: Ada: So to wrap this up, the paper "Aigner's majorization conjecture in quantitative group testing: counterexamples and eventual sufficiency for star forests" shows that Aigner's necessary condition is not enough for sufficiency when you have a star forest of defect pairs. They provide an explicit six-test counterexample and then an infinite family of them for any budget k greater than or equal to six.

Emmy: The implication here is that the structure of the search problem, specifically how the defect pairs connect in a star forest, matters more than just the size constraints alone when it comes to determining if you can solve it within a test budget.

Kolya: Kolya thinks that this result really shows where the complexity lies—it's in those specific structural arrangements that allow for those tight prefix sums to create incompatible demands on the outcomes of the first test, which is what creates the obstruction.

Ada: And Kolya makes a good point about how they pinpointed that exact mechanism leading to failure. We're going to take a quick break and then talk about some of those other papers we've been looking at.

Fedor Karpelevitch

math.CO

Submitted: 2026-09-29

Updated: 2026-11-06

Comments: 32 pages. Substantially expanded revision: analytic five-test converse, eventual sufficiency, sharp support bounds and delayed obstructions. Evidence: https://doi.org/10.5281/zenodo.23996063

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: In adaptive quantitative group testing with exactly two defective items, each test reports how many defectives lie in a chosen subset…

Key concepts

Star Forest Configurations
These are specific arrangements of potential defective pairs where the structure resembles a star forest. The study focuses on how the sizes of these stars relate to each other, as this structure is central to testing solvability within a given number of tests.
Majorization Condition ($M(F(a))$)
This is a necessary mathematical condition derived by Aigner that must be met for a star forest configuration $F(a)$ to be solvable within $k$ tests. The paper shows this condition is not enough, as there are configurations where the majorization holds but the number of tests required exceeds $k.
Analytic Family of Counterexamples
The authors construct an infinite set of specific test configurations for any budget $k ext{ ≥ 6}$. This construction preserves key properties like mass and majorization while deliberately forcing a violation of capacity inequalities, proving that the conjecture fails for all budgets greater than or equal to six.

Terminology

Summary

In adaptive quantitative group testing with exactly two defective items, each test reports how many defectives lie in a chosen subset, this paper disproves Aigner’s conjecture by providing an explicit six-test counterexample and an analytic family of counterexamples for every test budget k ≥ 6. p. 0

The core problem and conjecture

The study focuses on configurations in which the possible defective pairs form the edges of a star forest. Aigner proved a necessary majorization condition on the ordered star sizes for identifying the defective pair within a prescribed number of tests, and conjectured that this condition was sufficient. p. 0 Theorem 1.1 states that if M(F(a)) ≤ k, then a ⪯w N(k). p. 0 However, the paper demonstrates that for each k ≥ 6 there is a partition a ⪯w N(k) with M(F(a)) > k. p. 5

The six-test obstruction

The authors present an explicit six-test counterexample F(P) where P = (64, 63, 57[2], 42[4], 22[7], 8[15], 7[2], 1[32]). This example exhibits the obstruction because the bounding of three contributions from these t rows gives X t i=1 Pi ≤ H(pt) + H(t) + H(t − pt) ≤ H6(t). p. 3 The analysis shows that no first test leaves all three children solvable in five tests, leading to M(F(P)) > 6. p. 3

Generalizing the counterexamples

The authors provide an analytic family of counterexamples for every test budget k ≥ 6. For k = 2m or 2m + 1, m ≥ 3, they construct a partition ak by replacing a canonical band with b = ((q + 1)[r], q[L−r]). p. 3 This construction preserves mass and majorization while forcing two symmetric transitions that violate a pure-child capacity inequality. p. 3 The resulting expression F > Q(n) for both parities at every m ≥ 5, proving the failure at every greater budget. p. 3

The converse through five tests

The sufficiency statement through five tests is proven using a combination of analytic reductions and exhaustive computation. This involves reducing star forests majorized by N(k) to full-mass partitions with exactly 2k positive rows. p. 3 A Hall criterion is established for a fixed choice of each row's pure side, leading to the inequality Lp + Rq ≤ H(p) + H(p + q) + H(q). The complete lower-level census supports this by showing that all resulting children are solvable at the preceding level. p. 3

Computational verification

The converse relies on a complete exhaustive census of 5-test runs, which accounts for 1,431,800,647,444 such partitions. This computation is not a consequence of the analytic lemmas alone but serves as a computational premise for the exact-threshold statement. p. 4 The paper provides source identity and reproduction scope for this census in Appendix C. p. 1

Discussion and implications

The obstruction demonstrates that prefix-sum capacity alone does not characterize star-forest search, as at a single tight rank the child capacities can be compatible. The authors suggest that additional structural conditions might yield a useful characterization of solvable forests. p. 4 The analytic family does not determine the smallest counterexample by mass or support. p. 4

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI systems can utilize Aigner's necessary majorization condition as a simple criterion for recognizing solvable star-forest states without further recursive search, as suggested by the paper: Aigner proved a necessary majorization condition on the ordered star sizes for identifying the defective pair within a prescribed number of tests, and conjectured that this condition was sufficient.

  2. The system can perform exact verification of solvability up to five tests by combining analytic reductions with a complete exhaustive computation, as described in Section 4: The sufficiency statement through five tests is computer-assisted. It is needed to locate the first failure, but not to disprove the conjecture.

  3. The AI can leverage the transcript graph characterization for search states by using Lemma 2.1: The forest F(a) is solvable in at most k tests if and only if Qk contains pairwise disjoint stable sets of sizes a1, a2,.... This allows the system to construct a depth-k strategy by assigning words of prescribed stable sets to leaves.

  4. The system can generate analytic counterexamples for any test budget k greater than or equal to 6 using the infinite family theorem: "For each k ≥ 6 there is a partition a ⪯w N(k) with M(F(a)) > k." This provides a complete set of states that are unsolvable within budget k, regardless of computational limits.

  5. The system can employ the fixed-orientation Hall criterion to check for legal first cuts: This coloring admits a legal first cut into three h-majorized children if and only if Lp + Rq ≤ H(p) + H(p + q) + H(q). This provides an exact decision procedure for whether a given state allows a successful first test.

Related papers