Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.