Monday, 30 December 2013

Life and mathematics of Paul Erdos

There was a meeting on Saturday at Gokhale Sastri institute, organized by BrainsTrust. The mathematician and Professor in Univ of Florida, Krishnaswamy Alladi, grandson of Alladi Krishnaswami Iyer, one of the architects of the Constitution of India, was invited to speak on the Life and mathematics of Paul Erdos, a Hungarian genius.

Krishnaswamy Alladi started with Euclid’s Existence Proof that there are infinite primes. Then he explained the Sieve of Eratosthenes method of finding all primes upto a number. He contrasted their mutual incompatibility: Euclid does not tell you how to find a prime number, Eratosthenes cannot be used to prove that there are an infinite number of primes.
For a long time there was no real theory of prime numbers.  Late in the 18th century, the French mathematician Legendre conjectured that the number of primes upto a number x is π[x]=x/log x. There was also a conjecture by Bertrand that there is always at least one prime between any x and 2x. But nobody could prove either of these, until the Russian mathematician Chebyshev in 1850 who stated that if there is a limit to π[x]/ (x/log x) as x approaches infinity, then the limit must be 1. This is asymptotic,: it approaches 1, but [numerator – denominator] does not go to zero. Computer Science students and graduates may know the asymptotic idea from the notations used in algorimthic time and space complexity : O(n) and Ω(n).

Erdos, Elegance and Excellence

Effectively these ideas became to be called the Theory of Prime numbers. Paul Erdos became famous world wide, when as a 19 year old he came up with an elegant proof of Bertrand’s Postulate, more elegant than Chebyshev’s.

Elegance was a favorite theme of Erdos, who though an atheist believed God had a book, which contained the most elegant proofs in mathematics. Erdos was an interesting personality, who owned no home, possessed few clothes and only a suitcase, was a citizen of the world and travelled the earth unearthing and enthusing youngsters. A jet-age peripatetic global mentor, a social oddity, a sybaritic bachelor who was “married to mathematics”, and a sociable delight.

If Alladi’s rendition of the history of maths was delightfully elegant for a mathematics enthusiast like me, his narration of Erdos’ idiosyncrasies and charm regaled the lay person for whom math is an enigma.

There is an inside joke called the Erdos number – if you collaborated with Erdos, your Erdos number was 1. If you collobarated with someone who had collaborated with Erdos on a different paper, your Erdos number was 2, and so on. Like the six degrees of Kevin Bacon, perhaps modeled on the Erdos number. If you collaborated on n papers with Erdos, your Erdos number was 1/n, and Alladi said his Erdos number was 1/5!!

Ramanujan and Erdos

Some work was done in the 20th century by GH Hardy and his discovery, S Ramanujan. In Ramanujan’s famous letter to Hardy, one of his formulae was for the number of primes upto a given number. I have borrowed Hardy’s Lectures on Ramanujan from Sri Balasubramanian, my Sanskrit teacher. They collaborated and came up formulae related to primes - Sum of primes, number of primes, number of divisors. Ramanujan came up with the little vs big omega notation for prime divisors: count each divisor vs count only unique divisors. For example, 12=2*2*3. Does it have 2 divisors or 3? Count them both ways said Ramanujan, with different notations. Ω[12]=3 but ω[12]=2, counting 2 as divisor only once. Hardy & Ramanujan proved then that on the average they both don’t differmuch, that they both will be log log x – meaning most prime factors will not repeat, for large numbers. Alladi remarks that this was the first systematic discussion of prime numbers, even though they were known since Greek antiquity.

Coming back to Erdos, and his proof of Bertrand’s postulate, one of Erdos’ Hungarian colleagues mentioned that his proof was very similar to the proofs of S Ramanujan – and that was Erdos’ introduction to Ramanujan and Madras.

The Erdos - Alladi – Madras connection

Krishnaswami Alladi, then a student at Vivekananda College, looked at the missing element here : Sum of divisors. So devised a formula in second year of Vivekananda college which was accepted a conference on maths in Calcutta, which he could not go to but his father agreed to present, in the student’s section. Which was heard by Paul Erdos! Who came to Madras to specifically meet Krishnaswami! And related the Madras Iyer ditty, modeled on the Boston Cabott Lowell ditty. And wrote a recommendation letter to a Stanford University professor, which accepted him.

Krishnaswami Alladi’s formula for the sum of prime factors, which he called A(n) after himself, in “a moment of vanity”, he says. Erdos suggested that the largest prime factor will swamp the sum. Alladi wondered whether if it were removed the second largest would dominate, and so on. “Very good question,” replied Erdos. “Work on it!” And so Alladi worked with Erdos to prove this – one of his most quoted papers.

Alladi showing a paper handwritten by Paul Erdos

It was a delightful evening. Alladi’s presentation was approachable excellence, flavored with anecdote, humour and history, as opposed a lot of science or maths, which is dry erudition. Please watch the video links.

No comments:

Post a Comment