Results 1 to 5 of 5

Math Help - ratio of rational numbers to natural pairs

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    16

    ratio of rational numbers to natural pairs

    Cantor proved the enumerability of rational numbers by creating a chart like the one below

    the order crated by the zig-zag allowed the rational number to be put into one to one corespondence with natural numbers, but there are some repeats, which will be skipped.

    Figuring that the reducable fractions should be eliminated, I wrote a program in java that counted the nonreduceable fractions and divided this number by the total number of numerator/denominator pairs. It can easily be seen that three down and three across on the chart has 7 out of nine nonreducable fractions. 4 has 11 out of 16. I ran the program for 100,000 down and across, came back a half hour later and got a number very close to the reciprical of phi, the golden number.

    Does the ratio of nonreducable fractions to numerator pairs really approach this number? How can this be varified?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    The denominator is simple, just n^2.

    The numerator is: \sum_{k=1}^n \phi(k)\cdot \left[ \frac{n}{k} \right] + a(n,k).

    Where [ ] is the greatest integer function.
    And a(n,k) is the number of integers in the interval [1,n*mod(k)] relatively prime to k.

    The problem with this formula is that it is not pleasant to use in an limit. Another problem is a(n,k). Thus, my idea is going to produce is good lower bound and upper bound for this sum. The first bound to try is to use the fact that 1<=a(n,k)<=(k-1). But I am not sure if this is a good approximation. Another approximation is on phi(k) which can be found here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    There is a famous theorem to the effect that the probability that two integers chosen at random will be relatively prime is 6 / pi^2 , approximately 0.6079, which is close to 1 / phi, approximately 0.6180. So I suspect the first of these numbers is the limit you seek.

    One source of the 6 / pi^2 theorem is "Introduction to Analytic Number Theory", Apostol. There may be a proof on-line somewhere, I haven't looked.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by kd8bxz View Post
    Does the ratio of nonreducable fractions to numerator pairs really approach this number? How can this be varified?
    For example consider the set S_n={1, 2, ..., n} and all the fractions in[0,1] you can form with those numbers, these are n(n+1)/2 (the n-th triangular number)

    Now the number of nonreductable fractions is \sum_{k=1}^n{\phi(k)}

    Since for every denominator k in S_n= we have \phi(k) nonreductable fractions.

    As n tends to infinity, the ratio tends to \frac{6}{\pi^2}

    Similarly, if you consider all the fractions you can form with the numbers in the set S_n, these are nē, the numerator is 2\sum_{k=1}^n{\phi(k)}-1 (see your chart and you'll instantly realise why).This ratio is exactly the probability of picking randomly a pair of coprime numbers among the first n naturals. It again tends to \frac{6}{\pi^2} as n tends to infinity

    Now if you consider that zigzag is not so easy to work with, say the numerator is equal to \sum_{k=1}^{n}{\sum_{1\leq{s}\leq{n-k+1}; (s, k)=1}1} , after passing through exactly n diagonals (in your chart), the denominator is the n-th triangular number.
    Last edited by PaulRS; July 30th 2008 at 04:19 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    I'll show that <br />
\sum\limits_{k = 1}^n {\phi \left( k \right)}  \sim \tfrac{3}<br />
{{\pi ^2 }} \cdot n^2 <br />
to calculate the limit of the ratio considering the square ( also see here remember that a fraction is nonreduceable iff the numerator and denominator are coprime)

    Lemma 1 Let f(n) and g(n) be two arithmetic functions then <br />
\sum\limits_{k = 1}^n {\left( {\sum\limits_{\left. d \right|k} {f\left( d \right) \cdot g\left( {\tfrac{k}<br />
{d}} \right)} } \right) \cdot x^k }  = \sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } {f\left( k \right) \cdot g\left( j \right) \cdot x^{k \cdot j} } } <br />

    Proof
    Note that, since <br />
1 \leqslant \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  \leqslant \tfrac{n}<br />
{k}<br />
then <br />
1 \leqslant k \cdot j \leqslant n<br />
and in fact it goes through all the possible pairs (k, j) such that <br />
1 \leqslant k \cdot j \leqslant n<br />

    Thus we may rewrite it as follows: <br />
\sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } {f\left( k \right) \cdot g\left( j \right) \cdot x^{k \cdot j} } }  = \sum\limits_{k = 1}^n {\left( {\sum\limits_{d \cdot d' = k} {f\left( d \right) \cdot g\left( {d'} \right)} } \right) \cdot x^k } <br />
and now <br />
\sum\limits_{d \cdot d' = k} {f\left( d \right) \cdot g\left( {d'} \right)}  = \sum\limits_{\left. d \right|k} {f\left( d \right) \cdot g\left( {\tfrac{k}<br />
{d}} \right)} \blacksquare

    Lemma 2 <br />
\phi \left( n \right) = n \cdot \sum\limits_{\left. d \right|n} {\tfrac{{\mu \left( d \right)}}<br />
{d}} <br />

    Proof
    Recall the formula <br />
\phi \left( n \right) = n \cdot \prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}<br />
{p}} \right)} <br />
(p means prime)

    Expanding the product: <br />
\prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}<br />
{p}} \right)}  = 1 - \sum\limits_{\left. p \right|n} {\tfrac{1}<br />
{p}}  + \sum\limits_{\left. {\left( {pq} \right)} \right|n;q{\text{ prime}}} {\tfrac{1}<br />
{{pq}}}  \mp ...<br />

    Recalling the definition of \mu we find that: <br />
\prod\limits_{\left. p \right|n} {\left( {1 - \tfrac{1}<br />
{p}} \right)}  = \sum\limits_{\left. d \right|n} {\tfrac{{\mu \left( d \right)}}<br />
{d}} \blacksquare <br />

    Proof:

    Set: <br />
\left\{ \begin{gathered}<br />
  f\left( k \right) = \mu \left( k \right) \hfill \\<br />
  g\left( k \right) = k\hfill \\<br />
  x = 1 \hfill \\ <br />
\end{gathered}  \right.<br />
in Lemma 1 : <br />
\sum\limits_{k = 1}^n {\left( {\sum\limits_{\left. d \right|k} {\mu \left( d \right) \cdot \left( {\tfrac{k}<br />
{d}} \right)} } \right)}  = \sum\limits_{k = 1}^n {\left( {\mu \left( k \right) \cdot \sum\nolimits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } j } \right)} <br />

    By Lemma 2: <br />
\sum\limits_{\left. d \right|k} {\mu \left( d \right) \cdot \left( {\tfrac{k}<br />
{d}} \right)}  = \phi \left( k \right)<br />
thus: <br />
\sum\limits_{k = 1}^n {\phi \left( k \right)}  = \sum\limits_{k = 1}^n {\left( {\mu \left( k \right) \cdot \sum\nolimits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } j } \right)} <br />

    We also have: <br />
\sum\nolimits_{j = 1}^{\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } j  = \tfrac{1}<br />
{2} \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  \cdot \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1} \right)<br />
then <br />
\sum\limits_{k = 1}^n {\phi \left( k \right)}  = \tfrac{1}<br />
{2} \cdot \sum\limits_{k = 1}^n {\left[ {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  \cdot \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1} \right)} \right]}

    Now: <br />
\sum\limits_{k = 1}^n {\left[ {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  \cdot \left( {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1} \right)} \right]}  = \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2 }  + \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor } <br />

    BUt: <br />
\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }  = 1<br />
(set <br />
\left\{ \begin{gathered}<br />
  f\left( n \right) = \mu \left( n \right) \hfill \\<br />
  g\left( n \right) = 1 \hfill \\<br />
  x = 1 \hfill \\ <br />
\end{gathered}  \right.<br />
in Lemma 1 and remember that <br />
\sum\limits_{\left. d \right|n} {\mu \left( d \right)}  = \left\lfloor {\tfrac{1}<br />
{n}} \right\rfloor <br />
)

    By definition: <br />
\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  \leqslant \tfrac{n}<br />
{k} < \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1 \Rightarrow \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  \leqslant \left( {\tfrac{n}<br />
{k}} \right)^2  < \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  + 2 \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1<br />
Thus: <br />
 \left| {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  - \left( {\tfrac{n}<br />
{k}} \right)^2 } \right| \leqslant 2 \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1<br />
and <br />
 \left| {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  - \mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 } \right| \leqslant 2 \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor  + 1<br />
(1)

    By the triangular inequality <br />
\left| {\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  - } \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 } } \right| \leqslant \sum\limits_{k = 1}^n {\left| {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  - \mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 } \right|} <br />
from where, applying (1), we get: <br />
\left| {\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  - } \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 } } \right| \leqslant 2 \cdot \sum\limits_{k = 1}^n {\left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor }  + n \leqslant 2 \cdot \sum\limits_{k = 1}^n {\tfrac{n}<br />
{k}}  + n<br />
remember that: <br />
\sum\limits_{k = 1}^n {\tfrac{1}<br />
{k}} \leq \ln(n+1)+1<br />
thus: <br />
\left| {\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2  - } \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 } } \right| \leqslant n \cdot \left[ {2 \cdot \ln \left( {n + 1} \right) + 3} \right]<br />

    So we get: <br />
\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}<br />
{k}} \right\rfloor ^2 }  = \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 }  + O\left[ {n \cdot \ln \left( n \right)} \right]<br />
and: <br />
\sum\limits_{k = 1}^n {\phi \left( k \right)}  =\tfrac{1}{2}\cdot\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left( {\tfrac{n}<br />
{k}} \right)^2 }  + O\left[ {n \cdot \ln \left( n \right)} \right]<br />

    Now recall the Dirichlet Series: <br />
\sum\limits_{k = 1}^\infty  {\tfrac{{\mu \left( k \right)}}<br />
{{k^s }}}  = \tfrac{1}<br />
{{\zeta \left( s \right)}} \Rightarrow \sum\limits_{k = 1}^\infty  {\tfrac{{\mu \left( k \right)}}<br />
{{k^2 }}}  = \tfrac{6}<br />
{{\pi ^2 }}<br />
therefore: <br />
\mathop {\lim }\limits_{n \to  + \infty } \tfrac{1}<br />
{{n^2 }} \cdot \sum\limits_{k = 1}^n {\phi \left( k \right)}  = \tfrac{1}<br />
{2} \cdot \sum\limits_{k = 1}^\infty  {\tfrac{{\mu \left( k \right)}}<br />
{{k^2 }}}  = \tfrac{3}<br />
{{\pi ^2 }}\blacksquare <br />

    Observation: Now remember that if you take a square of side n in the chart, our ratio is: <br />
r_n  = \tfrac{\left({2 \cdot \sum\limits_{k = 1}^n {\phi \left( k \right)} }\right)-1}<br />
{{n^2 }}<br />
so taking the limit: <br />
r_{ + \infty }  = \tfrac{6}<br />
{{\pi ^2 }}<br />
    Last edited by PaulRS; July 30th 2008 at 04:45 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complex numbers-finding real number pairs
    Posted in the Calculus Forum
    Replies: 9
    Last Post: March 20th 2010, 10:36 PM
  2. Choosing pairs of numbers with a sum-bound
    Posted in the Statistics Forum
    Replies: 1
    Last Post: January 25th 2010, 09:15 AM
  3. Replies: 5
    Last Post: January 16th 2010, 11:48 AM
  4. Do sets of all pairs of real numbers form fields?
    Posted in the Advanced Algebra Forum
    Replies: 20
    Last Post: January 6th 2010, 07:37 PM
  5. pairs of numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 1st 2007, 12:48 PM

Search Tags


/mathhelpforum @mathhelpforum