Esta operación no tiene ningún misterio. El monoide $(\mathbf N,\circ)$ es isomorfo a un submonoide multiplicativo $T$ del anillo conmutativo $\mathbf Z[\varphi] = \mathbf Z[t]/(t^2-t-1)$ donde $\varphi = \tfrac{1+\sqrt{5}}{2}$ es la proporción áurea. En particular, es isomorfo a un submonoide de $\mathbf Z \oplus \mathbf N^{\oplus \mathcal P}$ donde $\mathcal P$ es el conjunto de ideales primos en $\mathbf Z[\varphi]$ y el primer factor son las potencias de la unidad fundamental $\varphi$ . De hecho, la agrupación $T^{\text{gp}} \hookrightarrow \mathbf Q(\varphi)^\times \cap \mathbf R_{>0} \cong \mathbf Z \oplus \mathbf Z^{\oplus \mathcal P}$ es un isomorfismo ; véase el corolario a continuación.
Primero escribí esto como una respuesta con todos los detalles, pero una pequeña búsqueda bibliográfica (empezando por el artículo de Knuth en MathSciNet y buscando referencias más adelante) encontró algunas fuentes originales que son un poco más ingeniosas que lo que escribí. Así que, en aras de la legibilidad, he eliminado algunas de las pruebas.
La referencia principal es el documento de 2 páginas [Arnoux, 1989], en el que se explica la relación con $\mathbf Z[\varphi]$ . Además, [Zhuravlev, 2007] señala que cada elemento no nulo de $\mathbf Z[\varphi]$ puede escribirse (de forma no unívoca) como $\pm\varphi^{-n}t$ para $t \in T$ y $n \in \mathbf N$ con lo que se obtiene el cómputo prometido de $T^{\text{gp}}$ del corolario siguiente.
Notación. Sea $f \colon \mathbf Z[t] \twoheadrightarrow \mathbf Z[\varphi]$ sea el mapa cociente $t \mapsto \varphi$ y que $g \colon \mathbf Z[\varphi] \to \mathbf Z$ sea el grupo homomorfismo $a+b\varphi \mapsto b$ . Tenga en cuenta que $g$ no es un homomorfismo de anillo; de hecho $g(\varphi^n) = F_n$ mediante la fórmula de Binet. Escriba $h$ para la composición $g \circ f$ ; esto exhibe un polinomio $\sum a_it^i$ como expansión radix-F de su imagen $\sum a_i F_i$ .
El producto Fibonacci $\circ$ tiene una extensión obvia a $\mathbf N \times \mathbf N \to \mathbf N$ estableciendo $n \circ 0 = n = 0 \circ n$ para todos $n \in \mathbf N$ (que no afecta a la asociatividad). Consideramos $\mathbf Z[\varphi]$ como un subring de $\mathbf R$ de la manera obvia, y tiene una conjugación $\overline{(-)} \colon \mathbf Z[\varphi] \to \mathbf Z[\varphi]$ tomando $\varphi$ a $1-\varphi = \varphi^{-1} = \tfrac{1-\sqrt{5}}{2}$ .
Definición. Definir el subconjunto $Z \subseteq t^2\mathbf Z[t]$ de elementos de la forma $P(t)=\sum_{i=2}^r a_it^i$ con todos $a_i \in \{0,1\}$ y $a_ia_{i+1} = 0$ para todos $i$ . Eliminamos $0$ de este conjunto y añadir $1$ ya que esta será nuestra unidad multiplicativa. Sea $T \subseteq \mathbf Z[\varphi]$ sea la imagen de $Z$ en $f$ . Entonces el teorema de Zeckendorf muestra que $f$ y $g$ dar biyecciones $$Z \stackrel\sim\to T \stackrel\sim\to \mathbf N.$$ Por definición, el mapa $h$ tiene la propiedad $h(xy) = h(x)h(y)$ para todos $x,y \in Z$ . Pero $Z$ no es cerrado bajo multiplicación, así que esto no produce un isomorfismo monoide $h \colon Z \stackrel\sim\to \mathbf N$ . El punto clave es:
Propuesta [Arnoux, 1989] El conjunto $T$ es cerrado bajo multiplicación. En particular, $g \colon T \to \mathbf N$ es un isomorfismo monoide para el producto Fibonacci sobre $\mathbf N$ es decir $$g(xy) = g(x) \circ g(y)\qquad \text{for all } x, y \in T.$$ Esto también proporciona una prueba conceptual de la asociatividad de $(\mathbf N,\circ)$ (que no se utiliza en la prueba). Vemos, pues, que $\mathbf Z[\varphi]$ interpola bien entre $\mathbf Z[t]$ y $(\mathbf N,\circ)$ .
La proposición puede demostrarse fácilmente a mano utilizando la estructura multiplicativa de $f$ junto con el Lemma 3 de Knuth; véase el historial de revisiones de este post para dicha demostración. En su lugar, Arnoux lo deduce de lo siguiente:
Lema [Arnoux, 1989]. El conjunto $T \setminus \{1\}$ viene dada por los elementos $t=a+n\varphi$ con $a,n \in \mathbf Z_{>0}$ tal que $\overline{\!\ t\ \!} \in (\varphi-2,\varphi-1)$ . El mapa $g^{-1}$ viene dada por $n \mapsto a_n + n\varphi$ donde $$a_n = \left\lfloor (n+1)\tfrac{-1+\sqrt{5}}{2} \right\rfloor$$ es la de Hofstadter $G$ -secuencia (OEIS A005206 ).
Véanse los lemas 2 y 3 de Arnoux. La última afirmación no está ahí, pero puede deducirse fácilmente de la primera. Esto demuestra que $T$ es cerrado bajo multiplicación como $(\varphi-2,\varphi-1) \subseteq (-1,1)$ . Además, proporciona la fórmula limpia $$n \circ m = nm + na_m + ma_n.$$ Obsérvese que en la primera afirmación no necesitamos la hipótesis $a > 0$ . En efecto, si $a \leq 0$ obtenemos $\overline{\!\ t\ \!} = a+n\overline\varphi \leq \overline\varphi < \varphi-2$ desde $\overline\varphi < 0$ y $n \geq 1$ .
Por último, necesitamos la siguiente observación que parece deberse a [Zhuravlev, 2007]; véase la Proposición 4.1.
Lema. Cada elemento $x \in \mathbf Z[\varphi]$ puede escribirse como $\pm\varphi^{-n} \cdot t$ para algunos $t \in T$ y $n \in \mathbf N$ .
Desde $T$ y $\varphi$ son positivos, el signo coincide con el signo de $x$ . La prueba (y todo el documento) es notacionalmente pesada (y lógicamente difícil de seguir), así que permítanme incluir aquí un argumento.
Prueba. Desde $\lvert \overline\varphi \rvert < 1$ obtenemos $\pm\overline{\!\ t\ \!} \in (\varphi-2,\varphi-1)$ para $n \gg 0$ . Si $t = a+n\varphi$ tenemos necesariamente $n \neq 0$ de lo contrario $t$ y por lo tanto $x$ es $0$ . Sin pérdida de generalidad, podemos suponer que $n > 0$ . Por el lema anterior (y la discusión posterior), obtenemos $t \in T$ Así que $x = \pm\varphi^{-n} \cdot t$ como desee. $\square$
(Nota: lo que Zhuravlev denomina $\delta(n)$ está relacionado con mi $g^{-1}(n)$ vía $-\delta(n)/\varphi = \overline{g^{-1}(n)}$ . La secuencia de Fibonacci de Zhuravlev se desvía en $1$ en comparación con Knuth).
Corolario. Existe una elección de generadores de cada ideal primo de $\mathbf Z[\varphi]$ inducir una inyección $\psi \colon T \hookrightarrow \mathbf Z \oplus \mathbf N^{\oplus \mathcal P}$ . Para cualquier elección de este tipo, el mapa $\psi^{\text{gp}} \colon T^{\text{gp}} \to \mathbf Z \oplus \mathbf Z^{\oplus \mathcal P}$ es un isomorfismo, y el mapa cociente $T \to \mathbf N^{\oplus \mathcal P}$ es suryectiva.
Prueba. Vimos que $T$ es un submonoide de $(\mathbf Z[\varphi]\setminus\{0\},\times)$ . Desde $\mathbf Z[\varphi]$ es un dominio ideal principal cuadrático real, podemos producir un isomorfismo $(\mathbf Z[\varphi]\setminus\{0\},\times) \cong \mathbf Z/2 \oplus \mathbf Z \oplus \mathbf N^{\oplus \mathcal P}$ eligiendo generadores para cada ideal primo. Por el lema, podemos elegir un generador en $T$ para cada ideal primo. Dado que todos los elementos de $T$ y todos los representantes elegidos son positivos, no necesitamos el factor de signo $\mathbf Z/2$ dando una incrustación $T \hookrightarrow \mathbf Z \oplus \mathbf N^{\oplus \mathcal P}$ . Las dos últimas afirmaciones se deducen inmediatamente del lema, ya que $\varphi^n \in T$ para todos $n \geq 2$ . $\square$
Mientras que los subgrupos de los grupos abelianos libres son libres, no ocurre lo mismo con los monoides conmutativos, es decir, no existe una factorización única en elementos irreducibles. Por ejemplo, los elementos $\varphi^n$ para $n \geq 2$ y $n=0$ están en $T$ pero $\varphi$ no es (como $g(\varphi) = 1 = g(\varphi^2)$ y $g$ es inyectiva en $T$ ). Así que $\varphi^6$ factores tanto como $(\varphi^2)^3$ o $(\varphi^3)^2$ . El resultado anterior es probablemente el más preciso que se puede obtener (también porque depende de infinitas opciones).
Tenga en cuenta que las potencias negativas de $\varphi$ no están en la imagen. De hecho, $(\mathbf N,\circ)$ es un monoide agudo: si $a,b \neq 0$ entonces $a \circ b \neq 0$ . No sé si existe una elección de generadores para la que ningún elemento recoja una potencia negativa de $\varphi$ (es decir, la imagen está en $\mathbf N \oplus \mathbf N^{\oplus \mathcal P} \subseteq \mathbf Z \oplus \mathbf N^{\oplus \mathcal P}$ ), pero me parece poco probable.
Referencias.
[Arnoux, 1989] P. Arnoux, Algunas observaciones sobre la multiplicación de Fibonacci . Appl. Math. Lett. 2 .4, p. 319-320 (1989). DOI: 10.1016/0893-9659(89)90078-5
[Zuravlev, 2007] V. G. Zhuravlev, Sumas de cuadrados sobre el Fibonacci $\circ$ -anillo . Zap. Nauchn. Semin. POMI 337 , p. 165-190 (2006). Traducción en J. Math. Sci., Nueva York 143 .3, p. 3108-3123 (2007). DOI: 10.1007/s10958-007-0195-1
