Nunca Cuadrado Perfecto De Permutación De Polinomios

Question

Yo había hecho hasta este problema hace un tiempo, y creo que he tenido un trabajo tedioso, uninsightful prueba. Además, yo no soy capaz de reconstruir la prueba de que he tenido.

Aquí está el problema:

Deje $\displaystyle \pi: \{1,2, \dots, 13\} \to \{1,2,\dots, 13\}$ ser un bijection, es decir, básicamente, es una permutación de la primera $\displaystyle 13$ enteros positivos.

Para cada una de las $\displaystyle \pi$ construir el polinomio $\displaystyle P_{\pi}: \mathbb{Z} \to \mathbb{Z}$ tal que

$$P_{\pi}(x) = \sum_{j=1}^{13} \ \ \pi(j) \ x^{j-1}$$

Hay algunos $\displaystyle \pi$ tal que para cada $\displaystyle n \in \mathbb{Z}$, $\displaystyle P_{\pi}(n)$ nunca es un cuadrado perfecto?

Yo creo que es cierto que hay un $\displaystyle \pi$. De hecho, me parece recordar haber "demostrado" que hay, al menos, $7!$ tales permutaciones.

Así, las preguntas son:

a) ¿existe una "mancha" la prueba de la existencia de al menos una de esas $\displaystyle \pi$? (Cualquier prueba bienvenida, aunque).

b) ¿Qué pasa si $\displaystyle 13$ es reemplazado por un genérico número natural $\displaystyle M$? Podemos darle una diferente (y esperemos que más sencillo) caracterización de la $\displaystyle M$ para que un $\displaystyle \pi$ existe?

Por favor, considere la posibilidad de publicar una respuesta, incluso si usted no tiene una respuesta para el b).

Answer 1

Edit: La solución original estaba mal, pero afortunadamente pudo ser fijo.

Dado $M$, nos encontramos con una condición suficiente para que una permutación $\pi$ a de trabajo. Hacemos uso de la siguiente propiedad: $m^2 \pmod{4} \in \{0,1\}$. Así que si se puede forzar a $P_\pi(n) \pmod{4} \in \{2,3\}$, hemos terminado.

Hay cuatro casos a considerar, de acuerdo a $n \pmod{4}$. Si $n \pmod{4} = 0$ $$P_\pi(n) \equiv \pi(1) \pmod{4},$$ and so we need $\pi(1) \pmod{4} \en \{2,3\}$. If $n \pmod{4} = 2$ then $$P_\pi(n) \equiv \pi(1) + 2\pi(2) \pmod{4},$$ and so we need $\pi(2)$ to be even. If $n \pmod{4} = 1$ then $$P_\pi(n) \equiv \sum_{i=1}^M \pi(i) = \sum_{i=1}^M i = \frac{M(M+1)}{2} \pmod{4};$$ that happens whenever $M \pmod{8} \en \{2,3,4,5\}$. Finally, if $n \pmod{4} = 2$ then $$P_\pi(n) \equiv \sum_{i=1}^M (-1)^{i+1} \pi(i) \equiv \frac{M(M+1)}{2} + 2\sum_{j=1}^{\lfloor M/2 \rfloor} \pi(2j) \pmod{4}.$$ Thus we need $$\sum_{j=1}^{\lfloor M/2 \rfloor} \pi(2j) \equiv 0 \pmod{2}.$$

Reclamo: Cuando $M\geq 3$ satisface $M \pmod{8} \in \{2,3,4,5\}$, podemos encontrar una $\pi$.

Prueba: Set$\pi(1) = 3$$\pi(2m) = 2m$.

Este método de prueba, probablemente puede ser generalizado por la sustitución de $4$ con otros módulos.