# 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? Oct 21, 2012 at 17:09
• Yes, of course. Oct 21, 2012 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]? Oct 21, 2012 at 17:21
• 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, 2012 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/… Feb 11, 2014 at 14:53
• @Lost1 Hmmm... I was wondering what caused the sudden renewed interest for this answer. Thanks for the appreciation.
– Did
Feb 11, 2014 at 15:26
• I guess the "and certainly for $c = 42$" bit was just to check that we were all paying attention. When I saw it I got suspicious and started to work on my own solution - taking 'harmonic $1/n$ steps'. +1 for a sense of humor! Sep 7, 2017 at 4:01

[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$$

This is the 'harmonic two-step' solution

Let $\mathbb{Q}_1 = [0,1] \cap \mathbb{Q}$.

Proposition 1: There exist an injective enumeration $q: \mathbb{N} \to \mathbb{Q}_1$ satisfying

$\tag 1 \text{For all } n \gt 0 \text{, } \; \; \; \frac{1}{2n} \le |q_{n} - q_{n-1}| \le \frac{1}{n}$ $\tag 2 \text{For all } n \gt 1 \text{, } \; \; \; 0 \lt q_{n} \lt 1$ Proof: Exercise.

Proposition 2: For any given $\hat q \in \mathbb{Q}_1$ there exist an injective enumeration $q: \mathbb{N} \to \mathbb{Q}_1$ satisfying (2) and

$\tag {1'} \text{For all } n \gt 0 \text{, } \; \; \; |q_{n} - q_{n-1}| \le \frac{1}{n}$ $\tag 3 \text{There exists a } m \in \mathbb{N} \text{ with } q_m = \hat q$ Proof: Exercise.

Proposition 3: There exist a bijective enumeration $q: \mathbb{N} \to \mathbb{Q}_1$ satisfying

$\tag {1'} \text{For all } n \gt 0 \text{, } \; \; \; |q_{n} - q_{n-1}| \le \frac{1}{n}$

Proof (critics might justly call it hand-waving)

Set $q_0 = 0$ and $q_1 = 1$ and with $n = 2$ just take a step of $-\frac{1}{2}$ to the left, and set $q_2 = .5$. For your next $\frac{1}{3}$ step, you can go left or right, so continue going left, setting $q_3 = q_2 - \frac{1}{3} = \frac{1}{6}$. You can continue taking these harmonic steps to your hearts content, but if you hit on a duplicate just start bisecting the step as specified by (1).

Looking at your favorite bijective correspondence $\mathbb{N} \equiv \mathbb{Q}_1$, you notice that you still haven't 'stepped on' the fifth number $\hat q$ on that list. But, with $n$ large enough, you can take harmonic (1)-adjusted steps towards that number ending on either an exact hit (uhh, very low odds) or straddling it. But instead of taking a straddle step, just adjust it for a direct hit. You can then continue taking harmonic (1)-adjusted steps to get to any number in $\mathbb{Q}_1$ still needing a '$q$ hit' check-mark.

So you can make further adjustments to 'get-em all', completing this do-si-do dance step proof.