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


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

Notes added:

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

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

1 Answer 1


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} $$

and all your conjectures follow.

  • $\begingroup$ 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". $\endgroup$
    – user
    Jan 20, 2018 at 20:44
  • $\begingroup$ @user355705 Answer to first question : the $M_d$ have no common root, so they are coprime, so we may use Gauss' lemma. $\endgroup$ Jan 20, 2018 at 20:50
  • $\begingroup$ @user355705 Answer to the second question : www2.oberlin.edu/faculty/jcalcut/tanpap.pdf, prop.2, p.5 $\endgroup$ Jan 20, 2018 at 20:52
  • $\begingroup$ 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. $\endgroup$
    – user
    Jan 21, 2018 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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