# Use Poincare Recurrence to show existence of $n$

Suppose $A\subset \mathbb N$ such that $d(A)=\lim_{n\to\infty}\dfrac{|A\cap [1,n]|}{n}>0$. Then show there exists $n\in\mathbb N$ such that $\overline{d}(A\cap (A-n))>0$ where $\overline{d}(B)=\limsup_{k\to\infty}\dfrac{|B\cap[1,k]|}{k}$. Can we achieve the same conclusion assuming $\overline{d}(A)>0$?

I know that for a finite measure preserving system, if $\mu(E)>0$ then there exists $n\in\mathbb N$ such that $\mu(A\cap T^{-n}A)>0$ and this is basically Poincare recurrence.

Here, what should my measure be? Note that I can do with finitely additive measure in Poincare recurrence. Here I am tempted to say that $\mu(A)=d(A)$ but the limit may not exist for all $A$. I understand the transformation will be $T:\mathbb N\to\mathbb N$ such that $T(n)=n+1$. Then $T^{-n}A=A-n$ so we need a proper measure.

Short Answer: Yes, you can just take $\mu=d$. That is, $\mu:D\to[0,1]$, where $D$ is the algebra of sets $A$ such that $d(A)$ exists. The fact that not every set is in $D$ doesn't matter; $A\in D$ does imply $A-1\in D$. Comments below...

Given a sequence $a=(a_n)$, define the mean value $$Ma=\lim_{n\to\infty}\frac1n\sum_{j=1}^na_j,$$if the limit exists.

Define $a_n=1$ if $n\in A$, $0$ if $n\notin A$. Then $$Ma=d(A)>0.$$ Choose $N$ so $(N+1)Ma>1$, and set $$b_n=a_n+a_{n+1}+\dots+a_{n+N}.$$ Then $$Mb=(N+1)Ma>1.$$

If we had $\overline d(A\cap(A-n))=0$ for all $n$ it would follow that $b_n\le 1$ for $n$ in a set of density $1$; since $b_n$ is bounded this would imply $Mb\le 1$. QED

The argument fails assuming just $\overline d(A)>0$, because if we define $\overline M$ in the obvious way then $\overline M$ is not additive. I'm pretty sure the result is still true, with a proof along the same lines; two sequences $a$ and $b$ with $\overline M(a+b)\ne \overline Ma+\overline Mb$ have to be sort of more independent than the $a$ and $b$ above.

[...]

Yes, it's true assuming just $\overline d(A)>0$. Choose a sequence $n_j\to\infty$ so that $$\lim_{j\to\infty}\frac{|A\cap[1,n_j]|}{n_j}=\overline d(A).$$Now define a mean $L$ adapted to this sequence $n_j$: $$Lc=\lim_{j\to\infty}\frac1{n_j}\sum_{k=1}^{n_j}c_k.$$Then $L$ is additive, and $L$ is also translation-invariant, at least for bounded sequences. Repeat the argument above.

Comments: When I saw the result you were trying to prove a solution seemed obvious; hence the original answer. Come to think of it, the original answer doesn't really answer your question, which was to prove this using Poincare recurrence. That's very simple.

All that's really going on in this:

Lemma Suppose $D$ is an algebra of subsets of $X$, $\mu$ is a finitely additive measure on $D$, $A_1,\dots,A_n\in D$ and $\sum_{j=1}^n\mu(A_j)>\mu(X)$. Then there exist $j,k$ with $j\ne k$ such that $\mu(A_j\cap A_k)>0$.

One can prove this using the "integral", as above. Or come to think of it it's trivial just from the fact that we have a finitely additive measure: If $\mu(A_j\cap A_k)=0$ for all $j\ne k$ then additivity shows that $\mu(\bigcup A_j)>\mu(X)$, contradiction.

(Although it wasn't needed here, my comment about integrals being useful in studying measures stands. Suppose for example we wanted to show that if $\sum\mu(A_j)>2\mu(X)$ then some three of the $A_j$ intersect in a set of positive measure...)

Say $T:X\to X$ is measurable if $T^{-1}(A)\in D$ for every $A\in D$. The result you're calling Poincare recurrence follows easily:

Cor Suppose $D$ is an algebra of subsets of $X$ and $\mu$ is a finitely additive measure on $D$ with $\mu(X)<\infty$. Suppose $T:X\to X$ is measurable and measure-preserving. If $A\in D$ and $\mu(A)>0$ there exists $n\ge 1$ with $\mu(A\cap T^{-n}(A))>0$.

If on the other hand $\mu(A\cap T^{-n}A)=0$ for every $n\ge0$ then it's easy to see that $\mu(T^{-n}(A)\cap T^{-m}(A))=0$ for all $n\ne m$; hence the corollary follows from the lemma.

And the result you ask about really is a special case. If $D$ is the algebra of $A\subset\Bbb N$ such that $d(A)$ exists, $\mu=d$ and $T(n)=n+1$ then $\mu$ is a finitely additive measure on $D$ and $T$ is measurable and measure-preserving, QED.

• May I know the motivation behind this solution? – Landon Carter Jul 2 '16 at 14:19
• @LandonCarter Integrals are useful in studying measures. (Not that we're actually talking about an integral or a measure here, quite...) – David C. Ullrich Jul 2 '16 at 14:23
• @LandonCarter Got the second half - yes, it's really the same as the first. – David C. Ullrich Jul 2 '16 at 14:44
• Maybe in the definition of $Ma,$ one should divide by $n?$ – awllower Jul 2 '16 at 14:45
• @awllower Eewps! Yes of course that's what I meant, thanks. – David C. Ullrich Jul 2 '16 at 14:46