The interviewer is Robert Calderbank, editor-in-chief of the IEEE Transactions on Information Theory.
The photograph was taken by Laine Whitcomb, Photographer, 105 East 2nd St. NY NY 10009; (212) 677 6754.
A: During my years as an undergraduate at the University of Melbourne (in Australia) I had a scholarship from the state phone company, which in those days was called the Postmaster General's Department. So in a sense I have been working for "the phone company" ever since 1956. I think that's the main reason I chose engineering rather than mathematics, because of this scholarship. In fact I ended up doing two four-year undergraduate degrees more or less simultaneously, one in electrical engineering and one in math.
I remember that during the summer breaks we had to learn how to erect telephone poles, to splice cables with hot lead while sitting at the top of these poles, to test telephone circuits, to drive 10-ton trucks, and so on.
After I got my math degree in 1960, I worked for the PMG's department in Sydney for a year (designing minimal cost telephone networks).
Originally I was planning to apply to several graduate schools in the U.S. However, Harvard said they were sorry, but they didn't have an engineering department. Cornell offered me a fellowship right away, and it was such a hassle filling out all the forms that I didn't apply anywhere else. [One form had to be signed by a professor in the English department, to certify that I could speak the language. No doubt they had had problems with Australians in the past.]
Nick DeClaris was my initial supervisor there, and I've always been grateful to him for his support. In those days I was working on circuit theory and graph theory.
Q: How did you get involved with coding theory?
A: Probably because of my math background, Fred Jelinek suggested that it was a field that might interest me, and it was. But I didn't really get into coding until after I had furnished my Ph.D., which was on Perceptrons, or what are now called neural networks, under Frank Rosenblatt. I studied the propagation of signals in large random directed graphs.
Q: And Bell Labs?
A: When I started working on coding theory I had a copy of the manuscript of Elwyn Berlekamp's marvelous book on algebraic coding theory. He was offering a dollar for each mistake, and I made several hundred dollars this way. This led to a summer job at Murray Hill in 1968, when Elwyn and I wrote several nice papers on the weight distribution of Reed-Muller codes [for example, "The weight enumerator for second-order Reed-Muller codes," IEEE Trans. Inform. Theory, IT-16 (1970), 745-751], and then to a permanent job in 1969.
Q: You had heard of Bell Labs even in Australia?
A: Yes indeed! I can't remember when I started subscribing to the Bell System Technical Journal, but it was in the early 1960's. Individual subscriptions were quite inexpensive. It was an impressive journal, on heavy glossy paper, with a good smell to it. And of course full of papers on circuit theory and communications. It was always my dream to work at Bell Labs. People from Murray Hill like Vaclav Benes, Irwin Sandberg, and Aaron Wyner were frequently seen in the electrical engineering department at Cornell, on recruiting trips, or just to visit and give a talk. So one was always being reminded of Bell Labs' existence.
Even at the end of my first year as a graduate student at Cornell, in 1962, I managed to arrange a summer job at Bell Labs in Holmdel. This was still on minimal cost networks. During that summer I met another of my heroes, John Riordan, one of the great early workers in combinatorics. His book An Introduction to Combinatorial Analysis is a classic. He was working at Bell Labs in West Street in Manhattan at that time. One of my earliest papers, on a problem that came up in my thesis work, was a joint paper with him. [ "The enumeration of rooted trees by total height," J. Australian Math. Soc. 10 (1969), 278-282.]
It was also because of people like John Riordan, Ron Graham, Elwyn Berlekamp, Aaron Wyner, Larry Shepp, Ed Gilbert, Dave Slepian, Colin Mallows and so on that I was eager to come to Bell Labs. At that time there was no one at Cornell who was interested in discrete mathematics.
Of course another person I worked with a lot was Jessie MacWilliams, although I didn't meet her until I came to the Labs in 1968.
Q: How did you come to meet John Conway?
A: That's a long (and interesting) story. In 1968 Jessie MacWilliams' daughter Anne was a graduate student at Cambridge University, a student of John Thompson, and one day she wrote home to her mother to say that there was a lot of excitement at Cambridge because John Conway had just discovered a new simple group. This was connected with a certain packing of spheres in twenty-four dimensions. I remember she described it in her letter as a very tightly packed basket of gooseberries - only twenty-four dimensional gooseberries. This was the Leech lattice, which John Leech had published a year or so earlier. [J. Leech, Notes on sphere packings, Canad. J. Math., 19 (1967), 251-267.]
Conway had found the automorphism group of this lattice, the now famous group Co.0 (also known as .0, which is pronounced "dot-oh"). [J. H. Conway, A perfect group of order 8, 315, 553, 613, 086, 720, 000 and the sporadic simple groups, Proc. Nat. Acad. Sci. U.S.A., 61 (1968), pp. 398-400 -- an excellent title for a paper!]
Q: And so this led you to John Leech?
A: Yes, I read his two long papers on sphere packings, and it was obvious that what he was really doing was taking binary codes and lifting them to form lattices. In the simplest case, which I immediately called "Construction A", the centers of the spheres are all the points which reduce to codewords when read mod 2.
This was very nice: taking the even weight code of length n one obtained the n-dimensional checker-board lattice - in three dimensions that's the face-centered cubic lattice, the densest sphere-packing known in three dimensions. The same code also gives the densest sphere packings known in dimensions 4 and 5. If you take the Hamming codes of lengths 7 and 8 you get the densest packings known in 7 and 8 dimensions (these are called the E_7 and E_8 lattices).
Construction A works well with codes of minimal distance 2 or 4. To make use of codes with higher minimal distance I formalized another of Leech's constructions, which I called Construction B - this is the same as Construction A except that the sum of the coordinates of the centers must be an even number.
This works very nicely with codes having minimal distance 8. For example, the first-order Reed-Muller code of length 16 immediately produces the Barnes-Wall lattice in 16D. A small variation (Construction B*) converts the Golay code of length 24 into the Leech lattice. And finally I generalized another of Leech's constructions that worked in higher dimensions - naturally I called this Construction C.
I was preparing to talk on sphere packing for a local meeting of the Math. Assoc. America, at Seton Hall University, I think - this would have been in 1969, when I realized that the constructions could be applied to nonlinear codes. In particular, I knew about some nonlinear single-error-correcting codes of lengths 8 through 11 that were better than shortened Hamming codes. Construction A immediately produced new record packings in dimensions 9 to 12.
There are simple formulae that say how good these packings are. If you start with a code of length n, distance 4 and having M codewords, you get an n-dimensional sphere packing with center density
and kissing number
where A4 is the number of codewords of weight 4.
So Golay's nonlinear code of length 9, with 20 codewords, 18 of which have weight 4, produces a 9-D packing with kissing number 18+16.18 = 306, which was a new record. What's more, this was the first time anyone had found a nonlattice packing that was better than any lattice packing.
I remember rushing in to tell Henry Pollak, the director of the Mathematics Center at Bell Labs about this, and he said, "Well, that sounds good but you had better check with Ed Gilbert." Edgar was soon convinced, so I wrote to John Leech. He and I then found lots more packings, and wrote three papers, the big one in the Canadian Jnl. Math. ["Sphere packing and error-correcting codes," in Vol. 23 (1971), 718-745].
The path then led from John Leech to Donald Coxeter, and from Coxeter to John Conway.
Incidentally this was not the last time that the focusing effort needed to prepare a talk has led to new discoveries.
Q: And all this was eventually incorporated into the book with John Conway?
A: Yes - the papers with John Leech were expanded and rewritten as Chapter 5 of Sphere Packings, Lattices and Groups, also known as SPLAG. Someone said about this book that it is the bible of sphere packing, and, like the bible, contains no proofs. This is completely false, of course.
Q: You seem to like the "kissing number" problem?
A: It was always one of my favorites. How many spheres can you arrange so that they all touch another sphere of the same size? In two dimensions you can place 6 pennies os they touch a central penny, so there the answer is 6. In three dimensions you work with billiard balls - that's where the term kissing number comes from, by the way, a name that I think I invented, since two billiard balls that just touch are said to "kiss" - and the answer is 12. It is such a natural and beautiful problem.
One of my favorite theorems is the result that Andrew Odlyzko and I proved, that in 8 and 24 dimensions the optimal kissing numbers are respectively 240 (from the E8 lattice) and 196560 (from the Leech lattice). (Vladimir Levenshtein independently proved the same result.) You can see the proof in Chapter 13 of SPLAG.
The amazing thing is that we now know the maximal kissing number in dimensions 1, 2, 3, 8 and 24, but not in any other dimensions.
Q: Even less is known about the densest packing problem?
A: Right - we know the densest sphere packings in all dimensions up to 2! There has been a lot of controversy over the three-dimensional problem, which is sometimes called the Kepler conjecture. It seems very likely that there is no packing that is denser than the face-centered cubic lattice, but the question is still open.
However, Tom Hales, at the University of Michigan, has been making great progress towards bringing the problem within reach of a finite computer calculation, so there is hope that it will be finally settled before too long [see T. C. Hales, "Sphere packings I," Discrete Comput. Geom. 17 (1997), 1-51].
Q: "SPLAG" isn't your only book?
A:
No, there have been several other books.
The
Theory of Error-Correcting Codes with Jessie MacWilliams, of course.
The two most recent are
The Encyclopedia of Integer Sequences
(with Simon Plouffe), and the
Rock-Climbing Guide to New Jersey Crags
(with Paul Nick).
Most people don't realize that New Jersey has a large number of potential climbing areas - I know of at least 50, although it is sad to report that very few of them are presently open to climbing. One of the best areas is just down the road from the Murray Hill labs, on Diamond Hill Road, in the Watchung Reservation. Vic Benes took me climbing there for the first time in the early 1970's, and he and other people from Bell Labs had been climbing there for many years.
Sadly, the Union County Recreation Department closed the area to climbing some years ago. I actually got a ticket for climbing there, and had to go to court.
A group of us (the "Watchung Area Recreational Climbers Organization") together with the Access Fund, have been trying for years to get the area reopened, but without success. If any readers of this interview have any influence with the Union County Board of Freeholders, we need your help! This is the best climbing area in central New Jersey, and, as I said, there is a long tradition of Bell Labs people climbing there.
Q: I see you feel strongly about it. What's your next project?
A: I had this truly great idea a couple of years ago that I would like to get some organization interested in.
This is an Internet service that someone like AT&T, the IEEE, the Amer. Math. Soc., the Amer. Medical Assoc., or even The Vatican could offer: a home page "in perpetuity".
Such a "perpetual page" or "eternity page" or "e-memorial page" would be a home page that the organization would help you set up, with a guarantee that it would last for (say) 500 years, or until the organization no longer exists. It would list all the things that you would like to be remembered for (accomplishments, family, writings, etc.). As the population of the U.S. ages, such a service should be very popular. After all, almost everyone wants to be remembered by posterity.
I wrote a memo [Proposal for an Internet Service: the Eternal Home Page, Dec. 13, 1996.] about this in 1996, and an html version is now on my (unfortunately not yet eternal) home page. Of course it turns out that other people have had similar ideas, and there may be some commercial versions that provide electronic gravestones available even now.
But in my version the service would be offered by a major organization or institute, something that has a chance of surviving for 500 years. And I'm not think of tombstones, but home pages. The organization would help you set up your home page, and would guarantee as far as possible to maintain it for 500 years. If this was marketed in the right way, by a sufficiently major organization, it seems to me that it would be immensely popular.
Q: What's your next technical project?
A: Impossible to predict! After all, the quantum error-correcting codes work came out of nowhere.
If Peter Shor hadn't run into the same eight-dimensional rotation group in quantum computing that John Conway, Ron Hardin and I had just seen in our work on packing planes in 8-space, and that you and Bill Kantor had studied in orthogonal geometry, the paper that you, Peter Shor, Eric Rains and I collaborated on would never have been written. Its existence depended on that double coincidence.
Concerning things that I can predict, well, Ron Hardin and I have a lot of material on optimal experimental designs, obtained with our program "Gosset," that we need to understand and generalize.
That's a thread that has linked several recent projects: we (usually Hardin and me) run the computer to find good packings, or coverings, or designs, we stare hard at the results, we learn, and we generalize. Take a look, for example, at our paper on McLaren's improved snub cube and other new spherical designs in three dimensions, (Discrete Comput. Geom., 15 (1996), 429-441), where we improve on Archimedes' version of the snub cube.
Q: We've talked a lot about Bell Labs, but we don't work there any more, do we. How do you feel about the new lab in Florham Park?
A: Naturally I was upset by the breakup of AT\&T Bell Labs, which still seems to me to have been a crime against humanity. I am surprised there hasn't been more of a public outcry. I'm not going to compare it to the destruction of the Amazon rain forest, which seems to be coming along very well, by the way, though I'm tempted to.
It was also a shock to be evicted from Murray Hill after 28 years, and to be separated from dozens of friends and colleagues. In the new AT\&T Research Labs building at Florham Park there are only 350 people, quite different from the 5000 we had at Murray Hill. On the other hand, these are 350 very good people, and I think you are doing a fantastic job as head of the Information Sciences Center (carrying on in Henry Pollak's footsteps), so I am optimistic.
See also: Neil Sloane's home page