MathOverflow is a question and answer site for professional mathematicians. 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

Consider $P_n(x)$ polynomials defined through the recurrence relations $$P_n(x)=2(1-x)P_{n-1}(x)-(1+x)^2P_{n-2}(x),$$ with $P_0(x)=1$ and $P_1(x)=1-3x$. In fact, the explicit solution of these recurrence relations is given by the formula $$P_n(x)=\frac{1}{2}\left[ (1+i\sqrt{x})^{2n+1}+(1-i\sqrt{x})^{2n+1}\right].$$ What condition(s) should satisfy the number $n$, the polynomial $P_n(x)$ to be reducible? I have checked, that $P_n(x)$ is reducible for $n=4,7,10,12,13,16,17,19,\ldots$ What is special about these numbers?

Another question: given a number $n$, for what numbers $0<m<n$ the polynomial $P_n(x)$ is divisible by $P_m(x)$? For example, $P_4$ is divisible by $P_1$; $P_7$ is divisible by $P_1$ and $P_2$; $P_{10}$ is divisible by $P_1$ and $P_3$; $P_{12}$ is divisible by $P_2$; $P_{13}$ is divisible by $P_1$; $P_{16}$ is divisible by $P_1$ and $P_5$; $P_{17}$ is divisible by $P_2$ and $P_3$; $P_{19} $ is divisible by $P_1$ and $P_6$.

These polynomials emerged in the solution of the certain collision problem (hence the name) from the book: David Morin, Introduction to Classical Mechanics With Problems and Solutions (Cambridge University Press, 2007). See problem 5.88 on page 192. It can be also found here (the problem for Week 19. The solution is also provided there, which, however, does not use the collision polynomials):

share|cite|improve this question
It's always a good idea to try the OEIS when encountering a mysterious sequence:… – Felix Goldberg Jul 25 '13 at 11:59
Thanks! I was not aware of OEIS. So now we have a conjucture: $P_n$ is reducible if and only if $n=(m-1)/2$ for some odd nonprime integer $m$. Amusing! It remains to prove it (I have checked some other numbers from the OEIS list and all of them works). – Zurab Silagadze Jul 25 '13 at 12:39
up vote 4 down vote accepted

Writing $P_n(x)=\frac{1}{2}\left[ (i\sqrt{x}+1)^{2n+1}-(i\sqrt{x}-1)^{2n+1}\right]$ and using that $x^u-y^u$ divides $x^v-y^v$ once $u$ divides $v$ easily shows that $P_m$ divides $P_n$ once $2m+1$ divides $2n+1$. With a little more effort, one should see that this sufficient condition is necessary, too.

I'm not sure whether your first question would like to see an answer why $P_n$ is irreducible over $\mathbb Q$ when $2n+1$ is a prime. Anyway, this is the case because the reciprocal $x^nP(1/x)$ is an Eisenstein polynomial with respect to the prime $2n+1$.

share|cite|improve this answer

This is not an 'answer' per se, but a long comment with some observations which seem to pan out quite well. First notice that the sequence $4,7,10,12,13,16,17,19$ when passed through the function $\lambda n \rightarrow 2n+1$ (which is gotten from the closed-form expression you provided), one gets the following sequence: $$9,15,21,25,27,33,35,39$$ which factorizes as $$3*3,5*3,7*3,5*5,3*3*3,3*11,5*7,3*13.$$ The most important item about the above sequence is that it corresponds exactly to your observed sequence of factorizations.

I would then bet that the pattern of factorization is that only for those $n$ where $2n+1$ factorizes in only odd numbers do you get a divisibility relation in your $P_n$'s.

share|cite|improve this answer
Can $2n+1$ have even factors ...??? – Peter Mueller Jul 25 '13 at 12:42
@Peter - of course not, that was just sloppy phrasing on my part. I guess I could have said "when it factors". – Jacques Carette Jul 25 '13 at 12:45

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.