# Basic question about natural density

Suppose that we have a sequence of finite sets $A_1, A_2, \ldots$, which partition $\mathbb{N}$. I am making no other assumptions on the $A_n$ - i.e. there could be any amount of interleaving between them. Now suppose we have $S\subset\mathbb{N}$. If $\lim_{n\rightarrow\infty} \frac{|S\cap A_n|}{|A_n|}=0$, does it follow that $S$ has a natural density of 0?

(And if so, while I'm at it, can 0 be replaced by other numbers? Natural density be replaced by upper, lower density? I mostly just care about the density 0 (equivalently density 1) case, though.)

EDIT: And if the statement is false, is there some sufficiently-little-interleaving condition on the $A_n$ I could assume that would make it true?

-
"Partition" generally implies that the sets are disjoint; I would use "cover." – Qiaochu Yuan Mar 16 '11 at 1:22
No, I did want them to be disjoint. I suppose that might not be necessary; I hadn't considered that. By interleaving I mean, e.g., $A_1$ contains 1 and 3 but not 2. – Harry Altman Mar 16 '11 at 1:41

Fix an increasing sequence of positive integers $(k(n))_n$ and let $A_n=[k(n),k(n+1))$.

Fix a sequence of positive integers $(\ell(n))_n$ such that $\ell(n)\le k(n+1)-k(n)$ for every $n$ and define $S$ as the union of the intervals $[k(n),k(n)+\ell(n))$.

Assume that $\ell(n)\ll k(n+1)-k(n)$. Then $|S\cap A_n|\ll|A_n|$ hence your hypothesis is met.

Assume furthermore that $\ell(n)\ge uk(n)$ for a given positive $u$, for every $n$. Then, for every $N=k(n)+\ell(n)$, $$\frac1N|S\cap\{1,2,\ldots,N\}|\ge\frac{\ell(n)}{k(n)+\ell(n)}\ge\frac{u}{1+u}$$ hence the natural density of $S$ cannot be $0$ and your conclusion does not hold.

Every condition above on the sequences $(k(n))$ and $(\ell(n))$ is met if, for example, $k(n)=2^{n^2}$ and $\ell(n)=2^{n^2+n}$.

In this specific example, the sequence of densities of general term $N^{-1}|S\cap\{1,2,\ldots,N\}|$ converges to $0$ when restricted to the integers $N=k(n)$ and converges to $1$ when restricted to the integers $N=k(n)+\ell(n)$, hence the set of limit points of the whole sequence of densities is the interval $[0,1]$.

-
A good construction. A bit simpler: let $S=\{k(n)|n \in \mathbb{N}\}$ Your argument goes through with no talk of $l(n)$. This just sets $l(n)=1$ – Ross Millikan Mar 16 '11 at 2:17
I don't follow why $l/(k+l)\ge u/(1+u)$ in general (the inequality goes the right way in the numerator but not the denominator), but in any case the example you give clearly works since there we have equality. I guess no-interleaving was a red herring. Upvoted, but I hope you don't mind if I edit the question once more to impose additional restrictions? :) (Well, after I think about it some more, to see whether I can modify your counterexample to be even worse. :) ) – Harry Altman Mar 16 '11 at 3:09
I guess I should really just accept this since it answers the question I asked, and just ask a new question if I want to add additional restrictions. – Harry Altman Mar 16 '11 at 3:20
@Ross If $\ell(n)=1$ for every $n$ and $k(n+1)-k(n)\gg1$, the density does exist and it is $0$, so that would not be a counterexample. – Did Mar 16 '11 at 6:34
@Harry We do not have equality but, every function $\varphi_k:x\mapsto x/(k+x)$ being increasing (at least on $x\ge0$), $\ell\ge uk$ implies $\varphi_k(\ell)\ge\varphi_k(uk)=u/(1+u)$. – Did Mar 16 '11 at 6:37

This is false. Let $S$ be any infinite coinfinite subset of $\mathbb{N}$, and let $A_n$ contain $1$ element of $S$ and $n$ elements of $\mathbb{N} \setminus S$ (it's clear we can always find such a partition, for example by recursively letting $A_n$ contain the smallest suitable numbers not already in $A_i$ for some $i < n$). Then $\lim_{n \to \infty} \frac{|S \cap A_n|}{|A_n|}=\lim_{n \to \infty} \frac{1}{n+1}=0$, but the density of $S$ can be anything in $[0,1]$, or not exist at all.

In other words: your condition on $S$ and the $A_n$s makes no use of the order structure on $\mathbb{N}$, and just treats $\mathbb{N}$ as an unstructured set. It thus can't imply anything about $S$ that isn't already implied by its cardinality and cocardinality.

-
Wow, I really didn't do enough searching for counterexamples. Not accepting an answer yet as I'd like to see if anyone has a sufficiently-little-interleaving condition that will work. – Harry Altman Mar 16 '11 at 1:45
@Harry: Didier Piau has shown that "no interleaving at all" is not enough. – Chris Eagle Mar 16 '11 at 1:49
I like that you show that every infinite coinfinite $S$ works for a suitable sequence $(A_n)$. Instead of searching for a nice $S$ once $(A_n)$ is given, you do it the other way round. Neat. – Did Mar 16 '11 at 9:29