NormStar and isometries

[joshmaglione]

It seems that NormStar does not compute the full normalizer. In this example it does not always contain the isometry group. Here is a demonstrating example.

t := Tensor(GF(3), \[ 8, 8, 4 ], [ GF(3) | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 2, 2, 0, 0, 0, 2, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 2, 2, 0, 2,
0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
1, 1, 0, 1, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
TensorCategory(\[ 1, 1, 1 ], { PowerSet(IntegerRing()) |
{ IntegerRing() | 0 },
{ IntegerRing() | 1, 2 }
}));
S := SystemOfForms(t);
I := IsometryGroup(S);
[I subset NormStar(S) : i in [1..10]];

My output: [ false, true, false, false, true, true, true, true, true, true ]

Here is another very similar example:

t := Tensor(GF(3), \[ 8, 8, 4 ], [ GF(3) | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 0, 0, 2, 2, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 2, 0, 2, 2, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 1,
0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0,
0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
1, 1, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
TensorCategory(\[ 1, 1, 1 ], { PowerSet(IntegerRing()) |
{ IntegerRing() | 0 },
{ IntegerRing() | 1, 2 }
}));

Another perspective of the same issue is seen looking at orders. Using the second example, NormStar is prescribed an order different from its computed order (tested with LMG package).

> S := SystemOfForms(t);
> NA := NormStar(S);
> NA`Order;
8294400
> LMGOrder(NA);
Matrix group error: computed group order differs from stored order
Stored: 2^12 * 3^4 * 5^2
New: 2^8 * 3^9 * 5^2

Magma: Internal error

EDIT: I noticed after I have discrepancies with NormStar my seed is set to 0. I suspect that this is because of TransformForm. If I remember correctly, TransformForm sets the seed to 0 to go through its algorithm. I think it meant to set the seed back, but it is commented out.

[galois60]

Ok, so first I need to replace this function with something robust. Normalizer of a general matrix algebra is more useful to us now, as is normalizer of matrix Lie algebra. I think this NormStar function should be decommissioned as it seems to create more problems than it solves! (Why were you trying to use it, Josh, by the way? What I mean is: do you really need it for some urgent purpose?)

Now to address the problems you raised. I believe the issue is with "subset" rather than with any of our code. Strange because I would have thought that "subset" would by default carry out a robust membership test. I don't think it does. My guess is that inside LMG machinery "subset" defaults to RandomSchreier, which is a randomized algorithm to set up a Schreier tree data structure with which to test order and membership. It can (and frequently does) go wrong, producing a proper subgroup of the input group. To support my theory I offer the following test with the example above:

for i in [1..20] do N := NormStar (S); Verify (N); I subset N; end for;

If you see a "false" in your 20 runs, let me know! The Verify command does what you think––it makes sure the data structures used for order and membership are correct, and fixes them if they are not.

Now, the second issue is different. That's a bit of NormStar nonsense that needs to be fixed if we wish to continue using it. I was, at some stage, cleverly trying to store the order of the normalizer as I went along. I know that this is incorrect in places and it cause all kinds of untold grief when you ask Magma to recompute order.

[joshmaglione]

Thanks, Pete. That's troubling that "subset" does not work as expected. Speaking of, it looks like there are two functions that probably should have used instead: LMGIsIn and LMGIsSubgroup.

I have no preference whether you fix the current NormStar, build a NormStar 2.0, or leave it to rot. While a DerNormalizer would be a great tool to have, I have no idea how to create a general (efficient) algorithm for this, so NormStar might have good uses when the derivation algebra isn't nice enough for Magma. Of course, both of these yield no new information for large random examples, but I am currently not looking at large or random p-groups.

I was using NormStar to construct autotopisms of invariant-free tensors that Mark and I are studying. It turns out, the adjoint algebra is a simple star algebra over some field extension, and running through its normalizer is actually faster than looking through GL(W).

Thanks for looking into this Pete.