Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Chebyshev polynomials of the first kind"
m
 
(8 intermediate revisions by the same user not shown)
Line 2: Line 2:
  
 
==Proof of equivalence of the two definitions==
 
==Proof of equivalence of the two definitions==
−
In the proof below, <math>T_n(x)</math> will refer to the recursive definition.
+
In the proof below, <math>T_n(x)</math> will refer to the recursive definition. Let <math>y = \arccos x</math>, so that <math>x = \cos y</math>.
  
−
For the <math>n = 0</math> base case, <cmath>\cos(0 \arccos x) = \cos 0 = 1 = T_0(x);</cmath> for the <math>n = 1</math> base case, <cmath>\cos(1 \arccos (x)) = \cos(\arccos (x)) = x = T_1(x).</cmath>
+
For the <math>n = 0</math> base case, <cmath>\cos 0 = 1 = T_0(x);</cmath> for the <math>n = 1</math> base case, <cmath>\cos y = x = T_1(x).</cmath>
  
−
Now for the inductive step, let <math>y = \arccos x</math>, so that <math>x = \cos y</math>. We then assume that <math>\cos ((n-1)y) = T_{n-1}(x)</math> and <math>\cos ny = T_n(x)</math>, and we wish to prove that <math>\cos ((n+1)y) = T_{n+1}(x)</math>.
+
Now for the inductive step, we assume that <math>\cos ((n-1)y) = T_{n-1}(x)</math> and <math>\cos ny = T_n(x)</math>, and we wish to prove that <math>\cos ((n+1)y) = T_{n+1}(x)</math>.
  
−
From the [[Trigonometric identities#Angle addition identities|cosine sum and difference identities]] we have <cmath> \cos ((n+1)y) = \cos (ny+y) = \cos ny \cos y - \sin ny \sin y</cmath> and <cmath> \cos ((n-1)y )= \cos (ny-y) = \cos ny \cos y + \sin ny \sin y.</cmath> The sum of these equations is <cmath> \cos ((n+1)y) + \cos ((n-1)y) = 2 \cos ny \cos y;</cmath> rearranging, <cmath> \cos ((n+1)y) = 2 \cos y \cos ny  - \cos ((n-1)y).</cmath>
+
From the [[Trigonometric identities#Angle addition identities|cosine sum and difference identities]] we have <cmath>\begin{align*} \cos ((n+1)y) &= \cos (ny+y) = \cos ny \cos y - \sin ny \sin y, \\ \cos ((n-1)y) &= \cos (ny-y) = \cos ny \cos y + \sin ny \sin y. \end{align*}</cmath> The sum of these equations is <cmath> \cos ((n+1)y) + \cos ((n-1)y) = 2 \cos ny \cos y;</cmath> rearranging, <cmath> \cos ((n+1)y) = 2 \cos y \cos ny  - \cos ((n-1)y).</cmath> Substituting our assumptions yields <cmath> \cos ((n+1)y) = 2xT_n(x) - T_{n-1}(x) = T_{n+1}(x),</cmath> as desired.
−
Substituting our assumptions yields <cmath> \cos ((n+1)y) = 2xT_n(x) - T_{n-1}(x) = T_{n+1}(x),</cmath> as desired.
 
  
 
==Composition identity==
 
==Composition identity==
Line 28: Line 27:
 
For all <math>k</math>, we have <cmath>T_{k}(x) = 2T_{k}(x) - T_k(x) = 2T_0(x)T_{k}(x) - T_{k}(x),</cmath> and for all <math>k \geq 1</math>, <cmath>T_{k+1}(x) = 2xT_k(x) - T_{k-1}(x) = 2T_1(x)T_k(x) - T_{k-1}(x),</cmath> proving the lemma for <math>n = 0</math> and <math>n = 1</math> respectively.  
 
For all <math>k</math>, we have <cmath>T_{k}(x) = 2T_{k}(x) - T_k(x) = 2T_0(x)T_{k}(x) - T_{k}(x),</cmath> and for all <math>k \geq 1</math>, <cmath>T_{k+1}(x) = 2xT_k(x) - T_{k-1}(x) = 2T_1(x)T_k(x) - T_{k-1}(x),</cmath> proving the lemma for <math>n = 0</math> and <math>n = 1</math> respectively.  
  
−
Suppose the lemma holds for <math>n - 1</math> and <math>n</math>; that is, <math>T_{k+n}(x) = 2T_{n}(x)T_k(x) - T_{k-n}(x)</math> and <math>T_{k+n-1}(x) = 2T_{n-1}(x)T_k(x) - T_{k-n+1}(x)</math>. Then multiplying the first equation by <math>2x</math> and subtracting the second equation gives <cmath>2xT_{k+n}(x) - T_{k+n-1}(x) = 2(2xT_{n}(x) - T_{n-1}(x))T_k(x) - (2xT_{k-n}(x) - T_{k-n+1}(x)),</cmath> which simplifies to <cmath>T_{k+n+1}(x) = 2T_{n+1}(x)T_k(x) - T_{k-n-1}(x)</cmath> using the original recursive definition, as long as <math>k-n-1 \geq 0</math>. Thus, the lemma holds for <math>n + 1</math> (as long as <math>n + 1 \leq k</math>), completing the inductive step.
+
Suppose the lemma holds for <math>n - 1</math> and <math>n</math>; that is, <cmath>\begin{align*} T_{k+n}(x) &= 2T_{n}(x)T_k(x) - T_{k-n}(x), \\ T_{k+n-1}(x) &= 2T_{n-1}(x)T_k(x) - T_{k-n+1}(x). \end{align*}</cmath> Then multiplying the first equation by <math>2x</math> and subtracting the second equation gives <cmath>2xT_{k+n}(x) - T_{k+n-1}(x) = 2(2xT_{n}(x) - T_{n-1}(x))T_k(x) - (2xT_{k-n}(x) - T_{k-n+1}(x)),</cmath> which simplifies to <cmath>T_{k+n+1}(x) = 2T_{n+1}(x)T_k(x) - T_{k-n-1}(x)</cmath> using the original recursive definition, as long as <math>k-n-1 \geq 0</math>. Thus, the lemma holds for <math>n + 1</math> (as long as <math>n + 1 \leq k</math>), completing the inductive step.
  
 
To prove the claim, we now fix <math>n</math> and induct on <math>m</math>.
 
To prove the claim, we now fix <math>n</math> and induct on <math>m</math>.
Line 34: Line 33:
 
For all <math>n</math>, we have <cmath>T_0(T_n(x)) = 1 = T_0(x)</cmath> and <cmath>T_1(T_n(x)) = T_n(x),</cmath> proving the claim for <math>m = 0</math> and <math>m = 1</math> respectively.  
 
For all <math>n</math>, we have <cmath>T_0(T_n(x)) = 1 = T_0(x)</cmath> and <cmath>T_1(T_n(x)) = T_n(x),</cmath> proving the claim for <math>m = 0</math> and <math>m = 1</math> respectively.  
  
−
Suppose the claim holds for <math>m - 1</math> and <math>m</math>; that is, <math>T_{m-1}(T_n(x)) = T_{(m-1)n}(x)</math> and <math>T_m(T_n(x)) = T_{mn}(x)</math>. We may also assume <math>m \geq 2</math>, since the smaller cases have already been proven, in order to ensure that <math>n \leq mn</math>. Then by the lemma (with <math>k = mn</math>) and the original recursive definition,
+
Suppose the claim holds for <math>m - 1</math> and <math>m</math>; that is, <cmath>\begin{align*} T_{m-1}(T_n(x)) &= T_{(m-1)n}(x), \\ T_m(T_n(x)) &= T_{mn}(x). \end{align*}</cmath> We may also assume <math>m \geq 2</math>, since the smaller cases have already been proven, in order to ensure that <math>n \leq mn</math>. Then by the lemma (with <math>k = mn</math>) and the original recursive definition,
 
<cmath> \begin{align*}  
 
<cmath> \begin{align*}  
 
T_{(m+1)n}(x) &= T_{mn+n}(x) \\
 
T_{(m+1)n}(x) &= T_{mn+n}(x) \\
Line 48: Line 47:
 
These roots are also called<b> Chebyshev nodes</b>.
 
These roots are also called<b> Chebyshev nodes</b>.
  
−
==Connection to roots of unity==
+
===Connection to roots of unity===
−
Because cosine is <math>1</math> only at integer multiples of <math>2\pi</math>, the roots of the polynomial <math>T_n(x) - 1</math> follow the simpler formula <math>\cos \frac{2k\pi}{n}</math>. The <math>n</math>th roots of unity have arguments of <math>\frac{2k\pi}{n}</math> and magnitude <math>1</math>, so the roots of <math>T_n(x) - 1</math> are the real parts of the <math>n</math>th roots of unity. This lends intuition to several patterns.
+
Because cosine is <math>1</math> only at integer multiples of <math>2\pi</math>, the roots of the polynomial <math>T_n(x) - 1</math> follow the simpler formula <math>\cos \frac{2k\pi}{n}</math>. The <math>n</math>th [[roots of unity]] have arguments of <math>\frac{2k\pi}{n}</math> and magnitude <math>1</math>, so the roots of <math>T_n(x) - 1</math> are the real parts of the <math>n</math>th roots of unity. This lends intuition to several patterns.
  
 
All roots of <math>T_n(x) - 1</math> are also roots of <math>T_{mn}(x) - 1</math>, since all <math>n</math>th roots of unity are also <math>mn</math>th roots of unity. This can also be shown algebraically as follows: Suppose <math>T_n(x) - 1 = 0</math>. Then <cmath>T_{mn}(x) - 1 = T_m(T_n(x)) - 1 = T_m(1) - 1 = 1 - 1 = 0,</cmath>
 
All roots of <math>T_n(x) - 1</math> are also roots of <math>T_{mn}(x) - 1</math>, since all <math>n</math>th roots of unity are also <math>mn</math>th roots of unity. This can also be shown algebraically as follows: Suppose <math>T_n(x) - 1 = 0</math>. Then <cmath>T_{mn}(x) - 1 = T_m(T_n(x)) - 1 = T_m(1) - 1 = 1 - 1 = 0,</cmath>
 
using the composition identity and the fact that <math>T_m(1) = \cos(m \arccos 1) = \cos 0 = 1</math> for all <math>m</math>.
 
using the composition identity and the fact that <math>T_m(1) = \cos(m \arccos 1) = \cos 0 = 1</math> for all <math>m</math>.
  
−
Particular cases include that <math>1</math>, being a root of <math>T_1(x) - 1 = x - 1</math>, is a root of <math>T_n(x) - 1</math> for all positive <math>n</math>, and <math>-1</math>, being a root of <math>T_2(x) - 1 = 2x^2 - 2</math>, is a root of <math>T_n(x) - 1</math> for all positive even <math>n</math>. All other roots of <math>T_n(x) - 1</math> correspond to roots of unity which fall into [[Complex conjugate|conjugate pairs]] with the same real part. One might therefore suspect that all remaining roots of <math>T_n(x) - 1</math> are double roots. In fact, <cmath>T_{2n+1}(x) - 1= (x - 1)(W_n(x))^2</cmath> and <cmath>T_{2n+2}(x) - 1 = 2(x - 1)(x + 1)(U_n(x))^2</cmath> for polynomials <math>W_n(x)</math> and <math>U_n(x)</math> satisfying the same recurrence relation as <math>T_n(x)</math>, but with the different base cases <math>W_1(x) = 2x + 1</math> and <math>U_1(x) = 2x</math>.
+
Particular cases include that <math>1</math>, being a root of <math>T_1(x) - 1 = x - 1</math>, is a root of <math>T_n(x) - 1</math> for all positive <math>n</math>, and <math>-1</math>, being a root of <math>T_2(x) - 1 = 2x^2 - 2</math>, is a root of <math>T_n(x) - 1</math> for all positive even <math>n</math>. All other roots of <math>T_n(x) - 1</math> correspond to roots of unity which fall into [[Complex conjugate|conjugate pairs]] with the same real part. One might therefore suspect that all remaining roots of <math>T_n(x) - 1</math> are double roots. In fact, <cmath>T_{2n+1}(x) - 1= (x - 1)(W_n(x))^2</cmath> and <cmath>T_{2n+2}(x) - 1 = 2(x - 1)(x + 1)(U_n(x))^2</cmath> for polynomials <math>W_n(x)</math> and <math>U_n(x)</math> satisfying the same recurrence relation as <math>T_n(x)</math>, but with the different base cases <math>W_1(x) = 2x + 1</math> and <math>U_1(x) = 2x</math>. The polynomials <math>U_n(x)</math> are known as [[Chebyshev polynomials of the second kind]].
 +
 
 +
===Rational roots===
 +
The rational roots of <math>T_n(x) - 1</math> for any <math>n</math> must be elements of the set <math>S = \{ -1, -\frac{1}{2}, 0, \frac{1}{2}, 1 \}</math>. This can be proven as follows.
 +
 
 +
Any root other than <math>1</math> of <math>T_{2n+1}(x) - 1</math> must be a root of <math>W_n(x)</math>. The polynomials <math>w_n(x) = W_n \left( \frac{x}{2} \right)</math> satisfy the recursive formula <cmath>\begin{align*} w_0(x) &= 1 \\ w_1(x) &= x + 1 \\ w_{n+1}(x) &= xw_n(x) - w_{n-1}(x), \end{align*}</cmath> ensuring that they have integer coefficients and are monic for all <math>n</math>. Furthermore, their constant terms satisfy <cmath>w_{n+1}(0) = -w_{n-1}(0),</cmath> and so are always either <math>-1</math> or <math>1</math>. Thus, by the [[Rational Root Theorem]], any rational roots of <math>w_n(x)</math> must be <math>-1</math> or <math>1</math>, so the only possible rational roots of <math>W_n(x)</math> are <math>-\frac{1}{2}</math> and <math>\frac{1}{2}</math>. Thus, the only possible rational roots of <math>T_{2n+1}(x) - 1</math> are <math>-\frac{1}{2}</math>, <math>\frac{1}{2}</math>, and <math>1</math>, each an element of <math>S</math>.
 +
 
 +
By the composition identity, <math>T_{2n}(x) - 1 = T_{n}(T_{2}(x)) - 1</math>. If <math>x</math> is rational, then <math>T_2(x) = 2x^2 - 1</math> is rational also. Therefore, if all rational roots of <math>T_n(x) - 1</math> lie in <math>S</math>, then any rational root of <math>T_{2n}(x) - 1</math> must be a solution of <math>2x^2 - 1 = s</math> for some <math>s \in S</math>. The following five cases show that the rational roots of <math>T_{2n}(x) - 1</math> must lie in <math>S</math> as well:
 +
<cmath>\begin{align*}  2x^2 - 1 = -1 &\Longrightarrow x = 0, \\ 2x^2 - 1 = -\frac{1}{2} &\Longrightarrow x = \pm \frac{1}{2}, \\ 2x^2 - 1 = 0 &\Longrightarrow x = \pm \frac{\sqrt 2}{2}, \\  2x^2 - 1 = \frac{1}{2} &\Longrightarrow x = \pm \frac{\sqrt 3}{2}, \\ 2x^2 - 1 = 1 &\Longrightarrow x = \pm 1. \end{align*}</cmath>
 +
 
 +
Because any value <math>\cos \frac{a\pi}{b}</math> for integer <math>a</math> and positive integer <math>b</math> is a root of <math>T_{2b}(x) - 1</math>, the five elements of <math>S</math> are the only rational values of the cosine of a rational multiple of <math>\pi</math>. This result is known as <b>Niven's Theorem</b>.
 +
 
 +
===Constructible roots===
 +
The <math>n</math>th roots of unity form a [[regular polygon]] with <math>n</math> sides and [[circumradius]] <math>1</math> in the [[complex plane]]. Therefore, such a polygon can be constructed if and only if the position of some primitive <math>n</math>th root of unity can be constructed. The root of unity in turn can be constructed if and only if its real part is a [[constructible number]].
 +
 
 +
Just as primitive roots of unity are roots of <math>x^n - 1</math> but not of <math>x^d - 1</math> for any <math>d < n</math>, the roots of <math>T_n(x) - 1</math> that are the real parts of primitive roots of unity are roots of <math>T_n(x) - 1</math> but not of <math>T_d(x) - 1</math> for any <math>d < n</math>. Therefore, a regular <math>n</math>-gon can be constructed if and only if <math>T_n(x) - 1</math> has a real root that is a constructible number and not a root of <math>T_d(x) - 1</math> for any <math>d < n</math>.

Latest revision as of 14:24, 26 June 2023

The Chebyshev polynomials of the first kind are defined recursively by \begin{align*} T_0(x) &= 1, \\ T_1(x) &= x, \\ T_{n+1}(x) &= 2xT_n(x) - T_{n-1}(x), \end{align*} or equivalently by \[T_n(x) = \cos (n \arccos x).\]

Proof of equivalence of the two definitions

In the proof below, $T_n(x)$ will refer to the recursive definition. Let $y = \arccos x$, so that $x = \cos y$.

For the $n = 0$ base case, \[\cos 0 = 1 = T_0(x);\] for the $n = 1$ base case, \[\cos y = x = T_1(x).\]

Now for the inductive step, we assume that $\cos ((n-1)y) = T_{n-1}(x)$ and $\cos ny = T_n(x)$, and we wish to prove that $\cos ((n+1)y) = T_{n+1}(x)$.

From the cosine sum and difference identities we have \begin{align*} \cos ((n+1)y) &= \cos (ny+y) = \cos ny \cos y - \sin ny \sin y, \\ \cos ((n-1)y) &= \cos (ny-y) = \cos ny \cos y + \sin ny \sin y. \end{align*} The sum of these equations is \[\cos ((n+1)y) + \cos ((n-1)y) = 2 \cos ny \cos y;\] rearranging, \[\cos ((n+1)y) = 2 \cos y \cos ny - \cos ((n-1)y).\] Substituting our assumptions yields \[\cos ((n+1)y) = 2xT_n(x) - T_{n-1}(x) = T_{n+1}(x),\] as desired.

Composition identity

For nonnegative integers $m$ and $n$, the identity $T_{mn} = T_m(T_n(x))$ holds.

First proof

By the trigonometric definition, $T_m(T_n(x)) = \cos(m(\arccos(\cos(n(\arccos(x))))))$.

As before, let $\arccos x = y$. We have $\arccos(\cos(ny)) = 2k\pi \pm ny$ for some integer $k$. Multiplying by $m$ and distributing gives $2mk\pi \pm mny$; taking the cosine gives $\cos (2mk\pi \pm mny) = \cos mny = \cos ( mn (\arccos x)) = T_{mn}(x)$.

For now this proof only applies where the trigonometric definition is defined; that is, for $x \in [-1,1]$. However, $T_{mn}(x)$ is a degree-$mn$ polynomial, and so is $T_m(T_n(x))$, so the fact that $T_{mn}(x) = T_m(T_n(x))$ for some $mn + 1$ distinct $x \in [-1,1]$ is sufficient to guarantee that the two polynomials are equal over all real numbers.

Second proof (Induction)

First we prove a lemma: that $T_{k+n}(x) = 2T_n(x)T_k(x) - T_{k-n}(x)$ for all $n \leq k$. To prove this lemma, we fix $k$ and induct on $n$.

For all $k$, we have \[T_{k}(x) = 2T_{k}(x) - T_k(x) = 2T_0(x)T_{k}(x) - T_{k}(x),\] and for all $k \geq 1$, \[T_{k+1}(x) = 2xT_k(x) - T_{k-1}(x) = 2T_1(x)T_k(x) - T_{k-1}(x),\] proving the lemma for $n = 0$ and $n = 1$ respectively.

Suppose the lemma holds for $n - 1$ and $n$; that is, \begin{align*} T_{k+n}(x) &= 2T_{n}(x)T_k(x) - T_{k-n}(x), \\ T_{k+n-1}(x) &= 2T_{n-1}(x)T_k(x) - T_{k-n+1}(x). \end{align*} Then multiplying the first equation by $2x$ and subtracting the second equation gives \[2xT_{k+n}(x) - T_{k+n-1}(x) = 2(2xT_{n}(x) - T_{n-1}(x))T_k(x) - (2xT_{k-n}(x) - T_{k-n+1}(x)),\] which simplifies to \[T_{k+n+1}(x) = 2T_{n+1}(x)T_k(x) - T_{k-n-1}(x)\] using the original recursive definition, as long as $k-n-1 \geq 0$. Thus, the lemma holds for $n + 1$ (as long as $n + 1 \leq k$), completing the inductive step.

To prove the claim, we now fix $n$ and induct on $m$.

For all $n$, we have \[T_0(T_n(x)) = 1 = T_0(x)\] and \[T_1(T_n(x)) = T_n(x),\] proving the claim for $m = 0$ and $m = 1$ respectively.

Suppose the claim holds for $m - 1$ and $m$; that is, \begin{align*} T_{m-1}(T_n(x)) &= T_{(m-1)n}(x), \\ T_m(T_n(x)) &= T_{mn}(x). \end{align*} We may also assume $m \geq 2$, since the smaller cases have already been proven, in order to ensure that $n \leq mn$. Then by the lemma (with $k = mn$) and the original recursive definition, \begin{align*} T_{(m+1)n}(x) &= T_{mn+n}(x) \\ &= 2T_n(x)T_{mn}(x) - T_{mn - n}(x) \\ &= 2T_n(x)T_{mn}(x) - T_{(m-1)n}(x) \\ &= 2T_n(x)T_m(T_n(x)) - T_{m-1}(T_n(x)) \\ &= T_{m+1}(T_n(x)), \\ \end{align*} completing the inductive step.

Roots

Since $T_n(\cos y) = \cos ny$, and the values of $ny$ for which $\cos ny = 0$ are $\frac{2k+1}{2}\pi$ for integers $k$, the roots of $T_n(x)$ are of the form \[\cos \left( \frac{2k+1}{2n}\pi \right).\]

These roots are also called Chebyshev nodes.

Connection to roots of unity

Because cosine is $1$ only at integer multiples of $2\pi$, the roots of the polynomial $T_n(x) - 1$ follow the simpler formula $\cos \frac{2k\pi}{n}$. The $n$th roots of unity have arguments of $\frac{2k\pi}{n}$ and magnitude $1$, so the roots of $T_n(x) - 1$ are the real parts of the $n$th roots of unity. This lends intuition to several patterns.

All roots of $T_n(x) - 1$ are also roots of $T_{mn}(x) - 1$, since all $n$th roots of unity are also $mn$th roots of unity. This can also be shown algebraically as follows: Suppose $T_n(x) - 1 = 0$. Then \[T_{mn}(x) - 1 = T_m(T_n(x)) - 1 = T_m(1) - 1 = 1 - 1 = 0,\] using the composition identity and the fact that $T_m(1) = \cos(m \arccos 1) = \cos 0 = 1$ for all $m$.

Particular cases include that $1$, being a root of $T_1(x) - 1 = x - 1$, is a root of $T_n(x) - 1$ for all positive $n$, and $-1$, being a root of $T_2(x) - 1 = 2x^2 - 2$, is a root of $T_n(x) - 1$ for all positive even $n$. All other roots of $T_n(x) - 1$ correspond to roots of unity which fall into conjugate pairs with the same real part. One might therefore suspect that all remaining roots of $T_n(x) - 1$ are double roots. In fact, \[T_{2n+1}(x) - 1= (x - 1)(W_n(x))^2\] and \[T_{2n+2}(x) - 1 = 2(x - 1)(x + 1)(U_n(x))^2\] for polynomials $W_n(x)$ and $U_n(x)$ satisfying the same recurrence relation as $T_n(x)$, but with the different base cases $W_1(x) = 2x + 1$ and $U_1(x) = 2x$. The polynomials $U_n(x)$ are known as Chebyshev polynomials of the second kind.

Rational roots

The rational roots of $T_n(x) - 1$ for any $n$ must be elements of the set $S = \{ -1, -\frac{1}{2}, 0, \frac{1}{2}, 1 \}$. This can be proven as follows.

Any root other than $1$ of $T_{2n+1}(x) - 1$ must be a root of $W_n(x)$. The polynomials $w_n(x) = W_n \left( \frac{x}{2} \right)$ satisfy the recursive formula \begin{align*} w_0(x) &= 1 \\ w_1(x) &= x + 1 \\ w_{n+1}(x) &= xw_n(x) - w_{n-1}(x), \end{align*} ensuring that they have integer coefficients and are monic for all $n$. Furthermore, their constant terms satisfy \[w_{n+1}(0) = -w_{n-1}(0),\] and so are always either $-1$ or $1$. Thus, by the Rational Root Theorem, any rational roots of $w_n(x)$ must be $-1$ or $1$, so the only possible rational roots of $W_n(x)$ are $-\frac{1}{2}$ and $\frac{1}{2}$. Thus, the only possible rational roots of $T_{2n+1}(x) - 1$ are $-\frac{1}{2}$, $\frac{1}{2}$, and $1$, each an element of $S$.

By the composition identity, $T_{2n}(x) - 1 = T_{n}(T_{2}(x)) - 1$. If $x$ is rational, then $T_2(x) = 2x^2 - 1$ is rational also. Therefore, if all rational roots of $T_n(x) - 1$ lie in $S$, then any rational root of $T_{2n}(x) - 1$ must be a solution of $2x^2 - 1 = s$ for some $s \in S$. The following five cases show that the rational roots of $T_{2n}(x) - 1$ must lie in $S$ as well: \begin{align*} 2x^2 - 1 = -1 &\Longrightarrow x = 0, \\ 2x^2 - 1 = -\frac{1}{2} &\Longrightarrow x = \pm \frac{1}{2}, \\ 2x^2 - 1 = 0 &\Longrightarrow x = \pm \frac{\sqrt 2}{2}, \\ 2x^2 - 1 = \frac{1}{2} &\Longrightarrow x = \pm \frac{\sqrt 3}{2}, \\ 2x^2 - 1 = 1 &\Longrightarrow x = \pm 1. \end{align*}

Because any value $\cos \frac{a\pi}{b}$ for integer $a$ and positive integer $b$ is a root of $T_{2b}(x) - 1$, the five elements of $S$ are the only rational values of the cosine of a rational multiple of $\pi$. This result is known as Niven's Theorem.

Constructible roots

The $n$th roots of unity form a regular polygon with $n$ sides and circumradius $1$ in the complex plane. Therefore, such a polygon can be constructed if and only if the position of some primitive $n$th root of unity can be constructed. The root of unity in turn can be constructed if and only if its real part is a constructible number.

Just as primitive roots of unity are roots of $x^n - 1$ but not of $x^d - 1$ for any $d < n$, the roots of $T_n(x) - 1$ that are the real parts of primitive roots of unity are roots of $T_n(x) - 1$ but not of $T_d(x) - 1$ for any $d < n$. Therefore, a regular $n$-gon can be constructed if and only if $T_n(x) - 1$ has a real root that is a constructible number and not a root of $T_d(x) - 1$ for any $d < n$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Chebyshev_polynomials_of_the_first_kind&oldid=194812"