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.

  • $\begingroup$ Another obvious example is $P = a{\mathbb N}$ and $Q$ the standard complete residue system modulo $a$. $\endgroup$ – Franz Lemmermeyer Dec 31 '10 at 10:33
  • $\begingroup$ On the other hand, $$\begin{eqnarray*} P\times Q & \rightarrow & {\mathbb Z} \\ (p,q) & \mapsto & p+q \end{eqnarray*}$$ can be quite bizarre. $\endgroup$ – Aaron Meyerowitz Jan 1 '11 at 8:53

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.

  • $\begingroup$ sorry, I do not see, why does $Q$ have such a form $Q(x)=Q_1(x^{a_1})$? $\endgroup$ – Fedor Petrov Dec 31 '10 at 12:39
  • 6
    $\begingroup$ Fedor, thanks for the edit. As to your question, let $x^{ka_1+r}$ be the smallest term in $Q(x)$ with exponent not divisible by $a_1$. Since the term $x^{ka_1+r-1}$ must appear in $PQ$ this means that for some $b$ we have $x^{ba_1}$ is a term in $Q$ and $x^{(k-b)a_1+r-1}$ is in $P$. If $x^{(k-b)a_1+r}$ is also in $P$ we get a contradiction as the coefficient of $x^{ka_1+r}$ in $PQ$ is greater than $1$, and so now we look at the term $x^{(k-b)a_1+r}$ in $PQ$, it must be written from $x^{ca_1}$ in $Q$ and $x^{(k-b-c)a_1+r}$ in $P$. So this, in turn implies that $x^{(k-b-c)a_1+r-1}$... $\endgroup$ – Gjergji Zaimi Dec 31 '10 at 13:26
  • $\begingroup$ ...is not in $P$. The contradiction follows from descent. $\endgroup$ – Gjergji Zaimi Dec 31 '10 at 13:26
  • $\begingroup$ Very nice. Does the natural generalization hold for 3 or more factors, $\frac 1 {1-x}=P(x)Q(x)R(x)$ etc? $\endgroup$ – Pietro Majer Dec 31 '10 at 17:25
  • 1
    $\begingroup$ @Pietro yes it does, the proof is pretty much the same. $\endgroup$ – Gjergji Zaimi Dec 31 '10 at 18:08

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.

  • $\begingroup$ So, the original $1/(1-x)$ factorization form of the problem is more natural. $\endgroup$ – Wadim Zudilin Dec 31 '10 at 11:17

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.

  • $\begingroup$ Hmm...if $0$ is not a natural number, then either $P$ or $Q$ contain $0$ and are not subsets of the natural numbers (as required by the question), or neither $P$ nor $Q$ contains zero, in which case $P+Q$ cannot contain $1$. So I think this just misses. But maybe it's late and I'm being stupid? $\endgroup$ – Daniel Litt Jan 1 '11 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.