# Convergence of $\sum_{n}\frac{q_n}{n}$, where $(q_n)$ enumerates $\mathbb{Q}\cap[0,1]$?

This problem is from a book reviewed Sep. 2020 Notices of AMS.

Rational numbers in $$[0,1]$$ are countable. Can they be ordered as $$(q_n)_n$$ so that $$\sum_{n=1}^\infty \frac{q_n}{n}$$ converges?

My belief is no, since half the rationals are in the upper half of the interval, the tail of the sum will always have half of its terms $$\gt \frac{1}{2n}$$ implying divergence. I am having difficulty in making this rigorous.

• My impression is that it is possible. You keep choosing lots of small $q_n$'s while you wait for $n$ to grow and then you pick a sporadic large $q_n$.
– Ruy
Sep 24, 2020 at 22:03
• I don't understand the current close vote: "This question currently includes multiple questions in one. It should focus on one problem only." The OP's question seems very clear and focused to me? Sep 24, 2020 at 22:42
• I cannot see close votes yet but if what @ClementC. says is true then I'm deeply worried. This is one of the most interesting question I've seen in days!
– Ruy
Sep 24, 2020 at 22:49
• @Ruy half of the rational numbers in the interval $[0,1]$ are in the interval $[1/2,1]$ so you can't avoid larger numbers as you describe. Sep 25, 2020 at 2:24
• This comment does not make the OP clearer (at least to me). Sep 25, 2020 at 2:31

Ruy makes a good point in the comments you could possibly formalise it as follows.

Consider any ordering of the rational numbers in $$[0,1]$$ and remove those elements of the form $$\frac{1}{n}$$ where $$n$$ is a positive integer which is not a positive power of $$2$$.

This leaves the sequence $$\{a_n\}_{n=1}^\infty$$

Then define $$q_n = \left\{ \begin{array}{ll} a_{\log_2 n}, \text{ if n is a positive power of 2}\\ \frac{1}{n}, \text{ otherwise}\\ \end{array} \right.$$

This will imply that $$\displaystyle \sum_{n=1}^{\infty} \frac{q_n}{n} < \sum_{n=1}^{\infty} \left( \frac{1}{n^2} + \frac{1}{2^n} \right) = \frac{\pi^2}{6} + 1$$

• Maybe I'm missing something, but it looks like this can be slightly modified to generalize to any decreasing function $f$ s.t. $\lim_{n\to\infty}f(n) = 0$, instead of $1/n$ (i.e., $\sum_n q_n f(n)$). Is that correct? Sep 24, 2020 at 22:57
• @hexamino I guess I wasn't clear enough in my statement. $q_n$ are the rational numbers in some order, NOT functions of the rational numbers. Sep 25, 2020 at 2:21
• @hexamino What happened to all the rationals m/n where n is not a power of 2 and m > 1? Sep 25, 2020 at 2:31
• @herb the result is correct as you get all the rationals except the $1/n, n \ne 2^k$ in a sequence $a_m$ and then you insert $a_1$ at $2$, $a_2$ at $4$, $a_3$ at $8$, $a_m$ at $2^m$ so all those get inserted but farther and farther, while at the rest of the $n$ you just insert the respective $1/n$ Sep 25, 2020 at 2:46
– Ruy
Sep 25, 2020 at 3:30

Here is a proof of the conjecture made by @ClementC, with an improvement suggested by @TSF.

Theorem. Given any bounded function $$f:\mathbb N\to \mathbb R_+$$ admitting a subsequence $$\{f(n_k)\}_k$$ that converges to zero, there is an enumeration $$\{q_n\}$$ of the rationals in $$[0,1]$$ such that $$\sum_nq_nf(n)<\infty.$$

Proof. By hypothesis there are arbitrarily small elements in the range of $$f$$ so we may choose an infinite subset $$N_1\subseteq \mathbb N$$ such that $$\sum_{n\in N_1}f(n)$$ converges. By discarding infinitely many elements from $$N_1$$, if necessary, we may assume that $$N_2:=\mathbb N\setminus N_1$$ is also infinite.

Furthermore let $$Q_1$$ be the set of rationals defined by $$Q_1=\{1/2^n: n\in \mathbb N\},$$ and let $$Q_2$$ be the complement of $$Q_1$$ in $$\mathbb Q \cap [0,1]$$.

All sets so far defined are countably infinite, so there are bijections $$\alpha :N_1\to Q_2,$$ $$\beta :N_2\to Q_1.$$ The union of $$\alpha$$ and $$\beta$$ is therefore a bijection, $$\gamma :\mathbb N\to \mathbb Q \cap [0,1]$$ which is the enumeration we are looking for, that is, $$q_n=\gamma (n)$$. We then have that \begin{align} \sum_{n\in \mathbb N} q_nf(n) &= \sum_{n\in N_1} \gamma (n)f(n) + \sum_{n\in N_2} \gamma (n)f(n) \\&= \sum_{n\in N_1} \alpha (n)f(n) + \sum_{n\in N_2} \beta (n)f(n) \\&\leq \sum_{n\in N_1} f(n) + \|f\|_\infty\sum_{n\in \mathbb N} 1/2^n < \infty. \tag*{\blacksquare} \end{align}

• I get it! $N_1$ and $Q_1$ are sparse sets, but still infinite, so $N_1$ gets matched with most of the points $(Q_2)$ and the sum converges, because of $N_1$. Similarly the other pair converges because of $Q_1$. Sep 25, 2020 at 3:52
• That's exactly it. Thanks for a very interesting question. I'd be curious to know the title of the book reviewed in the Notices where this problem comes from.
– Ruy
Sep 25, 2020 at 3:59
• I don't think you need $f_n$ to go to $0$. You just need it to be bounded and have a summable subsequence. For this the latter it's enough to assume that there is a subsequence $f_{n_k}$ which goes to $0$. Sep 25, 2020 at 8:03
• @TSF, you are right. Assuming you allow me to I edited to include your suggestion.
– Ruy
Sep 25, 2020 at 12:53
• @Ruy Book - "Bicycle or Unicycle: A collection of Intriguing Mathematical Puzzles" by Velleman and Wagon. Sep 25, 2020 at 17:41