Permanente de una matriz de enteros Impares

Question

Es evidente que la permanente de un $n\times n$ cuyas entradas son enteros Impares, es un número par, ya que es la suma de $n!$ Números Impares. Estoy interesado en encontrar la mayor potencia de $2$ que divide la permanente de dicha matriz.

Tenga en cuenta que si $A$ es un impar $n\times n$ matriz, entonces $\det (A)\equiv 0 (\mod 2^{n-1})$ . Esto se puede comprobar realizando $n-1$ operaciones de fila para obtener un $n\times n$ matriz $B$ que $n-1$ de sus filas están formadas por números enteros pares (encontré esta bonita observación en el artículo de Amos Nevo Peter Sarnak, "Prime and Almost Prime Points on Principal Homogeneous Spaces": http://web.math.princeton.edu/sarnak/NS-final-Oct-08.pdf ).

Mi objetivo es encontrar un resultado similar para la permanente. Por supuesto, aquí no puedo utilizar operaciones de fila. Ejecutando varios miles de ejemplos en un ordenador, sospecho lo siguiente:

Si $n=2^s -1$ para algún número entero $s\geq 2$ puis $\text {perm}(A)\equiv 2^{n-s} (\mod 2^{n-s+1})$ . Si $2^s \leq n < 2^{s+1} -1$ puis $\text {perm}(A)\equiv 0 (\mod 2^{n-s})$ .

He podido demostrarlo (mediante un tedioso análisis de casos) para $n=3,4,5$ . Es decir, ya lo tengo: $\text {perm}(A_{3\times 3})\equiv 2(\mod 4)$ , $\text {perm}(A_{4\times 4})\equiv 0(\mod 4)$ , $\text {perm}(A_{5\times 5})\equiv 0(\mod 8)$ .

¿Alguna idea de cómo generalizar esto para cualquier $n$ ¿O si ya se ha hecho algo parecido antes?

Answer 1

Consideremos $s$ con $2^s\leq n<2^{s+1}$ . Primero probamos la conjetura cuando todas las entradas de $A$ son $1$ 's. Entonces $\mathrm{perm}(A)=n!$ por lo tanto Fórmula de Legendre el exponente de $2$ en ella es igual a $n-t$ donde $t$ es el número de $1$ en la expansión binaria de $n$ . Para $n=2^{s+1}-1$ tenemos $t=s+1$ por lo que el exponente es igual a $n-s-1$ . Para $2^s\leq n< 2^{s+1}-1$ tenemos $t\leq s$ por lo que el exponente es al menos $n-s$ .

Para el caso general podemos suponer que la afirmación se cumple para $n-1$ . Por el caso especial anterior, basta con demostrar que si aumentamos en $2$ una sola entrada $a_{ij}$ de $A$ entonces la matriz resultante $B$ satisface $$ \mathrm{perm}(B) \equiv \mathrm{perm}(A) \pmod{2^{n-s}}. $$ Claramente, $$ \mathrm{perm}(B) = \mathrm{perm}(A) + 2\mathrm{perm}(C),$$ donde $C$ es el $(n-1)\times(n-1)$ matriz resultante de $A$ borrando el $i$ -y la fila $j$ -ésima columna. Obsérvese que $2^s-1\leq n-1<2^{s+1}-1$ de ahí que por la hipótesis de inducción tengamos $$ \mathrm{perm}(C) \equiv 0 \pmod{2^{n-1-s}}. $$ La reclamación sigue, y hemos terminado.