Most discussion I have found regarding the size of the set of rational numbers is regarding the
theoretical issues raised by countability, the continuum hypothesis, and so forth. However,
it seems to me that there is an important practical result to be considered here, which is the
approximate number of rational numbers expressible using a set of constituent positive integers
of size n, as n grows large. Surely this has been estimated algebraically and numerically long ago?
Basically, it seems to me we should be able to write down the ratio in terms of the number of
unique powers of primes less than n, then take the limit as n-> infinity. Boom, that's how many
rationals there are, kinda. At least we could bound the value based on certain assumptions
about the distributions of primes, right?
The continuation below shows the basic algebraic approach I'm looking for references to.
Yeah, I've studied a bit of abstract algebra, but I'd rather not have
to learn every hypothesis referenced here in order to answer the question, yo?
Hopefully a better informed cyberpal will just post the answer and a link in a comment.
A lot to hope for, yes, but then I've been learning that if you don't ask, you don't get!
If the answer is, nope, nobody's tried this, I'll be surprised, but I'll
go ahead and do a little simulation. I ain't no mathematica wonk, though.
Help a brutha out!
----
Update
Victor from the NMBRTHRY list pointed me to the Farey Sequence.
Apparently the number of rationals grows as 3/(pi^2) * n^2.
Now to ponder this result...
Consider a positive integer n. Let the set of positive integers less than or equal to n be I(n).
The square S(n) is the set of ordered pairs (i,j) drawn from I(n), representing
all the proper and improper fractions expressible using I(n): f(i,j) = i / j, where 1<= i,j <= n
The size of S(n) is n^2.
Let r(n) be the number of unique rational fractions in S(n).
Then, for starters, we know that r(n) is somewhere between n and n^2.
But surely we can assign tighter bounds without much work!
The number of equal fractions in S(n) for f(i,j) is the degeneracy d(n,i,j).
d(n,i,j) is the size of the equivalence class EC(n,f(i,j)) within S(n).
One of these values will be the proper reduced fraction, while the other values will be duplicate,
improper fractions.
But what we are really interested in is r(n), which is the the
number of equivalence classes EC at n.
Now, let p(n) be the size of P(n), the positive primes less than or equal to n.
Also let pp(n) is the size of PP(n), the integer powers of P(n) which are less than n. Intuitively,
it seems to me that when pp(n) grows quickly, then r(n) should grow quickly.
So,I think we should be able to write down r(n) as a function of some algebriac structures related
to PP(n), perhaps by way of the d(n,i,j). That is, r(n) should be boundable
using some functions of n dependent on our theoretical and experimental knowledge about primes.
It would be interesting, to me at least, to see how the bounds of r(n) can be tightened if the
Riemann Hypothesis holds. This would represent an example quantitative measure of progress
in a visualizable piece of knowledge about numbers as a result of an abstract theoretical advance.
I can see the estimates of r(n) being usefully expressed in several ways:
- as the simplest possible function of n
- as a ratio to size of I(n), i.e. r(n)/n
- as a ratio to size of S(n), i.e. r(n)/n^2
- as a real logarithmic value c(n) such that r(n) = n^c(n). Obviously 1 < c(n) < 2.
Update
From the wikipedia article on Farey Sequences, we now know that
r(n) ~ 3/pi^2 * n^2 = .30396 * n^2
So, we can crudely say the unique rationals are "about 30% dense" in S(n).
Comments