Tag Archives: number theory

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

Advertisements

Leave a comment

Filed under Algebra, Number theory

The van der Waerden theorem

In this post I aim to prove van der Waerden’s theorem on arithmetic progressions.

The theorem states that \forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N} so that if the set \{1,2\cdots W(k,r)\} is partitioned into r classes, one of the classes is guaranteed to contain an arithmetic progression of length k.

Before proceeding further, lets look at a bit of history regarding this result. As per a recent book the theorem was conjectured independently by the mathematicians Schur and Baudet sometime around the 1920’s. (The exact dates are unknown). In 1926 van der Waerden, then a young scholar in Hamburg, heard of this conjecture (he believed it to be solely by Baudet) and proved it in the course of a remarkable discussion with his teacher Emil Artin and the mathematician Otto Schreier. The beauty of the proof was that it did not use any tools of advanced mathematics and yet was not simple by any means. Khinchin has referred to it as one of the three pearls of number theory.

Our proof here is not the same proof as originally given by van der Waerden, but a slightly slicker version based on the same idea. We start by making some preparations for the proof. For convenience we will take [n]=\{1,2\cdots n\}. Further we can very well uniquely identify a partitioning \{W_1,W_2,\cdots W_r\} of a set [W(k,r)]=\cup_{i=1}^rW_i by a function f with domain [W(k,r)] and range [r] where f^{-1}(i) equals W_i. Traditionally the numbers \{1,2\cdots r\} are called colors, every such function is called a r-coloring and the sets f^{-1}(i) are referred to as being colored i. Given a r-coloring a subset of [W(k,r)] is called monochromatic if every element in it corresponds with the same color. With these new definitions the van der Waerden theorem takes the form:

Theorem: \forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N} so that if [W(k,r)] is r-colored then there is a monochromatic arithmetic progression of length k.

We shall also use the notation a + [0,k)d for the arithmetic progression of length k (also abbreviated as a k-AP) given by the ordered set \{a<a+d<a+2d<\cdots a+(k-1)d\}

And now, on to the proof. As a first step towards proving the result we shall first introduce the concept of wheels. The next step will establish some technical lemmas concerning them and after that we will prove the van der Waerden theorem.

A wheel of radius k, degree n and base point or origin a is a n tuple: W= (a + [0,k) d_1,\cdots, a + [0,k)d_n) of k-AP's each of which has base point a. The AP's a + [1,k)d_i, 1 \le i \le n are called the spokes of the wheel. Assuming that all numbers under consideration have been colored a wheel is weakly polychromatic if all of it’s n spokes are monochromatic with distinct colors, and strongly polychromatic if it’s n spokes and origin are all monochromatic with distinct colors.

An example of a strongly polychromatic wheel of degree 8 and radius 5 is given below. In case of a weakly polychromatic wheel the origin, i.e. 1, can be of any of the colors of the spokes.

The 8 AP’s are:
1,2,3,4,5
1,10,19,28,37
1,4,7,10,13
1,7,13,19,25
1,6,11,16,21
1,8,15,22,29
1,5,9,13,17
1,3,5,7,9

A translation of a wheel W by a number r defined as the wheel obtained by adding a to each number in W.

We now move on to the next stage in our proof, where we shall establish some technical lemmas concerning wheels.

Lemma 1: If W= (a + [0,k) r_1,\cdots, a + [0,k)r_n) is a wheel of radius k and degree n and the k-1 translations W + r ,\cdots W+(k-1)r of W are all strongly polychromatic with the same colors, then the wheel \hat{W} = (a + [0,k)r , a + [0,k)(r_1 + r),\cdots a + [0,k)(r_n + r)) of radius k and degree n+1 is weakly polychromatic.

Proof: The integers a + (r_i + r), a + 2(r_i + r), \cdots a + (k-1)(r_i + r) respectively picked from W+r, W + 2r ,\cdots  W+(k-1)r are identical in color because the ith component of each translation is colored identically. So \forall i, 1 \le i \le n, a + [1,k)(r_i + r) is monochromatically colored and distinct from others. Similarly the AP of the base points a+r,a+2r,\cdots a+(k-1)r also has a distinct color. Thus we have a n+1 tuple of AP’s each of which is distinctly monochromatic if we ignore the base point a, or that \hat{W} is weakly polychromatic.

Two more lemmas whose proofs are obvious are:

Lemma 2: If W is a weakly polychromatic wheel of radius k, then either W is strongly polychromatic, or contains a monochromatic AP of length k.

Lemma 3: A strongly polychromatic wheel cannot have degree r where r is the total number of colors.

With the necessary machinery in our arsenal we now attack the van der Waerden theorem proper.

Proof of the van der Waerden theorem: We shall use double induction. The first (outer) induction is on k. Clearly for k = 1,2 and any r the result holds. Let us suppose that W(k-1,r) exists for all r. Now we

Claim: For any n\in\mathbb{N},\exists N=N(k-1,r,n)\in\mathbb{N} such that given any r-coloring of [N], there exists either a monochromatic AP of length k, or there exists a strongly polychromatic wheel of radius k and degree n.

To prove the claim we use (an inner) induction on n. The case n = 1 is trivial if we use the outer induction hypothesis. Suppose the result holds for n-1, that is, N_1 = N(k-1,r,n-1) exists. Now by the inner hypothesis any block of integers of length N_1 contains either a monochromatic AP of length k (in which case we are done) or a strongly polychromatic wheel of radius k and degree n-1. In the second case let N_2 = 2W(k-1, r^{N_1}) which exists by the outer hypothesis, color the first N_1N_2 integers and consider N_2 consecutive blocks of length N_1. Since there are r^{N_1} colorings of each block, by the outer hypothesis there must be an AP of k-1 identically colored blocks: B+d, B+2d,\cdots B+(k-1)d.

Now as |B| = N_1 = N(k-1,r,n-1) so inside each block, there is either a monochromatic AP of length k in it, (which proves the theorem) or a strongly polychromatic wheel of radius k and degree n-1. Ruling out the former case means that each block B + d, \cdots B +(k-1)d contains a strongly polychromatic wheel of degree n-1. Since these blocks are identical in color so we have a AP of strongly polychromatic identical wheels. In this case, by lemma 1, the AP of blocks contains a weakly polychromatic wheel W of radius k and degree n. By lemma 2, W is either strongly polychromatic or contains a monochromatic AP of length k. In either case we have proved our claim.

The proof of van der Waerden’s theorem is trivial now. Choose W(k,r) = N(k-1,r,r). Now an r-coloring of [W(k,r)] contains either a monochromatic AP of length k or a strongly polychromatic wheel of degree r. The latter case is not possible due to lemma 3.\Box

1 Comment

Filed under Combinatorics, Ramsey theory