## Archive for the ‘maths’ Category

### 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!

### Concyclicity in the Euclidean Plane

August 21, 2014

I want to address the question of how to determine whether or not four points are concyclic. In a previous post, this question reared its head and was solved by an introduction of the circumcentre of three of the points. In this post, I present a direct approach.

We prove the following:

Let $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$ be four points in $\mathbb{R}^2$. Then these four points are concyclic if and only if

$\displaystyle \left| \begin{array}{cccc} x_1^2+y_1^2 & x_1 & y_1 & 1 \\ x_2^2+y_2^2 & x_2 & y_2 & 1 \\ x_3^2+y_3^2 & x_3 & y_3 & 1 \\ x_4^2+y_4^2 & x_4 & y_4 & 1 \end{array} \right|=0.$

For the proof, first suppose that the points $(x_i,y_i)$ all lie on the curve

$\displaystyle (x-x_0)^2+(y-y_0)^2=r^2.$

The four equations we obtain give a linear dependence of the columns in the $4\times 4$ matrix under consideration, hence its determinant is zero.

Conversely, suppose that the determinant in question is zero. Then there is a nonzero vector in the nullspace of our $4\times 4$ matrix. If its first entry is nonzero, we can normalise it to be of the form $(1,-2x_0,-2y_0,x_0^2+y_0^2-r^2)^T$ and we obtain the circle that the four points lie on. If the first entry of this vector is equal to zero, then the four points must lie on a line, which after is all is just a degenerate circle, QED.