Peter M. Neumann, 1940–2020

Memories from Oxford days

Mathematical Institute src

Peter Neumann, Professor of Mathematics at Queen’s College, Oxford University, passed away two weeks ago. Last Monday would have been his 80th birthday.

Today we join others mourning in private and remembering in public, including the authors of these stories and memories, who are among Peter’s 39 graduated doctoral students.

Peter died from Covid-19 while in a care home for long treatment of a stroke that had paralyzed one side two years ago—something he wrote he could recover from “no earlier than late 2020.” From the number of people we know who have been touched closely by this kind of happening, my family included, we have a small statistical window on a great tragedy. The one resolution we can most make for the New Year is that it bring a resolution, so that the progression Covid 19-20-21 stops there.

The two words that most define Peter for me are genial and acute. I knew him from the beginning of my time as a graduate student at Oxford under a Marshall Scholarship in 1981. Every “don” at Oxford is associated to one of the thirty-nine residential colleges or six private halls. I joined Merton College to associate with my advisor, Dominic Welsh, but also there was Peter Cameron, whose memories are linked above and who joined Merton’s faculty after earning his doctorate under Peter in 1971. Perhaps that contributed to why Peter—that is, Neumann—kept up spelling his name Πeter.

The Kinderseminar

Early in my first term, Peter invited me to join a special weekly seminar hosted by Πeter in his expansive room in Queen’s College. It was already called the Kinderseminar, for it was directed to the graduate students for experience reading current research papers and, importantly, presenting them. It always began at 11am and had flexible time after noon because college lunches at Oxford typically began at 12:20 or 12:30 for students and 1pm for fellows.

It is hard to replicate the atmosphere anywhere I have seen in the US. There was at least one big comfy chair, in which I remember Peter’s student Sarah Rees almost disappearing, and other chairs brought in around a coffee table for tea and—much more often—coffee. And a roll of McVitie’s that was passed around. High windows let in enough light to work lamps-off except on the darkest days. Lugged to the head of the table when the time for chitchat was over was a portable chalkboard. Then began a masterclass in how to give a masterclass.

Queen’s College toward his rooms at right. (Photo by Odicalmuse, own work.)

We have already mentioned the seminar a number of times on this blog. Two of those mentions recall a lecture by Πeter himself on Évariste Galois, whose ulterior point was to warn the dangers of carelessly using phrases like “it is easy to see that…” in proofs. Well Galois, explained Πeter, was writing in haste the night before the duel that killed him, but most of us don’t have that excuse. Here is a preserved later lecture by Πeter on Galois.

The most recent post featured Norman Biggs, who visited Oxford and took part in the seminar for some of my first year. My own first presentation in the seminar was on alternate proofs I’d found in my Princeton undergraduate thesis of theorems covered in a textbook by Biggs. He gave me the nice compliment of saying that if his text went to a second edition he could use my proofs.. But Πeter—ah, Πeter took me aside afterward and pointed out my kinks in delivering them, including body positioning and organizing diagrams and algebra on the board. Encouragingly, of course.

Also a regular was my fellow Mertonian and chess master Dugald Macpherson. Neither of us was the most illustrious chess player to enter that room, for grandmaster Colin McNab obtained his doctorate under Πeter shortly after I finished. I was more impressed by stories of playing first-class cricket in Jamaica by the visiting Ken Johnson. Thirty years later, when I emerged from my car in Princeton’s south campus parking lot and boarded a jitney going to the 2012 Alan Turing Centennial event covered here, there was Johnson—who is now a professor at Penn State. Other students I have particular memories of there are Muhammad Audu, Jacinta Covington, and Tim Penttila.

One quirky memory was coming in on Tuesday, Oct. 25, 1983, to find everyone around a radio bringing bulletins of the US invasion of Grenada which had begun at local dawn. After some pointed anti-imperialist disapproval they did get into math, but my mind stayed on Grenada as I composed in my head a steel-drum melody and the first verse of a still-unfinished song about the event.

Another Memory

Because his OBE from Queen Elizabeth in 2008 says Peter not Πeter, I will revert to the former. This was cited for services to mathematics education. He not only won other prizes, he has a prize named after him: the Neumann Prize by the British Society for the History of Mathematics. Peter served once as its president and also led the British Mathematical Association—whose logo spells its name with a lowercase .

Mathematical Association home

From various experiences I can aver that Peter took a whole-person approach to education. He followed the lives of his former students and I heard stories of social occasions in both Britain and France. He also wrote the Oxford Mathematical Institute’s guide to TeX and LaTeX for students.

In May, 1984, the Institute organized an outing to a Mathematics Day at the University of Warwick near Coventry, about 55 miles north of Oxford. Peter organized about a dozen for the trip—whether this was everyone coming from Oxford, and whether we had one shuttle or separate cars, I do not recall.

What I do recall is that he did not simply take us to and from the workshop. He planned a picnic en-route at the Rollright Stones, which are along a road at the Oxon-Warks border. I had not previously seen a Celtic stone circle. He told stories of its history. I also believe that after the meeting we took a drive into Coventry with a brief stop to walk around the cathedral to see the damage from World War II, but it is possible I am conflating that with a time the Oxford chess team played a match in Coventry.

“Visit baby Stonehenge” src

Instances and Problems in Ancient Complexity

Peter carried the Neumann pedigree in group theory, for it was the specialty of both his mother and his father. He supervised another friend from Merton, Julia Tompson, in a thesis on the history of the Jordan-Hölder theorem. But I will discuss a contribution in which group theory is in the background—where I can put ideas from computational complexity in the foreground.

Our May 2014 post “STOC 1500” had a semi-serious intent of aligning famous classical problems of geometric (non-)constructibility with modern complexity theory. It has a fantasized keynote by the chess master and mathematician Luca Pacioli introducing the “?” problem: using Euclid’s ruler and compass alone, can one trisect an angle, double a cube, or (going beyond ) square a circle? Much as we’re at pains to say that “” does not stand for “non-polynomial,” the name “” does not stand for “non-constructible” but rather constructible by neusis, meaning using fixed marks on a rotatable ruler. Of course, now we know that , a fact often attributed to Galois theory but, as Peter noted in his paper, provable from simpler considerations about field extensions.

Both “Ancient Complexity” and computational complexity have a key distinction between instances and problems. Trisecting a angle is an easy instance. If is a constructible angle, then the angle can be trisected—but the method is ad hoc to that instance, not a single algorithm that given only would efficiently discover how to trisect it. There are algorithms that work correctly on multiple angles but not on all of them.

What is most different from computational complexity is that there are single instances that cannot be solved, such as . It is not a case of a Euclid-based algorithm taking too long: no algorithm can construct a angle, period. This is akin to how a single string can be incompressible in Kolmogorov complexity, but without the latter’s dependence on a reference universal compression scheme.

Another difference is problems, such as doubling the cube and squaring the circle, that essentially have only one instance. One can impose algebraic coordinates to represent different instances of them, but that is different from defining the coordinates from features of a given instance, as allowed when marking a ruler for neusis. Peter’s paper speaks these problem/instance distinctions well.

The Reflection Problem

The problem addressed in Peter’s paper was formulated by Ptolemy in the year 150. Given a circle and points and , both inside or both outside , construct a point on so that light starting from will reflect at and go to . When the points are inside, this is imagined as shooting a perfect billiard ball from off a circular rim to hit .

There are two algorithms in that correctly solve an infinite set of instances, namely points equidistant from the center of the circle. One constructs the midpoint of the line segment between and , projects the ray from to , and finds where the ray intersects . The other (shown in the above figure) first finds the intersections of the rays from to with , bisects the line segment connecting them, and uses that to project outward to . The latter algorithm also works on points that are collinear with the rays to and , respectively, while the former is correct for pairs taken from the lines through and that are parallel to . If is not available, the methods can be combined—to work on the original equidistant cases.

Around the year 1020, Hasan Ibn al-Haytham presented a geometric algorithm that works in all cases, using conic sections in ways equivalent to neusis and further characterized this millennium by Roger Alperin of San José State. The problem was apparently not shown to be outside until a 1965 paper by Jack Elkin.

After considering solvable cases like the above in his paper, Elkin ended by giving a single non- case, analogous to for the trisection problem. His example did show the general algebraic ingredients. What Peter did in his 1998 paper, evidently unaware of Elkin’s, was to characterize all the -solvable cases and show that they form a set of measure zero. Thus, he gave a rigorous sense in which almost all instances of the reflection problem are not -solvable. The algebra and lemmas about field extensions and irreducibility are especially pretty in Peter’s paper.

Open Problems

Our condolences go to Peter’s wife Sylvia, his family, and all who knew him.

Discovering Alperin’s equivalences while writing this post leads me to re-pose this question from the “STOC 1500” post: is there a single problem that is -complete under -reductions?

Like this:

Like Loading...

Related

from Hacker News https://ift.tt/3oddngo