Skip to content

Fix PQuotient error for large groups. #5816

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Draft
wants to merge 5 commits into
base: master
Choose a base branch
from
Draft

Fix PQuotient error for large groups. #5816

wants to merge 5 commits into from

Conversation

FriedrichRober
Copy link
Contributor

Closes #5809

Text for release notes

Fix PQuotient error for large groups: If logord is too small, we return fail or error depending on option noninteractive.

@FriedrichRober
Fix PQuotient error for large groups.
2087635 
- Return fail in AbelianPQuotient if not enough generators for current
parameters (logord in PQuotient, or #gens in collector of QuotientSystem
qs)
- Return fail or error in PQuotient for large groups, depending on option
noninteractive
- Update documentation of PQuotient
- Add test for bugfix
fingolfin
fingolfin reviewed Oct 15, 2024
View reviewed changes
tst/testbugfix/2024-10-15-PQuotient.tst Outdated

#
gap> PQuotient( FreeGroup(2), 5, 10, 520 : noninteractive ) <> fail;
true
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

actually gives false (hence CI fails)

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, this is something I discuss right now with Hulpke in the original issue thread. The function does not behave like I would expect from the documentation. I already added this test case here, because in my opinion the function should behave like this. So in this case, the quotient can be generated by 520 elements, but the algorithm first needs to create a covering group that exceed this limit. Thus it currently throws fail. But actually I would expect it to not throw fail here.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I have put these lines out for now. I will open a new issue for this, since it is not clear if there is an easy fix for this.

#
gap> PQuotient( FreeGroup(2), 5, 10, 520 : noninteractive ) <> fail;
true
gap> PQuotient( FreeGroup(2), 5, 10, 519 : noninteractive ) = fail;
true

fingolfin
fingolfin reviewed Oct 15, 2024
View reviewed changes
lib/pquot.gd Outdated
## implementation produces an error message if the order of a
## <M>p</M>-quotient exceeds <M>p^{256}</M> or <M>p^{<A>logord</A>}</M>,
## respectively.
## given. If the order of a <M>p</M>-quotient exceeds <M>p^{256}</M>
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is 256 an additional limit, or just the default value for logord ?

Copy link
Contributor Author

@FriedrichRober FriedrichRober Oct 15, 2024 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

it is the default value, not an additional limit (at least what I can tell from the code and how it behaves on input groups whose quotients exceed 256 generators). Probably we should rephrase it. For now, I tried to stay as close to the original documentation as possible

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I changed the documentation now

fingolfin
fingolfin reviewed Oct 15, 2024
View reviewed changes
@FriedrichRober @fingolfin
Apply suggestions from code review
ee883b6 
Co-authored-by: Max Horn <max@quendi.de>
@fingolfin
Copy link
Member

@FriedrichRober last call for GAP 4.14 ...

@FriedrichRober
Copy link
Contributor Author

Hi, I will try to clean up in time, but can only start working on this on Monday.

@FriedrichRober
Copy link
Contributor Author

@fingolfin @hulpke, I adjusted the documentation of the method. Since I am not an expert of this implementation, I would really appreciate if someone can proof-read this.

As far as I understand, the current implementation throws an error/fail if the order of any p-group during the computation exceeds p^logord. This also includes the covers (which I guess they call intermediate p-groups in the original doc). This means that a p-quotient in the series might not be found, even if its order does not exceed p^logord, since the order of the cover of the p-quotient may exceed p^logord. However, for me and my package LINS, I am only interested in the class c=1 central p-quotient, and this seems to be a special case handled by the method AbelianPQuotient. Here it seems that the class 1 p-quotient is always found, if its order does not exceed p^logord. The next p-quotients are then handled by DefineNewGenerators, which I guess need to construct these covers and thus may return fail even if the order does not exceed p^logord.

fingolfin
fingolfin reviewed Mar 28, 2025
View reviewed changes
lib/pquot.gi
AbelianPQuotient( qs );
isAbelianPQuotientSucessful := AbelianPQuotient( qs );
if not isAbelianPQuotientSucessful then
if noninteractive then
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You need to initialize noninteractive before using it.

To use GAP options, use the ValueOption helper. E.g.

Suggested change
if noninteractive then
if ValueOption("noninteractive") = true then

lib/pquot.gd
Comment on lines +67 to +68
## <A>noninteractive</A>: if it is present, the current implementation
## produces an error message; otherwise it returns <C>fail</C>.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Isn't this the reverse of what the code does? If noninteractive is set (to true), then it returns fail; if it is not set or if it is set to false, then raise an error?

lib/pquot.gd
Comment on lines +71 to +72
## in the series. Thus a <M>p</M>-quotient is not necessarily computed
## even if its order does not exceed <M>p^{<A>logord</A>}</M>.
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't understand this sentence, or rather, I don't understand how the previous text implies ("thus") this sentence. Could you elaborate?

@fingolfin
Copy link
Member

Dear @FriedrichRober this got lost in the shuffle, partially because it is marked as a draft. Besides waiting for review feedback (I just gave some) are there other reasons it is marked as draft?

If you are "only" interested in the maximal abelian $p$-quotient for a given $p$, then independently of this PR perhaps we could/should also add a method for that; or you could write your own, which does not use PQuotient. Instead, it could call MaximalAbelianQuotient, then compute a maximal $p'$-subgroup in there, lift it back, and voila you have the kernel of the maximal abelian $p$-quotient.

@fingolfin fingolfin mentioned this pull request Mar 28, 2025
Draft
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@fingolfin fingolfin fingolfin left review comments

@hulpke hulpke Awaiting requested review from hulpke

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

PQuotient throwing error for large groups
2 participants
@FriedrichRober @fingolfin