# 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

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.

For every $n\geqslant0$ and $0\leqslant k\lt 2^n$, define the interval $I_{2^n+k}$ as $I_{2^n+k}=(k\cdot2^{-n},(k+1)\cdot2^{-n}]$ if $n$ is even and as $I_{2^n+k}=(1-(k+1)\cdot2^{-n},1-k\cdot2^{-n}]$ if $n$ is odd. 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}$, $|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.

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_{i-1}|\geqslant\frac12$. 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\frac12$, 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
@Yufan: $I_1=(0,1]$, $I_2=(1/2,1]$, $I_3=(0,1/2]$, $I_4=(0,1/4]$, $I_5=(1/4,1/2]$, $I_6=(1/2,3/4]$, $I_7=(3/4,1]$, $I_8=(7/8,1]$, $I_9=(3/4,7/8]$... – Did Oct 21 '12 at 17:23
I was thinking about $I_2$ but yes, sorry. $k<2^n$ – Lost1 Oct 21 '12 at 17:25
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

Yes. For an enumeration to work, it is enough that for any $i \in \mathbb{N}$, $|q_{i+1} - q_i| \leq \frac{1}{2}$. It should not be too difficult to justify the existence of such enumeration.

Edit : more detail Divide the set of rationals in $[0,1]$ into four sets : $[0,1/4] \cap \mathbb{Q}$, $[1/4,1/2] \cap \mathbb{Q}$, $[1/2,3/4] \cap \mathbb{Q}$ and $[3/4,1] \cup \mathbb{Q}$. Each set is countable, pick for each an enumeration $a_{n,i}$, where $1 \leq i \leq 4$ and $n$ is an integer. Consider the enumeration $a_{1,1}$, $a_{1,2}$, $a_{1,3}$, $a_{1,4}$, $a_{2,1}$, etc.

Edit : misread the question, doesn't work.

-
it is not a solution just an opinion – Norbert Oct 21 '12 at 16:57
the author said to give a hint. I can detail more if required. – Glougloubarbaki Oct 21 '12 at 16:57
sorry, I didn't read correctly the question. I thought the sum was $\sum_i (q_{i+1} - q_i)^i$. it would have been simpler ! – Glougloubarbaki Oct 21 '12 at 17:04
yes, it certainly would be. haha – Lost1 Oct 21 '12 at 17:06

Take $q_i := \frac{1}{i+1}$, then $\sum_{i=1}^\infty (q_i - q_{i-1})^2 = \frac{\pi^2}{3} - 3$

-
you have used just a small part of all rationals – Norbert Oct 21 '12 at 16:58
someone gave this an accident upvote. lol... – Lost1 Oct 21 '12 at 17:23