## Posts Tagged ‘maths’

### The Prime Number Theorem (up to a constant factor)

April 14, 2015

It is suprisingly easy and pretty to give an elementary proof that the prime number theorem (that the number $\pi(x)$ of primes less than $x$ is asymptotic to $x/\log x$) is true up to a constant factor. (I will address only the part where we show that there are many (i.e. at least $~cx/\log x$) primes less than $x$.)

Consider a binomial coefficient ${n \choose k}$. Let $p$ be a prime. We first want to know what the largest power of $p$ is which divides ${n \choose k}$. There is more than one way to express the answer, the most elegant one I know of is as follows:

Add the numbers $k$ and $n-k$ in base $p$ (by the usual primary school algorithm). Then the number of carries that occur in this addition is equal to the greatest power of $p$ dividing ${n \choose k}$.

What is most important for us is the fact that this number is no more than $\log_p n$.

We immediately get

$\displaystyle \prod_{p\leq n}p^{\log_pn}\geq {n\choose k}$

which is of course equivalent to

$\displaystyle n^{\pi(n)}\geq {n\choose k}.$

Make a good choice of $k$ and we are within a constant factor of the prime number theorem!

Let $M$ be the midpoint of the chord $PQ$ of a circle. Let $AB$ and $CD$ be two other chords of the circle passing through $M$ and let $X$ and $Y$ be the intersection points of $PQ$ with $AD$ and $BC$ respectively. Then $M$ is the midpoint of the segment $XY$. Proof: The space of all degree two polynomials vanishing at the four points $A, B, C$ and $D$ is of dimension 2*. Thus it is spanned by the equation of the circle and the equation of the union of the lines $AB$ and $CD$. Choose coordinates such that the line $PQ$ is the $x$-axis and the point $M$ is the origin. Then the coefficient of $x$ in both our spanning polynomials is equal to zero, hence this coefficient is also zero in the equation of the union of $AD$ and $BC$. Therefore $M$ is the midpoint of the segment $XY$, as required.