Upper density question For a set $A \subseteq \mathbf{N}$ define the upper density of a set, $\bar{d}(A)$, to be:
$$\bar{d}(A)=\limsup_{n \to \infty} \frac{|A \cap \{1,2,\dots,n\}|}{n}.$$
We also say that a set, $A$, is syndetic if $A$ has bounded gaps, i.e. there is $d \in \mathbf{N}$ such that for all consecutive $x,y \in A$, $|x-y| < d$.
The following question was assigned as a bonus exercise in a number theory class I'm currently taking, and I've been stuck with it for over a week now. I think my trouble stems from a difficulty in dealing with difference sets. Any hints or suggestions are appreciated.
Question:  If $\bar{d}(A)>0$, then $A-A$ is syndetic.
Where $A-A$ is the set of differences of $A$, i.e. $\{x-y : x, y \in A\}$.
 A: I have a solution for anyone who is interested, or may be in the future. I believe it is correct, but if any errors are found, please let me know.
Claim: If $\bar{d}(A)>0$ then $A-A$ is syndetic.
Proof: Let $A \subseteq \mathbf{N}$ such that $\bar{d}(A)>0$. Let $T$ be a shift of $A$, that is, $T:A \mapsto A+1$, where $x \in A+1$ iff $x-1 \in A$. Hence, $T^{-n}: A \mapsto A-n$.  
It is clear that $T$ preserves upper density (I have verified this before, it's rather straightforward.) Also, it is clear that $\bar{d}(\mathbf{N})=1$. More specifically, if we view this as a measure preserving system (with measure given by $\bar{d}$) then it is in fact a finite measure space.
Now, we will need the following lemma:
Lemma: If $(X,\mathcal{B},T,\mu)$ is a measure preserving system such that $\mu(X) < \infty$. Then, for all $A \in \mathcal{B}$ such that $\mu(A)>0$, the set $S=\{n : \bar{d}(A \cap T^{-n}A)>0\}$ is syndetic.
Proof: Without loss of generality, we can assume $\mu(X) =1$. Let $A \in \mathcal{B}$ such that $\mu(A)=\alpha>0$. Assume that $S$ is not syndetic. Let $n > \frac{1}{\alpha}$, then we should have an interval $I = \{n_i, n_i +1, \dots, n_i + n-1\}$ such that $\mu(T^{-m} \cap T^{-n}A) =0$ for all $m,n \in I$. 
But, then we have:
$$\mu(T^{-n_i}A \cup \dots \cup T^{-n_i-n+1} A) = \mu(T^{-n_i}A) + \dots + \mu(T^{-n_i+n-1}A)= \frac{n}{\alpha} > 1.$$
Which is a contradiction, so $S$ must be syndetic.$\square$
So, we can use this lemma on the system $(\mathbf{N}, \mathcal{P}(\mathbf{N}), T, \bar{d})$, where $\mathcal{P}(\mathbf{N})$ is the power set of $\mathbf{N}$.
Hence, the set $S = \{n:\bar{d}(A \cap A-n)>0\}$ is syndetic. 
Thus, we have $x \in A \cap A-n$ for some natural number $n$ if and only if $x \in A$ and $x+n \in A$. So, $n=(x+n)-x \in A-A$. Thus $S \subseteq A-A$ and, since syndeticity is not destroyed by adding more elements to a set, $A-A$ is syndetic. $\square$
A: We work with upper Banach density $d^{*}$ instead, which is defined by $d^{*}(A) = \displaystyle \limsup_{N -M \to \infty}\dfrac{|A \cap [M+1, N]|}{N-M}$ where the interval is taken in $\mathbb{N}.$ Since $d^{*}(A) \geq \overline{d}(A)$, if we show that $d^{*}(A) >0 \implies A-A $ is syndetic, we will be done.
We will make use of the use the easily proven fact that $d^{*}$ is shift invariant and the following two lemmas:
Lemma 1: If $A-x_{i} \quad(i=1, \ldots , k)$ are pairwise disjoint then $d^{*}\left(\displaystyle \bigcup_{i=1}^{k}(A -x_{i})\right) = kd^{*}(A)$
Proof of lemma 1: For simplicity, we will prove the case of $k=2$, the general case will follow a similar argument. Let $x_{1}, x_{2} \in \mathbb{Z}.$ By subadditivity of $\limsup$ and shift invariance, it can be readily seen that $d^{*}((A-x_{1})\cup (A- x_{2})) \leq 2d^{*}(A).$
For the reverse inequality, let $\varepsilon > 0$ be given.
Claim: $2d^{*}(A) - \varepsilon < d^{*}((A- x_{1})\cup (A-{x_{2}}))$
Proof of claim: By the proof of shift invariance of $d^{*}$, there exists a sequence of intervals $I_{k} = [M_{k}+1, N_{k}]$ with $N_{k} - M_{k} \to \infty$ such that $d^{*}(A-x_{1}) = d^{*}(A-x_{2}) = \displaystyle \lim_{k \to \infty}\dfrac{|A \cap I_{k}|}{N_{k} -M_{k}}.$
Corresponding to $\varepsilon >0,$ there exists $l_{1}, l_{2} \in \mathbb{N}$ such that  $k \geq l_{1} \implies d^{*}(A) - \dfrac{\varepsilon}{2}< \dfrac{|(A-x_{1})\cap I_{k}|}{N_{k}-M_k} \\$ and $k \geq l_{2} \implies d^{*}(A) - \dfrac{\varepsilon}{2}< \dfrac{|(A-x_{2})\cap I_{k}|}{N_{k}-M_k}$.
Then for $k \geq l_{1}, l_{2}$ and by disjointness of $A-x_{1}$ and $A-x_{2},$ we have:
$2d^{*}(A)- \varepsilon < \dfrac{|(A-x_{1})\cap I_{k}|}{N_{k}-M_k} + \dfrac{|(A-x_{2})\cap I_{k}|}{N_{k}-M_k} = \dfrac{|((A-x_{1})\cup (A-{x_{2}}))\cap I_{k}|}{N_{k}-M_k}$
Taking $\displaystyle \limsup_{k \to \infty}$ on both sides we get that $2d^{*}(A) - \varepsilon < d^{*}((A- x_{1})\cup (A-{x_{2}}))$ and since $\varepsilon >0$ is arbitrary, the proof of lemma $1$ is complete for $k=2. 
A set $T$ is defined to be thick if it contains arbitrarily long intervals and a set is readily seen to be thick iff its complement is not syndetic. 
Lemma 2: A thick set $T$ contains a set of the form $X - X = \{x_{j} - x_{i}: j >i\}$ for some infinite set $X=\{x_{1}< x_{2} \ldots \}$
Proof of lemma 2: By the definition of thickness, $\forall n \in \mathbb{N}, \exists a_{n} \in \mathbb{N}$ such that $[1, n] \subset T -a_{n}$.
We will inductively construct $X.$ Let $x_{1} \in \mathbb{N}$ be arbitrary. 
Suppose $k \geq 2$ and $x_{1},\ldots x_{k-1}$ have been chosen. Define $y = \max\{x_{i}: 1\leq i \leq k-1\}+1.$ Then for $i=1, \ldots , k-1$, it is clear that $y-x_{i} \in [1, y] \subset T-a_{y}$ which implies $a_{y} +y - x_{i} \in T,$ so setting $x_{k} = a_{y}+ y,$ it follows that for  $i=1, \ldots , k-1$, $x_{k} -x_{i}\in T$ and we are done by letting $X = \{x_{k}\}_{k \in \mathbb{N}}$ 
Putting the two lemmas together, we have the final result:
Suppose $A-A$ was not syndetic, then there exists a thick set $T \subset (A-A)^{c}.$ By lemma $2$, there exists an infinite set $X$ such that $X-X \subset T.$ Then  $(X-X) \cap (A-A) = \emptyset.$ Choose $k > \frac{1}{d^{*}(A)}$ and consider $A-x_{i}$ for $i=1, \ldots, k.$ If these sets were all pairwise disjoint, then $d^{*}\left(\displaystyle \bigcup_{i=1}^{k}(A -x_{i})\right) = kd^{*}(A)>1$ a contradiction. So there must exist $i<j$ such that $(A-x_{i})\cap (A-x_{j}) \neq \emptyset$ or in other words, $x_{j} -x_{i} \in A-A$ which contradicts the fact that $(X-X) \cap (A-A) = \emptyset,$ finishing the proof.
