Siendo la suma de enteros una biyección

Question

Cuáles son los pares $(P,Q)$ de subconjuntos de $\mathbb N$ para el que el mapa \begin{eqnarray*} P\times Q & \rightarrow & {\mathbb N} \\\\ (p,q) & \mapsto & p+q \end{eqnarray*} es una biyección ?

Algunos ejemplos evidentes son $P=\mathbb N$ con $Q=\{0\}$ ou $P=2\mathbb N$ con $Q=\{0,1\}$ . ¿Hay otros?

Esta pregunta está relacionada con un acertijo dado en EMISSARY (otoño 2010), pidiendo encontrar series infinitas $f(x)$ y $g(x)$ con coeficientes $0$ y $1$ cuyo producto es igual a $\frac{1}{1-x}$ . Sospecho que la palabra infinito fue escrito a propósito, y por lo tanto $P$ y $Q$ debe ser infinito.

Más tarde . Después de las respuestas, entiendo que se puede encontrar una secuencia $(P_j)_{j\ge0}$ de subconjuntos de $\mathbb N$ con $0\in P_j$ tal que cada $n\in\mathbb N$ escribe $\sum_{j\ge0}p_j$ con $p_j\in P_j$ de una manera única. Por supuesto, todos menos finitamente muchos $p_j$ son ceros. Ahora, me siento tonto, porque esto se deduce por ejemplo de la escritura de enteros en alguna base.

Answer 1

He aquí una clase bastante amplia de ejemplos. Elige cualquier subconjunto $S$ de $\mathbb{N}$ . Sea $P$ sea el conjunto de enteros no negativos tales que el único $1$ s en su expansión binaria están en índices en $S$ y que $Q$ sea el conjunto de enteros no negativos tal que el único $1$ s en su expansión binaria se encuentran en los índices del complemento de $S$ . (Sus ejemplos son, respectivamente, $S = \mathbb{N}$ y $S = \mathbb{N} - \{ 0 \}$ .) Construcciones similares funcionan para cualquier base, y para cosas un poco más generales que las bases (por ejemplo, la base factorial). En términos de series infinitas esto es una consecuencia de la identidad

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

que expresa la unicidad de la expansión binaria, y la elección de $S$ corresponde a una elección de agrupación de términos en el lado derecho.

Answer 2

Para comentar la respuesta de Qiaochu, se puede demostrar que todas esas factorizaciones proceden de radix mixto representaciones (diferentes bases, base factorial, etc.). Es decir, si $$\frac{1}{1-x}=P(x)Q(x)$$ entonces debe existir una secuencia $1=a_0\le a_1 \le a_2\le\cdots$ para que $a_i$ divide $a_{i+1}$ y subconjuntos disjuntos $A,B$ con $\mathbb N=A\cup B$ de modo que $$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}}.$$ La prueba es sencilla, supongamos $P(x)=1+x+\cdots +x^{a_1-1}+\cdots$ entonces $Q(x)=Q_1(x^{a_1})$ y $P(x)=\frac{x^{a_1}-1}{x-1}P_1(x)$ . Entonces procedemos por inducción.

Answer 3

Si aceptas que el 0 no es un número natural, entonces hay una respuesta muy sencilla a tu pregunta: toma $P$ son todos los números cuyas expansiones de base 4 contienen sólo los dígitos 0 y 1 y $Q$ para contener sólo los dígitos 0 y 2. Entonces $P\cap Q=\{0\}$ que hemos excluido con valentía.

Además, ambos conjuntos tienen la menor densidad asintótica posible de orden $1/\sqrt n$ lo que es bastante agradable.