by Wolfgang Haken
Forty years ago, Ken Appel asked me to give a talk in the Logic Seminar about my work on “unavoidable sets of configurations.” The reason was that one of my graduate students, Thomas Osgood, had written his Ph.D. thesis on that subject and had asked Ken to be a member of his thesis committee. So Ken wanted to know what this work was about and what it had to do with the “Four-Color Problem.” In fact, my research was intended to be a contribution to the work of Heinrich Heesch towards a proof of the Four-Color Theorem (then known as the Four-Color Conjecture). Heesch had worked over 30 years on finding “reducible configurations,” hundreds of them, first by hand, and in later years mainly by computer.1 In my talk I mentioned that the researchers on the 4-Color Problem were split into three groups:
The “optimists” who were convinced that an “elegant” proof, certainly without the use of computers, “must” exist and just has to be found by some sufficiently enlightened mathematician.
The “skeptics” who thought that there must exist a counterexample because all attempts to find an elegant proof had failed. Those researchers were trying to find a counterexample; and for that purpose, the use of computers was certainly permissible. Some remarkable reducible configurations were found by those skeptics.
The “modernists” who thought that a nonelegant proof, involving millions or even billions of case-distinctions, to be handled by a powerful computer, should be attempted. Heesch should be recognized as the founder of this group.
Finally, I suggested that it might be useful to do more research on unavoidable sets of configurations with the goal of finding such sets the members of which would be “likely to be reducible” or at least “not already known to be irreducible.” I concluded my talk saying that Osgood’s thesis work indicated that this could be done, but that the “dream set” would likely contain between ten thousand and ten million configurations. Thus, in order to make further progress, a powerful computer would be needed. But computer experts had pointed out to me that computers were not suitable for this kind of research. So I had decided to do no more work on this project, at least for several years. Perhaps, in ten years, with more powerful computers available, I would learn programming and give it another try.
To my total surprise, immediately after my lecture, Ken Appel came forward and told me he would be ready to do the computer work on this project right away. He was already familiar with 15 different machine-languages for several generations of computers. So he would do the programming himself, rather than try to get a professional programmer to do it for him.
The remarkable attitude of Ken’s made everything possible from here on.
Every morning we met in the cafeteria; Ken came from the Computer Building, carrying the print-out of the results of last night’s computing. That print-out was a package of large-format perforated paper; occasionally, the package was 10 inches thick (almost one cubic foot of paper — quite a load to carry for a man with back problems; but he assured me he had a good chiropractor.)
The print-out showed parts of an unavoidable set of configurations. We looked it over and, almost every time, we saw a possibility to improve the program and to simplify the results. Ken worked incredibly fast (almost as fast as I am slow) and in the evening he had the improved program ready to run. Then the next morning’s package was only about half as thick as the previous one. When the thickness of the package was down to about 1/8 inch, we started a more ambitious attempt — and got thicker packages again.
This continued with surprising regularity and in two years we were close to getting an unavoidable set of likely to be reducible configurations. Moreover, this set could be projected to be surprisingly small; “only” about five thousand configurations. This was in the summer of 1975, and we were quite happy about our progress.
On the other hand, Heesch did not believe that our work would be of any help towards the final goal of obtaining an unavoidable set of reducible configurations. He believed the only reasonable strategy was to get more and more reducible configurations. Unfortunately, he refused to cooperate with us, and he held his collection of reducible configurations strictly secret.
At this point, we were so optimistic about our approach that we did not want to quit. So we had to do our own reducibility computations. Again this did not discourage Ken. He enlisted the help of his graduate student, John Koch, and, starting from scratch, they had the computations going in a short time.
Meanwhile, the work on the unavoidable set had progressed so far, that further improvements could be done by hand — good for me since I had not yet learned computer programming. We still thought that we were many years away from final success, in particular since some of the configurations to be checked for reducibility were too big for the available computers.
But half a year later, things looked better again; only about 2000 configurations had to be computed and, most importantly, none of them were “oversized”. Perhaps this could be done in 2 years, provided that we would get enough computer-time granted.
Then came the last big surprise. In the spring of 1976, a Cyber-computer — the most powerful computer available then — was installed on our campus. Of course, there was much competition for its use. But, typical for Ken, he had his program ready long before the professional programmers.
So for a while, Ken was the only one to use that computer. The first 2 weeks were disappointing — nothing but installation — and start-up problems. But then he got all the computations we needed done in 2 months — rather than in the hoped for 2–7 years. It took us two more weeks to believe that we really had it!
Thank you Ken!
We miss you, but we are happy for the time you were with us.
