## October 19, 2011

### 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

$\left\{f,{f}^{2},{f}^{3},\dots \right\}$

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\ge 1$). The proof also shows how to construct it.

Proposition  Let $f:X\to X$ be an endomorphism of a finite set $X$. Then the set

$\left\{f,{f}^{2},{f}^{3},\dots \right\}$

contains exactly one idempotent.

This doesn’t say that there is exactly one $n\ge 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.

Proof  Existence: since $X$ is finite, we may choose $m,k\ge 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\ge m$ and all multiples $\ell$ of $k$. Choose $n$ such that $n\ge m$ and $n$ is a multiple of $k$, as we clearly may (e.g. $n=mk$). Then ${f}^{n}$ is idempotent.

Uniqueness: suppose that ${f}^{n}$ and ${f}^{m}$ are idempotent. Since $m\ge 1$, we have $\left({f}^{n}{\right)}^{m}={f}^{n}$, that is, ${f}^{nm}={f}^{n}$. Similarly, ${f}^{mn}={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}\left(x\right)=x$, say; then

$x=\left({f}^{p}{\right)}^{n}\left(x\right)=\left({f}^{n}{\right)}^{p}\left(x\right)={f}^{n}\left(x\right),$

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 $\left\{0,1,2\right\}$:

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}\left(0\right)=2$. But why? It’s not, for instance, the first periodic point that shows up in the trajectory

$0↦1↦2↦1↦2↦\cdots$

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

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.

Posted at October 19, 2011 11:31 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2448

### Re: Do You Know This Idempotent?

Given $x$, iterate forward up to the first periodic point, say ${f}^{m}\left(x\right)$ (with $m\ge 0$). Now iterate backwards through the periodic orbit $m$ steps. In practice, you could iterate forward until you find the first repetition, say ${f}^{m}\left(x\right)={f}^{m+k}\left(x\right)$, where $k$ is the size of the periodic orbit. Now the image of $x$ under the idempotent is ${f}^{m+\left(\left(-m\right)\phantom{\rule{thickmathspace}{0ex}}\mathrm{mod}\phantom{\rule{thickmathspace}{0ex}}k\right)}\left(x\right)$
Posted by: Anonymous on October 20, 2011 1:41 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Thanks, Anon. Your first couple of sentences give a neat way of looking at it. But this is exactly the algorithm embodied in my proof of the proposition, isn’t it?

(When I say “my proof”, I just mean the proof I gave in the post. The proposition has been known for decades, and I certainly don’t mean to claim any originality.)

Posted by: Tom Leinster on October 20, 2011 1:46 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Under iterations of f, any point ends up in a cycle of periodic points. Let F be the idempotent power of f. Then F is any large enough power of f^{lcm(l_i)} where the l_i are the lengths of the cycles. If it takes an x in the set k iterates to reach a cycle, then F(x) is the k-th predecessor (in its cycle) of the first periodic point that x reaches (in particular if x is periodic, F(x)=x (=predecessor of its successor)).

Posted by: benoit on October 20, 2011 1:53 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

oh, scooped… for once that I could answer a question here :(

Posted by: benoit on October 20, 2011 1:59 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Well, maybe the slogan “$k$th predecessor of the $k$th iterate” (where $k$ is the number of steps it takes to reach a cycle) is more useful than I originally thought.

It is the construction in the proof of the proposition, almost inevitably. But perhaps it provides some insight. For a start, if you abusively write the image of $x$ under the idempotent power as “${f}^{-k}\left({f}^{k}\left(x\right)\right)$” then that suggests that it’s something “on the same level” as $x$ — a kind of modified version of $x$. That seems right, and also reinforces my hope that it’s characterized by some universal property.

Posted by: Tom Leinster on October 20, 2011 2:07 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

The function $f$ defines a transitive relation by $x\prec y⇔\exists n>0:{f}^{n}\left(x\right)=y$.

The disjoint union $C$ of the eventual cycles of $f$ are the maximal subset on which $\prec$ is reflexive. What the idempotent ${f}^{m}$ does is to map $X$ to $C$, remembering how long it takes to reach the cycle; it ought to be the unique map $\phi :X\to C$ restricting to the identity on $C$ and satisfying $f\circ \phi =\phi \circ f$. That would be my categorical guess. If that’s right, the theorem above would be that there is an $n$ such that ${f}^{n}=\phi$.

If you like to think of $\prec$ being generated by the edges $x↦f\left(x\right)$; then defining $\mu \left(y\right)=\mathrm{min}\left\{m\mid \exists n{f}^{n+m}\left(y\right)={f}^{m}y\right\}$, then $\psi :y↦{f}^{\mu \left(y\right)}\left(y\right)$ is a map $X\to C$ and now our graph is fibered in trees over cycles — and $\psi$ ought to be the unique map $X\to C$ fixing $C$ and satisfying $x\in C\vee \psi \left(x\right)=\psi \left(f\left(x\right)\right)$, a much uglier condition! Under $\phi$, the vertices of each tree are coloured stepwise by distance in the tree from the root; it’s like wrapping each tree around its cycle, backwards.

Posted by: Jesse McKeown on October 20, 2011 2:37 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Sure I know this idempotent! It feels like an old friend.

It’s an old friend that I first met while reading Joyal’s wonderful paper

• Une théorie combinatoire des séries formelles, Adv. Math. 42, 1-82 (1981),

particularly the part where he gives his dazzling proof of Cayley’s theorem on the number of distinct tree structures on a given set of nodes $\left\{1,2,\dots ,n\right\}$ (it’s ${n}^{n-2}$), in terms of combinatorial species which this paper introduces for the first time.

I won’t describe how the proof goes exactly (if you don’t know it, you should read it in his paper, or you can find it reproduced in any number of places, such as Proofs from THE BOOK (sic)). But I can at least say that it involves thinking of the nicer-looking quantity ${n}^{n}$ as counting the number of endofunction structures on an $n$-element set, and picturing this endofunction in terms of tree-like structures.

Some of the comments above, particularly Jesse’s, hint at these structures. The picture of an endomorphism $f:X\to X$ is just the directed graph obtained by drawing an edge $i\to j$ if $f\left(i\right)=j$, what is sometimes called the cograph of $f$ (it’s a cospan, dual to the span which we call the graph of $f$). One can think of the cograph as depicting the dynamical flow of $f$. For finite sets, the long-term behavior of the dynamics stabilizes on the intersection of the decreasing chain ${f}^{\left(k+1\right)}\left(X\right)\subseteq {f}^{\left(k\right)}\left(X\right)$ of images of iterates of $f$,

${f}^{\left(\infty \right)}\left(X\right)≔\bigcap _{k=0}^{\infty }{f}^{\left(k\right)}\left(X\right),$

which is nonempty by a compactness argument if you like (any intersection of finitely many of the ${f}^{\left(k\right)}\left(X\right)$ is nonempty, so this infinite intersection is nonempty as well). Moreover, the restriction of $f$ to ${f}^{\left(\infty \right)}\left(X\right)$ is a surjective endofunction on ${f}^{\left(\infty \right)}\left(X\right)$ according to the definition of ${f}^{\left(\infty \right)}\left(X\right)$; hence, by finiteness it is a bijection (a permutation).

But more compelling is the sheer picture: the long-range dynamics is that $f$ eventually sucks everything into a collection of whirlpools which are precisely the cycles of this permutation. Eventually everything in each whirlpool cycles back to itself, and this more or less gives the idempotency you are talking about. To give a little more detail: if you remove the edges $i\to j$ where both $i$ and $j$ belong to a whirlpool cycle, the graph you are left with is a disjoint union of trees which are directed towards and rooted at the whirlpool elements. The idempotent you are referring to simply maps each element to the root of the tree to which it belongs!

Posted by: Todd Trimble on October 20, 2011 3:21 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

The picture of trees is a wonderful and important one. But the last sentence “The idempotent you are referring to simply maps each element to the root of the tree to which it belongs!” is not correct, as explained in Anonymous’s post. Rather, Tom’s idempotent folds each tree down along the whirlpool, and sends a node in the tree to its whirlpool-element that is underneath it once you knock down the tree.

Posted by: Theo on October 20, 2011 3:52 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Yes, that is a nice description, Theo – thanks!

Posted by: Todd Trimble on October 20, 2011 3:59 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Sorry, my description was somewhat embarrassingly wrong. Your 3-element example shows this is not the idempotent. Grr…

Posted by: Todd Trimble on October 20, 2011 3:55 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Todd wrote:

Sure I know this idempotent! It feels like an old friend.

Excellent! That’s just the kind of thing I was hoping to hear.

I should have said in my original post what you said in your comment: the image of the idempotent power of $f$ can not only be described as the set of periodic points of $f$, but also as the eventual image of $f$, that is, the intersection ${f}^{\infty }X$ of the chain

$X\supseteq fX\supseteq {f}^{2}X\supseteq \cdots .$

And then, as you say, $f$ restricts to an automorphism of the eventual image.

I don’t know that proof of Cayley’s theorem from Joyal’s paper. I didn’t even know Cayley’s theorem. I should have a look.

Posted by: Tom Leinster on October 21, 2011 1:08 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Something related with a universal property is the following. If $X$ is a finite set and $f$ is an endomorphism of $X$, and ${f}^{k}$ is the idempotent that you get from $f$ (for some $k$), then $f$ restricted to ${f}^{k}\left(X\right)$ is a bijection onto ${f}^{k}\left(X\right)$. If $Y$ is another set and $g$ is a endomorphism of $Y$, say that a map $h:\left(X,f\right)\to \left(Y,g\right)$ is a map $h:X\to Y$ such that $gh=hf$. Then

1)${f}^{k}:\left(X,f\right)\to \left({f}^{k}\left(X\right),f\right)$ is universal among maps $h:\left(X,f\right)\to \left(Y,g\right)$ such that $g$ is a bijection.

2)$\left({f}^{k}\left(X\right),f\right)↪\left(X,f\right)$ is universal among maps $h:\left(Y,g\right)\to \left(X,f\right)$ such that $g$ is a bijection.

In 1) the arrow $\left({f}^{k}\left(X\right),f\right)\to \left(Y,g\right)$ is the composition ${g}^{-k}hi$ and in 2) $\left(Y,g\right)\to \left({f}^{k}\left(X\right),f\right)$ it is ${f}^{k}h{g}^{-k}$.

Posted by: Federico on October 20, 2011 4:31 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Yes, this is also related to the notion of trace of a category, a kind of categorified dimension.

The trace of a ($\mathrm{Set}$-enriched) category $C$ is the coend ${\int }^{c:C}\mathrm{hom}\left(c,c\right)$, if this exists. If $C$ is the category of finite sets, then its trace is the set of conjugacy classes of finite permutations; here the image of $f\in \mathrm{hom}\left(c,c\right)$ in the trace is the conjugacy class of the permutation on the stable set ${f}^{\left(\infty \right)}\left(c\right)$. This is explained in the examples section of the nLab article linked above.

Posted by: Todd Trimble on October 20, 2011 8:23 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Hi Federico! Thanks for that. Now I feel like I’m making some progress in understanding things abstractly, though the fog hasn’t completely cleared.

Let me develop what you wrote. Take the additive monoids $ℕ$ and $ℤ$. I’ll write the corresponding one-object categories as $ℕ$ and $ℤ$ — so, contrary to custom, the categories called $ℕ$ and $ℤ$ are not discrete. I’ll write $i:ℕ↪ℤ$ for the inclusion.

Consider the category ${\mathrm{Set}}^{ℕ}$. An object is a set equipped with an endomorphism, and a map is a map of sets making the evident square commute (as in your comment). Similarly, an object of the category ${\mathrm{Set}}^{ℤ}$ is a set equipped with an automorphism. From this point of view, the functor ${i}^{*}:{\mathrm{Set}}^{ℤ}\to {\mathrm{Set}}^{ℕ}$ is simply inclusion. I’ll usually leave it nameless.

For completely general reasons, the inclusion ${i}^{*}:{\mathrm{Set}}^{ℤ}\to {\mathrm{Set}}^{ℕ}$ has both a left and a right adjoint: left and right Kan extension along $i$.

Here’s a description of the left adjoint. Let $X$ be a set equipped with an endomorphism $f$. The left adjoint sends $X=\left(X,f\right)$ to the set ${i}_{!}X={\mathrm{Lan}}_{i}X$ given by

${i}_{!}X=\left(ℤ×X\right)/\sim$

where $\sim$ is the equivalence relation generated by $\left(n+1,x\right)\sim \left(n,f\left(x\right)\right)$. The automorphism with which ${i}_{!}X$ comes equipped sends the equivalence class of $\left(n,x\right)$ to that of $\left(n+1,x\right)$. The component of the unit at $X$ (that is, the 2-cell inside the triangle, in the usual diagram for Kan extensions) is the map $X\to {i}_{!}X$ given by sending $x\in X$ to the equivalence class of $\left(0,x\right)$.

Here’s a description of the right adjoint. Let $X$ be a set equipped with an endomorphism $f$. The right adjoint sends $X=\left(X,f\right)$ to the set ${i}_{*}X={\mathrm{Ran}}_{i}X$ whose elements are doubly infinite trajectories

$\cdots ↦{x}_{-1}↦{x}_{0}↦{x}_{1}↦\cdots$

in $\left(X,f\right)$. In other words, an element of ${i}_{!}X$ is a doubly infinite sequence $\left({x}_{n}{\right)}_{n\in ℤ}$ such that ${x}_{n+1}=f\left({x}_{n}\right)$ for all $n\in ℤ$. The automorphism that it comes equipped with is left shift. The counit at $X$ is the map ${i}_{*}X\to X$ given by $\left({x}_{n}{\right)}_{n\in ℤ}↦{x}_{0}$.

These two adjoints are different: ${i}_{!}$ is not isomorphic to ${i}_{*}$. But the surprising thing — at least, it surprised me — is that if you restrict to finite sets, they become the same.

In other words, the left and right adjoints to the inclusion

${\mathrm{FinSet}}^{ℤ}\to {\mathrm{FinSet}}^{ℕ}$

are equal.

To see this, one only needs to think about the two descriptions above in the case that $X$ is finite. It’s fairly easy to see that both ${i}_{!}X$ and ${i}_{*}X$ are equal to the eventual image ${\bigcap }_{n\in ℕ}{f}^{n}X$ of $f$, on which $f$ acts bijectively. As Todd pointed out, this is the same as the image of the idempotent power of $f$, and it’s also equal to the set of periodic points of $f$.

Moreover, given a finite set $X$ equipped with an endomorphism $f$, we can compose the unit and counit maps mentioned above:

$X\to {i}_{!}X\cong {i}_{*}X\to X.$

And the composite is the idempotent that I was seeking to understand.

Note that this abstract description of the idempotent is only available because of the fact that ${i}_{!}X\cong {i}_{*}X$ for finite sets $X$.

It’s hard not to be reminded of another situation in which finiteness forces a left and right adjoint to become equal. For arbitrary sets $X$, the diagonal functor

$\mathrm{Vect}\to {\mathrm{Vect}}^{X}$

has distinct left and right adjoints; but if $X$ is finite, they’re equal. (They each send a finite family of vector spaces to its direct sum.) However, I can’t see any real connection between the two situations.

Posted by: Tom Leinster on October 21, 2011 1:34 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Lawvere talks about left and right adjoints to ${𝒮}^{T}\to {𝒮}^{T\prime }$ induced by monoid map $T\prime \to T$ from the bottom of p.6 of Functorial Remarks on the General Concept of Chaos.

It looks like understanding that paper would help us over at this nforum discussion.

Posted by: David Corfield on October 21, 2011 4:44 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Right: in order to work out the Kan extensions along $ℕ↪ℤ$, I first worked out the Kan extensions along any monoid homomorphism $T\prime \to T$.

The (co)end formulas for Kan extensions are not a perfect fit for this kind of situation: they emphasize the role of objects, whereas here each category has only one object. But of course, if they’re interpreted correctly then they give the correct result.

Posted by: Tom Leinster on October 21, 2011 6:12 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

when you say f is an endomorphism of X does this mean f is a permutation of X?

In your example of f where X=[0,1,2] what do those arrows mean? Can you write it as a cycle?

And is there an easier way to understand what Todd says without those fancy terms?
I think I understand Toms question although I don’t understand some of the answers given.

Posted by: kim on October 20, 2011 9:56 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Well, I’m afraid my post will raise more questions than it answers, but this idempotent is a special case of very nice (I think) combinatorial lemma.

Take a finite category and an infinite sequence of morphisms

(1)${A}_{0}\stackrel{{f}_{0}}{⟶}{A}_{1}\stackrel{{f}_{1}}{⟶}{A}_{2}\stackrel{{f}_{2}}{⟶}{A}_{3}\stackrel{{f}_{3}}{⟶}\dots \phantom{\rule{1em}{0ex}},$

then the sequence can be decomposed into a finite prefix followed by an infinite sequence of the same idempotent $f:A\to A$.

More precisely, we can group morphisms as

(2)$\dots \phantom{\rule{1em}{0ex}}{A}_{{n}_{0}}{\underset{⏟}{\stackrel{{f}_{{n}_{0}}}{⟶}{A}_{{n}_{0}+1}\dots \stackrel{{f}_{{n}_{1}-1}}{⟶}}}_{g}{A}_{{n}_{1}}{\underset{⏟}{\stackrel{{f}_{{n}_{1}}}{⟶}{A}_{{n}_{0}+1}\dots \stackrel{{f}_{{n}_{2}-1}}{⟶}}}_{g}{A}_{{n}_{2}}\phantom{\rule{1em}{0ex}}\dots \phantom{\rule{1em}{0ex}}{A}_{{n}_{k}}{\underset{⏟}{\stackrel{{f}_{{n}_{k}}}{⟶}{A}_{{n}_{k}+1}\dots \stackrel{{f}_{{n}_{k+1}}}{⟶}}}_{g}{A}_{{n}_{k+1}}\phantom{\rule{1em}{0ex}}\dots$

where

• ${A}_{{n}_{0}}={A}_{{n}_{1}}={A}_{{n}_{2}}=...$ are all equal to the same object $A$,
• all the compositions ${f}_{{n}_{k}-1}\circ \cdots {f}_{{n}_{k-1}}$ are equal to the same endomorphism $g:A\to A$,
• $g:A\to A$ is an idempotent.

The original idempotent is the special case when we consider

(3)$A\stackrel{f}{⟶}A\stackrel{f}{⟶}A\stackrel{f}{⟶}A\stackrel{f}{⟶}\dots \phantom{\rule{1em}{0ex}},$

While interesting, I don’t think it helps with the original question, in particular wrt to the computation part: the proof of this relies on the infinite Ramsey theorem, making it rather difficult to analyse in general.

Briefly, the proof goes as: color each $\left(i,j\right)$ with $i with the result of ${f}_{j-1}\circ \cdots \circ {f}_{i}$. Because the category is finite, this gives a coloring of the complete graph on $N$ with a finite number of colors. By the Ramsey theorem, there is an infinite monochromatic complete subgraph, say $I=\left\{{n}_{0}<{n}_{1}<\dots <{n}_{k}<\dots \right\}$ of color $g$. These things satisfy the conditions above…

Posted by: Pierre H. on October 21, 2011 12:23 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Since the eventual image has been mentioned, and I’ve been trying to learn spectral sequences for the last year or so, and particularly enjoyed the SpSeq of an exact couple, and thus I’ve become fond also of the eventual quotient, $X/\left(x\sim y⇔\exists n:{f}^{n}\left(x\right)={f}^{n}\left(y\right)\right)$, so it is worth mentioning now; this gadget remembers some things the eventual image does not. Of course, in the case of a finite $X$, it’s isomorphic to the eventual image (though, I think, not canonically, unless they’re both a bunch of fixed points), but in the case of infinite $X$ it can have half-cycles $\simeq N$ and infinite cycles $\simeq Z$.

On the other hand, the eventual image rememebrs all the nodes that support arbitrarily long branches in what Todd tells me I should call the cograph of $f$. It’s worth noting that in general $f\mid E$ need not be surjective! There may be nodes only supporting infinitely many finite branches, and this is behind the definition of height, particularly of $p$-height in abelian $p$-groups, on which $p$ acts as a finite-wise-nilpotent homomorphism. On the other hand, the induced map on $Q$ will always be injective, for if $f\left(x\right)\sim f\left(y\right)$, then ${f}^{n+1}\left(x\right)={f}^{n+1}\left(y\right)$ for some $n$; that is, $x\sim y$.

The eventual image can also be called the limit of the diagram

$\cdots \to ffX\to fX\to X$

while the eventual quotient is the colimit of the diagram

$X\to fX\to ffX\to \cdots .$

Incidentally, the connection to $p$-height insinuates that Tom is still thinking about operator spectra and characteristic polynomials and prime ideals.

Posted by: Jesse McKeown on October 21, 2011 9:57 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

That’s very interesting, Jesse. It hadn’t occurred to me that there was a connection with height in groups.

Here are a few thoughts.

Of course, in the case of a finite $X$, [the eventual quotient] is isomorphic to the eventual image (though, I think, not canonically, unless they’re both a bunch of fixed points).

Isn’t it canonical? Take an element $x$ of the eventual image, and send it to its equivalence class $\left[x\right]$ in the eventual quotient.

There may be nodes only supporting infinitely many finite branches

Did you mean to write “finitely many finite branches”?

Incidentally, the connection to p-height insinuates that Tom is still thinking about operator spectra and characteristic polynomials and prime ideals.

Yes! I’m glad you spotted that. I’ll reveal what actually lay behind my question.

Let $f$ be a linear endomorphism of a finite-dimensional vector space $X$. The eventual kernel of $f$ is the union $\mathrm{evKer}\left(f\right)$ of the chain of subspaces

$\mathrm{Ker}\left(f\right)\subseteq \mathrm{Ker}\left({f}^{2}\right)\subseteq \mathrm{Ker}\left({f}^{3}\right)\subseteq \cdots ,$

while the eventual image of $f$ is the intersection $\mathrm{evIm}\left(f\right)$ of the chain of subspaces

$\mathrm{Im}\left(f\right)\supseteq \mathrm{Im}\left({f}^{2}\right)\supseteq \mathrm{Im}\left({f}^{3}\right)\supseteq \cdots .$

This is the same eventual image as before, though as traditional in linear algebra, I’m writing $\mathrm{Im}\left({f}^{n}\right)$ instead of ${f}^{n}X$.

It’s not hard to prove that for any operator $f$ on a finite-dimensional vector space $X$,

$X=\mathrm{evKer}\left(f\right)\oplus \mathrm{evIm}\left(f\right).$

Projection onto $\mathrm{evIm}\left(f\right)$ gives us an idempotent operator on $X$. So, any endomorphism $f$ of a finite-dimensional vector space gives rise canonically to an idempotent whose image is the eventual image of $f$ — exactly as for sets. I was trying to understand that idempotent. But I realized that I didn’t even properly understand its set-theoretic analogue, which ought to be a simpler thing. Hence this post.

Here are a few simple facts about eventual kernel and image:

• $\mathrm{evKer}\left(f\right)=\mathrm{Ker}\left({f}^{N}\right)$ and $\mathrm{evIm}\left(f\right)=\mathrm{Im}\left({f}^{N}\right)$, where $N=\mathrm{dim}\left(X\right)$
• the subspaces $\mathrm{evKer}\left(f\right)$ and $\mathrm{evIm}\left(f\right)$ are both $f$-invariant
• the restricted operator $f$ on $\mathrm{evKer}\left(f\right)$ is nilpotent, and the restricted operator $f$ on $\mathrm{evIm}\left(f\right)$ is an automorphism
• this is the only way to decompose $f$ as the direct sum of a nilpotent and an automorphism.

In my comment up here, I pointed out that in the world of finite sets, eventual image arises as a simultaneous left and right adjoint. The same is true in the world of finite-dimensional vector spaces, as follows.

Let ${\mathrm{FDVect}}^{ℕ}$ denote the category in which an object is a finite-dimensional vector space equipped with an operator, and a map is a linear map commuting with the specified operators. Let ${\mathrm{FDVect}}^{ℤ}$ be the similar category in which an object is a finite-dimensional vector space equipped with an invertible operator, i.e. an automorphism. Then the inclusion

${\mathrm{FDVect}}^{ℤ}\to {\mathrm{FDVect}}^{ℕ}$

has a simultaneous left and right adjoint. It sends a pair $\left(X,f\right)$ (with $X$ a finite-dimensional vector space and $f$ an operator on $X$) to $\left(\mathrm{evIm}\left(f\right),f{\mid }_{\mathrm{evIm}\left(f\right)}\right)$. Because it’s both a left and a right adjoint, there are canonical maps

$X\to \mathrm{evIm}\left(f\right)\to X,$

which are projection and inclusion; their composite is our idempotent.

And something similar is true for eventual kernels. Let $\mathrm{FDNil}$ be the category in which an object is a finite-dimensional vector space equipped with a nilpotent operator. Then the inclusion

$\mathrm{FDNil}\to {\mathrm{FDVect}}^{ℕ}$

also has a simultaneous left and right adjoint. It sends a pair $\left(X,f\right)$ to $\left(\mathrm{evKer}\left(f\right),f{\mid }_{\mathrm{evKer}\left(f\right)}\right)$. Again, the projection, inclusion and idempotent associated with the subspace $\mathrm{evKer}\left(f\right)$ all arise from the structure of the adjunctions.

I must say, I don’t really understand the reason for the existence of these simultaneous left and right adjoints.

Posted by: Tom Leinster on October 21, 2011 10:38 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Conversely: on my way home yesterday evening I was thinking about your question, trying to see if converting it into a statement about (certain) endomorphisms on a finite-dimensional vector space gave me any ideas…

An aside, which is probably not very helpful: in operator theory people talk about the range projection of a given element in $B\left(H\right)$ (well, in a von Neumann algebra); but there they really mean something like the orthogonal projection onto the eventual image.

Posted by: Yemon Choi on October 22, 2011 12:07 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Isn’t it canonical? Take an element $x$ of the eventual image, and send it to its equivalence class $\left[x\right]$ in the eventual quotient.

Oh, yes! that’s very sensible. And of course, when this is a bijection, it has a canonical section and all that.

Did you mean to write “finitely many finite branches”?

No; perhaps I should transpose the “only” across the “infinitely many”. That is, “there may be nodes that support only finite branches, but infinitely many and of arbitrary length”. Though, again, no such thing can happen in the finite case.

I’m afraid I’m running out of insights, except that finiteness is sometimes defined as the extent to which one can promote either surjection or injection to bi-jection, and one promotion usually implies the other.

Posted by: Jesse McKeown on October 22, 2011 4:19 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Right, got you. That kind of branching seems to come up quite often when thinking about trees, as a kind of warning against sloppy thinking. A node might have no infinite path leading up from it (orienting the tree so that the root’s at the bottom), but it might have arbitrarily long finite paths.

Posted by: Tom Leinster on October 22, 2011 1:02 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Oh, er… did this get figured out? I’m pretty sure $\mid X\mid !$ is a fine power such that ${f}^{n}$ is the idempotent. Specifically, if $a+b+\cdots \le \mid X\mid$, then $\mathrm{lcm}\left(a,b,\cdots \right)$ divides $a!b!\cdots$ divides $\mid X\mid !$, so that ${f}^{\mid X\mid !}$ acts as the identity on all cycles; at the same time, no element of $X$ can be more than $\mid X\mid$ away from its eventual cycle, and $\mid X\mid \le \mid X\mid !$ with only two exceptions.

Posted by: Jesse McKeown on October 23, 2011 12:58 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Well, it’s not so much that I was interested in finding the smallest $n$ such that ${f}^{n}$ is idempotent. It must be possible to extract a value of $n$ that will do from the proof of the proposition that I gave. I certainly agree that $\mid X\mid !$ will do.

What I wanted was to improve my understanding of that idempotent power. That improved understanding might come in the form of a different way of calculating it, or in the form of a categorical explanation of its existence. I think we’ve made some progress on both fronts, thanks to various people’s contributions. Personally, I still don’t understand the idempotent power as well as I’d like to, although I now know how to describe it in several ways.

Posted by: Tom Leinster on October 23, 2011 2:20 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

A set $A$ with a map $f:A\to A$ is a (universal) algebra with a single unary operation – the simplest nontrivial universal algebra possible.

These objects are called “monounary algebras”. This subject is alive and well-doing in universal algebra.

Posted by: Gejza Jenca on October 30, 2011 4:45 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Thanks! I didn’t know the term “monounary algebra”.

I imagine that universal algebraists have a particular way of understanding the idempotent power of a unary operation. Can you pass any of that understanding on to us?

Google is aware of about a thousand pages containing both “mononunary algebra” and “idempotent”, but I haven’t found any specific discussion of the topic of this post. I’m sure such discussions exist and I’m just not seeing them.

Posted by: Tom Leinster on October 30, 2011 7:17 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

> I imagine that universal algebraists have a particular way of
> understanding the idempotent power of a unary operation. Can
> you pass any of that understanding on to us?

Not really, I just saw these things on some conferences.

Danica Jakubikova-Studenovska from Kosice, Slovakia is an expert
in monounary algebras, maybe you should drop her an e-mail.

Posted by: Gejza Jenca on October 31, 2011 12:34 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

As a finite semigroup theorist, I sure hope I do! If $S$ is a finite semigroup and $s\in S$, then we typically denote its unique idempotent power by ${s}^{\omega }$. It can, as was mentioned, be computed as ${s}^{\mid S\mid !}$. If ${s}^{k}={s}^{k+m}$ with these guys minimal, then it is ${s}^{r}$ where r is the unique number between $k$ and $k+m-1$ divisible by $n$. The categorical viewpoint is that the $\omega$-power is a natural transformation from the underlying set functor to itself. This functor is prorepresentable with pro-representing object the free profinite semigroup on one generator. This semigroup also has a unique idempotent ${x}^{\omega }={\mathrm{lim}}_{n\to \infty }{x}^{n!}$ where $x$ is the generator. So ${s}^{\omega }$ is the image of ${x}^{\omega }$ under the unique continuous extension of the map $x↦s$.

The existence of lots of idempotents is what makes finite semigroups have so much more structure than their infinite kin.

Posted by: Benjamin Steinberg on November 22, 2011 12:23 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

By the way, here are two other proofs I like of this result.

Proof 1. There is a decreasing chain $f\left(X\right)\supseteq {f}^{2}\left(X\right)\supseteq \cdots$ of finite sets and so it stabilizes with say ${f}^{n}\left(X\right)={f}^{n+1}\left(X\right)$. So $f$ restricts to a surjective map ${f}^{n}\left(X\right)\to {f}^{n}\left(X\right)$ which must then be injective by finiteness. Thus $f$ acts on ${f}^{n}\left(X\right)$ as a permutation and so has a power ${f}^{k}$ which acts on ${f}^{n}\left(X\right)$ as the identity by basic group theory. Then ${f}^{n+k}$ is an idempotent.

Proof 2. Let $S$ be the subsemigroup generated by $f$. Let $T$ be a minimal (non-empty) subsemigroup (using finiteness of $S$). The for all $t\in T$, one has $tT$ and $Tt$ are subsemigroups of $T$ so $tT=T=Tt$. In other words, one can solve $ax=b$ and $xa=b$ for all $a,b\in T$. Thus $T$ is a group by a standard group theory exercise. Then $T$ has an identity which is an idempotent of $S$.

Posted by: Benjamin Steinberg on November 22, 2011 11:07 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

I didn’t know the standard notation ${s}^{\omega }$; thanks. It’s also interesting what you write about prorepresentability, and it’s a completely different categorical point (as far as I know) from the one I’d arrived at up here. To say it briefly, the point there was as follows. The inclusion functor

$\left(\mathrm{finite}\mathrm{sets}\mathrm{equipped}\mathrm{with}\mathrm{an}\mathrm{automorphism}\right)↪\left(\mathrm{finite}\mathrm{sets}\mathrm{equipped}\mathrm{with}\mathrm{an}\mathrm{endomorphism}\right)$

has both left and right adjoints — and they’re the same. By putting together units and counits in a suitable way, this produces for each set $X$ equipped with an endomorphism $f:X\to X$ a canonical map $X\to X$. That canonical map is our idempotent, ${f}^{\omega }$.

I was hoping to be able to add a more general statement about arbitrary (commutative?) semigroup actions, not just single endomorphisms, but I haven’t figured it out.

Posted by: Tom Leinster on November 22, 2011 11:24 PM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Any finite commutative semigroup $S$ has a unique minimal ideal $I$ which turns out to be an abelian group. If $S$ acts on a finite set $X$ then $I$ acts on $\mathrm{IX}$ by permutations, as does $S$ (in fact this action factors through $I$ which is a retract of $S$. The elements of $\mathrm{IX}$ can be thought of as the recurrent points of $X$: they are the points such that $x\in \mathrm{Ssx}$ for all $s\in S$. Apparently the question of how to compute the identity of $I$ from a generating set of $S$ is important in the abelian sandpile model. Probably your description in terms of the adjunction generalizes to this context. By the way I liked it and hadn’t seen it.
Posted by: Benjamin Steinberg on November 23, 2011 2:15 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Tom, our two viewpoints are equivalent, as I now understood after reading your later post.

Namely, an endomorphism of a finite set is the same thing as an action of the free profinite monoid $M$ on $1$-generator and a permutation is an action of the free profinite group on $1$-generator $G$. It is well known that if $e$ is the unique idempotent of $M$, then $\mathrm{eM}\cong G$. Let $\mathrm{BM}$ and $\mathrm{BG}$ be the classifying toposes of continuous $M$-sets and $G$-sets respectively. Then there is an essential geometric morphism from $\mathrm{BG}\to \mathrm{BM}$ the left adjoint is the restriction to the eventual range and the right adjoint is the inclusion.

Posted by: Benjamin Steinberg on December 18, 2011 4:29 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

This is just another way to phrase what’s been said by a number of people above: $f$ uniquely decomposes as $m\circ e$, where $e$ is regular epic and $m$ is monic. $e$ in turn has a unique section $p$ which factors through $m$ (that is, every point in $X$ is equivalent to a unique periodic point under the equivalence relation given by the kernel pair of $f$), and the unique idempotent power of $f$ is $p\circ e$ (it sends every point to its unique periodic equivalent).
Posted by: Sridhar Ramesh on November 25, 2011 7:36 AM | Permalink | Reply to this

### Re: Do You Know This Idempotent?

Wait, argh, that’s not right… the equivalence relation of interest isn’t the kernel pair of $f$, it’s the combined kernel pairs of $f$, ${f}^{2}$, ${f}^{3}$, etc. Whoops, sorry!
Posted by: Sridhar Ramesh on November 25, 2011 7:39 AM | Permalink | Reply to this
Read the post The Eventual Image
Weblog: The n-Category Café
Excerpt: Three different categories exhibit very similar dynamical behaviour. Why?
Tracked: December 8, 2011 6:42 AM

Post a New Comment