Omar Khayyam, the Rubaiyat and other stories

His name means tent maker. His most renowned book as a mathematician is "Treatise on Demonstration of the Problems of Algebra". He is supposed to have calculated the length of a year as 365.24219858156 days. He was made famous by Edward Fitzgerald in 1859 in a different field.

That was Omar Khayyam, the Persian mathematician, poet, astronomer, and philosopher, of course. Outside of Iran, thanks to Edward Fitzgerald, he's mostly famous for his Rubaiyat. Rubaiyat derives from Rubaiyaas, which derives from the Arabic word for the number 4, meaning a verse with four lines, or a quatrain. The Rubaiyat is a collection of Khayyam's quatrains -- he wrote 1000s of them. One of the more famous ones (Edward Fitzgerald's translation) --

The Moving Finger writes: and, having writ,
Moves on: nor all thy Piety nor Wit
Shall lure it back to cancel half a Line,
Nor all thy Tears wash out a Word of it.

Even though Winston Churchill and Martin Luther King, Jr. have quoted the above quatrain in their speeches (MLK, in his speech Why I oppose the war in Vietnam says, "It is time for all people of conscience to call upon America to come back home. Come home America. Omar Khayyám is right 'The moving finger writes and having writ, moves on.'"), probably Omar Khayyam's biggest contributions are in the fields of mathematics and astronomy. He wrote the Treatise on Demonstration of Problems of Algebra. Importantly he generalized the algorithm for solving cubic equations (and some higher power equations). In his book, Omar Khayyam has this to say --

From the Indians one has methods for obtaining square and cube roots, methods which are based on knowledge of individual cases, namely the knowledge of the squares of the nine digits 1², 2², 3² (etc.) and their respective products, i.e. 2 × 3 etc. We have written a treatise on the proof of the validity of those methods and that they satisfy the conditions. In addition we have increased their types, namely in the form of the determination of the fourth, fifth, sixth roots up to any desired degree. No one preceded us in this and those proofs are purely arithmetic, founded on the arithmetic of The Elements (of Euclid).

On the lighter side, an extremely hilarious and interesting take on the theatrical managers of 1920s in Broadway by Wodehouse (from Little Warrior urf Jill the Reckless).

Mr.Goble is a theatrical Manager on Broadway and is putting on a musical comedy written and financed by Mr. Pilkington from England. Wally is an established writer and composer. Mr.Goble has just come to the sets during practice and has cut out a line about a watermelon from the hero's script.

The gentleman who was playing the part of Lord Finchley, an English character actor who specialized in London "nuts," raised his eyebrows, annoyed. Like Mr Pilkington, he had never before come into contact with Mr Goble as stage-director, and, accustomed to the suaver methods of his native land, he was finding the experience trying. He had not yet recovered from the agony of having that water-melon line cut out of his part. It was the only good line, he considered, that he had. Any line that is cut out of an actor's part is always the only good line he has.

"The speech about Omar Khayyam?" he enquired with suppressed irritation.

"I thought that was the way you said it. All wrong! It's Omar of Khayyam."

"I think you will find that Omar Khayyam is the--ah--generally accepted version of the poet's name," said the portrayer of Lord Finchley, adding beneath his breath. "You silly ass!"

"You say Omar of Khayyam," bellowed Mr Goble. "Who's running this show, anyway?"

"Just as you please."

Mr Goble turned to Wally.

"These actors . . ." he began, when Mr Pilkington appeared again at his elbow.

"Mr Goble! Mr Goble!"

"What is it now?"

"Omar Khayyam was a Persian poet. His name was Khayyam."

"That wasn't the way I heard it," said Mr Goble doggedly. "Did you?" he enquired of Wally. "I thought he was born at Khayyam."

"You're probably quite right," said Wally, "but, if so, everybody else has been wrong for a good many years. It's usually supposed that the gentleman's name was Omar Khayyam. Khayyam, Omar J. Born 1050 A.D., educated privately and at Bagdad University. Represented Persia in the Olympic Games of 1072, winning the sitting high-jump and the egg-and-spoon race. The Khayyams were quite a well-known family in Bagdad, and there was a lot of talk when Omar, who was Mrs Khayyam's pet son, took to drink and started writing poetry. They had had it all fixed for him to go into his father's date business."

Mr Goble was impressed. He had a respect for Wally's opinion, for Wally had written "Follow the Girl" and look what a knock-out that had been. He stopped the rehearsal again.

"Go back to that Khayyam speech!" he said, interrupting Lord Finchley in mid-sentence.

The actor whispered a hearty English oath beneath his breath. He had been up late last night, and, in spite of the fair weather, he was feeling a trifle on edge.

"'In the words of Omar of Khayyam' . . ."

Mr Goble clapped his hands.

"Cut that 'of,'" he said. "The show's too long, anyway."

And, having handled a delicate matter in masterly fashion, he leaned back in his chair and chewed the end off another cigar.

Your half is bigger than mine...... NOT! -- On fair division

The problem of fair division can be traced back a full 3000 years in history. Stated in simple terms, the problem is:

How do you divide a cake between n people such that each person gets a fair share of the cake? An additional clause is that if someone thinks they got lesser than someone else, then it should be such that, that person alone is to bear the blame.

Lets first consider the case of n=2. If there are two people involved, say Alice and Bob, the solution is simple -- "Alice cuts, Bob chooses". So the best solution for Alice in this scenario is to cut such that she feels both shares are equal halves, so that no matter which piece Bob chooses, she's happy with the other one. Best solution for Bob is that he chooses the piece he thinks is bigger. Now, if Alice didnt cut it into equal halves, and Bob chooses the bigger one, she has only herself to blame for being left with the smaller piece.

If you now extend this to n=3, the problem becomes extemely complicated. You can imagine how the above solution can be extended. Say Tom, Dick, and Harry are trying to divide the cake equally between themselves. You can imagine a solution where Tom cuts the cake into what he thinks are 1/3rd and 2/3rds. Then Dick cuts the 2/3rd piece into two halves. Harry picks one of the three pieces. Tom picks next, and the left over piece goes to Dick.

Some elementary analysis will reveal that this is fair to Tom and Harry, and not fair to Dick. Now, clearly, Harry is satisfied. There are three pieces and he picks the biggest of the three. Tom comes next. If Harry picked one of the pieces that Dick cut, then Tom can take the piece that he cut (as 1/3rd) and be satisfied. If Harry picks the 1/3rd piece that Tom cut, then Tom can take whichever of the other two he thinks is bigger -- at this stage it is a two-person problem betwen Tom and Dick, since he thinks the 2/3rd really was a 2/3rds.

The story for Dick though is very different. If Dick initially thought Tom's cut was fair, then he has no issues, and the solution works for all. However, if Dick thinks Tom's cut was unfair and the 2/3rd was smaller than actual 2/3rd, then no matter what, he will end up with an unfair deal.

The way to fix the solution is to not let Dick think Tom's cut was unfair. This is achieved by allowing Dick to "trim" Tom's 1/3rd version and adding that into the 2/3rd share before making the second cut. Now if Harry thought Tom's cut was fair, then he will pick from Dick's cut since he thinks that is bigger. Tom will also pick from Dick's cut. And Dick can take the "trimmed" 1/3rd since he thought that was a fair 1/3rd. The deal with this solution is it will take 3 cuts (one by Tom, one "trim" by Dick, and another by Dick). If you generalize this to the n player version, then this algorithm will take n*(n-1)/2 cuts.

This problem has been addressed by a lot of mathematicians in history. The first (erroneous) solution for the 3 person problem was provided by Robertson and Webb. The corrected n*(n-1)/2 cuts solution was provided in 1944 by Hugo Steinhaus. Since then advanced concepts in mathematics have chosen this problem to purvey their theories. We'll see a non-envy version of this problem later in this post. Fair division is a very practical problem in the real world. Be it geek-ish like bandwidth sharing, or esoteric like dividing Jerusalem and West Bank. As a twist, the problem gets very intricate and interesting when different parties believe different parts of the cake are better than other parts.

We extend the original problem to fair division without envy. In the earlier case, everyone got a fair deal, but we potentially still had people imagining that others got more than them. In fact, that was the case in all solutions except the 2 person scenario. The two person "I cut, you choose" scenario is guaranteed to be envy-free.

Lets define a cake-division as envy-free if no one thinks that someone else got a larger piece than they did. An envy-free division is always guaranteed to be fair. However a fair division need not be envy-free at all.

Lets look at a solution for the 3-person case envy-free fair division -- same drill: Tom, Dick, and Harry want to divide a cake fairly between them in an envy-free fashion -

• First, Tom divides the cake into three parts which he thinks are equal 1/3rds.
• Next, (a) if Dick thinks the two largest pieces are equal, he does nothing, otherwise (b) Dick trims one piece to achieve two equal largest pieces.
• Now, Harry, Dick, and Tom in that order pick. If Dick trimmed a piece earlier, then he has to pick the trimmed piece unless Harry has already picked it.

At this stage, you have an envy-free fair division of three pieces. What is leftover is the problem of dividing the "trimming".

• Now, if Dick didnt trim, then there is nothing to do. If he did trim, then either Dick or Harry took the trimmed piece. We'll assume Dick took the trimmed piece. (Substitute Harry for Dick in the rest of the solution if Harry took the trimmed piece.) Dick now divides the "trimming" into three equal parts.
  
• Harry, Tom, and Dick in that order now pick. Harry picks first, so he's not envious at all. Tom picks next, but he's absolutely not envious since this trimming is already a bonus for him -- he thought his first three way cut was already equal 1/3rds. Dick picks the last one, but he isnt envious either since he divided the "trimmings" 3-ways.
  

When you extend this to a n-person scenario, the problem becomes extremely complicated. Found a wikipedia link on Fair Division. Wikipedia talks about many versions of the problem and how after a century of solutions Steven Brams and Alan Taylor finally solved it in 1995. That was the solution for the general n-person envy-free fair division. That came 30 years after the first 3-person envy-free fair division solution. The first I came across this problem was when I heard Alan Taylor give a rather animated talk on this at Yale back in 1998.

a new Mersenne prime

A new Mersenne prime was discovered a few weeks ago, the largest prime number discovered to date --- "2 raised to the 30,402,457th power minus 1".

Mersenne primes are a special category of primes expressed as 2 to the "p" power minus 1, in which "p" also is a prime number. The theorems around mersenne primes turn out to be so aesthetic, that they had to have "come straight from the book". :)

Mersenne primes have a very interesting history:
[a] pre 1532
Mathematicians conjectured that all (2^n - 1) were primes for every prime n.

[b] 1532
Regius proved that (2^11 - 1) was not a prime.

[c] 1600
Cataldi proved (2^17 - 1) and (2^19 - 1) were both primes and conjectured that the theorem was true for primes 23, 29, 31, and 37.

[d] 1640
Fermat proved Cataldi was wrong about 23 and 37.

[e] 1644
Mersenne conjectured the theorem was true for primes 2, 3, 5, 7, 13, 17, 19, 31, 61, 127 and 257 and false for any other prime less than 258.

[f] 1947
It took excess of 3 centuries for folks to come to a mathematical conclusion about Mersenne's conjecture. Turned out, his conjecture was pretty close. He was right about all this primes, and had missed out 89 and 107. Took a lot of mathematicians, from Euler to our very own Ramanujam to verify Mersenne's theorem.

Subsequently, various folks have come up with tests for checking primality based on Mersenne primes (including the non-exponential primality test from IIT Kanpur) and with all the computing power available for brute force testing, what was discovered recently was the 43rd Mersenne prime.

Back in 1965 or so, math dept of Urbana cracked the Mersenne prime for n=11213. They were so kicked, they made a stamp out of it and would imprint it on all postal letters going out of the Urbana math dept (see below). This of course lasted until 1976 when Urbana math dept cracked the four-color theorem and proved it correct. After that for a while, the four-color theorem was on the envelopes.


More details about Mersenne Primes here

fun stuff.
Vinod