MacTutor
Kenneth Appel, who has died aged 80, was a mathematician who, with his colleague Wolfgang Haken and with the aid of an IBM computer, solved a problem concerning colours on a map that had been perplexing the world's best brains for over a century.
The problem had been identified in 1852 by a young Englishman called Francis Guthrie, who was colouring a map of the English counties when he noticed that he needed only four colours to complete the map so that no two neighbouring counties were the same colour. He wrote to his mathematician brother, Frederick, to ask whether the theory that, however boundaries change, only four colours are needed to colour a map of the world had a mathematical proof. Frederick did not know -- and neither did anyone else.
Guthrie's problem, known as the four-colour conjecture, continued to intrigue and baffle for the next 120 years. Between 1852 and 1976 it occupied the minds of mathematicians of every stripe, from Lewis Carroll to the Bishop of London. In 1879 the London barrister and amateur mathematician Alfred Bray Kempe thought that he had cracked it, and his solution was so good that 11 years passed before anyone realised that he had, in fact, failed. In 1890 it was shown conclusively that any map can be filled in with five colours, but it was not until 1976 that Appel and Haken, at the University of Illinois, showed the four-colour conjecture was correct.
The two men estimated that as mathematicians had already spent more than 10 million hours beavering away on the problem, it was a proof that would be impossible for any person to perform -- or to check -- by hand. Instead, they decided to get a computer to do most of the job for them.
They began by showing that the universe of all possible maps must contain what mathematicians call an unavoidable set of 1,936 different configurations. They then recruited a computer science graduate, John Koch, and persuaded the university to let them use its state-of-the-art IBM 370-168 computer (a lumbering monster) to prove that each configuration could be rendered on a map using only four colours.
The complexity of the mathematics involved in cracking a problem which seems, superficially, to be relatively simple, was reflected in the fact that it took 1,200 hours of computer time and involved some 10 billion logical steps.
In the summer of 1976, Appel and Haken announced their result to their colleagues by leaving a note on the department blackboard: "Four colors suffice." The proof of the four-colour conjecture was published in 1977 in the Illinois Journal of Mathematics.
But the article caused a furore, with some welcoming the pioneering use of computer power to solve a seemingly intractable puzzle, while others were outraged that the inscrutable -- and (because of the amount of work needed) uncheckable -- deliberations of a computer could be considered "proof" of anything. A Scientific American cover announced "The Death of Proof", and while their achievement won Appel and Haken a prize from the American Mathematical Society and the Mathematical Programming Society in 1979, the head of one university Mathematics department barred them from meeting his graduate students lest they contaminate them. "The problem had been taken care of by a totally inappropriate means," the man complained, as a result of which "A decent proof might be delayed indefinitely."
But soon after the proof was announced, Haken's son, Armin, gave a lecture on it and found that his audience was divided into those who would not trust the computer, and those who would not trust human line-by-line calculations. The advocates of pen and paper were typically over 40, while their opponents were under 40. As Robert Matthews observed in an article in The Sunday Telegraph: "Armin Haken's straw poll suggests that by about 2035 the naysayers will be dead and Appel and his father's computer-assisted proof will be no more controversial than a proof by Euclid."
The son of an electrical engineer, Kenneth Ira Appel was born on October 8 1932, in Brooklyn, New York, and grew up in Queens, graduating from Queens College with a degree in Mathematics in 1953.
After two years in the Army, Appel enrolled at the University of Michigan, where he took a PhD in Mathematics in 1959. After a couple of years with the Institute for Defense Analyses in Princeton, New Jersey, doing research in cryptography and number theory for the government, he joined the University of Illinois as a professor in 1961. In 1993 he became chairman of the Mathematics department at the University of New Hampshire. He retired in 2003.
Kenneth Appel is survived by his wife, Carole, and by two sons. A daughter predeceased him.
Kenneth Appel, born October 8 1932, died April 19 2013
© Telegraph
The problem had been identified in 1852 by a young Englishman called Francis Guthrie, who was colouring a map of the English counties when he noticed that he needed only four colours to complete the map so that no two neighbouring counties were the same colour. He wrote to his mathematician brother, Frederick, to ask whether the theory that, however boundaries change, only four colours are needed to colour a map of the world had a mathematical proof. Frederick did not know -- and neither did anyone else.
Guthrie's problem, known as the four-colour conjecture, continued to intrigue and baffle for the next 120 years. Between 1852 and 1976 it occupied the minds of mathematicians of every stripe, from Lewis Carroll to the Bishop of London. In 1879 the London barrister and amateur mathematician Alfred Bray Kempe thought that he had cracked it, and his solution was so good that 11 years passed before anyone realised that he had, in fact, failed. In 1890 it was shown conclusively that any map can be filled in with five colours, but it was not until 1976 that Appel and Haken, at the University of Illinois, showed the four-colour conjecture was correct.
The two men estimated that as mathematicians had already spent more than 10 million hours beavering away on the problem, it was a proof that would be impossible for any person to perform -- or to check -- by hand. Instead, they decided to get a computer to do most of the job for them.
They began by showing that the universe of all possible maps must contain what mathematicians call an unavoidable set of 1,936 different configurations. They then recruited a computer science graduate, John Koch, and persuaded the university to let them use its state-of-the-art IBM 370-168 computer (a lumbering monster) to prove that each configuration could be rendered on a map using only four colours.
The complexity of the mathematics involved in cracking a problem which seems, superficially, to be relatively simple, was reflected in the fact that it took 1,200 hours of computer time and involved some 10 billion logical steps.
In the summer of 1976, Appel and Haken announced their result to their colleagues by leaving a note on the department blackboard: "Four colors suffice." The proof of the four-colour conjecture was published in 1977 in the Illinois Journal of Mathematics.
But the article caused a furore, with some welcoming the pioneering use of computer power to solve a seemingly intractable puzzle, while others were outraged that the inscrutable -- and (because of the amount of work needed) uncheckable -- deliberations of a computer could be considered "proof" of anything. A Scientific American cover announced "The Death of Proof", and while their achievement won Appel and Haken a prize from the American Mathematical Society and the Mathematical Programming Society in 1979, the head of one university Mathematics department barred them from meeting his graduate students lest they contaminate them. "The problem had been taken care of by a totally inappropriate means," the man complained, as a result of which "A decent proof might be delayed indefinitely."
But soon after the proof was announced, Haken's son, Armin, gave a lecture on it and found that his audience was divided into those who would not trust the computer, and those who would not trust human line-by-line calculations. The advocates of pen and paper were typically over 40, while their opponents were under 40. As Robert Matthews observed in an article in The Sunday Telegraph: "Armin Haken's straw poll suggests that by about 2035 the naysayers will be dead and Appel and his father's computer-assisted proof will be no more controversial than a proof by Euclid."
The son of an electrical engineer, Kenneth Ira Appel was born on October 8 1932, in Brooklyn, New York, and grew up in Queens, graduating from Queens College with a degree in Mathematics in 1953.
After two years in the Army, Appel enrolled at the University of Michigan, where he took a PhD in Mathematics in 1959. After a couple of years with the Institute for Defense Analyses in Princeton, New Jersey, doing research in cryptography and number theory for the government, he joined the University of Illinois as a professor in 1961. In 1993 he became chairman of the Mathematics department at the University of New Hampshire. He retired in 2003.
Kenneth Appel is survived by his wife, Carole, and by two sons. A daughter predeceased him.
Kenneth Appel, born October 8 1932, died April 19 2013
© Telegraph