Enumerations of the rationals with summable gaps $(q_i-q_{i-1})^2$

Here is a question from my undergraduate days which I never knew the answer to. I just want to know if anyone can offer me a hint.

Consider the rationals in $[0,1]$. Does there exist a (bijective) enumeration of these rationals $q_1,q_2,\ldots$ such that the sum $\sum\limits^\infty_{i=1} (q_i-q_{i-1})^2$ is finite?


Solution 1:

Summary:

  • There exists a (bijective) enumeration $(q_i)_{i\geqslant0}$ of the rationals in $[0,1]$ such that, for every $a\gt1$, the series $\sum\limits_i|q_i-q_{i-1}|^a$ converges.

  • This result is optimal in the sense that no (bijective) enumeration $(q_i)_{i\geqslant0}$ of the rationals in $[0,1]$ is such that the series $\sum\limits_i|q_i-q_{i-1}|$ converges.

Let us show the first point. For every $n\geqslant0$ and $0\leqslant k\lt 2^n$, define the interval $I_{2^n+k}$ as $$I_{2^n+k}=\left\{\begin{array}{ll}(k\cdot2^{-n},(k+1)\cdot2^{-n}]&\text{if $n$ is even},\\ (1-(k+1)\cdot2^{-n},1-k\cdot2^{-n}]&\text{if $n$ is odd}.\end{array}\right. $$ Thus, for every $n\geqslant0$, $(I_{2^n+k})_{0\leqslant k\lt 2^n}$ is a partition of $(0,1]$ into $2^n$ intervals of length $2^{-n}$. For every $i\geqslant 2^n$, if $x$ is in $I_i$ and $y$ in $I_{i+1}$, then $|x-y|\leqslant c\cdot2^{-n}$, probably for $c=2$ and certainly for $c=42$.

Define recursively $(q_i)_{i\geqslant0}$ as follows: let $q_0=0$ and, for every $n\geqslant0$ and $0\leqslant k\lt 2^n$, let $q_{2^n+k}$ denote the rational in $I_{2^n+k}$ not already in $\{q_i\mid i\lt 2^n+k\}$ whose reduced fraction has minimal denominator and, if several such rationals exist, minimal numerator.

Then $(q_i)_{i\geqslant0}$ enumerates the rationals in $[0,1]$. Furthermore, for every $n\geqslant0$, if $2^n\leqslant i\lt 2^{n+1}$, then $$|q_i-q_{i-1}|\leqslant c\cdot2^{-n}.$$ Hence the slice of the sum $\sum\limits_i|q_i-q_{i-1}|^a$ for $2^n\leqslant i\lt 2^{n+1}$ is at most $$2^n\cdot(c\cdot2^{-n})^a=c^a\cdot2^{-(a-1)n}.$$ Since $a\gt1$, summing these shows that the complete series converges. QED.


The fact that the series $\sum\limits_i|q_i-q_{i-1}|$ diverges for every enumeration is easy. Define recursively the sequence $(N(n))_{n\geqslant0}$ as follows: let $N(0)=0$ and, for every $n\geqslant0$, let $N(n+1)$ denote the smallest integer $i\geqslant N(n)$ such that $$ |q_i-q_{N(n)}|\geqslant\tfrac12. $$ Then $N(n)$ is finite for every $n$ (why?) and the triangular inequality yields $$\sum\limits_i|q_i-q_{i-1}|\geqslant\sum\limits_n|q_{N(n)}-q_{N(n-1)}|\geqslant\sum\limits_n\tfrac12, $$ which is infinite.

Solution 2:

[EDIT: The argument below traverses all of the rational numbers instead of just the rational numbers in $[0,1]$.]

You can define the sequence $u_n$ in such a way that it moves from 0 to 1 in steps of $\frac{1}{1!}$, from to 1 to -1 in steps of $\frac{1}{2!}$, and from -1 to 2 in steps of $\frac{1}{3!}$ etc.

To get a good intuition for this solution, you can start by solving a different problem, which is enumerating all numbers with a finite decimal expansion. This can be done by moving from 0 to 1 in steps of size 0.1, from 1 to -1 in steps of 0.01, and then from -1 to 2 in steps of 0.001 etc. Since you want it to be a bijection, you simply skip over any point you've previously visited. Call this sequence $v_n$. The summation $\sum_{r=1}^{\infty} (v_r - v_{r-1})^2$ can be upper-bounded as $4(10 \times 0.1^2 + 20 \times 0.01^2 + 30 \times 0.001^3 + \ldots) = 4 \sum_{r=1}^{\infty} 10r \times 10^{-2r}$ which is clearly convergent. The multiplication by 4 came from the fact that every time you skip a point, the difference squared multiplies by 4, so to give an upper bound multiply the whole thing by 4.

Clearly, that's going to miss out on every rational number with an infinite decimal. So instead of using steps of 0.1, 0.01 etc. go in steps of $\frac{1}{1!}$, $\frac{1}{2!}$, $\frac{1}{3!}$ etc. Again, skip points you've already visited. Now construct an upper bound for $\sum_{r=1}^{\infty} (u_r - u_{r-1})^2$, which is $4( 1 \times 1! \times \frac{1}{1!^2} + 2 \times 2! \times \frac{1}{2!^2} + 3 \times 3! \times \frac{1}{3!^2} + \ldots) = 4 \sum_{r=1}^{\infty} r \times r! \times \frac{1}{r!^2} = 4 \sum_{r=1}^{\infty} \frac{1}{(r-1)!} =4e$ which is finite.


EDIT:

There is nothing special about the rational numbers in this problem.

Theorem: If a subset $S$ of the real numbers $\mathbb R$ is countable and dense in $\mathbb R$, then $S$ is traversable with summable gaps.

(Remark: In particular, this means that the rational numbers can be replaced by a more general set like the real algebraic numbers and the same result would be true.)

Proof: Let $s_i$ be an arbitrary enumeration of $S$. Let $\text{boundary}_n$ be a sequence that moves from $0$ to $1$ in steps of $0.1$; from $1$ to $-1$ in steps of $0.01$; from $-1$ to $2$ in steps of $0.001$; etc. Let $\text{traversal}_n$ be the first element of $s_i$ in between $\text{boundary}_n$ and $\text{boundary}_{n+1}$ that hasn't previously been visited. By first element, we mean the element $s_i$ with the smallest value of $i$ that meets our condition. The sequence $\text{traversal}_n$ then visits every element of $S$ exactly once, and the upper bound on the sum is at most $4\sum_{n=0}^\infty r10^{-r} < 0.5$; the multiplication by $4$ comes from assuming the largest possible distance between $\text{traversal}_n$ and $\text{traversal}_{n+1}$.

$\blacksquare$