Error-Correcting Group Testing based on Residuation and Finite Geometries

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 $+$ (Boolean sum) and multiplication $\cdot$ (Boolean product):

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 $+$) and meet (coordinatewise $\cdot$).

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.

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 statement that the residual mapping $g$ itself serves as an efficient, constructive decider — it directly recovers the infection pattern without any further search. Under ($t$-sep) alone, a unique solution exists in principle, but the residual is not guaranteed to find it.

A Small Example: a Binary Test Matrix

The $10 \times 6$ matrix $G$ below assigns 10 samples (1–10) to 6 test pools (A–F). Entry $G_{ij} = 1$ means sample $i$ participates in pool $j$.

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. Whether and how such an asymmetric metric can be integrated into the residuation-based framework is a natural question for further investigation.

Remark. Lack of reliability is often associated with inexpensive 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.

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$.

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 test matrix $G \in \mathbb{B}_2^{N \times K}$, used here as the generator matrix of a Boolean code, and a non-negative integer $s$, we define the code $$C_s \;=\; B_N(s, 0) \cdot G \;=\; \{x G \mid x \in \mathbb{B}_2^N,\; w_H(x) \leq s\},$$ where $B_N(s, 0)$ is the Hamming ball of radius $s$ around the origin. The minimum distance $d_\min(C_s)$ determines the error-correction capability: up to $e = \lfloor(d_\min - 1)/2\rfloor$ faulty test results can be corrected.

As $s$ ranges from $0$ to $N$, these codes form a nested chain: $$\{0\} \;=\; C_0 \;\subseteq\; C_1 \;\subseteq\; \cdots \;\subseteq\; C_N \;=\; \langle G \rangle,$$ where $\langle G \rangle \subseteq \mathbb{B}_2^K$ denotes the row space of $G$, with minimum distances decreasing along the chain — identifying more defectives leaves less room for error correction. In practice we stop at $s = t$, the target disjunctness level, since larger $s$ adds codewords that cannot be decoded by residuation.

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 matrix is determined by $(P, \mathcal{B}, I)$ only up to permutations of its rows and columns (relabellings of blocks and points); it is therefore not unique in the strict sense. The dual of $(P, \mathcal{B}, I)$ is the incidence structure $(\mathcal{B}, P, I^*)$ with $I^* = \{(B, p) : (p, B) \in I\}$; its incidence matrix is $M^T$.

For group testing we identify blocks with samples ($N = b$) and points with tests ($K = v$), so any incidence matrix $M$ serves directly as the test matrix $G = M \in \mathbb{B}_2^{N \times K}$. Passing to the dual yields $G = M^T$, giving a GT scheme on the same geometry with points as samples and blocks as tests. Both orientations may be used in practice.

Projective Geometry $\mathrm{PG}(d,q)$

For a prime power $q$, let $\mathbb{F}_q$ be the finite field of order $q$. The projective space $\mathrm{PG}(d, q)$ is the incidence structure $(P, \mathcal{B}, I)$, where $P$ is the set of all 1-dimensional subspaces (points), $\mathcal{B}$ is the set of all 2-dimensional subspaces (lines) of $\mathbb{F}_q^{d+1}$, and $I = \{\,(p, L) : p \subseteq L\,\}$ is subspace containment. The point count and line count are, respectively, $$v \;=\; \frac{q^{d+1}-1}{q-1}, \qquad b \;=\; \frac{(q^{d+1}-1)(q^d-1)}{(q-1)(q^2-1)}.$$ Each line contains exactly $q+1$ points, and any two distinct points determine a unique line, making $(P, \mathcal{B}, I)$ a $2$-$\!\left(v,\; q+1,\; 1\right)$ Steiner system. Two natural families of subspaces serve as blocks for GT schemes.

The Fano Plane $\mathrm{PG}(2,2)$

The smallest projective space that is not a single line is known as the Fano plane $\mathrm{PG}(2,2)$. It contains $v = 7$ points and $b = 7$ lines, each line passing through exactly $3$ points and each point lying on exactly $3$ lines. It hence forms a $2$-$(7,3,1)$ Steiner system $(P, \mathcal{B}, I)$; as $d=2$, this structure is self-dual, and therefore both GT orientations yield the same $7 \times 7$ matrix. The Corollary gives $2$-disjunctness, confirmed in the playground.

Scheme	Design	$N \times K$	max disjunctness	$d_{\min}(C_1)$	$d_{\min}(C_2)$
$\mathrm{PG}(2,2)$ / Fano	$2$-$(7,3,1)$	$7 \times 7$	$2$	$3$	$2$

Lines as samples for GT

With lines as samples ($N = b$) and points as tests ($K = v$), the Corollary applies with $t = 2$ and $k = q+1$:

Hyperplanes as samples for GT

The hyperplanes of $\mathrm{PG}(d,q)$ are the $(d-1)$-dimensional projective subspaces; there are again $$v \;=\; \frac{q^{d+1}-1}{q-1}$$ of them, so the incidence matrix $M$ is square ($N = K = v$). Any two points lie together in $\lambda = \frac{q^{d-1}-1}{q-1}$ hyperplanes, making this a $2$-design that is not a Steiner system in general, so that the Corollary does not directly apply. This family is studied in depth as Barbilian spaces in the next section.

Group Testing with Barbilian Spaces

Remark (Prior work). The bound $t = q$ for $d \geq 3$ was obtained independently by D'yachkov, Hwang, Macula, Vilenkin, and Weng [7] as a special case of their Corollary 4.8, via the containment matrix $M(d{+}1,\, d,\, 1)$ of points and hyperplanes in $\mathrm{PG}(d, q)$. Their argument requires $d \geq 3$ and does not address the case $d = 2$, nor the minimum distances of $C_t$ at each level.

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.

Code Properties by Scheme

Highlighted rows: maximum disjunctness level. Values for $\mathrm{Barb}(2,2)$–$\mathrm{Barb}(4,2)$ confirmed by both the Forbes–Gnilke–Greferath theorem and direct computation. Values for $\mathrm{Barb}(2,5)$ from direct computation (corrected from earlier FGG estimates).

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 $v = q^d$ affine points. The remaining subspaces, called $r$-flats for $r = 1, \ldots, d{-}1$, form natural families of blocks; incidence is again subspace containment. For each choice of $r$, the incidence structure $(P, \mathcal{B}_r, I_r)$ of affine points and $r$-flats yields a GT scheme with $r$-flats as samples and points as tests.

The affine plane $\mathrm{AG}(2, q)$ has $v = q^2$ points and $b = q^2 + q$ lines, partitioned into $q+1$ parallel classes of $q$ lines each. Any two points determine a unique line, making the line incidence structure a $2$-$(q^2, q, 1)$ Steiner system. With lines as samples ($N = q^2+q$) and points as tests ($K = q^2$), the Corollary applies with $t = 2$ and $k = q$:

For $d \geq 3$, the $r$-flats of $\mathrm{AG}(d,q)$ for $r \in \{1, d{-}1\}$ provide further GT schemes. The table below lists all affine playground presets; exact disjunctness and $d_{\min}$ values are listed in the table below.

Highlighted rows: maximum disjunctness. All $t_{\max}$ values confirm the Corollary ($t_{\max} = q-1$ for $\mathrm{AG}(2,q)$ lines).

Transversal Designs $\mathrm{TD}(k, n)$

With blocks as samples ($N = n^2$) and points as tests ($K = kn$), the test matrix is $G = M \in \mathbb{B}_2^{n^2 \times kn}$. Since $\mathrm{TD}(k,n)$ is a $1$-design (not a Steiner system for $t\geq 2$), the Corollary does not directly apply; disjunctness is determined computationally.

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.

Highlighted rows: maximum disjunctness.

Circle Geometries

The three classical Benz circle geometries — inversive (Möbius) planes, Laguerre planes, and Minkowski planes — arise as incidence structures associated with the three types of quadratic ring extensions of $\mathrm{GF}(q)$: the field extension $\mathrm{GF}(q^2)$, the dual-number ring $\mathrm{GF}(q)[\varepsilon]$, and the split extension $\mathrm{GF}(q)\times\mathrm{GF}(q)$, respectively. Each geometry yields a family of highly structured group-testing schemes whose properties are investigated below.

Inversive Planes (Möbius Planes) $\mathbb{M}_q$

An inversive plane of order $q$ is an incidence structure $(P, \mathcal{B}, I)$ with $|P| = q^2+1$ points and $|\mathcal{B}| = q(q^2+1)$ blocks called circles, each circle containing $q+1$ points, such that any three points determine a unique circle. It forms a $3$-$(q^2+1,\, q+1,\, 1)$ Steiner system. With circles as samples ($N = q(q^2+1)$) and points as tests ($K = q^2+1$), the Corollary applies with $t = 3$ and $k = q+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.

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

Incidence matrix $G$ (circles × points):

	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).

Highlighted rows: maximum disjunctness $t_{\max} = \lfloor q/2 \rfloor$.

Laguerre Planes $\mathbb{L}_q$

A Laguerre plane of order $q$ has $v = q^2+q$ points and $b = q^3$ circles, each circle containing $k = q+1$ points. Unlike inversive planes, Laguerre planes carry a parallelism relation partitioning the $q^2$ affine points into $q$ generator classes of $q$ points each.

Highlighted rows: maximum disjunctness.

Minkowski Planes $\mathbb{K}_q$

A Minkowski plane of order $q$ has $v = (q+1)^2$ points and $b = q(q^2-1)$ circles, each circle containing $k = q+1$ points. The point set carries two families of $q+1$ generators (rulings), and circles meet each generator in exactly one point.

Highlighted rows: maximum disjunctness.

Generalized Polygons

With lines as samples ($N = |\mathcal{L}|$) and points as tests ($K = |P|$), the incidence matrix $G = M \in \mathbb{B}_2^{N \times K}$ defines a GT scheme. A GQ is a partial geometry $\mathrm{pg}(s, t, 1)$ with parameter $\alpha = 1$: through any point outside a line, exactly one line meets it. The disjunctness result below is the special case $\alpha = 1$ of the general partial geometry result of [5].

Proof. Two distinct lines share at most one point, so any $d \leq s$ lines cover at most $d \leq s < s+1$ points of any given line $L$, leaving at least one point of $L$ uncovered. For sharpness: fix $L$ with points $p_0, \ldots, p_s$; since $t \geq 1$ there is a second line $L_i \neq L$ through each $p_i$. The lines $L_0, \ldots, L_s$ together cover all points of $L$, so the scheme is not $(s+1)$-disjunct. $\square$

Classical Families

For $q$ even: $\mathrm{W}(q) \cong \mathrm{Q}(4,q)$. For $q$ odd: $\mathrm{W}(q)$ and $\mathrm{Q}(4,q)$ are non-isomorphic but dual to each other.

Note that $\mathrm{W}(2)$ and $\mathrm{Barb}(3,2)$ are both $15 \times 15$ GT schemes with the same maximum disjunctness $t = 2$, yet are fundamentally different: $\mathrm{W}(2)$ has lines of size $3$ and is not a $2$-design, while $\mathrm{Barb}(3,2)$ has blocks of size $7$ and is a $2$-$(15,7,3)$ design.

The same disjunctness argument applies to any incidence structure in which two distinct blocks share at most one point — this includes not only GQs but also generalised hexagons and other generalised polygons. The split Cayley hexagon $\mathrm{G}_2(3)$ of order $(3,3)$ has $N = K = 364$, block size $4$, and maximum disjunctness $t = 3$. Its automorphism group $\mathrm{G}_2(3)$ of order $4{,}245{,}696$ makes orbit-based code computation feasible despite the large matrix size.

Code Properties by Scheme

Highlighted rows: maximum disjunctness level ($t_{\max} = s$). $^\dagger$ $d_{\min}$ not computed (GPU memory exceeded); values extrapolated from the observed pattern $d_{\min}(C_t) = s+2-t$ (confirmed for $t = 1,\ldots,4$). Compare $\mathrm{W}(2)$ with $\mathrm{Barb}(3,2)$: same $N = K = 15$, $t_{\max} = 2$, $|C_t|$, but $d_{\min} = 7$ and $4$ for Barb vs.\ $3$ and $2$ for $\mathrm{W}(2)$ — substantially better error correction from the Barbilian scheme. The parabolic quadric $\mathrm{Q}(4,q)$ is not listed separately: for $q$ even it is isomorphic to $\mathrm{W}(q)$; for $q$ odd it is the dual of $\mathrm{W}(q)$ (incidence matrix $M^T$), and a direct computation for $q = 3$ confirms that both give identical GT code properties.

Projective Geometry over $\mathbb{Z}_n$

Barbilian's programme of projective geometry over rings extends the field construction to arbitrary commutative rings such as $\mathbb{Z}_n$. Working with the free module $\mathbb{Z}_n^r$, a point is a free rank-1 submodule: the orbit $\langle v \rangle = \{\lambda v : \lambda \in \mathbb{Z}_n^\times\}$ of a unimodular vector $v$, i.e.\ one satisfying $\gcd(v_1,\ldots,v_r,\,n)=1$ (equivalently: there exists a linear form $\ell$ with $\ell(v) \in \mathbb{Z}_n^\times$). The corresponding hyperplane through $\langle v \rangle$ is the annihilator \[ L_v = \{\,u \in \mathbb{Z}_n^r : u \cdot v \equiv 0 \pmod{n}\,\} \;\cap\; \{\text{unimodular elements}\}, \] which is again a unimodular rank-1 submodule of the dual module. The point and block counts are given by the Jordan totient function $J_r(n) = n^r\!\prod_{p\mid n}(1-p^{-r})$: \[ N \;=\; \frac{J_r(n)}{\varphi(n)}, \qquad k \;=\; \frac{J_{r-1}(n)}{\varphi(n)}. \] For $n$ a prime power this reduces to the chain-ring formula $N = (n^r - m^r)/\varphi(n)$ with $m = n - \varphi(n)$.

The incidence matrix $M \in \mathbb{B}_2^{N \times N}$ is square and symmetric ($M = M^T$). For $n$ a prime power, $\mathrm{PGL}(r, \mathbb{Z}_n)$ acts regularly and $|\mathrm{Aut}(M)| = |\mathrm{PGL}(r, \mathbb{Z}_n)|$. When $n$ is not a prime power, the ring $\mathbb{Z}_n \cong \mathbb{Z}_{p_1^{a_1}} \times \cdots$ splits by CRT, and $\mathrm{PG}(r{-}1,\mathbb{Z}_n)$ is isomorphic to the product geometry $\mathrm{PG}(r{-}1,\mathbb{Z}_{p_1^{a_1}}) \times \cdots$; the incidence matrix is the Kronecker product of the factors, hence still regular, with $|\mathrm{Aut}| = \prod_i |\mathrm{PGL}(r,\mathbb{Z}_{p_i^{a_i}})|$.

For the group-testing identification: hyperplanes as samples, points as tests ($G = M$, $N = K$). The incidence structure is generally not a Steiner system, so the Steiner-system corollary does not apply; disjunctness values are determined computationally.

Code Properties by Scheme

Highlighted rows: maximum disjunctness level. $\mathrm{PG}(2,\mathbb{Z}_6)$: corrected using the unimodular condition $\gcd(v_1,\ldots,v_r,n)=1$ (e.g.\ $(2,3,0)\in\mathbb{Z}_6^3$ is unimodular); $N=91=7\times 13$, $k=12=3\times 4$, $|\mathrm{Aut}|=943{,}488=168\times 5{,}616$. For prime-power $n$: $|\mathrm{Aut}| = |\mathrm{PGL}(r, \mathbb{Z}_n)|$; for $n = p_1^{a_1}\cdots p_s^{a_s}$ the geometry is the product $\mathrm{PG}(r{-}1,\mathbb{Z}_{p_1^{a_1}})\times\cdots$ and $|\mathrm{Aut}| = \prod_i|\mathrm{PGL}(r,\mathbb{Z}_{p_i^{a_i}})|$. Observed $d_{\min}$ pattern for all rings studied (including non-chain rings): $d_{\min}(C_t) = k - m\,(t-1)$, where $m = n-\varphi(n)$; confirmed for $n\in\{4,6,8,9\}$. Cayley-graph comparisons on $N$ points with the same block size $k$ are at best equal at $t=1$ and strictly worse at $t\geq 2$, confirming that the advantage is intrinsic to the Barbilian geometry.

Strongly Regular Graphs as Group Testing Designs

A strongly regular graph $\Gamma = \mathrm{srg}(v, k, \lambda, \mu)$ is a $k$-regular graph on $v$ vertices in which every pair of adjacent vertices has exactly $\lambda$ common neighbours and every pair of non-adjacent vertices has exactly $\mu$ common neighbours. The adjacency matrix $A \in \mathbb{B}_2^{v \times v}$ satisfies \[ A^2 \;=\; k\,I \;+\; \lambda\,A \;+\; \mu\,(J - I - A), \] which encodes the pairwise intersection structure completely.

Taking $A$ as an incidence matrix — blocks as vertex neighbourhoods of size $k$, each point appearing in exactly $k$ blocks — yields a $1$-$(v,k,k)$ design with $N = K = v$. The resulting group-testing codes $C_t$ are controlled by the srg parameters: any two columns overlap in exactly $\lambda$ or $\mu$ positions depending on adjacency.

There is a classical connection to two-weight codes: a linear $[n,k]$ code over $\mathbb{F}_q$ with exactly two nonzero weights $w_1, w_2$ gives an $\mathrm{srg}$ on its nonzero codewords (Delsarte–Goethals–Seidel, 1971). Ring-geometric designs — in particular the incidence matrices of $\mathrm{PG}(r{-}1,\mathbb{Z}_n)$ — induce strongly regular structures on their point sets, making SRGs a natural lens through which to view the Barbilian examples.

The Johnson Graph $J(8,2)$

The vertices of $J(8,2)$ are the $\binom{8}{2} = 28$ two-element subsets of $\{0,\ldots,7\}$, two subsets adjacent iff $|\text{intersection}| = 1$. Parameters: $\mathrm{srg}(28,\,12,\,6,\,4)$; $|\mathrm{Aut}| = |S_8| = 40{,}320$. The incidence matrix has the same dimensions as $\mathrm{PHG}(2,\mathbb{Z}_4)$ ($28 \times 28$) but block size $k = 12$ instead of $6$.

The comparison with $\mathrm{PHG}(2,\mathbb{Z}_4)$ is telling: the ring geometry, with half the block size ($k=6$), achieves $t=2$ and sustained error-correction capacity that $J(8,2)$ cannot reach at any $t \geq 2$, despite its larger $k$ and larger symmetry group. High regularity and large $k$ alone do not guarantee strong group-testing performance; the algebraic structure of the ring geometry provides an essential additional ingredient.

The Gewirtz Graph

The Sims–Gewirtz graph is the unique $\mathrm{srg}(56,\,10,\,0,\,2)$: 56 vertices, degree $k=10$, triangle-free ($\lambda=0$), $\mu=2$. Its automorphism group has order $|\mathrm{Aut}| = 80{,}640$. Triangle-freeness eliminates the $J(n,2)$ obstruction entirely, and a sharp bound governs the achievable disjunctness:

For the Gewirtz graph: $\lfloor(10-1)/2\rfloor = 4$, so $t_{\max} \geq 4$. Computation confirms $t_{\max} = 4$ exactly (the boundary case $t=5$ gives $5\mu = 10 = k$, and indeed fails). The formula $d_{\min}(C_t) = 10 - 2(t-1)$ holds for all $t \in \{1,2,3,4\}$.

The parallel with the Hjelmslev formula $d_{\min}(C_t) = k - m(t-1)$ (where $m = n - \varphi(n)$) is exact: both reflect the same underlying regularity — the number of blocks shared by two “close” points — expressed in ring-theoretic ($m$) versus graph-theoretic ($\mu$) language. This suggests that the Barbilian ring geometries are, in a precise sense, SRG-derived designs whose block-intersection structure is controlled by the ring parameter $m$.

Code Properties

Highlighted rows: maximum disjunctness level. $J(8,2)$: not $2$-disjunct due to the triangle-covering obstruction (structural, holds for all $J(n,2)$). Gewirtz ($\lambda=0$, $\mu=2$): $t_{\max}=4$ and $d_{\min}(C_t) = k - \mu(t-1) = 10-2(t-1)$, confirming the general pattern with $\mu$ playing the role of the ring parameter $m$. $\mathrm{PHG}(2,\mathbb{Z}_4)$: smaller $k=6$ yet $t=2$ — ring geometry provides structure beyond mere regularity.

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.