Post
1 year ago

## What is a Manhattan Metric?

At this point, I think it is safe to say that computers are not just some passing fad.

Computers have become an indispensable tool for many people and an integral part of a number of different industries. If we expand our definition of computers to include all electronics that contain an integrated logic circuit, then something like 70% of all humans on the earth interact with computers on a daily basis (based on the number of mobile phones in use alone). Indeed, it is almost assured that the amount of computer technology in use on the planet Earth will only increase.

As revolutionary as this rapid spread of technology might seem, I do not think the number of devices in use is the real “computer revolution”. Computers and computation represent more than just a revolution in the way we accomplish everyday tasks. They represent a fundamental revolution in thought; a revolution as significant as those brought on by Newton’s Laws of Motion, Darwin’s Theory of Evolution, and Einstein’s Theories of Special and General Relativity.

That might seem like a fairly lofty claim, but I’m sticking to it. To understand why, I’d like to talk a bit about metrics…

## What is a metric?

A metric is, essentially, a fancy way for mathematicians to say “how to get from here to there”. More formally, a metric represents a way to measure distances. You probably learned your first metric in grade school without even knowing it. The Pythagorean theorem that we’re all familiar with, gives us a convenient way to measure distances in a plane: $$\sqrt{dx^2 + dy^2} = distance$$. This “square-root of the sum of squares” method, known as the Euclidean metric, can also be used to calculate distances in 3D space.

To be perfectly honest, the Euclidean metric is pretty boring stuff. Sure, there are plenty of practical applications for it, but unless you’re an ancient Greek this isn’t exactly going to cause a revolution in thought. For that, you have to fast forward all the way from Pythagoras and Euclid to the year 1905. This was the annus mirabilis of Albert Einstein, during which he published his paper on the Special Theory of Relativity. If you’ve studied Special Relativity at all, you’ll know that one of its consequences is that as you go faster, distances get shorter.

No, distances don’t appear shorter as you go faster. They are shorter, any way you measure it. Quite literally, your speed through the universe warps space. Since Special Relativity deals with the way we measure distances, this phenomenon is quite nicely described by a metric: the Lorentz metric. A number of years later, Einstein would take advantage of yet another metric, the Riemann metric, to formulate his General Theory of Relativity. With it, he related the way we measure distances not only to the speed we are traveling, but also to the mass and energy of objects around us. Gravity is just an alteration to the distances in space and time.

## Are we there yet?

So what does any of this have to do with Manhattan? Well, as much as we can do with all these other metrics, the one thing we can’t do is answer the question: “How far is it from Columbus Circle to the Javits Center?” That’s because midtown Manhattan’s streets are laid out in a grid fashion, and the “shortest route” according to Euclid would require the ability to walk through several city blocks worth of buildings.

Instead, we have to consider how many streets and how many avenues we would need to traverse. Mathematically speaking, we can consider Manhattan a graph, with each intersection representing a “node” and every street representing an “edge”. In order to calculate the distance between any two “nodes”, we have to walk the “edges”. This idea, this way of calculating distances, is sometimes called the Manhattan metric.

What is unique about the Manhattan metric, though, is that it is not exactly amenable to calculations. For example, if you toss a ball in the air, and I ask you how far away it is from you at any point in time, you can write down an equation that describes its motion, and use the Euclidean metric to figure out the distance. Likewise, if a spacecraft sets off in orbit around the Earth and I ask you how far it has traveled, you could use the equations of Special and General Relativity to give me an answer for any arbitrary number of orbits.

However, if I tell you that Joe’s pizza has moved from the corner of 53rd Street and Broadway to 34th Street and 7th Avenue, and I ask you how much longer of a walk that is from your place on 108th and Riverside…well, you’d probably have to pull up Google Maps.

You’d probably have to pull up Google Maps…

See where I’m going?

## It’s not just about pizza

Certainly, Google Maps is neat, but it is also not a revolution in thought. The thing to understand is that the Manhattan metric is not just useful for getting to the nearest pizza place. It’s also useful for buying the pizza. How?

Consider the tomatos in your pizza. How did they get there? Presumably, the owner of the pizza place has a supplier that brings him cans of tomato paste. The supplier probably gets them from a warehouse, the warehouse gets them from a distributor. The distributor probably sources tomato paste from a factory that processes tomatos, and the factory probably has warehouses and distributors of its own. Eventually, those distributors have to deal with the farmers who actually grow the tomatos in the first place.

As you hand over your \$2.50 for that slice, that money will traverse from you to the pizza shop to the supplier, the warehouse, the distributor, the factory, the other distributors, and eventually to the farmer. This is the economic distance between you and the tomato on your pizza. It is a distance also measured by a Manhattan metric, where every actor is a node and each transaction is an edge. In fact, the entire world economy is just a graph ruled by the Manhattan metric.

That might seem pretty impressive, but it’s not just pizza or economies. The Manhattan metric covers so much more. Consider, for example, biology. What makes you different from every other person you pass on the street? If you were to ask that question to a biologist, they would tell you that it’s your genes. More specifically, it’s the unique differences, the mutations, in your genes.

DNA is composed of 4 bases that we abbreviate with the letters A, C, G, and T. As DNA is copied over and over and over again, occasionally biology makes a mistake. An A might be changed to a G, or a T to a C. If one of these “mistakes” ends up in a sperm or egg cell, it will result in an offspring with a new version of a gene. As new versions of genes come and go, and their frequency increases or decreases in a population over a long enough period of time, you might even end up with a new species.

How different, then, are any two people or any two species? That answer depends on how many mutations have occurred to get from the sequence of one individual’s genes to those of the other. It might be a little more difficult to see how the Manhattan metric applies here, but if we consider all of the possible DNA sequences of a gene as nodes, and the mutations that transform one sequence into another as the edges, then we again have a system ruled by the Manhattan metric.

Treating evolution as a graph like this allows us a peek at the coming revolution of thought. Certainly, treating the economy as a graph is intriguing, and might make one rich a lot sooner than worrying about evolution. Yet, there are only 7 billion people on the Earth. The number of economic interactions that can take place is astronomically large, but finite.

On the other hand, inside of every human there are 6 billion bases, and that’s just humans. The “sequence space” of biology (that is, all the possible DNA sequences of any length) is beyond astronomical. Theoretically, it is infinite, though there are practical concerns that prevent that from actually being the case. Even though there are more bacterial cells than human cells in every human, and more than a million bacteriophages in every drop of water in the oceans, life as it exists on Earth explores but a minuscule portion of sequence space.

This, actually, is the essence of the study of evolution. Using the Manhattan metric, we can determine the distances between species, which allows us to construct a “tree of life”, but what really interests evolutionary biologists are all the paths untaken. Much like many of the streets of Manhattan are one way, therefore limiting which edges one can actually traverse (if traveling by car), the edges in evolution’s sequence space have layered upon them the concept of “fitness”.

Exactly how fitness drives the path of life along the edges of sequence space, and in which directions in might drive life into the future, are major open questions in the study of evolution.

## Just walk

To be sure, graph theory is a young field; perhaps the youngest field of mathematics. Every day there are new advances, new techniques, new algorithms devised. Still, there remains the very real possibility that, for the majority of problems in graph theory, the only way one will be able to find solutions will be to walk the edges. Finally, we return to Google Maps, and computers in general.

If there is one thing that computers are really good at, it is walking the edges of a graph. Computers don’t get tired, never get bored, and can walk very fast. As we refine the study of graph theory, and tackle the breathtakingly large number of problems to which graph theory can be applied, it is almost certain that computers and computation will be there with us every step of the way. Looking out even further into the future, the promise of quantum computing is nothing more than a computer that can walk all edges (or at least very many edges) simultaneously.

So, after millennia of mathematics driven mostly by the sheer force of human logic, we stand on the cusp of a future where essential discoveries will only be possible through the combined application of human ingenuity and raw computational brute force. Just something to think about the next time you walk down the street and pull out your phone to get directions to Joe’s pizza.

Post
1 year ago

## Hello, world!

Hello, 2012!

This is going to be, without a doubt, an exciting year. So, I thought I would kick things off by finally getting off my butt and finishing some of these draft blog posts I have been collecting. I have a lot on my mind that I would like to share, both high-level philosophical musings and nitty-gritty programming details. I’m going to try and restrict myself to subjects in computer programming, but don’t be surprised if I stray just a bit off topic from time to time. To get things started, I’d like to explain the title of this blog and the overall theme I hope to explore…