The Mathematician as an Explorer

Editor's note: This article originally appeared in the May 1961 issue of Scientific American. Sherman K. Stein is currently professor emeritus of mathematics at University of California, Davis. He is the author of several popular books on mathematics published after this article; his latest is "Survival Guide for Outsiders: How to Protect Yourself from Politicians, Experts and Other Insiders: (BookSurge Publishing, 2010).

The nature of mathematics is elucidated by one mathematician's account of how a memory word used by drummers in ancient India led him to the classic problem of the traveling salesman's route

Mathematics, like every branch of knowledge, is the product of the interplay between past and present, between accumulated knowledge and curiosity, between an autonomous structure and the tastes and needs of the time. What one age considers a pressing question, another may not ask at all. The pure mathematics of one era may be applied in another, perhaps centuries later.

A problem with which I recently tangled illustrates these aspects of the growth of knowledge, and its solution captures the adventurous flavor of mathematical research. Pushing into the unknown, the mathematician is an explorer who is likely to find what he did not seek and who cannot predict how others will use his discoveries.

This particular adventure began when the composer George Perle told me about an elaborate theory of rhythm that had been developed in India more than a thousand years ago. "While reading about this theory," he said, "I learned my one and only Sanskrit word: yamátárájahánsalagám." I asked him what it meant.

"It's just a nonsense word invented as a memory aid for Indian drummers."

"If a drummer can remember that, " I replied, "he can remember anything. "

"There is a lot in those ten syllables, " said Perle. "As you pronounce the word you sweep out all possible triplets of short and long beats. The first three syllables, ya má tá, have the rhythm short, long, long. The second through the fourth are má tá rá: long, long, long. Then you have tá rá já: long, long, short. "Next there are rá ja bhá: long, short, long. And so on." I wrote down the word and saw that what Perle said is true. Each successive triplet of syllables displays a different pattern, and the whole word displays all the possible patterns, giving each one once and only once. As a mathematician I was fascinated to find that such a sequence could exist.

That night I returned to the ancient word. To strip it of irrelevancies I replaced the syllables with digits, letting 0 stand for short beats and 1 for long. In this notation yamátárájahánsalagám became 0111010000l.

Staring at the simplified string for a while, I noticed a lovely thing. The first two digits are the same as the last two; so if I bent the string into a loop, it would look like a snake swallowing its own tail. That is, the last 01 could be placed over the first 01, so that the two pairs of digits would merge into a single pair. Instead of a line of 10 digits I now saw a circle of eight.

I could begin anywhere on this "memory wheel" and move around it in either direction, sweeping out triplets of 0's and l's. Starting at the top and reading clockwise, for example, gave 011, 111, 110, 101, 010, 100, 000, 00l.

The next thing that occurred to me, as it would automatically to any mathematician,was to generalize what I had found. Is there a "word" for listing all quadruplets of 0's and l's once and only once? For quintuplets? For groups of any size? And if so, does the snake always swallow its tail?

Before attacking the problem for quadruplets it seemed sensible to go back and look at couplets. Is there a word that lists each of the four couplets 00, 01, 10, 11 exactly once? Does it close up on itself? 'Writing down the sequence 0011, I saw that I already had the three couplets 00, 01, 11. Adding one 0 more, to form 00110, gave the final couplet: 10. I noted that the first and last digits are O's, so that the snake swallows its tail. The five-digit word could be bent into a four-digit wheel containing each couplet once and only once.

Now I was ready to take on the quadruplets. I began methodically by listing all the possible groups of four digits composed of 0's and l's. To do this I first wrote down the eight triplets and placed a zero in front of each. This gave me all the quadruplets beginning with 0. Then I repeated the triplets and preceded them with l's, obtaining the quadruplets beginning with 1. Since the list contained 16 quadruplets, I saw that a memory word to sweep out each of them once (if it exists) must have 19 digits. The first four digits make one quadruplet, and each of the next 15 digits completes another.

Now to find the word. Somewhere in it there would have to be a string of four 1's and somewhere four 0's. Why not put them together and see what would happen? I wrote down the eight symbols 11110000. Then I checked off my list the five quadruplets it contained: 1111, 1110, 1100, 1000, 0000. So far so good. To avoid getting 0000 twice, I next had to add a 1, obtaining 111100001. I checked off 0001 on the list. Adding 010 produced three more quadruplets, all new, and brought the sequence to 111100001010.

From here I proceeded one digit at a time, checking the list to make sure there were no duplications. At each of the next three places the choice was clear: one of the digits would form a quadruplet already checked; the other would not. I had then reached the 15-symbol word: 111100001010011.

Only four to go. Considering the next digit, I found that neither 1 nor 0 provided a duplication. But a 1 would lead to trouble in the following place, where either 0 or 1 would then produce a duplication. I was afraid I might not be able to reach 19 symbols after all. It turned out, however, that a zero in the 16th position involved no such difficulty, and the last three places again presented unambiguous choices. I had my word of 19 symbols, containing each of the 16 quadruplets precisely once: 1111000010100110111.

As soon as I had finished, I looked at the first three symbols and the last three. They were the same. So this snake also could swallow its tail. The 19-symbol word could be bent into a wheel of 16 symbols.

Inspired by this success, I decided that there must be memory words for quintuplets, sextuplets and so on. Furthermore, I felt sure they would all close up into wheels. It was time to stop experimenting, however, and look for a proof of the conjecture.

Grappling with the problem, I began to look at the Indian memory word in a slightly different way, concentrating on the eight overlapping triplets it contains [see bottom illustration at right]. In this light the word appeared as a means of arranging the triplets so that the last two symbols of one are the same as the first two of the next. Suppose the word had not been invented. How would one have gone about finding one? I decided to spread the triplets over a piece of paper and connect the appropriate pairs with arrows. That is, I would draw an arrow from one triplet to another whenever the last two symbols of the former were the same as the first two symbols of the latter; for example, 001 → 010 and 001 → 011. After moving the triplets and arrows around a little to make a simple pattern, I obtained the diagram on page 153.

As I gazed at the configuration, I suddenly saw it as a map in which the arrows were one-way roads and the triplets were towns. The problem of arranging the eight triplets into a memory word could now be stated in terms of a different kind of drummer: a traveling salesman who is looking for a route over the one-way roads that will take him through each town just once. With the help of the Indian memory word I traced one possible route. As the illustration on page 154 shows, the "town" in which the journey ends is adjacent to the one in which it starts. There is a section of road that will take the salesman from the finishing point back to the start. This, of course, reflects the fact that the memory word closes into a wheel.

Clearly the same scheme would apply for overlapping couplets, quadruplets or groups of any size. The general problem had been translated into a new language. The question "Is there always a memory word?" now read "Is there always a route for the salesman?" The question "Does every memory word close up on itself? " now read "Does the salesman always finish his trip in a town adjacent to the town in which his trip began?"

Unhappily the translation did me no good. I had absolutely no luck in solving either of the salesman problems. There is no known way other than trying all paths to tell whether a highway system has a route passing just once through every town.

After several days without progress I had no choice but to put the matter aside and worry about other things. A few months later, as I was leafing through the 1946 volume of The Journal of the London Mathematical Society, I saw a diagram that resembled my highway system. It appeared in a paper entitled "Normal Recurring Decimals, " by 1. J. Good. A quite different topic had brought Good to a consideration of the memory wheel problem-and he had solved it! He was chiefly interested in showing how to produce an endless string of 0's and 1's in which each of the possible sextuplets of 0's and l's appears with equal frequency. His solution was perfectly general and applied to groups of any size. He noted further that "the result has an application to the construction of teleprinters that use alphabets whose letters consist of a finite number (usually five or six) of 0's and l's. "

Good also had recognized that the problem is related to a highway system, but his system was different from mine. r had seen the triplets (or groups of any other size) as towns and the roads between them as representing overlaps. Good saw it the other way around: the triplets themselves are roads and they join towns made up of pairs of digits-the overlapping portions of the triplets. For example, the highway 011 runs from the town 01 to the town 11. To put it another way, there are four towns: 00, 01, 10, 11. One of these is joined to another if the last digit of the former is the same as the first digit of the latter: 01 is joined to 11 by 011.

A glance at the diagram makes it clear that two roads lead into, and two out of, every town. They all represent triplets, and every incoming triplet overlaps every outgoing triplet for every town. This means that if a person-say an efficient highway inspector−could find a route taking him over each road just once, he would in effect trace a memory wheel. For example, suppose the inspector began at town 01. He could follow a route consisting of highways 011, 111, 110, 101, 010, 100, 000 and 001. The trip is, of course, exactly the one given by yamátárájahánsalagám. Notice also that the last highway, 001, leads into the first one, 011.

Now it happens that the problem of whether the efficient inspector always has a route through a highway system such as Good's was solved some 200 years ago by Leol)hard Euler, the renowned Swiss mathematician. Euler's attention had been attracted to a puzzle known as the problem of the Koenigsberg Bridges. "In the town of Koenigsberg," he wrote, "there is an island called Kneiphof, with two branches of the river Pregel flowing around it. There are seven bridges crossing the two branches. The question is whether a person can plan a walk in such a way that he will cross each of these bridges once but not more than once.... On the basis of the above I formulated the following very general problem for myself: Given any configuration of the river and the branches into which it may divide, as well as any number of bridges, to determine whether or not it is possible to cross each bridge exactly once." [See "Leonhard Euler and the Koenigsberg Bridges"; SCIENTIFIC AMERICAN, July, 1953.]

Euler broke down the problem into several cases, the last of which was: "If, finally, there is no region with an odd number of approach bridges, the required journey can be effected, no matter where it begins" [and must end where it begins] .

I shall not present Euler's proof here. It is obvious, however, that the inspector's highway system satisfies the condition just quoted. Each town has exactly two roads entering it and two leaving, or, in Euler's terms, each region has four bridges. In the case of quadruplets the towns are the eight triplets and the roads are the 16 quadruplets: there are two entrances and two exits to each town.

Since the salesman's problem is equivalent to the inspector's, he also has a route and his journey must end in a town adjacent to the one in which he starts. Thus I had quite unintentionally found a special class of highway systems for which the salesman has a route, and so had shed some light on a famous problem raised by the Irish mathematician William Rowan Hamilton in 1859: Which highway systems have a salesman route? Curiously, in this special class the salesman finds a route by pretending to be a highway inspector of a related but quite different highway system.

The story does not end here. Through Mathematical Reviews I learned that other mathematicians in various parts of the world had been involved with the memory-word problem in one guise or another. Twelve years before Good had published his paper M. H. Martin had solved the problem in a completely different way; he had been led to it by a problem of dynamics. D. Rees, in a paper published adjacent to Good's, solved the problem by considering certain divisors of polynomials of the type X^m 1. In 1951 a Russian mathematician who was studying the fractional part of multiples of numbers described an entirely different technique for constructing memory wheels. K. Posthumus, a French engineer working on the theory of telephone circuits, posed another question about memory wheels: How many different wheels are there for couplets, triplets, quadruplets and so on? He found that there is one for couplets, two for triplets, 16 for quadruplets, 2,048 for quintuplets, and he guessed at a general formula for groups of any size (n-tuplets) : 2 raised to the power 2^n−l−n. In 1946 a Dutch mathematician proved the conjecture.

I learned also that memory wheels have found technological applications. A computer made in Czechoslovakia employs a memory wheel of 1,024 symbols to search through an equal number of storage locations on a memory drum. And in the Damodar Valley near Calcutta (the wheel of fate has now made a full turn) a memory wheel in a central office scans automatically transmitted reports from 64 rain gauges.

This has been a fable with many morals. It deals with a question that could have been raised a thousand years ago in India but was not. And little did Euler dream that his work on a puzzle would be of practical use in the 20th century. Moreover, the variety of applications reflects both the mathematical mood of our time and the fantastic amount of mathematics being created all over the world. The fact that so many of the workers were ignorant of the others' results, and therefore duplicated much effort, points to another problem: how to record the myriad discoveries constantly Rowing into man's store of knowledge. Above all, the story shows the power of curiosity that makes men explore the unknown to find the truth, whether it be of stars, continents or mathematics.