# Partitioning the naturals into an infinite number of large sets

Is it possible to partition the positive integers into an infinite number of disjoint large sets ?

-
Since I was thinking of how to partition into small sets, I'll share my thoughts as a comment rather than an answer. Define for each $n \notin \{0,1\}$ the set $S_n = \{n^k \mid k \in \mathbb{N}\}$ (i.e., $S_n$ contains all powers of $n$). Each $S_n$ is small, since the terms grow exponentially. Now, "disjointify" the $S_n$. That is, let $A_1 = S_1$, $A_2 = S_2 \setminus A_1$, $A_3 = S_3 \setminus (A_1 \cup A_2)$, and so on. The collection $\{A_i \mid i \in \mathbb{N}\}$ is a partition of $\mathbb{N}$ into small sets (provided you throw $0$ into $S_1$, say). –  Austin Mohr Jan 25 '14 at 20:45

Yes. $D=\{1,3,5,7,9,\dots\}$, the set of all odd numbers, is a large set; so is $2D=\{2,6,10,14,18,\dots\}$; so are $4D,8D,16D$, etc.

-
The sets indeed form a partition since every natural number can be written uniquely as $2^m(2n+1)$. –  Austin Mohr Jan 25 '14 at 20:37
I don't quite see how those sets are disjoint. –  E.P. Jan 26 '14 at 2:30
@episanty If an integer was present in any two sets, then it could be written both as $2^x n_1 \in 2^x D$ and $2^y n_2 \in 2^y D$, where $n_1, n_2 \in D$. By the fundamental theorem of arithmetic, this implies that $x = y$ and $n_1 = n_2$. –  Thomas Jan 26 '14 at 2:41
Apologies, I read this too hastily. That's correct, of course. –  E.P. Jan 26 '14 at 2:44

Similar, a squarefree number is $1,2,3,5,6,7,10,11,13,15,\ldots$ so let your disjoint sets be $m n^2$ for squarefree $m.$ These sets are called squareclasses, I like to write it as one word. The equivalence relation is that two numbers are equivalent if and only if their ratio is a rational square. As we are dealing with integers, that is the same as saying that two numbers are equivalent if and only if their product is a square.

This simple idea underlies a good deal of integer coefficient quadratic form theory. In particular, we speak of squareclasses in the $p$-adic numbers $\mathbb Q_p$ and the $p$-adic integers $\mathbb Z_p.$ See, for example, Cassels, Rational Quadratic Forms.

-
@OldJohn, no such number is a square multiple of another. If we had $m_1 n_1^2 = m_2 n_2^2,$ we would then have $m_1 m_2 = k^2$ and $m_1 = m_2.$ –  Will Jagy Jan 25 '14 at 20:51
@OldJohn, took me a while, evidently Maggie was saying she would not celebrate Burns Night any more if Scotland voted to move even farther out of the U.K. –  Will Jagy Jan 25 '14 at 20:53
@AsafKaragila, you should say And Toto Too. –  Will Jagy Jan 25 '14 at 20:55
I think we should just let them go, so long as they still sell us their whiskey! –  Old John Jan 25 '14 at 20:55
@OldJohn, good that you understand your priorities. –  Will Jagy Jan 25 '14 at 20:58

Let $N_k$ be the integers with exactly $k$ prime factors (counting with multiplicity). The $N_k$ for $k \ge 1$ partition the integers and are all infinite, if you just agree to stow $1$ somewhere.

-
An infinite set isn't the same as a large set, as far as I understand –  DanZimm Jan 25 '14 at 23:46
This answer needs to be expanded to show the $N_k$ are large, i.e. $\sum_{n\in N_k}\frac1n=\infty$. One can prove this by taking the product of the first $k-1$ primes $p_1,\ldots,p_{k-1}$ with the sequence of all the others, so that $$\sum_{n\in N_k}\frac1n\geq\frac{1}{p_1\cdots p_{k-1}}\sum_{j=k}^\infty \frac1{p_j}=\infty.$$ –  E.P. Jan 26 '14 at 2:37
Thanks episanty, for completing the argument. –  ncmathsadist Jan 26 '14 at 2:38

I understand that the question has already been answered, and answered well, but here is another very quick, but slightly different argument:

The usual proof that $\sum \frac{1}{n}$ diverges uses the fact that there are an infinite number of disjoint finite blocks of numbers whose reciprocals add up to more than $\frac{1}{2}$: $$\{1\} , \{2,3\}, \{4,5,6,7\}, \{8,9,10,\ldots,15\}, \ldots$$ Call these blocks $B_{1}, B_{2},\ldots$

It is obvious that any set of integers that contains an infinite number of these blocks must be a large set. So, just partition $\mathbb{N}$ into an infinite number of infinite sets $\{A_{i}\vert i\in \mathbb{N}\}$, and define the large set $L_{i}$ as $$L_{i}=\bigcup_{x\in A_{i}}B_{i}.$$

-