Density of permutation of syndetic sets of integers

Question

Define the upper uniform density of a set $A\subset\mathbb{Z}$ to be $$ D^+(A)=\lim_{r\rightarrow\infty}\sup_{a\in\mathbb{R}}\frac{|A\cap[a,a+r)|}{r} $$ Fix an arbitrary permutation of the integers $\omega:\mathbb{Z}\rightarrow\mathbb{Z}$ ( i.e. $\omega$ is a bijection) and let $\varepsilon>0$.

Does there exist a syndetic set $A\subset\mathbb{Z}$ (syndetic means it has bounded gaps, or equivalently that there exists some positive $n$ such that $A$ has nonempty intersection with any interval of length $n$) such that $$ D^+(\omega(A))<\varepsilon $$

Answer 1

Yes. Let $\mathbb{Z} = \bigcup_{i=1}^\infty I_i$ be a decomposition of $\mathbb{Z}$ into disjoint intervals of length $n$. We will find $A\subset\mathbb{Z}$ such that $|A\cap I_i| = 1$ for each $i$ and such that $|\omega(A)\cap I_i|\leq 1$ for each $i$. Thus $A$ is syndetic and $D^+(\omega(A)) \leq 1/n$.

Define an infinite bipartite graph $\mathcal{G}$ with vertex classes $U$ and $V$, both of which are indexed by $\mathbb{N}$. Put an edge between $i\in U$ and $j\in V$ whenever $\omega(I_i)\cap I_j\neq\emptyset$. Moreover give each edge $ij$ the weight $|\omega(I_i)\cap I_j|$. Then for every vertex $v\in \mathcal{G}$, the total weight of the edges incident with $v$ is exactly $n$. From this it follows that Hall's marriage condition is satisfied, since for finite $A\subset U$ we have $$ n |A| = \sum_{i\in A} \sum_{j\sim i} w_{ij} \leq \sum_{j\in \Gamma(A)} \sum_{i\sim j} w_{ij} = n |\Gamma(A)|. $$ Thus from the locally finite version of Hall's marriage theorem (which follows from the usual version and compactness) we have an injection $f:U\to V$ such that $f(i) \sim i$ for each $i$. Now choose $A$ by selecting from each interval $I_i$ a point $a$ such that $\omega(a) \in I_{f(i)}$.