Bug in Centre for PcGroups

[hulpke]

The following calculation

G:=SmallGroup(2^9,261648);;
Size(Center(G));

returns a center of order 4, which is wrong (One can easily check that the center has order 8).
The error persists when converting ->FP->PC, but does not arise when converting ->Perm->Fp->PC, which indicates that it is related to the particular PC presentation.

This was reported by Benjamin Sambale

[fingolfin]

The issue is already present in GAP 4.4.12. Eamonn O'Brien helped to verify that the group presentation etc. matches perfectly with what's in Magma. Magma produces three centre generators, [ G.5 * G.7, G.8, G.9 ]; while in GAP we get [G.8, id, G.9]. Computing the centre in an equivalent Pcp group also works:

gap> SmallGeneratingSet(Centre(PcGroupToPcpGroup(G)));
[ g5*g7*g9, g8, g9 ]

So next should be to check CentrePcGroup which is invoked here to compute the centre.

[fingolfin]

The problem is in the internal function NextStepCentralizer( <gens>, <cent>, <pcgsF>, <field> ) (or possibly in how it is used): That function would be correct if cent modulo pcgsF was elementary abelian. But in general it is just abelian. And in this concrete example it goes wrong when cent contains an element of order 4. Then we get to a point in the iteration of NextStepCentralizer where the auxiliary variable newgens contains an element of order 4 and its inverse; both act non-trivially, but their squares acts trivial (and is in the center). Alas, instead we compute their product, which of course is the one element.

So here is one possible fix (confirmed to work in experiments)

diff --git a/lib/grppcatr.gi b/lib/grppcatr.gi
index 044c73782..abb17b908 100644
--- a/lib/grppcatr.gi
+++ b/lib/grppcatr.gi
@@ -724,8 +724,9 @@ end);
 #F  NextStepCentralizer( <gens>, <cent>, <pcgsF>, <field> )
 ##
 NextStepCentralizer := function( gens, cent, pcgsF, field )
-    local   g,  newgens,  matlist,  notcentral,  h,  comm,  null,  j,  elm;
+    local   g,  newgens,  matlist,  notcentral,  h,  comm,  null,  j,  elm,  p;
   
+    p := Characteristic( field );
     for g in gens do
         if Length( cent ) = 0 then return []; fi;
 
@@ -750,7 +751,10 @@ NextStepCentralizer := function( gens, cent, pcgsF, field )
             # calculate elements corresponding to null
             for j  in [1..Length(null)]  do
                 elm := PcElementByExponentsNC( pcgsF, notcentral, null[j] );
-                Add( newgens, elm );
+                while not elm in GroupOfPcgs( pcgsF ) do
+                    Add( newgens, elm );
+                    elm := elm ^ p;
+                od;
             od;
         fi;
         cent := newgens;

An alternate way to think about this is that cent should always form (resp. contain) a pcgs for the subgroup it generates (modulo pcgsF), but the current code does not ensure that all powers of elements are in there.

Perhaps there is a better, more clever solution, but at 2 AM at night I can't think of one. Perhaps @hulpke or @beick have better / alternative suggestions.

For the record, the corresponding code in the polycyclic package (see function PcpNextStepCentralizer) is almost identical. It does produce the right result here, but my impression is that this is more by chance than by design, and slightly rearranging the input example might give wrong results there, too. However, I might be missing something there...

[hulpke]

Thank you, @fingolfin, for investigating. What you propose certainly will not introduce other problems. The question is whether this ommission is just an oversight, or if there is an implicit assumption on the generators that is not always satisfied:

Is the function using the familyPcgs, or a specialPcgs?

Is the result of this ruotine used as generators for a group, or is the assumption that it returns a pcgs?

[beick]

Dear all, the key step in the center algorithm is to compute the kernel of a homomorphism h : H -> F, where H is an abelian group generated by cent, F is elementary abelian given by a pcgs. This is then iteratedly applied to the commutator map H -> F : h -> Comm(h,g) for g looping over a generating set of G. Since F is elementary abelian and H abelian, H^p is in the kernel of h. The induced map H/H^p -> F is then a linear map of elementary abelian groups and the kernel can be computed using a nullspace computation. If N is this nullspace, then a short generating set of the kernel of h would be given by <N, p I>, where I is the identity map. It is essential for the performance of the algorithm that H is given by a short generating set cent, and that the generating set of the kernel is also short. Perhaps it is more efficient to compute a triangular matrix corresponding to <N, pI> and translate this to cent. Does that makes sense? Best wishes, Bettina

[fingolfin]

I've made PR #5036 with a patch bei @beick suggested via email.