Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help me find or prove an obvious (?) lemma

  1. Aug 27, 2008 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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 [itex]A\subseteq B\subseteq\mathbb{N}[/itex], with
    [tex]\lim_{n\to\infty}\frac{|A\cap\{1,2,\ldots,n\}|}{|B\cap\{1,2,\ldots,n\}|}=1[/tex]
    and
    [tex]|B\cap\{1,2,\ldots,n\}|\sim n(\log n)^k[/tex] for some k (perhaps this can be weakened to remaining between k1 and k2)
    it follows that
    [tex]\lim_{n\to\infty}a_n/b_n=1[/tex]
    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?
     
    Last edited: Aug 27, 2008
  2. jcsd
  3. Aug 27, 2008 #2

    statdad

    User Avatar
    Homework Helper

    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 (:smile:) , will soon offer some advice.
     
  4. Aug 27, 2008 #3
    I don't see how a_1/b_1 depends on n.
     
  5. Aug 27, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    :uhh:

    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.
     
  6. Aug 28, 2008 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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...').
     
  7. Aug 30, 2008 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    OK, so here goes.

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

    Now I just need to show that g(M) needn't get too big, right?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help me find or prove an obvious (?) lemma
Loading...