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



Density of permutation of syndetic sets of integers
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)}$.


