The Euler Spoilers

Executive Punchline: In 1959, mathematicians R.C. Bose and S. S. Shrikhande (later joined by E. T. Parker) published a groundbreaking paper that disproved a 177-year-old conjecture by Leonhard Euler.

The Background: Euler’s Conjecture

In 1782, Polymath Leonhard Euler proposed a problem regarding “Latin Squares”—grids where every symbol appears exactly once in each row and column. He specifically looked at Orthogonal Latin Squares (Graeco-Latin squares), which are pairs of grids that, when superimposed, result in every possible combination of symbols appearing exactly once.

Euler proved these squares existed for odd numbers (n=3, 5) and multiples of four (n=4, 8). However, he could not find one for n=6. He conjectured that such squares could not exist for any number that, when divided by 4, leaves a remainder of 2 (n = 4k + 2), such as 6, 10, 14, and so on.

The Mother of All Counterexamples

The mathematical community believed Euler was correct. However, Bose and Shrikhande developed new methods using combinatorial designs and balanced incomplete block designs.

They first constructed a Graeco-Latin square of order 22, and eventually, working with E. T. Parker, they proved that Euler’s conjecture was false for all n > 6 where n = 4k + 2. They showed that while Euler was right about n = 6 (which was proven impossible in 1901), he was wrong about every other number in that sequence.

The “Euler Spoilers”

The discovery was so significant that it made the front page of the New York Times on April 26, 1959, under the headline “Major Mathematical Conjecture Disproved.” The trio became known as the “Euler Spoilers.”

The photograph from the New York Times (seen above) famously captures Bose, Parker and Shrikhande standing before a chalkboard at the American Mathematical Society meeting, displaying the complex patterns of the 10 x 10 orthogonal Latin square that definitively disproved Euler’s long-standing claim.

Raj Chandra Bose’s Recollection

In his autobiography, Bose wrote about the incident:

Our paper was read at the New York meeting of the American Mathematical Society. The science editor of the New York Times came to interview us, and next morning our picture appeared on the first page of the Sunday edition of the New York Times with a description of our work. I was staying at a small hotel. Next morning when I went to pay the bill, the cashier looked at me and asked, “Is it your picture in the New York Times?” “Yes, it is my picture,” I said. He replied, “You must have done something. The front page of the New York Times cannot be bought for a million dollars.”

The original NYT article

Major Mathematical Conjecture Propounded 177 Years Ago Is Disproved

By John A. Osmundsen, April 26, 1959

Another major mathematical problem - this one 177 years old-has been solved. Its solution was reported at the 55th meeting of the American Mathematical Association, which ended at the New Yorker Hotel yesterday. It was the second such achievement to come out of the meeting, something attending mathematicians called “extremely rare.”

The problem had resisted attempts at solution ever since Leonhard Euler (pronounced “oiler”) stated it in a memoir in 1782. It became famous as Euler’s conjecture. The three mathematicians who finally cracked the problem are now known among their colleagues as “Euler’s spoilers” because they proved the conjecture wrong.

They are Prof. R. C. Bose and Prof. S. S. Shrikhande, both of the University of North Carolina, and Dr. E. T. Parker of the Univac division of Remington Rand. In an interview yesterday the three told how their partly independent and partly collaborative efforts had solved the problem and what its solution meant in terms of both theoretical and practical applications.

They said that the disproving of Euler’s conjecture had more than just passing theoretical interest because many mathematicians - including themselves - had felt for some time that Euler had been correct. Moreover, they said, the consequences of proving the conjecture wrong would find applications in the design of controlled experiments in biology, medicine, agriculture and industry.

Euler’s conjecture deals with Latin squares. These are squares divided into rows and columns of squares. A checker - board is an example. They are called Latin squares because Euler labeled the component cells of the large squares with Latin letters.

According to Professor Bose, the problem arose in the eighteenth century when someone in the Czar’s court wanted to arrange thirty-six officers of six ranks and from six regiments in a square. The men were to be arranged so that every row would contain one officer of each rank and each regiment. The same requirement was made for the arrangement of men in each column. There were to be no repeated combinations of rank and regiment in any of the thirty-six squares.

Euler’s Conclusion

What this amounts to is making two Latin squares of thirty - six cells (six cells across, six cells up and down), one for the arrangement of men according to rank, the other for arrangement according to regiment, and then superimposing the squares. Try as he might, Euler could not make the problem come out right. There was always a repetition of at least one rank - regiment combination in the total square. He concluded that it was im- possible to superimpose two divided squares (called paired orthogonal Latin squares) if the number of cells on each square’s side was even and such that dividing it by four left a remainder of two. Six, for example, when divided by four leaves one with two left over. He showed that a solution was possible for every other case. That, then, was Euler’s conjecture. It meant that it was impossible to match up orthogonal Latin squares with sides of cells numbering six, ten, fourteen, eighteen, twenty-two, twenty-six, etc. Several attempts to prove Euler right had failed, although it was proved in 1901 that Euler had been correct at least in his contention that the problem of thirty-six officers could not be solved. Dr. Parker explained that the higher order squares presented - until the new solution an almost impossible problem. One big research computer, he said, spent more than 100 hours on a single case involving squares with ten cells on a side and could not draw any conclusions.

Solved in 13 Days

He estimated that the best available computer would take at least a century to prove Euler wrong in only that one case. As it turned out, Dr. Parker solved that problem in thirteen days after getting a lead to the way the two North Carolina professors had dealt with cases involving squares of first fifty, then twenty-two cells on a side. Professor Bose said that he and Professor Shrikhande got their first lead in February from Dr. Parker who reported what he believed then to be an “un- important near miss” at disproving Euler’s conjecture.

Dr. Parker’s report gave Professor Bose ideas of general rules to apply to large blocks of cells all at once. Some of these rules came from branches of mathematics called “group theory,” “incomplete block design,” and “finite fields.” Professor Bose suggested the new method to Professor Shrikhande who applied it and solved the problem involving fifty-by- fifty squares within ten minutes.

This proved unwieldy, however, so the two attacked the case of twenty-two-by-twenty-two squares and succeeded again. When Dr. Parker saw that proof he applied methods he had inferred from it to ten-by-ten squares that had defied his two friends. He soon had made the third important chink in Euler’s conjecture.

Subsequent work then proved the conjecture wrong for all other cases. Professor Bose said that their victory would be extremely helpful in designing better controlled experiments in several scientific fields. Latin squares, he explained, are used in research to eliminate extraneous variation.

Executive takeaway: Raj Chandra Bose was a formidable scholar. He started his academic life in the US at age 47. Before that, he spent two decades as a researcher in Calcutta.

Most mathematicians beyond 50 do not discover new things. Bose was different. Along with disproving Euler, he was in the trio of the BCH Codes. BCH (Bose-Ray Chaudhuri-Hocquenghem) codes are powerful, cyclic error-correcting codes used widely in digital systems (CDs, SSDs, barcodes, satellites) to detect and correct multiple random bit errors.

His life was full of drama. The early death of his father caused great hardship for his family - almost to the point of starvation. His research took some great turns from pure mathematics to applied work on coding back to more mathematics. Only recently (under the initiative of Professor Bimal Roy), the Centre for Cryptology and Security at the ISI has been named after him. I will write more about his dramatic life, his connect and eventual disconnect with the ISI at a later date.

Postscript of Fun Trivia: The NYT discovered an error on the front page that persisted for more than a century

For more than a century, there was a numbering error on the front page of the New York Times every day.

In 1999, a news assistant named Aaron Donovan discovered the numbering of the issues was 500 issues off, and the newspaper published a correction on Jan. 1, 2000, explaining the backstory:

On Feb. 6, 1898, it seems, someone preparing the next day’s front page tried to add 1 to the issue number in the upper left corner (14,499) and came up with 15,000. Apparently no one noticed, because the 500-issue error persisted until yesterday (No. 51,753). Today The Times turns back the clock to correct the sequence: this issue is No. 51,254.

Thus an article on March 14, 1995, celebrating the arrival of No. 50,000 was 500 days premature. It should have appeared on July 26, 1996.