Intermittent failure in semifp.tst involving BruteForceInverseCheck

[wilfwilson]

There is sometimes a failure in the test in semifp.tst when the acting methods are enabled. This is one example (I accidentally already re-ran the test):

######## > Diff in:
/home/travis/gap/pkg/semigroups/tst/standard/semifp.tst:2076
# Input is:
BruteForceIsoCheck(iso);
# Expected output:
true
# But found:
false
########
######## > Diff in:
/home/travis/gap/pkg/semigroups/tst/standard/semifp.tst:2078
# Input is:
BruteForceInverseCheck(iso);
# Expected output:
true
# But found:
false
########
#I  Errors detected while testing
Error, Function Calls: <func> must return a value

This is the code that is being run:

gap> S := InverseSemigroup(
> [PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [2, 4, 8, 6, 3, 1, 5, 7]),
> PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [3, 5, 4, 7, 6, 8, 1, 2]),
> PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [4, 6, 7, 1, 8, 2, 3, 5]),
> PartialPerm([], [])]);;
gap> iso := IsomorphismFpSemigroup(S);;
gap> BruteForceIsoCheck(iso);
true
gap> BruteForceInverseCheck(iso);
true

...where the brute force functions are...

gap> BruteForceIsoCheck := function(iso)
>   local x, y;
>   if not IsInjective(iso) or not IsSurjective(iso) then
>     return false;
>   fi;
>   for x in Generators(Source(iso)) do
>     for y in Generators(Source(iso)) do
>       if x ^ iso * y ^ iso <> (x * y) ^ iso then
>         return false;
>       fi;
>     od;
>   od;
>   return true;
> end;;
gap> BruteForceInverseCheck := function(map)
> local inv;
>   inv := InverseGeneralMapping(map);
>   return ForAll(Source(map), x -> x = (x ^ map) ^ inv)
>     and ForAll(Range(map), x -> x = (x ^ inv) ^ map);
> end;;

Here's an example where it fails:

https://travis-ci.org/wilfwilson/Semigroups/jobs/332840055#L4483

[wilfwilson]

Here is another example of a failure:

https://travis-ci.org/gap-packages/Semigroups/jobs/332840001#L2446

[wilfwilson]

And here:

https://travis-ci.org/gap-packages/Semigroups/jobs/332828717#L6259

[james-d-mitchell]

Thanks for the report @wilfwilson, I think both @ChristopherRussell and I noticed this at some point too. Just to record this here: is it the same test that fails every time or different ones?

[ChristopherRussell]

Re-running the code from the tests doesn't seem to reproduce the error on my computer. I wrote the following function to run all the tests that were written by me in semifp.tst. I ran it 100 times with no errors (it takes about 1.7 seconds to run these tests once on my computer).

func := function()
  local S, iso, tst;
  S := SymmetricInverseMonoid(4);;
  iso := IsomorphismFpSemigroup(S);;
  if not BruteForceIsoCheck(iso) then Error("1.1"); fi;
  if not BruteForceInverseCheck(iso) then Error("1.2"); fi;
  S := InverseSemigroup(
  [PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [2, 4, 8, 6, 3, 1, 5, 7]),
  PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [3, 5, 4, 7, 6, 8, 1, 2]),
  PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [4, 6, 7, 1, 8, 2, 3, 5]),
  PartialPerm([], [])]);;
  iso := IsomorphismFpSemigroup(S);;
  if not BruteForceIsoCheck(iso) then Error("2.1"); fi;
  if not BruteForceInverseCheck(iso) then Error("2.2"); fi;
  S := InverseSemigroup(
  [PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [9, 10, 8, 2, 1, 7, 5, 4, 6, 3]),
  PartialPerm([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [10, 9, 3, 6, 5, 2, 8, 1, 4, 7]),
  PartialPerm([], [])]);;
  iso := IsomorphismFpSemigroup(S);;
  if not BruteForceIsoCheck(iso) then Error("3.1"); fi;
  if not BruteForceInverseCheck(iso) then Error("3.2"); fi;
  tst := [InverseMonoid([PartialPerm([1, 2, 3, 4, 5], [4, 5, 2, 3, 1]),
  PartialPerm([1, 3], [1, 3])]), 
  InverseMonoid([PartialPerm([1, 2, 3, 4], [1, 2, 3, 4]), 
  PartialPerm([1, 2, 3, 4, 5], [3, 1, 5, 4, 2])]),
  InverseMonoid([PartialPerm([1, 2, 3, 4, 5], [5, 4, 2, 3, 1]),
  PartialPerm([1, 2, 4], [1, 2, 4])]),
  InverseMonoid([PartialPerm([1, 2, 5], [2, 1, 5]),
  PartialPerm([1, 2], [1, 2])]),
  InverseMonoid([PartialPerm([1, 2, 3], [1, 4, 5]),
  PartialPerm([1, 2, 3, 4, 5], [1, 5, 4, 2, 3])]),
  InverseMonoid([PartialPerm([1, 2, 3, 4, 5], [3, 1, 5, 4, 2]),
  PartialPerm([1, 2, 3, 4, 5], [5, 1, 3, 4, 2])]),
  InverseMonoid([PartialPerm([1, 2, 5], [2, 3, 5]),
  PartialPerm([1, 2, 3, 5], [2, 3, 1, 5])]),
  InverseMonoid([PartialPerm([1, 2, 3, 4, 5], [4, 2, 3, 1, 5]),
  PartialPerm([1, 2, 3, 4, 5], [5, 3, 2, 1, 4])]),
  InverseMonoid([PartialPerm([1, 2, 3, 5], [2, 1, 3, 5]),
  PartialPerm([1, 2, 3, 5], [5, 2, 1, 3])]),
  InverseMonoid([PartialPerm([1, 2, 3], [5, 4, 1]),
  PartialPerm([1, 2, 3, 4, 5], [2, 3, 5, 1, 4])]),
  InverseMonoid([PartialPerm([1, 2, 3, 4, 5], [4, 3, 5, 2, 1]),
  PartialPerm([1, 2, 4, 5], [5, 4, 2, 1]),
  PartialPerm([1, 4], [3, 2]), PartialPerm([1, 2, 3, 4, 5], [2, 3, 5, 1, 4]),
  PartialPerm([1, 2, 5], [2, 3, 4])]),
  InverseMonoid([PartialPerm([1, 2, 3, 4, 5], [2, 4, 1, 5, 3]),
  PartialPerm([1, 3, 4], [2, 1, 3]),
  PartialPerm([1, 2, 3, 4, 5], [4, 1, 2, 5, 3]), PartialPerm([1, 3], [5, 4]),
  PartialPerm([1, 3, 5], [2, 4, 1])])];;
  if not ForAll(tst, IsFactorisableInverseMonoid) then Error("4.1"); fi;
  if not ForAll(tst, S -> BruteForceIsoCheck(IsomorphismFpSemigroup(S))) then
    Error("4.2");
  fi;
  if not ForAll(tst{[1 .. 10]}, S ->
                BruteForceInverseCheck(IsomorphismFpSemigroup(S))) then
    Error("4.3");
  fi;
end;

(requires the BruteForce functions)

[wilfwilson]

@james-d-mitchell It's always that section of the test file, however which lines actually fails varies. Something nothing fails, sometimes it is just the BruteForceInverseCheck on line 2078 that fails, and sometimes it is both the BruteForceIsoCheck and the BruteForceInverseCheck that fail. I've not been able to reproduce any failures on my computer.

[james-d-mitchell]

@wilfwilson and @ChristopherRussell I can reproduce this on my computer, it is some issue in libsemigroups, the code that @ChristopherRussell wrote just exposes the issue. I'll try to prepare a fix.

[mtorpey]

I can reproduce this easily, and I have distilled it as far as this:

SEMIGROUPS.DefaultOptionsRec.report := true;

quick_func := function()
  local S, iso, T, i;
  S := InverseSemigroup(
      [PartialPerm([1 .. 8], [2, 4, 8, 6, 3, 1, 5, 7]),
       PartialPerm([1 .. 8], [3, 5, 4, 7, 6, 8, 1, 2]),
       PartialPerm([1 .. 8], [4, 6, 7, 1, 8, 2, 3, 5]),
       PartialPerm([], [])]);;
  iso := IsomorphismFpSemigroup(S);;
  T := Range(iso);
  for i in [1 .. 10] do if Random(S)^iso = Random(S)^iso then fi; od;
  if (T.1 * T.3 ^ 2) ^ 2 <> T.1 then Error("Problem!"); fi;
end;

repeat quick_func(); until false;

which breaks quickly.

[wilfwilson]

Nice one @mtorpey. Running the above code triggers the Error in several seconds. Note that without the first line SEMIGROUPS.DefaultOptionsRec.report := true; I've not been able to trigger the error. Have you?

[james-d-mitchell]

The bug is definitely in the TC class in libsemigroups.

[james-d-mitchell]

I've fixed this, will push it later today.

[james-d-mitchell]

I believe that this is now resolved by the release of version 3.0.14, but just to be on the safe side, let's leave this issue open for a while.

[james-d-mitchell]

That's long enough, it seems that this is gone now.