### Do You Know This Idempotent?

#### Posted by Tom Leinster

Here’s something extremely elementary. Given a map $f$ from a finite set to itself, the set of iterates

$\{ f, f^2, f^3, \ldots \}$

contains precisely one idempotent. What does this idempotent *do*?

It’s easy to say what its image is: it’s the set of periodic points. But I’m having a harder time understanding the idempotent itself — that is, how it acts on the set concerned.

Can you give an abstract account of where this idempotent comes from? Do you know an alternative way of computing it to the one below? Do you have any other insight?

Here’s the (easy) proof that there *is* exactly one idempotent of the form $f^n$ ($n \geq 1$). The proof also shows how to construct it.

PropositionLet $f: X \to X$ be an endomorphism of a finite set $X$. Then the set$\{ f, f^2, f^3, \ldots \}$

contains exactly one idempotent.

This *doesn’t* say that there is exactly one $n \geq 1$ such that $f^n$ is idempotent. Rather, it says that there is at least one such $n$, and that if $f^n$ and $f^m$ are both idempotent then $f^n = f^m$. In fact, there are always infinitely many $n$ such that $f^n$ is idempotent.

ProofExistence: since $X$ is finite, we may choose $m, k \geq 1$ such that $f^m = f^{m + k}$. Then $f^m = f^{m + \ell}$ for all multiples $\ell$ of $k$, and so $f^n = f^{n + \ell}$ for all $n \geq m$ and all multiples $\ell$ of $k$. Choose $n$ such that $n \geq m$ and $n$ is a multiple of $k$, as we clearly may (e.g. $n = m k$). Then $f^n$ is idempotent.Uniqueness: suppose that $f^n$ and $f^m$ are idempotent. Since $m \geq 1$, we have $(f^n)^m = f^n$, that is, $f^{n m} = f^n$. Similarly, $f^{m n} = f^m$. So $f^n = f^m$.

(You could recast this result as ‘every element of a finite semigroup has a unique idempotent power’. Nothing is gained or lost by doing this, since by the usual Cayley/Yoneda-type argument, every finite semigroup embeds into the endomorphism semigroup of some finite set.)

Let’s write $f^n$ for our idempotent, and let’s call it the **idempotent power** of $f$. I said earlier that the image of $f^n$ is the set of periodic points of $f$. The proof is easy. One way round, anything in the image of $f^n$ is a fixed point of $f^n$, so it’s a periodic point of $f$. The other way round, let $x$ be a periodic point of $f$, with $f^p(x) = x$, say; then

$x = (f^p)^n(x) = (f^n)^p(x) = f^n(x),$

so $x$ is in the image of $f^n$.

So, the idempotent power of an endomorphism takes any point and turns it into a periodic point. But *how*? Consider, for instance, the following endomorphism $f$ of $\{0, 1, 2\}$:
$0 ↦ 1 \stackrel{↦}{↤} 2.$

The periodic points are 1 and 2, so the idempotent power of $f$ must send 0 to either 1 or 2. But which one? Of course, the computation is easy in this example: the idempotent power of $f$ is $f^2$, and $f^2(0) = 2$. But *why*? It’s not, for instance, the first periodic point that shows up in the trajectory

$0 \mapsto 1 \mapsto 2 \mapsto 1 \mapsto 2 \mapsto \cdots$

of 0. Do you know a way of looking at the diagram

$0 ↦ 1 \stackrel{↦}{↤} 2$

and concluding, without serious calculation, that the idempotent power sends 0 to 2?

To ask more or less the same question in a couple of other ways:

- Given an $f$, is there a way to compute its idempotent power without first computing an $n$ such that $f^n$ is idempotent?
- Does the process of turning an endomorphism into its idempotent power have some universal property?

This seems like it should be extremely elementary stuff. Nevertheless, I don’t know how to answer any of these questions.

## Re: Do You Know This Idempotent?