Differential checks
Descendants against the SmallGroups library
For a $p$-group $H$ of $p$-class $c \ge 2$, its parent in the tree is $H / P_c(H)$ and its step is
$\log_p |P_c(H)|$. So for $G$ of order $p^m$ and a step $s$ the immediate descendants of $G$ are exactly the
groups $H$ of order $p^{m+s}$ with $H / P_c(H) \cong G$. desc_vs_sg.g compares, for every $G$ in the
library and every $s$ in range, the multiset of IdGroup of PqDescendants(G : StepSize := s)
with that set (elementary abelian groups of rank $\ge 5$ only for $s = 1$: larger steps there take hours).
| $p$ | orders of $G$ | pairs $(G, s)$ | differences |
|---|---|---|---|
| 2 | $2 \dots 2^7$, descendants to $2^8$ | 3112 | 0 |
| 3 | $3 \dots 3^5$, to $3^6$ | 125 | 0 |
| 5 | to $5^5$ | 35 | 0 |
| 7 | to $7^4$ | 12 | 0 |
| 11 | to $11^4$ | 12 | 0 |
This is a check of pq on the library's own presentations, which are pq's: it cannot
see finding 1. Some of the step sizes are larger than the nuclear rank of
$G$; for those the empty answer is right, but, as finding 15
shows, pq reaches it through a desynchronised dialogue. Without PcgsAutomorphisms, as
here, the answer is the right one.
Descendants of other presentations of the same group
The descendants of a group cannot depend on its presentation. coords.g compares
PqDescendants(G : StepSize := 1) for $G$ = SmallGroup(n, k) ($n$ = 32, 64, 128,
$p$-class $\ge 3$, every third $k$) with three isomorphic copies: the special pcgs, a pcgs of a permutation
representation, and pq's own presentation of the fp group. On master, in this run, the first difference appears
at order 128 (SmallGroup(128, 3): 10 descendants, 8 for a copy), and 17 groups differ before
pq dies at SmallGroup(128, 1728); with fix 1:
1983 comparisons in each of four runs, 0 differences, also under AddressSanitizer with three seeds. The fixed list of
copies in the table of finding 1 (gen_codes.g, check_codes.g) is the reproducible
version of this check.
Standard presentations as an isomorphism key
spcheck.g: for every group of the order, its standard presentation is a presentation of it
(IdGroup of PcGroupFpGroup), different groups get different ones, and copies in another
pc presentation get the same one.
| order | groups | copies each | failures |
|---|---|---|---|
| 2 | 1 | 3 | 0 |
| 3 | 1 | 3 | 0 |
| 4 | 2 | 5 | 0 |
| 8 | 5 | 5 | 0 |
| 16 | 14 | 5 | 0 |
| 32 | 51 | 5 | 0 |
| 64 | 267 | 3 | 0 |
| 128 | 2328 | 1 | 0 |
| 243 | 67 | 3 | 0 |
| 625 | 15 | 3 | 0 |
| 729 | 504 | 1 | 0 |
Order 128: the first run died because pq was killed from outside, by a
pkill issued during the audit itself (Open items); it is being
rerun on master and on correctness. The one death of pq in a run of order 64 had the
same cause; order 64 was rerun six times (6408 calls) without a failure.
The pq2048 walk with its own covers and children
With PQ2048_OWNCOVER=1 PQ2048_OWNDESC=1, the D₅ project builds $p$-covers with GAP's
Extension and step-1 children as pc quotients of them, and calls PqDescendants on those
children: exactly the inputs of finding 1. For all 304 vertices of orders 16–64 of class $\le 3$, the 1186
children were compared with their SmallGroups copies (descendants by IdGroup, up to order 256):
0 differences on master. Beyond that we did not check; the fix removes the question.
AddressSanitizer
pq built with -fsanitize=address, run with the fixes through the copies above
and the standard presentation check of order 64: no report. On master, the crash of finding 1 is a
heap-buffer-overflow in stabiliser_generators (stabiliser.c:173): with maps that are
not automorphisms a Schreier word never closes, and the loop writes past the end of the workspace, which it never
checks (finding 21). In the second pass ASan showed the
heap overflows of findings 12 and 21 on master and nothing with their
fixes; what ASan alone sees at a tiny workspace is on Open items. The crash of finding 4 leaves no report: pq exits
on the input that does not fit it.