How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?

Question

This is a follow-up to this question by Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let

$$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N\}^2;(m-n)(f(m)-f(n))<0\right\}\right|}{N^2}\in[0,1].$$

How high can $\operatorname{rc}(f)$ get?

• Upper bound: $\frac{15}{16}$ can be seen to be an upper bound using the ideas of my answer to the aforementioned question.

• Lower bound: $\frac{1}{2}$, this is reached for the function $f:\mathbb{N}\to\mathbb{N}$ defined in each interval $[k!,(k+1)!-1]$ by $f(n)=(k+1)!+k!-1-n$ (this example was mentioned by the user bof in a deleted comment).

Answer 1

A fun problem. The answer is $3/4$.

Lower bound: We first make some relaxations to the problem.

Firstly we observe that we can relax the requirement that $f$ be bijective to $f$ being injective, because any injective map can converted to be a bijection by modifying it on an infinite set $A$ of density zero (replacing $f$ on $A$ with some bijection between the equinumerable sets $A$ and $f(A) \cup f({\bf N})^c$), which does not affect $\mathrm{rc}(f)$.

Secondly we can relax the requirement that $f$ be injective further, to the requirement that $f$ is proper (all preimages of $f$ are finite). Indeed, if we have a proper map $f$, enumerate each preimage $f^{-1}(k)$ in increasing order as $N_{k,1}<\dots< N_{k,a_k}$ for some $a_k \geq 0$, and then one can check that the modified map $\tilde f: {\bf N} \to {\bf N}$ defined by $$ \tilde f( N_{k,i} ) := (\sum_{j=1}^k a_j) - i + 1$$ is injective with $\mathrm{rc}(f) = \mathrm{rc}(\tilde f)$ (where in order to extend $\mathrm{rc}$ to non-injective $f$ one should use the closed condition $(m-n)(f(m)-f(n)) \leq 0$ rather than the open condition $(m-n)(f(m)-f(n)) < 0$). (Actually this second reduction subsumes the first, since $\tilde f$ is in fact bijective, but I retain the first reduction as I think it is a little more intuitive, and was the one I discovered first.)

Heuristically, the problem becomes easier the more slowly growing we allow $f$ to be, as this creates lots of collisions $f(n)=f(m)$ that automatically contribute to $\mathrm{rc}(f)$. A monotonic slowly growing function, such as $f(n) = \lfloor \log \log (n+100) \rfloor$, is proper, but only gives the lower bound of $1/2$ mentioned previously, with the main contribution coming from scales where $f$ transitions abruptly from one value $i$ to the next. To reduce the effect of this transition we perform a random construction to "smooth things out". Let $g: {\mathbf R}^+ \to {\mathbf R}^+$ be a sufficiently slowly growing function, e.g., $g(x) = \log\log(x+100)$ will suffice, and define a random function $f : {\bf N} \to {\bf N}$ by declaring $f(n)$ to equal $\lfloor g(n) \rfloor$ with probability $1 - \{g(n)\}$ and $\lfloor g(n) \rfloor+1$ with probability $\{g(n)\}$, independently in $n$. [One can think of $f$ as a "pointillist" discretization of $g$.] Clearly $f$ is proper, and it is a routine matter (using the Chernoff inequality) to verify that $\mathrm{rc}(f)=3/4$ almost surely if $g$ is sufficiently slowly growing (the key scales $N$ are those where $g(N)$ is close to a half-integer). [Compare with the indicator function $1_A$ of a random set of density $p$, where one can compute $\mathrm{rc}(1_A) = 1 - p(1-p) \geq 3/4$ almost surely, with equality at $p=1/2$, although this function is not directly eligible for consideration as it will not be proper.]

Upper bound: For each $N$, let $L_N$ be the median value of $\{f(1),\dots,f(N)\}$. As observed previously, these medians go to infinity as $N \to \infty$. Thus we can find arbitrarily large $N$ which have "world record medians" in the sense that $L_n < L_N$ for all $1 \leq n \leq N$. (In the lower bound example, these correspond to scales where $g(N)$ is close to a half-integer, which we previously identified to be critical.) We remark that this observation only requires $f$ to be proper, rather than bijective.

Let $N$ be as above, and let $E_N$ be the set of all $1 \leq n \leq N$ such that $f(n) \leq L_N$, then $E_N$ has cardinality $N/2+O(1)$; furthermore, for any $n \leq N$, $E_N \cap \{1,\dots,n\}$ has cardinality at least $n/2+O(1)$. The quantity $$ |\{(m,n) \in \{1,\dots,N\}^2: (m-n) (f(m)-f(n)) > 0 \}|$$ is equal by symmetry to $$ 2 |\{ (m,n): 1 \leq m < n \leq N; f(n) > f(m) \}|$$ which is at least $$ 2 |\{ (m,n): 1 \leq m < n \leq N; m \in E_N, n \not \in E_N \}|$$ which we can write as the difference of $$ 2 |\{ (m,n): 1 \leq m < n \leq N; m \in E_N \}| = 2 \sum_{n=1}^N |E_N \cap \{1,\dots,n-1\}|$$ and $$ 2 |\{ (m,n): 1 \leq m < n \leq N; n, m \in E_N \}| = 2 \binom{|E_N|}{2}.$$ By hypothesis, the first quantity is at least $$ 2 \sum_{n=1}^N (n/2+O(1)) = N^2/2 + O(N)$$ and the second quantity is $N^2/4 + O(N)$. Thus $$ |\{(m,n) \in \{1,\dots,N\}^2: (m-n) (f(m)-f(n)) > 0 \}| \geq N^2/4 + O(N)$$ or equivalently $$ |\{(m,n) \in \{1,\dots,N\}^2: (m-n) (f(m)-f(n)) < 0 \}| \leq 3N^2/4 + O(N)$$ giving the upper bound.

Answer 2

This problem arises in Section 4.3 of my PhD thesis in connection with a Ramsey-type result for infinite tournaments. The answer of $3/4$ is also confirmed by Theorem 4.5 in that section, and the corresponding upper/lower bound proofs are similar to the answer given by Tao in this thread.

In the context of the section, the problem comes about because the maximum possible density of forward edges in a tournament on $\mathbb{N}$ not containing an infinite forward path can be shown to be equal to $$\sup{\{\text{rc}(f):\text{$f:\mathbb{N}\to\omega_1$ is an injection}\}}.$$ It would be interesting to know if this problem has appeared anywhere else, or has other applications.