Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 37 down vote accepted

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.

share|improve this answer
    
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
1  
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
2  
@Lost1 Hmmm... I was wondering what caused the sudden renewed interest for this answer. Thanks for the appreciation. –  Did Feb 11 at 15:26
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.