The sum of integers being a bijection - MathOverflow

The sum of integers being a bijection

2010-12-31T10:22:27Z

What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map \begin{eqnarray*} P\times Q & \rightarrow & {\mathbb N} \\ (p,q) & \mapsto & p+q \end{eqnarray*} is a bijection ?

Obvious examples are $P=\mathbb N$ with $Q=\{0\}$, or $P=2\mathbb N$ with $Q=\{0,1\}$. Are there others ?

This question is related to a puzzle given in EMISSARY (fall 2010), asking to find infinite series $f(x)$ and $g(x)$ with coefficients $0$ and $1$, whose product equals $\frac{1}{1-x}$. I suspect that the word infinite was written on purpose, and therefore $P$ and $Q$ must be infinite.

Later. After the answers, I understand that one can find a sequence $(P_j)_{j\ge0}$ of subsets of $\mathbb N$ with $0\in P_j$, such that every $n\in\mathbb N$ writes $\sum_{j\ge0}p_j$ with $p_j\in P_j$, in a unique way. Of course, all but finitely many $p_j$'s are zeros. Now, I feel dumb, because this follows for instance from the writing of integers in some basis.

Answer by Qiaochu Yuan for The sum of integers being a bijection

2010-12-31T10:29:12Z

Here is a fairly large class of examples. Pick any subset $S$ of $\mathbb{N}$. Let $P$ be the set of non-negative integers such that the only $1$s in their binary expansion are at indices in $S$, and let $Q$ be the set of non-negative integers such that the only $1$s in their binary expansion are at indices in the complement of $S$. (Your examples are, respectively, $S = \mathbb{N}$ and $S = \mathbb{N} - \{ 0 \}$.) Similar constructions work for any base, and for slightly more general things than bases (e.g. factorial base). In terms of infinite series this is a consequence of the identity

$$\frac{1}{1 - x} = (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...$$

which expresses the uniqueness of binary expansion, and the choice of $S$ corresponds to a choice of grouping of terms on the RHS.

Answer by Gjergji Zaimi for The sum of integers being a bijection

2010-12-31T12:25:02Z

To comment on Qiaochu's answer, one can show that all such factorizations come from mixed radix representations (different bases, factorial base etc.). That is if $$\frac{1}{1-x}=P(x)Q(x)$$ then there must be a sequence $1=a_0\le a_1 \le a_2\le\cdots$ so that $a_i$ divides $a_{i+1}$ and disjoint subsets $A,B$ with $\mathbb N=A\cup B$, so that $$P(x)=\prod_{i\in A}\frac{1-x^{a_{i+1}}}{1-x^{a_i}},Q(x)=\prod_{i\in B}\frac{1-x^{a_{i+1}}}{1-x^{a_i}}.$$ The proof is simple, suppose $P(x)=1+x+\cdots x^{a_1-1}+\cdots$ then $Q(x)=Q_1(x^{a_1})$ and $P(x)=\frac{x^{a_1}-1}{x-1}P_1(x)$. Then we proceed by induction.

Answer by Nikita Sidorov for The sum of integers being a bijection

2010-12-31T18:24:07Z

If you accept that 0 is not a natural number, then there is a very simple answer to your question: take $P$ to be all numbers whose expansions base 4 contain only digits 0 and 1 and $Q$ to contain only digits 0 and 2. Then $P\cap Q={0}$, which we have boldly excluded.

Also, both sets have the lowest possible asymptotic density of order $1/\sqrt n$, which is kinda nice.