Posts Tagged ‘software-development’

A Little More Background

June 6, 2012 8 comments

In my recent post, A Little Background, I started to try to explain how one might go about building networks that looked like smooth structures with integer dimension at large scales. In other words, networks that might look something like the empty space our planet sails through.

At the end of that post, I set a puzzle in which a group of party attendees who could only communicate via cellphone tried to organize themselves into a ring. I did a  horrible job of making the details clear, but one of the fine commenters on this blog (Keir) solved it anyway. Hoorah for commenters!

Along the way, Keir remarked on the key point that I was hoping people would find. And that is this: when you’re trying to build a network that has some global property like the friendly geometry of space, it’s fairly easy to do if you add nodes to the network one at a time. It’s usually impossible if you try to acquire smoothness some other way, like, for instance, starting with a random network and telling it how to untangle itself.

This is true whenever you insist that the information available to each node in the network be local. In other words, so long as a node can only gather information about its neighbors, or even its neighbors’ neighbors’ neighbors, it won’t ever know enough to untangle its position relative to all the others. Bits of your network will always be breaking off. And even if you put in tricks to prevent the network from coming apart, it will retain twists and knots that stop it from ever sorting itself out (except perhaps in 1D).

This is interesting, and, to my mind, suggestive, because it says that if the universe is discrete, and if it started from simple initial conditions, then there should be ample evidence that it used to be tiny and got a lot bigger. And this, of course, is what we see. This doesn’t prove anything about the discreteness of spacetime, put it’s nice to know that reality and our simple simulation tools line up.

However, while it’s one thing to get drunk partygoers with cellphones to form an electronic conga-line, it’s trickier to get them to form a network that looks like a flat surface, (unless, perhaps, it’s a party full of topologists.) But it is doable, and the information that you need to make available to any node in the network doesn’t need to be that large. The result is the simplest closed surface that’s locally two-dimensional everywhere. In other words, a sphere.

Without getting too deep into the grimy details, here’s an example of a rule that does the job:

  1. Start with a graph of four nodes, all connected to each other.
  2. Make  a new node that you’d like to add to the graph. Call this X.
  3. Pick a random node on the graph to add to. Call this A.
  4. Pick a second node that’s a neighbor of A. Call this B.
  5. Pick a node that’s a neighbor of A and B, with the lowest neighbor-count possible. Call this C. Call the set {A,B,C} the New Neighbors.
  6. Look at the triangles that are formed when you take X and any pair of New Neighbors. We call each of those triangles a Face.
  7. Each Face should be adjacent to another triangle that contains two New Neighbors and a different node. We call that node the Opposite (O).
  8. If the sum of the neighbor counts of the two New Neighbors is greater than the sum of the neighbor counts of X and O plus two, then remove the link that runs between the New Neighbors, and add a link between X and O.
  9. Return to step 8 and keep iterating through your set of Faces until you’re not swapping any more links.
  10. Return to step 2 to add the next node.

In practice, you have to be slightly careful how you implement this, but not that careful. In fact, I’ve found several algorithms that will work for 2D. Here’s the output from one that’s completely deterministic.

And here’s another that’s adding at random.

And here’s what it looks like inside a randomized surface, because it’s pretty.

While I’ve had great success in 2D, I haven’t found an algorithm yet that will work for 3D. I don’t think that’s because it’s impossible, it’s just that it makes my head hurt. The bubble you form in the 3D network is wrapped in 4D, which takes a little getting used to. And when you increase the number of dimensions, the number of edge cases you need to consider goes up accordingly.

Of course, there are plenty of things wrong with these networks. For a start, they’re way too regular compared to the kind we’d like to run particles across. But these obstacles strike me as eminently surmountable. So while we’re still a ways a way from being able to build a plausible Big Bang from scratch, there are at least signs that it could be done.

By the way, for those who like a challenge, I vigorously encourage anyone keen to take a crack at the 3D case. If you want inspiration, here’s a sample Java file I wrote to build a 2D surface. Also, if you’re looking for a fresh perspective on this topic, I can highly recommend Ray Hinde’s excellent new digital physics blog over at Finitism Forever. He seems to be tackling the same problem.