Group Testing

The Boolean Semifield $\mathbb{B}_2$

Consider the lattice $\mathbb{B}_2 := \{0, 1\}$ with order $0 < 1$. Its sup and inf operations give it the structure of a semifield, with addition $+$ (logical OR) and multiplication $\cdot$ (logical AND):

The critical difference is highlighted: in $\mathbb{B}_2$ we have $1 + 1 = 1$ (gold), whereas in the Galois field $\mathbb{F}_2$ we have $1 \oplus 1 = 0$ (red). Over $\mathbb{B}_2$, there is no additive inverse, and hence no Gaussian elimination. This necessitates a different algebraic framework — residuation theory.

A mapping $f: \mathbb{B}_2^n \to \mathbb{B}_2^k$ is $\mathbb{B}_2$-linear if and only if it is residuated. If $f$ is represented by an $n \times k$ matrix $G$ (i.e., $f(x) = xG$), then its residual $g$ is given by $$g(y) \;=\; \overline{\,\overline{y} \cdot G^T\,},$$ where $\overline{(\cdot)}$ denotes componentwise negation.

Noiseless Group Testing

In the noiseless model, each test yields a perfectly reliable result. A binary vector $x \in \mathbb{B}_2^n$ represents the infection pattern ($x_i = 1$ if sample $i$ is defective). The test outcome is $y = xG \in \mathbb{B}_2^k$, computed over $\mathbb{B}_2$.

A central question is: can we recover $x$ from $y$, at least when the number of defectives is bounded? We write $w_H(x)$ for the Hamming weight of $x$ — the number of non-zero coordinates of $x$ — which equals the number of defective samples in the pattern $x$. Two conditions on $f$ capture recoverability, and their distinction is both subtle and important:

Both conditions are monotone: ($t$-dis) implies ($s$-dis) for all $s \leq t$, and likewise for ($t$-sep). This is immediate from the definitions, since $w_H(x) \leq s$ implies $w_H(x) \leq t$. We therefore speak of the maximum disjunctness of a scheme — the largest $t$ for which ($t$-dis) holds.

The condition ($t$-sep) merely says that different infection patterns of weight $\leq t$ produce different test outcomes — the mapping is invertible in principle. The condition ($t$-dis) is strictly stronger: it guarantees that no vector outside the Hamming ball can collide with one inside it. This has a decisive practical consequence:

In other words: ($t$-dis) is equivalent to the existence of an efficient, constructive decider — the residual mapping $g$, which directly determines which items are defective. Under ($t$-sep) alone, a unique solution exists but there is no guarantee that the residual (or any efficient algorithm) can find it.

A scheme satisfying ($t$-dis) may produce false positives (declaring a healthy sample as defective) but never false negatives (missing a truly defective sample).

A Small Example: the Möbius Plane $\mathbb{M}_2$

The inversive plane $\mathbb{M}_2$ is a $3$-$(5, 3, 1)$ design with 5 points and 10 blocks (circles). Each circle passes through exactly 3 points, and any 3 points determine a unique circle. Its incidence matrix provides a $(10, 5)$-group testing scheme with maximum disjunctness $t = 1$, identifying a single defective among 10 using only 5 tests.

$\mathbb{M}_2$: 5 points (A–E) and 10 circles (1–10).
Drawing by Cornelia Rößing †

Incidence matrix $G$ (samples × tests):

	A	B	C	D	E
1	1	0	1	0	1
2	0	1	1	1	0
3	1	1	0	0	1
4	1	0	0	1	1
5	1	1	0	1	0
6	0	1	0	1	1
7	1	1	1	0	0
8	1	0	1	1	0
9	0	0	1	1	1
10	0	1	1	0	1

Rows = samples (1–10), columns = tests (A–E).
Entry $1$: sample participates in pool.
Maximum disjunctness $t = 1$: any single
defective is recovered by the residual $g$.

Noisy Group Testing

In practice, tests may be unreliable. Experience with antigen tests during the COVID-19 pandemic shows that false-positive rates around 2% and false-negative rates exceeding 20% are realistic. We model test errors using the Hamming distance on $\mathbb{B}_2^k$. This is admittedly a simplification: the Hamming metric treats false positives and false negatives as equally costly, whereas in reality they arise with markedly different probabilities. A non-symmetric distance function — analogous to the Z-channel metric familiar from information theory — would be the more faithful model. Developing a full theory of group testing based on such an asymmetric metric remains an open research problem.

Remark. Lack of reliability is often associated with cheap tests: a less expensive assay tends to be less accurate. Error-correcting group testing offers a practical trade-off — it can compensate for reduced reliability without requiring one to pay for more expensive, higher-accuracy tests.

Caveat: Over $\mathbb{B}_2$, the Hamming distance does not enjoy all its familiar properties — in particular, it is not translation-invariant, since $\mathbb{B}_2$ has no subtraction. At least the following expression remains valid: $$d_H(x, y) \;=\; w_H(x) + w_H(y) - 2\,w_H(x \cdot y),$$ where $x \cdot y$ denotes the coordinatewise (Schur/Hadamard) product.

Codes over $\mathbb{B}_2$

Given a generator matrix $G \in \mathbb{B}_2^{n \times k}$ and a parameter $t$, we define the code $$C_t \;=\; B_n(t, 0) \cdot G \;=\; \{x G \mid x \in \mathbb{B}_2^n,\; w_H(x) \leq t\},$$ where $B_n(t, 0)$ is the Hamming ball of radius $t$ around the origin. The minimum distance $d_\min(C_t)$ determines the error-correction capability: up to $e = \lfloor(d_\min - 1)/2\rfloor$ faulty test results can be corrected.

As $t$ increases, the codes are nested: $\{0\} = C_0 \subseteq C_1 \subseteq \cdots \subseteq C_n$, and their minimum distances decrease — identifying more defectives leaves less room for error correction.

Group Testing with Barbilian Spaces

Why not insist on $K \ll N$?

In classical noiseless group testing, the primary goal is to minimise the number of tests $K$ relative to the number of participants $N$. This remains a valid and important objective. However, when tests are unreliable, the scheme must carry redundancy to enable error detection or correction — and redundancy requires additional tests. Depending on the error probability and the desired correction capability, this may lead to $K$ close to $N$, equal to $N$, or even $K > N$.

The Barbilian spaces happen to produce schemes with $K = N$, a consequence of the inner symmetry of the underlying projective geometry (points and hyperplanes are equinumerous). They are one family of examples — not the final word on the matter. In general, the problem of minimising $K$ subject to a given $t$-disjunctness and a given error-correction guarantee remains wide open.

To appreciate the value of pooling, consider the trivial alternative: the $N \times N$ identity matrix $I_N$ also has $K = N$ and maximum disjunctness $t = N$ — it identifies any number of defectives. Yet its codes $C_t$ have $d_\min = 1$ for every $t \geq 1$: a single faulty test causes misidentification with no possibility of detection. Pooling is the mechanism that converts tests into redundancy and hence into robustness.

Two Examples at $N = 31$: Dense vs. Sparse

The following two Barbilian schemes both operate on $N = 31$ participants with $K = 31$ tests, but with strikingly different characteristics. Their incidence matrices are circulant, generated by a single row.

Error-Correcting Group Testing Playground (ECGT)

Select a pre-loaded matrix or enter your own. The analyser computes the maximum $t$-disjunctness and the minimum distance of the associated codes $C_t$. Once the matrix is analysed, the ECGT simulation lets you choose an infection pattern $x$, introduce test errors, and watch the decoder recover $x$ — or fail when too many errors are present.