quantum_autmorphism_groups of matroid

[Sequenzer]

Add the functions quantum_permutation_group and quantum_automorphism_group to Oscar.

Both the quantum permutation group and the quantum automorphism group (of matroids) are defined in Quantum Automorphisms of Matroids.

Since both of these mathematical objects are defined as quotients of a non-commutative polynomial ring, I decided to represent them in OSCAR as just the vector of generators.

All functions are basically done. Suggestions for better tests are welcome.

[fingolfin]

Hi there, thanks for your contribution! I left a few suggestions for improving the code

[lgoettgens]

some misc julia/style things I noticed while reading through this. I have no knowledge about the mathematics involved

[Sequenzer]

I believe, I did something addressing all of your comments, Thank you guys :)

[codecov]

Codecov Report

Attention: Patch coverage is 96.03960% with 4 lines in your changes missing coverage. Please review.

Project coverage is 84.64%. Comparing base (efd6412) to head (53742db).
Report is 64 commits behind head on master.

Files	Patch %	Lines
...binatorics/Matroids/quantum_automorphism_groups.jl	96.03%	4 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #3950      +/-   ##
==========================================
+ Coverage   83.98%   84.64%   +0.65%     
==========================================
  Files         592      597       +5     
  Lines       81635    82647    +1012     
==========================================
+ Hits        68562    69956    +1394     
+ Misses      13073    12691     -382     

Files	Coverage Δ
src/Rings/FreeAssAlgIdeal.jl	87.17% <ø> (ø)
...binatorics/Matroids/quantum_automorphism_groups.jl	96.03% <96.03%> (ø)

... and 71 files with indirect coverage changes

[fingolfin]

Thanks to @Sequenzer for addressing the barrage of comments and suggestions by @lgoettgens and myself, well done :-)

Just as note: since GitHub's PR review feature is really stupid and often prefers showing resolved & outdated source code comments over newer, unresolved comments (which are then hidden behind a "show more comments..." button/link), I've deleted a bunch of, well, resolved & outdated comments by @lgoettgens and myself, to "unclog" the system a bit (this is of course crude. GH should fix their system, but I've been waiting for a long time now for that, so I don't think we can wait for it)

[fingolfin]

I have a hard time understanding this code :-( probably because I am missing some matroid theory?

So sets contains all bases/circuits/flats, sizes all sizes of those that occur; setSizes then is the same as sizes except duplicates aren't removed; you then count for each size how often it turns up.

Side remark: By chance (for unrelated reasons) yesterday I asked on the Julia slack about a convenient function doing such a thing and @lgoettgens pointed out multiset to me -- you might consider using setsCount = multiset(length.(sets)) which returns an MSet which counts for each key how often it occurs in it.

Aaanyway: for a set of size $n$ there are $\binom{n}{i}$ subsets of size $i$. So why do you check against SetsCount[i] == n^i and not SetsCount[i] == binomial(n,i) ?

Unless those sets are actually also multisets and may contain repetitions, then n^i makes of course sense.

But then why are the non-sets computed as n^i - (SetsCount[i] * factorial(i)) and not n^i - SetsCount[i] ?

Perhaps all of this is obvious when one is deep in this, but perhaps also some comments could be added, and perhaps some variables have bad names (e.g. if these "sets" are not "sets")

[Sequenzer]

So the answer is yes, these sets could technically be multisets containing repetitions, but for the implemented axiom structures they don't contain any duplicates. This means that the check against SetsCount[i] == n^i is useless at best.

We count with n^i -(SetsCount[i] * factorial(i)), because sets = getproperty(Oscar, structure)(M) will only return one permutation for each set of the chosen structure. In the cited paper we argue that instead of choosing sets from the powerset of the groundset, we need to generalise to new bases/circuits/hyperplanes which are a subset of all tuples consisting of elements of the groundset. In the case of bases, for example, this means that a basis is a tuple such that it has no duplicate elements and the support defines a basis in the classical sense.

As an example: If {1,2,3} is a classical basis, then (1,2,3), (2,1,3), (2,3,1), (1,3,2), (3,1,2), (3,2,1) are bases in our world.

As for the name sets, do you have a better suggestion? I chose sets because it is the only term that fits all the different structures that come from basis sets, independent sets, etc. but yeah it might be confusing haha

I will tinker around a bit more.

[Sequenzer]

So I for my part am done with it. I asked Dan to look at the mathematical aspects of it and he believes the code is correct.

So this should be ready to merge :)