Irrationally Walking in Love

Valentine’s day is upon us, and this is a great opportunity to finally write about a problem that has greatly disturbed me for many years. I’m sure you have all experienced this problem before – and it is certainly an annoying one.
It’s a fine evening, and you and your eternal love have decided to take a romantic walk outside in the cool night air. Hugged together and enjoying each other’s presence, an immense sense of satisfaction overcomes you. Could there be anything better in life? Certainly. Because there is one issue which keeps you from blessed comfort – you are walking out of sync. When your partner lifts his/her foot, you have just stepped down. When you step forward, he/she has just retracted the leg. So instead of walking in pace, the fact that you are hugged together makes you look like a pair of limping, waddling ducks. Hurray for romance.

Taken from 8photo.org
Taken from 8photo.org

You may have started together, but somewhere along the way, synchronization was lost. You are both quite sure that if only you stepped at the same time just once, everything would be alright, and you would be able to coordinate your pace from there on. Of course, it requires dexterous footwork in order to synchronize while in mid-walk, and it also looks ridiculous from the outside, so switching your legs or doing any footwork while striding is out of the question. No, you are going to have to wait until your footsteps naturally fall at the same time in order to synchronize.
If the time between each step were of integer size, and you started together at the same time (same split), then it would be quite easy. If your partner’s step time is a, and your step time is b, then after a \cdot b steps at most you would make a simultaneous step.
But what if you didn’t start out at the same time? Or worse yet, knowing how crazily and illogically love makes youngsters act, what if the both your and your partner’s step size is irrational? Is it even guaranteed that your footsteps will ever meet, or are you doomed to an entire night’s worth of out-of-sync walking?
Unfortunately for you, meeting your footsteps precisely with irrational step size is generally impossible. If your partner’s step size is \alpha, and your step size is \beta, both of which are irrational, and \alpha/ \beta is also irrational, then there is no such pair of numbers m,n such that m\alpha = n\beta.
However, it turns out that if you are not searching for maximum precision, a compromise can be made, and there exist numbers n,m such that | m \alpha - n \beta | < \varepsilon for any \varepsilon > 0 as small as you choose. So if you can synchronize your steps if they match only by a number as small as \varepsilon , you will be able to correct your pace. Neat!
Thus, even if both you and your lover are irrationally in love, assuming you are willing to tolerate a bit of imperfection with each other, you can keep walking in harmony, and enjoy your romantic journey.

\line(1,0){250}

For the mathematically inclined amongst us, here is the proof of the above statement. It is not my original research; this is a known problem, which I have first encountered in high school, although in another, less love-stricken form. The proof is taken from the site TopologyAtlas.
We want to show that for every two positive irrational numbers, \alpha,\beta, there exists two positive integers m,n, so that | m \alpha - n \beta | < \varepsilon. Without loss of generality, we can assume that our partner’s step size is 1, and therefore our own step size is \beta/ \alpha. This is still an irrational number, so we will rename it back to \alpha. We restate the above as:

| m - n \alpha | < \varepsilon

n\alpha cannot be an integer, so it has a fractional part. Setting m to the whole part of n\alpha, we only need to prove that there always exists an n so that the fractional part is smaller than \varepsilon.

The proof is as follows:
Let m,n be two different integers, and \alpha an irrational number. The term frac(x) means “the fractional part of x”, and will be denoted by \{x\}.
We note that \{m\alpha\} \neq \{n\alpha \}. Why must this be? If \{m\alpha\} = \{n\alpha \}, lets see what happens when we subtract n\alpha from m\alpha.

m\alpha - n\alpha = \alpha(m-n) .

The left side of this equation would be an integer, since the fractional parts are the same. However, the right part is irrational, since \alpha is irrational and m-n is not. This is a contradiction, and hence the fractional parts are not the same.
This means that the set D=\{ \{n \alpha \} | n \in Z\} contains infinitely many members – one for each integer.
Since \varepsilon > 0 , we can divide the region [0,1] into 1/\varepsilon segments of length \varepsilon. If 1/\varepsilon is not an integer, that’s alright – the last segment will be a little smaller than \varepsilon. All the points in the set D are contained within the region [0,1], and each falls into one of the segments. Since there is a finite number of segments, but an infinite number of points in D, by the pigeonhole principle we get that there is at least one segment, which has at least two points that fall into it. Since the length of each segment is \varepsilon, the distance between these two points is smaller than \varepsilon. Mathematically, we can always find two integers, m,n, such that:

| \{m\alpha\} - \{n\alpha\} | < \varepsilon .

Lets arbitrarily choose that m > n.
Now, what is the fractional part of a number, {x}? It is the number itself, minus its whole part.

\{x\} = x -\lfloor x \rfloor .

(The floor function, \lfloor x \rfloor, gives the largest integer which is not larger than x).
Lets put that in the equation above:

| m\alpha - \lfloor m\alpha \rfloor - n\alpha + \lfloor n\alpha \rfloor | < \varepsilon .
| \alpha(m-n) - (\lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor) | < \varepsilon .

Since m > n, then m-n > 0, and also \lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor \geq 0 . We can therefore give these two some convenient names. Lets define the integers:

p = m - n
q = \lfloor m\alpha \rfloor - \lfloor n\alpha \rfloor

This reduces us to:

| p \alpha - q | < \varepsilon

Hurray! We have now solved what we wanted to solve in the first place – compare this equation with the one we used to formulate our problem. We have satisfied the walking needs of your and your lover.

\line(1,0){250}

For the even more mathematically inclined amongst us, we will now continue with the proof of a stronger statement, about the density of irrational multiples.
The above statement – proving that there always exist p,q, so that | p \alpha - q | < \varepsilon , is part of a larger proof, of a stronger statement. The stronger statement is that the fractional part of m\alpha is dense in the region [0,1]. “Dense”, in this case, means that for any number x in the region [0,1], there exists an m so that | x - \{m\alpha\} | < \varepsilon. In plain English, it means that for any number x we choose in [0,1], we can find an m so that the fractional part of m\alpha is as close to x as we like.

So lets continue from where we left on. We assume that p\alpha > q, so we can open the absolute value without worrying too much. We also note two things:
First, since | p \alpha - q | < \varepsilon , and q is integer and \varepsilon is smaller than 1, it means that \{p\alpha\} is smaller than \varepsilon.
Second, a word about the fraction function. If \{p\alpha\} < \dfrac{1}{k} , then \{k \cdot p\alpha\} = k \cdot \{p\alpha\}. To see why this is, look at the left hand term, and remember that p\alpha has a fractional part and an integer part. We multiply both of them by k. The integer part doesn’t matter to us, since we are inside the frac function. The fractional part, which is \{p\alpha\} will not be rounded off when we multiply it by k, unless it is larger than than \dfrac{1}{k} .
Let us mark by N the largest integer such that \{p\alpha\} < \dfrac{1}{N} . We can now construct a series in the following manner:

0, \{p\alpha\}, \{2p\alpha\}, \{3p\alpha\}...\{Np\alpha\}

Since \{p\alpha\} < \dfrac{1}{N} , the distance between each one of these is the same, and is equal to \{p\alpha\}.
Lets divide the region [0,1] into N+1 segments. The first N segments will each be of the size \{p\alpha\}, starting from 0. The last segment will be what remains, which is from \{Np\alpha\} to 1.
Now we will prove the density. Take any number x in [0,1]. If this number is inside any of the first N segments, then we are done, because the length of each segment is \{p\alpha\}, and we have seen earlier that it is smaller than \varepsilon .
What if x is in the last segment? A little basic algebra will help. We have said that N is the largest number such that \{p\alpha\} < \dfrac{1}{N}. This inherently means that \{p\alpha\} > \dfrac{1}{N+1} . Multiplying both sides by N, we get:

\{Np\alpha\} > \dfrac{N}{N+1}

Subtracting both terms from 1 (note the reversal):

1 - \{Np\alpha\} < 1 - \dfrac{N}{N+1}
1 - \{Np\alpha\} < \dfrac{1}{N+1}

In English – the distance between \{Np\alpha\} and 1 is smaller than \dfrac{1}{N+1}. But that distance is exactly the length of the last segment. Since it is smaller than \dfrac{1}{N+1}, is it also smaller than \{p\alpha\}, which in turn, is smaller than \varepsilon, and we are done.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s