Archive for August, 2009

e is transcendental

August 19, 2009

In 1873 Charles Hermite showed that e is transcendental.  Liouville had earlier shown how to construct such numbers, but Hermite’s was the first proof that an ‘interesting’ mathematical constant was transcendental.

Hermite’s proof is long and complex.  It has since been simplified considerably and in particular a short and elegant proof appears in Baker’s book ‘Transcendental Number Theory’.  However Baker himself says that the motivation of the proof has been obscured by the process of simplification, and it is necessary to go back to Hermite’s original paper in order to understand it.

I think this is not entirely so but nevertheless in this post  I give in outline a version of Baker’s proof that I preface with some references to ideas in Hermite’s paper and I hope in so doing I make the motivation clearer.  A more detailed version of this outline is in a pdf here.

As discussed in an earlier post, by repeated integration by parts Hermite obtained an expression of the form

           i^{2m+1}\int_0^1e^{it}F_m(t)dt=k_i(m)e^i-h_i(m)

where Fm(t)=tm(1-t)m , m and i are positive integers and ki, hi are polynomials with integer coefficients.  The expression on the left of the equation is not zero but can be made arbitrarily small in absolute value by taking m sufficiently large, thereby proving that ei is irrational for any integer i.

This suggests that one could obtain in a similar manner a set of equations of the form

k(m)e^i-h_i(m)=I_i(m)   ………………………………………….   (1)

where k(m) is a non-zero integer not dependent on i and the Ii(m) either decrease in absolute value or grow only slowly with increasing m.

Now let q0, q1, … , qn be any set of integers (provided that n > 0 and q0, qn ≠0).  If we multiply (1) by qi and sum over i then we have

\sum_{i=0}^nq_iI_i(m)=-\sum_{i-0}^nq_ih_i(m)+k(m)(q_0+q_1e+ ... +q_ne^n)

Then if we can find Ii(m) and hi(m) and non-zero k(m) such that for sufficiently large m,

|\sum_{i=0}^nq_iI_i|<|\sum_{i=0}^nq_ih_i|   ……………………………………   (2)

we have proved e is transcendental because then it is not possible to have

q_0+q_1e+ ... +q_ne^n=0

If we use in the integral ei-t rather than eit as used by Hermite we  immediately obtain an expression in the desired form (1).  Let

I_i(m)=\int_0^ie^{i-t}f(t)dt

where f(t) is a polynomial of degree m with integer coefficients.  For i > 0 repeated integration by parts gives

I_i(m)=e^i\sum_{j=0}^mf^{(j)}(0)-\sum_{j=0}^mf^{(j)}(i)

and the equation, which is identical in form to (1), is also correct in a formal sense for I0=0.  Now let

 f(t)=t^{p-1}(t-1)^p(t-2)^p ... (t-n)^p

Then

|I_i|\leq\int_0^i|e^{i-t}f(t)|dt<(2i)^mie^i

and it is not hard to find that for sufficiently large p

|\sum_0^nq_iI_i| < A^p

where A is positive and independent of p.  This puts an upper bound on the left hand side of (2).  It is also not too hard to show (pdf) that

k(m)=\sum_{j=0}^mf^{(j)}(0)

cannot be zero if we make p a prime and greater than n (which we are quite at liberty to do).  Finally we can show that as long as p>|q0| then

|\sum_{i=0}^nq_ih_i(m)| > (p-1)!

giving a lower bound to the right hand side of (2).  But since (p-1)!>Ap for some large enough p, then (2) holds and we have proved e is transcendental.

Euler’s phi function

August 14, 2009

If k is some positive integer, φ(k) is defined as the number of positive integers less than or equal to k whose greatest common divisor (gcd) with k is one.  Thus φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2 and so on.

Let d, n be positive integers and let ‘d|n’ signify ‘d divides n’.  The theorem

\sum_{d|n}\phi(d)=n

is not difficult to prove (for example Hardy and Wright, 5th ed. Theorem 63).  The proof I like best however is not the simplest, but it shows how φ is related to the structure of the abstract finite cyclic groups, of which the additive groups of integers (modulo n) are concrete examples.

By the the latter groups I mean the set of integers 0, 1, … , n-1 and the binary operation ° which is defined such that a°b is the remainder on dividing a+b by n.  We call this addition (modulo n).

We define the order of a as the least positive integer i such that ai is divisible by n, that is, the remainder on dividing ai by n is 0, the identity element. 

Now every element of a group has some order and if N(d) is the number of elements of order d then

\sum_dN(d)=n

where n is the order of the group.  But an element of order d generates a subgroup of order d and so by Lagrange’s theorem, d|n.  Thus

\sum_{d|n}N(d)=n

Now the cyclic group of order n (Cn) is known to have exactly one subgroup of order d for each divisor d of n, and each subgroup is necessarily cyclic. An element of Cn has order d iff it is a generator of the subgroup of Cn of order d. Therefore N(d), the number of elements of order d in Cn, is equal to the number of generators in Cd. To complete the proof we need only show that this is φ(d).

We can represent Cd as consisting of the integers 0, 1, … , d-1 with the binary operation being addition modulo d. If gcd(k,d)=1 then none of the integers k, 2k, … ,(d-1)k is divisible by d, and they are all distinct (mod d) and since there are d-1 of them and dk=0 (mod d) then k is a generator. On the other hand, if k is a generator it has order d. But

\displaystyle k\frac{d}{gcd(k,d)}=k'd=0 (mod d)

so the order of k is no greater than d/gcd(k,d) and if gcd(k,d) were not one, we would have a contradiction.  Therefore k is a generator iff gcd(k,d)=1 and so the number of generators in Cd is φ(d).

The irrational nature of zeta(3)

August 2, 2009

If n is an integer greater than one, one defines

            \displaystyle\zeta(n)=\sum_{n=1}^\infty\frac{1}{k^n}

When n  is even, \zeta(n) is irrational iff \pi^n is irrational since

           \displaystyle\zeta(2n)=\frac{2^{2n-1}|B_{2n}|\pi^{2n}}{(2n)!}

and B_n, the n th Bernoulli number, is rational.

The nature of \zeta(n) for odd n remained a mystery until 1978, when it was shown by Roger Apéry that \zeta(3) is irrational.  (The mystery remains for odd n>3).

As before we use the fact that

x is irrational if there exist integers h and k such that 0 < |kx - h| < \epsilon for any given real number 1 > \epsilon> 0

Apéry [1] described sequences h_n, k_n that satisfy this condition for sufficiently large  n when x = \zeta(3).  In 1979 Beukers described [2] a simpler method of arriving at the same result.  This works as follows (to keep the post, and my editing time, short, I haven’t included proofs of the lemmas.  Instead, the full article with lemmas is available as a pdf here)

Firstly we note the following formulas (see Lemma 1)

 \displaystyle\int^1_0\int^1_0\frac{x^iy^i\ln xy}{1-xy}dydx=-2\sum^\infty_{k=i+1}\frac{1}{k^3}

\displaystyle =\begin{cases}-2\zeta(3) \text{ if i=0}\\-2\zeta(3)+2\sum^i_{k=1}\frac{1}{k^3} \text{ if }i>0\end{cases}   

When i>j

            \displaystyle\int^1_0\int^1_0\frac{x^iy^j\ln xy}{1-xy}dydx=\frac{-1}{i-j}\sum^i_{k=j+1}\frac{1}{k^2}

Suppose F_n(x) is some polynomial in x of degree n with integer coefficients.  Then we can represent F_n(x)F_n(y) as

\displaystyle F_n(x)F_n(y)=\sum^n_{i=0}a_{ii}x^iy^i+ \sum^n_{i=1}\sum^{i-1}_{j=0}a_{ij}x^iy^j  

with the aij integers.

Combining the three expressions above we can obtain

      \displaystyle\int^1_0\int^1_0\frac{F_n(x)F_n(y)\ln xy}{1-xy}dydx=-2a_{00}(n)\zeta(3)+

\displaystyle\sum^n_{i=1}a_{ii}(-2\zeta(3)+2\sum^i_{k=1}\frac{1}{k^3})+2\sum^n_{i=1}\sum^{i-1}_{j=0}a_{ij}\frac{-1}{i-j}\sum^i_{k=j+1}\frac{1}{k^2}

Let dn be the least integer that is divisible by each of the integers 1,2, .. ,n.  Then it is not hard to see that the denominators of all the fractions on the right hand side of the above expression divide (dn)3.  Therefore we have

            \displaystyle(d_n)^3\int^1_0\int^1_0\frac{F_n(x)F_n(y)\ln xy}{1-xy}dydx=k_n\zeta(3)-h_n

with kn, hn integers.  To complete the proof we need to find an F_n(x) such that for large enough n, we can make the absolute value of the left hand side as close as we like to zero, without actually being zero.

It was established in connection with the proof of the Prime Number Theorem that [3] dn<e(1+δ)n for sufficiently large n and any given positive real number δ.  Consequently (dn)3<e(3+δ)n for sufficiently large n.

In an earlier post we made use of the polynomial

 (d^n/dx^n)(x^n(1-x)^n)

This is a polynomial of degree n with integer coefficients, and each of its coefficients is divisible by n! (Lemma 2).  We take

\displaystyle F_n(x)=\frac{1}{n!}(d^n/dx^n)(x^n(1-x)^n)

It is not too difficult to establish (Lemma 3) that

\displaystyle\int^1_0\int^1_0\frac{F_n(x)F_n(y)\ln xy}{1-xy}dydx<\exp^{-4(\ln(\sqrt{2}+1))n}<e^{-3.5n}

Consequently

            \displaystyle0<(d_n)^3\int^1_0\int^1_0\frac{F_n(x)F_n(y)\ln xy}{1-xy}dydx<e^{(-n/2)+\delta}

And the result is proved.

[1] Roger Apéry, ‘Irrationalité de ζ(2)et ζ(3)’, Astérisque 61, 1979, pp 11-13; and ‘Interpolation de fractions continues et irrationalite de certaines constantes’, Bulletin de la Section des Sciences du C.T.H.S. III, 1981, pp 37-53.

[2] Frits Beukers, ‘A Note on the Irrationality of ζ(2)and ζ(3)’, Bulletin of the London Mathematical. Society, 11, 1979, pp 268-272.

[3]  In analytical number theory, the function ln dn is usually called ψ(n).  This function was introduced around 1850 by Chebyshev who showed that the conjecture limn→∞ψ(n)/n=1 (if such a limit exists) implies the prime number theorem.  (Chebyschev also obtained upper and lower bounds on ψ(n)/n and showed that if a limit exists, it must be 1).  Most proofs of the Prime Number Theorem whether by way of Riemann’s zeta function or by way of the ‘elementary proof’ proceed by proving the limit exists.  Consequently ln dn/n<1+δ for sufficiently large n and any given real positive δ.