IsomorphismRacks() may erroneously return fail #1
Description
To reproduce the bug, let
q2 = Rack([ [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, ....: 7, 6 ], [ 4, 5, 2, 3, 1, 6, 7 ], [ 4, 5, 2, 3, 1, 6, 7 ] ])
and
q1 = Rack([ [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, 7, 6 ], [ 1, 2, 3, 4, 5, ....: 7, 6 ], [ 2, 3, 4, 5, 1, 6, 7 ], [ 2, 3, 4, 5, 1, 6, 7 ] ])
and then execute
IsomorphismRacks(q2,q1)
It will return "fail" even though in fact q2 and q1 are isomorphic, as can be demonstrated by executing
IsomorphismRacks(q1,q2)
which returns the permutation (2,4). Inspection of the matrices confirms that this permutation is an isomorphism of these quandles.
I believe I have tracked down the issue to a difficulty in the function ExtendMorphism in basic.gi, the code for which is:
InstallGlobalFunction("ExtendMorphism", function(rack1, rack2, f)
local c, done, i, j;
c := true;
done := true;
while c = true do
c := false;
for i in [1..Size(rack1)] do
for j in [1..Size(rack1)] do
if f[i]*f[j] <> 0 then
###if f[rack1!.matrix[i][j]] = 0 and rack1!.matrix[i][j] <> 0 then
if f[rack1!.matrix[i][j]] = 0 then
f[rack1!.matrix[i][j]] := rack2!.matrix[f[i]][f[j]];
c := true;
elif f[rack1!.matrix[i][j]] <> 0 and f[rack1!.matrix[i][j]] <> rack2!.matrix[f[i]][f[j]] then
done := false;
c := false;
fi;
fi;
od;
od;
if done = true then
return f;
else
return done;
fi;
od;
end);
The difficulty appears to be that in the if..then..else at the bottom of the while c = true loop, both branches return from the function, so the function always returns in the first iteration in that loop, even if c is true, meaning that entries were added to the morphism f and so we might need to re-try the products of defined entries.
My proposed solution below is to move the return statement to below the while c = true loop. It also appears to me that as soon as the code hits the line where a self-inconsistency in f is detected (the only "elif" clause in the above code), one can simply return false immediately, rather than set a flag and wait until later to return false.
I hope a fix can make its way into the package, so that nobody else beats their head against quandles that are said to be non-isomorphic when they are. Let me know if there is any other way I can assist.
Best regards, Glen Whitney
InstallGlobalFunction("ExtendMorphismFixed", function(rack1, rack2, f)
local c, i, j;
c := true;
while c = true do
c := false;
for i in [1..Size(rack1)] do
for j in [1..Size(rack1)] do
if f[i]*f[j] <> 0 then
###if f[rack1!.matrix[i][j]] = 0 and rack1!.matrix[i][j] <> 0 then
if f[rack1!.matrix[i][j]] = 0 then
f[rack1!.matrix[i][j]] := rack2!.matrix[f[i]][f[j]];
c := true;
elif f[rack1!.matrix[i][j]] <> 0 and f[rack1!.matrix[i][j]] <> rack2!.matrix[f[i]][f[j]] then
return false;
fi;
fi;
od;
od;
od;
return f;
end);