Skip to content

Issue enumerating semigroups generated by FFE matrices of dimension at least 16 #1178

Description

@reiniscirpons

Ola, after investigating the recent CI failure I found the following minimal reproducer:

gap> g := Matrix(GF(7), Z(7) * PermutationMat((1, 2), 16));
< immutable compressed matrix 16x16 over GF(7) >
gap> S := Semigroup(g);
<commutative semigroup with 1 generator>
gap> Size(S);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `+' on 2 arguments
The 2nd argument is 'fail' which might point to an earlier problem
* [1] res * data[1] + data[3].func( m, data[3].data )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/orb/gap/hash.gi:780
  [2] data.func( x!.rows, data.data )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/elements/ffmat.gi:123
  [3] htvalue( ht, yy )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/main/orbits.gi:96
  [4] Enumerate( o, infinity );
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/main/orbits.gi:301
  [5] OrbSCC( o )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/main/acting.gi:382
  [6] Enumerate( data, limit, ReturnFalse )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/main/acting.gi:301
  [7] Enumerate( o, infinity );
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/main/orbits.gi:301
  [8] OrbSCC( SemigroupData( S ) )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/greens/acting.gi:1582
  [9] NrDClasses( Semigroup( x ) )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/elements/elements.gi:82
 [10] IndexPeriodOfSemigroupElement( gen )
    @ /Users/rcirpons/Desktop/Source/gap/pkg/Semigroups/gap/attributes/attr.gi:887
<function "_SemigroupSizeByIndexPeriod">( <arguments> )
 called from read-eval loop at *errin*:2

It seems that the issue might be related to hash function selection. A new method for (non-compressed matrices) was recently added to the orb package, see gap-packages/orb#78

Some more investigation:

  1. Dimension 16 seems to be the limit, e.g. for dimension 15 we get the following (the answer 6 is correct, since the matrix has non-identity entries):
gap> g := Matrix(GF(7), Z(7) * PermutationMat((1, 2), 15));
< immutable compressed matrix 15x15 over GF(7) >
gap> S := Semigroup(g);
<commutative semigroup with 1 generator>
gap> Size(S);
6
  1. Non-compressed matrices do not cause an issue:
gap> g := Z(7) * PermutationMat((1, 2), 16);
[ [ 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7), 0*Z(7) ], 
  [ 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), 0*Z(7), Z(7) ] ]
gap> S := Semigroup(g);
<commutative semigroup with 1 generator>
gap> Size(S);
6

My hunch is that we select the wrong hash function in between calls to orb, or we modify the generators to not be compressed at some point but still use the hash function for the compressed matrix.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugLabel for issues or PR which report or fix bugs

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions