Difference between revisions of "Chebyshev polynomials of the first kind"
(→Connection to roots of unity) |
m |
||
(7 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> | + | 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, | + | 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 | + | 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, < | + | 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, < | + | 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> | ||
Line 57: | Line 56: | ||
===Rational roots=== | ===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. | |
− | |||
− | Because any value <math>\cos {a\pi}{b}</math> for | + | 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 15:24, 26 June 2023
The Chebyshev polynomials of the first kind are defined recursively by or equivalently by
Contents
Proof of equivalence of the two definitions
In the proof below, will refer to the recursive definition. Let
, so that
.
For the base case,
for the
base case,
Now for the inductive step, we assume that and
, and we wish to prove that
.
From the cosine sum and difference identities we have The sum of these equations is
rearranging,
Substituting our assumptions yields
as desired.
Composition identity
For nonnegative integers and
, the identity
holds.
First proof
By the trigonometric definition, .
As before, let . We have
for some integer
. Multiplying by
and distributing gives
; taking the cosine gives
.
For now this proof only applies where the trigonometric definition is defined; that is, for . However,
is a degree-
polynomial, and so is
, so the fact that
for some
distinct
is sufficient to guarantee that the two polynomials are equal over all real numbers.
Second proof (Induction)
First we prove a lemma: that for all
. To prove this lemma, we fix
and induct on
.
For all , we have
and for all
,
proving the lemma for
and
respectively.
Suppose the lemma holds for and
; that is,
Then multiplying the first equation by
and subtracting the second equation gives
which simplifies to
using the original recursive definition, as long as
. Thus, the lemma holds for
(as long as
), completing the inductive step.
To prove the claim, we now fix and induct on
.
For all , we have
and
proving the claim for
and
respectively.
Suppose the claim holds for and
; that is,
We may also assume
, since the smaller cases have already been proven, in order to ensure that
. Then by the lemma (with
) and the original recursive definition,
completing the inductive step.
Roots
Since , and the values of
for which
are
for integers
, the roots of
are of the form
These roots are also called Chebyshev nodes.
Connection to roots of unity
Because cosine is only at integer multiples of
, the roots of the polynomial
follow the simpler formula
. The
th roots of unity have arguments of
and magnitude
, so the roots of
are the real parts of the
th roots of unity. This lends intuition to several patterns.
All roots of are also roots of
, since all
th roots of unity are also
th roots of unity. This can also be shown algebraically as follows: Suppose
. Then
using the composition identity and the fact that
for all
.
Particular cases include that , being a root of
, is a root of
for all positive
, and
, being a root of
, is a root of
for all positive even
. All other roots of
correspond to roots of unity which fall into conjugate pairs with the same real part. One might therefore suspect that all remaining roots of
are double roots. In fact,
and
for polynomials
and
satisfying the same recurrence relation as
, but with the different base cases
and
. The polynomials
are known as Chebyshev polynomials of the second kind.
Rational roots
The rational roots of for any
must be elements of the set
. This can be proven as follows.
Any root other than of
must be a root of
. The polynomials
satisfy the recursive formula
ensuring that they have integer coefficients and are monic for all
. Furthermore, their constant terms satisfy
and so are always either
or
. Thus, by the Rational Root Theorem, any rational roots of
must be
or
, so the only possible rational roots of
are
and
. Thus, the only possible rational roots of
are
,
, and
, each an element of
.
By the composition identity, . If
is rational, then
is rational also. Therefore, if all rational roots of
lie in
, then any rational root of
must be a solution of
for some
. The following five cases show that the rational roots of
must lie in
as well:
Because any value for integer
and positive integer
is a root of
, the five elements of
are the only rational values of the cosine of a rational multiple of
. This result is known as Niven's Theorem.
Constructible roots
The th roots of unity form a regular polygon with
sides and circumradius
in the complex plane. Therefore, such a polygon can be constructed if and only if the position of some primitive
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 but not of
for any
, the roots of
that are the real parts of primitive roots of unity are roots of
but not of
for any
. Therefore, a regular
-gon can be constructed if and only if
has a real root that is a constructible number and not a root of
for any
.