In introductory elementary theory courses there’s footnotes of all these theorems like this guy proved the number of primes less than n is less than ln(1000n)lnlnlnln(ln2)/sin(ln(n)) or whatever. But the actual courses don’t really have logarithms.
How do they relate primes or whatever else with logarithms? I mean, I know of logarithms as inverses of exponentiation. I don’t see how primes and such relate to exponential growth or its inverse. I hope my question is clear enough. For example, if it were trig functions, I’d look for how they relate to a circle. With logarithms, I’m not even sure if the inverse of exponentiation train of thought is even correct.
In: Mathematics
One way log pops up is because it is the antiderivative of 1/x. For example the discretized version is **the harmonic sum 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n which is about the same as the area under the curve 1/x from 1 to n, which in turn is ln(n)**, the natural logarithm of n.
Then **the sum of reciprocal primes 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + … + 1/p is roughly ln(ln(p))**:
The _infinite harmonic series_ 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … “factors” into the product of
– 1 + 1/2 + 1/4 + 1/8 + 1/16 + …
– 1 + 1/3 + 1/9 + 1/27 + 1/81 + …
– 1 + 1/5 + 1/25 + 1/125 + 1/625 + …
– 1 + 1/7 + 1/49 + 1/343 + …
– 1 + 1/11 + 1/121 + …
– …
Try to see what happens if you multiple all those lines together and expand: unique prime factorization means that each 1/n appears exactly once!
But then 1 + 1/p + 1/p² + 1/p³ + … is a _geometric series_ with value 1/(1 – 1/p). So we find the weird equality
1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … = 1 / [(1 – 1/2)·(1 – 1/3)·(1 – 1/5)·(1 – 1/7)·(1 – 1/11)· … ]
and taking logarithms and using that ln(1-x) ~ -x we finally arrive at
ln( 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … ) ~ 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + …
If done carefully and correctly one then finds that the left side grows like ln(ln(n)) as seen at the beginning and thus so does the sum of reciprocal primes. If continued even much more carefully and with further arguments this leads to the proofs of two very important results from analytic number theory:
– The **Prime Number Theorem**: there are ~ n/ln(n) primes up to n.
– **Dirichlet’s Theorem on primes in arithmetic progressions**: if a and n are coprime positive integers, then there are infinitely many primes in the sequence a, a+n, a+2n, a+3n, a+4n, … (and for each possible choice for a we get approximately the same amount of primes).
Latest Answers