Número de términos en ciertos polinomios sobre $\mathbb{F}_2$

Question

Me planteó esta cuestión en mi respuesta En el rango de una matriz $S$ con coeficientes en $\mathbb F_{2^m}$. Deje $s_1,s_3,s_5,\dots$ ser indeterminates sobre el campo $\mathbb{F}_2$, y recursívamente $s_{2n}=s_n^2$, con $s_0=1$. Vamos $$\begin{eqnarray*} F(x) & = & \frac{\sum_{n\geq 1} s_{2n-1}x^n}{\sum_{n\geq 0} s_{2n}x^n}\\ & = & \sum_{n\geq 0} p_n(s_1,s_3,\dots)x^n. \end{eqnarray*}$$ Es cierto que el número de términos del polinomio $p_n(s_1,s_3,\dots)$ es igual al número de formas de escribir $n$ como una suma de potencias de 2, sin tener en cuenta el orden? Por ejemplo, el número de términos de $p_5$ es de cuatro, correspondiente a $4+1=2+2+1=2+1+1+1=1+1+1+1+1$. Un bijective prueba sería especialmente interesante. Hay una generalización a $\mathbb{F}_p$?

Answer 1

La afirmación es verdadera. Vamos a empezar por la simplificación de la expresión de la siguiente manera: $$x\left(1+\frac{1}{1+s_1x+s_2x^2+s_3x^3+\cdots}\right)=\frac{\sum_{n\geq 1}s_{2n-1}x^{2n}}{\sum_{n\geq 0} s_{2n} x^{2n}}.$$ Esto se deduce porque $\sum_{n\geq 0}s_{2n}x^{2n}=\left(\sum_{n\geq 0}s_nx^n\right)^2$, y algunos básicos manipulaciones sobre $\mathbb F_2$.

Así que estamos interesados en el coeficiente de $x^{2n-1}$ en $$1+\frac{1}{1+s_1x+s_2x^2+\cdots}=\left(\sum_{n\geq 0}s_nx^n\right)+\left(\sum_{n\geq 0}s_nx^n\right)^2+\left(\sum_{n\geq 0}s_nx^n\right)^3+\cdots,$$ pero al tomar binario expansiones vemos que cada término es de la forma $$\left(\sum_{n\geq 0}s_{2^{i_1}n}x^{2^{i_1}n}\right)\cdots \left(\sum_{n\geq 0}s_{2^{i_k}n}x^{2^{i_k}n}\right),$$ donde $i_1,i_2,\dots,i_k\geq 1$. De ello se desprende que los términos del coeficiente de $x^{m}$ corresponden exactamente a las soluciones de $m=j_1+2j_2+\cdots 2^rj_{r+1}$. Los que aparecen con un coeficiente distinto de cero en $\mathbb F_2$ son precisamente aquellos en los que el $j_1,j_2,\dots$ son de todos los impares. Por lo que el número de términos en $p_n$, con su notación, es el número de maneras en que podemos escribir $$2n-1=\sum_{r= 0}^k (2i_r+1)2^{r}$$ para algunos k. Este es el mismo que $$n=2^k+\sum_{r= 0}^k i_r 2^r$$ que da exactamente el número de formas de partición de la $n$ como potencias de $2$. Por ejemplo, cuando se $n=6$, podemos escribir $11$ as $1+10, 1+6+4, 5+6, 5+2+4, 9+2,11$ cada uno correspondiente a los términos en $p_6=s_1s_5^2+s_1s_3^2s_1^4+s_5s_3^2+s_5s_1^2s_1^4+s_9s_1^2+s_{11}$.

Answer 2

Como una respuesta a Greg Martins comentarios;

Hay un natural de inyección a partir de una partición de $n$ con piezas que son potencias de 2, para las particiones de $2n-1$ donde todas las partes son impares.

La asignación de $(p_1,p_2,\dotsc,p_l) \mapsto (2p_1-1,2p_2-1,\dotsc,2p_l-1,1,1,\dotsc,1)$, donde el número de unos en la final son lo suficientemente numerosos, es como una inyección.

Dejo como ejercicio para el lector demostrar que esto es de hecho una inyección, pero como sugerencia, el siguiente código de Mathematica implementa el mapa de arriba, y a la inversa.

TheMapping[part_] := Module[{len},
    len = Length[part];
    Reverse@Sort@Flatten@Append[2*part - 1, ConstantArray[1, len - 1]]
];

TheMappingInverse[part_] := Module[{n, part2, p},
    n = (Total[part] + 1)/2;
    part2 = (part + 1)/2;
    p = First@Flatten@Position[Accumulate[part2], n];
    Return[part2[[;; p]]];
];

Ejemplo de uso:

TheMapping[{8, 2, 1, 1}] == {15, 3, 1, 1, 1, 1, 1}
TheMappingInverse[{15, 3, 1, 1, 1, 1, 1}] == {8, 2, 1, 1}

Answer 3

Esto no es realmente una respuesta, sólo un largo comentario. He trabajado algunos de los coeficientes de este poder de la serie, pueden ser de utilidad para otros. (Más están disponibles a petición).

• $s_1x$
• $(s_3 + s_1^3)x^2$
• $(s_5 + s_3s_1^2)x^3$
• $(s_7 + s_5s_1^2 + s_3^2s_1 + s_1^7)x^4$
• $(s_9 + s_7s_1^2 + s_3^3 + s_3s_1^6)x^5$
• $(s_{11} + s_9s_1^2 + s_5^2s_1 + s_5s_3^2 + s_5s_1^6 + s_3^2s_1^5)x^6$
• $(s_{13} + s_{11}s_1^2 + s_7s_3^2 + s_7s_1^6 + s_5^2s_3 + s_3^3s_1^4)x^7$
• $(s_{15} + s_{13}s_1^2 + s_9s_3^2 + s_9s_1^6 + s_7^2s_1 + s_5^3 + s_5^2s_1^5 + s_5s_3^2s_1^4 + s_3^4s_1^3 + s_1^{15})x^8$
• $(s_{17} + s_{15}s_1^2 + s_{11}s_3^2 + s_{11}s_1^6 + s_7^2s_3 + s_7s_5^2 + s_7s_3^2s_1^4 + s_5^2s_3s_1^4 + s_3^5s_1^2 + s_3s_1^{14})x^9$
• $(s_{19} + s_{17}s_1^2 + s_{13}s_3^2 + s_{13}s_1^6 + s_9^2s_1 + s_9s_5^2 + s_9s_3^2s_1^4 + s_7^2s_5 + s_7^2s_1^5 + s_5^3s_1^4 + s_5s_3^4s_1^2 + s_5s_1^{14} + s_3^6s_1 + s_3^2s_1^{13})x^{10}$
• $(s_{21} + s_{19}s_1^2 + s_{15}s_3^2 + s_{15}s_1^6 + s_{11}s_5^2 + s_{11}s_3^2s_1^4 + s_9^2s_3 + s_7^3 + s_7^2s_3s_1^4 + s_7s_5^2s_1^4 + s_7s_3^4s_1^2 + s_7s_1^{14} + s_3^7 + s_3^3s_1^{12})x^{11}$
• $(s_{23} + s_{21}s_1^2 + s_{17}s_3^2 + s_{17}s_1^6 + s_{13}s_5^2 + s_{13}s_3^2s_1^4 + s_{11}^2s_1 + s_9^2s_5 + s_9^2s_1^5 + s_9s_7^2 + s_9s_5^2s_1^4 + s_9s_3^4s_1^2 + s_9s_1^{14} + s_7^2s_5s_1^4 + s_5^4s_1^3 + s_5^2s_3^4s_1 + s_5^2s_1^{13} + s_5s_3^6 + s_5s_3^2s_1^{12} + s_3^4s_1^{11})x^{12}$