[GAP Forum] element in ideal (more specific)

[Alexander Hulpke]

Dear Forum,

b-eide (no real name given) asked:

>> I was asked to be more specific about my "element in ideal"  
>> question:  >This is what I am trying to do:
>
>> I have a matrix group with 3 generators (3 by 3 matrices), G.
>> Then R is the Group Ring over the integers,
>> R:=GroupRing(Integers,G);
>> Then I have
>> emb:=Embedding(G,R);
>> so that I could create 4 elements in R such as,
>> R3:=A^emb+B^emb+C^emb;
>> b;
>> where A, B, and C are 3 by 3 matrices.
>> Next, I created a right ideal, I, by generators(R3,R13,R6,R10) in R,
>> I:=RightIdealByGenerators(R,R3,R13,R6,R10);
Presumably
RightIdealByGenerators(R,[R3,R13,R6,R10]);

>>
>> Finally I have 3 more elements in R which look similar to R3 and  
>> I'd like to
> determine if they are in the ideal I.
>> I tried "in":
>> R7 in I;
>> and I got the error
>> Error, no method found! For debuggin hints type ?Recovery from  
>> NoMethodFound.
>> Error, no 1st choice method found for 'Basis' on 1 arguments called  
>> from
> NiceBasis(B) called from BasisVectors(MB!.immutableBasis ) called  
> from BasisVectors(MB)
> called from NrBasisVectors(MB) called from...
>
> If GAP cannot do this, does anyone know a software package that will?

Let me describe what GAP does, and where it fails. From this it should  
be clear how one can test "by hand" whether an element is an ideal (Or  
what is  needed to add functionality to make the `in' command working).

GAP  translates the problem into a linear algebra problem. It chooses  
a basis (presumably just the images of the group elements) for the  
algebra R. With respect to this basis every subring is simply a  
subspace of row vectors. To find a linear spanning set for the ideal  
R3, it  essentially uses what is called the spinning algorithm for  
submodules. We assume that we have a subspace T, which is initialized  
to be the space spanned by the ideal generators. We now iteratively  
expand T.
We form the products of all (linear) generators of T with all (linear)  
generators of R. If the product does not lie in T, we extend T with  
this product as new linear generator.
The process ends, once all products are found to lie in T.
At this point T will be the ideal R3, and we have a basis for it.
Testing from membership in the ideal now is simply testing for  
membership in the subspace T.

The problem arises,  because you form the group ring over the  
integers. (So de facto we do not have subspaces, but only submodules.)  
The membership test in such a submodule is not just Gaussian   
elimination, but requires an Hermite normal form. This is where GAP  
trips up. (Actually it even trips up a moment earlier when trying to  
find a basis, because methods for basis are only implemented over  
fields.)

Adding all this functionality to the system is a little bit tricky,  
because it would involve extending most of the vector space  
functionality to Z- modules. Still all the underlying machinery is  
available in the system. So what you could do is to construct the Z- 
submodule T yourself, doing membership tests using mobile forms.

What you also could do is to replace Integers by Rationals your  
definition of R. As long as your elements are simple sums of group  
elements, membership in the ideal should be the same regardless over  
which  scalar ring you are working.

There is of course one further difficulty. The vector space (module)  
over which we are working has dimension |G|. Once this goes beyond a  
few 10,000 you will likely run into memory problems. I do not have a  
good idea how to avoid this in general.
You could however replace R with an image under any representation of  
G. The image would be a smaller dimensional vector space, and you  
could test membership in this image  first.
A single image will give you only a necessary condition. If you use  
all irreducible representations of G (assuming we are working  
characteristic zero), I would think that one can use Wedderburn's  
structure theorem to patch a result together.

All the best,

Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke