Divergent permutations

NEW

Problem: Let $\mathbb N=\{1,2,\dots\}$. An infinite permutation is a bijection $\pi:\mathbb N\to\mathbb N$. Two infinite permutations $\pi,\sigma$ are divergent if

Determine the largest possible cardinality of a family $\mathcal F\subseteq \operatorname{Sym}(\mathbb N)$ such that every two distinct members of $\mathcal F$ are divergent.

This is the natural formalization of Fachini–Körner’s question, since their definition says that two permutations diverge when the absolute difference of their entries in the same position tends to infinity.

Result: The largest cardinality is

Proof. The upper bound is immediate because $\operatorname{Sym}(\mathbb N)\subseteq \mathbb N^{\mathbb N}$, so $|\operatorname{Sym}(\mathbb N)|=2^{\aleph_0}$.

We construct $2^{\aleph_0}$ pairwise divergent permutations.

For $m\ge1$, put

Partition $\mathbb N$ into consecutive finite intervals $I_m$ of length $L_m$. Identify each $I_m$ with $\mathbb Z/L_m\mathbb Z$. For $a\in\{0,\dots,k_m-1\}$, let $\tau_{m,a}$ be the cyclic shift of $I_m$ by $ad_m$.

If $a\ne b$, then for every $t\in I_m$,

because the cyclic distance between the two shifts is one of

so the corresponding ordinary difference is either $rd_m$ or $L_m-rd_m$, both at least $d_m$.

Now for each binary sequence $x=(x_1,x_2,\dots)\in 2^{\mathbb N}$, define

Thus $f_x(m)$ records the first $m$ bits of $x$. If $x\ne y$, then after their first differing bit, $f_x(m)\ne f_y(m)$ for every sufficiently large $m$.

Define a permutation $\pi_x$ by

Each $\pi_x$ is a bijection of $\mathbb N$, since it is a bijection on every block $I_m$.

Let $x\ne y$. Choose $m_0$ such that $f_x(m)\ne f_y(m)$ for all $m\ge m_0$. Then for $t\in I_m$, $m\ge m_0$,

Given $M$, choose $m\ge\max(m_0,M+1)$. For all sufficiently large positions $t$, lying in blocks $I_j$ with $j\ge m$, we have

Hence $|\pi_x(t)-\pi_y(t)|\to\infty$. Therefore the family

has cardinality $2^{\aleph_0}$ and is pairwise divergent.

Thus the maximum possible cardinality is exactly $2^{\aleph_0}$.

Citation: The open question is from E. Fachini and J. Körner, “Divergent permutations,” arXiv:1904.05113. No prior resolution is used here.