Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
"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
up vote 6 down vote accepted

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]$.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.