April 30, 2013 | Alumni
April 29, 2013
Kenneth I. Appel, who helped usher the venerable mathematical proof into the computer age, solving a longstanding problem concerning colors on a map with the help of an I.B.M. computer making billions of decisions, died on April 19 in Dover, N.H. He was 80.
The cause was esophageal cancer, which was diagnosed in October, his son Andrew said.
Since the time of Euclid and Pythagoras, proofs of mathematical theorems had consisted of long strings of equations or geometric notations that any mathematician could read and quibble with, all marching logically, step by step, toward a conclusion. But the proof that Dr. Appel and a colleague, Wolfgang Haken, established in 1976 was of a different order.
Their conclusion, that four colors would suffice for any map, depended on 1,200 hours of computer time — the equivalent of 50 days — and 10 billion logical decisions all made automatically and out of sight by the innards of an I.B.M. computer at the University of Illinois in Urbana.
Hailed in some circles, including this newspaper, as “a major intellectual feat,” the proof shepherded computers toward a greater role in higher math. But it made many mathematicians uneasy; they worried about computer bugs and wondered how they could check or understand a “proof” they could not see. And it ignited a long-running debate about what constitutes a mathematical proof.
“Like a landmark Supreme Court case, the proof’s legacy is still felt and hotly debated,” said Edward Frenkel, a mathematician at the University of California, Berkeley.
Kevin Short, a mathematician at the University of New Hampshire, where Dr. Appel spent his later years, called the feat “a watershed for modern mathematics.”
“It has spawned whole fields of study,” he said.
Kenneth Ira Appel (pronounced ah-PEL) was born on Oct. 8, 1932, in Brooklyn and grew up in Queens, where he graduated from Queens College with a degree in mathematics in 1953. His father, Irwin, was an electrical engineer, and his mother, the former Lillian Sender, had been an office worker.
After a short stint as an actuary and two years in the Army, Kenneth Appel enrolled at the University of Michigan, where he earned a Ph.D. in math in 1959. During the summers, he programmed computers for Douglas Aircraft.
Dr. Appel soon went to work for the Institute for Defense Analyses in Princeton, N.J., doing research in cryptography and number theory for the federal government. He joined the University of Illinois as a professor in 1961. Long interested in Democratic politics, he also served a term on the Urbana City Council.
Some of the thorniest problems in math are simple to state but hideously complex under the surface. Such is the case with the four-color theorem, first enunciated by an English mapmaker, Francis Guthrie, in 1852. He asserted that to create a map in which no adjacent countries are the same color, only four colors are needed. Although everyone believed it was true, proof had eluded a century of mathematicians until Dr. Appel attended a lecture in 1972 by Dr. Haken.
Because of the bewildering variety of map configurations, Dr. Haken was contemplating using computers to solve the problem, but as he related in his lecture that evening, experts had convinced him that it was not possible.
Dr. Appel, familiar with computers from his defense and government work, was more optimistic.
“I don’t know of anything involving computers that can’t be done; some things just take longer than others,” he said to Dr. Haken afterward, according to an account in the journal Social Studies of Science by Donald MacKenzie of the University of Edinburgh.
“Why don’t we take a shot at it?”
The two started off by showing that the universe of all possible maps must contain what mathematicians call an “unavoidable set” of 1,936 different configurations. One configuration might be a country surrounded by four neighbors, for example.
Their task, then, was to prove that each of these configurations could be rendered on a map using only four colors in such a way that no two adjacent land areas were of the same color. That was where the heaviest computation would come in. To help, they recruited a computer science graduate student, John Koch, and Dr. Appel persuaded the university to let them use its I.B.M. 370-168 computer, newly acquired for administrative services.
Those were the days when computers filled an entire room, although their memory capacities were minuscule compared with a modern smartphone. Dr. Short recounted an occasion, as described by Dr. Appel, when the computer gave an unexpected answer.
“Oh, that wire must have fallen out again,” Dr. Appel said.
Dr. Appel began to think of the computer as a partner, though with a different kind of brain, with almost “an artificial intelligence,” he told Dr. MacKenzie.
“The computer was, to the best of my feeling about the subject, not thinking like a mathematician,” he said. “And it was much more successful, because it was thinking not like a mathematician.”
In the summer of 1976, Dr. Appel and Dr. Haken announced their result to their colleagues by leaving a note on the department blackboard: “Four colors suffice.” Their work was published in 1977 in the Illinois Journal of Mathematics.
Their four-color proof earned newspaper headlines and a prestigious award in mathematics, the Delbert Ray Fulkerson Prize. But the notion of computer proofs drew skepticism in some academic circles. In a visit to one university, Dr. Appel and Dr. Haken said, professors barred them from meeting graduate students lest the students’ minds become contaminated.
Dr. Appel became the chairman of the mathematics department at the University of New Hampshire in 1993. He retired in 2003. He also served on the Dover School Board and for a time was the treasurer of the Strafford County Democratic Party.
Before their revolutionary work was published, Dr. Appel and Dr. Haken enlisted their entire families to check hundreds of pages of calculations, making sure that diagrams of map configurations matched the computer printouts and did not have typos. Andrew Appel said his sister, Laurel, found some 800 mistakes, most of which she could fix herself.
Laurel F. Appel, a biology professor at Wesleyan University, died this year. Besides his son Andrew, a computer science professor at Princeton, Dr. Appel is survived by his wife, the former Carole S. Stein; another son, Peter; a sister, Lois Green; and five grandchildren.
Despite the criticism in more traditionalist quarters, Dr. Appel never agonized about his reliance on a computer to arrive at the four-color theorem, his son Andrew said. The mathematician Alan Turing, he noted, had shown long ago that even very short theorems could have very long proofs, running hundreds of pages. As his son recalled, Dr. Appel used to say, “Without computers, we would be stuck only proving theorems that have short proofs.”
Originally published by The New York Times