ANUPQ: проверка корректности

Мы используем ANUPQ (PqDescendants, PqPCover, PqStandardPresentation), чтобы обойти дерево построения 2-групп до порядка $2^{11}$. Пропущенный или лишний потомок здесь молча изменил бы математический результат. Сопровождающие пакета говорили, что им важна корректность вычислений; нам тоже. Здесь описано, что мы проверили, что нашли и какие исправления предлагаем: к каждому дефекту приложены воспроизведение, обоснование исправления и проверка.

Коротко. 24 дефекта, у каждого есть воспроизведение; все исправлены в PR #96–#121.

Первый проход (#96–#104, девять дефектов): два молча дают неверных потомков (один из них к тому же роняет pq), один даёт неверный изоморфизм, ещё один роняет pq, один приводит к зависанию, четыре — ошибки или неверные данные на редко используемых путях. Оба тихих дефекта проявляются только в стороне от основного пути: при pc-презентации, отличной от собственной презентации pq, или при 127 и более автоморфизмах.
Второй проход (#105–#121, пятнадцать дефектов): мы проверили каждый из 15 подозреваемых дефектов, которые оставались открытыми. Тринадцать подтвердились, два опровергнуты. По ходу нашлись ещё три: два исправлены, третий безвреден и оставлен открытым. Десять из пятнадцати могут дать неверный результат без всякого сообщения, но ни один из них не достигается при построении 2-групп с параметрами по умолчанию: для этого нужны опция PcgsAutomorphisms, заданные вручную автоморфизмы вместе с законом экспоненты, простое $p \ge 2^{15}$ или $p^d > 10000$, pc-группа, не являющаяся $p$-группой, pQuotient класса 2 и выше в другой pc-презентации, больше 65535 pc-порождающих или рабочая память на самом пределе.

В сверке с библиотекой SmallGroups PqDescendants на собственных группах библиотеки верен везде, где мы смотрели (3296 пар (группа, шаг), $p = 2, 3, 5, 7, 11$), а стандартные презентации инвариантны и различают группы на 3255 группах.

Дефекты

Дефект	Последствие	Когда проявляется	Исправление
Первый проход: PR #96–#104
Автоморфизмы передаются в чужом базисе	неверные потомки; падение pq	`PqDescendants(G)` для pc-группы, чей pcgs не совпадает с pcp, который строит сам pq: из 2123 изоморфных копий групп SmallGroups порядков 64–256 неверных потомков дали 121, pq упал на 1	#96
Счётчики орбит в `char`	неверные потомки и стабилизаторы	127 и более автоморфизмов, например `AbelianGroup([2^3,2^5,2^7,2^9,2^11])`: 16384 потомка с шагом 1 вместо 26	#99
`EpimorphismStandardPresentation`	отображение не биективно	pc-группы, у которых порождающие не совпадают с pcgs, например `AbelianGroup(IsPcGroup,[4,2])`; сама стандартная презентация верна	#100
Закон экспоненты, которому группа не удовлетворяет	падение pq	`PqDescendants(SmallGroup(16,5) : Exponent := 4)`	#97
Ранг в SP при опции `Relators`	зависание	`PqStandardPresentation(F : Prime := 2, Relators := ["a^8", "b*a^-2"])`	#98
Старые группы в интерактивном `PqDescendants`	возвращаются лишние группы	интерактивный процесс после `PqPGConstructDescendants`	#101
`SavePqList`	файл не читается	группа с заданной группой автоморфизмов	#102
Опция `RelativeOrders`	неверные данные или ошибка	`PqPGSupplyAutomorphisms(.. : RelativeOrders := [3, 2])`	#103
Тривиальные группы в `IsIsomorphicPGroup`	ошибка	две тривиальные группы	#104
Второй проход: неверный результат без сообщения (ни один не достигается при построении 2-групп с параметрами по умолчанию)
Опция `PcgsAutomorphisms` с последовательностью, не являющейся PAG	неверные потомки (изоморфные повторы)	`PqDescendants(ElementaryAbelianGroup(4) : ClassBound := 3, PcgsAutomorphisms)`: 161 группа вместо 136	#110
Закон экспоненты при автоморфизмах, заданных вручную	группа слишком велика	`PqSupplyAutomorphisms` с автоморфизмами, которые не индуцируют $GL(d,p)$, затем `PqNextClass` с `Exponent`: $2^{13}$ вместо $2^4$	#112
Очередь закона экспоненты в классе 2	неверные группы или падение pq (переполнение кучи)	`PqSupplyAutomorphisms`, порождающие $GL(d,2)$, $d \ge 7$, с `Exponent := 2`: например $2^{11}$ вместо $2^7$ в 6 прогонах из 10	#106
`glOrder` при $p^d > 10000$	в pq передаются неверные стабилизаторы	`PqDescendants` для группы ранга $d$ с $p^d > 10000$, например $(C_{101})^2$: `glOrder` 1020000/1030301 вместо 1030200	#117
`PqEpimorphism` для pc-группы, не являющейся $p$-группой	отображение не гомоморфизм, или ошибка	порождающие не совпадают с pcgs, например порождающие pc-группы $S_3 \times C_4$ в обратном порядке	#111
`StepSize` больше ядерного ранга; временный каталог; имена групп	неверные потомки при `PcgsAutomorphisms`; в остальных случаях ошибки	`PqDescendants(SmallGroup(4,2) : StepSize := 4, PcgsAutomorphisms)`: 3 группы вместо пустого списка; `ANUPQDirectoryTemporary`; имя группы с `_`	#119, #120, #121
Простые $p \ge 2^{15}$	неверный эпиморфизм или $p$-накрытие	`PqEpimorphism(G : Prime := 32771, ClassBound := 1)`: соотношение группы $G$ в образе не выполняется	#116
Больше 65535 pc-порождающих в одном классе	испорченная презентация	`PqNextClass` для `FreeGroup(361)`, $p = 2$, переход от класса 1 к классу 2	#114
Рабочая память для коммутаторного соотношения с показателем	неверный порядок	`Relators := ["[b,a]^3"]` при `PqWorkspace` у самого предела: $2^7$ вместо $2^6$	#109
`StandardPresentation` с `pQuotient` в другой pc-презентации	неверная стандартная презентация; падение pq	`pQuotient := Q` класса не меньше 2, чей pcgs не совпадает с pcp pq: порядок 64, 354 копии, 59 неверных, 109 падений	#118
Второй проход: падения и ошибки
Файлы сохранённых групп при сборке с GMP	падение pq	`PqDescendants(CyclicGroup(53))`; любое $p$ с $p \bmod 256 \in [48, 57]$ (53, 307, 311, …)	#105
Слова Шрайера без проверки места	затирание памяти; падение pq	на master только через дефект 1, например копия `SmallGroup(256,1325)`	#108
Переполнение числа допустимых подгрупп	ошибка; pq продолжал работу в испорченном состоянии	`StandardPresentation` групп большого ранга Фраттини, например ранга 6 порядка $2^9$ (задача #32 в трекере пакета)	#113
Второй проход: неверные данные
Относительные порядки, записанные для GAP	неверные данные	`ANUPQAutomorphisms(D).relativeOrders` у потомка: последний элемент повторён	#107
Относительные порядки разрешимого стабилизатора	неверные данные	`ANUPQAutomorphisms` у потомков: разрешимых порождающих больше, чем автоморфизмов	#115

Красный: неверный математический результат или падение. Жёлтый: ошибка, зависание или неверные вспомогательные данные; неверная группа не возвращается. Что ещё открыто и что мы проверили и опровергли — на странице «Открытые вопросы».

Все исправления вместе

Ветка correctness репозитория ispacex/anupq, коммит b7deefa, — это master 81bcf35 со всеми исправлениями #96–#121 и ускорением орбит через union-find (ispacex/anupq#2, выдача та же); тесты пакета на ней проходят (123 файлов, 0 ошибок).

Как мы проверяли

Чтение кода. Ядро на C (p-фактор и p-накрытие, собирание, согласованность, приведение к ступенчатому виду), построение p-групп (допустимые подгруппы, метки, орбиты, стабилизаторы, автоморфизмы), стандартные презентации и интерфейс GAP — с вниманием к граничным случаям: $p = 2$ и большие $p$, ранг 1, класс 1, ядро ранга 0, шаг больше ядра, много порождающих, много автоморфизмов, интерактивная и неинтерактивная работа.
Сверки с независимыми данными (подробности): потомки против библиотеки SmallGroups, та же группа в других pc-презентациях, стандартная презентация как инвариант изоморфизма, pq под AddressSanitizer.
Каждое подозрение, возникшее при чтении кода, затем воспроизведено или опровергнуто на master и на ветке с предыдущими исправлениями; для каждого подтверждённого мы указываем, может ли он дать неверный результат без сообщения и могут ли его задеть наши собственные прогоны.
К каждому исправлению приложен тест, который падает до исправления и проходит после (кроме случая, когда после более раннего исправления вход уже не доходит до этого кода, как в дефекте 21); тесты пакета проходят с каждым исправлением по отдельности и со всеми вместе.

Что оказалось верным

PqDescendants на группах SmallGroups: для каждой группы $G$ порядка $p^m$ и каждого шага $s$, при котором $p^{m+s}$ в пределах библиотеки, потомки — это в точности группы $H$ порядка $p^{m+s}$ с $H/P_c(H) \cong G$ (как мультимножества IdGroup): $p = 2$ до порядка $2^8$, $p = 3$ до $3^6$, $p = 5$ до $5^5$, $p = 7, 11$ до $p^4$; 3296 пар, 0 расхождений.
PqStandardPresentation как ключ изоморфизма: все группы порядков 2, 3, 4, 8, 16, 32, 64, 128, 243, 625, 729 получают попарно различные стандартные презентации, каждая из них задаёт свою группу, а изоморфные копии в других pc-презентациях получают ту же самую (3255 групп, 0 ошибок).
Собиратели для $p = 2$ и нечётных $p$, согласованность и хвосты, приведение к ступенчатому виду, перевод между метками и подгруппами, проверка допустимости $U + N = M$, центральные автоморфизмы, алгоритм орбит неразрешимой группы и перестановочное представление $A/S$, передаваемое в AutPGrp (PR #85): прочитаны и признаны верными.

Окружение

GAP 4.16.1, AutPGrp 1.13.0, ANUPQ master 81bcf35 (с GMP), macOS 26 на arm64 (Apple clang); проверки исправлений повторены с pq, собранным с -fsanitize=address. Всё, что нужно для повторения, — на странице «Данные и скрипты».