Howdy, neighbor

Constructing phylogenetic trees from distances is crucial to computational genomics. That's why this paper is such a comfort; R. Mihaescu, D. Levy, and L. Pachter have shown that the neighbor-joining algorithm accomplishes this task very quickly, at least in an asymptotic and probabilistic sense.

I once overheard the third author wish to see his website at the top of the list of Liors. Back then he was fourth, as of this writing, he's made his way to the number two spot. I'm willing to do my part to help his dream become reality.

Recursion is child's play

Every mathematician (and almost everyone, in fact) is familiar with the "Tower of Hanoi" problem. Not only is it a great way to occupy a patient child for a while, it provides a wonderful illustration of the twin concepts of recursion and induction in the description of the solution to the n-disk problem and the expression of the minimum number of steps in the optimal solution, respectively.

But what if the moves were restricted beyond the basic three commandments? (Thou shalt not place a disk atop any disk of smaller size, for it is hateful to do so; and Thou shalt not place thy hand on more than one disk at the one time, lest you succumb to greed and avarice; and Thou shalt not try to weasel thy way around that last commandment by lifting a disk that is not topmost on its peg, what kind of fool do you take me for?) If, in addition, there is a bound on the difference between the sizes of adjacent disks, what is the optimal solution (if there is one) and how many moves does it take? S. Bendetkis and I. Safro have written a paper dealing with precisely this generalization of the classic problem.

It's always a joy to see some good math on such familiar puzzles.

0-0-0-...-0

The three authors I mentioned recently for completing my work on doubly-laced crystals have put another paper on the arXiv, this time using their framework to unravel some fascinating properties of A_n-crystals.

A special prize awaits the first to explain the title of this post in a comment!

Part of an RC graph

Also known as a pipe dream. While clearly not what the original designers had in mind for these tiles, this arrangement creates a beautiful rhythm, and could even be used in Schubert geometry.

Another shot at the travelling salesman problem

H. Kleiman has written a (very short) paper in which he claims to have proven that P=NP. Many of the usual red flags are up; e.g., his article is only available as a pdf (i.e., he provides no LaTeX source) and the references are light. On the other hand, he withholds the usual bluster with which such claims are made, instead using language like "we (hopefully) can always obtain an optimal tour in M(a) in polynomial time" and "[i]f the algorithm has no errors, ... P=NP." Time will tell...

The other half

Appropriately enough, on the day that I filed my dissertation, a paper went up completing my work on characterizing B₂-crystals by local criteria. It's great to see this, since my article proved only half of the desired result. As I said before, it's good to have publicly visible work; if I didn't, I would not have been given due acknowledgment both in the references and the introduction.

Especially exciting is the possibility that the approach taken by V. I. Danilov, A. V. Karzanov, and G. A. Koshevoy might be generalizable to bigger algebras, so we might see a local characterization of G₂-crystals sometime next year!

Return fire!

M. Diaby claims to have invalidated R. Hofman's refutation of his purported proof of P=NP that was discussed earlier. It's not so much an article as an invitation to a public shouting match, seeing as it lacks an abstract, or references, or even self-contained expository prose. I hope Hofman responds again; this could get interesting.

Symptoms of withdrawal

When I first saw mention of a proof of the existence of a solution to the Navier-Stokes equations, I assumed that it had more in common with "proofs" of P=NP or the Riemann hypothesis. In fact, P. Smith had some keen original insights, even if the paper ultimately needed to be withdrawn. There is no shame in this, of course. As G. Kuperberg has illustrated with many examples posted next to his office door, quite capable mathematicians will from time to time push something out the door before it can stand on its own two feet; many of these errors are discovered when a colleague provides a counter-example to one of the central proofs of the article, which I would find considerably more embarrassing than discovering a "serious flaw" in antecedent peer-reviewed literature. Real shame lies in leaving papers up after their erroneousness has been plainly illustrated; as of this writing, this is true of those who wrote about the LP formulation of the TSP just a few weeks ago.

This became a sufficiently hot topic in the blogosphere community that Seed magazine ran a short write-up of the brief history of Smith's work and the comments made from as high up as P. Woit's site. Unfortunately, S. Ornes took the opportunity to sensationalize the matter, suggesting that these events "might ... give mathematicians of the future a strong incentive to be hyper-meticulous about their work", and "[p]erhaps [they] will have to reconsider posting their work on arXiv."

As if there isn't already sufficient incentive. The referee process is ponderous, and it is simply not in anyone's interest, least of all the researcher's, to submit rough work to peer-reviewed journals. Sloppy work will take even longer to make it to press, or possibly be rejected outright. In our "publish or perish" world, six extra months between publications can have a severe impact on a performance review; while on the job market, it can make the difference between being employed and not.

And no one I know will change their practice of submitting to (or defying) the arXiv. The Seed article suggests that many members of the mathematical community will fear the public scrutiny and response that developed in the wake of the Navier-Stokes paper and therefore reduce their use of the electronic pre-print service. The fact is that extremely few of us are doing such high profile work that it will result in attention beyond the regular readership of our subclassifications, and thus have nothing of the sort to fear. Events such as this, as much as they might make for exciting news stories, have a minimal impact on the day-to-day life of working mathematicians.

The mechanisms that I see at work are two-fold: first, the increasing speed of mathematical communication via the internet, and second, the volume of positive attention mathematics has garnered in recent years in the culture at large. We just happen to be looking at a point in history where these two phenomena have interacted more dramatically than they have before, causing an unprecedented event, the speculated impact of which has been tremendously overstated.

Fifty years ago, preprints were mailed to colleagues at remote institutions, journals played a critical role in the communication of new research, and conferences were one of the rare opportunities for intimate interaction between mathematicians from different regions. Now, journals are published both in print and online, almost every author either uses the arXiv or maintains a collection of their preprints on their own website, and email is routinely used to disseminate results or facilitate collaborations. Conferences, while still providing a unique opportunity to travel to exotic locales and spend some uninterrupted quality time with like-minded researchers, no longer play their critical role in discourse, as conference proceedings are made available electronically and air travel costs for one-on-one collaboration are at stupendous historical lows. The trend always has been to take advantage of new technologies whenever they might be useful; the arXiv will maintain its utility, and will therefore see no decline in its usage.

Thanks to movies, television, and the popular press, a larger segment of the population has taken an interest in mathematics than ever before. This means not only that laypeople are more likely to have a demand for news from the math world, but also that more specialists are willing to fulfill that demand (such as in this forum, solipsistic as it may be). The result is one that has been seen time and time again; once a critical mass of anonymous commentators has accrued, the signal will be overwhelmed by noise. It's very sad that in this case some of that noise took the form of personal criticism of Prof. Smith by non-mathematicians who have no experience with the process of mathematics.

We all make mistakes; those of us who live on the cutting edge make a lot of them. We catch most of them before sharing our work with the world, but a few slip through, are caught later, and rectified. It's far better to live by the pursuit of truth than the fear of error.

As a fortune I got after a chinese meal once told me:

Rather, it's been a big week for crystals

I mentioned some new results on crystals a short while ago; and today, there are two more. These are are of even greater interest to me, as they naturally follow my contribution to the program on perfect crystals.

The next step in M. Okado's research is to obtain an explicit description of type $D_n^{(1)}$-crystals. Since I have more experience dealing with such objects than just about anyone else, Okado-san has invited me to join him in Osaka to work on this problem. I'm not sure if I'll be able to make it, but the invitation certainly is tempting.

IP $\neq$ LP

And in case you might have heard otherwise, we still don't know about P and NP. There are some recently submitted papers (all of which are rather light on references) in the Computational Complexity section of the CS arXiv claiming that P and NP are the same thing, based on formulating the traveling salesman problem as a linear program. Of course, they all make the classic mistake of underestimating the importance of constraining the variables to be integers.

The traveling salesman problem (or the TSP, an abbreviation that reduces the running time of saying its name by a factor of 2) asks simply "What is the shortest journey that makes exactly one stop in every city on a list?" Lest you think this problem is hopelessly academic, peruse this description of a few of the applications of the TSP. And lest you think that this problem seems simple, consider that $1,000,000 rests on its resolution.

I suppose it's not too shocking that a glory-seeking Associate Professor and an unknown researcher (is he a graduate student? an employee of a call-center software company?) would throw their hats in the ring. Hopefully they will learn that integer programming (IP) is not the same thing as linear programming (LP).

Fortunately, R. Hofman has set the record straight. Now, will those other two fellows follow the directions for withdrawing a paper from the arXiv?

Update 11/3/2006: R. Hofman has composed a more general rebuttal to those authors that have used linear programming to claim that P=NP.

A big day for crystals

Two papers just went on the arXiv dealing with crystals for generalized Kac-Moody algebras. None other than M. Kashiwara is involved in this project, so it must be big.

Oh, and there's this one, too. I think I know the author from somewhere.

Discrete topology

Of all the things that the title could mean, such as defining every singleton subset to be open, or discretizing the continuous as A. V. Evako does, this is by far the best I've ever seen.

Sometimes all you need is three pages

Do you know how to increase the volume of a cardboard box by crushing it? I. Pak does. And he shows the world how to do it in

Inflating the cube without stretching
I. Pak

That's definitely the most enjoyable paper I 've read in a while.

Irrationally effective

Everyone knows that e has some nice combinatorial properties, but occasionally a counting result comes along that transcends the well-known mundanity of cute factorials.

Counting and Computing by e
M. Hassani

The problem that just won't go away

Do you like maps? Do you like colors? Do you like coloring maps? Do you like signed permutations? I like signed permutations because they describe genetic mutations. I also like the fact that maybe, just maybe, there's a connection between mutations and how many colors are necessary for map-making.

Signed permutations and the four color theorem
S. Eliahou, C. Lecouvey

I guess you can write a paper about just about anything these days

But I really shouldn't be so harsh. The authors suggest that their work "rediscovers" a lost proof of a very interesting set theoretic result. And attention-grabbing titles can only help to spice up the literature-scape.

Division by three
Peter G. Doyle, John Horton Conway

Pants are one thing, but this is ridiculous

Pants to the power of two? And how did they get a a tree, anyway? Perhaps they were assisted by monkeys?

Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition
David Eppstein

Pachterian geometry

The hardest midterm I ever took was a Numerical Analysis take-home exam. One problem asked for a definition of "the circle that best approximates four co-planar points" and apply our definition to given data. This problem has clear applications to transceiver placement optimization; e.g., where to put a cell phone tower. The model discussed in this preprint describes not only multiple transciever locations, but also the cost to power a signal within a given radius from each tower. It's rare and wonderful to see a real world problem that translates so naturally to a mathematical model.

The professor for the above mentioned Numerical Analysis course, L. Pachter, has some geometric concerns of his own. In this case, the translation from real world problem to mathematical model is considerably harder to understand, mostly because the geometry does not take place in a plane or 3-space. The fundamental object is still a convex body, but it now lives in a larger number of dimensions. Don't let this scare you off; such models are extremely effective for countless applications.

The high TeX arXiv

Numerous posts of mine point to the arXiv, the famous "e-print" server managed by Cornell University. Those at the helm of this marvelous resource have always ridden the leading edge of internet usage. For instance, consider this decade-old page, in which they point out that "... large databases such as this one (which has millions of distinct URL's that lead to gigabytes of data) are likely to grow ever more commonly exported via www." At the time, such archives were commonly hosted on an ftp server. How many of today's internet users even know what ftp stands for?

Fortunately, Cornell's e-librarians are eager to support new internet technologies, such as rss and trackback, at least on an experimental basis. For some reason, this is not widely publicized; perhaps they don't want too many users to become dependent on such features, ensuring that they can be removed without warning while causing minimal disruption. If you are a Physicist, Mathematician, Non-linear Dynamacist, Computer Scientist, or Quantitative Biologist, take advantage of these informational tools; they're there for the using.

The other side of the arXiv

It turns out that some decent papers are posted to arXiv:cs, where authors are not listed alphabetically.

Convex Separation from Optimization via Heuristics
L. M. Ioannou, B. C. Travaglione, D. Cheung

It's good to see convex geometry presented in a decidedly algorithmic setting, since it really thrives there.