Problems with PrimitiveIdenfification

[olexandr-konovalov]

This comes from testing #818.

Observed behaviour

I reproduced this twice on my machine with GAP 4.8.4: PrimitiveIdentification produces the error saying

Error, Uh-Oh, this should never happen

when I am taking a group given by the generators of PrimitiveGroup(2197,122) and then trying to identify it. After quitting from the break loop, next time it runs fine:

gap> PrimitiveIdentification(Group(GeneratorsOfGroup(PrimitiveGroup(2197,122))));
Error, Uh-Oh, this should never happen [  ] called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 1 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> quit;
gap> PrimitiveIdentification(Group(GeneratorsOfGroup(PrimitiveGroup(2197,122))));
122

With master branch on another machine, I can see the same behaviour, except that one time I had segfault.

Expected behaviour

The documentation has no claims on limitations of PrimitiveIdentification to work only up to certain degree - if there are some, they should be made. The test of PrimitiveIdentification similar to the one above actually worked well for groups of degree up to 1728. For degree 1728, it runs out of 16g workspace (of course, a more complicates test should conjugate generators within the S_n before calling PrimitiveIdentification, but to start with I was willing to run the simple form).

I am now running PrimitiveIdentification for degree 2500 in #818, and after several hours it still checks group 15 out of 34.

[hulpke]

I cannot reproduce this, neither in stable-4.8, nor in master. (in a freshly started GAP)
Can you try without packages or give a bit more information on how to reproduce it?

[colva]

We should probably put an advertised upper limit on PrimitiveIdentification, either at 1000 or 2500. I can't remember whether I actually wrote any code to make it work for degrees [1001..2500], or whether it's just a fluke that you can make it run. It would be quite a lot of work to make it efficient for higher degrees.

[markuspf]

There are of course two issues at play: Making it not crash (and return a correct result), and making it efficient.

If the procedure in principle would work above whatever bound, but be awfully slow, a warning could be displayed, but one could still try running it.

[olexandr-konovalov]

@hulpke: on Intel Core i7 Mac under OS X Yosemite 10.5.5, opened new terminal window, started GAP:

$ gap -r -A
 ┌───────┐   GAP 4.8.4, 04-Jun-2016, build of 2016-06-05 16:52:58 (BST)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin14.5.0-gcc-5-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
 Packages:   GAPDoc 1.5.1
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap>  PrimitiveIdentification(Group(GeneratorsOfGroup(PrimitiveGroup(2197,122))));
Error, Uh-Oh, this should never happen [  ] called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 1 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

Now interesting things happen. Opened new Tab in the terminal, started GAP - works fine. Repeated 8 more times - works fine. Opened new terminal window instead of a tab - the "uh-oh" message again. Opened another terminal window and started GAP 4.7.9 - also got the "uh-oh" message.

Could it be triggered by garbage collections ?

[olexandr-konovalov]

I've started GAP with gap -r -A -m 70m -o 1g and was able to reproduce this 5 times in a row in the same terminal window:

$ gap -r -A -m 70m -o 1g
 ┌───────┐   GAP 4.8.4, 04-Jun-2016, build of 2016-06-05 16:52:58 (BST)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin14.5.0-gcc-5-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
 Packages:   GAPDoc 1.5.1
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap>  PrimitiveIdentification(Group(GeneratorsOfGroup(PrimitiveGroup(2197,122))));
Error, Uh-Oh, this should never happen [  ] called from
<function "unknown">( <arguments> )
 called from read-eval loop at line 1 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
brk> 

[colva]

My memory is that the code is a long collection of special cases, rather than a particularly general method - it just looks for distinguishing features of each group, trying methods to distinguish them that start at order and gradually get more expensive, until its down to one group. So to make it work for higher degrees would almost surely involve writing more code.

On 21 Jun 2016, at 10:03, Markus Pfeiffer [email protected] wrote:

There are of course two issues at play: Making it not crash (and return a correct result), and making it efficient.

If the procedure in principle would work above whatever bound, but be awfully slow, a warning could be displayed, but one could still try running it.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub, or mute the thread.

[hulpke]

OK, I can reproduce it in 4.8.4 (but not in stable-4.8)

While I agree with @colva on the performance aspect, that is not what is happening here.

The code is first eliminating groups by invariance properties (which are computed on the fly), and the error message indicates that no candidate group is left. So what must have happened is a genuine calculation error.

The problematic test uses cycle structures and orders for conjugacy classes, and does not get an agreement between the tested group and any of the candidates (numbers 121/122/123).

[hulpke]

I think I have a culprit:

When the error occurs, there are elements whose cycle structures are given as lists (such as the one pasted in below) in which the length is longer than the last bound entry. The result is that shapes are not seen as equal.

Such shapes (which are produced by the kernel function CYCLE_STRUCT_PERM) should not arise. I am unsure whether this is a mistake in how CYCLE_STRUCT_PERM produces lists, or in other list code.

[ ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,, 1,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,, ]

[olexandr-konovalov]

@hulpke thanks! First, there was not much happening in stable-4.8 branch after GAP 4.8.4 release (only two merges) and I was able to reproduce this in master branch, so i don't think this was fixed by some other change. Second, your later comment seems to discover the reason. There was a problem in the list code fixed in #766 by @frankluebeck, so though what we observe now is very similar, it should be somewhere else.

[olexandr-konovalov]

FWIW, I'm also running this version of PrimitiveIdentification test (i.e. groups given by the same generators, without conjugation), and by this morning it successfully tested all groups of degrees in [2500..2743](it took 43 hours) and then reached the pre-set memory limit (was started with -o 8g).

[ChristopherRussell]

FWIW, I'm also running this version of PrimitiveIdentification test (i.e. groups given by the same generators, without conjugation), and by this morning it successfully tested all groups of degrees in 2500..2743 and then reached the pre-set memory limit (was started with -o 8g).

@alex-konovalov degree 3600 may be a good place to test. This degree contains the first (and only) occurrences of O'Nan-Scott types 4a and 4b in the database. I haven't tried to understand the code behind PrimitiveIdentification but these are my thoughts since @colva said that it works with lots of cases and because it was written for a database where types 4a and 4b didn't occur.

[frankluebeck]

@hulpke said:

Such shapes (which are produced by the kernel function CYCLE_STRUCT_PERM) should not arise. I am unsure whether this is a mistake in how CYCLE_STRUCT_PERM produces lists, or in other list code.

I have checked the code of CYCLE_STRUCT_PERM but cannot find an error. Are you sure that in the example mentioned above that list was created by CYCLE_STRUCT_PERM? Could you produce an example where CYCLE_STRUCT_PERM returns an invalid list object? Or can you provide any code that produces such an object?

[hulpke]

It is possible that the cycle structure list got corrupted somehow. What is rather strange is that if I add debugging code (e.g. in prim/primitiv.gi after line 330

if Length(s)=0 then Error("bug!"); fi;

) the error vanishes.

In any case, when the error arises, look at the variable a (a long list) and it contains such corrupt cycle structures. (In my example
a[17][1][1];

is corrupt in this way.) It is possible that this did not happen upon generation, but later. but the primitive groups code just created this list with CycleStructurePerm, for which the kernel function is the first method.

[olexandr-konovalov]

@ChristopherRussell I have tried degree 3600, and the test passed:

gap> checkprimid := function(n)
> local i,g,h;
> for i in [1..NrPrimitiveGroups(n)] do
>   Print(i,"/",NrPrimitiveGroups(n),"\r");
>   g:=PrimitiveGroup(n,i);
>   h:=Group(GeneratorsOfGroup(g));
>   if PrimitiveIdentification(h) <> i then
>     Error("Failure at PrimitiveGroup(",n,",",i,"\n");
>   fi;
> od;
> Print("\n");
> end;;
gap> checkprimid(10);
9/9
gap> checkprimid(3600);
39/39
gap> time;
3161117

Maybe one should construct the test example more carefully to probe failures.

[olexandr-konovalov]

@hulpke I think this may be triggered by garbage collection. When I've started GAP with gap -r -A -m 70m -o 1g, I was able to reproduce this 5 times in a row in the same terminal window, while it was not so often with default settings. Hope maybe @ChrisJefferson will be able to look at this some time...

[ChrisJefferson]

Just having a look over the code.

There is a bug in FuncCycleStructurePerm I think.

on line permutat.c, offset2 (and scratch2) becomes invalid after line 2984 (and similarly 3054)

[ChrisJefferson]

Try the fix-cycleperm branch on my GAP branch (I tried on one test and it seemed to fix it, but it could just be luck, I'll be on flakey internet for a few days).

EDIT: Put it in pull request #849 , but someone should check it, as I only quickly skimmed the code.

[hulpke]

@ChrisJefferson Many thanks. This sounds exactly like the kind of error I was suspecting!

[olexandr-konovalov]

TODO: check whether this is fixed by #849 and may be closed.

[olexandr-konovalov]

I've tested this - it looks to me that #849 fixes this as it was intended. Thanks everyone!