Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is inspired by a recent one : Let $c$ be a variable and define a sequence by $a_0=0$ $a_1=1$ and $a_{n+1}=a_{n}c-a_{n-1}$ . So

$$\begin{align*} a_2 &= c \\ a_3 &={c}^{2}-1= \left( c-1 \right) \left( c+1 \right) \\ a_4 &= {c}^{3}-2\,c=c \left( {c}^{2}-2 \right) \\ a_5 &={c}^{4}-3\,{c}^{2}+1 = \left( {c}^{2}+c-1 \right) \left( {c}^{2}-c-1 \right) \\ a_6 &={c}^{5}-4\,{c}^{3}+3\,c= c \left( c-1 \right) \left( c+1 \right) \left( {c}^{2}-3 \right) \\ a_7 &={c}^{6}-5\,{c}^{4}+6\,{c}^{2}-1= \left( {c}^{3}-{c}^{2}-2\,c+1 \right) \left( {c}^{3}+{c}^{2}-2\,c-1 \right) \end{align*}$$


Note that $$a_{n+1}=\sum_{j=0}^t (-1)^j\binom{n-j}{j}c^{n-2j}$$ where $t=\lfloor\frac{n}{2}\rfloor.$ So the array of coefficients is just Pascal's triangle shifted with alternating signs. Not that I see a connection to the questions below.


The defining recurrence $a_{n+1}=a_{n}c-a_{n-1}$ i.e. $$a_{n+1}=a_{n}a_{2}-a_{n-1}a_1$$ is the first non-trivial case (and base for an induction proof of) of the more general $$a_{n+m}=a_{n}a_{m+1}-a_{n-1}a_{m}. \tag{$\ast$}$$

From this is follows that $$\gcd(a_n,a_m)=a_{\gcd(n,m)} \tag{$\ast \ast$}$$ so the polynomial $a_n$ factors unless, possibly, $n$ is prime. But for any odd index $2m+1$ we have $$a_{(m+1)+m}=a_{m+1}^2-a_{m}^2=(a_{m+1}+a_m)(a_{m+1}-a_m)$$

Q: If $p=2m+1$ is prime, must the monic polynomials $s_p=a_{m+1}+a_m$ and $d_p=a_{m+1}-a_m$ be irreducible in $\mathbb{Z}[c]$?

random remarks

This is the case up to $p=199$ (according to Maple) so it seems likely.

Replacing $c$ by $-c$ changes $s_p$ into $\pm d_p$ so either both are irreducible or both factor (in the same way).

$a_{m+1}+a_{m}=$$c^m+c^{m-1}-\binom{m-1}{1}c^{m-2}-\binom{m-2}{1}c^{m-3}+\binom{m-3}{2}c^{m-4}+\binom{m-4}{2}c^{m-5}-\cdots$

A heuristic argument (which should perhaps not be trusted) is as follows: For a fixed integer value $c \ge 2$ the $a_n$ become integers but $(\ast)$ and $(\ast \ast)$ remain true (now as statements in $\mathbb{Z}$) so if a prime $q$ divides $a_k$ for the first time at $k=n$ then it divides $a_k$ exactly when $n \mid k$. Accordingly, when $p=2m+1$ is prime, we have the factorization $a_p=s_p \cdot d_p$ where the two factors are co-prime and any prime $q$ which divides either of them (and hence $a_p$) does not divide $a_k$ for any $k \lt p$. Of course for a given $c$ one or both of $s_p,d_p$ might be composite, but it seems likely (weak!) that each (or even just one or the other) is prime for some value of $c$ and that would require both to be irreducible as polynomials.

When $c$ is set to $c=2$ we have $a_k=k$ so $d_p=a_{m+1}-a_m=1$ and $s_p=a_{m+1}+a_m=2m+1$ is prime when $p$ is. This makes it seem somewhat more likely that the polynomial $s_p$ is irreducible, however there could be factors of the form $(c-2)f(c)+1.$

share|improve this question
    
See comments in oeis.org/A115139 –  rwst Oct 29 '13 at 9:28
    
I was thinking about factoring over $Z[\zeta_n]$ (as in Peter's answer) which gives a lot of factors then computing the gcd of the norm and $a_n$ in hope to find more factors, but according to Peter this won't work... –  joro Oct 29 '13 at 10:58
    
Is $c$ an integer? If it is not they might be reducible over Z[c]... –  joro Oct 29 '13 at 11:01
    
@joro: The question says that $c$ is a variable. –  Peter Mueller Oct 29 '13 at 11:03
add comment

2 Answers

up vote 2 down vote accepted

The polynomials $s_p$ and $d_p$ are indeed irreducible: We have $a_p(c)=s_p(c)d_p(c)$ with $s_p$ and $d_p$ monic of degree $m=(p-1)/2$. Let $z$ be another variable. Then $z^{2m}a_p(z+1/z)=(z^ms_p(z+1/z))(z^md_p(z+1/z))$. The two factors on the right hand side are monic polynomials, and if we show that they are irreducible, then $s_p(x)$ and $d_p(c)$ are irreducible even more.

Using the explicit expression of $a_p(c)$ from Paolo's answer to this related question shows that \begin{equation} z^{2m}a_p(z+1/z)=(1+z+\dots+z^{p-2}+z^{p-1})(1-z+\dots-z^{p-2}+z^{p-1})=\Phi(z)\Phi(-z), \end{equation} where $\Phi(z)$ is the $p$-th cyclotomic polynomial. But $\Phi(z)$ is well known to be irreducible, and the claim follows.

share|improve this answer
add comment

With the substitution $c=x+2$, Eisentstein's criterion can be used. Then the first few polynomials $a_{m}+a_{m+1}$ become

$$\begin{align*} a_0+a_1&=1 \\a_1+a_2&=3+x \\ a_2+a_3&=5+5x+x^2\\a_3+a_4&=7+14x+7x^2+x^3\\a_4+a_5&=9+30x+27x^2+9x^3+x^4\\a_5+a_6&=11+55x+77x^2+44x^3+11x^4+x^5 \end{align*}$$

Evidently,when $p=2m+1$ is prime, the monic polynomial $$a_{m}+a_{m+1}=\left(\sum_{j=0}^{2m}b_jx^j\right)+x^{2m+1}$$ is such that all the coeffcients $b_i$ are multiples of $p$ including $b_0=p.$ If true (which it is), this is exactly what is needed to prove irreducibility.

It turns out (eventually) that $$ \begin{align*} b_0&=(2m+1)\\b_1&=(2m+1)\frac{m(m+1)}{3!}\\b_2&=(2m+1)\frac{m(m+1)(m+2)(m+3)}{5!}\end{align*}$$ and in general $$b_i=b_i(m)=\frac{2m+1}{2i+1}\binom{m+i}{2i}.$$

It may not be obvious that these are integers, but they are, and hence, as claimed, $b_i(m)$ is divisible by $p=2m+1$ when that number is prime.


After the fact, an easier description of the coefficients is as follows:

The odd integers give the constant terms $b_0(m)$

$[1,3,5,7,9,11,13,\cdots]$ whose partial sums are the squares

$[1,4,9,16,25,36,49,\cdots]$ whose partial sums (with a shift) are the $b_1(m)$

$[0,1,5,14,30,55,91,140,\cdots]$ and their partial sums are

$[0,1,6,20,50,105,196,236,\cdots]$ and their partial sums (with a shift) are the $b_2(m)$

$[0,0,1,7,27,77,182,378,714,\cdots]$ whose partial sums

$[0,0,1,8,35,\cdots]$ have as partial sums the $b_3(m)$

$[0,0,0,1,9,44,\cdots]$ etc.

share|improve this answer
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.