GTM 259 Exercise 2.2.2. $ \mathbf d(A)=\lim_{k\to\infty}\frac{1}{k}|A\cap [1,k]| $ exists and is positive

Question

(GTM 259 Exercise 2.2.2.)(a) Use Exercise 2.2.1 to show the following. If $A\subset\mathbb N$ has positive density, meaning that $$ \mathbf d(A)=\lim_{k\to\infty}\frac{1}{k}|A\cap [1,k]| $$ exists and is positive, prove that there is some $n\ge 1$ with $\overline{\mathbf d}(A\cap (A-n))>0$ (here $A-n=\{a-n\colon a\in A\}$), where $$ \overline{\mathbf{d}}(B)=\limsup_{k\to\infty}\frac 1k|B\cap[1,k]|. $$

(b) Can you prove this starting with the weaker assumption that the upper density $\overline{\mathbf{d}}(A)$ is positive, and reaching the same conclusion?

---

My attempt:

(a) follows directly from Exercise 2.2.1. by checking $\mathbf d(\cdot)$ is a probability measure on $2^{\mathbb N}$. In fact, we get the stronger $\mathbf{d}(A\cap(A-n))>0$ instead of the upper density.

For the sake of completeness, let me also quote Exercise 2.2.1 and its proof which is really simple:

Let $(X,\mathscr B,\mu,T)$ be a measure-preserving system with $\mu$ only assumed to be a finitely additive measure, and let $A\in\mathscr B$ have $\mu(A)>0$. Show that there is some positive $n\le\frac{1}{\mu(A)}$ for which $\mu(A\cap T^{-n}A)>0$.

Sketch of proof:

Argue by contradiction, considering the sequence $$A,T^{-1}A,...,T^{-\lfloor\frac{1}{\mu(A)}\rfloor}(A)$$ and we are done.

(b) The interesting thing is that we cannot prove $\overline{\mathbf d}(\cdot)$ is a probability measure. Hence our reasoning fails here. So how to save the proof?

Answer 1

Lemma: For every $\delta > 0$, there is some $\epsilon > 0$ so that for all large $N$ and any $A \subseteq [N]$ with $|A| \ge \delta N$, there is some $1 \le n \le \frac{2}{\delta}$ with $|A\cap (A-n)| \ge \epsilon N$.

Proof: We may assume $1/\delta \in \mathbb{N}$. Then, $N \ge |\cup_{n=0}^{2/\delta} (A-n)| \ge \frac{2}{\delta}\delta N-\sum_{0 \le i < j \le 2/\delta} |(A-i)\cap (A-j)|$. So, by pigeonhole, there are $0 \le i < j \le 2/\delta$ with $|(A-i)\cap (A-j)| \ge \frac{N}{(2/\delta)^2}$. Noting that $(A-i)\cap (A-j) = A\cap (A-(j-i))$, we see that $\epsilon := \frac{\delta^2}{4}$ works. $\square$

.

Corollary: If $A \subseteq \mathbb{N}$ has positive upper density, then there is some $n \ge 1$ so that $A\cap (A-n)$ has positive upper density.

Proof: Take $\delta > 0$ and $N_1 < N_2 < \dots$ so that $|A_k| \ge \delta N_k$ for each $k$, where $A_k := A\cap [N_k]$. The lemma gives an $\epsilon > 0$ and for each large $k$, an $n \in [1,\frac{2}{\delta}]$ with $|A_k\cap (A_k-n)| \ge \epsilon N_k$. By pigeonhole, there is some $n \in [1,\frac{2}{\delta}]$ so that $|(A\cap (A-n))\cap [N_k]| = |A_k \cap (A_k-n)| \ge \epsilon N_k$ for infinitely many $k$. This implies the upper density of $A\cap (A-n)$ is at least $\epsilon$ and thus positive. $\square$