issue with isomorphism test for two order 4 quasigroups

[Palmer323]

The LOOPS isomorphism test for the two quasigroups represented by tables t1 and t2 below does not seem to produce the correct result:

gap> t1:=[ [ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ], [ 3, 4, 1, 2 ], [ 4, 3, 2, 1 ] ];
[ [ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ], [ 3, 4, 1, 2 ], [ 4, 3, 2, 1 ] ]
gap> t2:=[ [ 3, 4, 1, 2 ], [ 4, 3, 2, 1 ], [ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ] ];
[ [ 3, 4, 1, 2 ], [ 4, 3, 2, 1 ], [ 1, 2, 3, 4 ], [ 2, 1, 4, 3 ] ]
gap> q1:= QuasigroupByCayleyTable(t1);
<quasigroup of order 4>
gap>  q2:= QuasigroupByCayleyTable(t2);
<quasigroup of order 4>
gap>  IsomorphismQuasigroups(q1,q2);
(1,3)

If my analysis is correct then this permutation should be (1,3)(2,4)

Is this an error in IsomorphismQuasigroups or is my understanding incorrect?

[nagygp]

Hi @Palmer323 !

The isomorphism from Q1 to Q2 must not be uniquely defined. In fact, if Q1, Q2 are isomorphic, then the number of Q1->Q2 isomorphisms equals |Aut(Q1)|=|Aut(Q2)|.

Your quasigroups are the elementary abelian group of order 4, their automorphism groups have order 6, and there are 6 isomorphisms from Q1 to Q2.

[Palmer323]

Hi @nagygp

Thank you for your comment.

It has been useful in clarifying what is going on in a program I am writing to test for isomorphism.

After further examination I discovered that my implementation was, in fact, delivering multiple solutions. After your comment I identified 3 solutions under formation. With further debugging I finally achieved the 6 solutions you indicated I should expect.

Testing so far shows the program is returning results which agree with the LOOPS standard test for isomorphism of two quasigroups. Preliminary timing runs seem to indicate this is with greater efficiency in most cases. Most of my effort since your response has been toward trying to overcome extremely long run times which occur in some situations. So far this has been without success.

The approach I am taking is to convert each quasigroup to the set of all Fibonacci cycles (I have called them F-cycles) which can be generated from the Cayley table representation and then search for permutations which map one set to the other. The list of periods of the F-cycles for a given quasigroup I have called the Pisano spectrum (P-spectrum) for the quasigroup. (From 'Pisano period' as used in work related to the numerical Fibonacci sequence mod n).

A README, documentation and code are available in my repository Fibo-quasi.

There seem to be two main reasons why this approach is efficient in the majority of cases.

Firstly, the P-spectrum is isomorphism invariant and is a very effective discriminator. It is used up front in my algorithm to quickly dismiss most non isomorphic cases.

Secondly, the rate of increase, with the order of the quasigroup, of the average number of elements in a P-spectrum is surprisingly low (for order 5 quasigroups the average number of items is approx 3.7 and only rises to approx 6.45 for order 20 quasigroups). Given that the elements of a P-spectrum form a partition of the square of the order this means that the maximum period in a spectrum is usually quite a substantial number. The algorithm matches the F-cycles of the two tables in order of length starting with the longest F-cycles. This means that in most cases all of the members of the quasigroup are involved in this matching process, and if the matching is successful a permutation is immediately derived.

Poor performance occurs in some situations where there are multiple F-cycles of the same length and only a subset of members of the quasigroup are involved in any F-cycle. Steiner Loops provide good examples of this. I would appreciate any ideas for solutions to this performance problem.

The set of F-cycles for a quasigroup can be considered as a 'representation' of the quasigroup, if it is permissible to use that term in this context? There is a one-one correspondence between each sub-sequence of three consecutive elements of an F-cycle to a multiplication instance in the quasigroup (with appropriate treatment of F-cycles of periods 1 and 2). It is a straight forward programming task to generate the F-cycles from a given Cayley table and it is also straight forward to generate the Cayley table from a given set of F-cycles. (functions for these are in my repository)

While there is some material related to some special sequences derived from applying the Fibonacci recurrence relation to quasigroups, e. g. Eulerian quasigroups, I have not found any related to the the full set of F-cycles generated by a quasigroup. Hence my invention of the terms 'F-cycle' and 'P-cycle'. Do you know of any such material?