A result of Specker in Recursive Combinatorics

Ernst Specker passed away in December. He has 91. He was not the oldest living mathematician. That title likely belongs to Sergey Nikolsky. A former student of Specker's, Martin Furer, posted about his life and his math on this blog here.

In this post I discuss a results of Specker that is not his most famous (that seems to be the Kochen-Specker theorem) but instead a result that I actually know. Hope you like it.

Background: Ramsey's theorem states that if COL is a 2-coloring of pairs of naturals then there exists an infinite homogenous set H (so every pair from H has the same color). The standard proof is non constructive.

More background: What if you were GIVEN a Turing Machine for a 2-coloring. Could you GIVE ME BACK a Turing machine for a homogenous set? The standard proof does not give this to you, so we are really asking if there is a more constructive proof. So, what is known?

Specker showed that there is a computable 2-coloring of pairs of naturals so that there is NO computable Homogenous set. Here is the proof in brief:

1. Let A be a bi-immune set (no subset of A or its complement is decidable) that is decidable with oracle HALT. You can easily construct such by an initial segment argument.
2. By the Shoenfield limit lemma there exists computable f(x,s) such that A(x) = limit_{s→ ∞} f(x,s). (Easy proof of the direction we need: if A is computable in HALT via oracle Turing machine M let f(x,s) be the result of running M for s steps and using as oracle the first s elements of HALT in some enumeration.)
3. Let COL(x,y) = f(x,y), for x< y. (NOTE- This is a correction, I earlier just had COL(x,y)=f(x,y).)
4. Assume, by way of contradiction, that there is an infinite homogenous set
   
   x₁ < x₂ < x₃ < x₄ < x₅ ...
   
   For all L we have f(x_L,x_L+1)= f(x_L,x_L+2) = f(x_L,x_L+3) = f(x_L,x_L+4) = ... (NOTE- I corrected this- I originally had x_1, x_2, x_3, x_4 where I now have x_{L+1}, x_{L+2}, ..)
   
   Since all of these values equal they also equal limit_{→ ∞}f(x_L,s) and hence equals A(x_L). Hence either ALL of the x's are IN A or all of the x's are NOT in A. Hence an infinite homogenous set yields an infinite subset of either A or the complement of A, which contradicts that A is bi-immune.

More has been proven since then:

1. Jockusch showed that (a) there is a 2-coloring of pairs so that no homogenous set is Sigma₂, and (b) every 2-coloring has a Pi₂ set.
2. More is known- see the paper by Cholak, Jockusch, Slaman On the strength of Ramsey's theorem for pairs

Specker's result is probability the first theorem in infinite combinatorics to be proven to be non-constructive.

Guest post on ITCS by Chazelle

(Requested announcement: Calling all Women PhD Students (and a few undergrads) We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012. Applications are due on: Feb 29, 2012. Go here for all the relevant information. Hoping to see you in June. From: Shubhangi Saraf, Lisa Zhang, Moses Charikar and Tal Rabin.)

(Guest Post by Bernard Chazelle) Why ITCS?

Thanks to Lance and Bill for their kind hospitality. I am delighted to be here. With the third edition of ITCS (formerly ICS) behind us, I thought it would be good to share a few personal, biased thoughts on the subject -- "personal" because I do not claim to speak for the Steering Committee; "biased" because I happen to chair that august body.

First, let me reach for my big bucket of gratitude. Shafi Goldwasser and Silvio Micali did an amazing job as PC & local chairs and I cannot thank them enough. A big shout-out to both. Toda Raba to Yael Kalai, too, for her great help, and to Omer Reingold, Nir Shavit, and their fellow actors for a fabulous "playback" show. If you missed it, fret not. If future organizing committees have any sense, the Nir-Omer show will soon come to a conference near you.

This year's ITCS had about 100 submissions, roughly a 20% growth from previous years, and 118 registrants. Talk attendance never seemed to dip below 90, a heart-warming figure that would be the envy of many conferences. In Shafi's and Silvio's deft hands, innovation came out swinging in all sorts of endearingly creative ways, from session chairs giving annotated previews of the talks to postdocs and graduating students making 5-min pitches to introduce themselves and their research. Brilliant! After watching the new generation of theorists in action, I can tell you that the future of theoretical computer science looks very bright, indeed!



And the future of ITCS, you'll ask, how bright is that? When I chaired the PC last year, a reviewer's comment struck a chord: "This submission would be good for STOC but might not be innovative enough for ICS." Now, that's the spirit! Of course, plenty of ITCS papers would fit in nicely at STOCS/FOCS. (Apparently, more than a few tried to fit in.) That said, it would take an advanced case of color blindness to miss the contrasting hues between ITCS and the rest. All PC members were instructed to add an innovation axis to their evaluation space, and, by golly, they did! (And when I use the word "golly," you know I mean business.)

STOC/FOCS has been accused of all sorts of dastardly deeds unmentionable on a family blog -- from accepting too few papers to boosting trends to rewarding technical wizardry. No less. STOC and FOCS might be four-letter words to some, but to me they're venerable legacy institutions that serve worthy professional functions, such as allowing junior researchers to trade these four-letter words for Theory Club membership cards. Nothing to sneer at. Over at Michael Mitzenmacher's corner, here, Umesh Vazirani bravely suggested merging STOC and FOCS into one mega-conference --- SFOCS, I guess. Much as I love the idea, beginning with the soothing effect of pronouncing the word SFOCS out loud, I didn't come here for a food fight, so I'll fall back on old New Jersey wisdom and say we cross that landfill when we come to it. Yet definitely something to mull over.

ITCS provides a venue for quality outside-the-box thinking. Not without reason, a few have wondered whether the best place outside the box is inside a new conference. On the plus side, conferences provide ideal platforms to publicize new work and, for younger scholars, increase the visibility of their research. With its particular focus on the uncharted, ITCS offers a welcome new outlet for a glut of quality papers. A conference is a big heads-up, a "breaking news" banner flashing on the Theory Channel. It's also a chance to initiate lasting collaborations and meet extraordinary people in pursuit of extraordinary ideas. It's fun.The downside is that a human being can attend only so many conferences before "their budget glares red and their head bursts in air" (as they say before kick-off at the Super Bowl).

This dichotomy, however, isn't quite right. It ignores the tangled web the online revolution has woven into our lives. Whereas in the past I'd have to go to a conference to hear a new result, this is no longer so. The PDF will come to me. It's a given that attendees at many talks will already know the results, perhaps even the proofs. This has diminished the relative importance of attending a conference while at the same time increasing its reach, and hence its influence. Don't get me wrong. I am not saying ITCS is so cool you don't even have to go. I am saying that, in the age of instant downloads, missing this month's Jay-Z & Kanye West "UGC" gig at the Garden ain't gonna be the heartbreak it would have been in the days of old. So, while I recognize that the burden of extra travel is a drawback and the timing always an issue, our wired world alleviates these concerns somewhat. And if you find this argument too subtle for its own good, well, remember, there's always the Umesh option.

Another worry heard on Theory Street is fragmentation. I don't get that. The sociological makeup of all these conferences is pretty much the same, anyway, so the risk of fragmentation is about as high as that of Dr. Jekyll and Mr. Hyde parting ways -- OK, make that Superman and Clark Kent if you prefer. In fact, this has it exactly backwards. Theory has yet to penetrate many geographical markets. Eurotheory shares a name with our kind, and little else. With Asia a promising growth area for our field, it is of more than symbolic value that ITCS was born in China. All theory conferences today are regional (North America, Latin America, Europe, Asia, etc). Maybe ITCS can be the exception. At any rate, to expand both the intellectual footprint and the geographical reach of Theory is a central goal of this conference.

To close on a personal note, let me get my crystal ball out of its dusty case and tell you what I see. As the new sciences of the 21st century further embrace their algorithmic nature, I see ITCS getting enriched with a growing flow of conceptual imports from physics, biology, economics, etc (and vice-versa). While the letter T was added to ICS for mundane reasons -- an ACM conference had a previous claim on the acronym -- I hope ITCS remains unabashedly theoretical. Yes, you heard right. And as you watch me adroitly duck the tomatoes sure to be hurled my way for this impolitic stand, you might even spot a contradiction or two. I mean, how can computing theory reach out to the sciences without losing its theoretical core? Well, well... Leaving aside the fact that math developed with precisely that sort of outreach, the answer is easy. What the "new" sciences (bio, neuro, socio, and all that) lack more than anything is a conceptual framework. Theoretical computer science can do for them what mathematics did for physics. Why? Because algorithms are the differential equations of the 21st c. They are the language of modern science. That's why. At this point, you expect me to clear my throat and indulge in a tasteful round of name dropping: "Moreover, as Newton and Einstein used to say, blah blah..." (I got that from my physicist friends. Works every time.)



But not today. Truth is, delusion won't help our cause one bit. Neither will diffidence or skittishness, however. These are heady times for computing theory, my friends. Hand wringing over fine tactical points should not distract us from our common goal, which is to allow Theory to expand and flourish, to unite and conquer. ITCS aims to do just that. It is an exciting experiment worthy of your support.

Thanks for your attention and, in a nod to ITCS' roots, a happy Year of the Dragon to all!

Bernard Chazelle

Ernst Specker (1920-2011)

Martin Fürer remembers his former advisor. 

While traveling, I received the unexpected sad news that Ernst Specker passed away on December 10, 2011. He was born in Zürich in 1920. After receiving his doctoral degree at ETH Zürich in 1949, he spent a year at the Institute for Advanced Study in Princeton. Then he returned to ETH in 1950 and stayed there with the exception of two visiting appointments at Cornell University.

Ernst Specker was teaching Linear Algebra when I started my studies at ETH Zürich in 1967. His teaching style was different from the typical polished and streamlined presentations of that time. He was looking for interaction, and did not hesitate to interrupt a proof to insert an example when he sensed that the audience was not following.

Outside the classroom, it was a turbulent time. The youth movement started to question many long established rules of society. For a long time, it seems that the majority of people, without ever thinking about it, had accepted the claim that the US with its war in Vietnam was defending western values. Quite suddenly, this consensus was widely questioned.

ETH had its own little problem. A new law governing the ETH (the only federal university in Switzerland) had just been adopted by the parliament. Many students took issue with the idea that the main goal of ETH was not to satisfy a general human right for education, but to prepare the students to serve the interests of business and industries.

Ernst Specker, who always liked discussions, never accepted anything based on authority without asking some critical questions, had quickly established a relationship with the young students at this time of evolving political turmoil.

Here are two examples, typical for Ernst. The mathematics and physics students of each semester had an open discussion about the ETH law. One professors came to our group to tell us, we should not complain, its our fault, we should have had this discussion a year ago, when it was the proper time to voice any opposition. He was not happy, when Ernst disagreed, noticing that this group of students has only been here for half a year.

A more important move was Ernst Specker's engagement for the Manifesto of Zürich, a public declaration against police brutality after some excesses when the "establishment" was shocked and fearful of the demonstrations in downtown Zürich.

During our studies, we all had to give talks in four seminars in different areas of mathematics. This rule was widely followed with one exception. A large group of students participated in the logic seminar, and they came back ever since (naturally in addition to the other seminars). Every semester, there was a different theme. My first subject was the solution of Hilbert's tenth problem, presented with all background information and details. The seminar was conducted with Hans Läuchli. Paul Bernays, who had started the seminar when he came from Göttingen before the second world war, was still a regular participant. He often followed the talks reading the blackboard with a two minute delay.

Ernst conducted the seminar still long after his retirement, because unfortunately ETH no longer had a position for mathematical logic. I participated in Ernst’s last logic seminar during my sabbatical in 2002. We ended the semester with a talk of Ernst that was intended for a general mathematical audience. I reserved the beautiful and rather spacious Aula of the ETH for this purpose. Luckily, we could still switch to the Auditorium Maximum, in the last minute, when we saw the people  arriving.

Scientifically, Ernst Specker has worked in many areas as illustrated in by the Selecta volume published by Birkhäuser on the occasion of his 70th birthday.  In his dissertation with Heinz Hopf, Ernst worked on cohomology groups. Then he moved on to investigate constructively in analysis, and the foundation of set theory, in particular Quine's new foundations. He also solved one of the early Erdős problems. Ernst’s most famous results are the works with Simon Kochen on the foundations of quantum mechanics, proving that certain hidden variable theories are not possible, and thus colliding with the assumptions made in the famous Einstein-Podolsky-Rosen paper. The results of Kochen and Specker are still discussed today in the physics literature. Early on and in his additional weekly seminar with Volker Strassen starting in the early seventies, he reached out to complexity theory.

Ernst Specker will always be remembered for his teaching and his scientific work, but most of all for his friendship, his openness and his engaging discussions.

Martin Fürer
Pennsylvania State University

What should we do?

Time for a post by tweet request.

Is a wave of action against big publishers' practices brewing?gowers.wordpress.com/2012/01/21/els…thecostofknowledge.com Should CS do more? @fortnow
— Tugkan Batu (@tugkanbatu) January 22, 2012

Quite a lot on the Internets on Tim Gowers' promise not to work with Elsevier anymore. I'm not as anti-Elsevier as Gowers or many of my readers but I understand the frustrations.

It's easy to make a promise not to publish, edit or referee papers, especially when you don't need to improve your academic reputation. Still a mathematician of his magnitude really puts a spotlight on that publisher.

Because of the Elsevier stigma we've had for several years, all the theoretical CS journals of Elsevier are not nearly as strong as they have been in the past. So you don't accomplish much more just by boycotting Elsevier.

Making a difference means what you do, not what you don't do. Be sure and support journals that are worthy of support by submitting and refereeing papers and serving on editorial boards. The best attack on publishers that you don't like is to have several strong alternatives. The best way to make them strong is by having your support.

No journals is completely free of cost, they require money or time. Open access journals without page charges generally have no revenue stream and require effort to make to publish the journal. For these journals you can volunteer your time as well as submitting, refereeing and editing.

Remember it's easy to complain and say what you won't do but it is what you do do that makes the difference.

Teaching an Honors Section of Discrete Mathematics

A few years ago I was assigned to teach the HONORS section of Discrete Math (a course for sophomores who have had a year of programming and a year a calculus). They told me it was up to me to figure out what to do to make it an honors course. (My section had 30 students, the non-Honors has about 60.) There were several options:

1. This could be taught separate from the non-honors course. Diff homework, diff exams.
   PRO: the homework and exams can be more interesting since you do not have to worry about how they are for the non-honors student.
   1. CON: If a student would have gotten (say) an A in the non-honors course, but gets a B in the honors section, that is not good. OR the teacher could grade inflate so that the students who got a B in the reg section gets an A in the honors section.
2. You could give the same exams and homework to the honors students but REQUIRE them to do more work- extra problems on the homework, extra problems on the Exams.
   1. PRO: They will get to do more fun problems.
   2. CON: They are being penalized for taking an honors course.
3. Same Exams and homework as the regular class. The regular class meets Tu-Th for 75 minutes. The Honors class meets MWF for 50 minutes each. What the Regular class does on Tu-Th, the honors class does on MW. On FRIDAY the honors class has an HONORS DAY- they work in groups of 3 or 4 on problems of more interest than usual. (example: For Logic devise a way to do do AND, OR, and NOT if the variables take on values BETWEEN 0 and 1 (including 0 and 1)). There is a LIGHT homework on this work just to keep them honest. But its not graded seriously.
   1. PRO: They get to learn more stuff in a fun way.
   2. CON: More work for the professor to make up these kinds of problems. (To brag- this is the sort of thing I am good at so not a problem for me.)

I did the last one and I think it worked, for some definition of worked. That is, the students liked it and found it interesting, but its hard to compare it to other ways of doing it. (Doing real studies that tell you things in the field of Education is hard.)

How have you, or would you, run an honors course in discrete math? How about for a programming course?

How important are the Fib numbers in math? in Nature? In History of Math books?

The following quotes is from In the book Algebra in Ancient and Modern Times by V.S. Varadarajan.

Fibonacci numbers thus grow very fast with N, indeed in geometric progression. This is often called exponential growth. They remained as curiosities till in the 1960's they were found to be crucial in certain studies in mathematical logic.

I suspected they were refering to its use in Hilbert's tenth problem even though that was really 1970 (a quibble) and I would hardly call it crucial (a more substantial objection). In fact Fib Numbers are not even needed in the end. I asked Chris Lastowksi who is a Model Theorist at UMCP and he told me the folowing:

Yes. Matijasec showed that the Fibonacci sequence was diophantine, and this sufficed to solve Hilbert's tenth problem (actually to show it could not be solved), by earlier work of Davis, J. Robinson and Putnam. However, Davis almost immediately showed that the exponential function is diophantine, which yields the solution to H-10 more easily, so I would hardly call that a deep connection.

V.S. Varadarajan wanted to make the Fib numbers interesting and important. The attempt was not quite right.

1. How bad is it for a history-of-math book to exaggerate how important some concept is?
2. How important are the Fib Numbers? Do they come up in Mathematics?
3. Could V.S. Varadarajan have picked a better example of their use in mathematics?
4. It has been said that the Fib Numbers come up in Nature. According to Fib Flim Flam most of the statements made about Fib numbers and nature are suspect.

The Information Flood

Twitter, Facebook, Google+. Information now comes to us as a faucet. If you don't drink it all it disappears forever. Try to find status updates and tweets from even a few days ago. Many of you wouldn't have seen this blog post if you didn't catch it on Twitter or Google+.

I try to keep my faucet turned relatively low. I still like RSS feeds like Google Reader. Stuff stays until you discard it. I try not to have too many Twitter followers or Facebook friends.

But the trend is for people, especially the younger generations, to subscribe to whatever fills their fancy. They get a continual stream of information and ignore what they don't see. So Google and Facebook develop algorithms based heavily on what the crowds and your friends are looking at, to determine the order of what you see. Twitter will surely have to follow. Google even tries to decide which of my emails are important.

As goes the Internet goes so does academic knowledge. How do we cut through the research clutter? Will we have algorithms and the crowds tell us which research papers to look at? That used to be the job of journal editors, conference program committees and my grad students.

Being Random and Trivial in Dagstuhl

This week I'm at the Computability, Complexity and Randomness workshop at Dagstuhl in Germany. This meeting brings together two groups, complexity theorists and computability theorists, who share a common love of Kolmogorov complexity.

From the logicians I learned about K-trivial sets. Let K(x) be the prefix-free Kolmogorov complexity of x, i.e., the size of the smallest program that generates x. There are several equivalent definitions of K-trivial sets, here is two of them. A are K-trivial if

1. For some constant c, for all x, K(x) ≤ K^A(x)+c, where K^A(x) is the smallest program generating x with access to oracle A.
2. For some constant c, for all n, K(A_1:n) ≤ K(n)+c, where A_1:n are the first n bits of the characteristic sequence of A.

Lots of interesting properties about K-trivial sets.

• All computable sets are K-trivial and there are K-trivial sets that are not computable.
• There are only a countable number of K-trivial sets. In fact there are only a finite number of K-trivial sets for each fixed constant c above. 
• Every K-trivial set is super-low, that is the halting problem relative to a K-trivial set is non-adaptively reducible to the halting problem.
• Every K-trivial non-adaptively reduces to a computably-enumerable set.
• Every set reducible to a K-trivial is K-trivial.
• The disjoint union of two K-trivial sets is K-trivial.
• Random sets are still random relative to A.

More about K-trivial sets and everything else computably random in a great book by Downey and Hirschfeldt. 

Us complexity theorists started thinking about polynomial-time versions of K-trivial sets but probably won't have as many nice properties. 

The Conjunction Paradox

In Yesterday's post you were told about Susan:

Susan is 31 years old, single, outspoken and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

You were asked to rank the probabilities of certain things about Susan. Two of the choices were

a bank teller

a bank teller and an active feminist

LOGICALLY bank teller and feminist would have a HIGHER probability than bank teller and and active feminist. Some people (including me when I first was given this exercise) ranked bank teller lower bank teller and active feminist. Why? I think that either people are not good at logic in real-world situations or people implicitly view bank teller as bank teller and NOT an active feminist. This problem has been extensively studied and there are other opinions.

Of the 30 responses I got before posting this roughly 10 ranked bank teller higher than bank teller and and active feminist (which is correct), 10 ranked bank teller and and active feminist higher than bank teller, and 10 of the answers were not relevant (e.g., clarifications of the question). (One person I blocked since he explained the above and would have given away the game, and one person who left a comment 5 minutes ago I will let through but only after I post this.)

I recommend giving this exercise to students in a class that covers logic and/or probability to see what they say.

Clyde Kruskal told me about this problem. He found it here though its also at other sites. This source credits the following (which I would guess is correct). Tversky, Amos; & Kahneman, Daniel (1983), Extensional Versus Intuitive Reasoning: The Conjunction Fallacy in Probability Judgment", Psychological Review 90(4) (October): 293-315. They are famous for these sorts of psychology questions. The latter won the Nobel prize in economics for joint work with the former.

The notion that A is less likely than A AND B is called The Conjunction Fallacy. The article pointed to only gives the two choices: (1) Bank Teller, and (2) Bank Teller and an active feminist. I think its better to give all of those choices as is done here other presentations of this exercise.

Rank these possibilities by probability

Readers- I want you to answer this question and post your answers as comments. I will tell you WHY I am asking tommorow.

Susan is 28 years old, single, outspoken, and very bright. She majored in philosophy. As a student she was deeply concerned with issues of discrimination and social justice and also participated in anti-nuke demonstrations.

Please rank the following possibilities by their probability. List them LOW to HIGH. (Just post your answers. Other comments I may block so that others can enjoy the question.)

1. a kindergarden teacher
2. works in a bookstore and takes yoga classes
3. an active feminist
4. a psychiatric social worker
5. a member of the Sierra club
6. a bank teller
7. an insurance salesperson
8. a bank teller and an active feminist

Starting the Year with Turing

This week I was in Boston for the Joint Math Meeting, a combined meeting of the AMS, MAA and a couple of other three-letter math societies with 7000 of my closest math buddies. This is the main American meeting of mathematicians one part of which are interviews for math jobs which seem few and far between.

The conference didn't seem large to me because I spent most of the meeting at the AMS-ASL Special Session on the Life and Legacy of Alan Turing. I got to see some exciting speakers I haven't seen before including Martin Davis, Andrew Hodges (who authored the famous Turing biography soon to be re-issued) and my great-grand advisor Marvin Minsky. Minsky talked mostly about the sorry state of AI over the past few decades including how the Watson people were working on the wrong problem. I found myself in the strange position of defending AI before my talk the next day.

Craig Bauer, a math historian, talked about the early days of voice encryption during Work War II, basically digitizing and then applying a one-time pad. Turing developed a mechanism that used a hardware PRG improving the quality of the audio and reducing the space needed from a large room to small box, though it was never deployed in the field.

Ted Slaman send me this link with Turing suggesting that PRG can help in searching. I guess Turing did care about running time after all but we still haven't found his lost letter on P v NP.

Interesting fact: Gödel and Turing both admired each other's work but there is no evidence that they ever met or had any direct communication of any kind.

A fun workshop but I'm all Turing'd out and it is only the first week of the Alan Turing Year though I am still looking forward to June to attending the ACM Turing Celebration in San Francisco and CiE in Cambridge.

Next week I'm off to Dagstuhl for Computability, Complexity and Randomness. The fun also continues in the Boston area with ITCS.

Is there a NICE gadget for showing PLANAR HC is NPC?

(I have already posted this question on CS Theory Stack Exchange.)

If you know that 3-COL is NPC then you can prove that PLANAR 3-COL is NPC by a NICE gadget that removes crossings (see here for some lecture notes on it. They are not mine. The original link is here but I can't figure out the real author, though it is likely whoever taught Algorithms at CMU in Spring of 2004.)

Lets say we know that HAM CYCLE is NPC (we do!). Is there a gadget to remove crossings so you can show that PLANAR HAM CYCLE is NPC? The problem of PLANAR HAM CYCLE is NPC so there sort-of has to be a gadget; but is there a NICE one? (The proof that PLANAR HAM Cycle is NPC is from SAT and I find it rather complicated (see here for the original paper.) I have tried to extract an uncrossing gadget from it but have not been able to it.

SO- I ask you, do you know of a NICE gadget for removing crossings in a graph so that we can easily go from HAM CYCLE NPC to PLANAR HAM CYCLE NPC.

I'll be happy with HAM PATH or HAM CYCLE or DIRECTED HAM PATH or DIRECTED HAM CYCLE.