Mathematics for the liberal arts (2013)

Part I. MATHEMATICS IN HISTORY

Chapter 3. MODERN MATHEMATICS

3.4 The 20th and 21st Centuries: Explosion

Introduction

The first half of the 20th century was dominated by the two world wars. World War I, 1914–1918, pitted Germany, Austria-Hungary, and Turkey against France, Great Britain, Russia, Italy, and Japan. In 1917 the United States entered the war and Russia left it, after the Bolshevik Revolution. The battles were characterized by trench warfare, made necessary by the new weapons, especially the machine gun and rapid-fire artillery. The war ended in defeat for Germany and its allies. An estimated 20 million people died.

Two decades later, after the Great Depression and the rise of Hitler in Germany, the second world war commenced. In this war, lasting from 1939 to 1945, the Axis powers–Germany, Italy, and Japan–battled the Allies–France, Great Britain, the Soviet Union, and the United States. The war was fought across most of the world. New technologies, led by tanks and airplanes, again increased the death toll. This was the deadliest war in history, with estimates of the number killed ranging from 35,000,000 to 60,000,000.

The United States emerged from the war as the dominant military and economic power, although the Soviet armies ruled Eastern Europe. Soon after, these two powers were locked in the Cold War, a time of great tension and many proxy wars, but fortunately no nuclear conflicts. Western Europe, which had been devastated by World War II, began rebuilding, helped by the United States’ reconstruction program known as the Marshall Plan.

The U.S. continued to dominate the world’s economy through the 1950s and 1960s. Gradually other nations grew stronger, led by Japan and Germany, joined later in the 20th century by the newly industrial “Asian Tigers”: Hong Kong, Singapore, South Korea, and Taiwan. The early part of the 21st century has seen the spectacular rise of China, as well as the other BRIC (Brazil, Russia, India, and China) countries.

The Industrial Revolution continued and spread through much of the world. Automobiles became common. Airplanes were invented, and radio, and television. There were great advances in chemistry, including nylon and detergents; in medicine, especially with antibiotics; in labor-saving devices for the home, such as the vacuum cleaner and washing machine. The Space Age began in 1957, when the Soviet Union launched the first artificial satellite of Earth, Sputnik 1; men walked on the Moon in 1969.

The transistor, invented in 1947, led to a revolution in electronics. In the late 1950s came the integrated circuit, in which as many as ten transistors were put on a single silicon chip. Today, there are commercially available chips containing billions of transistors each.

The first digital electronic computers were built in the 1940s. Mathematicians, including Alan Turing (1912–1954), John von Neumann (1903–1957), and Donald Knuth (b. 1938), played an important part in the invention of computers and computer science. In the 1970s the Internet grew out of a network called ARPANET, which was created in 1969 by the Advanced Research Projects Agency (ARPA) of the U.S. Department of Defense. The World Wide Web was invented by the Englishman Tim Bemers-Lee and colleagues at CERN in Switzerland, in the years 1989–92.

As the Industrial Revolution intensified and spread, the way people live has continued to change. The proportion of the United States population living in rural areas went from 60% in 1900 to 19% in 2000. As of 2010 some 23 cities in the world had metropolitan populations of more than 10 million people.

Science continued its dizzying growth in this century. Early in the century, Albert Einstein (1879–1955) introduced his theory of relativity. The study of atoms led physicists, including Max Planck (1858–1947), Einstein, Niels Bohr (1885–1962), Werner Heisenberg (1901–1976), and Erwin Schrödinger (1887–1961), to quantum mechanics. This theory has had far-reaching consequences in chemistry, technology (e.g., lasers, semiconductors), even philosophy, not to mention the bomb.

Our understanding of astronomy evolved dramatically since the turn of the 20th century. On 26 April 1920 the Great Debate took place at the Smithsonian Museum of Natural History. The issue was whether the fuzzy patches visible in telescopic photographs, known as spiral nebulae, were inside our galaxy, the Milky Way. By the end of that decade, the work of Edwin Hubble (1889–1953) demonstrated not only that these nebulae were galaxies in their own right, but that the galaxies were receding from each other. In 1965 Amo A. Penzias (b. 1933) and Robert W. Wilson (b. 1936) discovered a faint “noise” of radio waves pervading the universe, and confirmed the theory of the Big Bang, that the universe exploded some 13–14 billion years ago.

The work of astronomers Fritz Zwicky (1898–1974) and Vera Rubin (b. 1928), among others, revealed that much of the mass of the universe is not actually visible. This is called dark matter. In 1998 observations by Saul Perlmutter (b. 1959), Brian P. Schmidt (b. 1967), and Adam Riess (b. 1969) showed that the expansion of the universe discovered by Hubble is not being slowed down by gravity, as everyone had thought, but is in fact accelerating. This led to the hypothesis of a mysterious “dark energy,” which comprises roughly 73% of all of the universe’s energy. Most of the rest is dark matter. The part of the universe comprised of protons, neutrons, and atoms, i.e., the part of the universe that we understand, is less than 5%.

On Earth, the theory of continental drift was formulated by Alfred Wegener (1880–1930) and, after some initial setbacks, was confirmed, and expanded into the theory of plate tectonics by Harry H. Hess (1906–1969), J. Tuzo Wilson (1908–1993), and others. (Important to the theory is a theorem in spherical geometry due to Euler.) This theory is central to much of modem geology, explaining features from midocean mountain chains, to the islands of Hawaii, to the Himalayas.

The central actor in modem biology is DNA (deoxyribonucleic acid). In 1944 Oswald Avery (1877–1955) discovered that DNA was the stuff of heredity. Remarkably, he never won the Nobel Prize, perhaps because he was sixty-seven years old when he published the paper. In 1953 the structure of DNA was described by James Watson (b. 1928) and Francis Crick (1916–2004).

In mathematics, a large majority of all of the research done ever has been done since 1900.

There are currently more than 500 regularly published mathematical journals, the majority of which are devoted to reporting new mathematical discoveries. The next time someone claims that “math never changes” you can point out this fact. The explosion of mathematical research reached a dizzying level in the 20th century. New mathematical fields were invented, new applications were discovered, and some major open problems were solved.

A combination of factors caused the vast mathematical boom in these times. One of these was the expansion of universities, including the funding of research by governments. Another factor was the Cold War, which stimulated (through fear) an immense expenditure on mathematics in the U.S. Yet another reason was the increasing role of computers and the Internet in mathematical research. Today, it is common for mathematicians to collaborate with colleagues whom they have never met in person. Mathematicians can investigate ideas quickly and easily using mathematical exploration software, they can write up their findings using mathematical typesetting software, and they can disseminate their results rapidly over the World Wide Web.

In this section we give an overview of some of the main events in mathematics in the last hundred years. It is impossible to cover all topics, or even to list all topics. All we can do is briefly describe some of them.

Some Twentieth Century mathematicians

Hilbert’s Problems

The 20th century opened with the mathematician David Hilbert (1862–1943) presenting a list of 23 important unsolved mathematical problems. He introduced his list in a speech to the International Congress of Mathematicians in 1900, adding to the collection of open problems in a later publication. Hilbert’s problems helped to shape mathematical research in the 20th century, and a few of the original problems remain unsolved in the 21st century.

Some of Hilbert’s problems are technical and would require lengthy explanations. Others are easier to explain, such as the tenth problem on the list. This problem is concerned with equations whose solutions are positive integers. Such equations are called Diophantine, after the Greek mathematician Diophantus (c. 200–294), who discovered methods for solving certain types of them. An example is the equation

You are probably familiar with this as it is the formula relating the three sides of a right triangle given by the Pythagorean Theorem. You may know some integer solutions, such as

and

What happens if we change the exponent in the equation from 2 to 3? Are there positive integer solutions to the equation

Now the problem is much more difficult. Try as we may, we cannot find three positive integers x, y, z which satisfy the equation. It can be proved that this equation has no positive integer solutions (Euler showed this).¹

Hilbert asked whether there is a method that would tell whether any given polynomial equation has positive integer solutions. For instance, we would be able to say whether the equation

has a solution in positive integers x, y, and z. Such a method, if it existed, would be very useful. However, in 1970 Yuri Matiyasevich proved that there does not exist such a procedure. This is a stronger statement than merely saying that it is difficult to tell whether certain equations have integer solutions. There is no procedure that will tell, for any given polynomial equation, whether it has integer solutions. Thus, Hilbert’s tenth problem was resolved in the negative.

It may seem strange that someone could prove that a general method cannot exist. However, many such negative results were established in 20th century mathematics, and some of the most important theorems have this negative character.

David Hilbert (1862–1943)

David Hilbert was bom near Königsberg in Prussia (now Kaliningrad, Russia). He got his doctorate from the University of Königsberg in 1885, and taught there until 1895, when he became a professor at the University of Göttingen. He was a major reason why Göttingen was the best center of mathematics in the world throughout the first decades of the 20th century.

Hilbert was one of the most influential mathematicians in history. His famous list of unsolved problems, known as Hilbert’s problems, was a catalyst for research in the 20th century. As the list shows, Hilbert was interested in all areas of mathematics of his day, and consequently he is recognized as perhaps the last mathematician who was conversant with all contemporary mathematics. After Hilbert, mathematics has expanded too much for anyone to comprehend it all.

Hilbert investigated the foundations of geometry, finding some holes in the proofs of Euclid and adding axioms to gain precision. In his study of mathematical analysis, Hilbert contributed a new mathematical object called Hilbert space (a generalization of Euclidean space).

Hilbert endorsed Cantor’s theory of infinite sets, describing one of the results in an intuitive, yet mind-boggling, way. His thought-experiment is called the Grand Hotel. Suppose that a hotel has infinitely many rooms, numbered 1, 2, 3, … All the rooms are occupied when a new guest arrives. However, the manager merely moves the guest in room 1 to room 2, the guest in room 2 to room 3, the guest in room 3 to room 4, etc. The new guest then moves into room 1. This explains why the infinity of positive integers is the same as the infinity of positive integers plus one.

Next, a coach carrying infinitely many people arrives at the hotel. Each person wants a room. The manager moves the guest in room 1 to room 2, the guest in room2 to room 4, the guest in room 3 to room 6, etc. The guest in room n moves to room 2n. This frees up all the odd-numbered rooms for the infinitely many new guests. This explains why infinity plus infinity is the same size as infinity.

Now infinitely many coaches arrive, each carrying infinitely many people who want rooms. Can you see how all the new guests can be accommodated? The conclusion is that infinity times infinity is the same size as infinity.

Hilbert knew and collaborated with many of the great mathematicians of the turn of the century, including Hermann Minkowski, Adolf Hurwitz, Carl Lindemann, Hermann Weyl, and Ernst Zermelo. He was anguished when the Nazis forced Jewish mathematicians out of the University of Gottingen, where he was Chair.

Hilbert is remembered for his focus on the unsolved problems of mathematics and for his optimistic spirit toward the resolution of these problems. His motto was “We must know. We will know.”

Unsolvable Problems

The oldest posed problems which have turned out to be unsolvable are the three famous Greek geometric construction problems: trisection of an arbitrary angle, duplication of the cube, and quadrature of the circle. These constructions are to be done using only a straightedge and compass. Each of these tasks has been mathematically proved to be impossible. This is not to say that they are difficult, or that no one has discovered how to carry them out, but rather that they can never be accomplished using only the requisite tools.

One of the most important negative results in the history of mathematics, and one that continues to have a large impact on mathematical research, is a 1931 theorem of the logician Kurt Godel (1906–1978), the incompleteness theorem. Gödel’s theorem is concerned with limitations on what can be proved about the positive integers. The positive integers are a rich area of mathematics that has fascinated mathematicians for centuries. Godel’s shocking theorem is that there are true statements about positive integers that cannot be proved starting with the usual axioms about positive integers. The “usual axioms,” known technically as the Peano Axioms, include such suppositions as the fact that every positive integer has a successor (a next larger positive integer). Gödel’s theorem furthermore states that even if we added more axioms to the system of positive integers, there would still be true statements that cannot be proved within the system.

Kurt Godel (1906–1978)

Kurt Gödel was bom in Brünn, Austria-Hungary, now Brno, Czech Republic. He earned his doctorate at the University of Vienna, where he remained on the faculty until World War II started. He then fled east, taking the trans-Siberian railway across Russia to the Pacific, a ship to America, and another train to New Jersey, where he joined his friend Albert Einstein at the Institute for Advanced Study, from which he retired in 1976.

In 1931 Gödel published his incompleteness theorem in a landmark paper, “On Formally Undecidable Propositions of Principia Mathematica and Related Systems.” The Principia Mathematica (1910), a three-volume book by Bertrand Russell (1872— 1970) and Alfred North Whitehead (1861–1947), was a monumental effort to rewrite the foundations of mathematics as a branch of logic. The reasoning is slow and meticulous, with the proposition “1 + 1 = 2” not appearing until page 379.

Gödel was also interested in philosophy and physics. In 1949, he showed that relativity theory allowed for the possibility of time travel.

Gödel fought mental illness throughout his life. He became paranoid, convinced he was being poisoned. He ate food only after his wife had tasted it. When she became ill and had to be hospitalized, he starved himself to death.

The proof of Gödel’s theorem owes a debt to a venerable logical conundrum known as the Liar’s Paradox. Consider the statement “This is a false statement.” Is this statement true or false? There is a dilemma, because if the statement were true, then it would be false, and if it were false, then it would be true. This is considered a paradox but not a serious mathematical one. What Gödel did was to make this paradox mathematically precise. He was able to formulate, within the system of positive integers, the following statement.

Statement X: “Statement X is not provable within the system of positive integers.”

Statement X must be true, because if it were false, then statement X would be provable and hence we could prove a false statement (which isn’t allowed). Since statement X is true, what it asserts is true, namely, that it is not provable. Therefore, statement X is a true statement that is not provable within the system of positive integers.

Throughout the 20th century, Gödel’s ideas on the limitations of formal mathematical systems propagated into other areas of mathematics. An important offshoot is the analysis of algorithms proposed by the logician Alan Turing (1912–1954). An algorithm is a step-by-step method for solving a problem. In the 1930s (before modem computers were invented) Turing studied the question of what an algorithm can do, and concluded that all algorithms could be carried out on a theoretical computer now called a Turing machine (Figure 3.18). A Turing machine consists of a linear tape with square cells containing the symbols 0 or 1, and a pointer (↑) that points to one cell at a time. The machine is able to read the symbol indicated by the pointer, and decide whether to change the symbol and/or move the pointer.

Figure 3.18 Turing machine.

Although a Turing machine is very simple, it is very powerful, as it can calculate anything that can be calculated. It can do computations, produce and store data, and make decisions about what steps to perform next. However, Turing conceived of a task that a Turing machine cannot carry out, and which is therefore impossible for any machine to carry out. The task is called the Halting Problem. He considered the following question: Is there an algorithm which will check other algorithms to see whether or not they contain infinite loops? (An infinite loop is a set of steps that repeats forever, not allowing the program to halt.) If you program computers you will realize that this would be a valuable program to have. When you finish writing a program you could call up this wonderful master program–call it the Halting Program–and the Halting Program would tell you whether your program has an infinite loop, that is, whether it will halt. Turing proved mathematically that the Halting Program cannot be written–it is a logical impossibility. The solution to the Halting Problem implies a logical contradiction, so the Halting Problem is unsolvable. Thus, computers cannot be used to solve every problem.

Alan Turing (1912–1954)

Alan Turing was bom in London. His father worked in the Indian Civil Service, traveling between England and India, but Alan was educated in England. He did his undergraduate work at Cambridge, after which he was elected to a fellowship there. He submitted his famous paper on the Turing machine in 1936. The same year, he traveled to America, and he earned a PhD at Princeton University in 1938.

During World War II, Turing worked at Bletchley Park back in England and was a major participant in the successful effort to break German codes. After the war, in addition to foundational work in the theory of computing, he wrote a seminal paper on artificial intelligence. In the paper, he proposed what is known as the Turing test: if a human operator communicates remotely with a computer and another human, and can’t tell which is which, then we must say that the computer has human-like intelligence. All of Turing’s theoretical work in computer science was done before modem computers were in existence.

Turing was homosexual in an intolerant society. He was prosecuted, lost his security clearance, and given the choice of prison or chemical castration. He chose the latter. Two years later, Turing died of cyanide poisoning, probably a suicide, at age 41.

Computation

Our consideration of Turing’s analysis of algorithms leads to a consideration of the role of computers in mathematics.

Computation is about solving problems. Which problems are computable and which are not computable? We have already described some problems, such as the Halting Problem, that cannot be solved at all. This is an extreme situation. For other problems, solutions of a qualified flavor exist. In some cases, the idea of a problem solution is fairly straightforward but the solution is impractical because of the heavy computations involved. In other cases, clever methods allow for fast solutions of seemingly difficult problems.

Some problems have only been solved using computers. One of the most prominent is the solution of the famous Four Color Conjecture, which was proposed in the 1800s and finally solved in 1976 by Kenneth Appel and Wolfgang Haken from the University of Illinois. The problem is simply stated: Can one color the regions of every map with four colors so that no two adjacent regions have the same color? Most people believed that you can color every map in such a way. The difficulty was to prove it for all possible maps. When Appel and Haken confirmed this using a computer, the state of Illinois issued a postal seal declaring “Four Colors Suffice.” Appel and Haken solved the problem by examining some 1500 irreducible maps (a special term they had) on a computer. Many mathematicians are skeptical about computer proofs because they can’t be verified directly by humans, only by other computers.

Some problems are solvable in theory but intractable even using a computer. The NP¹ problems have the property that there is a known algorithm for their solution but the algorithm requires exponential time on a computer, so that even to find a solution for a small case might take billions of years on the fastest available machine. For instance, in the Traveling Salesman Problem, one is given a list of cities and the distances between cities, and is asked to find an optimal route (one with least total distance) that visits all the cities. This is a practical problem, as it can model shipping or telecommunications situations.

In contrast, it has recently been shown that the problem of determining whether a given positive integer is a prime number is in the class P of deterministic polynomial algorithms. These algorithms can be executed relatively quickly.

Some problems have been solved only by a large group of researchers working over a long period of time. A prime example of this (pun intended) is the classification of finite simple groups (to be described shortly).

The security of many types of transactions may ultimately depend on the intractability of prime factorization. The problem is to factor a number (positive integer) into its prime factors. A number is prime if it has only one and itself as divisors. The fastest computers today are unable to factor a reasonably large number (about 1000 digits) in a reasonable length of time (about one year). People working in the national security field use codes that rely on the factorization of large numbers. The banking system has been revolutionized by this idea. But a caveat: there are advances in factoring algorithms and computer speed every year. No code is unbreakable.

To natural philosophers of the 1700s, such as Lagrange and Laplace, the unsolvability of a problem would have been unimaginable. They believed that any problem that you can state precisely must have a solution. They believed, for example, that if you could specify the positions and velocities of every particle in the universe then you could determine the universe’s past and ultimate future. We now know that even the 3-body problem has no mathematical solution. One cannot take a system of three particles and determine with certainty their future states or their past states.

Mathematical Abstraction

Recall the group, the mathematical structure that became so important in the 19th century. The notion of the group developed only gradually throughout the century. It first appeared in concrete settings, then in more general settings. Various mathematicians realized that they could consider an abstract group, one whose properties were reduced to the minimum necessary to capture the essence of the concept. This abstract group could then be studied, and any theorems one could prove in this setting would apply to all of its concrete realizations.

As an example, we will prove an elementary theorem about groups, using only the definition. Recall that a group consists of a set G and an operation that associates to any two elements x and y of G a third element xy of G, with these properties.

1. The operation is associative: for any x, y, and z in G, we have the equality (xy)z = x(yz).

2. There exists an identity element, e, such that, for any x in G, we have xe — x and ex = x.

3. Each element x in G must have an inverse, an element y in G such that xy = e and yx = e.

Note that the last property asserts only the existence of inverses. Is it possible that an element could have more than one inverse? No.

Theorem. Each element of a group has only one inverse.

Proof. Suppose that x has two inverses, say, y and z. Then we have xy = e and yx = e, and also xz = e and zx = e. Using our properties,

Therefore, y = z, which is what we needed to prove.

(The little black box on the right above means that the proof is done. Some people use the abbreviation Q.E.D. to mark the end of a proof. In Euclid’s great book, the Elements, he concluded the proof of each proposition with “which was to be proved.” This has come down to us, through translations, as the Latin quod erat demonstrandum, or Q.E.D. for short.)

Although the importance of groups was realized in the 19th century, the 20th century saw the enshrinement of abstraction as the hallmark of modem algebra, and many other abstract algebraic structures have been studied. We will mention (without formal definitions) two of them. The first is the ring. This notion captures many, although not all, of the features of the integers. In particular, it adds another operation. The two operations, naturally enough, are called addition and multiplication.

An abstraction is of limited usefulness if there is only one concrete realization. In fact, other rings of interest arose in number theory. Ernst Kummer (1810–1893), as a result of attempting to prove Fermat’s Last Theorem, developed a new set of numbers, those of the form

where a and b are integers. This set of numbers forms a ring under the usual addition and multiplication. This ring is interesting because there is no equivalent to the Fundamental Theorem of Arithmetic–unique factorization into primes. For example, 6 = 2 · 3 and are two different factorizations of 6 into the equivalent of primes, called irreducibles. (They cannot be factored in the ring.) By comparison, the ring consisting of numbers a + bi, where a and b are integers, does enjoy unique factorization. These numbers are called the Gaussian integers.

Another algebraic abstraction is the field. Rings do not have division (e.g., dividing two integers does not always result in an integer). Of course, our familiar real numbers do have division, as long as you don’t divide by 0. A field is an abstract concept that captures the arithmetic of real numbers, including division.

Here is a different example of a field. The elements of this field are the numbers 0. 1.2.3.4. Addition and multiplication are the usual addition and multiplication, except that at the end we take the remainder upon division by 5. For example, 2+4 = 1, since the remainder of 6 is 1. Similarly, we can write 2 · 4 = 3. One can show that this structure is a field. In particular, we can define division.

What is division? We write a/b = c if a = bc. In our field of five elements, we can write 3/2 = 4 since 3 = 2·4. Of course, it takes some work to show that this division obeys all of the usual field properties. More on this example and others can be found in Chapter 5.

Rings, fields, and many other abstract mathematical structures were codified in the early decades of the 20th century. The most important researcher in this development was Emmy Noether.

Emmy Noether (1882–1935)

Amalie Emmy Noether was bom in Erlangen, Germany, the daughter of a mathematics professor. She originally studied French and English, and prepared to be a teacher. Although she passed the examination to become a teacher, she had in the meantime become more interested in mathematics. She audited classes at the University of Erlangen until women were officially allowed as students in 1904. She obtained her doctorate there in 1907. In the years 1907–1915 she taught at Erlangen, but was not paid.

In 1915 Noether was invited to the University of Gottingen by David Hilbert and Felix Klein to work on Einstein’s new theory of general relativity. They wanted her to be hired as a privatdozent (“private lecturer,” a sort of associate professor), but other faculty blocked the appointment because of her sex. Hilbert’s indignant reaction: “I do not see that the sex of the candidate is an argument against her admission as privatdozent. After all, we are a university, not a bath house.” For several years, she taught at Gottingen without position and without pay. Eventually, she did obtain an official position, and after 1922, was even paid.

In the late 1920s and early 1930s, Noether gathered a strong group of students around her. She was known as a generous teacher, freely sharing her great insights. Her students were themselves successful.

In 1933, with the ascent of the Nazis, many Jewish scholars lost their positions, including Noether. She accepted a position at Bryn Mawr College in a suburb of Philadelphia. There she was conveniently near the Institute of Advanced Study in New Jersey, which was home to fellow refugees Albert Einstein and Hermann Weyl, among many other leading scientists. Noether herself lectured at the Institute in 1934. The nearby Princeton University was not so welcoming; she described it as the “men’s university, where nothing female is admitted.”

In addition to her mathematics, Noether contributed to physics. In 1915 she proved Noether’s Theorem, one of the most important theorems in modem physics. This theorem connects symmetries with conservation laws. For example, the fact that physical laws don’t change over time is related to the conservation of energy.

Emmy Noether died in 1935, after surgery to remove a tumor.

Mathematical abstraction is not restricted to algebra. Another example comes from probability. This field had long been plagued by uncertainty in its foundations, which led to various paradoxes. These difficulties were overcome in 1933 by the Russian mathematician Andrey Nikolayevich Kolmogorov. He formulated a set of axioms which define a probability space. This concept is the bedrock on which modem probability theory has been built.

Andrey Nikolayevich Kolmogorov (1903–1987)

Andrey Nikolayevich Kolmogorov was bom in Tambov, Russia. His mother died giving him birth. He was raised by his sister and aunt, who moved to Moscow when Andrey was seven years old.

As a student Kolmogorov had many interests. In 1920 he was enrolled simultaneously at the Moscow State University and the Chemistry Technological Institute. His first published paper was on history. He eventually settled on mathematics, and obtained his doctorate from Moscow State University in 1929, having already published a number of important papers. He then worked at that university, becoming professor in 1931. He held positions at a number of Moscow research institutions, but remained associated with Moscow State University his entire career.

Although Kolmogorov is best known for his work in probability theory, he contributed to many fields, including chemistry, ecology, physics, and computer science. He did major work on the theory of turbulence. In computer science, he was a founder of algorithmic information theory, where people study “Kolmogorov complexity.”

Kolmogorov was important as well for his work in education. Many of his students obtained PhDs, and a number of them are quite famous for their own work. He wrote influential textbooks, and worked as well to improve education at secondary schools, especially for gifted students.

Finally, we mention a remarkable development of the late 20th century in group theory. It was inspired by a work published in 1870 by Camille Jordan (1838–1922), who found a way of decomposing the structure of a group that was analogous to how we represent integers as products of primes. The role of prime was played by what we call a simple group. Just as a prime is an integer that in some sense cannot be decomposed, a simple group is a group that cannot be broken down further. We have discussed some examples of simple groups: the symmetry group of the dodecahedron and the symmetry group of a seven-point geometry. All groups with a prime number of elements are simple. Simple groups are the building blocks that make up all symmetry in math and physics, and perhaps in art and music as well. After Jordan’s work, it was natural to try to classify the simple groups, i.e., to find all of them.

In 1986 an announcement was made that the classification of all finite simple groups had been achieved. What made this so remarkable is the degree of collaboration required. It was a mammoth project that engaged more than 100 scientists from 10 nations, working over 50 years, writing about 10,000 pages of journal articles. It is doubtful that a single person could have done it. Perhaps joint effort will be the norm in the future. There may well be problems in medicine, biology, and other sciences whose solutions will take a concentrated and orchestrated effort over hundreds of years.

The difficulty of this project was underscored when, after the initial announcement, it was discovered that the classification of finite simple groups wasn’t fully proved, as some omissions in the classification were found. In 2004 the completion of the classification was announced. These days, mathematicians are trying to simplify the hugely complex proof.

Game Theory

Game theory concerns mathematical questions about conflict. As a science, game theory had tentative beginnings in 1921 with the work of Emile Borel (1871–1956), who defined games of strategy, but began in earnest with the 1928 publication of the article “Zur Theorie der Gesellschaftspiele” (“On the Theory of Parlor Games”) by John von Neumann (1903–1957).

As used in game theory, the word “game” is more precise and focused than in general language. For example, common turn-based board games–such as tic-tac- toe, checkers, and chess–are usually not considered games in game theory. Most people who play tic-tac-toe for a period of time learn that there is little point in playing. Two experienced players will always achieve a tie. Board games such as checkers and chess share the same underlying characteristic: there is a single optimal (pre-scripted) way to play the game. It may not be feasible to explore every possible scenario of chess, but there is some optimal first move, second move, and so on. Games in game theory generally cannot be solved by exhaustive search.

Zero-Sum Games Although it is not a strict requirement, game play often occurs simultaneously rather than in turns. For example, a simple game between two players might work like this. Alice and Bob sit at a poker table. In each round of play, both players hide their hands under the table with a single poker chip, which they may or may not conceal in a fist. They bring their fist above the table and simultaneously open their hands to show. The outcome of a round in the game will be determined by these rules:

· If both Alice and Bob have a chip, then Alice will pay Bob $3.

· If both Alice and Bob have empty hands, then Alice will pay Bob $1.

· If one has a chip and the other is empty, then Bob will pay Alice $2.

It is common to describe games of this type in matrix form, and in fact they are often called matrix games. As a matrix, this game might look like:

Each ordered pair describes one possible outcome of the game, with the first number indicating the payoff for Bob and the second indicating the payoff for Alice. The pair (3, –3), for example, indicates that Bob has gained $3 while Alice has lost $3; that is, Alice pays Bob $3 when they both have a chip. This game is called a zero-sum game, because in each individual outcome the sum of the payoffs is always 0.

Von Neumann’s 1928 paper contained the “minimax theorem,” which states that every 2-player zero-sum game has an equilibrium solution. Each player has a strategy that completely determines the long term outcome of the game. For example, in our game between Alice and Bob, Alice has this equilibrium strategy: she can randomly choose to play a chip 3/8 of the time and to play an empty hand 5/8 of the time.

No matter how Bob plays against Alice’s equilibrium strategy, he can expect a long term payoff of $–0.125 per round. If he plays a chip, he has probability 3/8 of winning $3, and probability 5/8 of losing $2, for an expectation of E = 3(3/8) – 2(5/8) = –0.125. If he plays empty, his expectation is instead E = 1(3/8) – 2(5/8), which is also –0.125. Notice that since the game is zero-sum, she must win $0.125 per play on average to balance Bob’s loss, so Alice’s equilibrium strategy is a winning strategy for her.

The minimax theorem guarantees that Bob also has an equilibrium strategy, and for this game it is to play a chip 3/8 of the time and to play empty 5/8 of the time (note that though this game is symmetric, it won’t happen in every game that both players have identical strategies). If Bob follows this strategy, then no matter how Alice plays, her long term expectation is to win $0.125 per round.

It is not a coincidence that Bob’s equilibrium strategy and Alice’s equilibrium strategy lead to the same long term outcome. This always happens, and the long term value is said to be the value of the game. In this case, the value of the game is –0.125 to Bob (or equivalently +0.125 to Alice). Even for zero-sum games, game theory can’t necessarily guarantee a winning outcome in an inherently unfair game. In this game, Bob at best hopes to lose “only” $0.125 per round on average.

Non-Zero-Sum Games Not every game in game theory has the property that the losses of one player exactly balance the gains of the other. Some of the most interesting games are ones where both players may lose or both may win. Games like this are referred to as non-zero-sum games. The most famous of these games is the “prisoner’s dilemma,” which was introduced by Merrill Flood and Marvin Dresher in 1950, and has come to be described by a story:

Alice and Bob are arrested for committing some crime. The police don’t have enough evidence to convict them on the full offense, and each defendant is facing a one year prison term (conviction on the full offense carries a five year prison term). Alice and Bob are individually offered an opportunity to testify against the other in return for a one-year reduction in sentence.

Both prisoners face the choice of cooperating with (by keeping silent) or defecting from (by testifying against) their partner in crime. As a matrix, the game looks like this:

The prisoner’s dilemma is called a dilemma game because individual self interest leads to a poor result for both players. Consider the game from Bob’s perspective. If both players keep silent, the outcome of the game is (–1,–1) and he can anticipate one year in prison (as can Alice). If he believes that Alice will keep quiet, he can defect and testify against her to reduce his prison term to zero. But what if Bob knew that Alice would testify against him? He would face a five year prison term, and he should still defect in order to reduce the term to four years.

No matter what Alice does, it is in Bob’s best interested to defect. Of course, Alice’s point of view is similar, and the same reasoning requires that she should defect. However, the value of the game is (–4, –4) if they both defect. Each, by independently acting in their best interest, has helped guarantee a worse outcome for both. If they had only cooperated, they would both be better off.

Like zero-sum games, non-zero-sum games have equilibrium solutions. They are called Nash equilibriums after the mathematician John Forbes Nash, Jr., who worked in game theory and whose life inspired the movie A Beautiful Mind. In the prisoner’s dilemma, the Nash equilibrium is mutual defection.

The prisoner’s dilemma is particularly interesting for its similarity to other social dilemmas, such as the tragedy of the commons, the free rider problem, and the (nuclear) arms race. It also has applications to evolutionary biology and psychology.

John von Neumann (1903–1957)

John von Neumann, bom in Budapest in 1903, was the oldest son of a successful banker. He was raised in an environment of learning and from an early age showed an aptitude for languages and for mathematics. He was fluent in numerous languages, including Hungarian, German, Classical Greek, and English. He had a photographic memory, able to remember anything he read, and as a boy would memorize pages of the telephone directory as a party trick.

In 1921 von Neumann enrolled simultaneously at the University of Budapest and the University of Berlin. Although he wanted to pursue mathematics, he studied chemistry as a compromise with his father. By 1925 he had a degree in chemical engineering from the Swiss Federal Institute of Technology, and a year later he had earned a PhD in mathematics from the University of Budapest (with minors in physics and chemistry). He taught in Germany until 1930 when he came to Princeton.

Von Neumann did most of his pure mathematical research from 1925 to 1940. It was during this period that he essentially founded the area of game theory. He is said to have contributed in some significant way to most branches of mathematics, including set theory, logic, abstract algebra, and operator theory.

In 1943 von Neumann began work on the Manhattan Project. He was considered so important that he was one of the few scientists who had full knowledge of the entire project. His calculations were particularly instrumental in the success of the implosive design of the “Fat Man” nuclear bomb that was dropped on Nagasaki, Japan August 9, 1945.

Though he had a brilliant calculating mind, von Neumann was also a sociable, likeable person. He enjoyed throwing large parties, telling bawdy jokes, and playing pranks on his friends. Apparently his friends were not above returning the favor, according to an anecdote related in William Poundstone’s The Prisoner’s Dilemma.

[Once] a young scientist at the Aberdeen Proving Ground worked out the details of a mathematical problem beforehand and came up to von Neumann at a party. The scientist presented the problem as one that had been stumping him. Von Neumann gazed into the middle distance and began to calculate. Just as he was about to arrive at each intermediate result, the scientist interrupted, “It comes to this, doesn’t it?” Of course he was right each time. Finally the young scientist beat von Neumann to the answer. Von Neumann was shaken until he found out it was a setup.

Von Neumann’s work after the war was distinctly applied. He helped the United States develop the hydrogen (fusion) bomb ahead of the Soviet Union. He served as consultant to defense agencies, the CIA, and several corporations.

One of his most lasting contributions was to the design of the modem computer, which is known in computer science as the “Von Neumann architecture.” Among his ideas were that software programs should be stored on the computer as data (as opposed to being hard-wired separately), that the computer should work in a digital fashion (using discrete values like 0 and 1 rather than a continuous range of voltages), and that the computer should employ binary as its internal number system (rather than base 10 arithmetic). All popular modem computers share these very characteristics.

Von Neumann died from bone cancer in 1957, approximately one year after receiving the Medal of Freedom from President Dwight D. Eisenhower.

Graph Theory

In graph theory, a graph consists of a set of vertices, with some pairs of vertices joined by edges. Where the vertices are placed, and how the edges are drawn– straight or curved–doesn’t matter.

Graph theory was introduced by Leonhard Euler in the 1700s, and then further developed by mathematicians in the 1800s. Research in graph theory accelerated in the 1900s and is going strong in the 2000s. Although Euler used graphs to solve the Königsberg Bridge Problem in 1735, the first graph theory textbook did not appear until two centuries later, in 1936: Theorie der endlichen und unendlichen Graphen (Theory of finite and infinite graphs) by Denes König (1884–1944). See Section 5.12 for more on the Königsberg Bridge Problem.

Figure 3.19 A map and its graph.

We mentioned the Four Color Conjecture (now Theorem) earlier. This is really a theorem of graph theory in disguise. We can replace any map with a graph (see Figure 3.19), where each region is represented by a vertex, and two vertices are joined by an edge when the two regions share a boundary. In the language of graph theory, the Four Color Theorem says that the vertices of every planar graph (one that can be drawn in the plane without edge crossings) can be colored with four colors so that no two adjacent vertices are the same color.

Do you see how the vertices of the graph in the diagram can be colored with three colors so that no two adjacent vertices are the same color?

We have talked about planar graphs. Let’s take a look at a nonplanar graph, one that cannot be drawn in the plane without edge crossings. Our graph is the complete graph on five vertices, known as K$ (Figure 3.20). In a complete graph, every two vertices are joined by an edge. Try as we may, we cannot draw this graph on a flat sheet of paper so that no edges cross.

Figure 3.20 The complete graph on five vertices, K⁵.

Figure 3.21 Construction of a torus from a square.

However, we can draw this graph without edge crossings on a different surface. The surface is known technically as a torus, which is just a fancy way of saying a closed surface with a hole in it. This is the third shape in Figure 3.21.

In the square model of the torus, points on opposite edges are identified. Thus, we can wrap the square around and glue together its top and bottom edges. This produces the cylinder in the middle diagram. The cylinder is then wrapped around and the two circular ends are glued together to form the torus.

Figure 3.22 shows K$ on a torus without edge crossings. Each vertex is joined to every other vertex. Remember that lines going to the edge of the square come around to the other side.

Figure 3.22 A K⁵ on a torus.

A surface may have more than one hole. The number of holes is called the genus of the surface. In 1968 Gerhard Ringel (1919–2008) and J. W. T. Youngs (1910– 1970) proved that the minimum genus for a surface on which one can draw the complete graph K_n without edge crossings is

The notation [x] is the “ceiling function.” It outputs the least integer at least as large as x. Try the formula for n = 3, 4, and 5, to see that it gives the correct values.

Surfaces are studied in the branch of mathematics called topology. Topology is a generalization of ordinary geometry in which shapes can bend and stretch but not break.

Our time in history has been called the “Information Age,” and with good reason. People are interconnected more than ever by the Internet and telephone communication. The World Wide Web can be modeled by a graph in which the edges are directed. Jon Kleinberg (b. 1971) is a contemporary researcher in this area of information theory. His work has shown that it is useful to think of the Web’s structure as consisting of “authorities” and “hubs.” Authorities have information to disseminate, while hubs link to many authorities. The mathematics of directed graph networks is being developed by today’s mathematicians.

Paul Erds (1913–1996)

Paul Erds was bom in Budapest, Hungary, the son of two high school mathematics teachers. His two older sisters died of scarlet fever the day he was bom. He had a strange childhood. His father was captured in World War I, and spent six years in a Russian prisoner-of-war camp. His mother, after losing her daughters, was overly protective, not allowing Paul to go to school until age ten. He was quite a prodigy, being able to multiply three-digit numbers in his head at age three.

In 1934, at the age of 21, Erdos was awarded a doctorate in mathematics at Péter Pázmány University in Budapest. After graduation, with anti-Semitism increasing in Hungary, he moved to England, accepting a position at the University of Manchester. In 1938 he went for a year to the Institute for Advanced Study in New Jersey. During this year, he cofounded probabilistic number theory, one of many fields he started.

Beginning in the 1940s, Erdos became an itinerant world-traveler with no fixed address and no employment, living out of two half-filled suitcases. He collaborated with mathematicians in many countries, staying a few days to several months in each location, announcing upon his arrival that “My brain is open.”

Much of Erds’ early work was in number theory. His most famous accomplishment there was his proof, with Atle Selberg, of the Prime Number Theorem. This had been proven in the 19th century, but only by using the sophisticated machinery of complex analysis. Erdos and Selberg found an “elementary” proof, one that did not require complex analysis.

During his later career, Erds, while continuing to work in many areas, spent more time on discrete mathematics, pioneering several new branches, such as random graph theory (where the edges of a graph appear or don’t appear according to a probabilistic model).

Erds collaborated with so many mathematicians that the term “Erds number” was coined to describe how close any mathematician was to Erdos. Erdos himself has Erds number 0. Those who wrote a mathematical paper with Erdos have Erds number 1. Those who wrote a paper with someone having Erds number 1 have Erds number 2, and so on. There are 511 mathematicians with Erds number 1. Einstein’s Erds number is 2.

Erds was a colorful character, and many stories are told of him. One of his notions was The Book, a transfinite work in which God keeps every theorem, with its most elegant proof. Although whimsical, The Bookreflected Erds’ heartfelt Platonism, in which mathematics was discovered, not invented.

Erds was the second most prolific mathematician in history, after Euler. Partly powered by amphetamines, he continued to produce mathematics into his eighties, dying of a heart attack at a mathematics conference in Warsaw. In 1993 director George Csicsery made the documentary N Is a Number: A Portrait of Paul Erds, a fascinating window into the world of mathematical research, and the men and women who inhabit it.

Information Theory

Claude E. Shannon (1916–2001) was a pioneer in the field of information theory. He introduced the principle of entropy, which is randomness in an information channel. (Entropy is a concept in physics that Shannon transferred to information theory.) Shannon’s investigations were motivated by practical problems: transmitting over noisy phone lines or detecting and correcting errors in calculations on the primitive computers of the 1940s.

Information can be encoded as a stream of Os and Is. For example, the stream

might represent the words of a novel. If this information is stored and later retrieved, the person retrieving it could decode the stream and recover the words. In information theory, we are interested in the quantity of “information” conveyed by the symbol stream. If the two symbols, 0 and 1, are equally likely to appear, and the current symbol has no dependence on the previous symbols, then each new symbol conveys one bit of information. (“Bit” stands for “binary digit.”)

However, in the source output above, it seems that the symbol 1 is more prevalent than the symbol 0, although we see only a finite number of symbols. Twenty Is and ten 0s are shown. Hence, we may conjecture that 1 is twice as likely to occur as 0. Let’s assume this for the sake of argument. Thus, the probability that a 1 occurs is 2/3 and the probability that a 0 occurs is 1/3. We also assume that the currently output symbol has no dependence on any preceding symbols. This information stream is different from one in which the two symbols are equally likely. It is less random, since we can guess with some measure of certainty what the next symbol will be (bet on a 1). Correspondingly, the information source conveys less information than one

in which 0 and 1 are equally likely. When a symbol is revealed, it doesn’t convey as much information, since we knew in advance that the symbol was rather likely to be a 1. In information theory, randomness and information are synonymous terms.

How much information is conveyed in a stream? If the two symbols occur with probabilities p and 1 – p, then the entropy of the stream is defined as

Notice that the logarithms are base 2. (To compute logarithms base 2, use the formula log₂ x = In x/ In 2.) For our example stream, the entropy is

Each symbol in the stream reveals approximately 0.918296 bits of information.

One of Shannon’s theorems of information theory tells us how economically we can encode information. It says that the average number of Os and Is needed to encode a symbol is equal to the entropy (randomness) of the stream. Let’s apply this concept to our example. Perhaps we can devise a code that represents the same stream, but using fewer symbols. The standard way to accomplish this is to encode pairs of consecutive symbols. There are four possible pairs: 11, 10, 01, and 00. Given the probabilities of 1 and 0 occurring, the pairs occur with probabilities 4/9, 2/9, 2/9, and 1/9, respectively. The table shows an economical way to encode the pairs.

Notice that no code string is the prefix (beginning) of another code string. This allows us to decode a stream as it is output. Try encoding the above stream and note that the encoded stream requires fewer than thirty symbols.

Our encoding scheme requires, on average,

(The numbers in parentheses are the lengths of the code strings.) Since this code represents pairs of symbols, we divide the average number of bits by 2 to get the average number of bits necessary to encode each single symbol of the information stream: 17/18 ≈ 0.944444 bits. This is a reduction from 1 bit.

Shannon proved that the data stream can be encoded so that the average number of bits per source symbol is as close to the entropy as we like, but never below it. Thus, entropy is a measure of the compressibility of the information stream.

Perhaps the greatest applications of Shannon’s theory is to information conveyed over a channel with “noise” (distortion of information). If information is sent over an information channel, such as a computer connection, noise may result in loss of data. One of Shannon’s theorems states that, using an encoding procedure, information can be sent over a noisy information channel in a reliable way, without loss of information.

Claude E. Shannon (1916–2001)

Claude E. Shannon, the “father of information theory,” was bom in Michigan and did his undergraduate work at the University of Michigan, earning degrees in mathematics and electrical engineering. He did his graduate work at the Massachusetts Institute of Technology (MIT). In perhaps the most famous master’s thesis ever, he applied Boolean algebra to establish the mathematical theory of digital circuits. (The Russian Victor Ivanovich Shestakov (1907–1987) independently applied Boolean algebra to the problem, but published somewhat later.) Shannon’s PhD dissertation was An Algebra for Theoretical Genetics.

Shannon joined American Telephone and Telegraph’s Bell Laboratories in 1941. This famous industrial research institution gave us, in addition to Shannon’s information theory, transistors and the digital camera. Work done at Bell Labs has won seven Nobel prizes in physics. During the war, Shannon also worked on cryptography and on antiaircraft control systems.

Shannon published his groundbreaking paper on information theory in 1948. It was an immediate hit with engineers. It found wide applications. Shannon himself applied it to linguistics and to more lucrative pursuits, making a lot of money at blackjack and in the stock market.

In 1956 Shannon joined MIT, although he retained a connection with Bell Labs for many years after this. He retired in 1978 and died in 2001, a victim of Alzheimer’s disease

In addition to theory-building, Shannon enjoyed building strange machines. One of them was a mechanical/electronic device that solves Rubik’s Cube. Another is called the Ultimate Machine. You can probably find a video of this machine in action on YouTube.

The Millennium Prize Problems

Since David Hilbert gave his speech in 1900 outlining 23 important unsolved problems in mathematics, most of these problems have been solved. In 2000 the Clay Mathematics Institute announced a list of seven unsolved problems, known as the Millennium Prize Problems, whose solutions carry a prize of $1 million each. Since then, one of the problems, called the Poincaré Conjecture has been solved. The solver, Grigori Perelman, declined the prize.

Andrew Wiles, who proved Fermat’s Last Theorem in 1995, gave a vivid description of what it is like to be a mathematician trying to solve unsolved problems.

Perhaps I can best describe my experience of doing mathematics in terms of a journey through a dark unexplored mansion. You enter the first room of the mansion and it’s completely dark. You stumble around bumping into the furniture but gradually you learn where each piece of furniture is. Finally, after six months or so, you find the light switch, you turn it on, and suddenly it’s all illuminated. You can see exactly where you were. Then you move into the next room and spend another six months in the dark. So each of these breakthroughs, while sometimes they’re momentary, sometimes over a period of a day or two, they are the culmination of, and couldn’t exist without, the many months of stumbling around in the dark that precede them.

Andrew Wiles (b. 1953), from the Nova special, The Proof, 1997

Conclusion

Mathematics is not written in stone. Unsolved problems abound and new techniques await discovery. Mathematics is a living subject. Every mathematical fact was discovered by a person or a team and is part of human history. Future mathematical facts will also be discovered by humans. (Mathematicians are sometimes aided in their work by computers, both in the discovery and the proofs of results.) This section has given an indication of some exciting new developments and open vistas in mathematics. Knowing something about the problems helps us appreciate the ongoing nature and challenge of mathematical work. It also helps us understand the extent to which mathematics affects our daily lives.

EXERCISES

3.58 Find an estimate for the number of mathematical research articles published per year.

3.59 Look up Hilbert’s list of 23 problems. Report on one of them. What is the problem about? Is it solved? If so, who solved it?

3.60 Does the Diophantine equation x² + xy + y² = 3 have integer solutions?

3.61 Does the Diophantine equation 4x² + 4y² = 18 have integer solutions?

3.62 At Hilbert’s Grand Hotel, when infinitely many coaches arrive, each carrying infinitely many people, how can each person be given a room?

3.63 Show that a group has only one identity element.

3.64 This exercise concerns the field with elements {0,1,2,3,4} described in the text.

a) Below is a partial table of addition in this field. For example, 0 + 2 = 2 and 3 + 3 = 1. Complete the table.

b) Construct a multiplication table for the field.

c) Construct a subtraction table for the field. (Hint: a – b = c means a = b + c.)

d) Construct a division table for the field.

3.65 Look up and explain one or more of the common dilemma games or social dilemmas:

· chicken dilemma

· stag hunt dilemma

· tragedy of the commons

· free rider problem

3.66 Investigate the “tit for tat” solution to the iterated prisoner’s dilemma. Why does the method succeed?

3.67 Find a formula for the number of edges in the complete graph K_n.

3.68 Can K₆ be drawn on a torus without edge crossings? How about K₇ and K₈?

3.69 The graph K_3,3 consists of two sets of three vertices, and nine edges joining all pairs of vertices from the two sets. Draw K_3,3 on a torus without edge crossings.

3.70 Create a new 2-dimensional surface by starting with a square and identifying a pair of opposite sides, but twisting the square before joining them. The surface is called a Möbius strip. What unusual properties does this surface have?

3.71 Give an example of a map on a torus which requires five colors to be properly colored.

3.72 Find an encoding scheme for the information source shown on p. 212 that requires, on average, less than 17/18 bits per symbol.

3.73 Prove (using calculus) that the entropy of an information source with two symbols is maximized when the two sources occur with equal likelihood.

3.74 Look up the Millennium Prize Problems. Report on one of them. What is the problem about? Is it solved? If so, who solved it?

3.75 Investigate a branch of mathematics not listed in this chapter. What is the branch of mathematics about? What are some of its applications? Are there any important unsolved problems?