Twin Paradox in a Closed Universe

September 21, 2007 – 3:14 am

If you’re familiar with the twin paradox, you can skip straight to the Closed Universe section.

Suppose you’re sitting in a car heading east at 100 km/h, while another car passes you by heading west at 100 km/h. According to special relativity, if you compare your clock with the clock of the passenger in the other car (let’s call her Alice), you will notice that her clock runs slower than yours.

The closer your relative speed is to the speed of light, the more noticeable the difference will be. For example, if your relative speed is 90% the speed of light, you will see Alice’s clock running about 2.3 times slower than yours. Of course, it’s not just the clock that will run slower — everything will run slower, including, for example, biological processes. Alice will age 2.3 times slower than you.

But what makes you so special? Nothing, really. Because according to Alice, it’s you whose aging slowly. So whose right? Well, the short answer is that you’re both right, because time isn’t an absolute thing — it depends on who’s measuring it.

This line of reasoning leads to the famous ‘twin paradox’: Two twins, Alice and Bob, are born on earth (if you must know then yes, it’s the same Alice). At birth, Alice is put aboard a spaceship that can reach extremely high speeds and sent off into space for a long trip. She reaches the edge of the galaxy, makes a U-turn, and returns to earth. This round-trip takes her 40 years in earth-time.

Meanwhile, Bob remains on earth. When Alice gets back, Bob is 40 years old. Because Alice traveled at high speed, Bob saw her aging very slowly, so when she gets back she is much younger than Bob, say 20 years old. But according to Alice, it’s Bob who aged slowly, so actually Alice should be older than Bob.

That’s the twin paradox, but it isn’t really a paradox. The problem is that in order to make this round-trip, Alice has to accelerate — she can’t go away and back again with constant speed. Therefore, the problem is no longer symmetrical: Alice is accelerating, Bob isn’t. To calculate exactly what happens in this case you need to use general relativity, but the answer is that Bob is right and Alice is wrong: Alice will have aged more slowly than Bob.

Closed Universe

I’ve been wondering, what happens to the twin paradox if the universe is closed? What I mean by ‘closed’ is that if you travel in a straight line, you end up back where you started. So the universe looks like a closed loop, only in three dimensions. (*)

In such a universe, the Alice twin can leave earth, travel with constant speed, and return to earth by simply going straight (**). Meanwhile, the Bob twin remains on earth like before. No one is accelerating, so the usual explanation of ‘Alice is accelerating and that’s cheating’ doesn’t apply here. Apparently, the situation is symmetrical: Bob thinks Alice is moving and aging slowly, Alice thinks Bob is. Who is right?

Well the answer is rather interesting. In special relativity we are used to saying that there are no ‘preferred frames of reference’ — that all inertial observers are the same, and that there are no absolute speeds, only relative ones. It turns out that in a closed universe this is no longer the case.

Consider the following experiment. Bob, who is on non-moving earth, simultaneously fires two photons at opposite directions. The photons travel around the universe and return to Bob, both at exactly the same instant.

Now let Alice perform this experiment on her spaceship. She sends out two photons, traveling at the speed of light. Let’s look at this experiment from Bob’s frame of reference, where the photons are still traveling at the speed of light (***). Bob sees the photons going around the universe, but meanwhile Alice is moving. So one photon will reach Alice before the other. Alice must observe the same thing (although they will not agree on the timing).

The same experiment, conducted by Bob or by Alice, produces different results. This is because Bob’s frame is special: It has zero speed, an absolute speed. Thus the symmetry between Bob and Alice is broken. Further calculations are required, but it turns out that Bob is correct: Alice ages less than Bob.

If you want more details, I found an interesting paper that discusses this paradox, and also develops the Lorentz transformations for such a universe.


(*) The mathematical term for this is actually ‘compact’, but that’s because mathematicians enjoy complicating things.

(**) You may be wondering how it’s possible to go in a circle without accelerating. You can try looking at it this way: In circular motion with constant speed, the vector of acceleration points inward toward the center of the circle. If you live in a 2-dimensional world, you can measure this vector because it points in a direction you can move in. For instance, you can hang a ball from a piece of string and watch the string stretch.

But if you live in a closed, 1-dimensional world, and you’re going in a circle, where is the acceleration vector pointing? It can’t point inward, because for you there’s no ‘inward’. In your 1D world there’s only front and back. As a consequence, you can’t measure this acceleration experimentally. And what you can’t measure experimentally doesn’t exist.

By the way, in terms of differential geometry, this is what geodesic curvature is all about: It’s the part of the acceleration that’s due to the shape of the manifold.

(***) This is one of the premises of special relativity — that light travels at the same speed for all observers. If you’re unconvinced it’s still true in a closed universe, consider the following. The metric of a cylinder is the same as that of a plane — a cylinder isn’t curved. Similarly, the metric of a closed, 1-dimensional universe is the same as that of an open one:

ds^2 =-dt^2 + dx^2

The constancy of light speed follows from the metric, and from assuming that the correct transformations (boosts) preserve the metric.

It’s like deja vu all over again

September 20, 2007 – 8:21 pm

6th grader raises $6.5 million in round A funding. The bubble’s back, folks.

Fun With PDEs – Part 2

September 17, 2007 – 6:42 am

Last time I described the first pitfall I encountered when solving a PDE — an inherent instability in the partial derivatives. This time I’ll talk about the second pitfall, which is simpler conceptually, but has wider implications for programming in general.

In my first implementation of the solution I used a simple method to calculate the derivative:

\frac{\partial f}{\partial x}[j] = \frac{f[j+1]-f[j-1]}{2 \, dx}

-
This is just the average of the right and left derivatives. I wanted to improve the accuracy of the derivative calculation because of various reasons, so I turned to Savitsky-Golay filters, which were also described in the previous post. Using this method you get a digital filter that you apply to your data. If you’re not familiar with digital filters, you can think of a filter as an array of numbers c_n, \, n=-l,\cdots,l which are applied to your function f as follows:

F[j] = \sum_{n=-l}^{l} f[j-n] * c_n

-
(I’m probably mixing up some of the signs here, but the intention is clear I’m sure). To calculate a derivative using S-G, you first apply their filter to your data, and then divide by the spatial resolution dx — the distance between adjacent points on the grid. It is worth noting that there is a highly efficient way of doing this calculation using FFT. For more details, see Numerical Recipes.

I implemented S-G and tested it using a simple sin(x) function, and it worked flawlessly. But after I inserted it into my main program, the simulation started spewing out strange results. After some debugging I discovered something very strange: Using S-G, the derivative of a constant function wasn’t zero, and in one case reached 10^{44}. How odd! Debugging further, I found that non-zero derivatives only happened when the initial function f had very large (and constant) values, on the order of 10^{22}, and dx was very small, about 10^{-10}.

To continue debugging, I dropped the fancy FFT convolution and switched to straightforward calculation — the one that’s shown in the last equation. This finally revealed the problem: When multiplying each value of the function f by the factor c_n and summing, some of the least significant bits are lost, because the numbers don’t all have the same exponent. So even though the calculation is accurate, the limitation of the computer’s double precision causes a loss of data. When the convolution is done, you’re left with a small value that’s not zero. But then to get the derivative you divide by dx, a very small number, and this shoots that small error through the roof. The smaller dx, the larger the derivative of the constant function! So once again, decreasing dx actually caused a larger error.

What helped me solve this problem was noticing that the S-G coefficients are anti-symmetric, i.e. c_{-n} = -c_n. Specifically, anti-symmetric coefficients have the same exponent. Therefore I changed the summing order to sum pairs of anti-symmetric factors:

F[j] = \sum_{n=1}^{l} (f[j-n] \cdot c_n + f[j+n] \cdot c_{-n}) + f[j] \cdot c_0

-
This solved the problem: Constant functions now had a zero derivative, because each term in the sum was exactly zero, even in double precision. And the happy consequence was that this fix also solved the weird simulation results I started with.

No More Time Waste

August 30, 2007 – 3:57 am

Lately I’ve been spending way too much time on tech news sites like reddit. Whenever I had some free time and thought about doing something productive like reading a book, I would end up gravitating toward one of these time suckers instead. Hours would pass. From time to time I’d learn something new, but most of it was spent on mind-numbing entertainment like lolcat. (my personal favorite btw).
Read the rest of this entry »

August 19, 2007 – 8:12 pm

It’s not that I’m so smart, it’s just that I stay with problems longer.

– Albert Einstein

Prisoners’ Escape – The Solution

August 13, 2007 – 12:30 pm

(you can find the original riddle here)

Let’s begin with a draft solution, one that doesn’t work but will start us in the right direction. And to keep things simple, let’s say all the tasks are done the minute the prisoners leave the meeting, so all they have left is to notify someone that they’re done.

Prisoner 1 is responsible for telling the guard once all the tasks are complete. We’ll call him the Leader. He keeps a counter called ‘num_done‘ which starts at 1 (denoting that prisoner 1 himself is done). When the leader enters the room, this is what he does:

if light is on:
    num_done = num_done + 1
    turn light off
else:
    do nothing
-

When any other prisoner enters the room, this is what he does:

if light is off and not turned_light_on:
    turn light on
    turned_light_on = true
else:
    do nothing
-

And each such prisoner maintains a flag called turned_light_on, initialized to ‘false’.

At the end of this, num_done should show the number of prisoners whose task is complete. And when num_done = n, prisoner 1 will notify the guard.

The problem is that this algorithm has an off-by-one error. If the light was originally on before any prisoner entered the room, then when the leader enters the room he will count that on-light as one prisoner. Therefore he’ll reach a count of n while only (n-1) prisoners reported in.

To solve this problem we need to modify the algorithm a bit, to handle the possible initial states of the light switch. We want to give the leader a chance to see the initial state before anyone else touches it. So the other prisoners start by doing nothing, until they get some sort of signal from the leader. This signal will be ‘flicking the switch’: They first want to see the light turned on, and then, when the time is right, they will turn it on themselves.

So now, each prisoner other than the leader maintains another flag called saw_light_on, which starts as ‘false’. The algorithm is:

if light is on:
    saw_light_on = true
else if saw_light_on and not turned_light_on:
    // light is OFF
    turn light on
    turned_light_on = true
else:
    do nothing
-

Next, the leader maintains an extra flag: saw_initial_state initialized to ‘false’. Her algorithm is:

if saw_initial_state:
	if light is on:
	    turn light off
	    num_done = num_done + 1
	else
	    // flick the switch to signal the others
	    turn light on
	    num_done = num_done - 1
else:
	// This is the first time the leader enters the room
	turn light off (if it's on)
	saw_initial_state = true
-

Note that the leader needs to continue flicking the switch forever. Otherwise, latecomers will never turn the light on. Also note that the leader must discount for his own flicking by decrementing num_done. Finally, as before, when num_done = n, the leader notifies the guard and the prisoners escape. There you have it!

Prisoners’ Escape

August 1, 2007 – 9:53 pm

In an effort to make this blog more interactive, I’m switching the riddles to a new format. I’ll first post only the riddle, without the solution, so you guys can have a crack it. After a week or so, I’ll post the solution. Here goes…

n prisoners are planning an escape. They bribed a guard to let them all meet once. Each prisoner was given a task to complete, such as digging or stealing some key. Once all the tasks are complete, the prisoners will notify the corrupt guard who will turn a blind eye while they escape. The problem is, the prisoners can’t talk to each other because they are all in solitary confinement.

Once a day, a prisoner chosen at random enters a storage room that has a single light bulb in it. The prisoner can either flick the switch (turning the light bulb on or off), or leave it as it is. At the time of the initial meeting, as they plan their strategy, the state of the switch is unknown.

Using only switch flicking, how can the prisoners coordinate their escape? Specifically, one of the prisoners must know at some point that all the tasks are done, so he can notify the guard and lead them all to freedom. If the guard is notified before all tasks are complete, the plan will fail and the prisoners will be caught.

(ready for the solution? here it is)

aMule Hacking

May 31, 2007 – 3:19 am

aMule is an open source eMule-like client. It enforces a strict upload/download ratio at the client side: You set the maximum upload rate, and your down rate is limited accordingly. For example, if you allow aMule to use 5 kB/s for upload, your maximum download rate is 20 kB/s. 9 kB/s upload gives you 36 kB/s. 10 kB/s gives you unlimited download bandwidth.

My problem is (or rather, was :) ) this: 36 kB/s for download is very little compared with my ADSL line’s capacity of 180 kB/s. But to get the full speed I need to allow aMule to use 10 kB/s out of about 12 kB/s of upload capacity, which makes web surfing extremely painful (ping google.com gives > 2 secs). I don’t mind sharing my bandwidth, but this is too much.

I tried being a good citizen by doing some traffic shaping with wondershaper at my router, giving aMule traffic low priority compared with web surfing. This isn’t trivial, because aMule uses varying ports at both ends of a connection. I used netstat --program to find the peers and then lowered their priorities by host. This helped matters a bit (reducing latency to about half a second), but surfing still felt sluggish.

So I pulled out the big(ger) guns. I downloaded the aMule source code and found this nice little function in Preferences.cpp:

// Here we slightly limit the users' ability to be a bad citizen: for very low upload rates
// we force a low download rate, so as to discourage this type of leeching.
// We're Open Source, and whoever wants it can do his own mod to get around this, but the
// packaged product will try to enforce good behavior.
//
// Kry note: of course, any leecher mod will be banned asap.
void CPreferences::CheckUlDlRatio()
{
	// Backwards compatibility
	if ( s_maxupload == 0xFFFF )
		s_maxupload = UNLIMITED;

	// Backwards compatibility
	if ( s_maxdownload == 0xFFFF )
		s_maxdownload = UNLIMITED;

	if ( s_maxupload == UNLIMITED )
		return;

	// Enforce the limits
	if ( s_maxupload < 4  ) {
		if ( ( s_maxupload * 3 < s_maxdownload ) || ( s_maxdownload == 0 ) )
			s_maxdownload = s_maxupload * 3 ;
	} else if ( s_maxupload < 10  ) {
		if ( ( s_maxupload * 4 < s_maxdownload ) || ( s_maxdownload == 0 ) )
			s_maxdownload = s_maxupload * 4;
	}
}

So, commented out the 'Enforce the limits' section, compiled, and viola -- your basic leech mod. Now I was free to set my upload rate to 1 kB/s without affecting my download rate, but I didn't want to do that because:

  1. I didn't want to be a leech. As a citizen, I try to follow a set of rules that I believe is scalable. What I mean by 'scalable' is this: If everyone followed my set of rules, the community would prosper. My rules aren't necessarily the official ones. For example, I always vote at elections because I believe that if everyone voted it would be good for society. There's no rule that says you have to vote, but it's scalable so I do it. Anyway, being a leech on a P2P network is certainly not scalable.
  2. aMule has a 'credit' system: When you are on someone's queue waiting to download a chunk, uploading him some data gives you credit. You use this credit to jump ahead in his queue. The queue wait is typically very long, so jumping ahead is significant. Hence your effective upload rate still affects your download rate, even with the mod.
  3. Leeching clients are banned when they are discovered. As far as I can tell, this is not done automatically, but rather manually by people who notice skewed upload/download ratios.

Fortunately, there is good middle ground: Setting my upload rate to 7 kB/s. At this rate web surfing is smooth, I still share most of my bandwidth, and chances of getting detected are slim to none. Best of all, this is scalable behavior: If everyone set their upload rate to 3 kB/s under their max rate, and got max down rate in return, things would be terrific.

Fwd: Spread this number

May 1, 2007 – 5:02 pm

09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0

This is the Processing Key that will allow viewing HD-DVD movies on Linux. What’s happening now with this key is similar to what happened a couple of years ago with the DVD key and DeCSS.

For more, see here and here. The second link is an account of how the key was recovered by the guy who did it. Spread the word!

Fun with PDEs

May 1, 2007 – 4:58 am

I just finished working on a numerical simulation of a set of partial differential equations (PDE). I developed these equations for a physics research project I’m involved in. The equations did not seem to be solvable analytically, so I had to do it numerically. This was my first attempt at solving a PDE, and writing the simulation turned out to be much more involved than with ordinary differential equations. Here are a couple of interesting pitfalls I encountered.

PDE Primer

In case you’re not familiar with the terminology, I’ll first explain what a PDE is. A simple equation contains one or more unknowns which represent numbers. For example: x^2-x-1 = 0. An ordinary differential equation (ODE) is similar, except the unknown is a function rather than a number. Such an equation involves derivatives of the function. Here is an example:

f\prime(x) = f(x)

-
The solution of this particular equation is f(x) = c e^x, where c can be any number. Finally, a partial differential equation (PDE) involves a function that has two or more parameters, and includes partial derivatives of this function. For example, the following equation describes waves propagating through a medium:

\frac { \partial^2 f } { \partial t^2 } = v^2 \, \frac { \partial^2 f } { \partial x^2 }

-
PDEs are very important in physics. In fact, many of the basic laws of nature are described as PDEs. Examples include Maxwell’s equations, Shcrodinger’s equation, and Einstein’s field equations.

On to the simulation!

Pitfall 1: Exploding Waves

So, I built my model for the problem, derived the equations, and was ready to solve them. By ‘solving’ I mean that I start out with the known function at time t=0, and I want to find out what that function is at a later time. My function initially looked like this:

Some thousands of time-steps later, it evolved into this:

So far so good, but then it completely exploded:

Going back a bit in time, I was able to trace the beginning of this explosion:

And zooming in on the ‘wavy’ part:

It looked as though waves were forming on my function, and then ‘exploding’.

Inherent Instabilities

I was certain I had a bug, but I couldn’t find it. While debugging, at one point I decreased the spatial resolution — using less points per unit of space to describe the function… and the problem was gone! So, decreasing the accuracy of my solution actually solved the instability… That was very weird.

Mentioning this to a Ph.D student at the lab, he said this problem sounded familiar to him. And as it turns out, this is a universal problem with PDEs: If the time step is too large compared with the spatial resolution, the amplitude of small waves with short wavelengths quickly increases with time until they dominate the solution. This is due to the way numerical derivatives are calculated. The difficulty here is that the time step needs to be incredibly small, making calculation unfeasible. For some equation, the situation is even worse, as they are unstable for any time step, no matter how small.

For simple PDEs, it is very easy to see this effect by taking the function f to be a wave, and watching what happens to the amplitude over time. You can see a derivation of this result here. For a more in-depth discussion, Numerical Recipes is your friend. This method of analyzing equations is called von Neumann stability analysis.

In Comes Lax

Okay, so I found out not alone, but what can be done to solve this problem? The first thing I tried was to calculate the derivative more accurately. There is a method called Savitzky-Golay, where you fit a polynomial to your function at each point, and calculate the polynomial’s derivative at that point. The brilliant thing is that this whole operation (fit + derive) can be done using a single convolution, which costs a meager O(n log n) of processing time.

So I implemented S-G, only to discover it doesn’t solve the problem. More on that in a future post.

As it turns out, there is an incredibly simple solution due to Lax, which says the following. When advancing the function value to the next time step, you do something like this for each position:

f[j] = f[j] + \frac { \partial f } { \partial t } [j] * dt

-
The Lax method says that the f[j] at the right-hand side should be replaced by an average of it’s neighboring cells:

f[j] = \frac{f[j-1] + f[j+1]}{2} + \frac { \partial f } { \partial t } [j] \; dt

-
And that’s it! This replacement causes a numerical diffusion that ‘sedates’ the unruly waves, causing them to decay instead of explode. The time step used in the simulation still needs to be below some value, but now it decreases linearly with the spatial distance dx, which is much better than before. So Lax saved the day — and that was the end of my first pitfall. This is getting to be quite a long post, so I’ll describe the second problem in another post. Cheers!