Skip to main content
1 of 2
Anthony Quas
  • 23.2k
  • 5
  • 63
  • 98

OK. So now I understand the question (I think). And the answer is yes.

I think it is helpful to introduce the upper Banach density, $d^*(S)=\lim_{n\to\infty}\sup_{|I|\ge n}|S\cap I|/|I|$, where $I$ runs over intervals in $\mathbb N$. Clearly $d^*(S)$ is at least as large as the upper density.

Let $S$ be a set with positive upper density. Let $a=d^*(S)$. Let $\epsilon>0$ and let $4\eta/(a+\eta)<\epsilon$. By definition of $d^*(S)$, there exists an $N$ such that $|S\cap I|\le (a+\eta)|I|$ for any $I$ with $|I|\ge N$. Now fix any $M>0$. Again by definition of $d^*(S)$, there exists an interval $J$ of length at least $M$ such that $|S\cap J|\ge (a-\eta)|J|$. We may suppose without loss of generality that $|J|$ is a multiple of $N$. Let $L=2N$. Divide $J$ into sub-intervals of length $N$ (call these grid sub-intervals) and consider those which do not intersect $S$. Suppose there are $k$ of these. On the other $|J|/N-k$ intervals, we have $|S\cap I|\le (a+\eta)N$, so that $|S\cap J|\le (|J|/N-k)(a+\eta)N$. Combining the two inequalities gives $$ (a-\eta)|J|\le (|J|/N-k)(a+\eta)N. $$ Rearranging gives $Nk\le \epsilon|J|/2$. However each interval $[a_i,a_{i+1}]$ forming $J_L$ must contain grid sub-intervals whose total length is at least $(a_{i+1}-a_i)/2$. In particular, $|J_L|$ is at most twice the total length of the empty grid sub-intervals, that is $Nk$. Hence $|J_L|\le \epsilon|J|$.

By the way, I should say a little about how I arrived at this answer. First, I think what you are trying to prove is the equivalent to $d^*(A+\{1,\ldots,L\})\to 1$ as $N\to\infty$. In fact, the slightly more general result is $d^*(A)>0$ implies $d^*(A+\{1,\ldots,L\})\to 1$. My first proof of this went through the Furstenberg correspondence, where the result translates to a well known fact in ergodic theory: if $T$ is an ergodic probability measure-preserving transformation and $B$ is any set of positive measure, then $\mu(\bigcup_{n=1}^N B)\to 1$ as $N\to\infty$. I then tried to give an elementary proof of the same thing.

Anthony Quas
  • 23.2k
  • 5
  • 63
  • 98