matrix groups not necessarily over finite fields

[ThomasBreuer]

Currently MatrixGroup claims to cover only subgroups of the groups GL(n,q), that is, matrix groups over finite fields. This means that we cannot create for example a matrix group over the Integers, the Rationals, or a number field.

Are there already ideas to implement other matrix groups than subgroups of GL(n,q)?

We can write down matrices on the Julia side, with type fmpq_mat or AbstractAlgebra.Generic.MatSpaceElem{nf_elem}. It would be useful to use these matrices for the action on relevant Julia objects, and to wrap them into GAP objects in case that there are interesting GAP functions which one wants to use. (Converting the Julia matrices to the GAP side and then wrapping these GAP objects into group element objects in Julia --as is done for the FFE matrices-- would result in converting these GAP matrices back to julia whenever one wants to use that they are matrices, for example, for multiplying them with vectors.)

[fingolfin]

From my perspective, MatrixGroup is a pure placeholder right now, basically nothing has been done for it. Ultimately groups over arbitrary fields and indeed eventually arbitrary (commutative) rings should be supported. The problem there is that support for these in GAP is also rather underdeveloped.

I guess you, @GDeFranceschi and me (and possibly others) should at some point (soon) have a chat about how to proceed there. In the meantime, in the course of working on computational algebraic invariants, I had some discussions with @fieker. So first off, we really would like for the OSCAR user interface to provide a unified front, and that indeed would mean that when one e.g. asks an OSCAR matrix group for its base_ring, I'd expect it to return something like QQ or ZZ or GF(3,2), i.e. the OSCAR rings, not the GAP rings.

And yeah we'd need conversions between the various rings and their elements, and vectors, matrices, etc. (I actually already have some code which I should commit to Oscar ASAP).

In order to avoid too many conversions, we could use something like the mutable struct BiPolyArray trick @fieker uses to bridge between Oscar's mpoly and Singular's spoly: so, for a matrix group, we'd have a mutable struct MatrixGroup{R} or so, where R parametrizes the (type of the) domain, and in there we'd lazily store ...

• the underlying GAP group (as we already do) (but it might actually be nothing if not (yet) needed, or if GAP doesn't even support that kind of matrix group -- so we can implement things that are not in GAP)
• the basering as an Oscar ring
• perhaps also the degree d (so we are looking at d\times d matrices), as an Int64
• optionally the basering as a GAP ring (if needed/available)
• optionally the list of generators as Oscar matrices (e.g. if that's what the user provided; or if the user already asked for them)
• perhaps also an (optional) map between Oscar and GAP basering resp. matrices? (not sure we'd need this; it might make sense if there are cases where isomorphisms exist but they are not unique, and/or setting them up requires non-trivial computations, etc.)
• ...

The "lazy" bit is important: We don't generate things unless we need them. So this is also kind of a glorified cache. We can then do interesting things: For example, say we want to compute pseudo random elements using product replacement. Initially we would just call GAP's PseudoRandom, and convert the results as needed. But later we could also re-implement the product replacement algorithm in Julia; then that implementation could work with the group generators as Oscar elements; it would directly produce an Oscar matrix, w/o an intermediate GAP matrix object.

A somewhat orthogonal approach would be to actually start using matrices from Oscar (or rather, Hecke/Nemo/AbstractAlgebra) directly in GAP, by (a) providing a full MatrixObj API implementation for them (which may involve actually completing "the MatrixObj API"), (b) modifying GAP to work with our foreign MatrixObj implementation, and (c) ultimately also finding ways to adapt the code in GAp which is specifically taylored to produce great performance with e.g. FFE matrices to also apply these enhancements to "our" FFE matrices.

The second approach is also potentially appealing to GAP users. But it also requires substantial work on the GAP side, and I'd expect it overall to require more time. But the two approaches are not really mutually exclusive anyway. We'll have to see...

[GDeFranceschi]

I sketched a piece of code in the file src/Groups/julia_GAP.jl (I think the only branch where this file is located is GDeFranceschi/Oscar.jl/GAPGroups), where there are functions converting GAP fields and matrices into AbstractAlgebra fields and matrices, and allows to evaluate GAP group functions in AbstractAlgebra matrices. But, at the moment, it works only with finite fields.

[ThomasBreuer]

@GDeFranceschi thanks for the hint. I think in general we cannot assume a context-free translation between two algebraic structures (ring, field, ...) on the Julia/Hecke/AA side and on the GAP side. For example, finite prime fields on the Julia side can be represented by Nemo.NmodRing,Nemo.GaloisField, or Nemo.FqNmodFiniteField. Conversely, an element in a field extension in GAP that is created by AlgebraicExtension can be created only if this field extension object (or one of its elements) is available as an argument in the construction. Some experiments with "context objects" for safe conversions in both directions, for elements, vectors, matrices, polynomials over a given ring, can be found in the GAP package JuliaExperimental which is part of GAP.jl.

[simonbrandhorst]

I need matrix groups over QQ and ZZ, later possibly over number fields. Typically these will be finite groups. Seems like right now they are not at all operational.

[thofma]

@joschmitt and myself have been extending them recently for applications in invariant theory. We only added what we needed. Which functionality do you need?

[simonbrandhorst]

Like any functionality would be good.

julia> g = ZZ[0 1; 1 0]
[0   1]
[1   0]

julia> G = matrix_group([g])
Matrix group of degree 2 over Integer Ring

julia> order(G)
ERROR: MethodError: no method matching ring_iso_oscar_gap(::FlintIntegerRing)
....

I have the impression that they do not work at all. Lets say I am interested in finite matrix groups over a ring/field of characteristic zero, e.g. ZZ, QQ or a number field Here are some examples of what I would like to to: Basically anything that can be done with finite groups.

• Order (if finite)
• maximal subgroups
• isomorphic permutation group
• group actions in particular the natural action of the matrices on vectors
• small group id
• homomorphisms to and from other groups
• small generating sets
• really anything I can do with such groups in gap at the moment
• defining an isomorphism to some "nice" group which is then used to do computations internally.

[fingolfin]

I have a plan to support this, just is a matter of time. Basically, the machinery is already all there (@joschmitt provided code to map a finite matrix group in char 0 to one in char p; and GAP has code to delegate operations for one group to an isomorphic image). The main things left to do is to connect all these bits. It'll happen soon (hopefully at the latest in the week starting October 4, when we have a little coding sprint on "groups in Oscar" in Kaiserslautern)

[fingolfin]

@danielrademacher made progress on this in PR #1206 and is now working on addressing things from this issue