The sum of integers being a bijection - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:30:00Z http://mathoverflow.net/feeds/question/50798 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50798/the-sum-of-integers-being-a-bijection The sum of integers being a bijection Denis Serre 2010-12-31T10:22:27Z 2010-12-31T18:54:45Z <p>What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map \begin{eqnarray*} P\times Q &amp; \rightarrow &amp; {\mathbb N} \\ (p,q) &amp; \mapsto &amp; p+q \end{eqnarray*} is a bijection ?</p> <p>Obvious examples are $P=\mathbb N$ with $Q=\{0\}$, or $P=2\mathbb N$ with $Q=\{0,1\}$. Are there others ?</p> <p>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 <em>infinite</em> was written on purpose, and therefore $P$ and $Q$ must be infinite.</p> <p><strong>Later</strong>. 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.</p> http://mathoverflow.net/questions/50798/the-sum-of-integers-being-a-bijection/50799#50799 Answer by Qiaochu Yuan for The sum of integers being a bijection Qiaochu Yuan 2010-12-31T10:29:12Z 2010-12-31T10:29:12Z <p>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</p> <p>$$\frac{1}{1 - x} = (1 + x)(1 + x^2)(1 + x^4)(1 + x^8)...$$</p> <p>which expresses the uniqueness of binary expansion, and the choice of $S$ corresponds to a choice of grouping of terms on the RHS. </p> http://mathoverflow.net/questions/50798/the-sum-of-integers-being-a-bijection/50803#50803 Answer by Gjergji Zaimi for The sum of integers being a bijection Gjergji Zaimi 2010-12-31T12:25:02Z 2010-12-31T12:38:11Z <p>To comment on Qiaochu's answer, one can show that all such factorizations come from <a href="http://en.wikipedia.org/wiki/Mixed_radix" rel="nofollow">mixed radix</a> 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.</p> http://mathoverflow.net/questions/50798/the-sum-of-integers-being-a-bijection/50819#50819 Answer by Nikita Sidorov for The sum of integers being a bijection Nikita Sidorov 2010-12-31T18:24:07Z 2010-12-31T18:54:45Z <p>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. </p> <p>Also, both sets have the lowest possible asymptotic density of order $1/\sqrt n$, which is kinda nice. </p>