0
$\begingroup$

For any $A\subseteq \mathbb{N}$ we let the (lower) density of $A$ be defined by $$d(A) = \liminf_{n\to\infty}\frac{|A\cap\{0,\ldots,n\}|}{n+1}.$$ If $\pi:\mathbb{N}\to\mathbb{N}$ is a permutation (bijection), let $\text{ex}(\pi) = \{n\in\mathbb{N}: \pi(n) > n\}$ be the set of exceedances, and let $\text{negex}(\pi)=\{n\in\mathbb{N}: \pi(n) < n\}$ be the set of "negative exceedances".

To me it seems inconceivable that there is a permutation $\pi:\mathbb{N}\to\mathbb{N}$ with $d\big(\text{ex}(\pi)\big) \neq d\big(\text{negex}(\pi)\big)$ -- but my intuition has let me down many times.

Is my intuition correct this time? ${}$

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Terminological point: what you call $\mathrm{pos}(\pi)$ is usually called the set of excedances of the permutation $\pi$ (see also my question mathoverflow.net/questions/359684 ) $\endgroup$
    – Sam Hopkins
    Commented Aug 26, 2023 at 15:28
  • 1
    $\begingroup$ Do you perhaps mean $d\big(\text{pos}(\pi)\big) \neq d\big(\text{neg}(\pi)\big)$ is inconceivable? $\endgroup$
    – Gro-Tsen
    Commented Aug 26, 2023 at 15:28
  • 4
    $\begingroup$ Still, slight modification of the (already deleted) comments gives us this: if on each group of 4 consecutive elements we have rotation by 1 position. Then one limit is $\frac{3}{4}$ and the other one is $\frac{1}{4}$. $\endgroup$
    – Aleksei Kulikov
    Commented Aug 26, 2023 at 15:30
  • 2
    $\begingroup$ Wouldn't $(1)(23)(4567)(8, 9, 10 ,11 ,12, 13, 14, 15)...$ be such a permutation? (Add 1 if it isn't one less than a power of two, add 1 and halve if it is). It has $d(pos(\pi)) = 1$ and $d(neg(\pi))=0$ $\endgroup$
    – Daniel Weber
    Commented Aug 26, 2023 at 15:31
  • 2
    $\begingroup$ If $\{A,B\}$ is a partition of $\mathbb N=\{1,2,3,\dots\}$ into two infinite sets with $1\in A$, then there is a permutation $\pi:\mathbb N\to\mathbb N$ such that $A=\{n:\pi(n)\gt n\}$ and $B=\{n:\pi(n)\lt n\}$. Namely, write $A=\{a_1\lt a_2\lt a_2\lt\cdots\}$ and $B=\{b_1\lt b_2\lt b_3\lt\cdots\}$ and define $\pi(a_n)=a_{n+1}$ and $\pi(b_{n+1}=b_n$ for all $n\ge1$, and $\pi(b_1)=1=a_1$. $\endgroup$
    – bof
    Commented Aug 27, 2023 at 1:53

1 Answer 1

Reset to default
8
$\begingroup$

Let $\pi(n) = n+1$ for all $n$ except that $\pi(2^{k}-1) = 2^{k-1}$. In other words, permute cyclically $(2,3)$, $(4,5,6,7)$, $(8,9,10,\ldots,15)$, and so on. Then $d(\operatorname{pos}(\pi))=1$ whereas $d(\operatorname{neg}(\pi))=0$.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Ah, it seems that Command Master came up with the same answer (in the comments) as I was typing this one. $\endgroup$
    – Gro-Tsen
    Commented Aug 26, 2023 at 15:35
  • 1
    $\begingroup$ Re, @CommandMaster's comment. Perhaps the acknowledgement could go in the main post? $\endgroup$
    – LSpice
    Commented Aug 26, 2023 at 17:25
  • $\begingroup$ What I find extra counter-intuitive about @Gro-Tsen's and CommandMaster's construction is, that $\pi^{-1}$ has the property that $d\big(\text{ex}(\pi^{-1})\big) = 0 < 1 = d\big(\text{negex}((\pi^{-1})\big)$. Counterintuitive, because "below every natural number there are only finitely many naturals, but above infinitely many". $\endgroup$
    – Dominic van der Zypen
    Commented Aug 26, 2023 at 20:21

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