Facts about finite cyclic semigroups

Let S be a finite cyclic semigroup. Show that S has a unique maximal subgroup and compute it. Compute the kernel of S. Under what circumstances is S a group? Deduce that every finite semigroup contains an idempotent.

Let S be a finite cyclic subgroup with generator s. Now the map \varphi : \mathbb{N}^+ \rightarrow S given by k \mapsto s^k is a surjective semigroup homomorphism (where \mathbb{N}^+ is a semigroup under +). Since \varphi cannot be injective, there exist pairs of distinct positive natural numbers m+1 > n such that s^{m+1} = s^n. Let (n,m+1) be such that m+1 is minimal among these pairs. (For such m+1, there is a unique n < m+1 with s^n = s^{m+1}, since otherwise m+1 is not minimal.)

We now prove a lemma.

Lemma 1: If n,m \in \mathbb{N}^+ with n \leq m, then there exists a unique d \in \mathbb{N}^+ such that n \leq d(m+1-n) < m+1. Proof: (Existence) Note that m+1-n > 0. By the Division Algorithm in \mathbb{N}, there exist natural numbers (that is, nonnegative integers) q and r such that n = q(m+1-n) + r and 0 \leq r < m+1-n. Letting -t = r - (m+1-n) and d = q+1, we have n = d(m+1-n) - t, so that 0 \leq d(m+1-n) - n = t < m+1-n, and thus n \leq d(m+1-n) < m+1. (Uniqueness) Suppose n \leq d(m+1-n) < m and n \leq e(m+1-n) \leq m, we have (d-e)(m+1-n) = 0, so that d-e = 0, and so d = e. \square

This number d(m+1-n) will turn out to be very special.

Lemma 2: For all i \in \mathbb{N} and k \in \mathbb{N}^+, we have s^{k(m+1-n)}s^{n+i} = s^{n+i}. Proof: We proceed by induction on k. For the base case k = 1, if i = 0, then s^{m+1-n}s^{n+i} = s^{m+1-n+n} = s^{m+1} = s^n = s^{n+i}. If i \neq 0, then s^{m+1-n}s^{n+i} = s^{m+1+i} = s^{m+1}s^i = s^ns^i = s^{n+i}. Now for the inductive step, suppose the result holds for some k. Then s^{(k+1)(m+1-n)}s^{n+i} = s^{m+1-n}s^{k(m+1-n)}s^{n+1} = s^{m+1-n}s^{n+i} = s^{n+i}. So the result holds for all k \geq 1. \square

Corollary 2.1: If a,b \geq n and a \equiv b mod m+1-n, then s^a = s^b. Proof: Without loss of generality, say a > b. Now a-b = q(m+1-n) for some q \geq 1, and thus a = q(m+1-n) + b and b = n+i for some i. \square

Corollary 2.2: If b \geq m+1, then there exists a such that n \leq a < m+1 and s^b = s^a. Proof: It suffices to show that there exists a such that n \leq a < m+1 and a \equiv b mod m+1-n. To that end, let r be the least residue of b-n mod m+1-n. That is, b-n = q(m+1-n) + r, where q and r are nonnegative. Letting a = n+r, we have Then b = q(m+1-n) + a and n \leq a < m+1, so s^b = s^a. \square

Corollary 2.3: S consists of the elements \{s^1,s^2,\ldots,s^n,\ldots,s^m\}, and these are pairwise distinct.

Lemma 3: If a,b \geq n and s^a = s^b, then a \equiv b mod m+1-n. Proof: Since m+1-n \neq 0 and a-n, b-n \geq 0, there exist nonnegative integers q_1,q_2,r_1,r_2 such that a-n = q_1(m+1-n) + r_1, b-n = q_2(m+1-n) + r_2, and 0 \leq r_1,r_2 < m+1-n. Since s^a = s^b, we have s^{q_1(m+1-n)+n+r_1} = s^{q_2(m+1-n)+n+r_2}. Whether q_1 and q_2 are zero (trivially) or not (Lemma 2), we have s^{n+r_1} = s^{n+r_2}. Now r_1,r_2 < m+1-n, so that r_1+n,r_2+n < m+1. By the minimalness of m+1, we have r_1 + n = r_2 + n. Thus a-n \equiv b-n mod m+1-n, and so a \equiv b mod m+1-n. \square

Lemma 4: If a < n and b \in \mathbb{N}^+ such that b \neq a, then s^a \neq s^b. Proof: If b < m+1 and s^b = s^a, we violate the minimalness of m+1. If b \geq m+1, then by Corollary 2.2, there is an integer c with n \leq c < m+1 and s^c = s^b = s^a, again violating the minimalness of m+1. \square

Using Lemmas 3 and 4 and Corollary 2.1, we can now characterize the kernel of \varphi as follows. The equivalence class [a] is \{a\} if 1 \leq a < n, and is \{b \geq n \ |\ b \equiv a\ \mathsf{mod}\ m+1-n\} if a \geq n.

Lemma 5: If s^a is idempotent, with 1 \leq a \leq m, then a = d(m+1-n). (Where d is as defined in Lemma 1.) Proof: If 1 \leq a < n, then we have a = 2a, which has no solution in \mathbb{N}^+. If n \leq a \leq m, then 2a \equiv a mod m+1-n. So a \equiv 0 mod m+1-n, and then a = q(m+1-n) for some q. By Lemma 1, q = d. \square

So S has precisely one idempotent.

Lemma 6: Let S be a semigroup. Let E(S) denote the set of idempotents in S, and let \mathsf{MG}(S) denote the set of maximal subgroups of S. Let \psi : \mathsf{MG}(S) \rightarrow E(S) be defined by G \mapsto 1_G. Then \psi is bijective. Proof: (Surjective) If e \in S is idempotent, then the set G_e = \{a \in S\ |\ ea = ae = a, ab = ba = e\ \mathrm{for\ some}\ b \in S\} is the \subseteq-greatest subgroup of S having identity e by 1.4.11. In particular, G_e is a maximal subgroup, and \psi(G_e) = e. If H \subseteq S is a subgroup with identity e, then H \leq G_e. If H is maximal, then H = G_e. So \psi is injective, and thus bijective. \square

Since our cyclic semigroup S has only one idempotent, it has a unique maximal subgroup. Namely, G_e where e = s^{d(m+1-n)}.

Lemma 7: s^{d(m+1-n)}s^k = s^k if and only if k \geq n. Proof: The (\Leftarrow) direction was proved in Lemma 2. Now suppose s^{d(m+1-n) + k} = s^k. Now d(m+1-n) + k \geq n, so that k \geq n (using our characterization of \mathsf{ker}\ \varphi). \square

Lemma 8: If k \geq n, then there exists \ell \geq n such that s^ks^\ell = s^{d(m+1-n)}. Proof: Choose \ell \geq n such that k+\ell \equiv 0 mod d(m+1-n). \square

Lemmas 7 and 8 demonstrate that G_e = \{s^t\ |\ n \leq t \leq m\}.

In particular, S is a group if and only if n = 1.

Recall now that the kernel of a semigroup is the intersection of its two sided ideals.

Lemma 9: If I \subseteq S is an ideal, then G_e \subseteq I. Proof: Suppose s^a \in I. For all k \geq n, there exists b \geq 1 such that a+b \geq n and a+b \equiv k mod m+1-n; then s^bs^a = s^k. So G_e \subseteq I. \square

Finally, using Corollary 2.2 if necessary, we can see that G_e is itself an ideal of S. Thus the kernel of S is G_e.

Finally, suppose S is a finite semigroup and let s \in S. Now (s) is a cyclic subsemigroup of S, and so must be finite. As we argued above, (s), and thus S, contains an idempotent.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: