Chebyshev Polynomials and Primality Testing

Question

Let $T(n,x)$ be the nth Chebyshev polynomial of the first kind and let $U(n-1,x)$ the $(n-1)$th Chebyshev polynomial of the second kind. Would any one kindly help show that

1) $n$ is prime iff $T(n,x)$ is irreducible in $\mathbb{Z}[x]$.

2) $n$ is prime iff $U(n-1,x)$, expressed in powers of $(x^2-1)$, is irreducible in $\mathbb{Z}[x]$.

Many Thanks!!

---

No "ordering" is implied here. The wording of the question was done in similar fashion as any question in any math/research question. I do not see how a person who is asking for help would be ordering people to help.

Any way back to the topic,

For the first part of the question, I noticed that if n is prime, then T(n,x) satisfies Eisenstein's Irreducibility Criterion. But I am not sure how to show if T(n,x) is irreducible then n is prime.

Answer 1

I think the result for $T$ is in Hong Jen Hsiao, On factorization of Chebyshev's polynomials of the first kind, Bull. Inst. Math. Acad. Sinica 12 (1984), no. 1, 89–94, MR0743938 (86e:11017). Also, it looks like there is a proof in Rayes, M. O.; Trevisan, V.; Wang, P. S.; Factorization properties of Chebyshev polynomials, Comput. Math. Appl. 50 (2005), no. 8-9, 1231–1240, MR2175585 (2007e:33010), a version of which is available at http://icm.mcs.kent.edu/reports/1998/ICM-199802-0001.pdf.

Answer 2

The following was found at http://perso.uclouvain.be/alphonse.magnus/num1a/chebprim.htm

From: Robin Chapman
[1] Re: Primality Test Using Chebyshev Polynomials! Date: Fri Feb 20 05:35:18 EST 1998

---

Its roots are the non-zero numbers of the form $\cos(\pi/2n + 2j \pi)$ where $j$ is an integer. They include $\cos(\pi/2n)$ which generates the real subfield of the cyclotomic field $Q(\exp(2 \pi i/4n))$. This cyclotomic field has degree $\phi(4n) = 2 \phi(n)$ (where $\phi$ is the Euler function) and its real subfield has degree $\phi(n)$ [this is due to the irreducibility of the cyclotomic polynomials]. So the minimal polynomial of $\cos(\pi/2n)$ has degree $\phi(n)$, and so equals the Chebyshev divided by $x$ iff $\phi(n) = n-1$ iff $n$ is prime.

A related but simpler "primality test" is that p is prime iff Of course both of these "tests" are useless in practical terms.

---

Robin Chapman "256 256 256.

Department of Mathematics O hel, ol rite; 256; whot's

University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no.

[email protected] 2 dificult 2 work out."

http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn

Answer 3

I proved the following result, see http://arxiv.org/abs/1110.6620

Let $\psi_n(x)$ be the minimal polynomial of the algebraic integer $2 \cos \frac{2 \pi}{n}$. Then

$$ U_n(x)=\prod_{\substack{ j|2n+2 \\ j\not=1,2}} \psi_j(2x) \ . $$ Let $n=2^{\alpha} N$ where $N$ is odd and let $r=2^{\alpha+2}$. Then

$$ T_n(x)=\frac{1}{2}\prod_{\substack{ j|N \\ }} \psi_{r j}(2x) \ . $$

For example to prove i) (which should be corrected). Let $n=p$ prime. Then $\alpha=0$, $N=p$, and $r=4$. Therefore $$ T_n(x)=\frac{1}{2} \psi_4(2x) \psi_{4p}(2x) $$

Note that $\psi_4(x)=x$. As a result, $n$ prime is equivalent to $\frac{1}{x} T_n(x)$ is irreducible.