# Total distance traveled when visiting all rational numbers

My students found an old problem given in my school in 2007 (probably from a Honor Calculus class) and had been trying to solve for some time. Here is the problem:

Prove or disprove: there exists a bijection $a$ from $\mathbb N$ onto $\mathbb Q$ such that $\sum_{n=1}^\infty (a_n-a_{n+1})^2$ is convergent. (With $a_n=a(n)$)

I have to confess that I am clueless on the method to deal with this problem. My intuition is that the sum represents the square of the distance traveled when visiting all rational numbers, but there is so many rationals that the sum should be infinite. On the other hand, the density of Q means that I can travel the distance between consecutive rationals of my travel can be arbitrarily small, so I am confused...

The only thing we could prove is that $\sum(a_n-a_{n+1})$ is divergent (otherwise, $\{a_n\}$ would be bounded, a contradiction).

Any clue is welcome.

• You can do this. Let $a$ be any bijection from $\mathbb{N}$ onto $\mathbb{Q}$. Make a new sequence: Insert rationals between $a_1$ and $a_2$ so that the sum of squared distances is at most $1/2$ between $a_1$ and $a_2$. Do the same between $a_2$ and $a_3$, so that the sum is at most $1/4$. You will be inserting things from later on in the $a_n$, but this is fine; you simply mark those off your list of places to visit. Also, you can always find plenty of rationals between your current point and your next destination, because you will only ever have used up finitely many rationals so far. – Eric Tressler Nov 8 '16 at 4:45
• I find @EricTressler's comment to be the clearest answer. – Carsten S Nov 8 '16 at 18:53
• "My intuition is that the sum represents the square of the distance traveled when visiting all rational numbers," Luckily no, it's way smaller. $\sum d_i^2 \le (\sum |d_i|)^2$ – leonbloy Nov 8 '16 at 22:16
• I was going to say this is disturbing, but it's actually not; squaring makes the summands much smaller. The smaller the distance, the smaller its square. – Matt Samuel Nov 8 '16 at 23:36

My intuition says yes (there exists). Choose $a$ so that $a_n-a_{n+1}\leq \frac{1}{n}$; since $\sum_n\frac{1}{n^2}$ converges, if you can indeed choose one such $a$ you should be fine. Now, because $\sum_n\frac{1}{n}$ diverges, you could in principle take steps that are roughly that length and still get to 'cover all of $\mathbb{Q}$'. I might try and make this more precise.

EDIT: Making it precise.

Choose any bijection $f:\mathbb{N}\longrightarrow \mathbb{Q}$. We will obtain $a$ from $f$ inductively as follows.

First, let $a(1)=f(1)$. Now, if $|f(2)-a(1)|\leq \frac12$, we set $a(2)=f(2)$. Otherwise, we set $a(2)=a(1)\pm\frac12$, whichever sign brings $a(2)$ closer to $f(2)$. Then, if |$f(2)-a(2)|\leq \frac13$, we set $a(3)=f(2)$; otherwise we set $a(3)=a(2)\pm \frac13$, whichever signs brings $a(3)$ closer to $f(2)$. We proceed in this manner until we each $f(2)$, then we move onto $f(3)$, and so on.

Observations:

• Because $\sum_n\frac{1}{n}$ diverges, we will always reach the next $f(n)$ in finite time.
• Of course, since $f$ is a bijection, our intermediate $a(k)$'s may step onto some of the $f(n)$'s prematurely. If, after reaching some $f(n)$, $f(n+1)$ has already been previously assigned to some $a(k)$, we simply skip $f(n+1)$ and proceed to $f(n+2)$. Notice that, at any point in the induction, $a$ will be defined at a finite number of points so there may be at most a finite number of skips, and the process can always continue.
• Finally, if when defining $a(k+1) = a(k) \pm \tfrac1k$ the RHS is already taken, simply choose another rational $r$ near $a(k) \pm \tfrac1k$, say $\left|r-\left(a(k) \pm \tfrac1k\right)\right|\leq\tfrac{1}{2k}$, and put $a(k+1)=r$.

These observations guarantee that this inductive process can always continue and will eventually reach every rational. It uses the axiom of choice near the end, and I believe there's a way not to use it: look for

\begin{align} &a(k) \pm \tfrac1k\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\pm\tfrac{1}{4k}\\ &a(k) \pm \tfrac1k \mp\tfrac{1}{2k}\pm\tfrac{1}{4k}\mp\tfrac{1}{8k}\\ &\dots \end{align}

until you find one that's not yet been used. But honestly I'm not too worried about it.

• If moving a full $\frac{1}{k}$ doesn't work because $a(k)\pm\frac{1}{k}$ has already been visited, you could move $(\frac{1}{k}-\frac{1}{2^k})$ instead. Or if that's already taken, you could move $(\frac{1}{k}-\frac{1}{2^{k+1}})$. Or $(\frac{1}{k}-\frac{1}{2^{k+2}})$, etc. Since at every stage you've only exhausted finitely many values, you can always find one of these moves that will work. (Cont'd) – mathmandan Nov 8 '16 at 5:54
• (Cont'd) If you follow this procedure, you're always guaranteed to move at least $(\frac{1}{k}-\frac{1}{2^k})$. Since $\sum(\frac{1}{k}-\frac{1}{2^k})\geq \sum(\frac{1}{2k})$ diverges, you always need only finitely many steps to move from any rational to any other rational. And since you always move at most $\frac{1}{k}$, the sum of the squared steps converges. – mathmandan Nov 8 '16 at 5:55
• @Fimpellizieri Nice proof. You don't, in fact, need the axiom of choice near the end. You can do it the way you suggested, or you can just set $a(k+1)$ equal to the first rational in a standard enumeration of $\mathbb{Q}$ that is between $a(k)\pm \frac1{2k}$ and $a(k)\pm \frac1{k}$ and that isn't $a(j)$ for any $j \le k.$ – Mitchell Spector Nov 8 '16 at 17:06

Here's an idea (it'll take some work to flesh it out into a proof, but you asked for a clue, so...):

At some point I need to get from, say, $0$ to $1$ - I have to hit one of them, and then the other at some later time. Now, this looks like distance $1$, which is fine - IF I don't have to do steps like it very often. But I also have to do $1$ to $2$, $2$ to $3$, and so on; so I need to make it smaller. But $0, \frac{1}{2}, 1$ only has cumulative distance-squared equal to $\frac{1}{2}$. $0, \frac{1}{4}, \frac{1}{2}, \frac{3}{4}, 1$ has cumulative distance-squared of only $\frac{1}{4}$.

The cool thing is that I can do this with any interval I like. So imagine taking any enumeration of $\mathbb{Q}$ you like and inserting elements in between to "shrink" the steps involved so that each successive step of the original enumeration has smaller and smaller cumulative distance-squared in the new one - say, shrinking like $2^{-n}$.

This isn't complete - I've been very vague about lots of stuff, and I haven't said how to deal with the fact that the enumeration you end up with (at least the one I'm visualizing) visits most of the rationals many times; but you might be able to fill in the gaps.

I will expand my comment into an answer (though still not a formal proof).

Lemma: Given rationals $a < b$, $\epsilon > 0$, and any finite set $S$, there exist rationals $k_1,\ldots,k_n \not\in S$ such that $$(k_1 - a)^2 + \sum_i (k_{i+1} - k_i)^2 + (b - k_n)^2 < \varepsilon.$$

Sketch of proof: Note that by inserting a single rational $c$ in the interval $\left[\frac{3a+b}{4},\frac{a+3b}{4}\right]$, we have $$(b-a)^2 \leq \frac{5}{8}\left((c-a)^2 + (b-c)^2\right).$$ We can always do this, because that interval contains infinitely many rationals, and so in particular it contains a rational that is not in $S$. Keep doing this until the sum of squared distances is less than $\varepsilon$.

Now let $(a_n)$ be any enumeration of the rationals. Form a new enumeration of the rationals as follows: Let $b_{n_1} = b_1 = a_1$. Insert as many rationals $b_2, \ldots, b_{n_2-1}$ as necessary so that when finally $b_{n_2} = a_2$, we have $$\sum_{i=1}^{n_2-1} (b_{i+1} - b_i)^2 < 1/2.$$

Let $b_{n_3}$ be the next unvisited member of $(a_n)$. Continue like this, inserting rationals $b_{n_2+1},\ldots,b_{n_3-1}$ so that $$\sum_{i=n_2}^{n_3-1} (b_{i+1} - b_i)^2 < 1/4.$$

At each step, the forbidden set $S$ is simply the sequence $(b_n)$ that has been defined so far. We take finitely many steps to reach $a_1$, and then $a_2$, and so on, so $(b_n)$ is also an enumeration of the rationals. Moreover, $\sum_i (b_{i+1} - b_i)^2 < 1$.

My intuition says no.

Let $a_{n_1} := 0, a_{n_q} := q \in \mathbb{N}$

Then $q^2 = (a_{n_1} - a_{n_q})^2 \leq \sum_{n = 1}^{\max(n_1,n_q)} (a_n - a_{n+1})^2$ By the triangle inequality.

We know that $n_q \to \infty$ as $q \to \infty$ (because $a$ is a bijection, and the rationals are unbounded)

Hence $\sum_{n = 1}^{\infty} (a_n - a_{n+1})^2$ diverges.

• $a_0=0,a_1=1,a_2=2$, and yet $(a_0-a_2)^2 > (a_0-a_1)^2+(a_1-a_2)^2$ – Fimpellizieri Nov 8 '16 at 4:36
• Which triangle inequality? Note that $|\cdot|^2$ isn't a norm. – Vim Nov 8 '16 at 4:37

Think of it this way. What you need to make your sum convergent is to make $(a_n - a_{n+1})$ get infinitely close to, but not equal to 0 (otherwise it would not be a bijection). So we should try to eliminate as many options as we can:

Polynomials: Obviously, even-degreed ones can't work. Odd-degreed ones are our only option.

Non-polynomials Categories:

1. sin, cos, etc: disproved by bijection
2. polynomials divided by cases: we'll try this later
3. arrays: we'll try this later

So, for right now, I focused on odd polynomials. Grouping them into ones with positive degrees and negative degrees, I ruled out ones with positive degrees based on their common property of divergence.

Negative degrees look pretty interesting - so let's work with these - starting with $n^{-1}$, or more colloquially, $\frac{1}{x}$.

Theoretically, the limit as n approaches infinity of $(\frac{1}{n} - \frac{1}{n+1})$ is 0, but will never reach 0.

And bam, $\frac{1}{n}$ is your bijection. As a proof, let's replace infinity with rational numbers and test.

1. 0 - 0
2. 10 - 0.28961810696118045
3. 100 - 0.28986781017274627
4. 1000 - 0.28986813336411776
5. 10000 - 0.2898681336961168

We can additionally prove this is convergent by saying that if x is convergent, $x^2$ will be convergent. Therefore, since $(\frac{1}{n} - \frac{1}{n+1})$, then $(\frac{1}{n} - \frac{1}{n+1})^2$ is convergent, and its integral from 0 to infinity will also be convergent.

P.S., no clue why it converges at this exact point or if it has a deep mathematical meaning, and I just saw this and wanted to take a crack at it. Hopefully I didn't screw up and helped you.

• I think you might have confused bijection with injection. Also, the fact that a series converges to 0 doesn't mean the sum of that series converges. $\frac{1}{n}$ is actually one of the simplest counter examples to that. – dimpol Nov 8 '16 at 14:05
• @dimpol You are right about the bijection, but $(\frac{1}{1}-\frac{1}{2})+(\frac{1}{2}-\frac{1}{3})+\dots$ is just 1, since every other term cancles. – Stig Hemmer Nov 9 '16 at 9:51
• Ah, you indeed are correct – dimpol Nov 9 '16 at 12:12