PQuotient throwing error for large groups
FriedrichRober opened this issue · 11 comments
The issue was encountered in conjuction with the package LINS in gap-packages/LINS#67.
The way I would like pQuotient to behave is the following. If I want to search for a p-class c up to order p^logord, and if there is none to be found, I would like the function to return fail. Currently it throws an error instead, which is bad as this function is called as a subroutine in LINS.
Example:
gap> F := FreeGroup(["a", "b"]);;
gap> a := F.1;;
gap> b := F.1;;
gap> p := 5;;
gap> G := F / [a^p, b^p, Comm(a,b)];
<fp group on the generators [ a, b ]>
gap> PQuotient(G, p, 1, 2);
<5-quotient system of 5-class 1 with 2 generators>
gap> PQuotient(G, p, 1, 1); # throws error, since we need two generators
Error, List Elements: <list>[2] must have an assigned value in
qs!.images{generators} := gens{[ 1 .. d ]}; at /Users/friedrich/.gap/gapdev/lib/pquot.gi:1345 called from
AbelianPQuotient( qs ); at /Users/friedrich/.gap/gapdev/lib/pquot.gi:1456 called from
<function "PQuotient">( <arguments> )
called from read-eval loop at *stdin*:19
type 'quit;' to quit to outer loop
brk>
Since I am not sure, why it was designed to throw an error instead of fail, I wanted to ask if there are good reasons for this behaviour. If not, I volunteer to change the behaviour, I think it should be fairly easy by just checking if we try to insert too many generators into the list. But I might be wrong.
@FriedrichRober the error doesn't look like something deliberate, it's just an out-of-bounds access likely caused by the logord argument to PQuotient being too small.
As such I don't think it would be problematic if you inserted code into PQuotient that handled this more gracefully, e.g. by returning fail, and perhaps issuing an Info message (only visible if logging level is suitable) that explains why it failed.
Perhaps @hulpke or @ThomasBreuer have additional insights.
I think the issue is that the rank of G/G' is already 2, and thus 1 generator is infeasible. The routine should return a fail value.
If @FriedrichRober wants to make a PR changing this code path to return fail, that'd be fine. Ideally please also (a) modify the docstring for PQuotient to explain this behavior, and (b) include a test case :-)
Sure I will do it and let you know when I am finished
So I fixed the above error, I will do a draft pull request soon.
But maybe I encountered another error that is more irritating because it seems to contradict the manual:
gap> qs := PQuotient( FreeGroup(2), 5, 10, 1024 : noninteractive );
<5-quotient system of 5-class 10 with 520 generators>
gap> Order(Image(EpimorphismQuotientSystem(qs))) = 5^520;
true
gap> PQuotient( FreeGroup(2), 5, 10, 600 : noninteractive );
fail
gap> PQuotient( FreeGroup(2), 5, 10, 600);
Error, Collector not large enough to define generators for the next class.
To return the current quotient (of class 9) type `return;' and `quit;' otherwise.
at /Users/friedrich/.gap/gapdev/lib/pquot.gi:1477 called from
<function "PQuotient">( <arguments> )
called from read-eval loop at *stdin*:6
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
From the documentation:
‣ PQuotient( F, p[, c][, logord][, ctype] ) ─────────────────────── function
[...]
By default the algorithm computes only with factor groups of order at most
p^256. If the parameter logord is present, it will compute with factor
groups of order at most p^logord. If this parameter is specified, then the
parameter c must also be given. The present implementation produces an error
message if the order of a p-quotient exceeds p^256 or p^logord,
respectively. Note that the order of intermediate p-groups may be larger
than the final order of a p-quotient.
But now it doesn't look to me like the algorithm is actually doing what is written in the manual. Because the p-Quotient in the above example has 520 generators, but when I set the argument logord := 600, it returns fail. I guess, because the algorithm has to put a larger p-quotient underneath first? Maybe I understand something incorrectly. I hope somebody can help to clarify.
it returns fail. I guess, because the algorithm has to put a larger p-quotient underneath first?
Indeed. The PQ takes the group of the prior layer and constructs it covering group. It then evaluates the relators in the cover to get the next quotient. In other words, the number of generators available must be able to handle the coverign group, not just the next quotient. (Would it be better if the collector was not so stubborn on the number of generators? Yes, but that's not how the code was written.)
EpimorphismQuotientSystem gets around this issue by catching the error case and calling again with an increasing number of generators.
Okay, so I understood this part correctly. Indeed, I think it should be more lenient with the number of generators for the covering group. Are there any known bounds on how many generators are needed at most, if we say that the resulting quotient should have at most logord many generators. I somehow interpreted this sentence
Note that the order of intermediate p-groups may be larger
than the final order of a p-quotient.
that the code would allow covering groups to have more generators than logord.
Maybe a stupid question: Is it true, that the number of generators increases strictly in each layer? This would give at least a weak criterion to return fail and to stop descending the exponent-p central series.
because as far I understand, the number of generators n is always chosen such that the resulting quotient has order p^n
because as far I understand, the number of generators n is always chosen such that the resulting quotient has order p^n
Yes.
Okay, so I understood this part correctly. Indeed, I think it should be more lenient with the number of generators for the covering group. Are there any known bounds on how many generators are needed at most, if we say that the resulting quotient should have at most
logordmany generators.
Yes, it would be nice if it was more lenient, but I think there is a performance price to pay with a larger generator number. PArt of the problem is that the number of generators is initialized at the very start, not for each step. At that point, any upper bound for number of generators on lower levels will be huge (basically Nielsen-Schreier bound).