American Scientist

Gerrymandering is making headlines once again, with a case already before the Supreme Court regarding partisan redistricting in Wisconsin, and another from Pennsylvania waiting in the wings. At the core of the problem of redrawing congressional districts is the issue of “fairness,” and that is tricky business indeed.

The general subject of fair division has been studied extensively using mathematical tools, and some of that study has proved very useful in practice for problems such as dividing estates or fishing grounds. For gerrymandering, however, there is still no widely accepted fair solution. On the contrary, this past October Pablo Soberón of Northeastern University showed that a biased cartographer could apply mathematics to gerrymander on purpose, without even using strange shapes for the districts. The underlying idea traces back to one of mathematicians’ favorite theorems, which dates back to World War II.

The late 1930’s were devastating years for the Polish people, but they were years of astonishing discovery for Polish mathematicians. Between the rock of the Great Depression and the hard place of impending invasion and occupation by both Nazi and Soviet armies, a small group of mathematicians from the university in Lwów (today Lviv) met regularly in a coffee shop called the Scottish Café to exchange mathematical ideas. These ideas were not the mathematics of complicated calculations (which were then done with the aid of slide rulers), but rather were very general and esthetically beautiful abstract concepts, soon to prove extremely powerful in a wide variety of mathematical and scientific fields.

The café tables had marble tops, and could easily be written on in pencil and then later erased like a slate blackboard. Since the group often returned to ideas from previous meetings, they soon realized the need for a written record of their results, and purchased a large notebook for documenting the problems and answers. The book, kept in a safe place by the café headwaiter and produced by him upon the group’s next visit, was a collection of these mathematical questions, both solved and unsolved, that decades later became known in international mathematical circles as the Scottish Book.

The Ham Sandwich Problem

Problem No.123 in the book, posted by Hugo Steinhaus, a senior member of the café mathematics group and a professor of mathematics at the University of Lemberg (now the University of Lviv), was stated as follows:

“Given are three sets A₁, A₂, A₃ located in the three-dimensional Euclidean space and with finite Lebesgue measure. Does there exist a plane cutting each of the three sets A₁, A₂, A₃ into two parts of equal measure?”

To bring this question to life for his companions, Steinhaus illustrated it with one of his trademark vivid examples, one that reflected the venue of their meetings, and also perhaps their imminent preoccupation with daily essentials: Can every ordinary ham sandwich consisting of three ingredients, say bread, ham, and cheese, be cut by a planar slice of a knife so that each of the three is cut exactly in half? (See the figure on the right.)

A Simpler Problem

At the meeting where Steinhaus introduced this question, he reported that the analogous conclusion in two dimensions was true: Any two areas in a (flat) plane can always be simultaneously bisected by a single straight line, and he sketched out a solution on the marble tabletop. In the spirit of Steinhaus’s food theme, let’s consider the case where the two areas to be bisected are the crust and sausage on a pepperoni pizza. If the pizza happens to be a perfect circle, then every line passing through its center will exactly bisect the crust.

To see that there is always a line that will bisect both crust and sausage simultaneously, start with the potential cutting line in any fixed direction, and rotate it about the center slowly, say clockwise. If the proportion of sausage on the clockwise side of the arrow-cut happened to be 40 percent when the rotation began, then after the arrow-cut has rotated 180 degrees, the proportion on the clockwise side of the arrow-cut is now 60 percent. Because this proportion changed continuously from 40 percent to 60 percent, at some point it must have been exactly 50 percent, and at that point both crust and sausage have been exactly bisected. (See the figure below.)

On the other hand, if the pizza is not a perfect circle, as no real pizza is, then there may not be an exact center point such that every straight line through it exactly bisects the crust. But in this general noncircular case, again move the cutting line so that it always bisects the crust as it rotates, and note that even though the cutting line may not rotate around a single point as it did with a circular pizza, the same continuity argument applies. If the proportion clockwise of the north cut started at 40 percent, then when the cut arrow points south, that proportion will be 60 percent, which again completes the argument using the simple fact that to go continuously from 40 to 60, one must pass through 50. This simple but powerful observation, formally known as the Intermediate Value Theorem, also explains why if the temperature outside your front door was 40 degrees Fahrenheit yesterday at noon and 60 degrees today at noon, then at some time in between, perhaps several times, the temperature must have been exactly 50 degrees.

The general subject of fair division has been studied extensively using mathematical tools, and some of that study has proven useful for problems such as dividing estates or fishing grounds.

• Facebook
• Twitter

It is Steinhaus’s two-dimensional (pizza) version of the ham sandwich theorem that may be used for gerrymandering. Instead of a pizza, imagine a country with two political parties whose voters are sprinkled through it in any arbitrary way. The pizza theorem implies that there is a straight line bisecting the country so that exactly half of each party is on each side of the line. Suppose, for example, that 60 percent of the voters in the United States are from party Purple and 40 percent are from party Yellow. Then there is a single straight line dividing the country into two regions, each of which has exactly 30 percent of the Purple on each side, and exactly 20 percent of the Yellow on each side, so the Purple have the strict majority on both sides. Repeating this procedure to each side yields four districts with exactly 15 percent Purple and exactly 10 percent Yellow in each. Again the majority party (in this case Purple) has the majority in each district. Continuing this argument shows that whenever the number of desired districts is a power of two, there is always a straight-line partition of the country into that number of districts so that the majority party also has the majority of votes in every single district. (See the map below.)

This repeated-bisection argument may fail, however, for odd numbers of desired districts. Sergei Bespamyatnikh, David Kirkpatrick, and Jack Snoeyink of the University of British Columbia, however, found a generalization of the ham sandwich theorem that does the trick for any number of districts, power of two or not. They showed that for a given number of Yellow and Purple points in the plane (no three of which are on a line), there is always a subdivision of the plane into any given number of convex polygons (districts) each containing exactly the same numbers of Yellow points in each district, and the same number of Purple. (See the map below.)

In his application of this theorem to gerrymandering, Soberón observed that for any desired number of districts, this theorem implies that there is always a subdivision into that number of polygonal districts so that each district has exactly the same number of Purple, and exactly the same number of Yellow. Whichever party has the overall majority in the country will also have the majority in every district. Thus, as he found, a direct application of ham sandwich theory would not help fix the problem, but would actually make it worse, and the electorate should be wary if the person drawing congressional maps knows anything about that theory. No wonder the Supreme Court balked on all three of the most recent cases it has heard on partisan gerrymandering.

The Scottish Café

After giving his argument for the two-dimensional case of the ham sandwich theorem, Steinhaus then challenged his companions to prove the 3-dimensional version. The same basic Intermediate Value Theorem argument of continuity that worked for the pizza theorem will not settle the “ham sandwich” Problem 123 question, simply because there is no single “direction” to move a given starting plane passing through the sandwich, guaranteeing a return to the same spot having bisected both of two other objects somewhere along the way.

Two gifted students and protégés of Steinhaus, Stefan Banach and Stanisław Ulam, were also members of the Scottish Café group. Using a discovery Ulam had made around the same time with Karol Borsuk, another Scottish Café comrade, Banach was able to prove the sandwich conjecture of Steinhaus. The key to Banach’s proof, called the Ulam-Borsuk Theorem, was another general continuity theorem similar in spirit to the Intermediate Value Theorem, but much more sophisticated. Steinhaus also brought that abstract theorem to life with another of his colorful real-life examples: the Ulam-Borsuk Theorem, he said, implies that at any given moment in time there are two antipodal points on the Earth’s surface that have the same temperature and the same atmospheric pressure.

Direct application of the ham sandwich theorem would not fix the gerrymandering problem, but would make it worse.

• Facebook
• Twitter

If there are more than three solid objects, or more than two regions in the plane, then it may not be possible to bisect all of them simultaneously with a single plane (or line), as can easily be seen in the case where four small balls are located at the vertices of a pyramid. Also the conclusion of bisection cannot generally be relaxed. For example, if your goal is to split a pizza (or political territory) into two pieces so that one side contains exactly 60 percent of each, that may not always be possible. (See the figure below.)

Generalizations

During World War II, the statement of this colorful and elegant new mathematical result—that any three fixed objects simultaneously can be bisected by a single plane—somehow made it through enemy territory and across the Atlantic, long before email or smartphones or Skype. Mathematicians Arthur Stone and John Tukey at Princeton University learned about this new gem of a theorem via the international mathematics grapevine, and improved the result to include nonuniform distributions, higher dimensions, and a variety of other cutting surfaces and objects. The new Stone and Tukey extensions also showed, for example, that a single circle simultaneously can bisect any three shapes in the plane. For example, there is a location for a telecommunications satellite and a power level so that its broadcasts will reach exactly half the Yellow, half the Purple, and half the Teal (Independents). (See the map below.)

Formally speaking, of course, drawing a line to bisect two discrete mass distributions such as Yellow and Purple voters may require splitting one of the voter-points, which may not always be possible (or desirable). If a distribution has an odd number of indivisible points of one type, for example, then clearly no line can have exactly half those points on each side of the line. Inspired by the success of my PhD advisor Lester Dubins in addressing a different fair division problem involving indivisible points (professors, in that case), I wondered whether the conclusion of the ham sandwich theorem might be extended to also include mass distributions with indivisible points—such as grains of salt and pepper sprinkled on a table—by replacing the notion of exact bisection of distributions by a natural generalization of the statistical notion of a median.

Recall that a median of a distribution, say of house prices in a neighborhood, is a price such that no more than half of all the house values are below and no more than half are above that price. Extending this notion to higher dimensions yields the concept of median lines, median planes, and median hyperplanes in higher dimensions. Using the Ulam-Borsuk Theorem again, but this time applied to a different “midpoint median” function, it was straightforward to show that for any two arbitrary random distributions in the plane, or any three in space, there is always a line median or plane median, respectively, that has no more than half of each distribution on each side.

Some 20 years later, Columbia University economist Macartan Humphreys used this result to solve a problem in cooperative game theory. In a setting where several groups must agree on allocations of a fixed resource (say, how much of a given disaster fund should be allocated to medical, power, housing, and food), the objective is to find an allocation that no winning coalition could override in favor of another allocation. He showed that such equilibrium allocations exist precisely when they lie on “ham sandwich cuts.”

Touching Planes

In explaining the beauties of the ham sandwich theorem to nonmathematician friends over beer and pizza, one of my companions noticed that often there is more than one bisecting line (or plane), and we saw that some bisecting lines might touch each of the objects, whereas others may not. I started looking at this observation more closely and discovered that in every case, I could always find a bisecting line or plane that touched all the objects. When I could not find a reference or proof of this concept, I posed the question to my Georgia Tech friend and colleague John Elton, who had helped me crack a handful of other mathematical problems: Is there always a bisecting plane (or hyperplane, in dimensions greater than 3) that also touches each of the objects?

Together, he and I were able to show that the answer is yes, which strengthens the conclusion of the classical ham sandwich theorem. For example, this improved version implies that at any instant in time, in our Solar System there is always a single plane passing through three bodies—one planet, one moon, and one asteroid—that simultaneously bisects the planetary, the lunar, and the asteroidal masses in the Solar System. (See the figure below.)

Diverse Divisions

The ideas underlying the ham sandwich theorem have also been used in diverse fields, including computer science, economics, political science, and game theory. When I asked my friend Francis Su, Harvey Mudd College mathematician and fair-division expert, about his own applications of the ham sandwich theorem, he explained how he and Forest Simmons of Portland Community College had used ham sandwich results to solve problems in consensus-halving. In particular, they used it to show that given a territory and 2n explorers, two each of n different specialties (two zoologists, two botanists, two archeologists, etc.), there always exists a way to divide the territory into two regions and the people into two teams of n explorers (one of each type) such that each explorer is satisfied with their half of the territory.

The ideas underlying the ham sandwich theorem have also been used in diverse fields, including computer science, economics, political science, and game theory.

• Facebook
• Twitter

As a more light-hearted application during a keynote lecture at Georgia Tech, Tel Aviv University mathematician Noga Alon described a discrete analog of the ham sandwich theorem for splitting a necklace containing various types of jewels, as might be done, he said, by mathematically oriented thieves who steal a necklace and wish to divide it fairly between them. Even though it had been offered as an amusement, his result had applications, including to VSLI (Very Large Scale Integrated) circuit designs where an integrated chip composed of two different types of nodes is manufactured in the shape of a closed circuit (much like a necklace), and may be restructured after fabrication by cutting and regrouping the pieces. Alon’s theorem answers this question: How many cuts need to be made of the original circuit in order to bisect it into two parts, each containing exactly half of each type of node?

Revisiting the Café

Steinhaus published the proof of the ham sandwich theorem in the local Polish mathematical journal Mathesis Polska in 1938, the year of the infamously violent Kristallnacht. The Scottish Café mathematics gatherings continued for a few more years, despite the invasion of western Poland by the German army and the Soviet occupation of Lwów from the east, but the difficult times would soon disperse both scholars and their works. Ulam, a young man in his 20s and, like Steinhaus, also of Jewish roots, had left with his brother on a ship for America just two weeks before the German invasion.

Banach, nearing 50 and already widely known for his discoveries in mathematics, was appointed dean of the University of Lwów‘s department of mathematics and physics by the Soviets after they occupied that city, under the condition that he promised to learn Ukrainian. When the Nazis in turn occupied Lwów, they closed the universities, and Banach was forced to work feeding lice at a typhus research center, which at least protected him from being sent into slave labor. (Banach, like many others, was made to wear cages of lice on his body, so they could feed on his blood. The lice, which are carriers of typhus, were used in research efforts to create a vaccine against the disease.) Banach was able to help reestablish the university after Lwów was recaptured by the Soviets in 1944, but died of lung cancer in 1945.

Although the correct statement of the crisp ham sandwich theorem had made it through the World War II mathematical grapevine perfectly, the proper credit for its discoverers was garbled en route, and Stone and Tukey mistakenly attributed the first proof to Ulam. Sixty years later the record was set straight when a copy of Steinhaus’s article in the Mathesis Polska was finally tracked down, and we now know that Steinhaus posed the problem and published the first paper on it, but it was Banach who actually solved it first, using a theorem of Ulam’s.

Today Banach is widely recognized as one of the most important and influential mathematicians of the 20th century, and many fundamental theorems, as well as entire basic fields of mathematics, that are based on his work are now among the most extensively used tools in physics and mathematics.

Ulam went on to work as one of the key scientists on the Manhattan Project in Los Alamos, achieving fame in particular for the Teller-Ulam thermonuclear bomb design, and for his invention of Monte Carlo simulation, a ubiquitous tool in economics, physics, mathematics, and many other areas of science, which is used to estimate intractable probabilities by averaging the results of huge numbers of computer simulations of an experiment.

After the war, Steinhaus would have been welcomed with a professorship at almost any university in the world, but he chose to stay in Poland to help rebuild Polish mathematics, especially at the university in Wrocław, which had been destroyed during the war. During those years in hiding, Steinhaus had also been breaking ground on the mathematics of fair division—the study of how to partition and allocate portions of a single heterogeneous commodity, such as a cake or piece of land, among several people with possibly different values. One of Steinhaus’s key legacies was his insight to take the common vague concept of “fairness” and put it in a natural and concrete mathematical framework. From there it could be analyzed logically, and has now evolved into common and powerful tools. For example, both the website Spliddit, which provides free mathematical solutions to complicated everyday fair division problems from sharing rent to dividing estates, and the eBay auction system, which determines how much you pay—often below your maximum bid—are direct descendants of Steinhaus’s insights on how to cut a cake fairly.

These ideas, born of a mathematician living and working clandestinely with little contact with the outside world for long periods of time, and undoubtedly facing fair-allocation challenges almost daily, have inspired hundreds of research articles in fields from computer and political science to theoretical mathematics and physics, including many of my own. Steinhaus eventually became the first dean of the department of mathematics in the Technical University of Wrocław. Although I never met him in person, I had the good fortune to be invited to visit that university in December 2000, and it was my privilege to lodge in a special tower suite right above the mathematics department and to give a lecture in the Hugo Steinhaus Center.

Steinhaus had made the last entry in the original Scottish Book in 1941 just before he went into hiding with a Polish farm family, using the assumed name and papers of a deceased forest ranger. The Scottish Book itself also disappeared then, and when he came out of hiding and was able to rediscover the book, Steinhaus sent a typed version of it in Polish to Ulam at Los Alamos, who translated it into English. Mathematician R. Daniel Mauldin at the University of North Texas, a friend of Ulam, published a more complete version of the Scottish Book including comments and notes by many of the problems’ original authors. Their Problem 123, which evolved into the ham sandwich theorem, continues to fascinate and inspire researchers, and Google Scholar shows that eight decades later, several dozen new entries on the topic still appear every few months.

But what about that pesky gerrymandering problem? Negative results in science can also be very valuable; they can illuminate how a certain line of reasoning is doomed to failure, and inspire searches in other directions. That outcome is exactly what happened when the negative ham sandwich gerrymandering result showed that a redistricting attempt might still be radically biased even if the shapes of the districts are quite regular. That insight led researchers to drop the notion of shape as the key criterion, and to look for another approach. The result was a new “efficiency gap” formula that quantifies how much a map is gerrymandered based on vote shares, not on shape. This formula, too, has problems, and in turn it inspired me and my colleague Christian Houdré at Georgia Tech to look for a better measure of “gerrymandered-ness” using combinatorial models involving balls and urns. And so the exciting cycle of scientific discovery that started with the ham sandwich theorem continues.

A great many mathematicians today owe a huge debt to those intrepid Polish academics, and we raise our cups of java to those original Scottish Café mathematicians!