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

Question

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?

Answer 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.

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

Answer 3

This is the 'harmonic two-step' solution
(see also "Answer to: Total distance traveled when visiting all rational numbers").

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.