A Little Background
In this blog, we’ve talked a lot about particles, relativity, quantum mechanics, and even the reason for the universe itself. One important topic that I haven’t yet covered is spacetime. Where does it come from and why does it take the form that it does? Any Grand Unified Theory that we’d like to propose can’t just satisfy itself with describing the matter and energy that makes up the things we see. It also has to explain how the gaps between the things come to be there. In other words, it needs to be ‘background independent‘.
This feature has also been conspicuously absent from all of the research I’ve shared so far. In each case I’ve outlined, I’ve simulated space by sprinkling dots onto a preexisting smooth surface and hooking them up to those nearby. This isn’t good enough. In fact, it’s avoiding one of the hardest problems of the lot, and the physics community know this. If you look at any of the most promising research on discrete approaches, the main focus is on the structure of spacetime itself and how it changes. From that, it’s felt, everything else can spring.
People have had mixed success in this regard. There’s loop quantum gravity, which has been a relatively successful physical theory. However, at least as I understand it, it presupposes structures that have the four dimensions of spacetime we expect.
There’s the theory of causal sets, which starts with nothing but the idea of a partial order, and which can derive something roughly spacetime-like from it. However, reconciling it with quantum mechanics has proven tricky.
Then there’s causal dynamical triangulation, which has successfully assembled spacetime-like structures out of very simple raw ingredients. However, those ingredients once again have an implicit four-dimensionality built in at the smallest scales.
Do I have a model of spacetime to share with you that’s better than any of these? No. Categorically not. As with all of my research, I’m deliberately not trying to do physics directly. Instead, my goal is simply to illustrate ways that discrete techniques might make solving thorny physics problems easier, and to add to the theoretical toolkit with tricks from computer science.
What I do have is a way of building large, irregular networks from scratch that behave like smooth spatial surfaces, while using no geometrical information whatsoever. I’m going to share it with you over a sequence of posts. You’ll have to assess for yourselves whether you think it’s a good fit for nature.
As a starting point, let’s look at a simplified version of the problem. We’ll forget about time, and concentrate on only a single dimension of space.
Imagine you have fifty friends who you’re playing a party game with. The aim is to use your cellphones to form an invisible circle. When the circle is finished, you’ll be able to call Alice. Alice will then able to call Bob. Bob can call Cindy, and so on. At the end of the chain, Zachary can call you and tell you what message he received. The message will have gone through everyone in turn.
Each person is allowed to store the numbers of up to two friends on his phone. They can swap their numbers for others by calling one of their contacts and saying ‘who do you know?’ and picking which numbers to keep or discard. They can also say to someone, ‘you’re my friend now’. They can’t say anything else, or rank the contacts they receive by name or number.
At the start of the game, the numbers in everyone’s phones are random. How do they organize themselves into a chain?
As party organizer, you have one extra perk you can use if you want to. You can add people to the party one at a time if you like. If you decide to do that, people will receive their random phone numbers when they join, and the numbers they receive will always be for people who’re already at the party.
Any ideas?
How to Build A Universe 
Do the party members know that I am the host, i.e. I that I am a special node? That seems to be a requirement for a solution.
I’ve solved it for parties of one, two and three – the chain forms naturally :-).
For four it doesn’t work unless the phones have caller ID because you need to be able to swap in newcomers, so your problem isn’t fully specified.
Thought: Calling someone and saying “you’re my friend now” means that the receiving person should swap one of their contacts for the caller. But how to determine which of the contacts to swap is difficult. If you can, on being called, ask the caller “who do you know” (are you allowed to do that? Again – not specified in the problem) then you should swap any contact you have in common with the caller for the caller, but if you don’t have anyone in common it gets a bit trickier.
Perhaps I’ll think about it more when I have time.
Hi Keir,
Your right, the problem’s not specified very well. I did a somewhat lame job of that. To some extent, that’s because I’m applying artificial constraints to try to define a simpler case than the one I was originally trying to solve. So, in fumbling towards clarity, let’s say the following:
* New people who receive random numbers can call those numbers, and the recipients have to pick up and answer. However they don’t have to put the caller on their list until he says ‘you’re my friend now’.
* Once a person receives a list of numbers, they don’t have a way to store and remember them. If they want to keep hold of a number, they have to decide then and there to add it to their contacts.
* The recipient of a ‘you’re my friend now’ instruction can make his own mind up about which friends he drops. He’s at liberty to create some ranking system for his friends, so long as he doesn’t share it with others.
Does this clear things up, or did I miss the point of your questions?
Fun puzzle. Do party members know their own cell phone number?
I think that clarifies it a bit more, but I still need to know if the people know that I am the host node. But I now understand that if a person has two numbers, they can call one of them, and ask that person which numbers they have. That then means the caller has four numbers, of which he can keep two and discard two. Similarly after a call the callee will have three numbers (their two original numbers, and the number of the person who called them), and they can pick any two and discard one. Then the next call can happen.
Can I also use the fact that a caller might find the number is engaged? Then I can get extra information by getting people to make five minute long calls at specific times which other people can detect by the engaged tone and make decisions on.
Can my people indicate the rank they give their numbers by the order they present them to the caller who asks for them? That doesn’t seem to go against what you’ve described in the problem.
Finally, a footnote: there is the possibility that you randomly get closed loops if you have everyone entering the party at the same time and being assigned random numbers. To illustrate, if Peter, Quentin and Rolando each are assigned each other there is no way of them breaking out of their triad and joining the main group. So the requirement that each party goer joins one at a time is mandatory for there to be a solution.
Okay, I think I’ve solved it if you can give a caller your two numbers in a special order. It depends on the loop being formed in one direction. Each person in the loop has the number of the next person in the loop, and the person one beyond that.
You start with one person – me.
Then Alice joins. She knows that she is the second person, because she only gets assigned one number (the clever bit). So she calls me and asks me for my numbers, and I can’t give her anything (confirms that she is second). Then she tells me I’m her friend now, so I add her as my first number. It also tells her that she should put my number in her second number slot.
Then Bob joins. He gets assigned Alice and Me as his numbers, but can’t know that he’s number three. So he calls me and asks me for my numbers (if one of your random numbers is the host, you call them first to determine if you’re number 3). I can only give him one – Alice. So that tells him that he is number three. He adds Me as his first number, and Alice as his second and tells me that he’s my friend now. That tells me that he’s number 3, so I add him as my second number. Then he calls Alice, and without asking for her list says “You’re my friend now”. That tells Alice that he is number 3, and so she adds him as her first number.
So now we have Me, Alice and Bob. I have Alice as my first number and Bob as my second number, Alice has Bob as her first number and Me as her second number, and Bob has Me as his first number and Alice as his second number. We can make a chain call.
Now number 4 joins – let’s call her Deepthi. She either gets assigned Alice and Bob, or Alice and Me, or Bob and Me. This tells her that she’s not number 2. It doesn’t really matter because the chain is symmetrical[1], so let’s say she got Bob and Alice as first and second. She calls Bob and asks him for his list. He tells her “Me” and “Alice”. That tells her that she should put Me as her first number and Alice as her second number. She doesn’t say “You’re my friend now”. This tells Bob to swap Deepthi as his first number and to move Me to his second number. So we have a chain of four.
Number 5, Erik, follows the same protocol as Deepthi. And so on, by induction.
Ah Induction, how do I love thee? Let me count the ways…
[1] Actually, if she gets Bob and Me or Alice and Me she could be number 3, so she would call Me, and get two numbers telling her she’s at least number 4. She can then continue to follow the pattern as before, calling the other number that isn’t me.
Keir, you have taken a puzzle that I did a botched job of characterizing, and done something lovely with it. I realized somewhat belatedly that for what I originally conceived of, you needed to have the ability to call up and not only say ‘I’m your friend now’ but ‘replace X on your list with me’, which makes the whole thing rather easier. What you did, presuming I’m following correctly, was find a way to have the same effect as ‘replace X with me’ message using information already latent in the other two message types. Bravo. If only I’d done as good a job of explaining it as you did at investigating.
And by the way, you’re absolutely right about people needing to enter the party one at a time. This was sort of my core point, though it got a bit lost in the shuffle. Do the puzzle adding one person at a time and it’s fun and solvable. Try to do the same puzzle with everyone in the party at once, and it becomes impossible. This is what I’m intending to pick up on in my next post.
Note to self: Do not try to write somewhat technical blog-articles on a crowded commuter train, under the influence of mild jetlag.
… especially not when there is a Keir monitoring them!
Next challenge: find a way to allow the party to store state, invite a (countably) infinite number of people and convert the chain into a Universal Turing Machine.
To get started, if, instead of forming a loop, we form a system where there is a main loop of people, but every person in the loop also has a single contact hanging off them for storing a value, then there might be a possibility of doing this. By loop + dangling person I mean, for example, that A has B and X, B has C and Y and C has A and Z. X, Y and Z use one of their contacts to store a value, and one to store the backward contact. Then A can pass on calls to B directly, or can call X and swap B for C (X stores C for A). And X’s second contact is used to store a symbol on the tape, for example if X has two contacts the same it’s a 0, and if X has two different contacts, it’s a 1. We can then give all the main loop participants instructions in the form of a state machine – presumably this is allowed because in the solution to the first problem we had a set of instructions each participant was to follow to form the chain.
So now the challenge would be – how to get such a loop plus dangling people constructed. But perhaps you’re losing interest at this point.
Still interested. Still thinking it through.
This idea touches up against something else I’m planning to blog about at a future point–namely constructing simple models of computation out of networks. If you want something like this to be universal, it strikes me that you either need an infinite number of partygoers, or the ability to dynamically add partygoers at will. Perhaps the party sends out invitation when it runs out of tape. So you’d also need a way of indicating that the limits of tape capacity had been reached. So perhaps you need two bits for logical state instead of one.
One might also ask whether a network with integer dimension (such as a loop) is even necessary if we’re building a computational model rather than something with spatial implications. And if we do think that its necessary, I think that’s interesting in itself.