Represent extensions on cosets of a module hyperplane

[fingolfin]

The problem

Extensions(G,M) for a non-solvable G spends nearly all its time in
FpGroupCocycle, finding a permutation representation of the extension --
not in TwoCohomologyGeneric. Reported by Thomas Breuer for L3(3) with
its 7-dimensional GF(3) module, where the cohomolo package is an order
of magnitude faster overall:

G:= AtlasGroup( "L3(3)" );;
info:= AllAtlasGeneratingSetInfos( "L3(3)", Ring, GF(3), Dimension, 7 );;
M:= GModuleByMats( AtlasGenerators( info[1] ).generators, GF(3) );;
ext:= Extensions( G, M );;   # 6308 seconds

Breakdown on my machine: TwoCohomologyGeneric 0.4 s, then 373 s for
each of the eight non-split cocycles.

The search lifts the quotient E -> G step by step, testing subgroups of
descending index and using LargerQuotientBySubgroupAbelianization. For a
candidate of index i the preimage's presentation is rewritten on roughly
i * ngens generators. L3(3) has nothing usable below index 52; the
attempt at index 144 with 16 generators produces a presentation on some
2000 generators, and everything downstream chokes on it.

The change

If a subspace U of the module contains no nonzero submodule, then its
core in the extension is trivial -- a normal subgroup contained in U
lies in the module and hence is a submodule. So the extension acts
faithfully on the cosets of U, and one coset enumeration produces that
action. For an irreducible module U is a hyperplane, of index
prime * |G|.

Two new helpers, ModuleCoreOfSubspace and SubmoduleFreeSubspace, find
such a subspace; FpGroupCocycle uses it before falling back to the
existing search.

Guards, each of which measurement showed to be necessary:

• Only at codimension 1. Every further codimension multiplies the
  degree by prime, and the degree reduction afterwards then costs more
  than the old search. On the reducible 10-dimensional GF(5) module from
  tst/testbugfix/2025-11-06-PermrepExtension.tst: old 1 s, new 170 s.
• Only up to degree 10^5 (EXTENSION_COSET_ENUMERATION_MAXDEG).
• Not for 1-dimensional modules, where the only such subspace is
  trivial and the enumeration degenerates to the regular representation.
• :cheap skips the full SmallerDegreePermutationRepresentation
  afterwards. Without the option that reduction is worth its price here,
  because the degree coming out of the module is far off the optimum.

Numbers

Extensions for the example above, and the tests that cover this code:

	master	this PR
Extensions(L3(3), M)	~3400 s	~120 s
resulting degrees	156 ... 1296	117 ... 702
NrConjugacyClasses of all nine	1.7 s	0.9 s
tst/teststandard/twocohom.tst	5142 ms	4720 ms
tst/testbugfix/2025-11-06-PermrepExtension.tst	2108 ms	2102 ms
tst/testextra/grpperm.tst	211 s	240 s (noise)

For reference, the cohomolo route on the same machine costs about 200 s
for the nine extensions, so this also removes the gap that prompted the
report.

Test

tst/teststandard/twocohom.tst gains the reported example, built without
AtlasRep from the tensor square of the natural module of SL(3,3). It
constructs one of the nine extensions rather than all nine, which keeps it
at about 15 seconds -- against some 370 seconds on master.

Verification

• All nine groups have order 12282192, PCore(.,3) elementary abelian of
  order 3^7, quotient of order 5616, and exactly one of them splits.
• The multiset of class numbers matches what cohomolo produces
  (3 x 57, 6 x 49).
• twocohom.tst, 2025-11-06-PermrepExtension.tst,
  2026-08-02-TwoCohomologyGeneric.tst and testextra/grpperm.tst pass.
• Small cases (C2, S3, A5 with trivial, regular and reducible
  modules) produce degrees identical to master.

Not addressed here

• The presentation TwoCohomologyGeneric derives from the confluent
  rewriting system has 9 generators for L3(3) where 2 suffice.
  cohomolo's extension presentation has 9 generators against our 16, and
  that alone is worth a factor of about 7 when the generic
  IsomorphismPermGroup is used on either.
• What remains of the runtime is SmallerDegreePermutationRepresentation,
  roughly 8 s per extension; cohomolo pays the same.
• TwoCohomologyGeneric(TrivialGroup(IsPermGroup), <module of dim >= 2>)
  errors with MaximumList: <list> must contain at least one element.
  Pre-existing, unrelated, not touched here.

---

This pull request was prepared with AI assistance (Claude Opus 5); see the
Co-authored-by trailer on the commit.

[codecov]

Codecov Report

❌ Patch coverage is 98.41270% with 1 line in your changes missing coverage. Please review.
✅ Project coverage is 78.97%. Comparing base (66fd147) to head (fece423).
⚠️ Report is 9 commits behind head on master.

Files with missing lines	Patch %	Lines
lib/twocohom.gi	98.41%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #6545      +/-   ##
==========================================
- Coverage   78.97%   78.97%   -0.01%     
==========================================
  Files         684      683       -1     
  Lines      294201   294160      -41     
  Branches     8670     8651      -19     
==========================================
- Hits       232359   232323      -36     
- Misses      60030    60033       +3     
+ Partials     1812     1804       -8     

☔ View full report in Codecov by Harness.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

• ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
• 📦 JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

[hulpke]

The fundamental problem lies differently, namely in the MaximalAbelianQuotient method. This should use abelian rewriting, but the corresponding method (commented out, line 1143 in ghomfp.gi) had problems and thus was not ready for prime time.

This approach here is producing an initially horribly large permutation degree, larger than |G|. Is that what we want?