[GAP Forum] Computing kernel

[Alexander Hulpke]

Dear Mathieu,

> thank you very much, it works.
Glad to hear.

> 
> Still, it appears to me that the FreeGroup trick serves essentially
> to trigger off the checking of redundancy of generators.

No. The way how the system treats subgroups is fundamentally different. By default GAP has groups given by generators and builds data structures to allow for membership testing. The last fallback is to enumerate all elements, making the assumption that we can test cheaply for element equality.

In the case of finitely presented groups, a subgroup of finite index is by default represented as full preimage of a subgroup in a finite quotient. Calculations such as element test, intersection, normalizer etc. can be moved in this finite quotient. Subgroup generators are not computed unless a user asks explicitly about it. (This really just uses finite generation and the ability to assert that something is a homomorphism.)

> It looks like a hack.

It does so because the finite presentation is not needed. But the approach based on a membership test will definitely not work and the approach via finite images looks plausible to me.

>  I understand that checking redundancy of generators
> is expensive, but actually I am fine with having lots of generators.

The problem is that lots tend to accumulate once you iterate calculations or indices get larger. For example by default when reducing GL_3(Z) modulo 7 you would get about 10 million generators for the kernel -- this will choke anything.

I would be curious to hear what you eventually would like to calculate. I'm still not sure what the appropriuate functions for infinite matrix groups should be, and it is always helpful to see what people actually want to do.

> Also, does your two approaches use different algorithms?
Yes, the code for fp groups is completely different than the generic one using generators and membership.

Best,

   Alexander