Following my question Why is the minimum size of a generating set for a finite group at most $\log_2 n$?, we know that finite groups have generating sets of size at most $\log_2 n$, and a similar statement can be proven for quasigroups. Are there classes of semigroups (other than the class of groups) for which the minimum size of a generating set is at most logarithmic in the number of elements in the semigroup?

More formally, if $\mathcal{G}$ denotes the set of all finite groups and $\mathcal{S}$ denotes the set of all finite semigroups, is there a set $\mathcal{H}$ such that $\mathcal{G} \subsetneq \mathcal{H} \subsetneq \mathcal{S}$ and for each $G$ in $\mathcal{H}$ on $n$ elements, the semigroup $G$ has a generating set of size at most $\log_2 n$ (or even $O(\log_2 n)$)?

  • $\begingroup$ I think the answer is yes, but probably not what you are looking for. Why not set H to be the class of all finite semigroups which have a generating set of size at most log2(n). There are certainly some semigroups in H which are not groups, for example, all the 2-generated semigroups that are not groups, and Jean-Eric's example is in S but not H. $\endgroup$ – James Mitchell Apr 21 '15 at 21:04

No. Take an $n$-element set $S$ with the multiplication defined by $xy = y$ for all $x, y \in S$. Then the minimal set of generators for $S$ is $S$ itself.

  • $\begingroup$ Okay, this is one semigroup, the zero semigroup, that requires all $n$ elements to generate the semigroup. But there could be another class of semigroups that exclude these, right? $\endgroup$ – argentpepper Apr 16 '15 at 17:29
  • $\begingroup$ This is not one semigroup, there is one for each $n$. $\endgroup$ – J.-E. Pin Apr 16 '15 at 17:57
  • $\begingroup$ Maybe my question was unclear. I have edited my question to add a more formal statement of the problem. $\endgroup$ – argentpepper Apr 17 '15 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.