¿Por qué este polinomio relacionado con los códigos Hamming tiene coeficientes enteros?

Question

Pregunta: ¿Por qué $$ \frac{(1 + x)^{2^k - 1} - (1 - x^2)^{2^{k-1} - 1}(1-x)}{2^k} $$ tienen coeficientes enteros?

Detalles: Para una pregunta en la que estoy pensando, necesitaba saber todos los números reales $c$ tal que la función generadora $$ p(x) = \frac{(1 + x)^{2^k - 1}}{2^k} - c \cdot(1 - x^2)^{2^{k-1} - 1}(1-x) $$ es un polinomio con coeficientes enteros y término constante $0$ o $1$ . Enchufar $x = 0$ revela que $c = -\frac{1}{2^k}$ o $c = 1 - \frac{1}{2^k}$ . Ambos $c$ parecen funcionar empíricamente para todos los $k$ pero no me queda claro por qué. La fórmula binomial da el coeficiente de $x^i$ (por ejemplo, $i$ incluso) como $$ \frac{{{2^k - 1} \choose {i}} - (-1)^{i/2}{2^{k-1} - 1 \choose i/2} }{2^k} $$

Pero no creo que esta expresión sea agradable.

Además, una búsqueda en oeis revela que $p(x)$ está relacionado con los códigos Hamming.

Answer 1

Tenga en cuenta que $$ \frac{(1+x)^{2^{k+1}-1}-(1-x^2)^{2^k-1}(1-x)}{2^{k+1}} =(1+x)^{2^k-1}\frac{(1+x)^{2^k}-(1-x)^{2^k}}{2^{k+1}} $$ $\frac{(1+x)^{2^k}-(1-x)^{2^k}}{2}$ es la parte impar de $(1+x)^{2^k}$ . Por lo tanto, sólo tenemos que demostrar que $\left.2^k\,\middle|\,\binom{2^k}{j}\right.$ cuando $j$ es impar. El número de factores de $2$ en $\binom{2^k}{j}$ es la suma de los bits de la representación binaria de $j$ más la suma de los bits de la representación binaria de $2^k-j$ menos la suma de los bits de la representación binaria de $2^k$ . En $j$ es impar, esto es $k$ .

100000000000 $\leftarrow2^k$ tiene $k$ ceros a la derecha
001100100101 $\leftarrow j$ es impar, por lo que tiene una a la derecha
010011011011 $\leftarrow2^k-j$ es el complemento de $j$ más uno (tiene un uno a la derecha)

Excepto el bit más a la derecha, todos los bits de $j$ y $2^k-j$ son complementos. Como el bit más a la derecha es uno en ambos, la suma de los bits en $j$ y $2^k-j$ es $k+1$ . La suma de los bits en $2^k$ es $1$ . Así, hay $k$ factores de $2$ en $\binom{2^k}{j}$ . Es decir, $\left.2^k\,\middle|\,\binom{2^k}{j}\right.$ cuando $j$ es impar.