# On reducibility over $\mathbb{Z}$ of a special class of polynomials .

### Definitions

Let positive integer number $n$ be referred to as $p$-composite if there exist such positive integer numbers $k_1$ and $k_2$ that $$n=k_1+k_2+2k_1k_2\equiv k_1*k_2.$$

Let $\mathbb{K}_n$ be the set of all distinct ordered pairs $(k_1,k_2)$, such that $n=k_1*k_2$. Let the cardinality of the set $\mathbb{K}_n$ incremented by 1 be referred to as composition index ${\cal I}_n$ of the number $n$.

Based on numerical evidence I propose the following

### Conjecture

The polynomial $$P_n(x)=\sum_{i=0}^n(-1)^{\left\lfloor\frac{i+1}{2}\right\rfloor}\binom{\left\lfloor\frac{n+i}{2}\right\rfloor}{i}x^i$$ is reducible to product of exactly ${\cal I}_n$ irreducible polynomials over $\mathbb{Z}$.

Particularly this means that if $n$ is not $p$-composite $({\cal I}_n=1)$ the polynomial $P_n(x)$ is irreducible.

I would be thankful for any hint on proving or disproving the conjecture.

The following information may appear useful:

1. $P_n$ is characteristic polynomial of $n\times n$ dimensional integer matrix $M$ introduced in my previous question.

2. (based on numerical evidence) The polynomial $P_{k_1}((-1)^{k_2}x)$ divides the polynomial $P_{k_1*k_2}(x)$.

The first $p$-composite number is $\small 4$ with $\small {\cal I}_4=2$, the next $\small7$ with $\small{\cal I}_7=3$ and so on. As pointed out by Ewan Delanoy, $\small {\cal I}_n$ is just the decremented by 1 number of all distinct divisors of $\small 2n+1$. More generally if $\small d | 2n+1$, $\small k=\frac{d-1}{2}$ is "$\small p$-divisor" of $\small n$.

• Can you please add some values of $\mathcal{I_n}$? My numericals aren't agreeing what I think you're saying. Jan 18, 2018 at 16:06
• I am afraid not quite understanding your question. Do you mean something like ${\cal I}_4=2$, ${\cal I}_7=3$ and so on?
– user
Jan 18, 2018 at 16:15
• Yes, that's helpful. Thank you. Jan 18, 2018 at 16:59
• $n=k_1\star k_2$ iff $2n+1=(2k_1+1)(2k_2+1)$, so ${\cal I}_n-1$ is the number of odd divisors of $2n+1$ Jan 19, 2018 at 16:13
• You're absolutely right! Does the word "odd divisor" exclude 1 and 2n+1?
– user
Jan 19, 2018 at 16:56

All your conjectures are correct. The polynomials you have re-discovered are "real" analogues of the cyclotomic polynomials : their roots are (the double of) real parts of roots of unity. The factorization you have re-discovered is quite analogous to $X^n-1=\prod_{d\mid n}\Phi_d$, and indeed the proofs are quite similar as we will see in a moment.

Lemma. The roots of $P_n$ are exactly the numbers of the form $2\cos\bigg(\frac{l}{2n+1}\pi\bigg)$ for $0 \lt l \lt 2n+1$ and $l\equiv n \ [mod\ 2]$.

Proof of lemma : we use the fact mentioned in the question, that $P$ is (up to sign) the characteristic polynomial of the "anti-diagonal" matrix $M=(m_{ij})$ defined by $$m_{ij}=\left\lbrace \begin{array}{ll} -1 & \textrm{if}\ i+j=m, \\ 1 & \textrm{if}\ i+j=m+1, \\ 0 & \textrm{otherwise.} \\ \end{array} \right.$$

Let $\eta_k=e^{\frac{2k\pi i}{2(2n+1)}}$ $(0<k<2n+1)$. Let $u$ be the column matrix $u=(u_1,u_2,\ldots,u_n)$ where $u_j=(-1)^j (\eta^{2j}_k-\eta^{-2j}_k)$. A routine verification shows that $u$ is an eigenvector for $M$, associated with the eigenvalue $\lambda_k=(-1)^{n-k}(\eta^1_k+\eta^{-1}_k)$. Now $\lambda_k=2\cos\bigg(\frac{l}{2n+1}\pi\bigg)$ where $$l=\left\lbrace \begin{array}{ll} k & \textrm{when}\ k \equiv n [\mathsf{mod} \ 2] , \\ 2n+1-k & \textrm{when}\ k \not\equiv n [\mathsf{mod} \ 2]. \\ \end{array} \right.$$ So we have found $n$ distinct eigenvalues $\lambda_1,\ldots,\lambda_n$ for a $n\times n$ matrix, therefore there are no other eignevalues and the lemma is proved.

Rather than work on $P_n$ directly, it will be more convenient to use its rescaled version : $$Q_n=(-1)^{\left\lfloor\frac{n+1}{2}\right\rfloor}P_n((-1)^{n-1}x) \tag{1}$$

Then $Q_n$ is always monic, and the roots of $Q_n$ are exactly the numbers of the form $\mu_l=2\cos\bigg(\frac{l}{2n+1}\pi\bigg)$ for $0 \lt l \lt 2n+1$ and $l$ is odd. For any $m>0$, let us put $\rho_{m}=2\cos(\frac{\pi}{m})$, and let $M_m$ be the minimal polynomial of $\rho_{m}$ over $\mathbb Q$. For any divisor $d$ of $2n+1$, $\rho_d$ is a root of $Q_n$ so $M_d$ must divide $Q_n$. It follows that

$$\Bigg(\prod_{d\mid 2n+1,d \gt 1} M_d\Bigg) \ \textrm{divides} \ Q_n \tag{2}$$

Now, it is a well-known exercise that the degree of $M_d$ is $\frac{\phi(2d)}{2}=\phi(d)$. So the two sides in (2) have the same degree, and (2) is in fact an equality :

$$Q_n=\prod_{d\mid 2n+1,d \gt 1} M_d \tag{3}$$

• I find you answer really brilliant. However I have some questions. I cannot quite follow why from "$M_d$ divides $Q_n$" follows that the product of $M_d$ also divides $Q_n$. Please give also a reference to the "well-known exercise".
• @user355705 Answer to first question : the $M_d$ have no common root, so they are coprime, so we may use Gauss' lemma. Jan 20, 2018 at 20:50
• Thank you. Some suggestions: I believe the correct exponent for $(-1)$ in the first expression for $\lambda_k$ is $n-k$ (as it was in the first version). I would also suggest to remove unnecessary factor $\eta^2$ in definition of $u_j$, if there is no special reason for its presence.