Monthly Archives: April 2013

The infinitude of the primes

As we all know, a (natural) number $p>1$ is called prime if its positive divisors are only $1$ and $p$. The fact that prime numbers are infinite in number was proved by Euclid (although it is not clear whether he discovered it) and the proof is a little gem of mathematical reasoning. We present his proof below:

Theorem: There are infinitely many prime numbers.

Proof: Consider any list of prime numbers, say $p_1,p_2\cdots p_n$. The number $P=p_1p_2\cdots p_n+1$ is clearly not on the list. If $P$ is not prime, then by definition there is a prime number $p$ which divides $P$. Clearly $p\ne p_i$ for any $i$ as otherwise $p$ divides $1$, a contradiction.  So $p$ is a prime number not on the list. If, on the other hand, $P$ is prime, then it is anyway a prime number not on the list. Hence our list is incomplete.$\Box$

We now give another beautiful proof for the same theorem owing to Euler. Although it does not strictly qualify as a valid mathematical proof by modern standards and is really nothing more then heuristic reasoning yet its “wow factor” is so high that as an exception it is still referred to as a proof. It can be recast into a more rigorous form but we do not so here so that its original taste is not disturbed. The essential argument here is that if the primes were finite then the product $\prod_{\text{p prime}}\frac{1}{1-1/p}$ would be finite which is not the case.

Theorem: There are infinitely many prime numbers.

Proof: Let $P$ denote the set of all primes. Now consider the product $\prod_{p\in P}\frac{1}{1-1/p}$ i.e.

$(\frac{1}{1-1/2})(\frac{1}{1-1/3})(\frac{1}{1-1/5})\cdots\\\\=(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\cdots)(1+\frac{1}{3}+\frac{1}{9}+\frac{1}{27}\cdots)(1+\frac{1}{5}+\frac{1}{25}+\frac{1}{125}\cdots)\cdots$

by the formula of the geometric series.

Next we observe that if we multiply out the terms (assuming such a multiplication is valid) then the reciprocal of every positive integer will occur exactly once by the uniqueness of the fundamental theorem of arithmetic. If $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is the unique factorization of $n$ then $\frac{1}{n}$ would result in the multiplication only when $\frac{1}{p_1^{\alpha_1}},\cdots \frac{1}{p_k^{\alpha_k}}$ are multiplied. Hence the above product

$\prod_{p\in P}\frac{1}{1-1/p}=\sum_{n=1}^\infty \frac{1}{n}$. The latter harmonic series is well known to be divergent. Hence there must be infinitely many terms in $P$.$\Box$

Filed under Algebra, Number theory

The algebraic numbers are countable

By definition an algebraic number is a complex number which satisfies some polynomial $a_0+a_1x+\cdots a_nx^n\in\mathbb{Z}[x]$. Every rational number $m/n$ is algebraic as $m/n$ satisfies $nx-m$. Further irrational numbers can also be algebraic, $\sqrt{n},n\in\mathbb{N}$ clearly satisfies $x^2-n$. Similarly purely imaginary numbers can be algebraic: $i$ obviously satisfies $x^2+1$.

Just as algebraic numbers are called so because they lie within the range of the “classical algebra” (by which we understand manipulation of the integers) to be “described entirely”, a non-algebraic number is called transcendental because one needs to transcend this “algebra” to describe it. There are only a few mathematically significant numbers which are known to be transcendental. For 2500 years a debate ranged as to $\pi$ was transcendental or not, before the question was settled in the affirmative by Lindemann in 1882. Similarly $e$ is transcendental. (We do not know whether $\pi+e$ is transcendental or not).

Surprisingly, even though the transcendental numbers seem fewer then the algebraic numbers they actually exist in greater abundance. In fact, almost every real number is transcendental. This is because the set of algebraic numbers is countable and hence has Lebesgue measure zero. Our aim in this post is to formally prove the countable nature of the algebraic numbers.

Theorem: Let $A$ be the set of all algebraic numbers. Then $A$ is countable.

Proof: We define a height $h$ of a polynomial $a_0+a_1x+\cdots a_nx^n\in\mathbb{Z}[x]$ as $h=n+\sum_{i=0}^n|a_i|$. Clearly for a fixed $h$ there are only finitely many choices for $n$ and $a_i$ and so there are only finitely many polynomials of fixed height.

Now we make a list of all the algebraic numbers in the following way: Consider any height $h\in\mathbb{N}$ and for all the finitely many polynomials of this height, write down all the finitely many roots of these polynomials in the list. Keep repeating for all possible heights. It is clear that no algebraic number will be missed out in this list. This proves that $A$ is countable.$\Box$

Filed under Algebra, Real Analysis

Real numbers are uncountable

One of the slickest proofs of all time is using Georg Cantor‘s 1891 diagonal argument in proving that the real numbers $\mathbb{R}$ constitute an uncountable set, that is, they cannot be put in a bijective correspondence with $\mathbb{N}$. Strictly speaking, Cantor original paper only proved that the set of all $0,1$-sequences is uncountable. However since it is easy to argue that the set of all such sequences and $\mathbb{R}$ have the same cardinality, indirectly we get a proof for the uncountable nature of the reals. Moreover, the argument given by Cantor in his proof can be easily modified to give a direct proof for the uncountability of the reals. This is what we do presently.

Theorem: $\mathbb{R}$ is uncountable.

Proof: We will accept that every real number $x$ has a decimal expansion, $x=N.x_1x_2\cdots$ and it is uniquely determined by $x$ if one agrees never to terminate the expansion with an infinite string of $9$‘s. The proof is based on contradiction, and so we suppose that $\mathbb{R}$ is not uncountable. Then it must be that $\mathbb{R}$ is countable and we can make a list of all the elements of $\mathbb{R}$ along with their decimal expansion as follows:

$x_1=N_1.x_{11}x_{12}x_{13}\cdots\\x_2=N_2.x_{21}x_{22}x_{23}\cdots\\x_3=N_3.x_{31}x_{32}x_{33}\cdots\\\vdots$

We now consider the real number $0.y_1y_2y_3\cdots$ which is defined by $y_i=1$ if $x_{ii}\ne 1$ and $y_i=2$ otherwise. It is clear that this number differs from every $x_i$ in the list in at least the $i$‘th position. Hence this list is incomplete, a contradiction.$\Box$

Filed under Real Analysis, Set theory

Niven’s proof for the irrationality of π

In this post I will present a beautiful proof owing to Ivan Niven on the irrationality of $\pi$. An analytical definition of $\pi$ is that $\pi$ is twice the smallest positive $x$ for which $\cos x$ equals $0$. (This definition is better then the usual circumference/diameter  one since it is not dependent on Euclidean axioms).

Theorem (Niven): $\pi$ is irrational.

Proof: Let, by way of contradiction $\pi=a/b$ with $a,b\in\mathbb{N}$. Now let

$f(x)=\frac{x^n(a-bx)^n}{n!}$ and

$F(x)=f(x)-f^{(2)}(x)+f^{(4)}(x)-\cdots(-1)^nf^{(2n)}(x)$

where we will specify $n$ later. Now $n!f(x)=a_0x^n+a_1x^{n+1}+\cdots a_nx^{2n}$ with $a_i\in\mathbb{Z}$ and so $f(0)=0$. Not only this, $f^{(j)}(0)=0$ for $1\le j\le n-1$. For $n\le j\le 2n$ we have $n!f^{(j)}(x)=n!b_0+b_1x+\cdots b_nx^n$ with $b_i\in\mathbb{Z}$ and so $f^{(j)}(0)$ is integral in this case as well. Also note that $f(x)=f(\pi-x)$ and so for any $j\ge 0,j\in \mathbb{Z}$ we have $f^{(j)}(x)=(-1)^jf^{(j)}(\pi-x)$ following which $f^{(j)}(\pi)=(-1)^jf^{(j)}(0)$ i.e. $f^{(j)}(\pi)$ is also integral.

Now it follows by elementary calculus that $\frac{d}{dx}(F'(x)\sin x-F(x)\cos x)=(F''(x)+F(x))\sin x=f(x)\sin x$ and so $\int_0^\pi f(x)\sin x dx=(F'(x)\sin x-F(x)\cos x)_0^\pi=F(\pi)+F(0)$. Now $F(\pi)+F(0)$ is integral because $f^{(j)}(\pi)$ and $f^{(j)}(0)$ are both integers for any $j$. It is also easy to see that for $0 we have $0 and hence $0. But now  $0<\int_0^\pi f(x)\sin x dx\le\frac{\pi(a\pi)^n}{n!}$ and as $n!$ grows faster then any exponential so this upper bound for the integral can be made arbitrarily small. Hence the value of the integral lies between $0$ and $1$. This is the contradiction which proves the result.$\Box$

One final word. Even though the proof is credited to Ivan Niven, it is very much possible that the idea was given by Hermite much earlier and all did Niven was to tweak Hermite’s idea to give this proof.

Filed under Real Analysis

A geometric proof for the irrationality of √2

Tom Apostol in 2000 gave a geometric proof of the irrationality of 2, which for a bright student can even be considered as a “proof without words”:

(The figure has been taken from wikipedia)

The explanation is as follows: Suppose $\sqrt{2}$ is rational and equals $m/n$ where $m,n\in\mathbb{N}$ with $(m,n)=1$. Consider an isoceles right $\vartriangle ABC$ with legs of length $n$ and hypotenuse $m$. Draw the blue arcs with center $A$. Observe that $\vartriangle ABC$ is congruent to $\vartriangle ADE$ by SAS, and furthermore note the various lengths given in the figure follow from this fact. Hence we have an even smaller right isosceles triangle $\vartriangle CDF$, with hypotenuse length $2n-m$ and legs $m-n$. The fact these values are integers even smaller than $m$ and $n$ and in the same ratio is clear from the figure and thus we contradict the hypothesis that $(m,n)=1$.

The above proof may be aptly summarized in one line:  If $\sqrt{2}=m/n$ is in lowest terms then $\sqrt{2}=(2n-m)/(m-n)$ is in lower terms. In this case however the definition of the square root is implicitly used to show that $2n-m and $m-n.

Filed under Miscellaneous

The Gauss triangle trick

This is a part of a series of proofs I plan to write here which seem essential for any student of mathematics. This series is inspired by the stackexchange post here, although I am not sure yet as to how many proofs from the list I will pick up.

Theorem: $\sum_{k=1}^nk=\frac{n(n+1)}{2}$.

Proof: Let $S=1+2+\cdots n$ and write $2S$ as follows:

$1+2+\cdots n +\\n+(n-1)+\cdots 1$.

Now addition is associative, so adding each number in the top line with the number directly below it, we get $2S= (1+n) + (2+(n-1))+\cdots (n+1)$. Clearly there are $n$ parenthesis with each summing to $n+1$ and so $2S=n(n+1)$. The  result follows.$\Box$

So why is this called the Gauss triangle trick. Well, the story goes that when Gauss was in preparatory school, Gauss’s teacher told the kids to add up all the numbers from $1$ to $100$. He probably thought that this will give him some time to rest and was surprised when in a few minutes Gauss came up with answer using this trick.

The numbers obtained as the various sums, eg $1,1+2=3,1+2+3=6$ etc are called triangle numbers. A triangle number is so called because it is a count of the number of balls that can form a equilateral triangle.