What is Group Testing?
Group testing is a method to identify defective items in a large population using fewer tests than items. Developed around 1943 by R. Dorfman in an adaptive version (allowing several rounds of testing), the method was later studied in a non-adaptive setting, where all tests are designed in advance and run in a single round.
The key idea is that each test is applied to a pool of samples, while each sample participates in multiple pools. The test is positive if and only if the pool contains at least one defective item. A binary matrix $G \in \mathbb{B}_2^{n \times k}$ encodes the assignment: rows are samples, columns are tests, and $G_{ij} = 1$ means sample $i$ participates in test $j$.
This page provides a mathematical introduction and an interactive tool for analysing group testing matrices. The material is based on joint work with J. V. Dinesen, D. Forbes, O. Gnilke, and C. Rößing. The algebraic framework rests on the theory of residuated mappings, as developed in Blyth & Janowitz, Residuation Theory, while the coding-theoretic background can be found in Guruswami, Rudra & Sudan, Essential Coding Theory. See the references for the full list.
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):
| $+$ | $0$ | $1$ |
| $0$ | $0$ | $1$ |
| $1$ | $1$ | $\mathbf{1}$ |
| $\cdot$ | $0$ | $1$ |
| $0$ | $0$ | $0$ |
| $1$ | $0$ | $1$ |
| $\oplus$ | $0$ | $1$ |
| $0$ | $0$ | $1$ |
| $1$ | $1$ | $\mathbf{0}$ |
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.
The order $0 < 1$ on $\mathbb{B}_2$ extends componentwise to $\mathbb{B}_2^n$: for $x, y \in \mathbb{B}_2^n$ we write $x \leq y$ if $x_i \leq y_i$ for all $i$, i.e., every component of $x$ that is $1$ is also $1$ in $y$. This makes $\mathbb{B}_2^n$ a distributive lattice, with join (coordinatewise OR) and meet (coordinatewise AND).
Let $(A, \leq)$ and $(B, \preceq)$ be partially ordered sets. A pair of mappings $(f, g)$ with $f: A \to B$ and $g: B \to A$ is called a residuated pair if $$f(a) \preceq b \;\Longleftrightarrow\; a \leq g(b) \quad\text{for all } a \in A,\; b \in B.$$ Here $f$ is called residuated and $g$ is called residual.
The componentwise negation on $\mathbb{B}_2$ is the order-reversing involution $\overline{0} = 1$, $\overline{1} = 0$ (logical complement). Unlike subtraction in $\mathbb{F}_2$, this is not an algebraic inverse for addition — it lies outside the semifield operations but is essential for expressing residuals.
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 negation is applied componentwise.
For any residuated mapping $f$ with residual $g$, the inequality $$g(f(x)) \;\geq\; x$$ holds componentwise for all $x \in \mathbb{B}_2^n$. The inequality may be strict: $g \circ f$ is not the identity in general, but it is always an upper bound for $x$.
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:
A group testing scheme $f: \mathbb{B}_2^n \to \mathbb{B}_2^k$ satisfies ($t$-sep) if $f$ is injective on vectors of weight at most $t$: whenever $x, y \in \mathbb{B}_2^n$ with $w_H(x) \leq t$, $w_H(y) \leq t$, and $f(x) = f(y)$, then $x = y$.
The scheme satisfies the stronger condition ($t$-dis) if: whenever $x, y \in \mathbb{B}_2^n$ with $w_H(x) \leq t$ and $f(x) = f(y)$, then $x = y$. Note that here only $x$ is required to have small weight — $y$ is arbitrary. ($t$-dis) is precisely the condition under which equality $g(f(x)) = x$ holds for all $x$ with $w_H(x) \leq t$: the residual identifies the infection pattern exactly, producing neither false negatives (missed defectives) nor false positives (healthy samples declared defective).
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:
The scheme represented by $G$ satisfies ($t$-dis) if and only if the residual mapping $g(y) = \overline{\,\overline{y} \cdot G^T}$ inverts $f$ on all $x \in \mathbb{B}_2^n$ with $w_H(x) \leq t$, i.e., $g(f(x)) = x$.
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.
Remarkably, the stronger property admits a more efficient verification. The interactive tool below uses this residuation-based approach.
A Small Example: a Binary Test Matrix
To fix ideas, consider the $5 \times 4$ binary matrix $G$ below, assigning 5 samples (A–E) to 4 test pools (1–4). Entry $G_{ij} = 1$ means sample $i$ participates in pool $j$.
| 1 | 2 | 3 | 4 | |
| A | 1 | 0 | 1 | 0 |
| B | 0 | 1 | 1 | 0 |
| C | 1 | 1 | 0 | 0 |
| D | 0 | 0 | 1 | 1 |
| E | 1 | 0 | 0 | 1 |
If samples A and C are defective, the infection pattern is $x = (1,0,1,0,0)$. The test outcome $y = xG$ over $\mathbb{B}_2$ is computed via coordinatewise logical OR: $$y_j \;=\; \bigvee_{i:\,x_i = 1} G_{ij}.$$ We obtain $y = \mathrm{row}_A \vee \mathrm{row}_C = (1,0,1,0) \vee (1,1,0,0) = (1,1,1,0)$: pools 1, 2, 3 are positive; pool 4 is negative.
This matrix is not $1$-disjunct — every pool is shared by at least two samples, so no individual defective can be recovered by the residual alone. Achieving $t$-disjunctness requires additional combinatorial structure. Finite geometries, introduced in a later section, provide precisely this, along with explicit formulas for the resulting error-correction performance.
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.
Incidence Structures and Designs
The most effective group testing matrices do not arise by chance — they are incidence matrices of finite geometries, combinatorial structures whose regularity translates directly into disjunctness and error-correction guarantees.
An incidence structure is a triple $(P, B, I)$ where $P$ is a finite set of points, $B$ a finite set of blocks, and $I \subseteq P \times B$ the incidence relation. The incidence matrix $M \in \{0,1\}^{|B| \times |P|}$ has $M_{bp} = 1$ if point $p$ is incident with block $b$.
For group testing we identify blocks with samples ($n = |B|$) and points with tests ($k = |P|$), so the incidence matrix $M$ serves directly as the generator matrix $G \in \mathbb{B}_2^{n \times k}$.
An incidence structure with $v = |P|$ points, blocks of constant size $k$, is a $t$-$(v, k, \lambda)$ design if every $t$-element subset of points is contained in exactly $\lambda$ blocks. The total block count is $$b \;=\; \lambda\,\binom{v}{t}\Big/\binom{k}{t}.$$ The regularity of a design constrains the row and column sums of $G$, which in turn controls the disjunctness and code distances of the associated group testing scheme.
Projective Geometry $\mathrm{PG}(d,q)$
Let $\mathbb{F}_q$ be the finite field of order $q$ ($q$ a prime power). The projective space $\mathrm{PG}(d, q)$ consists of all 1-dimensional subspaces (points) of $\mathbb{F}_q^{d+1}$, with point count $$v \;=\; \frac{q^{d+1}-1}{q-1} \;=\; 1 + q + q^2 + \cdots + q^d.$$ The hyperplanes of $\mathrm{PG}(d,q)$ are the $(d-1)$-dimensional projective subspaces; there are equally $v$ of them, so the points-vs-hyperplanes incidence matrix is square. Any two points lie together in $\tfrac{q^{d-1}-1}{q-1}$ hyperplanes, making this a $2$-design.
The Fano Plane $\mathrm{PG}(2,2)$
The smallest projective plane is $\mathrm{PG}(2,2)$, the Fano plane, with $v = 7$ points and $b = 7$ lines (hyperplanes in dimension 2). Each line contains 3 points and each point lies on 3 lines, forming a $2$-$(7,3,1)$ design: any two points determine a unique line. As a group testing matrix $G$ is $7 \times 7$; it is also the smallest Barbilian space $\mathrm{Barb}(2,2)$ (see below).
| Scheme | Design | $n \times k$ | max $t$ | $d_{\min}(C_1)$ | $d_{\min}(C_t)$ |
|---|---|---|---|---|---|
| $\mathrm{PG}(2,2)$ / Fano = $\mathrm{Barb}(2,2)$ | $2$-$(7,3,1)$ | $7 \times 7$ | $2$ | $3$ | $2$ |
Group Testing with Barbilian Spaces
Let $\mathbb{F}_q$ be a finite field and $n \geq 2$. The Barbilian space $\mathrm{Barb}(q, n)$ is the incidence structure of $\mathrm{PG}(n, q)$, taking its points as samples and its hyperplanes as tests. It forms a $2$-$\big(\frac{q^{n+1}-1}{q-1},\; \frac{q^n-1}{q-1},\; \frac{q^{n-1}-1}{q-1}\big)$ design with a square incidence matrix ($N = K$).
For a prime power $q$ and integer $n \geq 2$, let $G$ be an incidence matrix of $\mathrm{Barb}(q, n)$. Then:
- The scheme tests $N = \frac{q^{n+1}-1}{q-1}$ participants using $K = N$ tests.
- Its maximum disjunctness is $t = q$.
- The minimum distance of $C_t = B_N(t, 0) \cdot G$ is: $$d_\min \;=\; \begin{cases} \dfrac{q^n - 1}{q-1} & \text{if } t = 1,\\[6pt] q^{n-1} - (t-2)\,q^{n-2} & \text{if } 2 \leq t \leq q.\end{cases}$$
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.
| $t$ | $|C_t|$ | $d_\min$ | corrects |
|---|---|---|---|
| 1 | 32 | 15 | 7 tests |
| 2 | 497 | 8 | 3 tests |
Each row has weight 15 (about half). Maximum disjunctness $t = 2$. The dense pooling yields high redundancy: even $C_2$ corrects 3 faulty tests.
| $t$ | $|C_t|$ | $d_\min$ | corrects |
|---|---|---|---|
| 1 | 32 | 6 | 2 tests |
| 2 | 497 | 5 | 2 tests |
| 3 | 4,528 | 4 | 1 test |
| 4 | 32,768 | 3 | 1 test |
| 5 | 174,898 | 2 | detects 1 |
Each row has weight 6 (about one fifth). Maximum disjunctness $t = 5$. The sparse structure trades error-correction strength for a much higher disjunctness ceiling.
| $\mathrm{Barb}(2,\,4)$ | Dense. Maximum disjunctness $t = 2$, but powerful error correction: $d_{\min} = 8$ at $t = 2$. |
| $\mathrm{Barb}(5,\,2)$ | Sparse. Maximum disjunctness $t = 5$, but weaker error correction: $d_{\min} = 2$ at $t = 5$. |
| $I_{31}$ | Trivial. Maximum disjunctness $t = 31$, but $d_{\min} = 1$ for every $C_t$ — no error handling at all. Pooling is the mechanism that converts tests into redundancy. |
Summary of Barbilian Playground Presets
| Scheme | $n \times k$ | max $t$ | $d_{\min}(C_1)$ | $d_{\min}(C_t)$ |
|---|---|---|---|---|
| $\mathrm{Barb}(2,2)$ = Fano | $7\times 7$ | $2$ | $3$ | $2$ |
| $\mathrm{Barb}(2,3)$ | $15\times 15$ | $2$ | $7$ | $4$ |
| $\mathrm{Barb}(2,4)$ | $31\times 31$ | $2$ | $15$ | $8$ |
| $\mathrm{Barb}(5,2)$ | $31\times 31$ | $5$ | $6$ | $2$ |
Affine Geometry $\mathrm{AG}(d,q)$
The affine space $\mathrm{AG}(d,q)$ is obtained from $\mathrm{PG}(d,q)$ by removing a fixed hyperplane (the hyperplane at infinity) together with all its subspaces. It has $q^d$ affine points. The remaining subspaces, called $r$-flats for $r = 1, \ldots, d{-}1$, form natural families of blocks.
The affine plane $\mathrm{AG}(2, q)$ has $q^2$ points and $q^2 + q$ lines partitioned into $q+1$ parallel classes of $q$ lines each. The point–line incidence forms a $2$-$(q^2, q, 1)$ design: any two points determine a unique line. Taking lines as samples ($n = q^2 + q$) and points as tests ($k = q^2$) yields a rectangular matrix $G \in \mathbb{B}_2^{(q^2+q)\times q^2}$.
For $d \geq 3$, the $r$-flats of $\mathrm{AG}(d,q)$ for $r \in \{1, d{-}1\}$ provide further incidence matrices. The table below lists all affine playground presets; exact disjunctness and $d_{\min}$ values are computed interactively.
| Scheme | Blocks | $n \times k$ | Design |
|---|---|---|---|
| $\mathrm{AG}(2,4)$ | lines | $20\times 16$ | $2$-$(16,4,1)$ |
| $\mathrm{AG}(2,5)$ | lines | $30\times 25$ | $2$-$(25,5,1)$ |
| $\mathrm{AG}(2,7)$ | lines | $56\times 49$ | $2$-$(49,7,1)$ |
| $\mathrm{AG}(3,2)$ | lines | $28\times 8$ | |
| $\mathrm{AG}(3,2)$ | hyperplanes | $14\times 8$ | |
| $\mathrm{AG}(3,3)$ | lines | $117\times 27$ | |
| $\mathrm{AG}(3,3)$ | hyperplanes | $39\times 27$ | |
| $\mathrm{AG}(3,4)$ | hyperplanes | $84\times 64$ | |
| $\mathrm{AG}(4,2)$ | lines | $120\times 16$ | |
| $\mathrm{AG}(4,2)$ | $2$-flats | $140\times 16$ | |
| $\mathrm{AG}(4,2)$ | hyperplanes | $30\times 16$ |
Transversal Designs $\mathrm{TD}(k, n)$
A transversal design $\mathrm{TD}(k, n)$ is an incidence structure with $kn$ points partitioned into $k$ groups of $n$ and $n^2$ blocks, such that every block contains exactly one point from each group, and any two points from different groups appear together in exactly one block. It is a $1$-$(kn,\, k,\, 1)$ design.
For group testing: $n^2$ blocks serve as samples and $kn$ points as tests, giving $G \in \mathbb{B}_2^{n^2 \times kn}$.
Existence. $\mathrm{TD}(k, n)$ exists if and only if there are $k-2$ mutually orthogonal Latin squares (MOLS) of order $n$. In particular, whenever $n = p^r$ is a prime power and $k \leq n + 1$, a $\mathrm{TD}(k,n)$ can be constructed from the affine plane $\mathrm{AG}(2, n)$ by selecting $k$ of its $n+1$ parallel classes.
| Scheme | $n \times k$ matrix | samples | tests |
|---|---|---|---|
| $\mathrm{TD}(3,5)$ | $25\times 15$ | $25$ | $15$ |
| $\mathrm{TD}(4,5)$ | $25\times 20$ | $25$ | $20$ |
| $\mathrm{TD}(5,5)$ | $25\times 25$ | $25$ | $25$ |
| $\mathrm{TD}(3,7)$ | $49\times 21$ | $49$ | $21$ |
| $\mathrm{TD}(4,7)$ | $49\times 28$ | $49$ | $28$ |
| $\mathrm{TD}(k, 11)$, $3\leq k\leq 12$ | $121\times 11k$ | $121$ | $11k$ |
| $\mathrm{TD}(k, 13)$, $k\in\{3,4,5,6,7,10\}$ | $169\times 13k$ | $169$ | $13k$ |
Exact disjunctness and $d_{\min}$ values for each preset are computed interactively by the playground below.
Circle Geometries and Inversive Planes
An inversive plane of order $q$ is a $3$-$(q^2+1,\, q+1,\, 1)$ design: $q^2+1$ points and $q(q^2+1)$ blocks called circles, each circle containing $q+1$ points, such that any three points determine a unique circle. For group testing: circles as samples ($n = q(q^2+1)$), points as tests ($k = q^2+1$).
The Möbius Plane $\mathbb{M}_2$
The smallest inversive plane is $\mathbb{M}_2$ of order $q = 2$: a $3$-$(5, 3, 1)$ design with 5 points and 10 circles. Its incidence matrix provides a $(10, 5)$-group testing scheme with maximum disjunctness $t = 1$, identifying a single defective among 10 samples using only 5 tests.
Drawing by Cornelia Rößing †
| 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 = circles/samples (1–10), columns = points/tests (A–E).
| Scheme | $n \times k$ | max $t$ | $d_{\min}(C_1)$ | error handling |
|---|---|---|---|---|
| $\mathbb{M}_2$ | $10\times 5$ | $1$ | $2$ | detects 1 error |
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.
Enter a binary matrix (rows separated by newlines, entries by spaces or commas). Loads automatically when you stop typing or leave the field.
Select or enter a matrix to begin.
References
- [1] R. Dorfman, The detection of defective members of large populations, Ann. Math. Statist. 14 (1943), 436–440.
- [2] G. O. H. Katona, Combinatorial Search Problems, in: A Survey of Combinatorial Theory, North-Holland, 1973, 285–308.
- [3] T. S. Blyth and M. F. Janowitz, Residuation Theory, Pergamon Press, 1972.
- [4] V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory, 2021.
- [5] J. V. Dinesen, O. W. Gnilke, M. Greferath, C. Rößing, Group testing via residuation and partial geometries, Advances in Mathematics of Communications 19 (2025), 397–405.
- [6] M. Greferath and C. Rößing, Group Testing with Error-Correction Capabilities for General Pandemics, Elsevier IFAC-Papers OnLine 55 (2022), 295–298.