4
$\begingroup$

Motivation. If we consider any bijection $\varphi:\newcommand{\N}{\mathbb{N}} \N \to \N$, we say integers $m\neq n$ are shrinking with respect to $\varphi$ if $|m-n|>|\varphi(m) - \varphi(n)|$, and expanding if $|m-n|<|\varphi(m) - \varphi(n)|$. I wondered whether it is possible that expanding and shrinking pairs are in disbalance. Let's make this precise.

Precise formulation. For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. For any positive integer $n\in\N$, we set $[n]^2 :=[\{1,\ldots,n\}]^2$. For $P\subseteq [\N]^2$, we let $$\newcommand{\mmu}{\mu_{[\N]^2}}\mmu(P) = \lim\inf_{n\to\infty}\frac{\newcommand{\card}{\text{card}}\card\big(P\cap [n]^2\big)}{\card\big([n]^2\big)},$$where of course $\card([n]^2) = n(n-1)/2$.

By $S_\N$ we define the set of all bijections $\varphi:\N\to\N$. For $\varphi\in S_\N$ we let the set of shrinking pairs be $\newcommand{\shr}{\text{shr}}\shr(\varphi) = \big\{\{m,n\}\in [\N]^2: |m-n| > |\varphi(m) - \varphi(n)|\big\}$, and for the set of expanding pairs $\newcommand{\exp}{\text{exp}}\exp(\varphi)$ we replace $>$ by $<$.

Question. What are the values of $\sup\big\{\mmu\big(\shr(\varphi)\big) :\varphi \in S_\N\big\}$ and $\sup\big\{\mmu\big(\exp(\varphi)\big) :\varphi \in S_\N\big\}$?

UPDATE. In the comment section below, Emil Jeřábek constructs a bijection $\varphi\in S_\N$ with $\mmu\big(\exp(\varphi)\big) = 1$, establishing $\sup\big\{\mmu\big(\exp(\varphi)\big) :\varphi \in S_\N\big\} = 1$.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ It’s quite trivial to make almost all pairs expanding: e.g., let $\phi(n)=2n$ unless $n$ is a power of $2$, in which case $\phi(n)=2\log_2n+1$. $\endgroup$ Commented Jun 3, 2024 at 8:50
  • 1
    $\begingroup$ @EmilJeřábek I dont think this is a bijection. What is the preimage of 4? $\endgroup$ Commented Jun 3, 2024 at 9:08
  • 4
    $\begingroup$ Yeah, I’ve just realized the image of $\phi$ misses nontrivial powers of $2$. But that’s easy to fix: e.g., make $\phi(2^{2k})=2^{k+1}$, $\phi(2^{2k+1})=2k+1$. $\endgroup$ Commented Jun 3, 2024 at 9:10
  • 1
    $\begingroup$ Shrinking pairs seem more difficult to handle But as a start, for the inverse of the $\phi$ above, about $1/4$ of the pairs are shrinking. $\endgroup$ Commented Jun 3, 2024 at 9:12
  • 2
    $\begingroup$ It seems that the minimal number of non-strictly shrinking (or expanding) pairs for a permutation from $S_n$ is $\Theta(n^{3/2}$, so that the numerator in the $\liminf$ can be taken to any power less than $4/3$ without changing the result, but not further. $\endgroup$ Commented Jun 4, 2024 at 13:24

1 Answer 1

Reset to default
7
$\begingroup$

One has $\max\big\{\mu\big(\exp(\varphi)\big) :\varphi \in S_{\mathbb{N}}\big\}=1$, as mentioned by Emil Jeřábek in the comments.

We can also create a function $\varphi$ with $\mu\big(\text{shr}(\varphi)\big)=1$ in the following way. Consider a sequence of intervals $I_n=\{a_n,\dots,a_{n}+n-1\}$ in $\mathbb{Z}$, where $a_1=1$ and $a_{n+1}=a_n+n+2$, so that there are gaps $2$ points between consecutive intervals.

Also let $J_n=\{b_n,\dots,b_{n}+n-1\}$, where $b_1=1$ and $b_{n+1}=b_n+n+1$.

Note that the sets $\cup_nI_n$ and $\cup_nJ_n$ have density $1$ in $\mathbb{N}$.

Partially define a map $\varphi:\mathbb{N}\to\mathbb{N}$ by $\varphi(a_n+k)=b_n+k$ for all $k=1,\dots,n-1$. So $\varphi$ maps $\cup_nI_n$ bijectively to $\cup_nJ_n$. Extend $\varphi$ to a bijection in $\mathbb{N}$, it doesn't matter how.

Note that for any $a\in I_n$, $b\in I_m$ with $n\neq m$, we have $|\varphi(a)-\varphi(b)|<|a-b|$. This implies that $\mu_{[\mathbb{N}]^2}(\text{shr}(\varphi))=1$, as we wanted.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.