[GAP Forum] lack of big space

[Max Horn]

Am 16.08.2010 um 17:19 schrieb mohammad j.mamaghani:

> I would like to calculate the order of a subgroup of symmetric group S_2187 generated by two cycles of length 2187=3^7 using GAP, but gap has not enough space and does not accept all the members of the cycles . Are there any ways to use GAP for this problem?best regards mamaghaniAllameh Tabatabaei university dept of maths and  statsTehran, Iran.

Hi there,

according to a result by John Dixon, two random permutations each moving n points with high probability generate the symmetric or alternating group on n points. To be more precise, the probability is a bit less than 1 - 1/n - 1/n^2 which is roughly 0.9995. In your case, of course only the alternating group is possible (you are looking at two cycles of odd order). Now of course your elements are (I assume) not random, but still, you could first try to somehow (dis)prove that you are looking at the alternating group.

As it is, to determine the size of a permutation group, GAP computes a stabilizer chain. For an alternating group, the number of elements in such a stabilizer chain is huge,  something in O(n^2). In addition, the larger n is, the more space you need to store the permutation, so the memory usage for a single permutation is O(n). This means memory usage is at least O(n^3), maybe worse. (Indeed, some empiric tests I just run seem to confirm this roughly). So it is no surprise that you run out of memory. One can save some memory using so-called "straight line programs" instead of plain permutations (the GAP manual has more information on these), at the cost of some speed, but I doubt it will help much -- you'd still need more than O(n^2) memory just for the stabilizer chain. But then again, maybe if your group is *not* the alternating group, perhaps it has a much shorter stabilizer chain, and you can get further this way.

In summary, unless you happen to have strong reasons to believe that those two cycles generate a much, much, MUCH smaller group (say, if they commute :), it is probably hopeless to compute the order of the subgroup they generate directly by conventional methods. 


Cheers,
Max