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

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$$.

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.

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

• I think your example doesn't describe a bijection $\mathbb N \to \mathbb N$. Sep 28, 2021 at 20:23
• here trick is simmilar to show that $\#\mathbb{Z} = \#\mathbb{N}$ only that then we had $\mathbb{Z}_+$ and $\mathbb{Z}_-$, but here we have $f[odds]$ and $f[evens]$, and we disperse one of them, I can write code for it in python or C++ Sep 29, 2021 at 6:50
• I corrected some mistakes Sep 29, 2021 at 6:56