return

Celebratio Mathematica

Kenneth Ira Appel

Memories of Ken Appel

by Wolfgang Haken

Forty years ago, Ken Ap­pel asked me to give a talk in the Lo­gic Sem­in­ar about my work on “un­avoid­able sets of con­fig­ur­a­tions.” The reas­on was that one of my gradu­ate stu­dents, Thomas Os­good, had writ­ten his Ph.D. thes­is on that sub­ject and had asked Ken to be a mem­ber of his thes­is com­mit­tee. So Ken wanted to know what this work was about and what it had to do with the “Four-Col­or Prob­lem.” In fact, my re­search was in­ten­ded to be a con­tri­bu­tion to the work of Hein­rich Heesch to­wards a proof of the Four-Col­or The­or­em (then known as the Four-Col­or Con­jec­ture). Heesch had worked over 30 years on find­ing “re­du­cible con­fig­ur­a­tions,” hun­dreds of them, first by hand, and in later years mainly by com­puter.1 In my talk I men­tioned that the re­search­ers on the 4-Col­or Prob­lem were split in­to three groups:

  1. The “op­tim­ists” who were con­vinced that an “el­eg­ant” proof, cer­tainly without the use of com­puters, “must” ex­ist and just has to be found by some suf­fi­ciently en­lightened math­em­atician.

  2. The “skep­tics” who thought that there must ex­ist a counter­example be­cause all at­tempts to find an el­eg­ant proof had failed. Those re­search­ers were try­ing to find a counter­example; and for that pur­pose, the use of com­puters was cer­tainly per­miss­ible. Some re­mark­able re­du­cible con­fig­ur­a­tions were found by those skep­tics.

  3. The “mod­ern­ists” who thought that a nonel­eg­ant proof, in­volving mil­lions or even bil­lions of case-dis­tinc­tions, to be handled by a power­ful com­puter, should be at­temp­ted. Heesch should be re­cog­nized as the founder of this group.

Fi­nally, I sug­ges­ted that it might be use­ful to do more re­search on un­avoid­able sets of con­fig­ur­a­tions with the goal of find­ing such sets the mem­bers of which would be “likely to be re­du­cible” or at least “not already known to be ir­re­du­cible.” I con­cluded my talk say­ing that Os­good’s thes­is work in­dic­ated that this could be done, but that the “dream set” would likely con­tain between ten thou­sand and ten mil­lion con­fig­ur­a­tions. Thus, in or­der to make fur­ther pro­gress, a power­ful com­puter would be needed. But com­puter ex­perts had poin­ted out to me that com­puters were not suit­able for this kind of re­search. So I had de­cided to do no more work on this pro­ject, at least for sev­er­al years. Per­haps, in ten years, with more power­ful com­puters avail­able, I would learn pro­gram­ming and give it an­oth­er try.

To my total sur­prise, im­me­di­ately after my lec­ture, Ken Ap­pel came for­ward and told me he would be ready to do the com­puter work on this pro­ject right away. He was already fa­mil­i­ar with 15 dif­fer­ent ma­chine-lan­guages for sev­er­al gen­er­a­tions of com­puters. So he would do the pro­gram­ming him­self, rather than try to get a pro­fes­sion­al pro­gram­mer to do it for him.

The re­mark­able at­ti­tude of Ken’s made everything pos­sible from here on.

Every morn­ing we met in the cafet­er­ia; Ken came from the Com­puter Build­ing, car­ry­ing the print-out of the res­ults of last night’s com­put­ing. That print-out was a pack­age of large-format per­for­ated pa­per; oc­ca­sion­ally, the pack­age was 10 inches thick (al­most one cu­bic foot of pa­per — quite a load to carry for a man with back prob­lems; but he as­sured me he had a good chiro­pract­or.)

The print-out showed parts of an un­avoid­able set of con­fig­ur­a­tions. We looked it over and, al­most every time, we saw a pos­sib­il­ity to im­prove the pro­gram and to sim­pli­fy the res­ults. Ken worked in­cred­ibly fast (al­most as fast as I am slow) and in the even­ing he had the im­proved pro­gram ready to run. Then the next morn­ing’s pack­age was only about half as thick as the pre­vi­ous one. When the thick­ness of the pack­age was down to about 1/8 inch, we star­ted a more am­bi­tious at­tempt — and got thick­er pack­ages again.

This con­tin­ued with sur­pris­ing reg­u­lar­ity and in two years we were close to get­ting an un­avoid­able set of likely to be re­du­cible con­fig­ur­a­tions. Moreover, this set could be pro­jec­ted to be sur­pris­ingly small; “only” about five thou­sand con­fig­ur­a­tions. This was in the sum­mer of 1975, and we were quite happy about our pro­gress.

On the oth­er hand, Heesch did not be­lieve that our work would be of any help to­wards the fi­nal goal of ob­tain­ing an un­avoid­able set of re­du­cible con­fig­ur­a­tions. He be­lieved the only reas­on­able strategy was to get more and more re­du­cible con­fig­ur­a­tions. Un­for­tu­nately, he re­fused to co­oper­ate with us, and he held his col­lec­tion of re­du­cible con­fig­ur­a­tions strictly secret.

At this point, we were so op­tim­ist­ic about our ap­proach that we did not want to quit. So we had to do our own re­du­cib­il­ity com­pu­ta­tions. Again this did not dis­cour­age Ken. He en­lis­ted the help of his gradu­ate stu­dent, John Koch, and, start­ing from scratch, they had the com­pu­ta­tions go­ing in a short time.

Mean­while, the work on the un­avoid­able set had pro­gressed so far, that fur­ther im­prove­ments could be done by hand — good for me since I had not yet learned com­puter pro­gram­ming. We still thought that we were many years away from fi­nal suc­cess, in par­tic­u­lar since some of the con­fig­ur­a­tions to be checked for re­du­cib­il­ity were too big for the avail­able com­puters.

But half a year later, things looked bet­ter again; only about 2000 con­fig­ur­a­tions had to be com­puted and, most im­port­antly, none of them were “over­sized”. Per­haps this could be done in 2 years, provided that we would get enough com­puter-time gran­ted.

Then came the last big sur­prise. In the spring of 1976, a Cy­ber-com­puter — the most power­ful com­puter avail­able then — was in­stalled on our cam­pus. Of course, there was much com­pet­i­tion for its use. But, typ­ic­al for Ken, he had his pro­gram ready long be­fore the pro­fes­sion­al pro­gram­mers.

So for a while, Ken was the only one to use that com­puter. The first 2 weeks were dis­ap­point­ing — noth­ing but in­stall­a­tion — and start-up prob­lems. But then he got all the com­pu­ta­tions we needed done in 2 months — rather than in the hoped for 2–7 years. It took us two more weeks to be­lieve that we really had it!

Thank you Ken!

We miss you, but we are happy for the time you were with us.