17
$\begingroup$

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.

$\endgroup$
8
  • 7
    $\begingroup$ 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$. $\endgroup$
    – Ruy
    Sep 24, 2020 at 22:03
  • 2
    $\begingroup$ 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? $\endgroup$
    – Clement C.
    Sep 24, 2020 at 22:42
  • 3
    $\begingroup$ 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! $\endgroup$
    – Ruy
    Sep 24, 2020 at 22:49
  • $\begingroup$ @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. $\endgroup$ Sep 25, 2020 at 2:24
  • $\begingroup$ This comment does not make the OP clearer (at least to me). $\endgroup$
    – markvs
    Sep 25, 2020 at 2:31

2 Answers 2

13
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$
    – Clement C.
    Sep 24, 2020 at 22:57
  • $\begingroup$ @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. $\endgroup$ Sep 25, 2020 at 2:21
  • $\begingroup$ @hexamino What happened to all the rationals m/n where n is not a power of 2 and m > 1? $\endgroup$ Sep 25, 2020 at 2:31
  • $\begingroup$ @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$ $\endgroup$
    – Conrad
    Sep 25, 2020 at 2:46
  • 1
    $\begingroup$ @ClementC, please see below a proof of your conjecture. $\endgroup$
    – Ruy
    Sep 25, 2020 at 3:30
8
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ Sep 25, 2020 at 3:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ruy
    Sep 25, 2020 at 3:59
  • 1
    $\begingroup$ 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$. $\endgroup$ Sep 25, 2020 at 8:03
  • 1
    $\begingroup$ @TSF, you are right. Assuming you allow me to I edited to include your suggestion. $\endgroup$
    – Ruy
    Sep 25, 2020 at 12:53
  • 1
    $\begingroup$ @Ruy Book - "Bicycle or Unicycle: A collection of Intriguing Mathematical Puzzles" by Velleman and Wagon. $\endgroup$ Sep 25, 2020 at 17:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .