# Maximal order of an order-preserving map

Let $$X$$ be a finite partially ordered set, let $$f\colon X\to X$$ be an order-preserving map [edit: meaning $$x\le y\implies f(x)\le f(y)$$], and let $$x_0$$ be an initial point. Define $$x_n = f(x_{n-1})$$ for all $$n$$; then the sequence $$(x_n)$$ is ultimately periodic. What is its worst-case period? I.e. what are the minimal $$k<\ell$$ such that $$x_k=x_\ell$$?

With no order assumption, one could have $$\ell=\#X$$ since the map $$f$$ could cycle through all of $$X$$. I'm particularly interested in the case when $$X$$ is the family of subsets of a set $$Y$$, and $$x_0$$ is a small subset. Does there then exist a non-trivial bound, say polynomial in $$\#Y$$ and exponential in $$\#x_0$$?

• Nice question. In the case you care about, when $X=2^{Y}$ is a Boolean lattice, maybe you can argue that the worst case would be if $f$ is a permutation on $Y$. – Sam Hopkins Sep 20 '20 at 20:24
• I can never remember whether "order-preserving" means $x\lt y\implies f(x)\lt f(y)$ or $x\le y\implies f(x)\le f(y)$, please remind me. – bof Sep 21 '20 at 4:45
• @SamHopkins So the answer would be related somehow to Landau's function? – bof Sep 21 '20 at 4:53
• @bof: Regarding Landau's function- well, sort of, except that if we want to keep track of $\#x_0$ we should only take the lcm of $\#x_0$ cycle sizes. Regarding $<$ vs. $\leq$, I think $\leq$ is the usual one for defining morphisms of posets. – Sam Hopkins Sep 21 '20 at 5:00
• @bof I would rather state it with $\le$ (for the application I have in mind), I'll update the question for clarity. – grok Sep 21 '20 at 9:24

This is a comment about a special case that I think gives a negative answer to the last question. Let $$\varOmega$$ be a set of size $$n$$ and let $$B$$ be the lattice of its subsets with the inclusion order.

Now let $$\phi:\varOmega\to\varOmega$$ be any function. For $$X\subseteq\varOmega$$, define $$X^\phi=\lbrace \phi(x) \mid x\in X\rbrace$$ (duplicates removed of course).

Now it is elementary that $$f:B\to B$$ by $$X\mapsto X^\phi$$ is order-preserving. The question is: what can be said about the eventual cycle length of the trajectory of an element of $$B$$?

Consider the case that $$\phi$$ is a permutation. Take $$x_0\in B$$ to have one element from each of the cycles of $$\phi$$. Then the trajectory of $$x_0$$ is a cycle of length equal to the order of $$\phi$$ (as an element of the symmetric group).

For example, if $$n=2 + 3 + \cdots + p_k$$ (sum of first $$k$$ primes) and $$\phi$$ has one cycle of each prime size, then $$\#x_0=k$$ and the length of the cycle is $$N = 2\times3\times\cdots\times p_k$$.

I understand that $$N = \exp\bigl((1 + o(1)) k \log k\bigr)$$. So $$N$$ is larger than exponential in $$\# x_0$$.

Also, $$n\sim \frac12 k^2\log k$$. If I got the inversion right, $$\# x_0=\Theta(\sqrt{n/\log n})$$ and $$N=\exp(\Theta(n^{1/2}\log n))$$.

• Nice, so this is basically using Landau's function as mentioned in the comments. – Sam Hopkins Sep 23 '20 at 2:43
• Thanks -- it shows that not much can be hoped for, even in that (presumably nicest) case. I'll accept it as a (negative) answer! – grok Sep 23 '20 at 15:25