F.T.A. via Complex Analysis

Although this requires a bit of knowledge on Complex Anlaysis, I recently discovered this new way to prove the Fundamental Theorem of Algebra and I couldn’t help but share it.

First of all, what is the Fundamental Theorem of Algebra (FTA)? This very important (hence the name!) result states that:

Every non-constant polynomial with complex coefficients has a complex root.

In order to prove this, we must first be aware of Liouville’s Theorem:

Every bounded, entire function is constant.

Definitions

Bounded: a function on a set X is said to be bounded if there exists a real number M such that

for all x in X.

Entire: An entire function is a holomorphic function on the entire complex plane.

Liouville’s theorem is proved using the Cauchy integral formula for a disc, one of the most important results in Complex Analysis. Although I will not describe how to prove it or what it states in this blog post, I encourage you to read about here it as it is truly a remarkable result.

Now armed with Liouville’s Theorem we can prove the FTA.

Proof

Let P(z) = zn + cn-1zn-1 + … + c1z + c0 be a polynomial of degree n > 0. Then |P(z)| –> ∞ as |z| –> ∞, so there exists R such that |P(z)| > 1 for all z with |z| > R.

Consider f(z) = 1/P(z). If P has no complex zeros then f is entire. So, as f is continuous, f is bounded on {|z| ≤ R}.

As |f(z)| < 1 when |z| > R, f is a bounded entire function, so by Liouville’s Theorem f is constant, which is a contradiction.

The only thing we assumed was that P had no complex zeros, and so we contradicted this fact. Hence, P must have at least one complex zero. Amazing right!

M x

Catalan’s Conjecture

Although popularly known as Catalan’s conjecture, this is in fact a theorem in number theory, proven by Preda Mihăilescu in 2002, 158 years after it was conjecture in 1844 by French and Belgian mathematician Eugène Charles Catalan.

The theorem states that the only solution in the natural numbers of

for a,b>1; x,y>0 is x = 3, a=2, y=2, b=3.

Catalan ‘Near Misses’ (i.e. xa – yb <= 10; 2 <= x,y,a,b <= 100; a,b prime)

• 33 – 52 = 2
• 27 – 53 = 3
• 23 – 22 = 62 – 25 = 53 – 112 = 4
• 25 – 33 = 5
• 25 – 52 = 42 – 32 = 27 – 112 = 7
• 42 – 23 = 8
• 52 – 42 = 62 – 33 = 152 – 63 = 9
• 133 – 37 = 10

Proving the Conjecture

Similarly to Fermat’s last theorem, the solution to this conjecture was assembled over a long period of time. In 1850, Victor Lebesgue established that b cannot equal 2. But then it was only after around 100 years, in 1960, that Chao Ko constructed a proof for the other quadratic case: a cannot equal 2 unless x = 3.

Hence, this left a,b odd primes. Expressing the equation as (x-1)(xa-1)/(x-1) = yb one can show that the greatest common divisor of the two left hand factors is either 1 or a. The case where the gcd = 1 was eliminated by J.W.S Cassels in 1960. Hence, only the case where gcd = a remained.

It was this “last, formidable, hurdle” that Mihailescu surmounted. In 2000, he showed that a and b would have to be a ‘Wieferich pair’, i.e. they would have to satisfy ab-1 ≡ 1 (mod b2) and ba-1 ≡ 1 (mod a2). In 2002,  he showed that such solutions were impossible!

M x

Waring’s Problem

Statement:

Take any whole number k that is greater than or equal to 2.  Show that there is some number s (that is allowed to depend on k) so that every positive whole number is a sum of s kth powers.

Proof

This problem was first solved by David Hilbert, and was then later proved by G.H. Hardy and John Littlewood in a different way. In this case, the second proof actually gave a lot more insight to the problem. To solve Waring’s problem as it has been stated you don’t need to give an s, you only need to show that one exists.  Finding the smallest s that works is a much more challenging (although arguably more interesting) problem. Using the, now named, Hardy-Littlewood circle method, Hardy and Littlewood wrote down an expression that approximated the number of ways to write N as a sum of s kth powers:

The proof of Waring’s problem comes from that fact that since this must be positive and also be a whole number, there must be some way to write N as a sum of s kth powers.

M x

(Sorry for missing a post last week, my university work is getting a bit hectic so posts may be more sporadic!)

Lychrel numbers

Lychrel number is a natural number that cannot form a palindrome by the 196-algorithm: an iterative process of repeatedly reversing a numbers’ digits and adding the resulting numbers.

Whilst in other bases (powers of two) certain numbers can be proven to never form a palindrome, in base 10 (the base system we use in everyday life) no Lychrel numbers have been proven to exist. However many numbers, such as 196, are suspected to be a Lychrel number on “heuristic and statistical grounds“.

The name Lychrel was coined by Wade Van Landingham in 2002 as an anagram of Cheryl, his girlfriend’s name.

196-Algorithm

The reverse-and-add process is when you add a number to the number formed by reversing the order of its digits.

Examples of non-Lychrel numbers are (taken from Wikipedia):

• 56 becomes palindromic after one iteration: 56+65 = 121.
• 57 becomes palindromic after two iterations: 57+75 = 132, 132+231 = 363.
• 59 becomes a palindrome after 3 iterations: 59+95 = 154, 154+451 = 605, 605+506 = 1111
• 89 takes an unusually large 24 iterations to reach the palindrome 8,813,200,023,188.
• 1,186,060,307,891,929,990 takes 261 iterations to reach the 119-digit palindrome 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544, which is the current world record for the Most Delayed Palindromic Number. It was solved by Jason Doucette‘s algorithm and program in 2005.

196

196 is the smallest number suspected to never reach a palindrome in base 10 and has thus received the most attention:

• In 1985 a program by James Killman ran unsuccessfully for over 28 days, cycling through 12,954 passes and reaching a 5366-digit number.
• John Walker began his 196 Palindrome Quest in 1987. His program ran for almost three years, then terminated (as instructed) in 1990 with the message:

Stop point reached on pass 2,415,836.
Number contains 1,000,000 digits.
• In 1995, Tim Irvin and Larry Simkins reached the two million digit mark in only three months without finding a palindrome.
• Jason Doucette then reached 12.5 million digits in May 2000.
• Wade Van Landingham used Jason Doucette’s program to reach a 13 million digit. By May 2006, Van Landingham had reached the 300 million digit mark.
• In 2011 Romain Dolbeau completed a billion iterations to produce a number with 413,930,770 digits, and in February 2015 his calculations reached a number with billion digits.

A palindrome has yet to be found.

M x

MATHS BITE: Shoelace Theorem

The Shoelace theorem is a useful formula for finding the area of a polygon when we know the coordinates of its vertices. The formula was described by Meister in 1769, and then by Gauss in 1795.

Formula

Let’s suppose that a polygon P has vertices (a1, b1), (a2, b2), …, (an, bn), in clockwise order. Then the area of P is given by

$$\dfrac{1}{2} |(a_1b_2 + a_2b_3 + \cdots + a_nb_1) - (b_1a_2 + b_2a_3 + \cdots + b_na_1)|$$

The name of this theorem comes from the fact that if you were to list the coordinates in a column and mark the pairs to be multiplied, then the image looks like laced-up shoes.

Proof

(Note: this proof is taken from artofproblemsolving.)

Let $\Omega$ be the set of points that belong to the polygon. Then

$$A=\int_{\Omega}\alpha,$$

where $\alpha=dx\wedge dy$.

Note that the volume form $\alpha$ is an exact form since $d\omega=\alpha$, where

$$\omega=\frac{x\,dy}{2}-\frac{y\,dx}{2}.\label{omega}$$

Substitute this in to give us

$$\int_{\Omega}\alpha=\int_{\Omega}d\omega.$$

and then use Stokes’ theorem (a key theorem in vector calculus) to obtain

$$\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.$$

where

$\partial \Omega=\bigcup A(i)$

and $A(i)$ is the line segment from $(x_i,y_i)$ to $(x_{i+1},y_{i+1})$, i.e.  is the boundary of the polygon.

Next we substitute for $\omega$:

$$\sum_{i=1}^n\int_{A(i)}\omega=\frac{1}{2}\sum_{i=1}^n\int_{A(i)}{x\,dy}-{y\,dx}.$$

Parameterising this expression gives us

$$\frac{1}{2}\sum_{i=1}^n\int_0^1{(x_i+(x_{i+1}-x_i)t)(y_{i+1}-y_i)}-{(y_i+(y_{i+1}-y_i)t)(x_{i+1}-x_i)\,dt}.$$

Then, by integrating this we obtain

$$\frac{1}{2}\sum_{i=1}^n\frac{1}{2}[(x_i+x_{i+1})(y_{i+1}-y_i)- (y_{i}+y_{i+1})(x_{i+1}-x_i)].$$

This then yields, after further manipulation, the shoelace formula:

$$\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i).$$

M x

Proof Without Words #3

Proof of the identity

The figure for general n is similar, with n right pyramids, one with an (n-1)-cube of side length xk as its base and height xk for each k=1,….,n.

The derivative of sin is cosine.

From ‘Proof without words‘ by Roger Nelsen

Previous ‘Proof Without Words‘: Part 1 | Part 2

M x

Goodstein Theorem

On reading a magazine on Gödel’s Incompleteness Theorems, I came across a family of sequences of non-negative integers called Goodstein sequences and the Goodstein Theorem involving these sequences.

Goodstein’s thoerem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence converges to 0.

What is a Goodstein Sequence?

To understand what a Goodstein sequence, first we must understand what hereditary base-n notation is. Whilst this notation is very similar to the usual base-n notation, base-n notation is not sufficient for Goodstein’s theorem.

To convert a base-n representation to a hereditary base-n notation, first rewrite all of the exponents in base-n notation. Then rewrite any exponents inside the exponents, and continue this way until every number in the expression has been converted to base-n notation.

For example, 35 = 25 + 2 + 1 in ordinary base-2 notation but  in hereditary base-2 notation.

Now we can define the Goodstein sequence G(m) of a natural number m. In general the (n+1)-st term G(m)(n+1) of the Goodstein sequence of m is given as follows (taken from Wikipedia):

• Take the hereditary base-n + 1 representation of G(m)(n).
• Replace each occurrence of the base-n + 1 with n + 2.
• Subtract one. (Note that the next term depends both on the previous term and on the index n.)
• Continue until the result is zero, at which point the sequence terminates.

In spite of the rapid growth of the terms in the sequence, Goodstein’s theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.

Mathematicians Laurie Kirby and Jeff Paris proved in 1982 that Goodstein’s theorem is not provable in ordinary Peano arithmetic. In other words, this is the type of theorem described in 1931 by Gödel’s incompleteness theorem.

M x