Syndeticity- and thickness-preserving bijections of $\mathbb N$

Question

Let me recall some definitions: a set $A \subseteq \mathbb N$ is:

• syndetic if it intersects every large enough interval, i.e. if $\exists \ell \in \mathbb N^* : \forall k \in \mathbb N, A \cap ⟦ k, k+\ell - 1 ⟧ \neq\varnothing$ ;
• thick if it contains arbitrarily long intervals, i.e. if $\forall \ell \in \mathbb N^*, \exists k \in \mathbb N : ⟦k, k+\ell-1⟧ \subseteq A$.

I'm interested in bijections $\mathbb N \to \mathbb N$ preserving these two notions. More precisely, I say that a bijection $f : \mathbb N \to \mathbb N$

• preserves thickness if, for every set $A \subset \mathbb N$, $A$ thick $\implies$ $f[A]$ thick ;

• strongly preserves thickness if, for every set $A \subset \mathbb N$, $A$ thick $\iff$ $f[A]$ thick.

I can define the same notions for syndeticity, but they are at least partly redundant. Indeed, a set $A$ is syndetic iff $\mathbb N \setminus A$ isn't thick. That shows that a bijection strongly preserves thickness iff it strongly preserves syndeticity.

My first question is the following:

Do you have an example of a bijection $f : \mathbb N \to \mathbb N$ which preserves thickness, but doesn't preserve it strongly?

I'm not sure my second question has a satisfying answer, but here it is:

What is a good description of (strongly) thickness-preserving bijections?

Here's a (hopefully correct) very partial answer: if $W(\mathbb N)$ denote the group of bijections $\mathbb N \to \mathbb N$ satisfying $\exists d \in \mathbb N^* : \forall i \in \mathbb N, \left\lvert f(i) - i \right\rvert \leq d$, every $f \in W(\mathbb N)$ strongly preserves thickness, but there are other examples. For instance, if $(a_n)$ is a rapidly growing sequence, I think that the bijection $f$ swapping each $a_{2n}$ with $a_{2n+1}$ strongly preserves thickness, even if $f \not\in W(\mathbb N)$.

Edit. I now believe that if $f : \mathbb N \to \mathbb N$ is a bijection, and there exists $d \in \mathbb N^*$ such that the "d-approximate support" $S_d(f) = \left\{ i \in \mathbb N \, \big| \, \left\lvert f(i) - i \right\rvert > d \right\}$ isn't piecewise syndetic, $f$ strongly preserves thickness. Could it be a necessary and sufficient condition?

A set is piecewise syndetic iff it can be written as $S \cap T$, where $S$ is syndetic and $T$ thick. It means that, for some $\ell$, it contains arbitrarily long sequences $a_1 < \ldots < a_p$ s.t. $a_{i+1} - a_i \leq \ell$.

Answer 1

The answer to your first question is NO.

In case you use the opposite convention, let me clarify here that what I call $\mathbb N$ starts with $1$ not $0$. Also, an $l$-interval is an interval of $l$ successive integers.

Let $(a_n)_{n\geq 1}$ be an increasing sequence of integers with $a_1=1$ and whose growth is fast enough, in the sense that $a_{n+1}-a_n \geq 3$ for all $n$ and $\lim_{n\to\infty}{a_{n+1}-a_n}=\infty$ (for example $a_n=n^2$ will do).

Let $I_n$ be the integer interval $[|a_n+1,a_{n+1}-2|]$ and $b_n=a_{n+1}-1$ so that $\mathbb N$ is partitioned by the $I_k\cup\lbrace a_k,b_k \rbrace (k\geq 1)$. We now define our counter-example recursively.

Lemma. There is a sequence of partial functions $f_n:{\mathbb N} \to {\mathbb N}(n\geq 0)$, with the following properties :

(1) $f_n$ is injective, and extends $f_{n-1}$ for $n\geq 1$.

(2) The (finite) domain of $f_n$ is equal to $[|1,b_n|]=\bigcup_{m=1}^{n}I_m \cup \lbrace a_m,b_m \rbrace $ plus a finite number of some other $b_m$'s.

(3) For each $j\in [|1,n|]$, there is a constant $c_j$ such that $f_n(x)=x+c_j$ for all $x\in I_j$.

(4) For each $j\in [|1,n|]$, there is an integer interval $K_j$ of length $j$ such that $f_n(b_k)=k$ for all $k\in K_j$. Also the intervals $K_1,K_2,\ldots, K_n$ are pairwise disjoint.

(5) All the numbers $1,2,\ldots ,n$ are in the image of $f_n$.

Proof of lemma. For $n=0$ we may take $f_0$ to be empty map, which vacuously satisfies all the conditions listed. It will then suffice to explain how to construct $f_{n+1}$ from $f_n$.

First, set $f_{n+1}(a_{n+1})$ to be the smallest integer not in the image of $f_n$. This preserves injectivity, and will ensure that (5) will stay true on the $n+1$ level.

Next, (obeying (3)) set $f_{n+1}(x)=x+c_{n+1}$ for all $x\in I_{n+1}$ for a large enough $c_{n+1}$, so that injectivity is preserved.

There is an integer $M$ such that no $b_k$ with $k\geq M$ is in the domain of $f_n$, and no $k\geq M$ is in the image of $f_n$. We can then take $K_{n+1}=[|M+1,\ldots,M+(n+1)|]$, and $f_{n+1}(b_k)=k$ for all $k\in K_{n+1}$, so that (4) stays true on the $n+1$ level.

Finally, if $f_{n+1}(b_n)$ hasn't been defined yet, set it to any yet unused value.
This ensures that the domain of $f_{n+1}$ contains all of $[|1,b_n|]$ and finishes the proof of the lemma.

Proof of claim from lemma. Let $(f_n)_{n\geq 1}$ be a sequence as in the lemma. Since they are mutually compatible, there is an $f$ extending all of them, and $f$ is defined on all of $\mathbb N$ by (2), injective by (1), surjective by (5).

Let $T$ be a thick set, and let $l\geq 0$. Then $T$ contains infinitely many $(2l+3)$-intervals, of which all but finitely many have a $l$-subinterval wholly contained in a single $I_m$ (the worst-case scenario consisting of the $(2l+3)$-interval being centered around some $a_n$). The image of this subinterval by $f$ is an $l$-interval in $f[T]$. Since $l$ is arbitrary, $f[T]$ is thick, so $f$ preserves thickness.

On the other hand, consider $K=\bigcup_{n=1}^{\infty} K_n$. Then $K$ is thick since each $K_n$ is a $n$-interval. Now $f^{-1}[K]=\lbrace b_k \ | \ k \in K \rbrace$ does not contain any $2$-interval, so it's certainly not thick. We see then that $f^{-1}$ does not preserve thickness, which finishes the proof.

Answer 2

Do you have an example of a bijection f:N→N which preserves thickness, but doesn't preserve it strongly?

Think about the Hilbert hotel problem: How do we fit an infinite number of guests to already full infinite hotel? We ask guests that are already in to move to room that have index 2* current index and new guests will fill rooms with odd indexes

Here, we split $\mathbb{N}$ into two categories: even and odd. $\{f(n)\}_n$ is then

• the first even number, followed by
• the first odd number, followed by
• the next $2$ even numbers, followed by
• the next $2$ odd numbers, followed by
• …

The odd numbers are not thick, but their image under this bijection is, so it cannot be strongly thickness-preserving.

To see that $f$ is thickness preserving, fix a thick set $A$ and length $l$. Since $A$ is thick, it contains an interval of length $2(2l)+1$. That interval contains at least $2l$ consecutive odd numbers. Of those consecutive odd numbers, $f$ maps at least half of them together, so that $f(A)$ contains an interval of size at least $l$.

What is a good description of (strongly) thickness-preserving bijections?

Not sure if this will satisfy your needs: since $A\text{ thick}\Leftrightarrow\mathbb{N}\setminus A\text{ not syndetic}$, we have:

Strongly thickness-preserving bijections are strongly nonsyndeticism-preserving bijections