Never Perfect Square Permutation Polynomials

I had made up this problem a while back, and I think I had a tedious, uninsightful proof. Also, I am not able to reconstruct the proof I had.

Here is the problem:

Let $\displaystyle \pi: \{1,2, \dots, 13\} \to \{1,2,\dots, 13\}$ be a bijection, i.e. it is basically a permutation of the first $\displaystyle 13$ positive integers.

For each such $\displaystyle \pi$ construct the polynomial $\displaystyle P_{\pi}: \mathbb{Z} \to \mathbb{Z}$ such that

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

Is there some $\displaystyle \pi$ such that for every $\displaystyle n \in \mathbb{Z}$, $\displaystyle P_{\pi}(n)$ is never a perfect square?

I believe it is true that there is such a $\displaystyle \pi$. In fact, I seem to recollect having "proved" that there are at least $7!$ such permutations.

So the questions are:

a) Is there a "slick" proof of the existence of at least one such $\displaystyle \pi$? (Any proof welcome, though).

b) What if $\displaystyle 13$ is replaced by a generic natural number $\displaystyle M$? Can we give a different (and hopefully simpler) characterization of the $\displaystyle M$ for which such a $\displaystyle \pi$ exists?

Please consider posting an answer even if you don't have an answer for b).

Solution 1:

Edit: The original solution was wrong, but fortunately could be fixed.

Given $M$, we find a sufficient condition for a permutation $\pi$ to work. We use the following simple property: $m^2 \pmod{4} \in \{0,1\}$. So if we can force $P_\pi(n) \pmod{4} \in \{2,3\}$, we are done.

There are four cases to consider, according to $n \pmod{4}$. If $n \pmod{4} = 0$ then $$P_\pi(n) \equiv \pi(1) \pmod{4},$$ and so we need $\pi(1) \pmod{4} \in \{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} \in \{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}.$$

Claim: Whenever $M\geq 3$ satisfies $M \pmod{8} \in \{2,3,4,5\}$, we can find such a $\pi$.

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

This method of proof can probably be generalized by replacing $4$ with other moduli.