TGRandomGenus does not obey law

[algeboy]

I think there is a theoretical problem with TGRandomGroup. From my reading of the documentation it should obey the following law.

For all primepowers q, d, and g

Genus(TGRandomGroup(q,d,g)) le g;

This was not the true, but recently I added a repeat-until to just skip useless cases. But I'm finding it doesn't return very quickly now for specific (q,d,g), e.g. (16,64,6), (9,39,1) etc.. I believe what is happening is that the method to make these groups is theoretically misunderstanding something.

[joshmaglione]

le instead of lt.

Why should it return quickly? Are you sure it is running through the loop many times?

I thought this constructor was documented reasonably. But if you want to improve speed you'll need to do more than wrap with a loop because it's computing centroids (over the base field) which is significantly slower than doing it over the field you start with.

[algeboy]

I don't think it is making things of any known genus, it is guessing. Note before I put in the loop to guard the return it was truly returning incorrectly, i.e. groups whose genus was higher than g, as measured by our own command Genus. The point is, I don't think what we are doing here is actually building groups of a given genus bound. It is creating random groups, then filtering if they are of the right genus. I think there should be a way to build something of a specified genus bound directly, not by hoping.

[algeboy]

Just to clarify the bug is temporarily turned off because of my loop guard, but that isn't the right fix.

[algeboy]

Yes, I mistyped the original post, it is failing (without my guard) with le, not just lt.

[joshmaglione]

I have no idea how it is possible that the genus is higher than the given g. Do you have an example?

[algeboy]

Yeah, this is an unintended consequence linked back to decomposable. Roughly speaking

TGAutomorphism(G) should work whenever Genus(G) le 2.

But in the decomposable case Genus(G) outputed 2 but crashes the TensorOverCentroid command. The fix that seemed most natural was to assume Genus(G) means genus over fields, and so in the decomposable case one can not have genus say 4 given a genus 2 over GF(p)[x]/(x^2). It could be fixed to report 2 in this case but it wasn't clear that it worked properly in that case. But if you know it does then we just adjust that command.

The main point is one probably has an expectation from the existing documentation that the following tests always work, and they dont:

TGAutomorphismGroup( TGRandomGroup(d,q,2) ) TGSignature ( TGRandomGroup(d,q,2) ) and if Genus(G) eq 2 then TGAutomorphismGroup(G)

So while might perhaps argue that the set of inputs to TGAuto, TGSign, etc. is a subset of the outputs of TGRand, and therefore this shouldn't be required, I think at least the default behavior is that this should be the usage. That means commands like TGRand and Genus should be outputing results that match what we use. Or something, but spending time testing on random inputs that somehow don't count is getting us now where. We can turn TGRand back to full power later as we add features, or leave that option in as a optional..

[joshmaglione]

I disagree. TGRandomGroup should either be how it was or removed from the package. It's literally just the universal coefficients theorem. This was meant to capture the "pair of forms" construction, and I just included the general case.

I think the only fix that's required is to communicate this in the documentation. If you think this is ultimately too confusing for a user, then we should just remove it.

One problem that is not described in the documentation is the notion of decomposable. I think I only made errors for it in code and did not write about it in the documentation. My apologies. You can see hints of it though. Look for example at Genus. It is not the definition in the paper, but one that is correct assuming that the input is decomposable. There are no hints in the auto/ iso functions.

[joshmaglione]

After thinking about it, maybe the documentation should be re-done for TGRandomGroup. It should read something like TGRandomGroup(q, d, e: Exponentp := true) Assuming q = p^k, returns a random class two k*d-generated p-group.

Maybe we add (in the intrinsic) how the group is built? We can certainly do this in the documentation. What do you think?

[algeboy]

Documentation can solve some problems, but what's happening is uncaught exceptions for illegal inputs is seeming too strong a fail type. Perhaps what is needed is 2 functions.

TGRandomGroup(...)
TGRandomIndecomposableGroup(...)

I like the idea that we can articulate a few key laws for this package such as

P := TGRandomIndecomposable(q,d,2);
Order(TGAutomorphismGroup(P)) ge Order(IsometryGroup(pCentralTensor(P))*q^(d*2);

Or whatever. This gives us a very clear test case and supplies the user with some expectations of what it does. Without it the test that fail seem frustrating because you expected it work.

also perhaps rename, for now

TGAutomorphismIndecomposableGroup(G)

Not sure about the length of these but self-documenting functions avoid confusion

[joshmaglione]

See my response for my thoughts on your automorphism remark.

We have two threads that have identified two symptoms of a single problem. We do not have a way to deal with decomposable groups/ tensors.

I do not like incorporating indecomposbale into the name because this just misses the entire point of this constructor. See my response above.

Why is this constructor being singled out? All other constructors can produce decomposable groups as well. In fact, it's even easier with the other constructors. I cannot actually run it at the moment but here's are samples that make my point.

/* Generalizes to f(x)*g(y) for irreducible f and g */
P<x, y> := PolynomialRing(GF(3), 2);
G := Genus2Group(x^2 - y^2);

With the genus 1 constructor, this won't happen in a nontrivial way (of course radicals decompose).

With the other genus 2 constructor:

G := RandomGenus2Group(3, [2, 2]);

I don't think we should build workarounds to an issue that is more fundamental, and ones that we'd ultimately remove. I'd rather comment out all constructors, but I don't want that either because they're valuable. If TameGenus isn't meeting some standard of completion, then I'm fine with it being considered incomplete until we can handle all tame genus groups/ tensors.

It goes without saying, @galois60, that your feedback is very much welcomed. I know you're in the middle of traveling and recovering.

[joshmaglione]

See Issue #17.