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!

The Butterfly Theorem

March 1, 2015

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. Butterfly Theorem diagram (from wikipedia) 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.

*To see this there is a six dimensional space of degree two polynomials and we are imposing one linear condition each time we require the polynomial to vanish at a point. These four conditions are linearly independent since it is easy to find degree two curves passing through three of these points and not the fourth (e.g. a union of two lines).