Extend invariant computation to permutation groups

[fingolfin]

The function invariant_ring currently is implemented for matrix groups (resp. a list of matrix generators).

We should also add a constructor invariant_ring(K::Field, G::PermGroup) (with K defaulting to QQ if it is omitted).

In the first approximation, this could simply create an isomorphic matrix group over K, generated by the corresponding permutation matrices. That will be good enough to get us going.

I think various algorithms could potentially be made faster in this context, too. E.g. at the very bottom level, the action of a permutation (matrix) on a polynomial is cheaper to compute than that of an arbitrary matrix. Alas, we don't want to duplicate everything. My hope would be that we can carefully restructure the code, adding a few key abstraction with differing implementations for matrix vs. permutation groups, and then Julia does the rest for us... Of course that's just a rather high-level naive thought, one needs to look carefully over the code and implementation (and possibly re-implement more Singular code in Julia)

[joschmitt]

Without really looking into it I would say that it should not be too much of a problem to implement a special right_action for elements of permutation groups and let Julia call it if appropriate. And as soon as one can compute bases of a fixed degree component the primary and secondary invariants should "just work".

However, I didn't have time in the past weeks (months?) to really work on the invariant theory and I still have work-in-progress branches for better secondary invariants and algebra syzygies lingering around...

[fingolfin]

Yeah, I also don't think it'll require too much effort, and when I have some spare time, I'll try to tackle it.

As to your work in progress: Feel free to open draft PRs for those WIP branches, then perhaps others can help out.

[ThomasBreuer]

Since I am interested (at least) in the group action part, I have made an experiment. The following works after a few changes.

julia> G = symmetric_group(3); action = gens(G); IR = Oscar.InvRing(QQ, G, action)
Invariant ring of
Sym( [ 1 .. 3 ] )
with generators
PermGroupElem[(1,2,3), (1,2)]

julia> primary_invariants(IR)
3-element Vector{MPolyElem_dec{fmpq, fmpq_mpoly}}:
 x[1] + x[2] + x[3]
 x[1]*x[2] + x[1]*x[3] + x[2]*x[3]
 x[1]^3 + x[2]^3 + x[3]^3

julia> secondary_invariants(IR)
1-element Vector{MPolyElem_dec{fmpq, fmpq_mpoly}}:
 1

Here is the list of changes:

• In the InvRing construction, construct permutation matrices from the given permutations such that the field action_singular can be set.
• Add a right_action(R::MPolyRing{T}, p::PermGroupElem) method that returns MapFromFunc((f::MPolyElem{T}) -> on_indeterminates(f, p), R, R); I am not sure whether it is a good idea to wrap each group element into a mapping just in order to get a unary operation.
• The function _molien_series_char0 currently assumes that the group in question is a matrix group of a certain type, and that Oscar.isomorphic_group_over_finite_field can be applied to it. This is done only in order to be able to compute conjugacy class representatives, this step can be omitted for permutation groups.
• Again in _molien_series_char0, the characteristic polynomial of the group element is computed. Here one has to provide a meaning for the permutation g, for example by switching to permutation_matrix(K, g).

[joschmitt]

This looks good, thank you! I hope that the action_singular can be completely removed at some point. But so far it is at least needed for the fundamental invariants which still call the Singular implementation. When I implemented right_action it was to have this functionality at all. I think for matrices it makes sense to return a map, because one can do some precomputations. If you have other suggestions, I'm of course open for this. In the end, group actions should probably exist generically anyways? Probably they already do?

[ThomasBreuer]

Concerning the availability of group actions, there is src/Groups/action.jl, which defines for example on_indeterminates(f::Nemo.MPolyElem, s::PermGroupElem) to return the polynomial obtained from f by permuting the indeterminates with s. (The analogous function for the matrix action on multivariate polynomials is not yet there.)