Notices
Results 1 to 12 of 12

Thread: Densities

  1. #1 Densities 
    Forum Sophomore
    Join Date
    Jul 2007
    Location
    South Africa
    Posts
    196
    :?

    What is the density of the following sets S_0 and S_1 in the natural numbers?

    S = {n element of Natural numbers | n = 0 (mod 3) and n/2 not = 0 (mod 3)}

    S_0 = {n element of S | 1/2(3n+1) is even}
    S_1 = {n element of S | 1/2(3n+1) is odd}

    What is the general way to compute it? Would it be strange if their densities are equal?


    It also matters what isn't there - Tao Te Ching interpreted.
    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    What do you mean when you write "n/2 not = 0 mod 3"? Presumably, you mean that the rational number n/2 is not 3 times an integer, which given that n is 3 time an integer, is equivalent to n/2 not being an integer. So you could say n is odd, or n = 3 mod 6. The density of this set is what you should expect it is: 1/6. To calculate this, note that for any N:

    [1,N] intersect S = {3, 9, ..., [(N-3)/6]*6+3}

    How many elements are in here? [(N-3)/6]+1, which is equal to (N-3)/6 + O(1), which when divided by N is (1-3/N)/6 + O(1/N), and as N goes to infinity, this is 1/6.

    Now let me just say that "n/2 not = 0 mod 3" may take on different meanings. Since 2 is invertible mod 3, and its inverse is itself, so you might interpret this as "n*2 not = 0 mod 3", and this is the same as "n not = 0 mod 3". Clearly, you don't mean this, but you have to be careful. Similarly, another common interpretation would be "n/2 not = 0 mod 3" means that the prime factorization of n/2 (as a rational number) has no 3 in it. And this, again, would be the same as "n not = 0 mod 3". You would have been better off saying "n is not even" or "2 does not divide n" or "n = 1 mod 2", because these are unambiguous.

    For S_0, if n is in S, S is 3 mod 6. We also want (3n+1)/2 even. Division by 2 here makes sense, as n is odd, so 3n is odd and 3n+1 is even. So (3n+1)/2 is even iff 3n+1 = 0 mod 4, which is the same as 3n = 3 mod 4, which is the same as n = 1 mod 4. Since we're already dealing with n = 3 mod 6, we see this gives us a congruence mod 12. If n = 1 mod 4, then n = 1, 5, or 9 mod 12. If n = 3 mod 6, then n = 3 or 9 mod 12. So n = 9 mod 12. Then calculating the density is easy.

    For S_1, the same sort of argument gives you n = 3 mod 12. You clearly get the same density for this as for S_0.


    Reply With Quote  
     

  4. #3  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Which version of density are you talking about here talanum1?
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  5. #4  
    Forum Sophomore
    Join Date
    Jul 2007
    Location
    South Africa
    Posts
    196


    The greatest lower bound of A(n)/n where A(n) is the amount of elements <= n version.

    serpicojr: I mean n/2 is an integer not devisable by 3, i.e n/2 is an integer congruent to 1 or 2 mod 3. Does this change your answer?

    Thanks anyway.
    It also matters what isn't there - Tao Te Ching interpreted.
    Reply With Quote  
     

  6. #5  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Okay, so you should have learned a lemma that says something like:

    Suppose a divides bc and gcd(a,b) = 1. Then a divides c.

    Applying this to our situation, you're asking for an integer n divisible by 2, i.e. n = 2m for another integer m. And then you're assuming that 2m = n = 0 mod 3. Well, then 3 divides 2m, and since gcd(2,3) = 1, we have 3 divides m, so that n/2 = m = 0 mod 3.

    So S is empty.
    Reply With Quote  
     

  7. #6  
    Forum Sophomore
    Join Date
    Jul 2007
    Location
    South Africa
    Posts
    196


    That's right. In fact your first guess was correct, I ment:

    S = {n element of natural numbers | n = 0 mod 3 and n odd}

    giving you n = 3 mod 6.
    It also matters what isn't there - Tao Te Ching interpreted.
    Reply With Quote  
     

  8. #7  
    Forum Ph.D.
    Join Date
    Apr 2008
    Posts
    956
    In other words, S is the set of all odd multiples of 3: S = {3,9,15,21,27,33,…}

    S<sub>0</sub> = {9,21,33,…}

    S<sub>1</sub> = {3,15,27,…}

    The elements of S<sub>0</sub> are of the form 9+12k while those of S<sub>1</sub> are of the form 3+12k (k a non-negative integer). Hence the natural density of both the sets is 1*⁄*12.
    Reply With Quote  
     

  9. #8  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    So let's note that, for any integers a >= 0 and q > 0, the density of the set (which I'd call an arithmetic progression):

    S = {qn+a: n a natural number}

    is always 1/q. First, we may assume a < q, as this only changes our set by a finite number of elements, and a finite number of elements has density 0. Now let S(N) be the elements of S less than or equal to N. Assume S(N) is nonempty, and divide N by q--i.e., find integers m and b such that N = qm+b, 0 =< b < q. Now if b < a, it's easy to see that the number of elements in S(N) is m. If b >= a, it's easy to see that the number of elements in S(N) is m+1. Note that:

    m = qm/q = (qm+b-b)/q = (N-b)/q = N/q - b/q

    Now whatever b/q is, it's a quantity between 0 and 1. Thus dividing by N, we get:

    1/q - b/qN

    and the quantity b/qN goes to 0 as N goes to infinity no matter which of the finite number of choices for b we take, so it goes to 0 unconditionally.
    Reply With Quote  
     

  10. #9  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    Exercise for today - what is the density of the primes
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  11. #10  
    Forum Sophomore
    Join Date
    Jul 2007
    Location
    South Africa
    Posts
    196


    About 0.131
    It also matters what isn't there - Tao Te Ching interpreted.
    Reply With Quote  
     

  12. #11  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Okay, so let's remember that:

    π(n) = #{primes p : p ≤ n} ~ n/ln(n)
    Reply With Quote  
     

  13. #12  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,497
    I'm trying to recall some rather interesting results from my side of the maths wood with regard to densities of sequences. I think the definition is different though, I will have to attack my paper collection again.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •