Intuitive Proofs

As I mentioned a few months ago, I briefly joined an undergraduate research seminar my freshman year at Cornell. In that seminar I was asked if a two-dimensional random walk on a lattice would return to the origin infinitely often. I said of course. The advisor was impressed until he asked about three-dimensional walks and I said they also hit the origin infinitely often. My intuition was wrong.

33 years later I'd like to give the right intuition. This is rough intuition, not a proof, and I'm sure none of this is original with me.

In a 1-dimensional random walk, you will be at the origin on the nth step with probability about 1/n^0.5. Since the sum of 1/n^0.5 diverges this happens infinitely often.

In a 2-dimensional random walk, you will be at the origin on the nth step with probability about (1/n^0.5)² = 1/n. Since the sum of 1/n diverges this happens infinitely often.

In a 3-dimensional random walk, you will be at the origin on the nth step with probability about (1/n^0.5)³ = 1/n^1.5. Since the sum of 1/n^1.5 converges this happens finitely often.

News Aplenty

Both the Turing Award and the Abel Prize were announced this morning.

MIT databases researcher Michael Stonebraker wins the ACM Turing Award. He developed INGRES one of the first relational databases. Stonebraker is the first Turing award winner since the prize went up to a cool million dollars.

John Nash and Louis Nirenberg share this years Abel Prize “for striking and seminal contributions to the theory of nonlinear partial differential equations and its applications to geometric analysis.” This work on PDEs is completely independent from the equilibrium results that won Nash the 1994 Nobel Prize.

Earlier this week the CRA released their latest Best Practice Memo: Incentivizing Quality and Impact: Evaluating Scholarship in Hiring, Tenure, and Promotion. In short: Emphasize quality over quantity in research.

The NSF announced their public access plan to ensure that research is "available for download, reading and analysis free of charge no later than 12 months after initial publication".

Which mathematician had the biggest gap between fame and contribution?

(I was going to call this entry  Who was the worst mathematician of all time? but Clyde Kruskal reminded me that its not (say) Goldbach's fault that his conjecture got so well known, in fact its a good thing! I'll come back to Goldbach later.)

Would Hawking be as well known if he didn't have ALS?  I suspect that within Physics yes, but I doubt he would have had guest shots on ST:TNG, The Simpsons, Futurama, and The Big Bang Theory (I just checked the IDMB database- they don't mention Futurama but they do say he's a Capricorn. I find that appalling that they mention a Scientists Horoscope.) I also doubt there would be a movie about him.

Would Turing be as well known if he wasn't gay and didn't die young  (likely because of the ``treatment'') would he be as well known? I suspect that within Computer Science yes, but I doubt there would be a play, a movie, and there are rumors of a musical. Contrast him with John von Neumann who one could argue contributed as much as Turing, but, alas, no guest shots on I Love Lucy, no movie, no Rap songs about him. (The only scientist that there may be a rap song about is Heisenberg, and that doesn't count since it would really be about Walter White.)

Hawking and Turing are/were world class in their fields. Is there someone who is very well known but didn't do that much?

SO we are looking for a large gap between how well known the person is and how much math they actually did. This might be unfair to well-known people (it might be unfair to ME since complexityblog makes me better known than I would be otherwise).  However, I have AN answer that is defensible. Since the question is not that well defined there prob cannot be a definitive answer.

First lets consider Goldbach (who is NOT my answer). He was a professor  of math and did some stuff on the Theory of curves, diff eqs, and infinite series. Certainly respectable. But if not for his
conjecture (every even number is the sum of two primes- still open)  I doubt we would have heard of him.

My answer: Pythagoras! He is well known as a mathematician but there is no evidence that he had any connection to the theorem that bears his name.

Historians (or so-called historians) would say that it was well known that he proved the theorem, or gave the first rigorous proof, or something, but there is no evidence. Can people make things up out of whole cloth? Indeed they can.

Witness this Mr. Clean Commercial which says:  they say that after seeing a magician make his assistant disappear Mr Clean came up with a product that makes dirt disappear- the magic eraser. REALLY? Who are ``they''? Is this entire story fabricated? Should we call the FCC :-) ANYWAY, yes, people can and do make up things out of whole cloth and then claim they are well known. Even historians.

Commenters: I politely request that if you suggest other candidates for large gap then they be people who died before 1950 (arbitrary but firm deadline). This is not just out of politeness to the living and recently deceased, its also because these questions needs time. Kind of like people who want to rank George W Bush or Barack Obama as the worst prez of all time--- we need lots more time to evaluate these things.

Feeling Underappreciated

As academics we live and die by our research. While our proofs are either correct or not, the import of our work has a far more subjective feel. One can see where the work is published or how many citations it gets and we often say that we care most about the true intrinsic or extrinsic value of the research. But the measure of success of a research that we truly care most about is how it is viewed within the community. Such measures can have a real value in terms of hiring, tenure, promotion, raises and grants but it goes deeper, filling some internal need to have our research matter to our peers.

So even little things can bother you. Not being cited when you think your work should be. Not being mentioned during a talk. Seeing a review that questions the relevance of your model. Nobody following up on your open questions. Difficulty in finding excitement in others about your work. We tend to keep these feelings bottled up since we feel we shouldn't be bragging about own work.

If you feel this way a few things to keep in mind. It happens to all of us even though we rarely talk about it. You are not alone. Try not to obsess, it's counterproductive and just makes you feel even worse. If appropriate let the authors know that your work is relevant to theirs, the authors truly may have been unaware. Sometimes it is just best to acknowledge to yourself that while you think the work is good, you can't always convince the rest of the world and just move on.

More importantly remember the golden rule, and try to cite all relevant research and show interest in other people's work as well as your own.

Has anything interesting ever come out of a claimed proof that P=NP or P ≠ NP?

When I was young and foolish and I heard that someone thinks they proven P=NP or P ≠  NP I would think Wow- maybe they did!. Then my adviser, who was on the FOCS committee, gave me a paper that claimed to resolve P vs NP!   to review for FOCS.  It was terrible. I got a became more skeptical.

When I was older and perhaps a byte less foolish I would think the following:

For P=NP proofs: I am sure it does not proof P=NP BUT maybe there are some nice ideas here that could be used to speed up some known algorithms in practice, or give some insights, or something. Could still be solid research (A type of research that Sheldon Cooper has disdain for, but I think is fine).

and

For P ≠  NP proofs: I am sure it does not prove P ≠ NP BUT maybe there are some nice ideas  here, perhaps a `if BLAH than P ≠  NP', perhaps an nlog^* lower bound on something in some restricted model'.

Since I've joined this blog I've been emailed some proofs that claim to resolve P vs NP (I also get some proofs in Ramsey Theory, which probably  saves Graham/Rothchild/Spencer some time since cranks might bother me instead of them). These proofs fall into some categories:

P ≠  NP because there are all those possibilities to look through (or papers that are far less coherent than that but that's what it comes down to)

P=NP look at my code!

P=NP here is my (incoherent) approach. For example `first look for two variables that are quasi-related' What does `quasi-related' mean? They don't say.

Papers where I can't tell what they are saying. NO they are not saying independent of ZFC, I wish they were that coherent. Some say that its the wrong question, a point which could be argued intelligently but not by those who are writing such papers.

OKAY, so is there ANY value to these papers? Sadly looking over all of the papers I've gotten on P vs NP (in my mind- I didn't save them --should I have?) the answer is an empirical NO. Why not? I'll tell you why not by way of counter-example:

Very early on, before most people know about FPT, I met Mike Fellows at a conference and he told me about the Graph Minor Theorem and Vertex Cover. It was fascinating. Did he say `I've solved P vs NP' Of course not. He knew better.

Taking Mike Sipers's Grad Theory course back in the 1980's he presented the recent result: DTIME(n) ≠ NTIME(n). Did Mike Sipser or the authors (Paul, Pippenger, Szemeredi, Trotter) claim that they had proven P vs NP? Of course not, they knew better

Think of the real advances made in theory. They are made by insiders, outsiders, people you've heard of, people you hadn't heard of before, but they were all made my people who... were pretty good and know stuff.  YES, some are made by people who are  not tainted by conventional thinking, but such people can still differentiate an informal argument from a proof, and they know that an alleged proof that resolves P vs NP needs to be checked quite carefully before bragging about it.

When the result that Monotone circuits have exponential lower bounds for some problems there was excitement that this may lead to a proof that P ≠ NP, however, nobody, literally nobody, claimed that these results proved P ≠ NP. They knew better.

So, roughly speaking, the people who claim they've resolved P vs NP either have a knowledge gap or can't see their own mistakes or something that makes their work unlikely to have value. One test for that is to ask if they retracted the proof once flaws have been exposed.

This is not universally true- I know of two people who claimed to have solved the problem who are pretty careful normally.  I won't name names since my story might not be quite right, and because they of them retracted IMMEDIATELY after seeing the error. (When Lance proofread this post he guessed one of them,
so there just aren't that many careful people who claim to have resolved P vs NP.)  And one of them got an obscure paper into an obscure journal out of their efforts.

I honestly don't know how careful Deolaikar  is, nor do I know if anything of interest every came out of his work, or if has retracted it.  If someone knows, please leave a comment.

I discuss Swart after the next paragraph.

I WELCOME counter-example! If you know of a claim to resolve P vs NP where the authors paper had something of value, please comment. The term of value means one of two things: there really was some theorem of interest OR there really were some ideas that were later turned into theorems (or in the case of P=NP turned into usable algorithms that worked well in practice).

One partial counter-example- Swarts claim that P=NP inspired OTHER papers that were good: Yannakakis's proof that Swart's approach could not work and some sequels that made Lance's list of best papers of the 2000's (see this post). I don't quite know how to count that.

Quotes with which I disagree

Often we hear pithy quotes by famous people but some just don't hold water.

"Computer science is no more about computers than astronomy is about telescopes."

Usually attributed to Edsger Dijkstra, the quote tries to capture that using computers or even programming is not computer science, which I agree. But computer science is most definitely about the computers, making them connected, smarter, faster, safer, reliable and easier to use. You can get a PhD in computer science with a smarter cache system, you can't get a PhD in Astronomy from developing a better telescope lens.

"If your laptop cannot find it, neither can the market."

This quote by Kamal Jain is used to say a market can't find equilibrium prices when the equilibrium problem is hard to compute. But to think that the market, with thousands of highly sophisticated and unknown trading algorithm combined with more than a few less than rational agents all interacting with each other can be simulated on a sole laptop seems absurd, even in theory.

"If you never miss the plane, you're spending too much time in airports."

George Stigler, a 1982 Nobelist in economics, had this quote to explain individual rationality. But missing a flight is a selfish activity since you will delay seeing people at the place or conference you are heading to or family if you are heading home. I've seen people miss PhD defenses because they couldn't take an extra half hour to head to the airport earlier. If you really have no one on the other side, go ahead and miss your plane. But keep in mind usually you aren't the only one to suffer if you have to take a later flight.

I take the opposite approach, heading to the airport far in advance of my flight and working at the airport free of distractions of the office. Most airports have the three ingredients I need for an effective working environment: wifi, coffee and restrooms.

Guest Post by Thomas Zeume on Applications of Ramsey Theory to Dynamic Descriptive Complexity

Guest Post by Thomas Zeume on

Lower Bounds for Dynamic Descriptive Complexity

(A result that uses Ramsey Theory!)


In a previous blog post Bill mentioned his hobby to collect theorems that
apply Ramsey theory.  I will present one such application that arises in
dynamic descriptive complexity theory.  The first half of the post introduces
the setting, the second part sketches a lower bound proof that uses Ramsey theory.

Dynamic descriptive complexity theory studies which queries can be maintained by
first-order formulas with the help of auxiliary relations, when the input structure
is subject to simple modifications  such as tuple insertions and tuple deletions.

As an example consider a directed graph into which edges are inserted. When an edge
(u, v) is inserted, then the new transitive closure T' can be defined from the old
transitive closure T by a first-order formula that uses u and v as parameters:

T'(x,y) = T(x,y) ∨ (T(x, u) ∧ T(v, y))

Thus the reachability query can be maintained under insertions in this fashion
(even though it cannot be expressed in first-order logic directly).

The above update formula is an example of a dynamic descriptive complexity program.
In general, dynamic programs may use several auxiliary relations that are helpful
to maintain the query under consideration. Then each auxiliary relation has one
update formula for edge insertions and one formula for edge deletions.
The example above uses a single auxiliary relation T (which is also the designated
query result) and only updates T under insertions.

This principle setting has been independently formalized in very similar ways by
Dong, Su and Topor [1, 2] and by Patnaik and Immerman [3]. For both groups one of
the main motivations was that first-order logic is the core of SQL and therefore
       queries maintainable in this setting can also be maintained using SQL. Furthermore
the correspondance of first-order logic with built-in arithmetic to uniform
AC0-circuits (constant-depth circuits of polynomial size with unbounded fan-in)
yields that queries maintainable in this way can be evaluated dynamically in a
highly parallel fashion.

One of the main questions studied in Dynamic Complexity has been whether
Reachability on directed graphs can be maintained in DynFO
(under insertions and deletions of edges). Here DynFO is the class of
properties that can be maintained by first-order update formulas.
The conjecture by Patnaik and Immerman that this is possible has been recently
confirmed by Datta, Kulkarni, Mukherjee, Schwentick and the author of this post,
but has not been published yet [4].

In this blog post, I would like to talk about dynamic complexity LOWER rather
than upper bounds.  Research on dynamic complexity lower bounds has not been
very successful so far. Even though there are routine methods to prove that a
property can not be expressed in first-order logic (or, for that matter, not in AC0),
the dynamic setting adds a considerable level of complication. So far, there is
no lower bound showing that a particular property can not be maintained in
DynFO (besides trivial bounds for properties beyond polynomial time).

For this reason, all (meaningful) lower bounds proved so far in this setting
have been proved for restricted dynamic programs. One such restriction is to
disallow the use of quantifiers in update formulas.  The example above illustrates
that useful properties can be maintained even without quantifiers
(though in this example under insertions only). Therefore proving lower bounds
for this small syntactic fragment can be of interest.

Several lower bounds for quantifier-free dynamic programs have been proved by using
basic combinatorial tools. For example, counting arguments yield a lower bound for
alternating reachability and non-regular languages [5], and Ramsey-like theorems
as well as Higman's lemma can be used to prove that the reachability query
(under edge insertions and deletions) cannot be maintained by
quantifier-free dynamic programs with binary auxiliary relations [6].

Here, I will present how bounds for Ramsey numbers can be used to obtain lower bounds.
Surprisingly, the proof of the lower bound in the following result relies on both
upper and lower bounds for Ramsey numbers. Therefore the result might be a good candidate
for Bill's collection of theorems that use Ramsey-like results.

THEOREM (from [7])
When only edge insertions are allowed, then (k+2)-clique can be maintained by a
quantifier-free dynamic program with (k+1)-ary auxiliary relations, but it cannot be
maintained by such a program with k-ary auxiliary relations.

SKETCH OF PROOF

I present a (very) rough proof sketch of the lower bound in the theorem.
The proof sketch aims at giving a flavour of how the upper and lower bounds
on the size of Ramsey numbers are used to prove the above lower bound.

Instead of using bounds on Ramsey numbers, it will be more convenient to use
the following equivalent bounds on the size of Ramsey cliques. For every c and large enough n:

1) Every $c$-colored complete $k$-hypergraph of size n contains a large Ramsey clique.

2) There is a 2-coloring of the complete $(k+1)$-hypergraph of size n that does \emph{not} contain a large Ramsey clique.


In the following it is not necessary to know what "large" exactly means
(though it roughly means of size log^{k-1} n in both statements).
Those bounds are due to Rado, Hajnal and Erdős.

Towards a contradiction we assume that there is a quantifier-free program P with
k-ary auxiliary relations that maintains whether a graph contains a (k+2)-clique.

The first step is to construct a graph G = (V UNION W, E) such that in all large subsets
C of V one can find independent sets A and B of size k+1 such that adding all edges
between nodes of A yields a graph containing a (k+2)-clique while adding all edges
between nodes of B yields a graph without a (k+2)-clique. Such a graph G can be constructed
 using (2). (Choose a large set V and let W := V^{k+1}. Color the set W according to
(2) with colors red and blue. Connect all blue elements w = (v_1, ..., v_{k+1}) in W
with the elements v_1, \ldots, v_{k+1} in V.)

Now, if the program P currently stores G, then within the current auxiliary relations
stored by P one can find a large subset C of V where all k-tuples are colored equally
by the auxiliary relations. Such a set C can be found using (1). (More precisely:
by a slight extension of (1) to structures.)

By the construction of G there are subsets A and B of the set C with the property stated
above. As A and B are subsets of C, they are isomorphic with respect to the auxiliary
relations and the edge relation. A property of quantifier-free programs is that for such
isomorphic sets, the application of corresponding modification sequences yields the same
answer of the program, where "corresponding" means that they adhere to the isomorphism.

Thus the dynamic program P will give the same answer when adding all edges of A, and whenadding all edges of B (in an order that preserves the isomorphism). This is a contradiction
as the first sequence of modifications yields a graph with a (k+2)-clique while the second
yields a graph without a (k+2)-clique. Hence such a program P cannot exist. This proves
the lower bound from the above theorem.

I thank Thomas Schwentick and Nils Vortmeier for many helpful suggestions on how to
improve a draft of this blog post.

 [1] Guozhu Dong and Rodney W. Topor. Incremental evaluation of datalog queries. In ICDT 1992, pages 282–296. Springer, 1992.

 [2] Guozhu Dong and Jianwen Su. First-order incremental evaluation of datalog queries. In Database Programming Languages, pages 295–308. Springer, 1993.

 [3] Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199–209, 1997.

 [4] Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. ArXiv 2015.

 [5] Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. ACM Trans. Comput. Log., 13(3):19, 2012.

 [6] Thomas Zeume and Thomas Schwentick. On the quantifier-free dynamic complexity of Reachability. Inf. Comput. 240 (2015), pp. 108–129

 [7] Thomas Zeume. The dynamic descriptive complexity of k-clique. In MFCS 2014, pages 547–558. Springer, 2014.

(1/2)! = sqrt(pi) /2 and other conventions

 (This post is inspired by the book The cult of Pythagoras: Math and Myths which I recently
read and reviewed. See here for my review.)

STUDENT: The factorial function is only defined on the natural numbers. Is there some way to extend it to all the reals? For example, what is (1/2)! ?

BILL: Actually (1/2)! is sqrt(π)/2

STUDENT: Oh well, ask a stupid question, get a stupid answer.

BILL: No, I'm serious, (1/2)! is sqrt(π)/2.

STUDENT: C'mon, be serious. If you don't know or if its not known just tell me.

The Student has a point. (1/2)! = sqrt(π)/2 is stupid even though its true. So I ask--- is there some other way that factorial could be expanded to all the reals that is as well motivated as the Gamma function? Since 0!=1 and 1!=1, perhaps  (1/2)! should be 1.

Is there a combinatorial interpretation  for (1/2)!=sqrt(π) /2?

If one defined n! by piecewies linear interpolation that works but is it useful? interesting?

For that matter is the Gamma function useful? Interesting?

ANOTHER CONVENTION:  We say that 0^0 is undefined. But I think it should be 1.
Here is why:

d/dx  x^n = nx^{n-1} is true except at 1. Lets make it ALSO true at 1 by saying that x^0=1 ALWAYS
and that includes at 0.

A SECOND LOOK AT A CONVENTION:  (-3)(4) = -12 makes sense since if I owe my bookie
3 dollars 4 times than I owe him 12 dollars. But what about (-3)(-4)=12. This makes certain
other laws of arithmetic extend to the negatives, which is well and good, but we should not
mistake this convention for a discovered truth. IF there was an application where definiting
NEG*NEG = NEG then that would be a nice alternative system, much like the diff geometries.

I COULD TALK ABOUT a^{1/2} = sqrt(a) also being a convention to make a rule work out
however (1) my point is made, and (2) I think I blogged about that a while back.

So what is my point- we adapt certain conventions which are fine and good, but should not
mistake them for eternal truths. This may also play into the question of is math invented or
discovered.

Leonard Nimoy (1931-2015)

Bill and I rarely write joint blog posts but with the loss of a great cultural icon we both had to have our say.

Bill: Leonard Nimoy (Spock) died last week at the age of 83. DeForest Kelley (McCoy) passed away in 1999. William Shatner (Kirk) is still alive, though I note that he is four days older than Nimoy.

Spock tried to always be logical. I wonder if an unemotional scientist would be a better or worse scientist.
Does emotion drive our desire to learn things? Our choice of problems to work on? Our creativity?

Did Star Trek (or its successors) inspire many to go into science? Hard to tell but I suspect yes. Did it inspire you?

There depiction of technology ranged from predicative (communicators are cell phones!) to awful (Episode 'The Ultimate Computer' wanted to show that humans are better than computers. It instead showed that humans are better than a malfunctioning killer-computer. I think we knew that.) I think TV shows now hire science consultants to get things right (The Big Bang Theory seems to get lots of science right, though their view of academia is off.) but in those days there was less of a concern for that.

Lance: I'm too young to remember the original Star Trek series when it first aired but I did watch the series religiously during the 70's when a local TV station aired an episode every day, seeing every episode multiple times. The original Star Trek was a product of its time, using the future to reflect the current societal issues of the 60's. Later Star Trek movies and series seemed to have lost that premise.

Every nerdy teenager, myself included, could relate to Spock with his logical exterior and his half-human emotional interior that he could usually suppress. Perhaps my favorite Spock episode was the penultimate "All Our Yesterdays" where Spock having been sent back in time takes on an earlier emotional state of the old Vulcans and falls in love.

I did see Leonard Nimoy in person once, during a lecture at MIT in the 80's. He clearly relished being Spock and we all relished him.

Goodby Leonard. You have lived long and prospered and gone well beyond where any man has gone before.