I often use a computer to create graphics, but there was a time when I used graphics to compute. That era came back to me the other day in the library. I was browsing among dusty volumes in the folio section when I came upon this:

The Design of Diagrams
for Engineering Formulas
and
The Theory of Nomography

by

Laurence I. Hewes, B. Sc., Ph. D.
and
Herbert L. Seward, Ph. B., M. E.

McGraw-Hill Book Company, Inc.
1923

The clerk at the circulation desk observed that there was no record anyone had ever borrowed this book. Although the records don’t go all the way back to 1923, I wouldn’t be surprised if I’m the first reader of this volume in 30 or 40 years.

It’s a book full of nomograms and similar graphic devices, with instructions on how to create them. Here’s a simple example for calculating the volume of a torus:

If you know any two of d, V and D, you can find the third quantity by laying a straightedge across the scales. (Quick quiz: What’s that constant in the formula V = 2.4674d²D?)

I used to see computational aids like this all the time. Some magazine I read in the seventies (I’m not sure which one—maybe Electronics?) published a new nomogram every month. But now such diagrams have a decidedly fusty look. They’re like tools you might find in an old blacksmith shop or a tannery; it’s a challenge just to figure out how they worked and what they were used for. You find yourself admiring the workers who created useful products with such implements.

The graphic device below is for calculating the strength of a metal plate pierced by rivet holes:

Did the engineers who specified the half-inch gusset plates for certain joints on the I-35W bridge in Minneapolis rely on such aids? The preliminary report from the National Transportation Safety Board (.pdf) doesn’t comment on the computational methods that might have been used when the bridge was designed in the early 1960s. In any case, it’s not at all obvious which is more error-prone—pencil and paper, slide rule, nomogram, CAD software.

The Theory of Nomography—as Hewes and Seward term their art—could hardly be more distant from modern computing practice. For one thing, it converts arithmetic into geometry; nowadays, we’re more likely to go the opposite way. A nomogram also emphasizes a static, declarative style of representing knowledge: A single diagram embodies all the relations of several variables, and one method solves for any unknown. Most digital computing is procedural rather than declarative; the emphasis is on step-by-step algorithms to go from givens to answers.

I’m not about to give up silicon in favor of paper computers, but I do find some of these diagrams both beautiful and illuminating. Here’s a nomogram for solving the quadratic equation z²+pz+q=0:

Instead of three straight-line scales, as in the formula for the volume of a torus, we have two linear scales and a hyperbola. A moment’s thought reveals why the diagram must have this form: For any combination of the coefficients p and q, the equation must have either two roots or no (real) root. One branch of the hyperbola carries all the positive roots and the other all the negative values of z. Poking around in the diagram brings various properties of the equation into sharp focus. For example, if you lay a straightedge across the diagram in such a way that it passes through the point p=0, then it will either cut the two branches of the hyperbola symmetrically (if q is negative) or it will miss both branches (if q is positive). This is no surprise—the roots of z²+q=0 had better be plus and minus the square root of q—but the graphic presentation carries a lot of explanatory force.

Hewes and Seward give an even more elaborate tableau for solving a cubic equation:

The dashed line drawn across this diagram represents a straightedge placed so as to solve the particular instance z³+4z²-4z+0.5=0. The straightedge is set to the points 4 and –4 on the left and right scales, and then the roots are read off by projecting vertically from the intersections of this line with the curve labeled 0.50. Working by eye, the roots appear to lie at about 0.15 and 0.7. Newton’s method—the archetype of iterative, step-by-step computations—gives 0.14758497342482376768480 and 0.69902089681305967783231. (On the SAGE server at the University of Washington, finding each of those roots took a couple of hundredths of a second.)

Note: Ask Dr. Math has an informative article on nomograms (or nomographs) with lots of references. One of the references led me to a 1999 lecture by Thomas Hankins, published in Isis (Hankins, Thomas L. 1999. Blood, dirt, and nomograms: A particular history of graphs. Isis 90(1):50–80). Hankins traces the origin and early history of the nomogram, which I had never known. Both the name and the concept came from Maurice d’Ocagne of the École des Ponts et Chaussées in Paris toward the end of the 19th century. Their first uses were in calculations needed for railroad construction.

Update 2008-03-05: Ron Doerfler, in a blog called Dead Reckonings, has several illuminating and thorough essays on the construction of nomographs, including a very fishy example laid out on an elliptic curve. The rest of the blog is also worth reading. Thanks to Mitch Burrill for the pointer.

My friends up north tell me they have quite enough snowflakes already, thank you. Nevertheless, Janko Gravner and David Griffeath are making more. Or, rather, they’re making snowfakes (the word is theirs, not mine):

In case there’s any doubt, the image above is not a photograph of a real snowflake; it’s an incredible simulation.

Mathematical and computational models of snowflakes have a long history, perhaps going back to the snowflake curve of Helge von Koch. I say “perhaps” because Koch, a Swede, seems not to have been much interested in snow; his 1904 paper on the subject was all about nowhere-differentiable everywhere-continuous curves. By the 1970s and 80s, however, there was a serious search for simple rules that would give rise to realistic snowflake patterns.

In a series of three long and detailed papers, all written over the course of little more than a year, Gravner and Griffeath recapitulate the entire history of this effort, and then they advance the state of the art. They begin with cellular automata, especially a model first discussed in 1984 by Norman H. Packard. They go on to two-dimensional models based on the idea of diffusion-limited aggregation (which is also the process that generated the banner atop the bit-player.org page). Finally they develop the three-dimensional model that produced the image above. They write:

The key features of our model are diffusion of vapor, anisotropic attachment of water molecules, and a narrow semi-liquid layer at the boundary. All three ingredients seems to be essential for faithful emulation of the morphology observed in nature.

All three papers and much more (movies, a slide show, even source code if you want your own snowfaking machine) are available at the Snowfake site. The first of the papers has also been published in Experimental Mathematics.

How much can these artificial snowflakes tell us about the formation of real ones? In modeling there always seems to be an interesting tension between simplicity and realism. Choose too crude an approximation and you never make contact with the real world; but a model that’s too complicated can be as hard to understand as nature itself. In this case, though, all three of the Gravner-Griffeath approaches seem to have something to teach us. Even the most abstract model, the cellular automaton, offers a hint of where those feathery patterns come from: an essential element of the automaton rules is that cells become active only if some but not all of their neighbors are active, favoring the growth of a structure that’s connected but not solid. The diffusion-limited aggregation models derive from a similar underlying principle but add a lot more physics, since the simulated water molecules can move through space. The 3D models include still more details and simulate the crystal-growth process in a way that begins to illuminate physical concepts such as the phase diagram.

For those who insist on real snowflakes, there’s the impressive work of Kenneth G. Libbrecht on exhibit at snowccrystals.com. (Don’t be put off by the sales pitch for the Snowflake Store; there’s good physics here.) Libbrecht has also written on snowflakes for my own magazine, American Scientist, but I’m not going to include a link because, sadly, the article is being held for ransom behind a paywall.

From the listener’s point of view, the utility curve for mathematics talks seems to look something like the plot at right. If you already know everything about a subject before you walk into the room, you’re not likely to learn much. At the opposite extreme, if your prior knowledge is absolutely zero, it’s again all too likely that you’ll remain just as ignorant afterwards as you were before. The existence of a peak between these zeroes is my optimistic hypothesis. (The nonexistence of regions where the function dips into negative territory is also asserted on faith, although I’m less sure about this. Over the years there have been a few talks where I felt I knew less at the end than at the beginning.)

I’ve had little experience with the know-it-all end of the curve, but I could give a fairly detailed account of what life is like near the ignoramibus end. In the past four days I’ve wandered into a a number of talks from which I was not equipped to profit—but there’s not much point in my discussing those. The paragraphs that follow are brief and hasty notes on some of the talks that taught me something.

Diffusion of knowledge

Steve Smale was one of the organizers of a session titled “The Mathematics of Information and Knowledge.” I went to Smale’s own talk in the session partly because it’s always worthwhile finding out what Smale has on his mind, but also because I was puzzled by that opaque and generic title. It might describe almost anything.

What Smale wanted to talk about was recent work on learning and vision, done in collaboration with Tomaso Poggio of MIT. Smale alluded to Noam Chomsky’s observations about “poverty of stimulus”: a child needs to see an elephant only once or twice to be able to recognize elephants forever after. Computational learning algorithms come nowhere near this level of efficiency; if you want a computer program to recognize elephants, you’ll need to show it many examples.

In their study of recognition algorithms, Smale and Poggio have chosen to work with simple grayscale images, which require less care and feeding than elephants. Their aim is to create a distance function that will measure the similarity of any two images, classifying them in much the way the human visual system does. For example, an image of a cat should be closer to another image of a cat than it is to an image of a dog. The ordinary Euclidean distance function is not much help here. If images have a million pixels, then each possible image is represented by a point in a million-dimensional space. The Euclidean distance between two such points doesn’t tell us much about cats and dogs; besides, there’s so much elbow room in a high-dimensional space that “closeness” doesn’t mean much. Some kind of drastic dimensional reduction is needed.

Image recognition algorithms have a long history, and techniques of dimensional reduction are a longstanding problem in statistics. What’s new here? Unfortunately, this is where I begin to slide down to the wrong end of the knowledge curve. What I’ve been able to piece together (both from Smale’s talk and from an earlier talk by Peter W. Jones of Yale) is that the key is to transform the problem into a new space that comes equipped with a new coordinate system and a new distance metric. The metric tries to measure distance based entirely on “local” information. Conventional similarity measures serve to determine which of the images are near neighbors, but then other methods define longer-range relations.

One such metric, called diffusion geometry, measures distance in terms of a random walk. In a database of images, for example, the distance between two images is the expected number of steps needed to get from one image to the other, taking each step by choosing a nearest neighbor at random. A benefit of this scheme is that it respects the structure of any clusters present in the population. Two images are close if there is one short path between them, but also if there are many long paths.

Techniques like these can be applied not only to image recognition but also to text mining, bioinformatics, internet search engines and doubtless other fields. Indeed, another aspect of the story came out in Fan Chung’s talk on the PageRank algorithm that search engines employ to match queries against web pages. It had never occurred to me that searching the web for the word “elephant” is so much like the process that goes on inside my head when I see and recognize an elephant. Perhaps this is what was so brilliant about the invention of Google: the search engine doesn’t really search (in the sense of sequentially considering all the possibilities); it recognizes.

Zeta functions of graphs

No sense pretending: I didn’t even know that graphs have zeta functions. I guess the celebrity of Riemann’s zeta function in number theory is so great that it has overshadowed other members of the family—at least for me. The Riemann zeta function involves a product of powers of all the prime numbers, but this is a concept that can be extended to other realms. In graphs, the analog of a prime number is a path that satisfies certain criteria: It must be “closed, backtrackless, tailless and primitive.” The graph-theory zeta function is defined in terms of these prime paths.

In number theory, the zeta function has a special place because it tells us something about the distribution of primes among the natural numbers. In particular, there’s a connection between the distribution of the primes and the positions of the zeroes of the zeta function (this is the Riemann Hypothesis). There’s a similar hypothesis in graph theory, although it concerns the “poles” rather than the zeroes of the zeta function. (A pole is a place where the function becomes infinite or undefined.) There may even be practical consequences of all this: The distribution of the poles affects the abundance of a special family of graphs called Ramanujan graphs, which have applications in computing and communication.

Audrey Terras and Wen-Ching Winnie Li both gave major talks on zeta functions of graphs. In addition, there were other sessions devoted to Ramanujan graphs and related topics.

Percolation

On this subject I thought I was at least near the middle of the knowledge curve, but I learned that I still have lots to learn.

The mathematical version of percolation has a connection to what happens in coffee pots and septic tanks, but it’s a pretty distant and abstract connection. The process happens on a lattice of some kind, such as a grid or a honeycomb. You color the nodes of the lattice black or white at random and then ask whether there’s a continuous path of one color that extends all the way across the lattice. In a four-sided lattice, if there’s a black path that extends all the way from the left edge to the right edge, then there can’t be a white path from top to bottom.

Percolation was a lively topic in the 1970s. (I’m fond of the problem in part because one of my own early experiments, when I first got my hands on a computer, was building a Lotus 1-2-3 spreadsheet to simulate percolation.) But I had thought that all the interesting questions had been settled by the early 1980s, especially in the work of Harry Kesten. Evidently not.

Wendelin Werner, the recent Fields medalist, gave the series of three Colloquium Lectures this year, and percolation was a major topic within his presentation. Greg Lawler, in a Current Events talk, also touched on the subject. On the final day of the meeting I heard another hour-long discussion of percolation by Gabor Pete.

The new twist that seems to have attracted this attention is the question of whether solutions to percolation problems are stable in the presence of noise or uncertainty. For example, if a lattice configuration has a percolating black path, what’s the probability that changing the color of a single site will destroy the path? It’s not hard to get approximate or experimental answers to questions like these—you might be able to do it with a spreadsheet—but the work reported here in San Diego is on the trail of exact and rigorous results.

The patron saint of hopeless problems

Jeffrey Lagarias has devoted no end of thought, labor and scholarship to problems that he acknowledges are “hopeless.” The best-known example is the 3X+1 problem: Iterate the map X → X/2 if X is even, X → (3X+1)/2 if X is odd, and determine whether the process always reaches the same terminal loop. In San Diego Lagarias spoke on another hopeless problem: “Basic ternary digit sets and associated tiles.” Given a set of digits, can you represent all real numbers by concatenating those digits? For standard digit sets such as {0,1} or {0,1,2} or{0,1,2,3,4,5,6,7,8,9}, the answer is yes. The set {–1,0,1}, known as balanced ternary, also works: It is said to be a “basic” digit set. But what about {0,1,π}? For this trio of digits, it can’t be done: No matter how you arrange the digits, there will be gaps on the number line that you cannot fill. The problem is deciding which digit sets are basic. Trying ternary representations of the form {0, 1 –q} yields a peculiar list of values of q for which the set is not basic. Trying to discover a formula that would generate that list of q’s is now on the Lagarias list of hopeless problems.

Ringing up primes

This comes from a very diverting lecture by Brian Conrey on the Riemann hypothesis:

“The probability that an N-digit number is prime is approximately 1/(2.3N). For example, given a seven-digit telephone number, the probability is about 1/16. So, let’s try the experiment: How many of you have a prime phone number? (If only I were a little quicker at mental primality testing—gotta practice that Pollard rho algorithm—I could have raised my hand.)

The best of all possible lectures

Judith Grabiner spoke on the history of the idea of optimization in mathematics. Her story began with Heron of Alexandria, who explain the optical principle that the angle of incidence equals the angle of reflection by showing that this geometry yields the shortest path. Later, Fermat gave a subtly different rule for the law of refraction: The optimum path is the one that minimizes time rather than distance. Maupertuis then subsumed both of these ideas under the principle of least action. I have always found these laws of nature mildly mysterious. It’s not that I doubt their truth or applicability; my problem is that I don’t see why nature should “want” to minimize distance or time or action. Nature has all the time and space in the world—Where’s the need to be stingy with these resources.

Grabiner gave a thought-provoking review of the philosophical and theological background to these optimization principles. In this context it’s not hard to see a link between Leibniz’s work in the calculus and his optimistic philosophy, epitomized and satirized in the slogan “All is for the best in this best of all possible worlds.” In the world according to Leibniz, “God is the great optimizer,” and we should expect to find that the laws of nature are as simple as possible. Newton had a quite different but equally theological basis for his belief that the universe is ideally suited to human habitation. The question I’m left with, then, is how to account for the prevalence of optimization principles in the absence of such theistic underpinnings.

Sophie Germaine’s mathematical oeuvre

For me, this talk by David Pengelley was the big surprise of the meeting. Sophie Germain is perhaps the most famous of women mathematicians before the 20th century. But not one line of her own mathematical writing had been known; our only primary source was a footnote in a paper by Legendre. But now two great troves of letters and manuscripts have been uncovered in Paris and Florence, and suddenly we know that Germain was far more accomplished and ambitious than anyone had guessed. She had a full plan for proving Fermat’s Last Theorem; although it couldn’t have succeeded, it was a masterful attempt. As this story unfolds over the next few years—hopefully with publication of the papers—it’s going to be fascinating.

There’s lots more that’s worthy of mention, but it’s Thursday, the meeting is over, I’m at the airport in San Diego on my way home, and I’m exhausted. Happily, I can point out that I’m not the only one blogging this meeting. In particular, Adriana Salerno has been writing for the American Mathematical Society. (There’s a link on the AMS web site, but it’s well hidden; go here.)

There’s a lot of mathematics going on here in San Diego, and I’m taking notes. But for now, what I have to offer is a bucket of pixels:

It’s hard to get excited about the architecture of convention centers. They’re like airports: You’re pleasantly surprised if they’re merely functional. In many respects the San Diego convention center is no better than any other. It squats on an enormous tract of bayside property, cutting off a downtown neighborhood from the waterfront. But one tent-like wing (above) has genuine visual interest. (As the trash cans and “Wet Floor” signs at right indicate, it also seems to have a leaky roof.) The adjacent stairway (below) offers the public (arduous) access to the waterfront. No one seems to be using it, but it does make a rather handsome abstraction.

Much as we despise airports, we all love railroad terminals. Below is a bit of the old Santa Fe Depot, still in use by Amtrak. It is seen from (and reflected in) the trolley terminal next door.

I often gripe about a meeting schedule that has talks starting at 7:45. On the other hand, that agenda gets you out and about in time to see aspects of city life you might otherwise miss.

San Diego has some of the most distinctive street plumbing in the country (below). Note the Dalek fire hydrant. The chromed pipe in the foreground is labeled “suction connection.” Like the hydrant, it’s for use in firefighting, but whereas the hydrant supplies water under pressure, the suction connection merely provides access to a water reservoir and needs a pumper truck to supply pressure.

Of course that silvery cylinder (bent into a segment of a torus) is an irresistible target for experiments in projective geometry.

In the exhibit hall (below), legendary hacker hunter and astronomer Cliff Stoll is hawking the Acme Klein Bottle. The sales pitch is a high-energy performance that hasn’t been equalled since the glory days of the Vegematic.

More to come.

The fellow across the aisle is a stranger to me, but I know we share a destination. He’s scanning the index of the meeting program, presumably looking for friends or colleagues delivering a paper. When I unfold myself from seat 22D and stroll toward the back of the plane, I spot a few more of us. Someone is working on foils in LaTeX. Someone else is doodling on squared paper, making lots of little stairstep diagrams—they could be Young tableaux or they could be some kind of self-avoiding walks. The group of three college kids playing cards in row 32 might be on their way to a football game, but when I overhear a snippet of conversation that includes the phrase “convex hull,” I conclude they are not just Chargers fans.

It’s time again for the Joint Mathematics Meeting, held this year in sunny San Diego—which is actually quite soggy at the moment. (In front of my hotel this morning I found a manhole cover that had floated free of its foundation sometime during last night’s downpour.)

We’ll muddle through (and try not to fall in). Sometime over the next few days, maybe I’ll even learn what all those little stairstep diagrams were all about.