Serious work amid the puzzles and jokes.

 Amazon source

When Raymond Smullyan was born, Emanuel Lasker was still the world chess champion. Indeed, of the 16 universally recognized champions, only the first, Wilhelm Steinitz, lived outside Smullyan’s lifetime. Smullyan passed away a week ago Monday at age 97.

Today, Dick and I wish to add some thoughts to the many comments and tributes about Smullyan.

He was known for many things, but his best-known contributions were books with titles like: “What Is the Name of This Book?” Besides their obit in Sunday’s paper, the New York Times ran a sample of puzzles from these books. No doubt many enjoyed the books, and many may have been moved to study “real” logic and mathematics. His book To Mock a Mockingbird dressed up a serious introduction to combinatory logic. This logic is as powerful as normal predicate calculus but has no quantified variables. So making it readable to non-experts is a tribute to Smullyan’s ability to express deep ideas in ways that were so clear.

Smullyan earned his PhD under the guidance of Alonzo Church in 1959 at age 40. When I (Ken) was an undergrad at Princeton, I remember thinking, “gee, that’s old.” Well there’s old and there’s old… As we noted in our profile of him 19 months ago, he was still writing books at a splendid pace at age 95, including a textbook on logic.

Neither of us met him, so we never experienced his tricks and riddles firsthand, but we had impressions on the serious side. Here are some of Dick’s, first.

A Great Book

Smullyan and Melvin Fitting, who was one of his nine PhD students, wrote a wonderful book on set theory: Set Theory and the Continuum Problem (Oxford Logic Guides), 1996.

The blurb at Amazon says:

Set Theory and the Continuum Problem is a novel introduction to set theory … Part I introduces set theory, including basic axioms, development of the natural number system, Zorn’s Lemma and other maximal principles. Part II proves the consistency of the continuum hypothesis and the axiom of choice, with material on collapsing mappings, model-theoretic results, and constructible sets. Part III presents a version of Cohen’s proofs of the independence of the continuum hypothesis and the axiom of choice. It also presents, for the first time in a textbook, the double induction and superinduction principles, and Cowen’s theorem.

The blurb at Amazon says:

A lucid, elegant, and complete survey of set theory [in] three parts… Part One’s focus on axiomatic set theory features nine chapters that examine problems related to size comparisons between infinite sets, basics of class theory, and natural numbers. Additional topics include author Raymond Smullyan’s double induction principle, super induction, ordinal numbers, order isomorphism and transfinite recursion, and the axiom of foundation and cardinals. The six chapters of Part Two address Mostowski-Shepherdson mappings, reflection principles, constructible sets and constructibility, and the continuum hypothesis. The text concludes with a seven-chapter exploration of forcing and independence results.

Wait—are these the same book? Yes they are, and this is one way of saying the book is chock full of content while being self-contained. Neither blurb mentions the part that most grabbed me (Dick). This is their use of modal logic to explain forcing.

Modal logic has extra operators ${\Box\phi}$ which is usually interpreted as “Necessarily ${\phi}$” and ${\diamond\phi}$ meaning “Possibly ${\phi}$“; like the quantifiers ${\forall}$ and ${\exists}$ they obey the relation

$\displaystyle \Box \phi \longleftrightarrow \neg\diamond\neg\phi.$

Saul Kripke codified models as directed graphs whose nodes each have an interpretation of ${\phi}$. Then ${\Box\phi}$ holds at a node ${u}$ if all nodes reachable from ${u}$ satisfy ${\phi}$ (and hence ${\Box\phi}$), while ${\diamond\phi}$ holds at ${u}$ if ${\phi}$ holds at some node reachable from ${u}$. The nodes are “possible worlds.”

What Fitting and Smullyan do is define a translation ${\phi \rightarrow \phi'}$ from set theory to their modal logic such that ${\phi}$ is valid if and only if ${\Box\phi'}$. Then the game is to build a node ${u}$ such that every Zermelo-Fraenkel axiom gets a ${\Box}$ but the translated continuum hypothesis fails in some world reachable from ${u}$.

One reprinting of the book posed an inadvertent puzzle: many mathematical symbols were omitted. Symbols for set membership, subset, quantifiers, and so on were missing. As one online reviewer noted, “it really does make the book useless.” My copy at least was unaffected.

Rudimentary, My Dear

A week after our 7/28/15 Smullyan post mentioned above, I (Ken again) went with my family to Oregon for vacation. This included a trip to Powell’s Books in Portland, which may be the largest independent bookstore in the world. The math and science sections were larger and more eclectic than any Barnes or college bookstores I’ve seen. There were several copies of the 1961 Princeton Annals paperback edition of Smullyan’s PhD thesis, Theory of Formal Systems, on sale for \$20. I felt spurred to buy one and felt it could be useful because of Smullyan’s penchant for combinatorial concreteness.

Sure enough, section B of Chapter IV formulates the rudimentary relations crisply and clearly. Here are Smullyan’s words atop page 78 on their motivation:

As remarked in the Preface, our proof follows novel lines in that all appeal to the traditional number theory devices … in the past—e.g., prime factorization, congruences and the Chinese remainder theorem—are avoided. Thus Gödel’s program of establishing incompleteness, even of first-order theories involving plus and times as their some arithmetical primitives, can, by the methods of this section, be carried out without appeal to number theory.

Simply said: Smullyan avoids all the complicated numerical machinery needed in the usual treatments and makes them—like magic—disappear. The main predicate needed by Smullyan is ${R(p,x) =}$ ${x}$ is a power of ${p}$, provided ${p}$ is prime. From that he defined a predicate ${C(x,y,z)}$ meaning that the binary representation of ${z}$ is the concatenation of those of ${x}$ and ${y}$. The formal language is still that of logic and numbers but the operations are really manipulating strings. His predicates were able to fulfill all roles for which the class of primitive recursive relations and subclasses involving ${+}$ and ${\times}$ had previously been employed.

Smullyan was writing in 1959. Turing machine complexity had not even been defined yet. It transpired later that Smullyan’s class ${\mathsf{RUD}}$ contains nondeterministic logspace and equals the alternating linear time hierarchy. Linear time by itself is annoyingly dependent on machine details, but once you have a couple levels of quantifier alternation the class becomes very robust. Dick employed tricks with alternating linear time in some papers, and such alternation is used to amplify the time hierarchy theorem so that ${\mathsf{NLIN = DLIN}}$ for multitape Turing machines leads to a contradiction higher up. It is also intriguing to see Smullyan write on page 81:

We do not know whether or not all constructive arithmetic attributes are rudimentary. Quine […] has shown that plus and times are first order definable from [concatenation] … but this leaves unanswered the question as to whether plus and times are themselves rudimentary.

The thesis has a footnote saying this had been done for plus, and times follows from remarks above, but whether the predicate ${x*y = z}$ is in deterministic linear time remains open. It is likely that Smullyan went through similar concrete thinking as Juris Hartmanis and Richard Stearns when they conjectured no. We wonder if anyone thought to ask Smullyan about this and wish we had.

Open Problems

Our condolences go to his family along with our appreciation for his writings.

Emanuel Lasker philosophized in his 1906 book Struggle about perfect strategists in any walk of life, calling them Macheeides after Greek for “battle species.” An improved edition of Google DeepMind’s AlphaGo probably joined their ranks by beating top human players 60-0 in games played via online servers, not counting one game disrupted by connection failure. The top ranked player, Ke Jie, lost 3 games and landed in the hospital, but desires a 4th try. Where will computer Macheeides strike next?

A discussion on the famous problem

William Agnew is the chairperson of the Georgia Tech Theoretical Computer Science Club. He is, of course, an undergraduate at Tech with a multitude of interests—all related to computer science.

Today I want to report on a panel that we had the other night on the famous P vs. NP question.

What to do about claims of hard theorems?

 Cropped from source

Shinichi Mochizuki has claimed the famous ABC conjecture since 2012. It is still unclear whether or not the claimed proof is correct. We covered it then and have mentioned it a few times since, but have not delved in to check it. Anyway its probably way above our ability to understand in some finite time.

Today I want to talk about how to check proofs like that of the ABC conjecture.

The issue is simple:

Someone writes up a paper that “proves” that X is true, where X is some hard open problem. How do we check that X is proved?

The proof in question is almost always long and complex. So the checking is not a simple matter. In some cases the proof might even use nonstandard methods and make it even harder to understand. That is exactly the case with Mochizuki’s proof—see here for some comments.

Possible Approaches

Let’s further assume that the claimed proof resolves X which is the P vs. NP problem. What should we do? There are some possible answers:

• Ignore: I have many colleagues who will not even open the paper to glance at it. Ken and I get a fair number of these, but I do at least open the file and take a quick look. I will send a message to the author—it usually is a single author—about some issue if I see one right away.

• Show Me The Beef: I firmly believe that a proof of an open problem should have at least one simple to state new trick or insight that we all missed. I would suggest that the author must be able to articulate this new idea: if they cannot then we can safely refuse to read it. I have worked some on the famous Jacobian Problem. At one time an author claimed they had a proof and it was just “a careful induction.” No. I never looked at it because of the lack of “beef,” and in a few weeks the proof fell apart.

• Money: Several people have suggested—perhaps not seriously—that any one claiming a proof must be ready to post a “bond” of some money. If someone finds an error they get the bond money. If no one does or even better if the proof is correct, then the money can be donated to one of our conferences.

• Hire: I have seen this idea just recently. The author posts a request for someone to work on their paper as a type of consultant. They are paid a fair hourly rate and help find the error.

• Timeout: An author who posts a false proof gets a timeout. They are not allowed to post another paper or submit a paper on X for some fixed time period. Some of the top journals like the Journal of the ACM already have a long timeout in place. The rationale behind this is that very often when an error is found in such a paper the author quickly “fixes” the issue and re-claims the result. In Stanislaw Ulam’s wonderful book Adventures of a Mathematician he talks about false proofs: Here “he” refers to an amateur who often joined Ulam at his habitual coffeehouse:

Every once in a while he would get up and join our table to gossip or kibitz ${\dots}$ Then he would add, “The bigger my proof, the smaller the hole. The longer and larger the proof, the smaller the hole.”

• Knock Heads Together: Oxford University hosted in December 2015 a workshop to examine Mochizuki’s claimed proof, including contact by Skype with Mochizuki himself. A report by Brian Conrad on the MathBabe blog makes for engaging reading—we could quote extensively from its concluding section 6. This shorter news report cited feelings of greater understanding and promise but lack of definite progress on verifying the proof, noting:

…[N]o one wants to be the guy that spent years working to understand a proof, only to find that it was not really a proof after all.

• Share The Credit: Building on the last point, perhaps proper credit can be given to someone who does spent a great deal of time working on trying to understand a long proof. If they find an unfixable error, then maybe they can publish that as a paper—especially if the error is nontrivial and not just a simple one. If they show that the proof is indeed correct, could they be rewarded with some type of co-authorship? Maybe a new type of authorship:

P Does Not Equal NP: A Proof Via Non-Linear Fourier Methods
Alice Azure with Bob Blue

Here the “with” signals that Alice is the main author and Bob was simply a helper. Recall a maxim sometimes credited to President Harry Truman: “It is amazing what you can accomplish if you do not care who gets the credit.”

Open Problems

What do you think about ways to check proofs? Any better ideas?

Impetus to study a new reducibility relation

 See Mike’s other projects too

Michael Wehar has just earned his PhD degree in near-record time in my department. He has posted the final version of his dissertation titled On the Complexity of Intersection Non-Emptiness Problems which he defended last month. The dissertation expands on his paper at ICALP 2014, joint paper at ICALP 2015 with Joseph Swernofsky, and joint paper at FoSSaCS 2016.

Today, Dick and I congratulate Mike on his accomplishment and wish him all the best in his upcoming plans, which center on his new job with CapSen Robotics near Pitt and CMU in Pittsburgh.

The 25th Anniversary of the ACO Program

 Cropped from src1 & src2 in gardens for karma

Prasad Tetali and Robin Thomas are mathematicians at Georgia Tech who are organizing the Conference Celebrating the 25th Anniversary of the ACO Program. ACO stands for our multidisciplinary program in Algorithms, Combinatorics and Optimization. The conference is planned to be held starting this Monday, January 9–11, 2017.

Today I say “planned” because there is some chance that Mother Nature could mess up our plans.

Even after today’s retraction of quasi-polynomial time for graph isomorphism

 Cropped from source

László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasi-polynomial time.

Today Laci posted a retraction of this claim, conceding that the proof has a flaw in the timing analysis, and Ken and I want to make a comment on what is up. Update 1/10: He has posted a 1/9 update reinstating the claim of quasi-polynomial time with a revised algorithm. As we’ve noted, he is currently speaking at Georgia Tech, and we hope to have more information soon.