4
$\begingroup$

Let $\mathbb{N}$ denote the set of non-negative integers. If $f:\mathbb{N}\to\mathbb{N}$ is a map, we set for $k\in \mathbb{N}$:

  • $f^{(0)}(k) = k$, and
  • $f^{(n+1)}(k) = f(f^{(n)}(k))$ for all $n\in\mathbb{N}$.

We say $r\in \mathbb{N}$ is a rocket element of $f$ if $f^{(n)}(r) < f^{(n+1)}(r)$ for all $n\in \mathbb{N}$ and denote the set of all rocket elements of $f$ by $\text{Roc}(f)$.

If $A\subseteq \mathbb{N}$ we define the upper density $\mu^+(A)$ of $A$ by $$\mu^+(A) = \limsup_{n\to\infty}\frac{|A\cap \{0,\ldots n\}|}{n+1}.$$

By $S_\mathbb{N}$ we denote the set of all bijections $f:\mathbb{N}\to \mathbb{N}$.

Question. Is there $f\in S_\mathbb{N}$ such that $\mu^+(\text{Roc}(f)) = 1$?

Bonus question. If not, what is the value of $\sup\{\text{Roc}(f): f\in S_\mathbb{N}\}$?

(Note. Only the question needs to be answered for acceptance, but I am also keen to know about the "bonus question" if the answer cannot be directly inferred from the answer to the question.)

Improve this question
$\endgroup$
5
  • $\begingroup$ The beginning is just redefining powers in the monoid of self-maps of $\mathbb{N}$. $\endgroup$
    – YCor
    Commented Jul 14, 2019 at 16:48
  • 3
    $\begingroup$ And with a slight misuse of notation, too. Normally you'd write $f^n(k)$, I've only seen $f^{(n)}$ in the context of the $n$th derivative. $\endgroup$
    – Asaf Karagila ♦
    Commented Jul 14, 2019 at 16:50
  • 1
    $\begingroup$ If you restrict to the wobbling group, that is, the group of permutations $f$ of $\mathbb{N}$ such that $\sup_n|f(n)-n|<\infty$, the trivial counterexample fails and there's no $f$ with the given condition, I think. $\endgroup$
    – YCor
    Commented Jul 14, 2019 at 16:51
  • 1
    $\begingroup$ (Yet in the wobbling group the sup (of the bonus question) is $1$, by an easy argument.) $\endgroup$
    – YCor
    Commented Jul 14, 2019 at 18:08
  • $\begingroup$ @AsafKaragila Actually I would write $f^{[n]}(k)$. $\endgroup$
    – Matemáticos Chibchas
    Commented Jul 14, 2019 at 20:15

2 Answers 2

Reset to default
19
$\begingroup$

Choose any infinite set $A\subseteq\mathbb N$ such that $\mu^+(A)=0$. Enumerate both $A$ and $B=\mathbb N\setminus A$ as \begin{align*} A&=\{a_1<a_2< \dots < a_n < \dots\}\\ B&=\{b_1<b_2< \dots < b_n < \dots\} \end{align*} Then you can definite the function $f\colon\mathbb N\to\mathbb N$ \begin{align*} f(b_k)&=b_{k+1}\\ f(a_1)&=b_1\\ f(a_{k+1})&=a_k \end{align*} for $k=1,2,\dots$. It is clear that $f$ is a bijection.

For this function $f$, the set of the rocket elements is either $B$ or $B\cup\{a_1\}$ and the asymptotic density of this set is equal to one.

Improve this answer
$\endgroup$
8
  • 5
    $\begingroup$ The elevators in the Hilbert Hotel $\endgroup$
    – Pietro Majer
    Commented Jul 14, 2019 at 17:00
  • 5
    $\begingroup$ Indeed, this argument shows that any infinite subset of $\Bbb N$ is Roc$(f)$ for some bijection $f$ (and of course, it's impossible for a nonempty finite subset to be Roc$(f)$ for any function $f$). Although we need to be a little careful, because $a_1$ might be in Roc$(f)$ with this construction. $\endgroup$
    – Greg Martin
    Commented Jul 14, 2019 at 18:27
  • 2
    $\begingroup$ @GregMartin Thanks for the comment. I missed the fact that $a_1$ might be in $\operatorname{Roc}(f)$. $\endgroup$
    – Martin Sleziak
    Commented Jul 14, 2019 at 18:36
  • 2
    $\begingroup$ Just to tie off the loose end, here's a modification of the construction: instead of listing $A$ in increasing order, choose any way of writing $A=\{a_1,a_2,\dots\}$ as a sequence, subject only to the restriction $a_1>b_1$. Then the bijection given in the construction definitely has Roc$(f)=B$. $\endgroup$
    – Greg Martin
    Commented Jul 14, 2019 at 19:23
  • 3
    $\begingroup$ @LSpice Aha, well spotted! And indeed (on further thought) no final segment $\{n,n+1,n+2,\dots\}$ with $n>1$ can be the rocket set of a bijection, because the preimage of $n$ would also be in the rocket set. $\endgroup$
    – Greg Martin
    Commented Jul 14, 2019 at 20:00
3
$\begingroup$

You could also make the condition for $r$ to be a rocket element be much stricter such as $$f^{(n+1)}(r) \gt f^n(r)^{f^n(r)!}$$ for all $n.$

Pick $A,B$ as before. Define $f$ on $A$ to satisfy this strong rocket condition. You will have a countable number of wildly increasing sequences. Split $B$ into a countable number of countable subsequences in a more or less explicit manner and use them to provide infinite front ends for each increasing sequence. These front ends might be strictly decreasing, but need not be.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .