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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Another obvious example is $P = a{\mathbb N}$ and $Q$ the standard complete residue system modulo $a$. $\endgroup$
    – Franz Lemmermeyer
    Commented 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$
    – Aaron Meyerowitz
    Commented Jan 1, 2011 at 8:53

3 Answers 3

Reset to default
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.

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ So, the original $1/(1-x)$ factorization form of the problem is more natural. $\endgroup$
    – Wadim Zudilin
    Commented 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.

Improve this answer
$\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$
    – Daniel Litt
    Commented Jan 1, 2011 at 6:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .