Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression

Question

Let $\mathbb{N}$ denote the set of non-negative integers. We say $A\subseteq \mathbb{N}$ is a finite arithmetic progression if there are $a, n, d\in\mathbb{N}$ with $d \geq 1$ and $n \geq 2$ such that $A = \{a+kd: k\in\mathbb{N}\text{ and } k\leq n\}$. (So every finite arithmetic progression has at least $3$ elements.) Let ${\frak A}$ be the (countable) collection of all finite arithmetic progressions.

Question. Is there a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ such that for all $A\in {\frak A}$ we have $\varphi(A)\notin {\frak A}$?

Answer 1

$\newcommand{\N}{\mathbf{N}}$Define, say, $Q=\{2^{2^n}:n\ge 4\}$.

Let $f$ be the permutation of $\N$ exchanging $Q$ and its complement, and increasing on both. I claim that $f$ maps no finite arithmetic progression $A$ of length $\ge 3$ to another one.

Suppose by contradiction that $A$ and $f(A)$ are both finite arithmetic progressions, $|A|\ge 3$. Write $m=\max(A)$ and $k$ the step of $A$, and $c\ge 3$ the cardinal of $A$. Write $A=\{n_1,\dots,n_c\}$, $n_{i+1}-n_i=k$, $n_c=m$. Write $J=\{i:n_i\in Q\}$.

We use that $f(n)\ge 2^n$ for $n\notin Q$ and $f(n)\le \log(n)$ for $n\in Q$.

Start with $c=3$. Since $Q$ contains no arithmetic progression of size 3, $A$ contains exactly 1 or 2 elements of $Q$. If $J\in\{\{1,2\},\{1,3\}\}$ elements, two elements of $Q$ map into $[0,\log(m)]$ and the third one maps beyond $2^{m/2}$, so the image doesn't form an arithmetic progression. If $J=\{2,3\}$ we have a contradiction because $n_2,n_3\in Q$ forces $c_1<0$ for an arithmetic progression $n_1<n_2<n_3$. Finally if $|J|=1$ just apply the case $|J|=2$ to $f^{-1}$.

Now suppose $c\ge 4$. Define $A'=A\cap [m/4,m]$; then $A'$ is an arithmetic progression of length $\ge 3$. Elements of $A'-Q$ map to elements $\ge 2^{m/4}$. Elements of $A\cap Q$ map to elements $\le\log(m)$. Let $k'$ be the step of $f(A)$.

If $|A\cap Q|\ge 2$, then $f(A)$ contains two elements of $[0,\log(m)]$ and hence $k'\le\log(m)$. If in addition $A'-Q$ is nonempty, then $f(A)$ contains an element $\ge 2^{m/4}$ and hence $f(A)$ contains at least $2^{m/4}/\log(m)$ elements. Since $A$ meets $Q$, $m\ge 256$ and hence $2^{m/4}/\log(m)>m\ge c=|f(A)|$, a contradiction.

So one of the following holds (a) $|A\cap Q|\le 1$ or (b) $A'\subset Q$. If $f$ satisfies (b), then strictly more than half of elements of $A$ are in $Q$. Hence replacing $f$ with $f^{-1}$ and $A$ with $f(A)$, we can suppose that strictly less than half of elements of $A$ are in $Q$, and hence (a) holds. Then $f(A)$ is an arithmetic progression of size $\ge 4$ with all elements in $Q$ except possibly one. But this does not exist.

Answer 2

It exists for rather trivial reasons. Define this map inductively. In the even steps, send the smallest element of the domain, which does not yet have an image to the smallest element of the range, such that this choice does not violate your condition.

Your condition is build in such a way that if we have only chosen the images of finitely many elements, there are also only finitely many elements forbidden, so there is always such a choice.

In the odd steps, choose the smallest element of the range which does not have a preimage yet and send to it the smallest element of the domain that does not violate any of these conditions.

Proceed like this ans you get a bijection that does not violate the conditions.