4
$\begingroup$

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$?

$\endgroup$
8
  • $\begingroup$ 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$. $\endgroup$ – Sam Hopkins Sep 20 '20 at 20:24
  • $\begingroup$ 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. $\endgroup$ – bof Sep 21 '20 at 4:45
  • $\begingroup$ @SamHopkins So the answer would be related somehow to Landau's function? $\endgroup$ – bof Sep 21 '20 at 4:53
  • $\begingroup$ @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. $\endgroup$ – Sam Hopkins Sep 21 '20 at 5:00
  • $\begingroup$ @bof I would rather state it with $\le$ (for the application I have in mind), I'll update the question for clarity. $\endgroup$ – grok Sep 21 '20 at 9:24
1
$\begingroup$

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))$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.