Skip to main content
3 of 3
Defined `\N`
LSpice
  • 12.9k
  • 4
  • 45
  • 69

$\newcommand\N{\mathbb N}$No, it is not possible to have $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big) = 1$.

Given the function $f$, we will say that $n\in\mathbb{N}$ is good if $f(n)<f(k)$ for more than $\frac{3n}{4}$ values of $k\in\{1,\dots,n-1\}$. If $\mu_{[\N]^2}\big({\operatorname{rev}(f)}\big) = 1$, then the set of good numbers necessarily has density $1$.

So for big enough $N$ there will be more than $2^{N-1}+1$ good numbers in $[2^N,2^{N+1}-1]$. But that poses a problem: let $N$ be big and let $L_N$ be the median of the set of values $\{f(1),\dots,f(2^N-1)\}$. Then, for all good numbers $n\in[2^N,2^{N+1}-1]$ we have $f(n)<L_N$. Thus, $f(n)\leq L$ for at least $2^N$ values in $\{1,\dots,2^{N+1}\}$. Thus $L_{N+1}\leq L_N$. This cannot happen for all $N$, of course, as $\lim_{N\to\infty}L_N=\infty$, so we have a contradiction.

Saúl RM
  • 10.6k
  • 2
  • 28
  • 48