Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

October 19, 2011

Do You Know This Idempotent?

Posted by Tom Leinster

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

{f,f 2,f 3,} \{ 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 nf^n (n1n \geq 1). The proof also shows how to construct it.

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

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

contains exactly one idempotent.

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

Proof  Existence: since XX is finite, we may choose m,k1m, k \geq 1 such that f m=f m+kf^m = f^{m + k}. Then f m=f m+f^m = f^{m + \ell} for all multiples \ell of kk, and so f n=f n+f^n = f^{n + \ell} for all nmn \geq m and all multiples \ell of kk. Choose nn such that nmn \geq m and nn is a multiple of kk, as we clearly may (e.g. n=mkn = m k). Then f nf^n is idempotent.

Uniqueness: suppose that f nf^n and f mf^m are idempotent. Since m1m \geq 1, we have (f n) m=f n(f^n)^m = f^n, that is, f nm=f nf^{n m} = f^n. Similarly, f mn=f mf^{m n} = f^m. So f n=f mf^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 nf^n for our idempotent, and let’s call it the idempotent power of ff. I said earlier that the image of f nf^n is the set of periodic points of ff. The proof is easy. One way round, anything in the image of f nf^n is a fixed point of f nf^n, so it’s a periodic point of ff. The other way round, let xx be a periodic point of ff, with f p(x)=xf^p(x) = x, say; then

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

so xx is in the image of f nf^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 ff of {0,1,2}\{0, 1, 2\}: 0  1  2. 0  ↦   1   \stackrel{↦}{↤}   2.

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

01212 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  2 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 ff, is there a way to compute its idempotent power without first computing an nn such that f nf^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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2448

36 Comments & 2 Trackbacks

Re: Do You Know This Idempotent?

Given xx, iterate forward up to the first periodic point, say f m(x)f^m(x) (with m0m\geq 0). Now iterate backwards through the periodic orbit mm steps. In practice, you could iterate forward until you find the first repetition, say f m(x)=f m+k(x)f^m(x) = f^{m+k}(x), where kk is the size of the periodic orbit. Now the image of xx under the idempotent is f m+((m)modk)(x)f^{m + ((-m)\; mod\; k)}(x)
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 “kkth predecessor of the kkth iterate” (where kk 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 xx under the idempotent power as “f k(f k(x))f^{-k}(f^k(x))” then that suggests that it’s something “on the same level” as xx — a kind of modified version of xx. 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 ff defines a transitive relation by xyn>0:f n(x)=y x \prec y \iff \exists n\gt 0: f^n(x) = y .

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

If you like to think of \prec being generated by the edges xf(x)x\mapsto f(x); then defining μ(y)=min{m|nf n+m(y)=f my}\mu(y) = min\{ m | \exists n f^{n+m}(y)=f^m y\}, then ψ:yf μ(y)(y)\psi:y\mapsto f^{\mu(y)}(y) is a map XCX\to C and now our graph is fibered in trees over cycles — and ψ\psi ought to be the unique map XCX\to C fixing CC and satisfying xCψ(x)=ψ(f(x))x\in C \vee \psi(x)=\psi(f(x)), a much uglier condition! Under φ\varphi, 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 {1,2,,n}\{1, 2, \ldots, n\} (it’s n n2n^{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 nn^n as counting the number of endofunction structures on an nn-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:XXf: X \to X is just the directed graph obtained by drawing an edge iji \to j if f(i)=jf(i) = j, what is sometimes called the cograph of ff (it’s a cospan, dual to the span which we call the graph of ff). One can think of the cograph as depicting the dynamical flow of ff. For finite sets, the long-term behavior of the dynamics stabilizes on the intersection of the decreasing chain f (k+1)(X)f (k)(X)f^{(k+1)}(X) \subseteq f^{(k)}(X) of images of iterates of ff,

f ()(X) k=0 f (k)(X),f^{(\infty)}(X) \coloneqq \bigcap_{k=0}^{\infty} f^{(k)}(X),

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

But more compelling is the sheer picture: the long-range dynamics is that ff 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 iji \to j where both ii and jj 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 ff can not only be described as the set of periodic points of ff, but also as the eventual image of ff, that is, the intersection f Xf^\infty X of the chain

XfXf 2X. X \supseteq f X \supseteq f^2 X \supseteq \cdots.

And then, as you say, ff 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 XX is a finite set and ff is an endomorphism of XX, and f kf^{k} is the idempotent that you get from ff (for some kk), then ff restricted to f k(X)f^{k}(X) is a bijection onto f k(X)f^k(X). If YY is another set and gg is a endomorphism of YY, say that a map h:(X,f)(Y,g)h\colon (X,f)\rightarrow (Y,g) is a map h:XYh\colon X\rightarrow Y such that gh=hfg h=h f. Then

1)f k:(X,f)(f k(X),f)f^k\colon (X,f)\rightarrow (f^k(X),f) is universal among maps h:(X,f)(Y,g)h\colon (X,f)\rightarrow (Y,g) such that gg is a bijection.

2)(f k(X),f)(X,f)(f^k(X),f)\hookrightarrow (X,f) is universal among maps h:(Y,g)(X,f)h\colon (Y,g)\rightarrow (X,f) such that gg is a bijection.

In 1) the arrow (f k(X),f)(Y,g)(f^k(X),f)\rightarrow (Y,g) is the composition g khig^{-k}h i and in 2) (Y,g)(f k(X),f)(Y,g)\rightarrow (f^k(X),f) it is f khg kf^{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 (SetSet-enriched) category CC is the coend c:Chom(c,c)\int^{c: C} \hom(c, c), if this exists. If CC is the category of finite sets, then its trace is the set of conjugacy classes of finite permutations; here the image of fhom(c,c)f \in \hom(c, c) in the trace is the conjugacy class of the permutation on the stable set f ()(c)f^{(\infty)}(c). 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?

Hello! I stumbled upon this very old thread; I think I have a proof that Chom(C,C)\int^C \hom(C,C) coincides with the set of connected components of the endomorphism-arrow category of C\mathbf{C}, namely with π 0\pi_0 of the full subcategory of C 2\mathbf{C}^2 whose objects are pairs (X,u:XX)(X,u :X \to X). Is this description compatible with the one written here?

Posted by: Fosco on November 18, 2019 7:51 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 \mathbb{N} and \mathbb{Z}. I’ll write the corresponding one-object categories as \mathbb{N} and \mathbb{Z} — so, contrary to custom, the categories called \mathbb{N} and \mathbb{Z} are not discrete. I’ll write i:i: \mathbb{N} \hookrightarrow \mathbb{Z} for the inclusion.

Consider the category Set Set^\mathbb{N}. 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 Set Set^\mathbb{Z} is a set equipped with an automorphism. From this point of view, the functor i *:Set Set i^*: Set^{\mathbb{Z}} \to Set^\mathbb{N} is simply inclusion. I’ll usually leave it nameless.

For completely general reasons, the inclusion i *:Set Set i^*: Set^\mathbb{Z} \to Set^\mathbb{N} has both a left and a right adjoint: left and right Kan extension along ii.

Here’s a description of the left adjoint. Let XX be a set equipped with an endomorphism ff. The left adjoint sends X=(X,f)X = (X, f) to the set i !X=Lan iXi_! X = Lan_i X given by

i !X=(×X)/ i_! X = \bigl( \mathbb{Z} \times X \bigr) / \sim

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

Here’s a description of the right adjoint. Let XX be a set equipped with an endomorphism ff. The right adjoint sends X=(X,f)X = (X, f) to the set i *X=Ran iXi_* X = Ran_i X whose elements are doubly infinite trajectories

x 1x 0x 1 \cdots \mapsto x_{-1} \mapsto x_0 \mapsto x_1 \mapsto \cdots

in (X,f)(X, f). In other words, an element of i !Xi_! X is a doubly infinite sequence (x n) n(x_n)_{n \in \mathbb{Z}} such that x n+1=f(x n)x_{n + 1} = f(x_n) for all nn \in \mathbb{Z}. The automorphism that it comes equipped with is left shift. The counit at XX is the map i *XXi_* X \to X given by (x n) nx 0(x_n)_{n \in \mathbb{Z}} \mapsto x_0.

These two adjoints are different: i !i_! is not isomorphic to i *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

FinSet FinSet FinSet^\mathbb{Z} \to FinSet^\mathbb{N}

are equal.

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

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

Xi !Xi *XX. 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 !Xi *Xi_! X \cong i_* X for finite sets XX.

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 XX, the diagonal functor

VectVect X Vect \to Vect^X

has distinct left and right adjoints; but if XX 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𝒮 T\mathcal{S}^T \to \mathcal{S}^{T'} induced by monoid map TTT' \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 \mathbb{N} \hookrightarrow \mathbb{Z}, I first worked out the Kan extensions along any monoid homomorphism TTT' \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 0f 0A 1f 1A 2f 2A 3f 3, A_0 \stackrel{f_0}\longrightarrow A_1 \stackrel{f_1}\longrightarrow A_2 \stackrel{f_2}\longrightarrow A_3 \stackrel{f_3}\longrightarrow \dots\quad ,

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

More precisely, we can group morphisms as

(2)A n 0f n 0A n 0+1f n 11 gA n 1f n 1A n 0+1f n 21 gA n 2A n kf n kA n k+1f n k+1 gA n k+1 \dots\quad A_{n_0} \underbrace{\stackrel{f_{n_0}}\longrightarrow A_{n_0+1} \dots \stackrel{f_{n_1-1}}\longrightarrow}_g A_{n_1} \underbrace{\stackrel{f_{n_1}}\longrightarrow A_{n_0+1} \dots \stackrel{f_{n_2-1}}\longrightarrow}_g A_{n_2} \quad\dots\quad A_{n_k} \underbrace{\stackrel{f_{n_k}}\longrightarrow A_{n_k+1} \dots \stackrel{f_{n_{k+1}}}\longrightarrow}_g A_{n_{k+1}} \quad \dots

where

  • A n 0=A n 1=A n 2=...A_{n_0} = A_{n_1} = A_{n_2} = ... are all equal to the same object AA,
  • all the compositions f n k1f n k1f_{n_k-1} \circ \cdots f_{n_{k-1}} are equal to the same endomorphism g:AAg:A\to A,
  • g:AAg : A\to A is an idempotent.

The original idempotent is the special case when we consider

(3)AfAfAfAf, A \stackrel{f}\longrightarrow A \stackrel{f}\longrightarrow A \stackrel{f}\longrightarrow A \stackrel{f}\longrightarrow \dots\quad ,

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 (i,j)(i,j) with i<ji\lt j with the result of f j1f if_{j-1}\circ\cdots\circ f_i. Because the category is finite, this gives a coloring of the complete graph on N\mathbf{N} with a finite number of colors. By the Ramsey theorem, there is an infinite monochromatic complete subgraph, say I={n 0<n 1<<n k<}I=\{n_0 \lt n_1 \lt \dots \lt n_k \lt \dots \} of color gg. 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/(xyn:f n(x)=f n(y))X / ( x\sim y \iff \exists n: f^n(x)=f^n(y) ), so it is worth mentioning now; this gadget remembers some things the eventual image does not. Of course, in the case of a finite XX, 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 XX it can have half-cycles N\simeq \mathbf{N} and infinite cycles Z\simeq \mathbf{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 ff. It’s worth noting that in general f|Ef|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 pp-height in abelian pp-groups, on which pp acts as a finite-wise-nilpotent homomorphism. On the other hand, the induced map on QQ will always be injective, for if f(x)f(y)f(x)\sim f(y), then f n+1(x)=f n+1(y)f^{n+1}(x)=f^{n+1}(y) for some nn; that is, xyx\sim y.

The eventual image can also be called the limit of the diagram ffXfXX \cdots \to f f X \to f X \to X while the eventual quotient is the colimit of the diagram XfXffX. X \to f X \to f f X \to \cdots .

Incidentally, the connection to pp-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 XX, [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 xx of the eventual image, and send it to its equivalence class [x][x] 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 ff be a linear endomorphism of a finite-dimensional vector space XX. The eventual kernel of ff is the union evKer(f)evKer(f) of the chain of subspaces

Ker(f)Ker(f 2)Ker(f 3), Ker(f) \subseteq Ker(f^2) \subseteq Ker(f^3) \subseteq \cdots,

while the eventual image of ff is the intersection evIm(f)evIm(f) of the chain of subspaces

Im(f)Im(f 2)Im(f 3). Im(f) \supseteq Im(f^2) \supseteq Im(f^3) \supseteq \cdots.

This is the same eventual image as before, though as traditional in linear algebra, I’m writing Im(f n)Im(f^n) instead of f nXf^n X.

It’s not hard to prove that for any operator ff on a finite-dimensional vector space XX,

X=evKer(f)evIm(f). X = evKer(f) \oplus evIm(f).

Projection onto evIm(f)evIm(f) gives us an idempotent operator on XX. So, any endomorphism ff of a finite-dimensional vector space gives rise canonically to an idempotent whose image is the eventual image of ff — 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:

  • evKer(f)=Ker(f N)evKer(f) = Ker(f^N) and evIm(f)=Im(f N)evIm(f) = Im(f^N), where N=dim(X)N = dim(X)
  • the subspaces evKer(f)evKer(f) and evIm(f)evIm(f) are both ff-invariant
  • the restricted operator ff on evKer(f)evKer(f) is nilpotent, and the restricted operator ff on evIm(f)evIm(f) is an automorphism
  • this is the only way to decompose ff 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 FDVect FDVect^\mathbb{N} 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 FDVect FDVect^\mathbb{Z} 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

FDVect FDVect FDVect^\mathbb{Z} \to FDVect^\mathbb{N}

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

XevIm(f)X, X \to evIm(f) \to X,

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

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

FDNilFDVect FDNil \to FDVect^\mathbb{N}

also has a simultaneous left and right adjoint. It sends a pair (X,f)(X, f) to (evKer(f),f| evKer(f))(evKer(f), f|_{evKer(f)}). Again, the projection, inclusion and idempotent associated with the subspace evKer(f)evKer(f) 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(H)B(H) (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 xx of the eventual image, and send it to its equivalence class [x][x] 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 |X|!|X|! is a fine power such that f nf^{n} is the idempotent. Specifically, if a+b+|X|a+b+\cdots \leq |X|, then lcm(a,b,)lcm(a,b,\cdots) divides a!b!a! b! \cdots divides |X|!|X|!, so that f |X|!f^{|X|!} acts as the identity on all cycles; at the same time, no element of XX can be more than |X||X| away from its eventual cycle, and |X||X|!|X|\leq |X|! 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 nn such that f nf^n is idempotent. It must be possible to extract a value of nn that will do from the proof of the proposition that I gave. I certainly agree that |X|!|X|! 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 AA with a map f:AAf: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 SS is a finite semigroup and sSs\in S, then we typically denote its unique idempotent power by s ωs^{\omega}. It can, as was mentioned, be computed as s |S|!s^{|S|!}. If s k=s k+ms^k=s^{k+m} with these guys minimal, then it is s rs^r where r is the unique number between kk and k+m1k+m-1 divisible by nn. 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 ω=lim nx n!x^{\omega}=\lim_{n\to \infty} x^{n!} where xx is the generator. So s ωs^{\omega} is the image of x ωx^{\omega} under the unique continuous extension of the map xsx\mapsto 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(X)f 2(X)f(X)\supseteq f^2(X)\supseteq \cdots of finite sets and so it stabilizes with say f n(X)=f n+1(X)f^n(X)=f^{n+1}(X). So ff restricts to a surjective map f n(X)f n(X)f^n(X)\to f^n(X) which must then be injective by finiteness. Thus ff acts on f n(X)f^n(X) as a permutation and so has a power f kf^k which acts on f n(X)f^n(X) as the identity by basic group theory. Then f n+kf^{n+k} is an idempotent.

Proof 2. Let SS be the subsemigroup generated by ff. Let TT be a minimal (non-empty) subsemigroup (using finiteness of SS). The for all tTt\in T, one has tTt T and TtT t are subsemigroups of TT so tT=T=Ttt T=T=T t. In other words, one can solve ax=ba x=b and xa=bx a=b for all a,bTa,b\in T. Thus TT is a group by a standard group theory exercise. Then TT has an identity which is an idempotent of SS.

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

Re: Do You Know This Idempotent?

Thanks for your comments! Incidentally, to make the math come out right, you need to select an appropriate “Text Filter” from the drop-down menu below where you enter your email address. Anything containing “itex” will do; I use “itex to MathML with parbreaks”. (I fixed the two comments you just made.)

I didn’t know the standard notation s ω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

(finitesetsequippedwithanautomorphism)(finitesetsequippedwithanendomorphism) (finite sets equipped with an automorphism) \hookrightarrow (finite sets equipped with an endomorphism)

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 XX equipped with an endomorphism f:XXf: X \to X a canonical map XXX \to X. That canonical map is our idempotent, f ω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 SS has a unique minimal ideal II which turns out to be an abelian group. If SS acts on a finite set XX then II acts on IXIX by permutations, as does SS (in fact this action factors through II which is a retract of SS. The elements of IXIX can be thought of as the recurrent points of XX: they are the points such that xSsxx\in Ssx for all sSs\in S. Apparently the question of how to compute the identity of II from a generating set of SS 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 MM on 11-generator and a permutation is an action of the free profinite group on 11-generator GG. It is well known that if ee is the unique idempotent of MM, then eMGeM\cong G. Let BMBM and BGBG be the classifying toposes of continuous MM-sets and GG-sets respectively. Then there is an essential geometric morphism from BGBMBG\to 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: ff uniquely decomposes as mem \circ e, where ee is regular epic and mm is monic. ee in turn has a unique section pp which factors through mm (that is, every point in XX is equivalent to a unique periodic point under the equivalence relation given by the kernel pair of ff), and the unique idempotent power of ff is pep \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 ff, it’s the combined kernel pairs of ff, f 2f^2, f 3f^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
Read the post The Eventual Image, Eventually
Weblog: The n-Category Café
Excerpt: The many-sided concept of the eventual image.
Tracked: October 7, 2022 6:07 PM

Post a New Comment