19
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Another obvious example is $P = a{\mathbb N}$ and $Q$ the standard complete residue system modulo $a$. $\endgroup$ Dec 31, 2010 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$ Jan 1, 2011 at 8:53

3 Answers 3

25
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ sorry, I do not see, why does $Q$ have such a form $Q(x)=Q_1(x^{a_1})$? $\endgroup$ Dec 31, 2010 at 12:39
  • 7
    $\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$ Dec 31, 2010 at 13:26
  • $\begingroup$ ...is not in $P$. The contradiction follows from descent. $\endgroup$ Dec 31, 2010 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$ Dec 31, 2010 at 17:25
  • 1
    $\begingroup$ @Pietro yes it does, the proof is pretty much the same. $\endgroup$ Dec 31, 2010 at 18:08
30
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\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$ Jan 1, 2011 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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