# Summable enumerations of $\Bbb Q$

We say that a set of natural numbers $A$ is summable if $\sum_{n\in A}\frac1n$ is finite. It is not hard to see that $\{A\subseteq\Bbb N\mid A\text{ is summable}\}$ is an ideal on $\Bbb N$:

• Subsets of summable sets are summable.
• The union of two summable sets is summable.
• The intersection of any number of summable sets is summable.
• Every finite set is summable.
• $\Bbb N$ is not summable.

Given an enumeration of $\Bbb Q$, we say that it is summable at $q$, or that $q$ is a summable point for the enumeration, if $\{n\mid q_n<q\}$ is summable. And the enumeration is summable if it is summable at each rational point.

It is not hard to see that if $A$ is an infinite summable set, then we can pick any $q\in\Bbb Q$ and we can find an enumeration of $\Bbb Q$ such that $A=\{n\mid q_n<q\}$ (simply take a bijection between $A$ and $\{p\in\Bbb Q\mid p<q\}$ and a bijection of $\Bbb N\setminus A$ with $\{p\in\Bbb Q\mid q\leq p\}$ as the enumeration). So each rational is a summable point for the enumeration.

Question. Is there a summable enumeration of $\Bbb Q$?

This can be translated into a slightly more order theoretic question about the ideal of summable sets:

Question (Reinterpreted). Is there an infinite partition of $\Bbb N$ into infinite summable sets?

If the answer is positive, then by taking such partition into $A_n$'s we can enumerate the negative rationals by $A_0$, then the rationals in the interval $[n-1,n)$ by $A_n$ for $n>0$. It is not hard to see that this enumeration is summable; and vice versa if we are given a summable enumeration, this method produces an infinite partition of $\Bbb N$ into infinite summable enumerations.

• I'm completely unsure about the tags. So feel free to chime in. – Asaf Karagila Sep 23 '14 at 4:51
• People seem to have come up with different solutions for reinterpreted question that solves the original question. Instead of posting a new question, I'll throw a possibly not so difficult variation into the comments. How about finding an enumeration of $\mathbb{Q}$ such that no open interval is summable? – Burak Sep 23 '14 at 5:35
• @bof: What I had in mind was the obvious interpretation: (a,b) is summable if $\{n: a<q_n<b\}$ is summable. I did not bother posting a new question because as in your hint we could start with an infinite collection no element of which is summable, but then we will have to repeat the process for each piece and for each piece of these pieces... and so on. That's the obvious way to attack. However the process is kind of working backwards compared to the question, so I wasn't able to figure out whether we can actually write down a map. – Burak Sep 23 '14 at 5:56
• @Burak: I actually started by asking about nowhere summable enumerations too. But if $q_n$ is a summable enumeration, then $p_n=-q_n$ is nowhere summable enumeration. I suppose that asking about all the open intervals does indeed turn this into a bit more difficult question. But it seems that you guys got it covered nicely. – Asaf Karagila Sep 23 '14 at 6:07
• @Ali: No, it has nothing to do with it. – Asaf Karagila Feb 12 '15 at 8:32

## 5 Answers

Let $A$ be some infinite summable set, say, $A=\{1,10,100,\dots\}$.

Partition $A$ into infinitely many disjoint infinite subsets $A_1,A_2,A_3,\dots$.

Let $\mathbb N\setminus A=\{b_1,b_2,b_3,\dots\}$.

Then $\mathbb N$ is the union of the disjoint infinite summable sets
$$A_1\cup\{b_1\},A_2\cup\{b_2\},A_3\cup\{b_3\},\dots.$$

Here's another take on the reinterpreted question:

Let $A_0 = \{a^2 : a \in \mathbb{N}\}$ be the set of all perfect squares. Let $A_1 = \{a + 1: a \in A_0\} - A_0$. And inductively, define $$A_n = \{a + n: a \in A_0\} - \bigcup_{i < n} A_i$$

So this just shifts the perfect squares, and throws away anything that was already seen. Since the squares grow arbitrarily long apart, each of these sets will be nonempty (and indeed infinite), and are summable since they are spaced the same as perfect squares.

It's also not hard to see that this is a partition of $\mathbb{N}$.

Here's an answer to your reinterpreted question.

Associate to each natural number $m$ except $0$ and $1$ the pair $(p,k)$, such that

1. $p$ is the least prime appearing in the factorization of $m$,
2. $m = p^n k$ for some $n$, and
3. $p$ does not divide $k$

Let $A_{p,k}$ be the set of natural numbers associated to $(p,k)$. This is nonempty whenever $p$ is prime and all primes dividing $k$ are greater than $p$. Then $A_{p,k} = \{p^nk\mid n\geq 1\}$, which is summable - it's a geometric series.

This gives an infinite partition of $\mathbb{N}\setminus \{0,1\}$ into infinite summable sets. 0 can't be in any summable set, so you'd better leave it out, but you can add $1$ to any of the sets $A_{p,k}$, and it will still be summable.

• I think we can safely ignore the issue about $0$ here. Either by assuming the convention that $0\notin\Bbb N$ or by agreeing to a ad hoc definition that $\frac10=0$. I tried my best to ignore this issue from the start of my post, too. – Asaf Karagila Sep 23 '14 at 5:13
• I totally agree, I was just being pedantic. But this construction does what you want, no? – Alex Kruckman Sep 23 '14 at 5:16
• I think so, I have to go for a bit, but when I'm back I'll give it a more thorough reading. – Asaf Karagila Sep 23 '14 at 5:17
• Yeah, this answer does the trick. Although, truth be told, bof's answer is a much nicer solution. – Asaf Karagila Sep 23 '14 at 6:20
• A matter of taste, I suppose... bof's is a very clever trick, but this seems to me to be the most natural solution. The fact that $\mathbb{N}$ can be partitioned into geometric series is rather fundamental, and it immediately solves the problem. – Alex Kruckman Sep 23 '14 at 6:27

For every natural number $n \ge 1$ define its support $\text{supp}(n)$ to be the set of prime divisors of $n$. We get a surjective map from $\{1,2,3, \ldots,\}$ to the set of finite parts of the set of prime numbers. $$\text{supp} \colon \mathbb{N}_{>0} \to \mathcal{P}_{fin}(P)$$ Each nonvoid finite subset of $P$ (the primes ) has an infinite fiber which is clearly summable (Euler's proof of the infinity of the number of primes), with an easy calculable sum ( a product of geometric series).

We got in this way a natural partition of the set of natural numbers $>1$ into a countable family of infinite summable sets.

• Yes, that works too. However, think of Euler's proof. It was a big deal to note that the sum of reciprocal of any fixed positive power of naturals with a given finite set of prime divisors is finite. For eg this trick shows right away that for a polynomial function $P(\cdot)$ the set of primes dividing some $P(n)$ is infinite because $\sum_n\frac{1}{P(n)^{\frac{1}{\deg P}}} = \infty$ – orangeskid Sep 23 '14 at 7:59
• @bof: The partition you mention is obtained by grouping the other partition into groups of finitely many parts. So they are in a way equivalent. I also like your clever trick for the other partition. – orangeskid Sep 23 '14 at 8:07
• It's nice because this is a much more number theoretic answer than the others (although Alex's comes close). – Asaf Karagila Sep 23 '14 at 11:32

A very nice question (as can be seen from the large number and diversity of the answers already given)! There's another solution that came to my mind, but it looks so obvious to me that I wonder why nobody has posted it yet. Did I get anything wrong in the definition? Anyway, here it is:

For a nonnegative integer $n\in\mathbb{N}_0$, let $P_n=\{(2n+1)\cdot2^k\,|\,k\in\mathbb{N}_0\}$. Then the sets $P_0$, $P_1$, ... form an infinite partition of $\mathbb{N}$ into infinite summable sets.