Grupo de Grothendieck del monoide de Fibonacci

Question

Denotemos los números de Fibonacci por $F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n \; \forall n \ge 0$ . Según Teorema de Zeckendorf todo número entero positivo puede representarse unívocamente como la suma de algunos (al menos $1$ ) números de Fibonacci distintos en los que no aparecen dos números de Fibonacci consecutivos.

Supongamos números enteros positivos $a=\sum_{r=1}^{p}F_{i_r}$ y $b=\sum_{s=1}^{q}F_{j_s}$ están en sus formas de Zeckendorf, es decir $i_1 \ll \cdots \ll i_p,j_1 \ll \cdots \ll j_q$ donde $x \ll y \Leftrightarrow x+2 \le y$ . Desde $F_0=0$ y $F_1=F_2=1$ podemos exigir que $i_1,j_1 \ge 2$ si ambos $a$ y $b$ son distintos de cero. Definir el Producto Fibonacci de $a$ y $b$ por $a \circ b=\sum_{r=1}^{p}\sum_{s=1}^{q}F_{i_r+j_s}$ (este resultado no está necesariamente en su forma Zeckendorf), y la forma Zeckendorf de $0$ ser $0=F_0$ . Se puede comprobar que $0$ es el elemento identidad del producto de Fibonacci. Por un teorema de Knuth El producto Fibonacci sobre enteros no negativos es conmutativo y asociativo (la introducción de una identidad no los rompe), lo que convierte a los enteros no negativos en un monoide conmutativo.

En el mismo papel Knuth llegó a la conclusión de que el producto de Fibonacci es monotónicamente creciente en cada variable, lo que significa que tiene la propiedad de cancelación. Por lo tanto, el monoide se incrusta en su grupo de Grothendieck $G_F$ . Consideremos el submonoide generado por $\{ F_i \}_{i \ne 1}$ obtenemos que $\Bbb{Z} \vartriangleleft G_F$ ( $F_i \circ F_j=F_{i+j} \; \forall i,j \ge 2$ ), pero los demás elementos de $G_F$ no me quedan claras ( Por ejemplo, no sé si $G_F$ tiene cualquier elemento de torsión ). ¿Tiene el grupo $G_F$ se ha estudiado en alguna parte, o la estructura de $G_F$ es demasiado trivial para ser investigado? Cualquier referencia o descripción directa es bienvenida.

Corrección: Hay una errata en las "normas de transporte" $(8)$ & $(9)$ en el artículo de Knuth. Las reglas de transporte correctas deberían ser: $$\overline{0(d+1)(e+1)} \rightarrow \overline{1de} \\ \overline{0(d+2)0e} \rightarrow \overline{1d0(e+1)}$$ para $d,e \ge 0$ . Knuth parecía utilizar estas reglas correctas en su siguiente discusión, por lo que no perjudicó a su conclusión.

Answer 1

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