Shrikhande, “Euler’s Spoiler”, Turns 100

  •  
  •  

courtesy The Shrikhande Family
courtesy The Shrikhande Family

Relatives, well-wishers and dignitaries kept arriving to greet Professor Shrikhande. Seated on the lawns, he would adjust his hearing aid—trying to hear over the firecrackers in the background—thank them and smile, and now and then burst into a hearty chuckle, trying not to look in the direction of the intense light drenching the table.

Sharadchandra Shankar Shrikhande, celebrating his one hundredth birthday on 19 October 2017, wasn’t too keen to remain in the spotlight. The bright light on the pole was turned away, but visitors kept coming to greet him and seek his blessings, some aware of his great mathematical achievements—in particular, the one that ensured his name would be associated with Euler, one of the greatest mathematicians in history. It was fifty eight years ago that Shrikhande, along with his mentor R.C. Bose and their collaborator E.T. Parker, proved Euler wrong and made the headlines.

Leonhard Euler courtesy Emanuel Handmann via Wikimedia Commons

Late in his life, the legendary Swiss mathematician Leonhard Euler (1707–1783) began a long paper [1] pondering a puzzle he couldn’t find an answer to. Although he was almost completely blind by then, his already prodigious productivity had increased, distractions having been reduced. He had always made the most of his phenomenal memory and ability to calculate in his head and, after his loss of vision, he used a scribe to record his discoveries. The puzzle he was considering was this: Imagine that there are 36 officers belonging to six different military regiments, each regiment having six officers of different ranks. How does one arrange them in the form of a square such that each row and column has six officers, and no rank or regiment appears more than once in a row and column?

Mathematicians, professional and otherwise, like to ponder such puzzles for recreation, and not a few mathematical gems have emerged from such playing around. In many such puzzles, a simplification helps clarify the picture. Consider nine officers instead of 36, belonging to three different regiments, each regiment having one officer of each of the three ranks. The problem, as before, is to arrange them in a square such that no rank or regiment is repeated in a row or column. This is actually two problems in one. One can arrange the nine officers such that no regiment—labelled 1, 2 or 3 below—is repeated in a row or column. Such an arrangement is called a Latin square (since Euler originally used Latin letters instead of numbers).

1 2 3 2 3 1 2 3 1

One can also arrange the officers such that no rank—red, green or blue below—is repeated in a row or column to get another Latin square.

How does one satisfy both the requirements—neither rank nor regiment repeated in a row or column? If we combine, or superpose, the two squares, we get another square as below, where the numbers are now coloured.

1 2 3 2 3 1 2 3 1

In the square above, both requirements are satisfied. And there is only one red 1 and only one green 2; only once does each such combination of rank and regiment appear in the square. Two such superposed Latin squares, therefore, are called orthogonal to each other.

Orthogonal Latin squares were, in fact, around much before Euler. Amulets bearing Latin squares were known in medieval Islam, circa 1200 [2]. Choi Seok-Jeong (1646–1715), a Korean government official and mathematician, used orthogonal Latin squares of order 9 to construct magic squares—one in which the entries in any of the rows or columns or diagonals add up to the same number. (Euler himself was interested in magic squares.)

The pair of Latin squares in the above example is of order n = 3. Euler observed that a similar exercise can be done for orders 4 and 5, and also whenever n is an odd number or is divisible by four. Now, the 36 officers problem, in the language of Latin squares, is to find a pair of orthogonal Latin squares of order 6. But Euler found himself unable to do it for n = 6. He couldn’t find an arrangement to solve the puzzle, and concluded that one didn’t exist at all (although his proof wasn’t fully correct). He went on to conjecture that no solutions existed for a number that, like six, left a remainder of two when divided by four. These are numbers such as 10, 14, 18, 22, and so on, which are called “oddly even” numbers. (There are no orthogonal Latin squares of order 2 as well.)

Euler conjectured that no orthogonal Latin squares existed for oddly even numbers

This conjecture by Euler was in 1782. In 1901, a French mathematician named Gaston Tarry (1843–1913) proved that n = 6 was indeed impossible by laboriously checking all possible cases. But Euler’s conjecture that orthogonality was impossible for all oddly even numbers remained to be resolved. Until 1959, when R.C. Bose, Shrikhande and E.T. Parker disproved the conjecture.

“The suddenness with which complete success came,” Bose recalled later [3], “in a problem which had baffled mathematicians for over one and three-quarters centuries startled the authors as much as anyone else. What makes this even more surprising is that the concepts employed were not even close to the frontiers of deep modern mathematics.”

The result was announced in the annual meeting of the American Mathematical Society held in New York in April 1959. “Bose, Ernie (Parker) and I,” Shrikhande said later [4], “had the rare privilege of seeing our works reported on the front page of the Sunday Edition of the New York Times of April 26, 1959.”

The three of them, noted the NYT report [5], “are now known among their colleagues as ‘Euler’s spoilers’”.

§

Shrikhande and Bose were, at the time, at the University of North Carolina, Chapel Hill in the Department of Mathematical Statistics, which had been founded in 1946 by the statistician Harold Hotelling (1895–1973). Bose had been a faculty there since 1949, and Shrikhande, who had joined for a PhD in 1947, had been Bose’s first PhD student. But his path hadn’t been straightforward. Born on 19 October 1917, the fifth of ten siblings, in Sagar, now in Madhya Pradesh, his family faced severe financial difficulties. Despite that, Shrikhande’s father, who worked at a flour mill, was determined to educate his children. Shrikhande did well academically and won scholarships that helped him complete his B.Sc. Honours at the Government College of Science (now known as the Institute of Science) in Nagpur with a first rank and a gold medal.

courtesy The Shrikhande Family
courtesy The Shrikhande Family

“At this point of time,” he wrote in an autobiographical essay [6], “I was badly in need of a gainful employment, which however was not available.” Unable to find a job, he instead made his way, in January 1940, to Kolkata where financial assistance was available to join the Indian Statistical Institute (ISI). Founded by P.C. Mahalanobis (1893–1972), ISI at that time “was located in four of five rooms in the Presidency College” where Mahalanobis was a professor of physics. But those rooms housed a hotbed of young talent in statistics many of whom would go on to make major contributions. One of them was Raj Chandra Bose (1901–1987), whom Shrikhande describes as “the major architect of my research involvement in combinatorics”, the field of mathematics that studies how to combine different things, whether certain combinations are possible at all, and what combination is most appropriate given certain constraints.

After a year at ISI, Shrikhande had a short-lived appointment at the college in Jabalpur where he had done his Intermediate studies (the equivalent of two years after Class 10 today) and then joined as a lecturer in mathematics at the Government College of Science in Nagpur. But he kept making trips to Calcutta in the early 1940s to work with Bose, who introduced him to the theory of statistical design of experiments, a field where Latin squares proved to be more than amusement. In the 1920s, R.A. Fisher (1890–1962), the pioneering British statistician and biologist, had applied them to the design of field experiments in agriculture. His ideas were later developed by Bose.

Suppose one wishes to test the effects of three different agricultural fertilizers on the growth of a crop. Now, it is likely that the fertility of soil in different patches of a large plot of land varies naturally, perhaps because the amount of moisture in the soil varies. How does one test how good the fertilizers are while accounting for this natural variation in fertility of the soil? Fisher’s solution to this problem was to divide the field into cells of a three-by-three square and apply the three fertilizers in the pattern of a Latin square of order 3 (such as the one shown previously). Because of this pattern, one can use statistical analysis to eliminate the bias due to variation in natural soil fertility along a row or column of the field.

Bose introduced Shrikhande to the theory of statistical design of experiments, a field where Latin squares proved to be more than amusement

Now, if instead of one variety of crop, what if we had three? The solution to accommodate this variable is to use a Latin square of order 3 orthogonal to the earlier one. The first Latin square tells us where the three different fertilizers are to be applied and the second Latin square tells us where the three different varieties of the crop are to be planted. The orthogonal Latin square obtained by combining them would show the combination of crop and fertilizer to be applied in each cell.

Raj Chandra Bose MacTutoraHistoryOfMathArchive, University of St. Andrews
R.C. Bose MacTutor History Of Math Archive, University of St. Andrews

In fact, one can accommodate more variables by superposing additional orthogonal Latin squares. This is useful in the design of experiments wherever there are many variables involved, such as in medical research where one may need to test a medical treatment for its efficacy on patients of different age, weight, stages of a disease and so on, while needing to eliminate any effects due to such unavoidable variations. For a given order n, however, there can be a maximum of n -1 mutually orthogonal Latin squares—“mutual” because any pair of them will be orthogonal. But it’s not necessary that the entire set of n - 1 mutually orthogonal Latin squares exist. If they do exist, they are said to form a complete set of mutually orthogonal Latin squares. Such a complete set can be constructed if n is a prime number—divisible only by one and itself, such as 3,5,7,11 and so on—or a power of a prime number. In 1938, Bose showed [7] how to construct a complete set of mutually orthogonal Latin squares in such a case, a result that, unknown to him, had been discovered earlier in 1896 by E.H. Moore (1862–1932), and independently by W.L. Stevens in 1939 [2]. In this work, he was influenced by F.W. Levi, a German Jewish mathematician who, having fled the Nazis, became the head of the Department of Mathematics at the University of Calcutta. (Levi had shown that an attempted proof of Euler’s conjecture by H.F. MacNeish, an American mathematician, was wrong. Others had made unsuccessful attempts earlier too.) Bose also showed that a complete set of mutually orthogonal Latin squares is essentially the same as a finite projective plane, a concept from geometry.

For mathematicians, there are few things more beautiful than such surprising connections between disparate areas of mathematics. What’s more, projective geometry too, like Euler’s conjecture, had what would seem an unlikely provenance—Renaissance artists. They were interested in perspective, in representing three-dimensional objects and scenes on the two-dimensional surface of their paintings. To draw, for example, square-shaped tiles on a floor, they would not paint them all to have the same size with their sides parallel to each other—this would look like a view from above. Instead, two of the opposing sides of a tile would be drawn as if they were approaching each other, with the tiles further away drawn smaller.

Bose showed that a complete set of mutually orthogonal Latin squares is essentially the same as a finite projective plane

This effect can be readily seen from an image of railway tracks—the parallel tracks, as they recede, appear to meet at the horizon. Projective geometry takes this idea seriously and imagines a point at “infinity” where a family of parallel lines “meet”. Or to put it differently, a point at infinity can be thought of as a point which lies on each member of a family of parallel lines. This trick ensures that any two lines on a plane, parallel or not, will meet. Different families of parallel lines meet at different points at infinity, and these points would make up a line at infinity. Such a line at infinity, along with an ordinary (finite) plane, makes up a finite projective plane. (Mathematically, a finite projective plane has the property that lines and points in it are dual to each other—one can exchange their roles and the plane and its properties would remain the same. Any two lines, for example, intersect at only one point, and any two points lie on only one line.)

If there exists a finite projective plane of order n, which is a prime or a prime power, Bose showed, a complete set of mutually orthogonal Latin squares exists for order n. Whether this condition is necessary—that is, is there an n which is not a prime or a prime power for which one can find a complete set of mutually orthogonal Latin squares—is unknown. (This is equivalent to the question of whether a projective plane of non-prime power order exists.) We do know [2] that there exists no complete set of mutually orthogonal Latin squares for order 10, but since 10 is not a prime or a prime power, the problem remains open.

Bose had become famous for his work on block designs by the time he left Calcutta for North Carolina. Shrikhande was already there, having been selected, in 1947, for a government scholarship programme that sent Indians abroad for higher studies. He was later joined by his wife, Shakuntala, whose heart he had won over a game of badminton in Nagpur, and their children. Bose too arrived, but then left, only to return as permanent faculty in 1949. “His arrival there proved a turning point in my academic career,” wrote Shrikhande. [6] “Under his inspiring guidance I was fortunate to complete my [PhD] thesis in about a year.” Shrikhande found time to interact with and help his fellow students too. Another student of Bose at the time, K.A. Bush, recalls that a particular affinity developed between him and Shrikhande. “I turned to him for support,” wrote Bush in an essay commemorating Shrikhande’s work [8], “because I instinctively recognized his compassionate nature almost from our first meeting.” (There were other Indians too in the Department who would go on to make a name for themselves. R.R. Bahadur (1924–1997) and Gopinath Kallianpur (1925–2015), who would later become Director of ISI, were also students. S.N. Roy (1906–1964) joined later as faculty.)

Bose’s “arrival there [Chapel Hill] proved a turning point in my academic career”, wrote Shrikhande

Shrikhande returned to India in 1953, to his position at Nagpur, till 1958 when he resigned and accepted a visiting position at Chapel Hill. “My two years stay there till 1960 was the most productive period of my research career,” he would write later [6].

§

Mathematicians, when unable to make progress on a particular problem, sometimes find it useful to consider related problems. For Euler’s conjecture, the first chink appeared via a related conjecture. H.F. MacNeish gave a lower bound [9] to the number of mutually orthogonal Latin squares of any order n: it would be one less than the smallest prime number that appears when n is written out as a product of its prime number factors (called its prime power decomposition). Any number can be written as the product of prime numbers. The number 22, for example, is 2 times 11, both prime numbers. For 22, MacNeish guaranteed, the minimum number of mutually orthogonal Latin squares was one, meaning there’s at least one Latin square of this order. He then conjectured that this lower bound is the same as the upper bound. Thus, if MacNeish’s conjecture (later worked on by H.B. Mann) was true, then the maximum number of mutually orthogonal Latin squares of order 22 (which leaves remainder two when divided by four), would have been one—there would be only one Latin square of that order, implying that Euler’s conjecture would be true. Proving MacNeish’s conjecture would mean proving Euler’s conjecture, but disproving MacNeish’s conjecture wouldn’t necessarily disprove Euler’s conjecture.

Parker, nevertheless, saw an opening. He was, at the time, working at Remington Rand Univac, an early computer company. His work on this problem, his sister Edythe Parker Woodruff later wrote, “was done entirely outside of company work; it was his recreation. He did it out of his pure love for the subject.” Parker found [10] four mutually orthogonal Latin squares of order 21 (we now know there are five [2]), whereas there should have been only two according to MacNeish’s conjecture.

He had used a method used to design statistical experiments called balanced incomplete block designs, which Bose had contributed greatly to. Suppose, in the earlier example of the testing of different fertilizers on a crop, we divide a plot into three columns because we have reason to believe that the soil fertility is constant in a given column but varies between columns. How does one then test the effect of three different fertilizers on a given crop, eliminating the natural fertility variation between columns? One could divide each column into two and use two fertilizers in each column. For example, one could have the following arrangement—the first column has fertilizer 2 and 3 applied, the second column has fertilizer 1 and 3 applied, and the third column has fertilizer 1 and 2 applied. This is a balanced incomplete block design—it’s “balanced” because each pair of fertilizers has the same probability of occurring in this scheme, and “incomplete” because in no column do we have all three fertilizers used. Today, Latin squares and balanced incomplete block designs have found applications as varied as communication systems, cryptography, error-control coding, and clinical trials of medicines.

Parker believed his disproof of the MacNeish conjecture to be “an unimportant near miss”

Parker believed his disproof of the MacNeish conjecture to be “an unimportant near miss” [5]. But “Parker’s result”, as a later paper he wrote with Bose and Shrikhande noted, “though it did not disprove Euler’s conjecture threw serious doubts on its correctness.” [11] Building on this, Bose and Shrikhande constructed orthogonal Latin squares of order 22 [12, 13]. They used a generalization of balanced incomplete block designs called pairwise balanced designs.

Shrikhande and Bose at workcourtesy The Shrikhande Family
Shrikhande and Bose at work courtesy The Shrikhande Family

Parker became aware of this work, and he came up with two orthogonal Latin squares of order 10 through a different method [14]. There ensued “feverish correspondence” [15] between the three mathematicians, culminating in their proof that there did indeed exist orthogonal Latin squares of all orders other than six (and two). Euler was wrong.

Their proof had bridged geometry, combinatorics and statistics. “It is a striking example of the unity of science,” said Bose of this famous result [3], “that the initial impulse which leads to a solution of the problem propounded by Euler, came from the practical needs of agricultural experimentation, thus reversing the more usual passage from basic to applied knowledge.”

The disproof of Euler’s conjecture bridged geometry, combinatorics and statistics

Later in his life, in an autobiographical essay [16], Bose recalled what happened the day after the result was announced at the AMS meeting. “The science editor of the New York Times came to interview us,” he wrote, “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.’”

Shrikhande’s second son, Mohan, was in school when his teacher stopped him on the stairs and asked him if he had seen that day’s New York Times. In the news report, recalled the late Dutch combinatorist J.J. Seidel (1919–2001) in an address on Shrikhande’s 70th birthday in 1987 [4], “The three scientists stood in front of, and partly made invisible a huge 10 \times 10 tableau showing the Latin square that spoiled Euler’s conjecture. The next day, dozens of school-boys had computed the missing pieces.”

§

As his children—Mohan, Asha and Anil—grandchildren, and great-grandchildren took to the stage to speak lovingly of how deeply he had influenced them, and how grateful they were for his presence and openness, Shrikhande’s life flashed by on the screen behind. Shrikhande the young man travelling to distant shores, the loving husband and father, the family man who remained close to his siblings, the mathematician and mentor, the yoga practitioner, and the doting grandfather and great-grandfather. From Nagpur arrived a message from his academic descendants, expressing their gratitude for having started and sustained research in statistics and combinatorics in that city by founding the Department of Statistics at the Institute of Science in Nagpur in 1955. All these facets of “Gramps”, as his grandchildren call him, were not orthogonal to each other but blended harmoniously.

courtesy The Shrikhande Family
courtesy The Shrikhande Family

After his famous work, Shrikhande returned to India in 1960, joining Banaras Hindu University, which he left in 1963 to join the University of Bombay where he was the first head of the Department of Mathematics and the Director of the UGC Centre for Advanced Study in Mathematics. Navin Singhi, who did his PhD with Shrikhande at the University of Bombay in 1972–73 and went on to collaborate with him and Bose, remembers Shrikhande’s simplicity and unassuming style, and also his focused approach to his work. As head of the department, he had to do a lot of administrative work, his office often a continuous stream of visitors. But Shrikhande nonchalantly returned to his work as soon as he had disposed off such frequent interruptions.

His students remember his endearing personality and habits. “He used empty envelopes left from incoming mails for writing research papers. He almost never used normal paper or notebook to write down,” Singhi recalls. “As a chairman, he used to get a lot of mails. He had developed his own techniques on how to open an envelope of incoming mail carefully so that its inside could be used to write mathematics. These covers which most people throw away were the ones which carried most of Shrikhande’s research work, with me and with others.”

The late Vasanti Bhat-Nayak, who did her PhD with Shrikhande at the University of Bombay, had joined the Department as a lecturer after an unhappy spell at the Tata Institute of Fundamental Research. She felt welcomed by the cordial environment Shrikhande had nurtured and his gentle encouragement that restored her shattered confidence. “Shrikhande would always introduce me to others as his colleague and not as his student,” she wrote in a commemorative essay. “I was never ridiculed even if I made a mathematically wrong statement.” She later became head of the Department herself.

Shrikhande made many other notable contributions to combinatorics and design theory. In particular, while investigating Latin squares, he published another landmark paper [17] in the same year, 1959, on what has come to be known as the Shrikhande graph, which has connections to algebra, group theory and topology. “All his work,” said Sharad Sane, a combinatorist at IIT Bombay, “had the hallmark of being simple and elegant, yet deep.” They echoed the words of the late statistician J.N. Srivastava (1933–2010) who, like Shrikhande, did his PhD with Bose and wrote that [8], “In any given combinatorial setting, Professor Shrikhande has the knack of discovering questions which are deep, elegant and significant. This gives a fundamental character to all his work…”

Shrikhande’s work has had a deep influence on combinatorics and design theory, and he has mentored many mathematicians in India and abroad

Mohan Shrikhande, a renowned combinatorist himself, and who retired from the Central Michigan University in 2015, did not begin his career as a combinatorist, having done his PhD in a different area. “I wasn’t particularly interested in combinatorics until after my PhD,” he said, “which was when I read a paper my father sent me.” He went on to co-author papers with some of his father’s colleagues and students, including Bose, Singhi and Sane.

Sane and S.B. Rao—former director of both the Indian Statistical Institute, Kolkata, and the C.R. Rao Advanced Institute of Mathematics, Statistics and Computer Science, Hyderabad—had both worked with Shrikhande at the University of Bombay, and, at the birthday party, spoke of the deep influence his work has had on combinatorics and design theory, and the many mathematicians he had mentored, in India and abroad.

And they spoke of his humility. The late Canadian mathematician Ralph G. Stanton (1923–2010) found this out when he first met Shrikhande at the American Mathematical Society meeting where the disproof of Euler’s conjecture was announced. Stanton found Shrikhande “much more interested in discussing other mathematical topics in design theory than in dwelling on his achievement.” [8] As Srivastava wrote, “Many people, in the midst of their achievements, get puffed up. Not so with Professor Shrikhande. There is a certain humility about him which is worth emulating.” Yashodhan Hatwalne, a physicist at the Raman Research Institute in Bengaluru, whose mother was the sister of Shrikhande’s wife Shakuntala, used to take long walks with Shrikhande when they were in the US. He knew about Shrikhande’s fame and achievement. “But he never talked about all this. Not once,” says Hatwalne.

Shrikhande retired in 1978, but accepted the directorship of the Mehta Research Institute (now the Harish-Chandra Research Institute) in Allahabad, 1983–86. After his wife Shakuntala passed away in 1988, Shrikhande lived with his children and grandchildren in the US. He returned to India in 2009, and now lives in Vijayawada, taken care of by the in-laws of Nita Kulkarni, one of his grandchildren, in the ashram they run for underprivileged girls. On his birthday, which also happened to be Deepavali, the festival of lights, the girls sang songs, drew a rangoli in the form of a Shrikhande graph, and prepared a special cake for him.

Shrikhande’s fellow Euler’s spoilers, Bose and Parker, passed away in 1987 and 1991 respectively, but their work has had an enduring impact. “The techniques they developed,” said Sane, “have now become an important part of the study of design theory and combinatorics.”

Shrikhande hasn’t stopped learning. When living with his family in the US, he enthusiastically learnt how to use email, said his grand-daughter Nita. These days, he still enjoys trying to fill in numbers in a square—in the form of Sudoku puzzles, which is just a special kind of Latin square.

“Yeah, I’m trying. But it’s getting very difficult,” he said, laughing.

Portrait by Mohan Raj
Portrait by Mohan R

References

Nithyanand Rao is a science journalist based in Bangalore, and a Contributing Editor of Bhāvanā.