4
$\begingroup$

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

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

$\endgroup$
7
  • $\begingroup$ Can you please add some values of $\mathcal{I_n}$? My numericals aren't agreeing what I think you're saying. $\endgroup$ Commented 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$ Commented Jan 18, 2018 at 16:15
  • $\begingroup$ Yes, that's helpful. Thank you. $\endgroup$ Commented 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$ Commented Jan 19, 2018 at 16:13
  • $\begingroup$ You're absolutely right! Does the word "odd divisor" exclude 1 and 2n+1? $\endgroup$ Commented Jan 19, 2018 at 16:56

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Commented 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$ Commented 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$ Commented 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$ Commented Jan 21, 2018 at 23:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.