For a positive integer $n$, let $p_n$ denote the $n$-th prime number. Further let $f: {\rm Sym}(\mathbb{N}) \rightarrow {\rm Sym}(\mathbb{N})$ be the monomorphism which maps a permutation $\sigma$ to the permutation $f(\sigma)$ which maps any prime number $p_n$ to $p_{n^\sigma}$ and which is a homomorphism of the monoid $(\mathbb{N},\cdot)$.

Denoting by $f^{(k)}$ the $k$-fold iteration of $f$, is it true that the trajectory $(f^{(k)}(\sigma))_{k \in \mathbb{N}}$ is cyclic only if $\sigma$ is the identity?

Further, is it even true that $$\bigcap_{k=0}^\infty f^{(k)}({\rm Sym}(\mathbb{N})) \ = \ 1?$$ If the latter is false, can one explicitly describe a non-identity element of this intersection?

  • $\begingroup$ What is $n^\sigma$? Should it be $\sigma_n$ or $\sigma(n)$? $\endgroup$ – Max Alekseyev Feb 18 '17 at 13:47
  • $\begingroup$ @MaxAlekseyev $n^\sigma$ denotes the image of $n$ under $\sigma$. $\endgroup$ – Stefan Kohl Feb 18 '17 at 13:50
  • $\begingroup$ Ok, so it's same as $\sigma(n)$. $\endgroup$ – Max Alekseyev Feb 18 '17 at 14:28

If $\sigma$ is the identity, then so is $f(\sigma)$.

Suppose that $\sigma$ is not the identity. Let $m_k$ be the smallest non-fixed point of $f^{(k)}(\sigma)$. It is clear that $m_0\geq 1$ is some finite integer, and for any $k\geq 0$, $m_{k+1} = p_{m_k} > m_k$. In particular, we have $m_k\geq q_k$, where $q_0=1$ and $q_{i+1}=p_{q_i}$ for $i\geq 0$ (A007097).

It follows that the trajectory of $f^{(k)}(\sigma)$ cannot be cyclic unless $\sigma$ is the identity.

Now, for every $k\geq 0$, all elements of $f^{(k)}(\mathrm{Sym}(\mathbb N))$, except the identity, have smallest non-fixed point $\geq q_k$. Hence, the intersection of $f^{(k)}(\mathrm{Sym}(\mathbb N))$ consists of the identity permutation only.

  • $\begingroup$ @StefanKohl: I'm not sure what is interesting to you. Personally I find it quite interesting that $m_k$ is fully determined by $m_0$ (i.e., the smallest non-fixed point of $\sigma$) and otherwise does not depend on $\sigma$. $\endgroup$ – Max Alekseyev Feb 18 '17 at 19:53

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.