describe for free groups and finitely presented groups

[micjoswig]

While implementing fundamental_group(K::SimplicialComplex) I am running into the following:

julia> describe(free_group(2))
ERROR: Error thrown by GAP: Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 4th choice method found for `StructureDescription' on 1 arguments at /cache/oscar-dev-depot/artifacts/1ae5d8f1898d9dcbe8dc3d93f56369c864a8e717/share/gap/lib/methsel2.g:249 called from
<function "HANDLE_METHOD_NOT_FOUND">( <arguments> )
 called from read-eval loop at *defin*:0

Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:33
 [2] ThrowObserver(depth::Int32)
   @ GAP /cache/oscar-dev-depot/packages/GAP/h4tDv/src/GAP.jl:51
 [3] _call_gap_func(func::GAP.GapObj, a1::GAP.GapObj)
   @ GAP /cache/oscar-dev-depot/packages/GAP/h4tDv/src/ccalls.jl:257
 [4] call_gap_func_nokw
   @ /cache/oscar-dev-depot/packages/GAP/h4tDv/src/ccalls.jl:224 [inlined]
 [5] (::GAP.GapObj)(a1::GAP.GapObj)
   @ GAP /cache/oscar-dev-depot/packages/GAP/h4tDv/src/ccalls.jl:234
 [6] describe(G::FPGroup)
   @ Oscar /cache/polymake/oscar-system/Oscar.jl/src/Groups/GAPGroups.jl:930
 [7] top-level scope
   @ REPL[38]:1

To me this looks like a bug. If not, please enlighten me.

At any rate, the result of that function may be a free group or a proper quotient. I tried a quotient of a free group by an empty list of relations, but that was not better either,

[fingolfin]

describe is a function that's basically written for finite groups. Of course we could also let it print something for e.g. free groups, but I am not sure there's much more to say than what the regular print/show methods already show, i.e.

julia> free_group(2)
<free group on the generators [ f1, f2 ]>

To form a quotient:

julia> F = free_group(2)
<free group on the generators [ f1, f2 ]>

julia> rels = [ F[1]^2, F[2]^2, comm(F[1], F[2]) ]
3-element Vector{FPGroupElem}:
 f1^2
 f2^2
 f1^-1*f2^-1*f1*f2

julia> G, epi = quo(F,rels)
(<fp group on the generators [ f1, f2 ]>, Group homomorphism from
<free group on the generators [ f1, f2 ]>
to
<fp group on the generators [ f1, f2 ]>)

[micjoswig]

Look at the following:

julia> F = free_group(2)
<free group on the generators [ f1, f2 ]>

julia> rels = [ F[1]^2, F[2]^2, comm(F[1], F[2]) ];

julia> G, _ = quo(F,rels)
(<fp group on the generators [ f1, f2 ]>, Group homomorphism from 
<free group on the generators [ f1, f2 ]>
to
<fp group on the generators [ f1, f2 ]>)

julia> describe(G)
"C2 x C2"

julia> describe(F)
ERROR: Error thrown by GAP: Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 4th choice method found for `StructureDescription' on 1 arguments at /cache/oscar-dev-depot/artifacts
/1ae5d8f1898d9dcbe8dc3d93f56369c864a8e717/share/gap/lib/methsel2.g:249 called from
<function "HANDLE_METHOD_NOT_FOUND">( <arguments> )
 called from read-eval loop at *defin*:0

Stacktrace:
 [1] error(s::String)
   @ Base ./error.jl:33
 [2] ThrowObserver(depth::Int32)
   @ GAP /cache/oscar-dev-depot/packages/GAP/zvGEa/src/GAP.jl:51
 [3] _call_gap_func(func::GAP.GapObj, a1::GAP.GapObj)
   @ GAP /cache/oscar-dev-depot/packages/GAP/zvGEa/src/ccalls.jl:257
 [4] call_gap_func_nokw
   @ /cache/oscar-dev-depot/packages/GAP/zvGEa/src/ccalls.jl:224 [inlined]
 [5] (::GAP.GapObj)(a1::GAP.GapObj)
   @ GAP /cache/oscar-dev-depot/packages/GAP/zvGEa/src/ccalls.jl:234
 [6] describe(G::FPGroup)
   @ Oscar /cache/polymake/oscar-system/Oscar.jl/src/Groups/GAPGroups.jl:930
 [7] top-level scope
   @ REPL[8]:1

Now both groups may occur as output of fundamental_group(). As

Oscar.jl/src/Combinatorics/SimplicialComplexes.jl

Lines 358 to 364 in 7e7cde6

	# Example
	```jldoctest
	julia> x = fundamental_group(torus());
	julia> describe(x[1])
	"Z x Z"
	```

(written by @alexej-jordan ) suggests, describe() should be callable on any output of that function.

Also the help text does not say that this only works for finite groups (and it does work for the fundamental group of the torus).

Even if this was never intended, wouldn't it be nice if the user would get a bit more input than from a mere show()? Actually, in the recent version of polymake we introduced a describe() function for polytopes; and this was inspired by GAP's describe(). We could make this OSCAR-wide.

What do you think?

[micjoswig]

PS: If a function is callable or not should only depend on the argument type(s). In case you want to stick to your plan, what should be that (uniform) return type for fundamental_group()?

[fingolfin]

I agree that describe should ideally work on all groups, and if it doesn't, then at least this should be documented. Above I was merely describing the current state of things, not a "plan". (For some background, describe was originally only added as a quick&dirty hack for a software demo, no deep planning went into it.)

Question is what to output in which case. Here are some ideas:

1. for free groups, one could print "free group of rank NN"
2. ... or one could print "free group with generators [ ... ]
3. for non-free fp groups, one could print "finitely presented group on NNN generators"
4. ... or "finitely presented group with generator [ .... ] and relators [ ... ]"
5. should we try to handle fp groups which are known to be finite differently (i.e. as before?!?)
6. for pc groups, one could call PrintPcPresentation
7. in all cases, one could of course also print known properties of the groups, e.g. is it (non)abelian, (non)solvable, (in)finite (and if known, the order), ... but of course there is a potentially very long list...

But also note that the output of describe in general is not stable, it depends on random choices (it is cached for a given input, so if you call it twice on the same group, it'll give the same result; but if you call it on an isomorphic copy, it may give different output). Changing this is difficult and of unclear usefulness, as many groups admit different descriptions which are subjectively all equally "nice".

[fingolfin]

You suggested to write something like Z x Z. But that's a very rare cases: sure, if the fp group happens to be free or finite, I can write such a thing. And if it is free, we could agree to write e.g. F_2; I could probably even handle some more "obvious cases", e.g. F_2 x F_2 if the generators are aligned nicely.

But for a general fp group, as you well know, it is not even decidable if it is non-trivial. So what should we do then? Try anyway and run into an infinite loop? Or fall back to some less descriptive thing?

[micjoswig]

I did not suggest anything. This is what came out in this case. I am aware of all (or at least most) of the complications, you are listing. Still it is worth to give it a try.

I am not picky about what exactly should be the output. My reasoning: the show() command should only produce a description which is directly accessible (no expensive computations), while for describe() we could be a bit more generous (like saying: "tell me whatever you can find out within 10 secs").

All of the above makes sense to me, and we could do this in a gradual fashion. So maybe we do not want to doctest describe() then.

[thofma]

If I remember correctly we don't have a safe way to do "kill some function after 10 minutes", which basically means describe cannot try to do any (useful) computation without running into an infinite loop for finitely presented groups. If it is known to be finite, I would run the ordinary describe on it and otherwise probably 1) + 4) + 7).

P.S.: FWIW Magmas GroupName errors for groups which are not known to be finite, but does the usual thing if it knows that group is finite:

> Fx<x, y, z> := FreeGroup(3);
> Q := quo< Fx | x, y, z>;
> GroupName(Q);
C1
> Q := quo< Fx | x>;
> GroupName(Q);

>> GroupName(Q);
            ^
Runtime error: G must be a finite group

[fingolfin]

Actually GAP can limit computations in fp groups in various ways, so this is not completely out of reach. But for now, I'd start with printing only things that are known.

BTW, describe can also take arbitrary long for finite group. It isn't super clever right now (we need fully working group recognition to fix that, which is also something Alice Niemeyer and me and our students are working towards, but don't expect quick progress there...)

Of course there is quite a disparity between a string like "C2 x Z x F_2" versus "a solvable infinite finitely presented group". But that can't be helped in general. Though perhaps one want to have different functions for these different kinds of descriptions...?

[micjoswig]

I'm not so picky here. If there is a choice, I'd go for the version that I can have quicker. If speed does not matter, I'd prefer a terse output string.