Cyclotomic pre-polynomial

For every $n\ge 3$, corresponding to the cyclotomic polynomial ${\mathrm{\Phi }}_n(x)$ of degree $\phi (n)$ there exists a unique polynomial ${\mathrm{\Psi }}_n(x)$ of degree $\phi (n)/2$ such that $$x^{\phi (n)/2}{\mathrm{\Psi }}_n(x+\frac{1}{x})={\mathrm{\Phi }}_n(x),$$ where $\phi (n)$ denotes Euler's totient function.

The polynomials ${\mathrm{\Psi }}_n(x)$ may be referred to as cyclotomic pre-polynomials, since the cyclotomic polynomials can be obtained from them via a well-defined mapping.

Alternatively, the cyclotomic pre-polynomial ${\mathrm{\Psi }}_n(x)$ can be defined as $${\mathrm{\Psi }}_n(x)=\prod (x-2\cos \frac{2k\pi }{n}),$$ where product is taken over all positive integers $k<n/2$ that are relative prime to $n$.

For n up to 30, the cyclotomic pre-polynomials are:

$\begin{array}{rl}{\mathrm{\Psi }}_3(x)& =x+1\\ {\mathrm{\Psi }}_4(x)& =x\\ {\mathrm{\Psi }}_5(x)& =x^2+x-1\\ {\mathrm{\Psi }}_6(x)& =x-1\\ {\mathrm{\Psi }}_7(x)& =x^3+x^2-2x-1\\ {\mathrm{\Psi }}_8(x)& =x^2-2\\ {\mathrm{\Psi }}_9(x)& =x^3-3x+1\\ {\mathrm{\Psi }}_{10}(x)& =x^2-x-1\\ {\mathrm{\Psi }}_{11}(x)& =x^5+x^4-4x^3-3x^2+3x+1\\ {\mathrm{\Psi }}_{12}(x)& =x^2-3\\ {\mathrm{\Psi }}_{13}(x)& =x^6+x^5-5x^4-4x^3+6x^2+3x-1\\ {\mathrm{\Psi }}_{14}(x)& =x^3-x^2-2x+1\\ {\mathrm{\Psi }}_{15}(x)& =x^4-x^3-4x^2+4x+1\\ {\mathrm{\Psi }}_{16}(x)& =x^4-4x^2+2\\ {\mathrm{\Psi }}_{17}(x)& =x^8+x^7-7x^6-6x^5+15x^4+10x^3-10x^2-4x+1\\ {\mathrm{\Psi }}_{18}(x)& =x^3-3x-1\\ {\mathrm{\Psi }}_{19}(x)& =x^9+x^8-8x^7-7x^6+21x^5+15x^4-20x^3-10x^2+5x+1\\ {\mathrm{\Psi }}_{20}(x)& =x^4-5x^2+5\\ {\mathrm{\Psi }}_{21}(x)& =x^6-x^5-6x^4+6x^3+8x^2-8x+1\\ {\mathrm{\Psi }}_{22}(x)& =x^5-x^4-4x^3+3x^2+3x-1\\ {\mathrm{\Psi }}_{23}(x)& =x^{11}+x^{10}-10x^9-9x^8+36x^7+28x^6-56x^5-35x^4+35x^3+15x^2-6x-1\\ {\mathrm{\Psi }}_{24}(x)& =x^4-4x^2+1\\ {\mathrm{\Psi }}_{25}(x)& =x^{10}-10x^8+35x^6+x^5-50x^4-5x^3+25x^2+5x-1\\ {\mathrm{\Psi }}_{26}(x)& =x^6-x^5-5x^4+4x^3+6x^2-3x-1\\ {\mathrm{\Psi }}_{27}(x)& =x^9-9x^7+27x^5-30x^3+9x+1\\ {\mathrm{\Psi }}_{28}(x)& =x^6-7x^4+14x^2-7\\ {\mathrm{\Psi }}_{29}(x)& =x^{14}+x^{13}-13x^{12}-12x^{11}+66x^{10}+55x^9-165x^8-120x^7\\ & +210x^6+126x^5-126x^4-56x^3+28x^2+7x-1\\ {\mathrm{\Psi }}_{30}(x)& =x^4+x^3-4x^2-4x+1.\end{array}$

Applications

It is well known that cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers. From this fact it obviously follows that cyclotomic pre-polynomials are also irreducible over the field of the rational numbers.

Because of their irreducibility, both cyclotomic polynomials and cyclotomic pre-polynomials are useful in the irreducible factorization of polynomials.

Examples of their application for irreducible factorization:

1. Power functions defining complex roots of unity and their compositions

By the definition of cyclotomic polynomials, for any positive integer $k$ $$x^{kn}-1=\prod _{d\mid kn}{\mathrm{\Phi }}_d(x).$$

Two examples of such compositions are $$x^{2n}+1=\prod _{d\ge 3,d\mid 4n,d\nmid 2n}{\mathrm{\Phi }}_d(x)$$ and $$\sum _{k=0}^n{x}^{2k}=\frac{x^{2n+2}-1}{x^2-1}=\prod _{d\ge 3,d\mid 2n+2}{\mathrm{\Phi }}_d(x).$$

2. Chebyshev polynomials

For the purpose of factorization, it is more convenient to first consider the following polynomials before factoring the original Chebyshev polynomials $T_n(x)$ and $U_n(x)$.

Vieta-Lucas polynomial is defined by $$C_n(x)=2T_n\left(\frac{x}{2}\right)$$ for which we also have $$2\cos n\vartheta =C_n(2\cos \vartheta ),$$ and the Vieta-Fibonacci polynomial is defined by $$S_n(x)=U_n\left(\frac{x}{2}\right)$$ for which we also have $$\sin ((n+1)\vartheta )=\sin \vartheta S_n(2\cos \vartheta ).$$

The irreducible factorization of these polynomials are ase follows. $$C_n(x)=\prod _{d\ge 3,d\mid 4n,d\nmid 2n}{\mathrm{\Psi }}_d(x)$$ and $$S_n(x)=\prod _{d\ge 3,d\mid 2n+2}{\mathrm{\Psi }}_d(x).$$

Now, it follows directly that the Chebyshev polynomials $T_n(x)$ and $U_n(x)$ can be factorized as follows: $$T_n(x)=\frac{1}{2}\prod _{d\ge 3,d\mid 4n,d\nmid 2n}{\mathrm{\Psi }}_d(2x)$$ and $$U_n(x)=\prod _{d\ge 3,d\mid 2n+2}{\mathrm{\Psi }}_d(2x).$$

By similar methods, we find that the third- and fifth kind Chebyshev polynomials, $V_n(x)$ and $W_n(x)$ can be factorized as follows: $$V_n(x)=\prod _{d\ge 3,d\mid 4n+2,d\nmid 2n+1}{\mathrm{\Psi }}_d(2x),$$ and $$W_n(x)=\prod _{d\ge 3,d\mid 2n+1}{\mathrm{\Psi }}_d(2x).$$

3. Factorization of shifted Chebyshev polynomials

Slightly different formulas hold depending on the parity of $n$.

For odd $n$ we have $$T_n(x)-1=(x-1)\prod _{d\ge 3,d\mid n}[{\mathrm{\Psi }}_d(2x){]}^2$$ and $$T_n(x)+1=(x+1)\prod _{d\ge 3,d\mid 2n,d\nmid n}[{\mathrm{\Psi }}_d(2x){]}^2,$$ while for even $n$ we have $$T_n(x)-1=2(x-1)(x+1)\prod _{d\ge 3,d\mid n}[{\mathrm{\Psi }}_d(2x){]}^2$$ and $$T_n(x)+1=\frac{1}{2}\prod _{d\ge 3,d\mid 2n,d\nmid n}[{\mathrm{\Psi }}_d(2x){]}^2.$$

Pseudo cyclotomic pre-polynomials

In formulas for the trigonometric functions of multiple angles, replacing the trigonometric functions with the corresponding hyperbolic functions often yields expressions that remain valid, either unchanged or with only minor modifications. For example: $$2\cosh n\vartheta =C_n(2\cosh \vartheta ).$$

In some other cases, the formula should be modified by replacing all coefficients of the polynomial $C_n(x)$ or $S_n(x)$ with their absolute values. Let us denote the resulting polynomials by $C_n^{\oplus }(x)$ and $S_n^{\oplus }(x)$, respectively, which can also be formally defined by formulas $C_n^{\oplus }(x)=(-i{)}^n{C}_n(ix),$ and similarly $S_n^{\oplus }(x)=(-i{)}^n{S}_n(ix).$ With this notation it can be shown that for odd $n$, $$2\sinh n\vartheta =C_n^{\oplus }(2\sinh \vartheta ),$$ while for even $n$, $$2\cosh n\vartheta =C_n^{\oplus }(2\sinh \vartheta )$$ holds.

An example with the use of $S_n^{\oplus }(x)$ is as follows: for odd $n$, $$\sinh ((n+1)\vartheta )=\cosh \vartheta S_n^{\oplus }(2\sinh \vartheta ),$$ while for even $n$, $$\cosh ((n+1)\vartheta )=\cosh \vartheta S_n^{\oplus }(2\sinh \vartheta )$$ holds.

The factors in the irreducible factorizations of $C_n^{\oplus }(x)$ and $S_n^{\oplus }(x)$ are not cyclotomic pre-polynomials, but rather another type of polynomial resembling them, which we call pseudo cyclotomic pre-polynomials and denote by ${\mathrm{\Psi }}_n^{\oplus }(x)$.

Their definition is as follows: $${\mathrm{\Psi }}_4^{\oplus }(x)={\mathrm{\Psi }}_4(x)=x;$$ $${\mathrm{\Psi }}_{4d}^{\oplus }(x)=|{\mathrm{\Psi }}_{4d}(ix)|,$$ or alternatively $${\mathrm{\Psi }}_{4d}^{\oplus }(x)=\prod _{\genfrac{}{}{0ex}{}{0<k<d}{\gcd (k,4d)=1}}[x^2+4{\cos }^2\left(\frac{k\pi }{2d}\right)]$$ for any $d>1$ integer; $${\mathrm{\Psi }}_d^{\oplus }(x)=|{\mathrm{\Psi }}_d(ix){\mathrm{\Psi }}_{2d}(ix)|,$$ or alternatively $${\mathrm{\Psi }}_d^{\oplus }(x)=\prod _{\genfrac{}{}{0ex}{}{0<k<d/2}{\gcd (k,d)=1}}[x^2+4{\cos }^2\left(\frac{2k\pi }{d}\right)]$$ for any odd $d$ greater than $1$.

The expression ${\mathrm{\Psi }}_d^{\oplus }(x)$ cannot be interpreted in the case when $d\equiv 2(\mathrm{mod}4).$

Similarly to the cyclotomic polynomials and cyclotomic pre-polynomials, the pseudo cyclotomic pre-polynomials also have only integer coefficients and are irreducible over the field of the rational numbers.

For n up to 27, the pseudo cyclotomic pre-polynomials are:

$\begin{array}{rl}{\mathrm{\Psi }}_3^{\oplus }(x)& =x^2+1\\ {\mathrm{\Psi }}_4^{\oplus }(x)& =x\\ {\mathrm{\Psi }}_5^{\oplus }(x)& =x^4+3x^2+1\\ \\ {\mathrm{\Psi }}_7^{\oplus }(x)& =x^6+5x^4+6x^2+1\\ {\mathrm{\Psi }}_8^{\oplus }(x)& =x^2+2\\ {\mathrm{\Psi }}_9^{\oplus }(x)& =x^6+6x^4+9x^2+1\\ \\ {\mathrm{\Psi }}_{11}^{\oplus }(x)& =x^{10}+9x^8+28x^6+35x^4+15x^2+1\\ {\mathrm{\Psi }}_{12}^{\oplus }(x)& =x^2+3\\ {\mathrm{\Psi }}_{13}^{\oplus }(x)& =x^{12}+11x^{10}+45x^8+84x^6+70x^4+21x^2+1\\ \\ {\mathrm{\Psi }}_{15}^{\oplus }(x)& =x^8+9x^6+26x^4+24x^2+1\\ {\mathrm{\Psi }}_{16}^{\oplus }(x)& =x^4+4x^2+2\\ {\mathrm{\Psi }}_{17}^{\oplus }(x)& =x^{16}+15x^{14}+91x^{12}+286x^{10}+495x^8+462x^6+210x^4+36x^2+1\\ \\ {\mathrm{\Psi }}_{19}^{\oplus }(x)& =x^{18}+17x^{16}+120x^{14}+455x^{12}+1001x^{10}+1287x^8+924x^6+330x^4+45x^2+1\\ {\mathrm{\Psi }}_{20}^{\oplus }(x)& =x^4+5x^2+5\\ {\mathrm{\Psi }}_{21}^{\oplus }(x)& =x^{12}+13x^{10}+64x^8+146x^6+148x^4+48x^2+1\\ \\ {\mathrm{\Psi }}_{23}^{\oplus }(x)& =x^{22}+21x^{20}+190x^{18}+969x^{16}+3060x^{14}\\ & +6188x^{12}+8008x^{10}+6435x^8+3003x^6+715x^4+66x^2+1\\ {\mathrm{\Psi }}_{24}^{\oplus }(x)& =x^4+4x^2+1\\ {\mathrm{\Psi }}_{25}^{\oplus }(x)& =x^{20}+20x^{18}+170x^{16}+800x^{14}+2275x^{12}+4003x^{10}+4280x^8\\ & +2605x^6+775x^4+75x^2+1\\ \\ {\mathrm{\Psi }}_{27}^{\oplus }(x)& =x^{18}+18x^{16}+135x^{14}+546x^{12}+1287x^{10}+1782x^8+1386x^6+540x^4+81x^2+1\\ \end{array}$

From all of the above, we obtain the irreducible factorization of $C_n^{\oplus }(x)$ and $S_n^{\oplus }(x)$ as follows: $$C_n^{\oplus }(x)=\prod _{d|n,2d\nmid n}{\mathrm{\Psi }}_{4d}^{\oplus }(x)$$ and $$S_n^{\oplus }(x)=\prod _{d\ge 3,d|2n+2,d\equiv ̸2(\mathrm{mod}4)}{\mathrm{\Psi }}_d^{\oplus }(x).$$

For several publicatons using cyclotomic pre-polynomials, see , . , .

This article "Cyclotomic pre-polynomial" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Cyclotomic pre-polynomial. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• 2024 Speaker of the British House of Commons election
• Deo Gracia Ngokaba
• Indira Naik
• Retrospective conversion of library systems
• Nightlife in Bangkok
• Dostana 2
• Daniel Francisco

---