Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question

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.

share|cite|improve this answer
Ahh, now I remember! I think this was similar to what I had, but this is much more elegant! Thanks. I was hoping a slick proof for a) would generalize easily to b). – Aryabhata Jan 21 '11 at 23:29
It seems to me this only works for $M \pmod{8} \in \{3,5\}$ as when M is 2, both 2n+1 and n+2 yield squares. The argument that $P_\pi(n) \equiv \pi(1) \pmod{4} \in \{2,3\}$ seems to depend on M being odd. – Ross Millikan Jan 22 '11 at 2:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.