ANUPQ: a correctness audit

We use ANUPQ (PqDescendants, PqPCover, PqStandardPresentation) to walk the 2-group generation tree to order $2^{11}$, where a missed or a spurious descendant would silently change a mathematical result. The maintainers have said that they care for correct computations; so do we. This is what we checked, what we found, and the fixes we propose, each with a reproducer, an argument for why the fix is right, and the evidence.

In short. 24 defects, each with a reproducer, all fixed in pull requests #96–#121.

First pass (#96–#104, nine defects): two give wrong descendants silently (one of them also crashes pq), one gives a wrong isomorphism, one more crashes pq, one hangs, and four are errors or wrong data on less used paths. The two silent errors are reached only off the default path: a pc presentation other than pq's own, or 127 or more automorphisms.
Second pass (#105–#121, fifteen defects): we checked each of the 15 suspected defects that were left open: thirteen are confirmed and two refuted. Three more turned up on the way; two are fixed here, the third is harmless and left open. Ten of the fifteen can give a wrong result without any message, but none of them is reached by 2-group generation with default options: they need the option PcgsAutomorphisms, automorphisms supplied by hand together with an exponent law, a prime $p \ge 2^{15}$ or $p^d > 10000$, a pc group that is not a $p$-group, a pQuotient of class 2 or more in another pc presentation, more than 65535 pc generators, or a workspace near its limit.

Against the SmallGroups library, PqDescendants on the library's own groups is right everywhere we looked (3296 pairs (group, step size), $p = 2, 3, 5, 7, 11$), and standard presentations are invariant and separating on 3255 groups.

Findings

Defect	Effect	Reached by	Fix
First pass: pull requests #96–#104
Automorphisms sent in the wrong basis	wrong descendants; pq crash	`PqDescendants(G)` for a pc group whose pcgs is not pq's own pcp: 121 of 2123 isomorphic copies of SmallGroups of order 64–256 gave wrong descendants, 1 crashed pq	#96
Orbit counters in `char`	wrong descendants and stabilisers	127 or more automorphisms, e.g. `AbelianGroup([2^3,2^5,2^7,2^9,2^11])`: 16384 step-1 descendants instead of 26	#99
`EpimorphismStandardPresentation`	map not bijective	pc groups whose generators are not their pcgs, e.g. `AbelianGroup(IsPcGroup,[4,2])`; the SP itself is right	#100
Exponent law the group breaks	pq crash	`PqDescendants(SmallGroup(16,5) : Exponent := 4)`	#97
SP rank with `Relators`	hang	`PqStandardPresentation(F : Prime := 2, Relators := ["a^8", "b*a^-2"])`	#98
Stale groups in interactive `PqDescendants`	extra groups returned	an interactive process after `PqPGConstructDescendants`	#101
`SavePqList`	file unreadable	a group with an automorphism group	#102
`RelativeOrders` option	wrong data or error	`PqPGSupplyAutomorphisms(.. : RelativeOrders := [3, 2])`	#103
Trivial groups in `IsIsomorphicPGroup`	error	two trivial groups	#104
Second pass, wrong results without a message (none is reached by 2-group generation with default options)
Option `PcgsAutomorphisms` with a sequence that is not PAG	wrong descendants (isomorphic duplicates)	`PqDescendants(ElementaryAbelianGroup(4) : ClassBound := 3, PcgsAutomorphisms)`: 161 groups instead of 136	#110
Exponent law with automorphisms supplied by hand	group too large	`PqSupplyAutomorphisms` with automorphisms that do not induce $GL(d,p)$, then `PqNextClass` under `Exponent`: $2^{13}$ instead of $2^4$	#112
Exponent-law queue at class 2	wrong groups or pq crash (heap overflow)	`PqSupplyAutomorphisms` generating $GL(d,2)$, $d \ge 7$, with `Exponent := 2`: e.g. $2^{11}$ instead of $2^7$ in 6 of 10 runs	#106
`glOrder` for $p^d > 10000$	wrong stabilisers handed to pq	`PqDescendants` of a group of rank $d$ with $p^d > 10000$, e.g. $(C_{101})^2$: `glOrder` 1020000/1030301 instead of 1030200	#117
`PqEpimorphism` for a pc group that is not a $p$-group	map not a homomorphism, or error	generators other than the pcgs, e.g. those of a pc group $S_3 \times C_4$ in reverse order	#111
`StepSize` above the nuclear rank; temporary directory; group names	wrong descendants with `PcgsAutomorphisms`; otherwise errors	`PqDescendants(SmallGroup(4,2) : StepSize := 4, PcgsAutomorphisms)`: 3 groups instead of none; `ANUPQDirectoryTemporary`; a group name with `_`	#119, #120, #121
Primes $p \ge 2^{15}$	wrong epimorphism or $p$-cover	`PqEpimorphism(G : Prime := 32771, ClassBound := 1)`: a relation of $G$ fails in the image	#116
More than 65535 pc generators in one class	corrupted presentation	`PqNextClass` for `FreeGroup(361)`, $p = 2$, from class 1 to class 2	#114
Workspace for a commutator relation with an exponent	wrong order	`Relators := ["[b,a]^3"]` with `PqWorkspace` near its limit: $2^7$ instead of $2^6$	#109
`StandardPresentation` with a `pQuotient` in another pc presentation	wrong standard presentation; pq crash	`pQuotient := Q` of class at least 2 whose pcgs is not pq's: order 64, 354 copies, 59 wrong, 109 crashes	#118
Second pass, crashes and errors
Saved group files with GMP	pq crash	`PqDescendants(CyclicGroup(53))`; every $p$ with $p \bmod 256 \in [48, 57]$ (53, 307, 311, …)	#105
Schreier words without a space check	memory overwrite; pq crash	on master only through finding 1, e.g. a copy of `SmallGroup(256,1325)`	#108
Overflow of the number of allowable subgroups	error; pq went on in a broken state	`StandardPresentation` of groups of large Frattini rank, e.g. rank 6, order $2^9$ (issue #32)	#113
Second pass, wrong data
Relative orders written for GAP	wrong data	`ANUPQAutomorphisms(D).relativeOrders` of a descendant: the last entry repeated	#107
Relative orders of a soluble stabiliser	wrong data	`ANUPQAutomorphisms` of descendants: more soluble generators than automorphisms	#115

Red: a wrong mathematical result or a crash. Amber: an error, a hang or wrong auxiliary data; no wrong group is returned. What is still open, and what we checked and refuted, is on Open items.

All fixes together

The branch correctness of ispacex/anupq, at b7deefa, is master 81bcf35 with all fixes #96–#121 merged and the union-find orbit speed-up (ispacex/anupq#2, same output); the package test suite passes on it (123 test files, 0 failures).

How we checked

Reading. The C core (p-quotient and p-cover, collection, consistency, echelon), p-group generation (allowable subgroups, labels, orbits, stabilisers, automorphisms), standard presentations, and the GAP interface, with an eye on boundary cases: $p = 2$ and large $p$, rank 1, class 1, nucleus of rank 0, step size larger than the nucleus, many generators, many automorphisms, interactive and non-interactive use.
Differential checks against independent data (details): descendants against the SmallGroups library, the same group in other pc presentations, standard presentations as an isomorphism invariant, pq under AddressSanitizer.
Every suspicion read in the code was then reproduced or refuted on master and on the branch with the earlier fixes; for each confirmed one we state whether it can give a wrong result without a message and whether our own runs can reach it.
Every fix comes with a test that fails before and passes after (except where the input no longer reaches the code after an earlier fix, as for finding 21), and the package test suite passes with each fix and with all of them together.

Found correct

PqDescendants on SmallGroups: for every group $G$ of order $p^m$ and every step size $s$ with $p^{m+s}$ in range, the descendants are exactly the groups $H$ of order $p^{m+s}$ with $H/P_c(H) \cong G$ (as multisets of IdGroup): $p = 2$ to order $2^8$, $p = 3$ to $3^6$, $p = 5$ to $5^5$, $p = 7, 11$ to $p^4$; 3296 pairs, 0 differences.
PqStandardPresentation as an isomorphism key: all groups of orders 2, 3, 4, 8, 16, 32, 64, 128, 243, 625, 729 get pairwise different standard presentations, each is a presentation of its group, and isomorphic copies in other pc presentations get the same one (3255 groups, 0 failures).
The collectors for $p = 2$ and odd $p$, consistency and tails, echelonisation, label/subgroup conversion, the allowability test $U + N = M$, the central automorphisms, the insoluble orbit algorithm, and the permutation representation of $A/S$ handed to AutPGrp (PR #85): read and found right.

Environment

GAP 4.16.1, AutPGrp 1.13.0, ANUPQ master 81bcf35 (with GMP), macOS 26 on arm64 (Apple clang); the checks of the fixes were repeated with pq built with -fsanitize=address. Everything needed to repeat them is on Data and scripts.