Slow CharacteristicSubgroups

[ChrisJefferson]

This may just be 'one of those things', where a different chosen method ends up being extremely slow.

Basically, CharacteristicSubgroups can be suprisingly small on a tiny group (64 elements, 12 points), if you first call StabChain and FittingSubgroup.

# H is a 64-element subdirect of D_8^3 acting on 12 points with three
# orbits of length 4.  CharacteristicSubgroups(H) finishes in ~30 ms
# in a fresh interpreter — but if StabChain(H, base) has been called
# with an explicit base argument and any subsequent call has forced
# FittingSubgroup(H), then CharacteristicSubgroups(H) hangs indefinitely
# (>>5 min on M-class hardware).
#
# This is GAP-only.  The two passes below differ in exactly one line.

H := Group([(1,2)(3,4)(5,8,7,6)(9,12)(10,11),
            (1,4,3,2)(5,7),
            (2,4)(5,6,7,8)(9,10,11,12)]);

# Pass 1 (fast, ~30 ms):
#   t := NanosecondsSinceEpoch();
#   FittingSubgroup(H);;
#   CharacteristicSubgroups(H);;
#   Print(QuoInt(NanosecondsSinceEpoch() - t, 1000000), " ms\n");

# Pass 2 (hangs):
StabChain(H, [1, 5, 9]);;      # any base argument here; even [5,1,9,6]
                               # (which equals what GAP picks naturally
                               # without an argument) triggers it.
FittingSubgroup(H);;
Print("about to call CharacteristicSubgroups; this will not return.\n");
t := NanosecondsSinceEpoch();
cs := CharacteristicSubgroups(H);
Print(QuoInt(NanosecondsSinceEpoch() - t, 1000000), " ms\n");

[fingolfin]

My guess is that @hulpke is by far best position to have an idea what might be going on here :-)

[hulpke]

I have not been able to reproduce this. Which version do you use?

What happens if you explicitly ask for AutomorphismGroup and NormalSubgroups of H before asking for the characteristic ones?
What output do you get with
SetInfoLevel(InfoLattice,2);SetInfoLevel(InfoMorph,5);SetInfoLevel(InfoAutGrp,5);. ?

The stabilizer chain should not really impact methods chosen.

[fingolfin]

I cannot reproduce this if I load GAP with the -A option (so a minimal set of packages is loaded).

But I can reproduce this if I load GAP with the default set of packages loaded.

The difference seems to be caused by the crips package. Indeed, pressing ctrl-C, I get this:

$ gap
     ● G  GAP 4.16.0-beta1-45-g4a52d83-dirty built on 2026-05-23 22:03:51+0200
  ● ●  A  https://www.gap-system.org
     ● P  Architecture: aarch64-apple-darwin25-default64-kv11
 Configuration:  gmp 6.3.0, GASMAN, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.3, Alnuth 4.0.0, AtlasRep 2.1.11, AutoDoc 2026.05.11,
             AutPGrp 1.12.0, Browse 1.8.22, CaratInterface 2.3.9, CRISP 1.5.dev,
             Cryst 4.1.31, CrystCat 1.1.11, CTblLib 1.3.11, curlInterface 2.4.3,
             FactInt 1.6.3, FGA 1.5.0, Forms 1.3.0, GAPDoc 1.6.10.dev, genss 1.6.9,
             IO 4.9.3, IRREDSOL 1.4.4, LAGUNA 3.9.7, orb 5.1.0, PackageManager 1.6.3,
             Polenta 1.3.11, Polycyclic 2.18, PrimGrp 4.0.2, RadiRoot 2.9, recog 1.5.1,
             ResClasses 4.7.4, SmallGrp 1.5.4, Sophus 1.27, SpinSym 1.5.2,
             StandardFF 1.0.dev, TomLib 1.2.11, TransGrp 3.6.5, utils 0.95
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap> H := Group([(1,2)(3,4)(5,8,7,6)(9,12)(10,11),
>             (1,4,3,2)(5,7),
>             (2,4)(5,6,7,8)(9,10,11,12)]);;
gap> StabChain(H, [1, 5, 9]);;      # any base argument here; even [5,1,9,6]
gap> FittingSubgroup(H);;
gap> cs := CharacteristicSubgroups(H);
^CError, user interrupt
*[1] I := N[i];
   @ /Users/mhorn/Projekte/GAP/gap/lib/grp.gi:1476
 [2] ElementaryAbelianSeriesLargeSteps( e )
   @ /Users/mhorn/Projekte/GAP/gap/lib/grppclat.gi:39
 [3] InvariantElementaryAbelianSeries( G, act )
   @ /Users/mhorn/Projekte/GAP/repos/pkg/others/crisp/lib/util.gi:343
 [4] CompositionSeriesUnderAction( act, G )
   @ /Users/mhorn/Projekte/GAP/repos/pkg/others/crisp/lib/residual.gi:194
 [5] AllInvariantSubgroupsWithQProperty( AutomorphismGroup( G ), G, ReturnTrue,
 ReturnTrue, rec(
     ) )
   @ /Users/mhorn/Projekte/GAP/repos/pkg/others/crisp/lib/residual.gi:117
<function "CharacteristicSubgroups normal complement method for pcgs computable groups">(\
 <arguments> )
 called from read-eval loop at *stdin*:6
you can 'return;'
brk>

[hulpke]

OK. So this is really an issue in the separate CharacteristicSubgroups method in CRISP.

[fingolfin]

This is not a CRISP bug after all — it reproduces with gap -A and no packages loaded (GAP 4.17dev). CRISP merely happens to call the exact combination of operations that triggers it.

Standalone reproducer

H := Group([(1,2)(3,4)(5,8,7,6)(9,12)(10,11),
            (1,4,3,2)(5,7),
            (2,4)(5,6,7,8)(9,10,11,12)]);;
StabChain(H, [1,5,9]);;
FittingSubgroup(H);;
AutomorphismGroup(H);;
e := ElementaryAbelianSeries(H);;
List(e, Size);
# [ 64, 32, 16, 4, 2, 1 ]
List([1..Length(e)-1], i -> HasElementaryAbelianFactorGroup(e[i], e[i+1]));
# [ true, true, false, true, true ]     <-- not an elementary abelian series!
ElementaryAbelianSeriesLargeSteps(H);   # hangs forever

All three preparatory calls are needed; drop any one of them and everything is fine.

Causal chain

1. A central-series pcgs gets stamped with IndicesEANormalSteps.

FittingSubgroup(H) → IsNilpotentGroup → PcgsCentralSeries (lib/grpperm.gi:1381) → TryPcgsPermGroup(G, cent := true, desc := false, elab := false). At lib/pcgsperm.gi:423 the iselab argument is

    pcgs := PcgsStabChainSeries( filter, grp, series, oldlen,
      (elab=true) or cent);

so because of or cent, PcgsStabChainSeries (lib/pcgsperm.gi:707-710) sets IndicesEANormalSteps on a purely central series pcgs. Central factors are abelian but need not have exponent p — here the offending factor is a cyclic C4. This pcgs becomes HomePcgs(H):

IndicesCentralNormalSteps = [ 1, 2, 3, 5, 6, 7 ]
IndicesEANormalSteps      = [ 1, 2, 3, 5, 6, 7 ]   # sizes 64,32,16,4,2,1

The explicit base in StabChain(H,[1,5,9]) matters only because with GAP's natural base the central steps happen to be elementary abelian as well, so the problem stays latent.

2. SpecialPcgs reuses that pcgs object and cannot overwrite the stale value.

AutomorphismGroup(H) computes SpecialPcgs(H), which turns out to be the same object. The "pcgs is reused — force new one" guard in lib/pcgsspec.gi:602 only tests IsBound(pcgssys.pcgs!.LGWeights), which is not set here, so it does not fire. The subsequent SetIndicesEANormalSteps(newpcgs, pcgssys.first) at lib/pcgsspec.gi:623 is then silently a no-op, because the attribute is already set. Resulting state:

IsSpecialPcgs        = true
LGFirst              = [ 1, 4, 7 ]          # correct EA steps: sizes 64, 8, 1
IndicesEANormalSteps = [ 1, 2, 3, 5, 6, 7 ] # stale

3. The IsSpecialPcgs implication now makes IsPcgsElementaryAbelianSeries lie.

InstallTrueMethod(IsPcgsElementaryAbelianSeries, IsSpecialPcgs) (lib/pcgsspec.gd:37) makes the property true without any verification. Before AutomorphismGroup is called, the honest test in lib/pcgs.gi:1572 correctly returns false for this pcgs (it validates the stored indices), and GAP routes around the damage — which is exactly why all three steps are needed to see the bug.

4. ElementaryAbelianSeries trusts the flag (lib/grpperm.gi:1474 → PcgsElementaryAbelianSeries → EANormalSeriesByPcgs) and hands out the invalid series [64,32,16,4,2,1].

5. ElementaryAbelianSeriesLargeSteps then hangs. In DoEASLS (lib/grp.gi:1489):

  repeat
    while i<Length(N) and HasElementaryAbelianFactorGroup(I,N[i+1])
      and (IsIdenticalObj(I,N[i]) or not N[i] in S) do
      i:=i+1;
    od;
    I:=N[i];
    Add(L,I);
  until Size(I)=1;

At i = 3 the guard HasElementaryAbelianFactorGroup(N[3], N[4]) is false, so i never advances and the repeat loop appends to L forever. That is the frame @fingolfin saw under Ctrl-C; CRISP only shows up in the traceback because CompositionSeriesUnderAction calls InvariantElementaryAbelianSeries(G, act) right after AutomorphismGroup(G).

Fix

I am preparing a PR with:

• lib/pcgsspec.gi: broaden the reuse guard so that a pcgs which already carries any of IndicesEANormalSteps / IndicesChiefNormalSteps / IndicesCentralNormalSteps / IndicesPCentralNormalStepsPGroup is not reused as the special pcgs (since Set… on an already-set attribute is silently ignored, reuse would leave it inconsistent).
• lib/grp.gi: make DoEASLS raise an error instead of looping forever when the series it gets is not elementary abelian — a hang here is never the right outcome.
• a regression test in tst/testbugfix/.

With that change ElementaryAbelianSeries(H) is valid again and CRISP's CharacteristicSubgroups(H) returns the same 15 subgroups ([1,2,2,2,4,4,4,8,16,16,16,32,32,32,64]) as the non-triggering fast path.

Follow-up for @hulpke

Step 1 above is left untouched by that fix, and looks like a separate latent problem: IndicesEANormalSteps is deliberately overloaded as a generic "indices of the steps of the series belonging to this pcgs", including for central pcgs where the factors are not elementary abelian. lib/grppc.gi:1306 and lib/grppc.gi:1496 read IndicesEANormalSteps(home) where home is PcgsCentralSeries(G) resp. PcgsPCentralSeriesPGroup(G), and lib/claspcgs.gi:660/1038 do the same — which is presumably why or cent is there in the first place. So any pcgs from PcgsCentralSeries / LowerCentralSeriesOfGroup still reports EANormalSeriesByPcgs values that are not elementary abelian series. Fixing that properly means teaching those consumers to use IndicesCentralNormalSteps in the central branch; I did not want to bundle that with a bug fix. Does the overload look intentional to you, or should the central call sites be migrated?

---

AI disclosure: the analysis above and the accompanying patch were prepared with the help of Claude Code (Claude Opus 5); the reproducer reduction, the diagnostic sessions and the proposed patch were produced by the tool and reviewed by me.