Martin Kruskal was born Sept 28, 1925 and passed away on Dec 26, 2006, at the age of 81. Today, Sept 28, 2025, is his 100th birthday. His son Clyde Kruskal wrote today's blog post as a tribute to his father.
We note that Clyde did a blog for his Uncle Bill's 100th Birthday, here, and plans on doing one for his Uncle Joe in two years.
-----------------------------------------------------------------------------------------
My father, Martin Kruskal, was a mathematician and physicist, best known for his early work in plasma physics, the discovery (independently of George Szerekes) of Kruskal-Szerekes coordinates, the modern discovery with Norman Zabusky of solitons, and the discovery with Clifford Gardner, John Greene, and Robert Miura of the inverse scattering transform. He had an incredible willingness to tackle interesting, seemingly small problems\(-\)some of which later turned out to be highly influential. Here, in chronological order, is a list of some of his more esoteric and/or less well-known contributions, not necessarily research contributions (besides me).
1. Random Mappings
Renowned mathematicians Nicholas Metropolis and Stanislaw Ulam (inventors of the Monte Carlo method) posed the problem of determining the expected number of components in a random mapping from \(N\) to \(N\). Framing this as a random graph problem: Construct a graph on \(N\) vertices by choosing, for each vertex \(i\) (from 1 to \(N\)), a random vertex \(j\) (also from \(1\) and \(N\)), and create the undirected edge \((i,j)\). If \(i=j\), no edge is created (or equivalently, a self-loop is created). The question is: What is the expected number of connected components in such a graph? In 1954, in his first paper after graduate school, he showed that this value is asymptotically \((1/2)(\ln(2N) + C) + o(1)\), where \(C=0.5772\ldots\) is Euler's constant. For the paper see here.
2. Computer Chess
My father was a strong chess player and, in 1956, arguably became the first person to play a game of chess against a computer. When I learned about this in junior high school, I figured that this must be his most significant achievement. Because the MANIAC 1 computer was slow and had little memory, the game was played on a 6×6 chessboard without bishops and simplified rules. My father gave the computer queen odds. Spoiler alert: He won. For more details, including the full game, see this explanation on Wikipedia here.
3. The Card Game Delphi
In 1956, Bob Abbott invented Eleusis, a card game involving inductive inference. While the game itself was highly original, the scoring system was somewhat arbitrary. In 1962, my father devised the game Delphi, which, according to Martin Gardner, made several important improvements, including a much more logical scoring system. While it solved the scoring problem, Delphi turned out to be less fun to play than Eleusis. Later, Bob Abbott created an improved version of Eleusis called New Eleusis, which, unfortunately, still did not completely solve the scoring problem.
For the rules to Delphi, see this article in Denexa Games here.
4. The Kruskal Count
My father invented a card trick, called the Kruskal Count, with the unique characteristic that the magician never touches the deck of cards during the performance. To make this plausible, he would claim to the audience that he was psychic. There are various YouTube videos demonstrating and discussing it. Shortly after devising the trick, my father, brother, and I visited a young married couple. My father performed the trick several times on the husband, who kept accusing his wife of secretly colluding with him. She was insulted and kept denying it\(-\)truthfully. Finally my father said to the wife, Well, the cat’s out of the bag. You have been in on it all along, and you can admit it now. (She hadn’t.) My brother and I (both teenagers) thought it was hilarious; I doubt the couple did.
The trick turned out to have serious applications: According to Wikipedia, the underlying phenomenon has applications in cryptography, code-breaking, software tamper protection, code self-synchronization, control-flow resynchronization, design of variable-length codes and variable-length instruction sets, web navigation, object alignment, and others. There are various YouTube videos demonstrating and discussing it.
The Kruskal Count was featured in an episode of NUMB3RS, which Gasarch blogged about here.
5. Surreal Numbers
My father had a lifelong fascination with infinity starting in childhood, which deepened when he read Donald Knuth’s introductory book on surreal numbers. For more about his interaction with Knuth after reading the book, see this blog entry here. Wikipedia provides a concise explanation on my father’s webpage about surreal numbers and his contributions. The entry highlights important results\(-\)both positive and negative\(-\)by Ovidiu Costin, Philip Ehrlich, and the mathematical logician Harvey Friedman (see here and here for the papers).
Martin's website has the following passage, which captures the issue beautifully.
Surreal numbers, which are defined constructively, have all the basic properties and operations of the real numbers. They include the real numbers alongside many types of infinities and infinitesimals. Kruskal contributed to the foundation of the theory, to defining surreal functions, and to analyzing their structure. He discovered a remarkable link between surreal numbers, asymptotics, and exponential asymptotics. A major open question, raised by Conway, Kruskal, and Norton in the late 1970s, and investigated by Kruskal with great tenacity, is whether sufficiently well behaved surreal functions possess definite integrals. This question was answered negatively in the full generality, for which Conway et al. had hoped, by Costin, Friedman, and Ehrlich in 2015. However, the analysis of Costin et al. shows that definite integrals do exist for a sufficiently broad class of surreal functions for which Kruskal's vision of asymptotic analysis, broadly conceived, goes through. At the time of his death, Kruskal was in the process of writing a book on surreal analysis with O. Costin.
6. Alpha-Beta Search
While in graduate school, I came across Donald Knuth and Ronald Moore's paper on alpha-beta search (see here). They posed the question of what is the expected branching factor in a game tree with \(c\) children per node and depth \(d\), and uniformly distributed values at the leaves. They gave a partial solution. Gerard Baudet found a recurrence for this value and improved the bound (see here). This was the kind of asymptotics that my father excelled at, so I asked him if he could solve the recurrence. He solved it by finding an asymptotic value for the number of leaves evaluated. Right after that Judea Pearl published the asymptotic value for the branching factor (see here).
At the time I figured that the original question had been answered by Pearl, so the stronger result was not interesting. A more mature version of me might have pursued it. In reality, answering the original question is interesting, but for a number of reasons any further improvement is not particularly interesting, so I was probably right to drop it even if for the wrong reasons. Unfortunately it was in the file drawer lost during the move to our new building, but if anyone cares I think I remember the exact high order term.
7. Public Key Crypto
When he learned about public key cryptography, he invented his own system based on quadratic mapping just to understand how it works. He gave a talk on it in 1983. He showed it to Ron Rivest who said that it was not secure. Oh well.
No comments:
Post a Comment