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.

In the shadow of Sun

You know you live in Silicon Valley when your employer is on the same exit as campuses for Yahoo! and Sun.

Familiar territory

See, set theory is easy!

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.

Divide and be conquered

When I first read about J. Anderson's new theory of diving by zero, I was skeptical. There are numerous algebraic tricks one can play to make zero-division work out, and I would be surprised to see a novel approach to this problem so late in the game. After seeing the details of the "theory", I knew it was garbage, and suspected that it had already been dissected by M. Chu-Carroll at Good Math, Bad Math; lo and behold, it had.

In true ScienceBlogs form, Chu-Carroll pumps much more vitriol into his response than I would have. Rather than pushing my bile to the surface, it simply makes me wonder why Anderson would make such a foolhardy public display of his "discovery" without first consulting a working mathematician. England has no shortage of universities; they can't all be inaccessible from Berkshire.

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...

SECANTS RATE highly in my book

Longtime readers already know that I'm a regular visitor to dieselsweeties.com to get the daily comic by R. Stevens (or rstevens, as he prefers) featuring the inimitable Clango Cyclotron. He really should visit LBL at some point and see some of the ARCANE TESTS they carry out with the 88". You know, Clango could get in touch with his roots; after all, that first 'L' stands for Lawrence, the inventor of the cyclotron.

I'm enough of a fan of DS that I got my lovely wife a t-shirt featuring a punchline from the comic for Christmas last year. Being a mammalogist, this is far and away the most appropriate of the DS shirts for her to wear, although our CAT RESENTS A message so positive about another species.


I get the impression that R. Stevens is a cat person (and Mac user) like me; given the opportunity, I would CARESS TEN, AT least.

A wish of mine has been granted, and some recent Diesel Sweeties strips have featured mathematically-themed humor. It's good to see that R. Stevens RECASTS A NET from time to time to trawl for these sorts of jokes. The second, in addition to referencing one of the great integer sequences, is concerned with puns, which mathematicians inexplicably enjoy more than most other people. Some mathematicians also enjoy anagrams, although that's more easily explained by the fact that they are a special case of permutations.

To celebrate cope with the commerce season, Stevens is running an anagrammatically named contest. He's a rather good sport about it, even suggesting that writers might describe his pants as a one-ACRE ASS TENT. If I were to open myself up to such public conversation, I'd feel like an ANT AT RECESS, leaving myself completely at the whim of schoolkids. I like his output too much to be so cruel; I especially enjoy Maura's antics (A TART'S SCENE if ever there was one) and the strips in which A SCAT ENTERS. I usually detest "bio-humor", but somehow Stevens treats it so absurdly that it has a certain appeal.

Here's wishing R. Stevens, Clango, and the whole Diesel Sweeties crew a Merry Present Season and a Happy New Year!

Elucidating low technology

All manner of news outlets are reporting on the just announced unraveling of the heretofore mysterious Antikythera mechanism, rediscovered over 100 years ago after falling to the bottom of the Sea of Crete nearly 2000 years before that. Network World has a few photos of the X-ray and tomographic technicians at work, and Wired has put up some beautiful pictures of the device produced from Hewlett-Packard's gallery of reflectance images, in which the user can control how the object is lit. Especially interesting are the fragments of documentation etched into the works, although I must say, it's all Greek to me.

As long-time readers know, I have a soft spot for collisions between the old and the new. It's rather appealing to see the advances in imaging technology over the past century reverse the effects of the elements grinding away for millennia. Consider how lucky we are that it was recovered late enough in history that non-destructive methods were used to study it; it's not too hard to imagine a Victorian-era engineer attempting to take it apart or washing it with baking soda and vinegar.

Having recently read Guns, Germs, and Steel, I can't help but be reminded of the Phaistos disk, another artifact illustrating that Cretan technology was far ahead of its time. It would seem that in both cases the adaptive advantage offered by adopting the new technology (in the case of Phaistos, movable type; in the case of Antikythera, geared wheels) was insufficient to merit the labor required to implement them. The criteria for an innovative idea to be "good" depends on context much more than many people realize.

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!

Ph.inally D.one

There's another F-word that I could have used to title this post, but I know that some of my readership prefer more Ph.amily-Ph.riendly language.

It's hard to get a Ph.D., and not just in the sense that a lot of work goes into the coursework, finding a topic, making an original contribution to the field, etc. After it seems that everything is done; after all 130 pages have been edited, re-edited, and verified by three committee members; after it's been printed on at least 20# paper with at least 25% cotton content; after the cover sheet has been signed by all three members (one of whom is in Australia, another of whom is now in Paris); after two additional copies of the abstract (without page numbers) have been printed; the work isn't done. There are two anonymous questionnaires, one from the NSF and one from UC Davis; there is a release form authorizing the powers that be to copy the document that I spent the last four years preparing onto microfilm and bind it in the library; there is an appointment (between the hours of 1:00 and 4:00 on Tuesday) to be made with one of the staff in the office of graduate studies, wherein the above forms are put in order to be passed on the appropriate offices, and every page of my dissertation is examined to ensure that the pages are consecutive, as are the chapters, and the sections, and the subsections, and that my font is suficiently large and uniform throughout, and that the margins are respected (god forbid you disrespect the margins!). Frankly, if this kind of administrative scrutiny was demanded of bachelors recipients, the numbers for that degree would be much lower. But if you can make it through all of that, then you will have satisfied all requirements of the degree of Doctor of Philosophy, and I'm proud to report that I have done precisely that.


I was somewhat surprised by my elation when D. Swindall handed me that certificate. For many months now, when asked how far along I was, I've said something like "It's mostly paperwork at this point," or "I just have some administrative details to take care of," or "I'm down to minor editing." After saying such a white lie so many times I started to believe that the work I had left really was negligible, and that, for all intents and purposes, I was done. I had even walked; how much could that feeling of completion be enhanced by mere paperwork?

A whole lot, as it turns out. After spending those fifteen minutes yesterday witnessing the inspection of my dissertation's pages, I could say, for the first time without qualification, that I am Dr. Philip Max Sternberg. I'm now as educated as my wife, (although the jury's still out as to who's the smarter one). I'm also the second Dr. Sternberg in my family, a tradition that my father would be happy to see me carry on. Of course, in his view, the important aspect of this endeavor is scholarship, not the title; I'm glad to have had him instill me with that sense of values. For this, and many other reasons, I'm extremely grateful to have the opportunity to dedicate my dissertation to his memory.


Yesterday marked the end of this stage of my life in another way, too; my Jetta, my first car, my graduation present, the car that carried me through all of grad school, was sold to a young couple, both of whom just started their graduate studies. It served me well, and was with me for many fond memories. But it was time to let it go. I think it was best to have it pass out of my hands at the same time as my dissertation; the sense of completion and finality is made all the more real because of it.

A big day, in so many ways.

In my office for the last time

(photo credit: Isaiah Lankham)

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.

What's a four-letter word starting with "R" for "Computer technology developed by D. Patterson"?

It all depends on your interests: if data storage is your thing, the answer is RAID; if you like compilers and microprocessor architecture, you're probably looking for RISC. If, on the other hand, you're taken by what the future might hold for parallel computing, the correct acronym is RAMP; Research Accelerator for Multiple Processors. If you want to continue to be impressed, look over the short version of D. Patterson's biography; he also has a slightly longer version, illustrating that impressiveness can scale linearly.

I had the great pleasure to attend Patterson's talk at PARC a week ago on the view from Berkeley. I strongly encourage you to watch the video linked from the above page or look over the accompanying slides; in them the audience is treated to the old and new conventional wisdoms on processor design, an explanation of the sudden π-turn the industry has made regarding parallelism, and visions of a future with 1000's of processors (or cores, as some call them) on a single chip; this scenario (termed "many-core" by Patterson) is a far cry from the so-called "multi-core" chips emerging on the market right now.

This is good news for the computational science community; for one thing, it means that we're not going to run into the "brick wall" of power consumption, memory accessibility, and instruction-level parallelism, so scientific applications will continue their exponential march toward ever-greater computational power. For another, it means there's plenty of work to be done in adapting the fundamental algorithms behind the computational work that goes on these days.

And what does it mean for the general, non-scientific computer-using population? At first, it may seem that computers are fast enough, hard drives large enough, etc., for most of what anyone could ever need. However, all it takes is some ingenuity to put all that power to good use; another great example of this sort of imagination was already discussed. If you've ever edited photos, audio, or video, or waited an hour to extract the music from a CD, you've wanted the power that many-core processors may be able to deliver. When asked "How fast is fast enough?", L. Ellison said "In the blink of an eye." We clearly have a long way to go before the current generation of applications meet that standard; hopefully, many-core technology will carry us a long way along that road.

Get your hands on some games

One of the most common expository metaphors of discrete mathematics is "playing a game". Sometimes this is taken quite literally, as with the algebro-geometric algorithm jeu de taquin, the enumerative object named for an 8-bit Nintendo game, and the patience sorting algorithm, which American audiences might prefer to call the Klondike sorting algorithm. It shouldn't be surprising that some discrete games have been a rich source of interesting mathematical questions, and that a certain game with a long history still poses academic challenges.

And speaking of games, an excellent source of casual games is J. Bibby's site Jay is Games. I discussed one of their recommended games earlier, although I came across it independently of JiG.

In Planarity, I often have planarized a subset of the vertices and want to move them all at once. If only the interface would let me manipulate more than one vertex at a time! J. Han has put together a device implementing a multi-touch interface in his lab at the Courant Institute; in addition to running silly graph-theoretic games, it augurs what may very well be the next paradigm in human-computer interaction. In case the video on that page isn't enough to make you covet the tenth-generation iMac, take a look at this live demo. He mentions while illustrating the "puppet" application that cutting-edge mathematics and computational science make those dancing drawings possible. We are finally reaching the stage where the massive computational power sitting on the desktop can be harnessed to make computers behave in a way that is convenient to us, rather than the other way around. This is true innovation.

Bucking the trend

As the title of my dissertation indicates, I've done research on crystals. Most non-mathematicians think that crystals refer to three-dimensional polytopes with evident symmetries; I've had to tell many a suddenly eager listener that what they call polyhedra are not the topic of my work. There is a path between crystals and polytopes, but it makes a lengthy journey through Lie theory and algebraic geometry (sometimes with a tropical substition), which makes even my head spin.

One reason I suspect that so many educated people feels a certain comfort with 3-polytopes is their diagrammatic use in chemistry. I know I have a fondness for my days spent at a lab bench playing with wooden balls and springs, building crude models for carbon rings and water molecules; I'm sure I'm not the only one with this sentiment.

Geodesic domes are a famous family of polytopes, closely related to buckyballs, named for the man responsible for bringing these structures into the public eye. Not only are they good for housing humans, they can also deliver microscopic payloads when its vertices are atoms and its edges are bonds between them; its facets will be pentagons and hexagons, thanks to the chemical nature of carbon. Generally the pentagons in these nano-scale buckyballs (also called fullerenes) must not be adjacent, as is the case for your garden variety soccer ball. However, a team of chemists (including some at my alma mater) have found an ovoid counterexample.

It seems the motivating application is to get heavy molecules such as triterbium nitride to slip into the human body undetected by encasing them in a carbon cage; we therefore have discreet metals thanks to discrete geometry!

num·ber: a musical selection

A. Gelfand (any relation to I. Gelfand or S. Gelfand?) has written a pair of stories for Seed and Wired concerning R. Mahanthappa and his new cryptologically inspired album, Codebook. I highly recommend that you give it a listen; between Gelfand's articles, the label's site for the recording, and the artist's myspace page you can listen to most of the numbers on the CD.

I really appreciate his approach to mathematical composition. He describes his initial cipher of J. Coltrane's "Giant Steps" as "unplayable", specifically wishing to avoid "the appearance of random noise." Rather than leave the melody of "Frontburner" in its raw encrypted state, Mahanthappa "had to tweak his coded message until it could be classified as music."

Perhaps it's an overstatement to assert that it wasn't music before the "tweaks", but I'm sure that it's much better music on their account. It's refreshing to see serial elements used as a stimulus for creative expression rather than a programmatic straitjacket.

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.

Entropy always increases

And that goes for information too, of course. We all should be used to this phenomenon by now; whenever a scientific opinion or study is released, the press mangles it terribly, especially with its attention-grabbing, copy-selling headlines. It should come as no surprise that when a news source simply relays stories of interest to a niche group, there may be an additional loss of fidelity.

For example; there's a nice story on CNN reporting on a study from the Brown Center that shows a negative correlation between a nation's average math performance and its average enjoyment of and self-confidence in mathematics. And somehow, the esteemed editors have transformed this into a statement about people skills. (Update 11/6/2006: added link)

I would like to conclude, with overwhelming sarcasm, that slashdot editors have great confidence in and derive great pleasure from their ability to read a news story closely. But that wouldn't really be part of the solution, now would it?

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.

Simply irresistible

I hope no one at this conference chooses to speak about acyclic graphs; the audience might not see the forest for the trees.

Art, technically

Seed magazine interviewed Matmos, ostensibly about their use of an enigma machine in their forthcoming album, although their conversation turned more generally to their use of "scientific" sources in their music. Who knew that one of the fringe benefits of getting Ph.D. in English would turn out to be access to the vaults of a cryptography research company?

Matmos, as well as their more well-known collaborator, perform a truly amazing feat; they produce art that is positively brilliant and at the same time accessible. I suspect that this ability comes out of having impeccable technique and formidable instinct while having the ear steeped in popular musical culture.

Russian reveals result, refuses reward

The previously mentioned G. Perelman has surprised the world by insisting that he not be seen as a "figurehead".

But, hey, someone's got to win the prizes, and A. Okounkov, W. Werner and T. Tao seem happy to oblige.

Stacks!

Stacks are one of the most fundamental abstract data structures in computer science, providing most with their first exposure to dynamic memory allocation. And as E. LaForest explains, they can also serve in place of registers in a processor core, potentially with a dramatic performance benefit. I'm curious to see how far this technology can go; will we have stack-based handhelds in ten years? Will CS undergrads bemoan their Forth class as they now do of C++?

How many mathematicians does it take to prove the Poincaré conjecture?

Perhaps a better question would be "How many math-months does it take to prove it?"^* It's been three years since the Perelman program was announced, about 30 since Thurston's geometrization conjecture, and 102 since Poincaré first declared that the 3-sphere was unique among 3-manifolds for having trivial fundamental group; there were, of course, many more stops along the way. The answers to those questions are probably much larger than I would care to guess.

So, who's working on P vs NP?

*While the man-month is said to be mythical, I suspect the "mathematician-month" to be a realistic unit of measurement.

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.

High Performance

I now have an account on Jacquard for the purpose of parallel programming, which I'll be getting into later this summer. I would imagine it's not unlike sitting in the driver's seat of a Lotus.

Those who are concerned about how I might use all this power can rest easy; I've agreed not to use it to develop weapons of mass destruction, and I am forbidden from using it on behalf of citizens of certain countries.

These robes were made for walking

Note the bell-shaped sleeves and velvet; that's what sets us Doctors apart from the mere Masters, or (I'm loath even to say it) the Bachelors.


In all seriousness, it's great to have had the degree conferred upon me, even if my transcript still lacks the Regents' imprimatur.

Thanks to Andy for being there with his camera!

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

Cubicles have no doors

While I, unlike the heroes of this comic strip, am quite productive at my workplace, I am highly attuned to passersby. My back is to the entry-break in the carpeted wall, so my reactions are as follows:

1. When I do not have headphones on, I turn to look every time someone passes by;
2. When I have headphones on, I am startled by a tap on my shoulder by whoever needs my attention.

The first is less disruptive, but more frequent, so there is clearly an optimization problem buried here. In either case, it is clear why the principles of feng shui dictate that one should always have a clear view of the entrance to their space.

When does a hiatus become a leave of absence?

Abject apologies to those who would like to have read more frequent musings in this space. You have witnessed the effect of finishing a doctoral dissertation. After a decent run of at-least-weekly posts, I realized that I wasn't going to be able to keep it up during my home stretch. Having recently begun a transition to a new phase of my career, I expect to be able to devote an appropriate amount of time to this pursuit again.

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

The new generation of audio ransom note

Wired's music guy, E. Van Buskirk, interviewed S. König about his software project cum musical mash-up collage tool cum political statement on intellectual property, sCrAmBlEd?HaCkZ!. It's not only an interesting idea, but there are also numerous computational challenges to making it work, and work so well. I want to know how he does all that! I suppose I'll find out when it gets sourceforged.

Freed from economic and social constraints, I would volunteer to work on this without a second thought.

Limited options precipitate creativity

All mathematicians (and many others) immediately recognize the sequence 1, 1, 2, 3, 5, 8 as the first few Fibonacci numbers. In this article, G. K. Pincus proposes a new poetic form, the fib, whose line lengths (measured in syllables) are given by these numbers.

At first, I suspected that most such verses would simply be twenty syllables of English prose broken up to fit the "design parameters". After all, history is full of awkward attempts to use mathematical toys such as the Fibonacci senquence as a basis for art. However, after reading some contributions from the comments to the original post, as well as those featured in a follow-up article, I've found that this form has a real character to it. The first four lines are short and punchy, almost primal; the last two lines seem locquacious by comparison, allowing an outpour of articulate expression. It seems that Pincus struck that delicate balance of constraint; both sufficient to focus creative drive while relaxed enough to prevent the output from being artificial and bland.

Good?
Bad?
Great? Poor?
I'm no judge
Of this kind of thing,
But I know I like what I see.

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.

But what about $K_5$ and $K_3,3$?

As a dear friend once told me, everyone should take time to play games. Here's one that I think my reader(s) will enjoy. In fact, I think (t)he(y) may have already. I'd really love to see it played on a 2-torus.

Human Experience Engineering

Last December C. Wetherell, a Google software engineer, told me that his next twenty-percent project would be an algorithm for love. It seems to have entered beta.

Complimentarily, Red Robot of Diesel Sweeties has been honing an algorithm for hate. While I would not take on such a research program myself, I commend him for this endeavor, as it progresses our overall understanding of emotional algorithms. Perhaps Google should recruit Red Robot to be their new Director of Human Experience Engineering.

Perhaps a more practical approach would be for Google to acquire an anti-social networking site, such as Snubster, or perhaps adapt Orkut to this end.

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.

Mathematics reaps the benefits of physical insight

A few days ago, slashdot linked to this essay by M. du Sautoy in Seed on the relationship between the Riemann Hypothesis and quantum physics. I've been consistently impressed by Seed's provision of scientific reporting that neither glosses over significant concepts nor drowns the non-specialist in technical details. I think it answers the scientist's perpetual complaint against journalists' relationship with science, as summarized by this recent opinion piece in the Notices of the AMS. Now, if only more media outlets would follow Seed's excellent example.

On a tenuously related note; the author's website is by far the most elaborate I've ever seen among academics. It's refreshing to see such an open rejection of the reverse snobbery so common among our ilk.

A formula for misery

R. Stevens does it again; this time, he illustrates why Math is Life.

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.

No opportunity for subtle wordplay

The fourth Abel prize has been awarded to L. Carleson of the Royal Institute of Technology, Sweden "for his profound and seminal contributions to harmonic analysis and the theory of smooth dynamical systems." The Slashdot story mentions that "[h]is theorems have been helpful in creating [the] iPod," and includes a decent layman's explanation of Prof. Carleson's contributions to analysis. Essentially, he proved that using Fourier series to encode functions is theoretically sound, and not just "effective in practice."

I name my Apple products after mathematicians; my iPod shuffle is Diaconis, my Airport Express is Heddy (after H. Lamar), and my iPod (with video), after careful consideration, was christened Fourier, owing to its algorithmic dependence on Fourier series. Perhaps Carleson would have been a better choice. Well, there will probably be an iPod in need of a name in the future.

Watershed

The project I mentioned in some previous posts is now on the arXiv.

On the local structure of doubly laced crystals
P. Sternberg

It's good to have publicly visible work.

Non, c'est pas une Weezer logo

As part of a run of strips on superheroes, R. Stevens produced a comic in which a character points out that "... Justice League is not a reputable science journal." Buzzwords from mathematical physics puncuate the retort that follows.

I know what the golden "W" in the comic's header stands for, but I can't help but wish it was meant to recognize E. Witten as the strongest driving force in string theory.

Many scientifically concerned individuals bemoan the lack of public interest in science and mathematics. Perhaps what we need is better personal brand management, beginning with a broad campaign of brand identification.

Here, I'll start.

What's a five-letter word for "Surfaces of genus zero with three boundary cycles"?

Any situation can be made humorous (or more so, if it's already funny) by the addition or subtraction of pants or monkeys. At least, so said a dear friend of mine several years ago. I'm inclined to believe him.

As far as I know, there is no mathematical object known as a monkey; until last night, I thought the same was true of pants. As this nomenclature is due to W. Thurston, it has been suggested that they should be called Thurstonian pant-pairs.

A colleague of mine has written a paper on the subject.

Heegaard Splittings and the Pants Complex
J. Johnson

A nice round number

If you write dates with the month before the day, today is 3/14, or more affectionately, π day. Those who are especially meticulous celebrate at a moment about half a minute past 1:59. Yesterday, the Independent ran an article celebrating the wonderful properties and history of this number. Unfortunately, the following sentence appeared near the end of the story:

Pi, you see, is always going to be represented by an approximation because, like all irrational numbers, its digits never really end.

This is perfectly acceptable for a pre-calculus audience, but anyone who has been exposed to infinite sums deserves to see some of the miraculous closed-form expressions for π, such as the following, famously due to Ramanujan.

Happy π day!

Physics and Sociology, helping each other

The history of Mathematical Physics includes many examples of both of its constituent disciplines providing insight to the other. The mathematical tools of differential equations, linear algebra, and manifolds have allowed for precise descriptions of physical models; at the same time, formulas such as the Riemann-Roch Theorem and the ongoing X=M Conjecture could never have been discovered without deep physical insight.

In this article (which I found by way of Slashdot) we see an example of Physics informing the study of social networks. The authors point out that Physics is, in some sense, just returning the favor Sociology lent it about 100 years ago by inspiring the use of probabilistic models for gases, rather than relying on determinism.

Personally, I want to know if a mechanistic relationship exists between statistical particle models and large groups of people. Sadly, such a connection is missing from the current stage of this research; not surprising, since it is still so new. Once that bridge is built, however, a new paradigm for complex systems will likely emerge. There's no telling what we might be able to do then.

Look, biological imaging is actually useful

A group led by David Shapiro of SUNY Stony Brook has developed a new algorithm for image reconstruction from X-ray diffraction microscopy. And as has been reported on Cornell's news site, it is easily adapted to quickly solve sudoku puzzles.

So, will a sizable number of young Americans realize that combinatorialists solve puzzles like sudoku, and decide that they want to pursue discrete math as a major, or even a career?

For future reference

It's always a joy (if a slightly vain one) to see one's work cited, as in this paper which makes an important step in the program to understand the representation theory of quantum affine algebras:

Paths and tableaux descriptions of Jacobi-Trudi determinant associated with quantum affine algebra of type D_n
W. Nakai, T. Nakanishi

I've received a few citations before, but the sense of recognition that comes from seeing my name on the page is still strong. According to researchers who are considerably my senior, this feeling is very slow to fade.

It reminds me of a point of advice made by Gian-Carlo Rota at a 1996 conference in his honor:

8 Give lavish acknowledgments

I have always felt miffed after reading a paper in which I felt I was not being given proper credit, and it is safe to conjecture that the same happens to everyone else. One day, I tried an experiment. After writing a rather long paper, I began to draft a thorough bibliography. On the spur of the moment, I decided to cite a few papers which had nothing whatsoever to do with the content of my paper, to see what might happen.

Somewhat to my surprise, I received letters from two of the authors whose papers I believed were irrelevant to my article. Both letters were written in an emotionally charged tone. Each of the authors warmly congratulated me for being the first to acknowledge their contribution to the field.

One may conclude that the marginal cost of liberal citation is overwhelmed by the potential for improved collegiality.

We don't need no (constructivist) education!

In the world of mathematical research, the word "constructivism" refers to a debate addressing the existence of objects that cannot be explicitly constructed. If such assumptions are disallowed, some aspects of the infinite become very difficult to deal with. However, in the field of mathematics education (which is simultaneously close to and distant from mathematical research), constructivism instead applies to an approach to learning based on individual experience.

For a little more than a decade, so-called Math Wars have raged across the country. Textbooks and curricula advocating an exclusively constructivist approach to mathematics have been adopted by many boards of education both on the state and local levels. A very insightful comparison between a constructivist and a deductionist approach to the Pythagorean Theorem was written by G. D. Chakerian and K. Kreith of the UC Davis Department of Mathematics when the Math Wars reached the secondary schools of Davis.

What I find saddest about this situation is that Mathematics education does benefit from taking constructivism into account. The best teachers from whom I've ever had the pleasure to learn made excellent use of examples to be worked out by the student, often when only a partial understanding of the mathematical theory had been presented. However, these instructors made absolutely certain to declare clearly to the students the general principles governing the behavior of these examples. Examples present students with data; theorems provide a framework for making sense of these data. Without teaching students the theorems that control the behavior of the numbers that surround us, we tell them either that a few examples suffice to determine general behavior, or that every situation is a special case and general principles cannot inform our understanding. I'm not sure which is a more dangerous lesson to learn.

A matter of preference

From Incomplete Preferences to Ranking via Optimization
P. Chebotarev, E. Shamis

This fascinating problem deals with how to determine a full ranking of a finite list of candidates given only partial preference data. For instance, if I prefer cola to coffee and green tea to black tea, and you prefer coffee to black tea, the following are compatible rankings for these preference data:

1. cola
2. coffee
3. green tea
4. black tea

and

1. cola
2. coffee
3. black tea
4. green tea

In this simple example there are two possible rankings; but in real-world situations, there are often none. How can one use a ranking to best approximate sets of incomplete prefence data, given that there will probably be no single ranking consistent with all preferences? I (and many others) would really like to know.

Wrapped in a riddle

Slashdot has reported on a project to decode three original Enigma messages intercepted in 1942. The method employed is, of course, brute force distributed computing, combined with statistical methods and some clever optimization tricks.

I had thought that the Enigma had been completely unraveled; as it turns out, even with today's computers, very sophisticated computational tools are required to answer some of its questions.

Revisionism

The first draft of the first paragraph of the paper I've been writing needed a little more depth, so I added a few clauses and then cleaned up the grammar. Once it was printed out and in black and white, though, I saw that the new version was horribly written; repeated words, confusing syntax, and who knows what other barriers to readability. Less can be more, and still not be enough.

Asymptotically approaching truth

Over the past month, I've been writing a paper based on some results that I completed last October. At least, I thought I had completed them. As I type, there are more and more subtle details that I realize I need to consider. What I thought would have been a ten-page note, including an introduction and technical padding, has grown to be twice that length, and I haven't even started adding examples. I really am close to putting it on the arXiv, I swear...

Return to roots

A curious identity and the volume of the root spherical simplex
C. De Concini, C. Procesi

Take a maximal parabolic subgroup of an affine Weyl group. Take the product of its exponents, and divide by the product of its degrees. Now, sum that over all maximal parabolic subgroups; you get 1. Now that's an elegant equation.

And further, acconding to E. Vinberg, this also tells us about the ratio of the volumes of the Weyl chamber and its intersection with the unit sphere. I'm excited to see where this goes.

Fusion coefficients

Fusion products of Kirillov-Reshetikhin modules and fermionic multiplicity formulas
E. Ardonne, R. Kedem

The second author is my "academic aunt", having been advised by B. McCoy.

I love combinatorics in mathematical physics.

Fossil fuel lovers

Diesel Sweeties by R. Stevens has featured math humor on two occasions. I hope Stevens includes such gags again.

In 2006 we use the technology of 1958 to recreate the technology of 1849

A. Carol has built a difference engine No. 2 from LEGO.* Not only does this evoke fond childhood memories of building trucks and castles, but it also calls me to consider the role of mechanically assisted computation in mathematics.

The difference engine sits at a fascinating point in the history of the relationship between mathematicians and machines. Because the mechanism by which its atomic components produce its output can be seen, and even touched, the user can maintain intimate contact with the algorithm as it progresses. Compare this to the simplest of modern calculators, or the first vacuum tube computers; their processes are invisible, necessarily rendering them "black boxes", even to their creators. A tremendous leap of faith is required to accept their output as valid. Because the difference engine is what an educator might call a "manipulative", no such leap is needed.

However, I would never trade my computational tools for C. Babbage's technology. The importance of computational mathematics both with an eye to applications and as a means of generating examples, as well as methods of computer-assisted proof (as used for the four-color theorem or the work of S. B. Echad), cannot be understated. Of course, this doesn't even include the immeasurable societal benefit of computational technology that has proceeded in parallel with these advances in the mathematical arts and sciences.

But still, there's that irreplaceable satisfaction that comes from seeing an algorithm happen. As it is, I can only achieve this from examples worked out by hand.

*The plural of LEGO is in fact LEGO.

On the lighter side

A New Upper Bound on Rubik's Cube Group
Silviu Radu

The Rubik Cube has had more success inhabiting pop consciousness than any other big discrete object. I never got really good at it myself; I could solve one side perfectly well, but that's no big achievement. I suppose my ability to hold parallel data in my head has improved in the past 15 years, but I doubt that would be the best use of my time and mental energy. It truly is a mathematical gift that keeps on giving.

From the arXiv

Crystal interpretation of Kerov-Kirillov-Reshetikhin bijection
A. Kuniba, M. Okado, R. Sakamoto, T. Takagi, Y. Yamada

This paper elucidates the relationship between rigged configurations and Young tableaux. Being able to pass back and forth between them is essential to the application of my first result.


Alcove walks, Hecke algebras, spherical functions, crystals and column strict tableaux
A. Ram

Includes an introduction to crystals and some of the latest exciting generalizations and applications of them.

Just apply yourself!

I'm very fortunate to be in a math department where little to no distinction is made between pure and applied mathematics. In D. Zeilberger's opinion, one who sees such a distinction as impacting the value of their work deserves a rather harsh qualitative evaluation as a mathematician.

Consider the areas of computer science, theoretical physics, and theoretical ecology. Most of the questions addressed by researchers in these fields would be right at home in "pure" math journals; they simply are viewed within the context of other intellectual concerns, and (in the best cases) the research is guided by insights arising from the greater context.

For example; computer science research consists (in part) of questions in probability, combinatorics, logic, complexity, statistics. Mathematical physics involves itself with differential geometry, differential equations, representation theory, and homological algebra. Theoretical ecology is essentially the study of complex systems; historically the only mathematical method for studying such objects was differential equations, but more recently cellular automata, both probabalistic and deterministic, have been used to describe such systems in potentially mathematically tractable terms.*

In all of these cases, the application only enhances the value of the mathematics. Does it really hurt algebraic geometry (or algebraic geometers) to use varieties in the pursuit of genetic alignment? If it does, I'd love to hear precisely how.

If you do "pure" math, get off your high horse. It doesn't make you better than anyone else, in any sense of the word.

*Omissions of mathematical topics are due to my own ignorance; please bring others that deserve mention to my attention.

It's a pun, not a spelling error

So, the natural (albeit somewhat narcissistic) thing to do once you start a blog is to do a blog search for the name, right? And what do I find, but a whole lot of individuals who don't know the difference between "discrete" and "discreet".

This leads to two unpleasant situations:

• A reader who doesn't know the difference sees this blog, reinforcing their error (and not seeing the humor in the name);
  
• A reader who does know the difference sees this blog and assumes that I don't know the difference.

Seriously, learn the language and don't rely on spell-check to clean up your act.

Let $n\in\mathbb{Z}_{\geq 0}$.

This is a repository for my thoughts, observations, and reactions to goings-on in the world of mathematics. If you notice a slant towards discrete math/combinatorics, it's because that's the kind of math I do.

If you can't understand the title of this post, you really should learn TeX.