3
$\begingroup$

Given some $k>1$, I am interested in the number of $k$-generated semigroups of order $n$ (either up to isomorphism or all associative binary operations on an n-element set). At first I thought $3$-nilpotent semigroups were the way forward (almost all finite semigroups are $3$-nilpotent). But it appears almost none of the $k$-generated semigroups are $3$-nilpotent (only finitely many), in fact, there are no $k$-generated $3$-nilpotent semigroups of order greater than $k^2+k+1$.

According to gap the number of $2$-generated semigroups (up to isomorphism) of orders $2$ through $8$ is: $3,14,64,212,664,1930,5678$. It seems to be exponential, but it is difficult to say anything from $7$ numbers.

I'm sure someone else must have thought about this before me. Is there anything in the literature? I would love to show they grow exponentially (if indeed this is true), but I'd be interested in any reasonable bounds (upper or lower).

Improve this question
$\endgroup$
4
  • $\begingroup$ The ratio of suceessive terms seems to tend monotonically to e. Based on earlier work with magmas, I am not surprised at this for 2-generated algebras. I would expect similar behaviour for larger k. Have you tried constructions that embed a k generated semigroup into a k+1 generated semigroup of a given order? Gerhard "Enumerating Almost Semigroups Might Work" Paseman, 2014.06.16 $\endgroup$
    – Gerhard Paseman
    Jun 16, 2014 at 22:26
  • $\begingroup$ It's not quite monotonic, the last ratio increases. It would be good to have a few more numbers really (if anyone can think of an efficient algorithm to do this?) Do you mean embed a $k$-generated semigroup of order $n$ in to a $k+1$ generated semigroup of order $n+1$? $\endgroup$
    – alexbailey
    Jun 18, 2014 at 6:38
  • $\begingroup$ Any construction that you can control that allows you to show the desired growth. For example, adjoin an element u to a semigroup of n elements that is k-generated. How do you complete the multiplication table to ensure the result is a k+1 generated semigroup? A (lousy) upper bound is (n+1)^(2n+1), but I suspect n^n is a lower bound. There may be other constructions that bump up n but are easier to count. Gerhard "Finds Computing Labeled Counts Easier" Paseman, 2014.06.18 $\endgroup$
    – Gerhard Paseman
    Jun 19, 2014 at 3:31
  • $\begingroup$ In case anyone is still interested in this. I managed to show that the number of k-generated semigroups has an exponential lower bound (by considering the number of ideals of the rank k free semigroup). But still no progress on an exponential upper bound. Superexponential growth is still a possibility. $\endgroup$
    – alexbailey
    Jan 17, 2015 at 12:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.