How much smaller is the set of ratios than the set of ordered pairs?

71 Views Asked by At

For integers $a, b$ with $0 < a < N$ and $0 < b < N$ for some integer $N$, let $\{(a, b)\}$ be the set of all their ordered pairs and let $\{\frac{a}{b}\}$ be the set of all their ratios.

Clearly, $|\{\frac{a}{b}\}| < |\{(a, b)\}|$ (the number of possible ratios is smaller than the number of possible ordered pairs), since for example $\frac{2}{1} = \frac{4}{2}$ but $(2, 1) \neq (4, 2)$.

My question is: how much smaller is $|\{\frac{a}{b}\}|$ than $|\{(a, b)\}|$, as $N \to \infty$?


Here's my approach so far: for any given $b$, we can determine how many $a$s get "eliminated." For example, if $b=2$, then $a=2, 4, 6, \ldots$ are all eliminated (because $\frac{2}{2}=\frac{1}{1}, \frac{4}{2}=\frac{2}{1}, \frac{6}{2}=\frac{3}{1}, \ldots$). So when $b=2$, $|\{\frac{a}{b}\}| = (1 - \frac{1}{2}) |\{(a, b)\}|$. The first few such ratios $r$ are:

$b = 1 \implies r = 1$

$b = 2 \implies r = \frac{1}{2}$

$b = 3 \implies r = \frac{1}{3}$

$b = 4 \implies r = \frac{1}{2}$

$b = 5 \implies r = \frac{1}{5}$

$b = 6 \implies r = \frac{1}{2} + \frac{1}{3} - \left(\frac{1}{2}\right) \left(\frac{1}{3}\right) = \frac{2}{3}$

$b = 7 \implies r = \frac{1}{7}$

In other words, we find the prime factors $p_1, p_2, \ldots$ of $b$ and that reduces $|\{\frac{a}{b}\}|$ by $\frac{1}{p_1} + \frac{1}{p_2} + \ldots - \left(\frac{1}{p_1}\right) \left(\frac{1}{p_2}\right) - \ldots$

So, we want to know the average $r$ for all $b$ (as $b \to \infty$). Does this help us?

1

There are 1 best solutions below

2
On BEST ANSWER

I will use inclusive bounds, so $1 \leq a, b \leq n$.

$|\{\frac{a}{b}\}|$ is the number of coprime pairs $1 \leq a, b \leq n$. This is OEIS sequence A018805. For large $n$ it's noted that we have $\text{A018805(n)} \approx \dfrac{6}{\pi^2} n^2$.

$|\{a, b\}|$ is the number of pairs $1 \leq a, b \leq n$. This is simply $n^2$.

So their asymptotic density is the fraction of these two, giving simply $\dfrac{6}{\pi^2} \approx 0.60793$.