# Math Help - ratio of rational numbers to natural pairs

1. ## 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?

2. 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.

3. 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.

4. Originally Posted by kd8bxz
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.

5. I'll show that $
\sum\limits_{k = 1}^n {\phi \left( k \right)} \sim \tfrac{3}
{{\pi ^2 }} \cdot n^2
$
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 $
\sum\limits_{k = 1}^n {\left( {\sum\limits_{\left. d \right|k} {f\left( d \right) \cdot g\left( {\tfrac{k}
{d}} \right)} } \right) \cdot x^k } = \sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}
{k}} \right\rfloor } {f\left( k \right) \cdot g\left( j \right) \cdot x^{k \cdot j} } }
$

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

Thus we may rewrite it as follows: $
\sum\limits_{k = 1}^n {\sum\limits_{j = 1}^{\left\lfloor {\tfrac{n}
{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 }
$
and now $
\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}
{d}} \right)} \blacksquare$

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

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

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

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

Proof:

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

By Lemma 2: $
\sum\limits_{\left. d \right|k} {\mu \left( d \right) \cdot \left( {\tfrac{k}
{d}} \right)} = \phi \left( k \right)
$
thus: $
\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}
{k}} \right\rfloor } j } \right)}
$

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

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

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

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

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

So we get: $
\sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left\lfloor {\tfrac{n}
{k}} \right\rfloor ^2 } = \sum\limits_{k = 1}^n {\mu \left( k \right) \cdot \left( {\tfrac{n}
{k}} \right)^2 } + O\left[ {n \cdot \ln \left( n \right)} \right]
$
and: $
\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}
{k}} \right)^2 } + O\left[ {n \cdot \ln \left( n \right)} \right]
$

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

Observation: Now remember that if you take a square of side n in the chart, our ratio is: $
r_n = \tfrac{\left({2 \cdot \sum\limits_{k = 1}^n {\phi \left( k \right)} }\right)-1}
{{n^2 }}
$
so taking the limit: $
r_{ + \infty } = \tfrac{6}
{{\pi ^2 }}
$