Rakesh Vohra of the Game Theory Society reports that not only was John Nash returning from the airport after returning from Norway to receive the Abel Prize in mathematics, its equivalent of the Nobel (the Fields medal is the equivalent of the John Bates Clark award, given for those under 40), which he got for his embedding theorem, which he always viewed as more important than his Nobel prize winning game theory equilibrium, which he considered to be mathematically trivial, despite its wide applicability in economics and other disciplines, but it has only recently been revealed that he had a third major intellectual breakthrough that has only become public since 2012 when the National Security Agency declassified a letter Nash initially wrote in 1950 to its predecessor, the NSA not becoming officially organized until 1952.
In this letter Nash proposed a form of possible encryption used decades later by the NSA based on computational complexity theory, particularly the distinction between P, or polynomial length programs, and NP, or non-deteriministic polynomial (exponential and greater) length programs, relative to the key. While declaring this to be a true distinction, he foresaw the later problem that it might be impossible to prove, and so far it has not been, becoming the greatest unsolved problem of computational complexity theory. Nevertheless Nash used this as the key to hardening encryption code systems, with his thoughts on this far ahead of any of the thinking at that time, although it took those he wrote to a long time to realize it and follow up on his advice.
This makes me understand a bit more a famous incident in 1958 reported in Sylvia Nasar's book, A Beautiful Mind, although it did not turn up in the movie version. A. Adrian Albert, chair of the math department at the University of Chicago, then one of the top in the world, offered Nash a position, with him then in the MIT department. He turned down the offer on the grounds that he was expecting to shortly be appointed "Emperor of Antactica." In fact, this was one of the first signs of his developing mental illness, although at the time Albert dismissed this as mere eccentricity, which many brilliant mathematicians exhibit.
What makes this new report from Vohra interesing in light of this is that this secret letter may have been the key to Albert's invitation. The reason for this was a little known fact even now, that during World War II Adrian Albert was almost certainly the top cryptanalyst in the US, with some of his work remaining classified for decades as well. Under the circumstances, it is highly likely that Albert was one of the few people who was privy to Nash's letter at the time and understood its significance. I have no confirmation of this, but the facts about Albert are fairly clear if one googles him properly, with his role in these matters in the US publicly, but not widely, known (I provide a link to his Wiki entry, which is both sparse and contains at least one mistake). He remains a relatively obscure mathematician, but one , whose importance far outweighs his reputation.
Update: So, there is more about the Albert-Nash link that I have been thinking about, with a further speculation completely unprovable regarding why it was this year that Nash (with Nirenberg) got the Abel Prize. First let me note that Abel's work is closely linked to that of Albert, with Abelian groups being a central focus of Albert's study and linked to the algebraic forms he used in his cryptanalytic (or cryptographic) work. I also suspect that while officially Nash received the prize for his embedding theorem, the revelation of his letter on computational complexity to the NSA (sent in 1955, closer to the year Albert made his job offer to Nash, with that even more evidence that the secret letter was crucial to that rejected job offer), The revelation of this letter may well have provided a tipping point for finally giving the award to Nash, although he had almost certainly been on the list for a long time for the embedding theorem, as he himself considered it his most important work, at least in his public comments, having kept quiet about this letter until its public revelation.
The further wiggle on this is the appearance and success during the past year of the movie about fellow cryptanalyst, Alan Turing, The Imitation Game. Again, I do not know, but my speculation is that this could not have hurt. Both Nash and Turing were the prime subjects of popular movies that depicted both their sufferings and their classified work, although in the movie about Nash it did not show his most serious classified work, but rather depicted it as the central part of his fantasy, and his fantasies did involve matters of international peace and war, with himself both the victim of red-tie wearing communist agents as well as thinking he was an international messianic figure who would achieve world peace between the superpowers. Indeed, the matter of his thinking he would become the Emperor of Antarctica, the ostensible reason he rejected Adrian Albert's job offer, was tied to such fantasies, 1958 being the Internatinal Geophysical Year of Antarctica, when the US and the USSR and 10 other nations signed a treaty to mutually manage Antarctica.
This matter of the letter was not in Sylvia Nasar's book, but he did work for RAND, although probably not on this openly, with most of his more known work there being on game theory, with him becoming upset there by the Dresher-Flood experiments on the repeated prisoner's dilemma showing agents not using the Nash equilibrium but cooperating a lot in the experiments, including even the very rationalistic, Armen Alchian. This upset him so much that it would lead him to abandon game theory work, leaving the naming of the prisoner's dilemma game to his major professor, the late Albert W. Tucker. But, in the end , the more fantastical version in the movie may have been closer to reality, with his close link to the also suffering and highly secret Alan Turing possibly a key to his eventual receipt of this prestigious award, clearly the culmination of his life. It was indeed "going out at the top" that happened in this particular case of a husband-wife death, for better or worse (with their schizophrenic son, Johnny, the clear victim of this situation)..
Further update: The error that I am aware of in Adrian Albert's Wiki entry is the claim that in 1961-62, he was the first director of the Communications Research Division of the Institute for Defense Analysis, located in John von Neumann Hall on the Princeton campus, an NSA front research group. He was the second such director, not the first. (One can find a discussion of Princeton's IDA/CRD unit, no longer on the campus, in James Bamford's seminal book on the NSA, The Puzzle Palace.)
Barkley Rosser
Further Update, 5/38/16: I thank Dan Weber and "Jake," commenters on Marginal Revolution for noting errors in my original post, with Dan catching the especially elementary (and egregious) one that polynomial length programs are "P," not "N," duh. I have corrected the text to fix the points raised (Jake's were more esoteric but valid about the nature of NP).
Why would he have been so impressed, when the NSA was deeply unimpressed by Nash's suggested system and it was easily broken?
ReplyDeleteClearly NSA was impressed enough to classify the letter until 2012, and my description is clearly a simplification. That it is now declassified indicates that what is in it is now old hat and no longer cutting edge (try elliptical curve encryption, at least according to Scott Aaronson and some other commentators). After all, what they are using and have used when and how remains very classified (and I do not have personal access to that).
ReplyDeleteA crucial point is that A. Adrian Albert almost certainly was one of the handful of people who was asked to figure out Nash's letter and its usefulness. That he made that offer to Nash a few years after it arrived suggests he thought it was pretty impressive.
> Clearly NSA was impressed enough to classify the letter until 2012
ReplyDeleteIt's not the least bit clear. Classification guidelines have next to nothing to do with whether something is important or not. The most trivial things get classified and there are millions upon millions of documents locked up where classification was absurd in the first place. Ask some of the groups which work a lot with classified works about how sensible classification is as a process... They released it because it was completely harmless and of minor historical interest about a well-known Nobelist. (Compare the voluntary release of the Nash letters with the prolonged and mostly futile attempts by outsiders to get documents about thins that were actually important, like the NSA and GCHQ's inventions of public key cryptography. Or ask groups like the FAS Project on Government Secrecy whether classification implies importance...)
> That it is now declassified indicates that what is in it is now old hat and no longer cutting edge
As far as I can tell, Nash's system was always broken (cryptographers like Schneier like to say that anyone can invent a crypto system they themselves cannot break), was never cutting-edge, and the main historical interest is to what extent, with the benefit of hindsight, that Nash's comments prefigured Godel's P=NP comments.
> That he made that offer to Nash a few years after it arrived suggests he thought it was pretty impressive.
Albert is not mentioned at all in the letters. So he *may* have seen Nash's system and *may* have disagreed with the NSA's evaluation of it as insecure & offering only "limited security" (this is in addition to the NSA's evaluation of earlier 1950 material as "not suitable") and *may* have taken that into account later. Or, more parsimoniously, he never saw it, and any later interactions - such as being a chair of a math department who was not working for the NSA anymore but was looking to hire a math professor - with Nash were based on his landmark work in math areas other than crypto.
It is now recognized that Nash prefigured Goedel on posing the P != NP problem, although neither put it quite as those who posed it in the 1970s, notably Cook, Levin, and Karp, none of whom knew of the work of either Nash or Goedel on this, Goedel's letter to von Neumann in 1956 not publicly revealed until 1988, and Nash's in 2012. They came at it from somewhat different directions, Goedel more from
ReplyDeletemathematical logic and Turing, while Nash was in fact more concerned with the problem of encryption and drew directly on Shannon's 1949 work on information. A nice account of how they relate and how all this went down more generally is a recent paper by David S. Johnson, "A brief history of NP-completeness, 1954-2012," available at davidjohnson.net/papers/ismp12.pdf .
Actually, Nash wrote several letters to the NSA in 1955, all of them rather messily handwritten. The only reply from NSA at the time in the released records somewhat dismissed his suggestions, saying other approaches were more useful. It is unclear exactly how and when his ideas came to be viewed as more important is unclear.
Now, it is certainly not certain that Abraham Adrian Albert, known privately as "A Cubed" was involved in initially reading the letter(s) or writing that reply, but the probability that he saw it/them pretty early on, prior to 1958 when he made the offer to Nash is incredibly high. His work for the NSA and its predecessor agency is reported in the biography of him by his daughter, Nancy Albert, "A Cubed and his Algebra," published in 2005, along with reports in Bamford's books, in more detail in James Bamford's Body of Secrets. If one googles properly, one can even find a letter sent to Albert from I.T. MacDonald, then assistant to William Friedman, NSA's longtime early director, about a trip he was making to Cheltenham, the location of the HQ of GCHQ. Bamford reports on his heading the IDA's center at Princeton, 1961-62, which in 1865 produced a crptographic device considered to be a major breakthrough. Did this device rely at all upon Nash's ideas? There is no way of knowing.
That Albert was involved with cryptanalysis was in fact a public matter based on certain publications of his in the early 1940s, but his important work in WW II remains much less reported on. In any case, he had not just gone to Chicago in 1958 from NSA but continued to work for both. His education was at Chicago, and he had been a member of its math department since 1931, and also made visits to the Institute for Advanced Study in Princeton, where von Neumann was based. It was apparently Albert who met Einstein and his wife when they arrived at Princeton in 1933 when Einstein came to join the IAS.
His biography and also Bamford report that he founded several bodies closely associated with the NSA, not only the institute for Defense Analysis (IDA) of which the Princeton facility he directed in the early 60s was a part, but Project SCAMP in the early 1950s, which was based at UCLA and the RAND Corporation and continues to this day. The hard fact is that Albert was NSA at the highest levels from WW II on well into the 1960s (he died in 1972). There are very few people besides him who would have seen the Nash letter(s), indeed, given that he clearly played a major role in developing the 1965 cryptographic machine of the NSA, and if Nash's ideas had any relevance to that, it may well have been Albert himself who ordered the classifying of Nash's letters.
BTW, some note that there was serious consideration of the problem of how long it takes to solve a computer program prior to these letters by Goedel and Nash in the mid-1950s. Von Neumann himself was doing so in the late 1940s when he was building his first computer, and he was the person to whom Goedel addressed his 1956 letter, at which time von Neumann was dying of cancer.
ReplyDeleteIn the 1930s, Goedel had also considered the problem, especially after he became aware of Turing's work. There is reason to believe that von Neumann, who also knew Turing, was inspired by his work in both building his computer and in these considerations.
Finally, before any of them was Emil Post in the 1920s, who tried too hard to do too much, and while he made great accomplishments remains one of the most underappreciated figures in mathematical logic and theoretical computer science. In any case, he studied this issue in the 20s, but as part of a much larger project that was close to the independence theorems that Goedel would prove not too long thereafter.
> It is unclear exactly how and when his ideas came to be viewed as more important is unclear.
ReplyDeleteI think that's pretty clear: when he became a major pop culture and mathematical figure and someone noted that the old Nash files contained some letters. (Note, for example, that the NSA author merely refers to his work on noncooperative games as "interesting" - the full importance has yet to dawn.)
> Now, it is certainly not certain that Abraham Adrian Albert, known privately as "A Cubed" was involved in initially reading the letter(s) or writing that reply, but the probability that he saw it/them pretty early on, prior to 1958 when he made the offer to Nash is incredibly high
Why is it "incredibly high"? The annotations to the letters document the people who the letters were forwarded to or were involved. *None* is Albert or his institution. Is this not strong evidence against Albert having been involved, the complete silence about him? "Not certain"? Try: 'there is not the slightest scrap of evidence that a particular former NSA mathematician was given copies of NSA correspondence'. You seem very confident in your connections given the absence of all possible evidence. Please try to remember that the NSA was ultra-paranoid about secrecy and took it very seriously and classified everything possible it could about the thousands of employees which comprised the "No Such Agency" that lived in Puzzle Palace.
> Bamford reports on his heading the IDA's center at Princeton, 1961-62, which in 1965 produced a crptographic device considered to be a major breakthrough. Did this device rely at all upon Nash's ideas? There is no way of knowing.
Are you seriously suggesting that a broken cryptosystem dismissed immediately as useless had anything to do with a major breakthrough?
> it may well have been Albert himself who ordered the classifying of Nash's letters.
Wild speculation piled upon speculation piled upon speculation. There is nothing at all you can point to which says that Albert was involved in any way.
> There are very few people besides him who would have seen the Nash letter(s),
You mean, few people besides all the people and groups named in the letters and annotations, none of whom are named Albert, cubed or not.
(Talk about privileging the hypothesis!)
I throw in one other ironic observation here. Apparently Nancy Albert was inspired to write her bio of her dad by the success of Sylvia Nasar's book on John Nash, especially given that her dad appears in that book in the way already noted, for his invitation to Nash in 1958 to go to Chicago (that was the year Albert became dept chair, which he was 58-61, when he went to Princeton for a year, then becoming dean at Chicago upon his return in 62). It is somewhat ironic how closely entangled these figures were, Nash, Alberf, von Neumann, Turing, and Goedel.
ReplyDeleteUnfortunately for Ms. Albert, there was no dramatic angle about her dad, who did not suffer particularly. Indeed, in his day he was a public figure who advocated for government support for mathematics research (including that done secretly, although that was not advertised at the time). He was highly respectable, with probably the only real drama being his involvement with all that classified stuff and these other figures. But somehow the book never made much of a splash, and Albert is an increasingly unknown figure even inside the world of mathermatics, except in algebra, where "Albert algebras" continue to be studied.
Here is another link for the Johnson paper on the brief history of NP-completeness. Hope it works better than the other one. In any case, you can find it by googling for it, and it is very good.
ReplyDeletewww.math.uiuc.edu/documenta/vol-ismp/50_johnson-david.pdf .
Gwern makes many valid points, and there is no way to ressolve this given the nature of much of the information involved here. I shall make only a few further points.
ReplyDelete1) Albert was not a full time empployee of the NSA and never was or of its predecessor agency, although through consulting and related research and advisory bodies he was probaably the most important mathematician working on their deepest mathematical problems for them. Anyway, that his name is not on the distribution list is easily explained by his not being an actual agency employee.
2) While much of the discusson in the letters involved a machine that Nash claimed he had sent to NSA at some point that apparently never arrived (or maybe never existed), somebody at some point marked in red on the letters the particular sections making the serious mathematical arguments (you can see copies of the actual letters if you dig through the Vohra links in the post). Maybe these were put on much later, but it is also possible that they were noted at the time, with the thought that the top mathematical researchers of NSA should look at it, and Albert was as top as they came, with him hanging out in LA in Summer 1955 at the first SCAMP, which he organized and led.
3) In any case, Gwern is right that at some level all this is "wild speculation," but the pieces are certainly in place for the story I tell. It was known that Albert liked to hire colleagues and have students whose research had national security applications, especially in cryptology. Maybe Albert did not know that aspect of Nash's skill set, or maybe he was aware only of the game theory part of it, but given many things, if he did know, he certainly would have been most interested, and the chances are good that he did know, although not at all certain.
BTW, let me make a terminological distinction. Properly speaking "cryptography" is making codes, "cryptanalysis" is breaking codes, whereas "cryptology" is the study of both, although some would say the latter is a particular form of less mathematical cryptanalysis. In that regard, the title of the post here might have more accurately been "John Nash as Cryptologist."