Help me find or prove an obvious (?) lemma

[CRGreathouse]

I was trying to prove something when I realized that it generalized fairly nicely. The basic idea is that if a subset contains 'almost all' of its superset (both sets inside N), and the superset has 'nice' growth, the ratio between the nth element of the two sets approaches 1 as a limit.

Here's an attempt to formalize:

Given $A\subseteq B\subseteq\mathbb{N}$, with
$$\lim_{n\to\infty}\frac{|A\cap\{1,2,\ldots,n\}|}{|B\cap\{1,2,\ldots,n\}|}=1$$
and
$$|B\cap\{1,2,\ldots,n\}|\sim n(\log n)^k$$ for some k (perhaps this can be weakened to remaining between k1 and k2)
it follows that
$$\lim_{n\to\infty}a_n/b_n=1$$
where a_i is the ith largest member of A and likewise for b_i.

1. Is this known? Does it have a name or a standard (textbook?) reference?
2. Failing #1, is there an easy proof for this?
3. Failing #2, is the result -- or something similar -- true?

 

[statdad]

I don't know a proof, or of a quick method of attack, but this does look familiar as a type of problem I saw in Number Theory many years ago. Look for a discussion of densities of sets of integers in those books - that may be a guide.
Keep checking back - I'm sure someone here, far more knowledgeable about this area than this poor statistician () , will soon offer some advice.

 

[DeadWolfe]

I don't see how a_1/b_1 depends on n.

 

[CRGreathouse]

I don't see how a_1/b_1 depends on n.

Sorry, that should be a_n/b_n.

The intuition here is that if A is almost all of B, their ratio shouldn't get too large if the sequence is well-behaved and grows slowly.

 

[CRGreathouse]

I don't know a proof, or of a quick method of attack, but this does look familiar as a type of problem I saw in Number Theory many years ago. Look for a discussion of densities of sets of integers in those books - that may be a guide.

Well, I'm still looking. It does seem a rather familiar result, though, just as you mention... I can't help but think I'm missing something glaringly obvious ('a simple reduction to foo, with a judicious application of Bar's Theorem, shows that this is true for |A| > N for some N...').

 

[CRGreathouse]

OK, so here goes.

The parent sequence is distributed so for any $\varepsilon>0$, the nth member $b_n$ is at most $k_\varepsilon n^{1+\varepsilon}.$ The subsequence $(a_i)_n$ is such that $f(m)$ that maps m to the unique n such that $a_m=b_n$ has
$$\lim_{m\to\infty}f(m)/m=1$$
or alternatively for every M there is a g(M) with
$$f(m)\le g(M)m$$ for all m > M.

Now I just need to show that g(M) needn't get too big, right?