Broken example in GAP master branch

[olexandr-konovalov]

The following code is based on example from Chapter 4:

LoadPackage("unitlib":OnlyNeeded);
IdGroup(DihedralGroup(128));
V := PcNormalizedUnitGroupSmallGroup( 128, 161 );
C := Center( V );           
gens := MinimalGeneratingSet( C );;
Length(gens);
KG := UnderlyingGroupRing( V );
f := NaturalBijectionToNormalizedUnitGroup( KG );;
gens1:=List(gens,x -> x^f);
IsAbelian(Group(gens1));

In GAP 4.8.8, the last command returns true and in the master branch it returns false. Reproducible in various settings, including -r -A options.

[olexandr-konovalov]

It also works faster in my GAP 4.8.8 installation (the whole test as well).

[olexandr-konovalov]

For dihedral 2-groups, minimal order to reproduce this is 32: start with

V := PcNormalizedUnitGroupSmallGroup( 32,18 );

Actually, it happens for a number of groups of order 32, namely groups with numbers

2 5 9 10 11 12 18 19 20 27 28 29 30 31 32 33 34 35 39 40 41 42 49 50 

and not for any 2-groups of a smaller order.

[fingolfin]

But note:

gap> IsAbelian(C);
true

So it is your NaturalBijectionToNormalizedUnitGroup which produces nonsense.

[fingolfin]

Indeed, this is the code from Laguna:

InstallMethod( NaturalBijectionToNormalizedUnitGroup,
        "LAGUNA: for modular group algebra of finite p-group",
        true,
        [ IsPModularGroupAlgebra ],
        0,
        FG -> GroupHomomorphismByImagesNC( 
	           PcNormalizedUnitGroup( FG ),
                   NormalizedUnitGroup( FG ),
                   GeneratorsOfGroup( PcNormalizedUnitGroup( FG ) ),
                   GeneratorsOfGroup( NormalizedUnitGroup( FG ) ) ) );

If you remove the NC, it will return fail.

[olexandr-konovalov]

@fingolfin thanks, this helps to localise example. LAGUNA and UnitLib had no recent changes - I will try to look for a change in GAP that triggers this. The theory behind LAGUNA guarantees 1-to-1 correspondence between generators, hence NC-version was used all that time.

[fingolfin]

I bisected this. The above examples stopped working with GAP commit gap-system/gap@25cfbbe which was part of gap-system/gap#609 and changed our sorting algorithm to a faster one. But both algorithms are not stable sorts, and this would break code which implicitly relayed on the specific algorithm.

The example with a dihedral group of order 32 indeed is fixed for me if I change Laguna to use StableSortParallel instead of SortParallel. Unfortunately, the original example of order 128 is not fixed by this. I strongly suspect that some other code in Laguna and/or UnitLib and/or the GAP library implicitly relies on the sort being stable (or, worse, on the sort being unstable in exactly the way the old GAP sorting mechanism was -- but I consider that at least to be rather unlikely).

[fingolfin]

To test the theory, I just replaced all SortParallel calls in the GAP library by StableSortParallel. That did not resolve the issue, however. Of course it's still possible that a call to Sort, SortedList, AsSortedList, Set, AsSet, ... is responsible. Or some code which does not even call any of them directly. Hard to say.

[olexandr-konovalov]

Thanks @fingolfin. Just to provide some more context, UnitLib contains a databased of presentations for unit groups, computed with LAGUNA. When it retrieves a unit group from its database, it reconstructs a group algebra of SmallGroup(m,n) for appropriate arguments, and then tells that its unit group is the one given by that presentation. It relies on the stability of the small groups library. Also, it saves some details about Jennings series of the underlying group, because those may depend on randomised algorithms. Maybe it should save details about the weighted basis too to avoid mismatch. I need to think. Maybe the way is to run over all unitlib collections in GAP 4.8.8 and save that additional information there. I will think.

[olexandr-konovalov]

@fingolfin wrote

I strongly suspect that some other code in Laguna and/or UnitLib and/or the GAP library implicitly relies on the sort being stable (or, worse, on the sort being unstable in exactly the way the old GAP sorting mechanism was -- but I consider that at least to be rather unlikely).

Actually, it was indeed the worst of the mentioned above alternatives. LAGUNA accumulated elements of the weighted bases in wb and their weights in weights and then called SortParallel( weights, wb ). I don't think there was an assumption of sort being stable. If there was any assumption, it was that the order in which elements of the weighted basis are added to wb is the same. In addition, UntiLib assumes that groups in Small Groups Library are not changing the way how they are given - that's really crucial here.

I think that switching to StableSortParallel and rebuilding the database will make it more robust. However, one could go even further and enforce the strict ordering on weighted basis elements of the same weight:

            # Order elements of the weighted basis by their weights.
            # Then fix the ordering of elements of the same weight
            SortParallel( weights, wb );
            for k in [ 1 .. Maximum( weights) ] do
              pos := Positions(weights,k);
              if Length(pos) > 1 then
                wb{pos}:=AsSSortedList(wb{pos});
              fi;
            od;

I intend to recalculate UnitLib database and provide a new version for GAP 4.9.

[olexandr-konovalov]

Fixed in #7