Upper Bound On the Average Of $(\phi_n-n)$ For $\phi\in S_\infty$

Question

Let $\phi:\mathbb{N}\rightarrow\mathbb{N}$ be a bijection. Consider $D_N=\biggr\lvert\sum_{n=0}^N(\phi_n-n)\biggr\lvert.$ Are there any well established upper bounds on this value in the limit? It seems reasonable to me that $D_N=o(N),$ essentially saying that the mean of $(\phi_n-n)$ is 0. Are there even stronger claims? Perhaps $D_N=o(N^\epsilon),$ for any $\epsilon>0?$ The problem seems kind of inaccessible to me, so forgive me if the answer is obvious.

Answer 1

Let $f:\ \Bbb{N}\ \longrightarrow\ \Bbb{N}$ be any strictly increasing function. Define $[n]:=\{0,\ldots,n-1\}$ and $$\phi(n):=\begin{cases}f(n)&\text{ if }\ \phi([n])=[n]\\n-1&\text{ if }\ \phi([n])\neq[n]\end{cases}$$ Then $\phi$ is a bijection and $\phi(n)=f(n)$ infinitely often, and for these $n$ you have $D_n=f(n)-n$. This means that $\lim\sup D_n$ is not bounded above by any function of $n$, and also illustrates that $\lim D_n$ need not exist.