# 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?

-
Presumably, you mean a $1-1$ enumeration? – Thomas Andrews Oct 21 '12 at 17:09
Yes, of course. – Lost1 Oct 21 '12 at 17:14

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.

-
n=0, k=1, I think we get the interval (1,2]? – Lost1 Oct 21 '12 at 17:21
@Yufan - must have $k<2^n=2^0=1$. – James Fennell Oct 21 '12 at 17:22
Call a term of the enumeration high if it is in (3/4,1) and low if it is in (0,1/4). There are infinitely many highs and lows. A subsequence of $(q_n)$ is such that every $q_{\varphi(2n)}$ is high and every $q_{\varphi(2n+1)}$ is low. And |high$-$low| is always at least 1/2. QED. – Did Oct 22 '12 at 5:25
I am extremely glad to seethis answer at last got a 'good answer' badge after some promotion here: math.stackexchange.com/questions/671076/… – Lost1 Feb 11 '14 at 14:53
@Lost1 Hmmm... I was wondering what caused the sudden renewed interest for this answer. Thanks for the appreciation. – Did Feb 11 '14 at 15:26

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.

-