Type instability in quo for groups

[joschmitt]

quo for groups is type instable:

julia> K, a = cyclotomic_field(3, "a");
julia> G = matrix_group(matrix(K, 2, 2, [ a, 0, 0, inv(a) ]), matrix(K, 2, 2, [ 0, 1, 1, 0 ])); # finite group, non-abelian
julia> H, HtoG = derived_subgroup(G);
julia> typeof(quo(G, H)[1])
PcGroup

julia> G = matrix_group(matrix(K, 2, 2, [ a, 0, 0, inv(a) ])); # finite group, abelian
julia> H, HtoG = derived_subgroup(G);
julia> typeof(quo(G, H)[1])
MatrixGroup{AbsSimpleNumFieldElem, AbstractAlgebra.Generic.MatSpaceElem{AbsSimpleNumFieldElem}}

julia> G = matrix_group(matrix(K, 2, 2, [ 1, 1, 0, 1 ])); # infinite group
julia> H, HtoG = derived_subgroup(G);
julia> typeof(quo(G, H)[1])
MatrixGroup{QQFieldElem, QQMatrix}

In particular the first vs. the second case is pretty annoying.

[fieker]

On Thu, Mar 17, 2022 at 08:22:01AM -0700, Johannes Schmitt wrote: `quo` for groups is type instable:

I'm not too certain that can be avoided, but we can try to ask Max... The type-instability is inherited from gap

…

``` julia> K, a = CyclotomicField(3, "a"); julia> G = matrix_group(matrix(K, 2, 2, [ a, 0, 0, inv(a) ]), matrix(K, 2, 2, [ 0, 1, 1, 0 ])); # finite group, non-abelian julia> H, HtoG = derived_subgroup(G); julia> typeof(quo(G, H)[1]) PcGroup julia> G = matrix_group(matrix(K, 2, 2, [ a, 0, 0, inv(a) ])); # finite group, abelian julia> H, HtoG = derived_subgroup(G); julia> typeof(quo(G, H)[1]) MatrixGroup{nf_elem, AbstractAlgebra.Generic.MatSpaceElem{nf_elem}} julia> G = matrix_group(matrix(K, 2, 2, [ 1, 1, 0, 1 ])); # infinite group julia> H, HtoG = derived_subgroup(G); julia> typeof(quo(G, H)[1]) MatrixGroup{fmpq, fmpq_mat} ``` In particular the first vs. the second case is pretty annoying. -- Reply to this email directly or view it on GitHub: #1178 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[joschmitt]

It makes it really hard to write "generic" code. I have a function that takes a (finite) matrix group and computes the abelianization and then turns it into a GrpAbFinGen. I thought I managed this, until I tried it with an abelian group and ran into case 2 above.

[fieker]

On Thu, Mar 17, 2022 at 08:42:09AM -0700, Johannes Schmitt wrote: It makes it really hard to write "generic" code. I have a function that takes a (finite) matrix group and computes the abelianization and then turns it into a `GrpAbFinGen`. I thought I managed this, until I tried it with an abelian group and ran into case 2 above.

I understand. Lets try to find Max tomorrow.

…

-- Reply to this email directly or view it on GitHub: #1178 (comment) You are receiving this because you commented. Message ID: ***@***.***>

[fingolfin]

I have not yet had a chance to look at this issue resp. the examples in detail (I will tomorrow), but it is unlikely that we can ever achieve type stability for quo in general (well, perhaps unless we agree to always return an FPGroup which then is useless for most actual computation)

However, it should actually not at all be a problem to write this generically -- you don't need type stability for that, as any abelian GAP group can be deal with in a uniform way. But really this is part of issue #161 which is long overdue, and @ThomasBreuer and me should focus on resolving that ASAP.

Anyway, I'll have a proper look tomorrow.

[ThomasBreuer]

O. k., I am working on the mapping between abelian GAP groups and GrpAbFinGen groups.

[fingolfin]

I've discussed this with @ThomasBreuer this morning. For now the plan is to add methods for quo and isomorphism which take as first argument the desired type for the result (and which throw an exception if that type is not possible).

Indeed, this is precisely what maximal_abelian_quotient does, the existing function that you may wish to use in your case. However, it does not currently support GrbAbFinGen (@ThomasBreuer please take care of this one, too?)

One the long run, for permutation, fp and pc groups, type stability for quo is not a problem, but it is for matrix groups, as in general quotients of matrix groups are not matrix groups in a computationally meaningful way. For these, the only result type that would always work is FPGroup. But that's not ideal computationally either, as in general the quotient as computed by GAP may not have a known finite presentation, so one first has to compute one, which can make an otherwise efficient quotient computation much slower...

Of course for special quotients, we could offer special function that are type stable in a different way; e.g. maximal_abelian_quotient could return a GrpAbFinGen by default, as this always allows representing the result.

(One concern I have about GrpAbFinGen is that it is additive, and that makes for some awkwardness in generic code, which can deal either with GAP groups, or with GrpAbFinGen. I think we also need a multiplicative variant of GrpAbFinGen, and then possibly interface it with the GAP side... Or perhaps on the GAP side, we can add a few methods to make the "abelian FP groups" more useful...

[fingolfin]

Just to say: maximal_abelian_quotient(GrpAbFinGen, G)[1] works great for the first two examples.

For the final one, it doesn't. That's because it's an infinite abelian matrix group, and GAP has no particularly good tools to deal with such groups. In this particular case, the group is cyclic, so we could of course produce that information somehow. But producing an efficient homomorphism from such a matrix group onto a GrpAbFinGen probably is difficult in general (of course in this particular example we can easily write it down, but I am not sure how helpful that is in general? I mean, just take matrix_group(matrix(K, [ 2 1 ; 17 8 ])), can we solve the discrete logarithm problem for this? What about matrices of larger degree?

But perhaps you don't need this map? Then one could provide helpers to just get that, e.g. perhaps as a wrapper for GAP's AbelianInvariants.

[fieker]

On Wed, Mar 15, 2023 at 07:57:09AM -0700, Max Horn wrote: Just to say: `maximal_abelian_quotient(GrpAbFinGen, G)[1]` works great for the first two examples. For the final one, it doesn't. That's because it's an infinite abelian matrix group, and GAP has no particularly good tools to deal with such groups. In this particular case, the group is cyclic, so we could of course produce that information somehow. But producing an efficient homomorphism from such a matrix group onto a `GrpAbFinGen` probably is difficult in general (of course *in this particular example* we can easily write it down, but I am not sure how helpful that is in general? I mean, just take `matrix_group(matrix(K, [ 2 1 ; 17 8 ]))`, can we solve the discrete logarithm problem for this? What about matrices of larger degree?

DiscLog on the eigenvalues?

…

But perhaps you don't *need* this map? Then one could provide helpers to just get that, e.g. perhaps as a wrapper for GAP's `AbelianInvariants`. -- Reply to this email directly or view it on GitHub: #1178 (comment) You are receiving this because you commented. Message ID: ***@***.***>

[ThomasBreuer]

Concerning the infinite abelian matrix group, IsomorphismPcpGroup from GAP's Polenta package would be the natural candidate, but the example matrix_group(matrix(K, [ 2 1 ; 17 8 ])) wants to use PARI/GP and runs into an error if this is not available.

[fieker]

On Wed, Mar 15, 2023 at 08:47:22AM -0700, Thomas Breuer wrote: Concerning the infinite abelian matrix group, `IsomorphismPcpGroup` from GAP's Polenta package would be the natural candidate, but the example `matrix_group(matrix(K, [ 2 1 ; 17 8 ]))` wants to use PARI/GP and runs into an error if this is not available.

SO a natural candidate for an Oscar re-write...

…

-- Reply to this email directly or view it on GitHub: #1178 (comment) You are receiving this because you commented. Message ID: ***@***.***>