4
$\begingroup$

Let $R=\mathbb{Z}/1024\mathbb{Z}$ and $G=GL(3,R)$. Let $H$ be the subgroup of $G$ consisting of all matrices with determinant $1$ which are congruent to the identity matrix modulo the ideal $4R$. Let

$A=\begin{pmatrix} 1 &0&512\\ 0& 1&0\\0&0 &1\end{pmatrix}$ and $B=\begin{pmatrix} 1 &4&2\\ 8& 1&4\\16 &8 &1\end{pmatrix}$.

Can one use GAP (or other software) to find out if $A\in B^H$? (Here $B^H$ is the subgroup of $G$ generated by the set $\{ B^h\mid h\in H\}$.)

$\endgroup$
3
  • 2
    $\begingroup$ Yes, in principle, and this is quite easy to do for smaller rings -- but $\operatorname{GL}(3, R)$ has order $2^{84} \cdot 3 \cdot 7$, so this might take quite some time in your case (and this is not a limitation unique to GAP!). $\endgroup$ Jun 15, 2021 at 14:51
  • $\begingroup$ About what amount of time are we talking here? $\endgroup$
    – Ralle
    Jun 18, 2021 at 7:48
  • 3
    $\begingroup$ Yes, if we wanted to write down all elements this would be hopeless. But grouop theoretic algoriths try to describe the large group using a much smaller data structure, which makes it feasible to do this kind of calculation. $\endgroup$
    – ahulpke
    Jul 11, 2021 at 16:21

1 Answer 1

5
$\begingroup$

It is contained. Here is the way I did the calculation with GAP. It ought to work nicer, but there is a stupid technical issue in the way that makes it hard to implement a membership test in a subgroup. (The issue is basically that we cannot guarantee that elements will always lie in one big parent group.)

Thus, one needs to do things in a somewhat pedestrian way. You will need my matgrp package for some calculations in the large groups over residue class rings to work:

gap> LoadPackage("matgrp");
true
gap> A:=[[1,0,512],[0,1,0],[0,0,1]];
[ [ 1, 0, 512 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ]
gap> B:=[[1,4,2],[8,1,4],[16,8,1]];
[ [ 1, 4, 2 ], [ 8, 1, 4 ], [ 16, 8, 1 ] ]
gap> r:=Integers mod 1024;
(Integers mod 1024)
gap> Ar:=A*One(r);
[ [ ZmodnZObj( 1, 1024 ), ZmodnZObj( 0, 1024 ), ZmodnZObj( 512, 1024 ) ],
  [ ZmodnZObj( 0, 1024 ), ZmodnZObj( 1, 1024 ), ZmodnZObj( 0, 1024 ) ],
  [ ZmodnZObj( 0, 1024 ), ZmodnZObj( 0, 1024 ), ZmodnZObj( 1, 1024 ) ] ]
gap> Br:=B*One(r);
[ [ ZmodnZObj( 1, 1024 ), ZmodnZObj( 4, 1024 ), ZmodnZObj( 2, 1024 ) ],
  [ ZmodnZObj( 8, 1024 ), ZmodnZObj( 1, 1024 ), ZmodnZObj( 4, 1024 ) ],
  [ ZmodnZObj( 16, 1024 ), ZmodnZObj( 8, 1024 ), ZmodnZObj( 1, 1024 ) ] ]
gap> G:=GL(3,r);
GL(3,Z/1024Z)
gap> FittingFreeLiftSetup(G);; # build a data structure for group order
gap> Size(G);
406199075390515402701275136

Next we look at the image modulo 4. We construct it also as a permutation group (so we can use permutation group functionality for homomorphisms:

gap> rf:=Integers mod 4;
(Integers mod 4)
gap> gens:=List(GeneratorsOfGroup(G),m->List(m,r->List(r,x->Int(x)*One(rf))));;
gap> q:=Group(gens);
<matrix group with 5 generators>
gap> Size(q);
86016
gap> Size(GL(3,rf));
86016
gap> isop:=IsomorphismPermGroup(q);;
gap> p:=Image(isop);

We now construct a map from this permutation group to the matrix group and collect generators for its co-kernel -- these are evaluated relators for the factor that together will generate the kernel of the reduction map on $G$:

gap> reverse:=GroupGeneralMappingByImagesNC(p,G,GeneratorsOfGroup(p),
> GeneratorsOfGroup(G));;
gap> it:=CoKernelGensIterator(reverse);
<iterator>
gap> hg:=[];;
gap> for i in it do
>   if not IsOne(i) then
>     Add(hg,i);
>   fi;
> od;
gap> Length(hg);
448

This number of generators is a bit too large. We just pick 20 random ones and verify they still generate the kernel. (Would iterate/try more generators if not):

gap> preH:=Group(List([1..20],x->Random(hg)));
<matrix group with 20 generators>
gap> FittingFreeLiftSetup(preH);;
gap> Size(G)/Size(preH);
86016

Now for determinant 1. We use the same idea for the homomorphism onto the determinant, and get $H$ as kernel

gap> dets:=List(GeneratorsOfGroup(preH),DeterminantMat);;
gap> d:=Group(det); # GAP will issue a harmless warning that it assumes the elements indeed are invertible
<group with 20 generators>
gap> Size(d);
256
gap> isop:=IsomorphismPermGroup(d);;
gap> p:=Image(isop);;
gap> reverse:=GroupGeneralMappingByImagesNC(p,preH,GeneratorsOfGroup(p),
> GeneratorsOfGroup(preH));;
gap> it:=CoKernelGensIterator(reverse);;
gap> hg:=[];;
gap> for i in it do
>   if not IsOne(i) then
>     Add(hg,i);
>   fi;
> od;
gap> Length(hg);
4873
gap> H:=Group(List([1..20],x->Random(hg)));;FittingFreeLiftSetup(H);;
gap> Size(preH)/Size(H);
256

Now we are ready to calculate $B^H$. We use a standard closure algorithm, starting with $B$ and then take conjugates of generators with generators of $H$ until no new conjugates arise, that is the group is normal.

To test membership $x\in S$, we check (this is the kludge I mentioned) whether $|S|=|\langle S,x\rangle|$. (Indeed this ought to be better, but it still beats hand-calculations.)

gap> bco:=[Br];;
gap> sub:=Group(bco);;
gap> FittingFreeLiftSetup(sub);;
gap> Size(sub);
512
gap> for i in bco do
>   for j in GeneratorsOfGroup(H) do
>     x:=i^j;
>     t:=Group(Concatenation(bco,[x]));
>     FittingFreeLiftSetup(t);
>     if Size(t)<>Size(sub) then
>       Add(bco,x);
>       sub:=t;
>     fi;
>   od;
> od;

We now use the same kludgy element test to see whether $A\in B^H$:

gap> Size(sub);
4503599627370496
gap> t:=Group(Concatenation(bco,[Ar]));
<matrix group with 11 generators>
gap> FittingFreeLiftSetup(t);;
gap> Size(t);
4503599627370496

The order stays the same after adding $A$, thus $A\in B^H$.

$\endgroup$
6
  • $\begingroup$ Thank you very much! In my question I demanded that the elements of $H$ have determinant $1$. Was this taken into account in your solution? $\endgroup$
    – Ralle
    Jul 12, 2021 at 13:05
  • 1
    $\begingroup$ Sorry, I had overlooked this extra condition. Is included now. Since $B^H$ stays the same, the result is the same. $\endgroup$
    – ahulpke
    Jul 12, 2021 at 16:08
  • $\begingroup$ Thanks again! I have a question, regarding We now construct a map from this permutation group to the matrix group and collect generators for its co-kernel -- these are evaluated relators for the factor that together will generate the kernel of the reduction map on G. Could you explain why these elements generate the kernel of the reduction map? $\endgroup$
    – Ralle
    Jul 14, 2021 at 9:14
  • $\begingroup$ As far as this question is concerned, we verified that they generate a subgroup of correct index (and could verify that they reduce to zero mod 4). More generally, this is the specification of the function (which is used to calculate kernels of homomorphisms) -- see e.g. Holt, Handbook of CGT. $\endgroup$
    – ahulpke
    Jul 14, 2021 at 14:19
  • $\begingroup$ Is it possible to get a (short) expression of $A$ as a product of generators $B^h$ of $B^H$? $\endgroup$
    – Ralle
    Jul 23, 2021 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.