# Infinite Partitions of the Primes and Sums of Reciprocals (Revised)

I have revised my original post. The questions I asked there were not well-put or even thought through. I don't want to delete, however, since some of the comments may be of interest to other MO users.

It is well known that the sums of the reciprocals of the primes diverges. But suppose we decompose the set of prime numbers, call this set $P$, into disjoint infinite sets $\langle A_\alpha\rangle$ in some way to guarantee that each member $A_\alpha$ of the partition has the following "nice" property: $$\Sigma_{p\in A_{\alpha}} \frac{1}{p} \text{ converges}.$$

There are by now several interesting partitions in the comments and answers below. Here I include two of my own attempts at such a partition.

Attempt 1: Let $\langle \epsilon_i: i<\omega\rangle$ be a sequence of positive real numbers be such that $\Sigma_i \epsilon_i$ diverges (goes to infinity). Suppose you want an infinite $X\subseteq P$ such that $$\Sigma_{p\in X}\frac{1}{p} <\epsilon_1.$$ Then inductively define $X_1$ as follows: Pick $p_1\in P$ least such that $\frac{1}{p}<\epsilon_1$. Continuing, suppose $p_1,p_2,\dots,p_n$ have been chosen such that $$\Sigma^n_1\frac{1}{p_i}<\epsilon.$$ Then let $p_{n+1}$ be the least such that $$\Sigma^{n+1}_1\frac{1}{p_i}<\epsilon_1.$$

It seems like we could continue this strategy to produce a partition with the desired property by setting $P=P_1$, and $P_2=P_1\setminus X_1$. Then repeat the process described above. If this stage goes all the way through, define $P_3$, etc. It seems that all the $P_n$s will be defined and each will, by construction converge.

But this sort of strategy seems to depend on the paramater sequence $\langle\epsilon_i\rangle$ in an essential way. It may be constructive, but the strategy doesn't really give me a concrete or satisfying (or even really explicit) definition for the partition.

Attempt 2: I proposed the following partial strategy (based on the Green-Tao Theorem). Index the primes according to their natural order (i.e., $p_1 =2, p_2 =3, p_3=5$, etc.). Let $P=A_1\cup B_1$ where $$n\in A_1\Longleftrightarrow n \text{ has a prime index},$$ and $n\in B_1$ otherwise. Since $B$ has positive upper density, it must contain arbitrarily long arithmetic progressions by the Tao-Green Theorem (see the related question Extension of Tao-Green Theorem). I'm not sure if this means $$\Sigma_{p\in B_1} \text{ diverges }$$ but I think it does.

Also, Ben Green comments there that $A$ must contain arbitrarily long arithmetic progressions since the density of this set is roughly $1/\log^2(N)$ (though this may still be conjecture, I'm not sure).

But suppose we attempt to destroy each such arithmetic progression by decomposing both $A_1$ and $B_1$ in the following way: Re-index both $A_1$ and $B_1$ according to their natural order and partition each by placing an $n$ in one set of the partition if it is indexed by a prime, and placing it in the other set in the partition if it indexed by a composite.

If we repeat the construction $k$ times (for both $A_1$ and $B_1$ and all subsequently formed subsets) we must surely eliminate all arithmetic progressions with common difference $k$. But perhaps there are still arithmetic progressions with common difference $k'>k$. So we continue the iteration, creating a binary tree of height $\omega$, the leaves of which union to all of $P$.

It is still not clear to me that this partition will have the property I requested above. Certainly there are several nice examples in the comments and answers below.

-
Any partition of $P$ an have at most countably many non-empty pieces, Everett. No idea why you are suggesting $2^{\aleph_0}$. –  Andres Caicedo Nov 5 '13 at 3:04
What if you just sort them by distance to the nearest square? –  Lev Borisov Nov 5 '13 at 3:28
@Andres-Thank you! I'm not sure why I asserted that. –  Everett Piper Nov 5 '13 at 3:32

The following is rather more simple-minded that what you are suggesting.

Let's say we have a deck of cards, with the cards labelled by the primes in order. We are going to think of constructing the partition by dealing out the cards into piles; the piles will be the parts of the partition.

The dealing proceeds in rounds. On $n$-th round, we deal out a card to the first $2^n$ stacks.

So, on the zero-th round, we deal out 1 card, onto the zero-th stack. On the first round, we deal out the second card into the zero-th stack, and the third card into the first stack. On the third round, we deal out the fourth card onto the zero-th stack, the fifth card onto the first stack, the sixth card onto the second stack, and the seventh card onto the third stack. And so on.

The first stack therefore gets the first prime number, the second prime number, the fourth prime number, the eighth prime number... The k-th prime number is greater than k, so the sum of the reciprocals converges.

The corresponding reciprocals of other piles are smaller, so they also converge.

And it is clear that all the piles eventually acquire infinitely many cards.

-
This is a very neat (and intuitive) construction! –  Everett Piper Nov 5 '13 at 3:41

There is nothing special going on related to primes or even to integers (see below.) But let me start with the positive integers. What you want can't be harder than partitioning the positive integers similarly. Consider partitioning the positive integers in sequences as follows:

$\ 1,\ 3,\ 6,10,15,21\cdots$

$\ 2,\ 5,\ 9,14,20,\cdots$

$\ 4,\ 8,13,19,26\cdots$

$\ 7,12,18,25,33,\cdots$

$11,\cdots$

The growing triangular pattern should be clear, but to be specific, row $k$ starts with $1+\frac{k(k-1)}{2}$ and then the gaps between successive terms are $k+1,k+2,k+3,\cdots.$

The sum of the reciprocals in the first row is $2$ and each other row has a smaller sum than the one above it.

Now replace $n$ in this partition with the $n$th prime instead to get what you want.

It would be possible to arrange to have the first row converge quite slowly and then have every following row converge even more slowly (but still converge) and that would work as well. More rapid convergence is possible as well. However the scheme above is specific and easy to follow.

Rather than the sequence of reciprocals of integers or primes, assume merely a sequence of positive reals $x_1 \ge x_2 \ge \cdots$ such that

• $\lim x_k =0$ and
• $\sum x_k=\infty.$

Suppose we wish to partition into a countable number of infinite subsequences such that the $m$th subsequence has sum $s_m$ where the values $s_1,s_2,\cdots$ are some positive reals. We can't always do this, for example the sum of the $s_m$ has to diverge and we can't have all the $s_m$ less than $\frac{1}{3}$ if $x_3=\frac{1}{2}$.

Here is a sufficient condition:

• There is a sequence $N_1 \lt N_2 \lt \cdots$ such that $x_m \lt s_{N_m}$

So this allows $s_m=x_m+m!$ (huge sums) or $s_m=x_m(1+\frac1{m!})$ (small sums) as well as a mix of extremely small and extremely large target sums. With this condition we can make the subsequences by the greedy rule of considering the $x_i$ in turn and assigning $x_i$ to subsequence $m$ where $m$ is the smallest possible index such that the partial sum will remain strictly less than $s_m.$ This might mean that it takes longer ( at 10 placements per second) than the life of the universe to put anything in subsequence $2$ (or to put the second member into subsequence $1$), but infinity is much larger.

The condition and greedy rule ensure that $x_m$ will be assigned to subsequence $N_m$ or an earlier one. How do we know that each subsequence is infinite and with the proper sum? Pick any index $m$ and $\varepsilon \gt 0.$ There are $M_1 \lt M_2$ so large that $x_{M_1} \lt \varepsilon$ and $$\sum_{i=M_1}^{M_2}x_i \gt \sum_{j=1}^ms_j.$$ Then there must be some $M_1 \le \ell \le M_2$ with $x_{\ell}$ assigned past sequence $m$. But this requires that the partial sum for subsequence $k$ is at least $s_k-\varepsilon$ for all $1 \le k \le m.$

-
This is another (classic) construction that I hadn't thought about. Thank you! –  Everett Piper Nov 5 '13 at 4:57
A very simple way to obtain such partition of the primes is to put the $n$-th prime into the $k$-th set in the partition, where $k$ is the number of 1's in the binary representation of $n$.