MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a transformation $t$ from the transformation semigroup $T_{n}$, if you take powers of $t$ under composition you get a length $s$ stem followed by a cycle. Permutations by definition have a length zero stem.

Are the terms "stem" and "cycle" common, or is some other terminology used in the literature?

share|cite|improve this question
up vote 1 down vote accepted

This question seems a bit ill-posed to me. There are two possible interpretations here.

(1) If $s$ is an element of a finite semigroup, then $s^i=s^{i+p}$ where there is a minimal such $i$ and $p$. What is the common terminology for $i,p$?

The "official" terminology is that $i$ is the index and $p$ is the period. Or one might call the elements $\lbrace s,..,s^{i-1}\rbrace$ the nilpotent part and $\lbrace s^i,..,s^{i+p-1}\rbrace$ the maximal subgroup or minimal ideal.

This in any event has nothing to do with transformations.

(2) You are interested in the analogue of cycle decomposition for a transformation. In this case, the situation is more complicated than a stem and cycle.

The transformation $f$ has a set of recurrent points (also called the eventual image) on which $f$ acts like a permutation and hence decomposes into cycles. There may be several of them. Attached to each cycle are some number of trees which are directed toward the cycle. There is a only a stem followed by a cycle if there is a point from which every other point can be reached. The terminology is not so standard for this setup. I think there is a good chapter in Peter Higgins book Techniques of semigroups on this sort of thing.

share|cite|improve this answer
s= [3, 3, 1, 0], s^2= [0, 0, 3, 3], s^3=[3, 3, 0, 0], s^4=[0, 0, 3, 3], ... The stem is [3, 3, 1, 0], the next two form the a cycle with period two. So "nilpotent" for [3, 3, 1, 0], and "maximal subgroup/minimal ideal" for {[0, 0, 3, 3], [3, 3, 0, 0]}? Hmm. I'll try to track down a copy of Higgins. – Chad Brewbaker May 15 '13 at 19:08
Ben, you seem like just the person to ask a related question I posted on CSTheory: – Chad Brewbaker May 15 '13 at 19:26
Yep, index and period seem to be standard: – Chad Brewbaker May 15 '13 at 19:50
@Chad, it seems then that it is the cycle/stem in the semigroup you are interested in. The situation I refer to in 2 is s=[1,2,1,2]. Then on the level on {0,1,2,3} one has s cycles {1,2} and has two branches 0->1 and 2<-3. But on the semigroup it is still index 2, period 2. – Benjamin Steinberg May 15 '13 at 19:58
I am not on cstheory stackexchange. The answer to your question is the directed power graph of the semigroup, or at least says this is the name in group theory for this. I think the undirected version is more commonly studied, see this paper by Peter Cameron et al. – Benjamin Steinberg May 15 '13 at 20:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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