A property of Chebyshev polynomials

[T.Rex]

Hi,
I fail finding a proof (even in MathWorld, in my Mathematic dictionary or on the Web) for the following property of Chebyshev polynomials:

(T_i o T_j)(x) = (T_j o T_i)(x) = T_ij(x) when x is in ] -inf ; + inf [

Example :
T_2(x) = 2x^2-1
T_3(x) = 4x^3-3x
T_3(T_2(x)) = T_2(T_3(x)) = T_6(x)

When x is in ]-1 ; +1[ , it seems easy to use x=cosA and T_n(cosA) = cos(nA) .

But how to do when x is any real ?

Thanks,
Tony

 

[Hurkyl]

But how to do when x is any real ?

You could probably do something clever by letting A be any complex number!


Try doing it with induction.

 

[T.Rex]

Hyperbolic Cosinus ?

Huuumm,
I did not find with A being any complex number.
But I thought to use cosh (Hyperbolic Cosinus). It has the same properties than Cosinus about cos(nx). But, with x = cosh(A), we have both A in ]-inf;+inf[ and x in ]-inf;+inf[ . So it's less general than A being complex, but it answers my needs.
The proof:
We define: x=cosh(A) , T_n(x) = T_n(cosh(A)) = cosh(nA) .
So (T_i o T_j)(x) = T_i(cosh(jA)) = cosh(ijA) = (T_j o T_i)(x) = T_[ij](x) .

Now, I have another series of Polynomials that are very close to Chebyshev polynomials:
S_0(x) = 2
S_1(x) = x
S_i(x) = x.S_[i-1](x) - S_[i-2](x) (as with T_n(x) ).
So: S_2(x) = x^2 - 2 , S_3(x) = x^3 - 3x .
It seems to have the same property: S_i o S_j = S_j o S-_i = S_[ij] .
But there is now no way to connect S_n(x) with the properties of cos(nx) or of cosh(nx) ...
I just noticed that, if S_n(x) = Sum{ a_i . x^i } , then T_n(x) = Sum{ 2^(i-1) . a_i . x^i } , where i=0..n .

This series is used in order to prove certain properties of Lucas Sequences, helping to prove the famous LLT (Lucas Lehmer Test): L(0)=4 , L(i) = L(i-1)^2 - 2 , M_q=2^q-1 is prime iff M_q divides L(q-2).

Tony

 

[Hurkyl]

I did not find with A being any complex number.
But I thought to use cosh

That's essentially what I was suggesting; the neat thing about cos and cosh is that they're related via cosh x = cos ix. (And also cosh ix = cos x)


Here's another, fairly powerful trick that I wasn't able to remember when I wrote my post:

If f(x) is a polynomial, it either has a finite number of zeroes, or it is the zero polynomial.

You were able to show, using the relationship with cosines, that the polynomial (T_j o T_i)(x) - T_ij(x) = 0 for all x in the interval [-1, 1]. This implies this polynomial must be zero for all x!

I just noticed that, if S_n(x) = Sum{ a_i . x^i } , then T_n(x) = Sum{ 2^(i-1) . a_i . x^i } , where i=0..n .

So, in other words. T_n(x) = (1/2) * S_n(2x)?

 

[Integral]

It is not clear to me that if you move outside of the region [-1,1] that you are still dealing with a Chebyshev polynomial. The definition:
T_k(Cos \Theta ) = Cos k \Theta

results in properties used to prove bounds on the resulting errors. If you do not have the cosine then all bets are off on the errors of the resulting function.

The main result of the Chebyshev Polynomial is to obtian the Chebyshev points. These are the points which should be used for ANY polynomial approximation to a function. Just for interest sake the expanded Chebyshev points for and arbritray interval [a,b] are given by:

2 x_i = a + b + (a-b) \frac { Cos ( \frac {2i+1} {2n +2} \pi)} {Cos( \frac {\pi} {2n +2})}

Reference:
Elementary Numerical Analysis: An Algorithmic Approach by Conte and De Boor

 

[T.Rex]

Chebyshev polynomials for Lucas Sequences (LLT).

Thanks Hurkyl !
Yes you're right !

So, in other words. T_n(x) = \frac{1}{2} S_n(2x) ?

That works fine !
So it proves that C_n has the same properties than T_n has !
Tony

 

[T.Rex]

x in ]-inf ; + inf[ or x in ]-1 ; +1[ ??

Hi Integral,

It is not clear to me that if you move outside of the region [-1,1] that you are still dealing with a Chebyshev polynomial. The definition: T_k(Cos \Theta ) = Cos k \Theta results in properties used to prove bounds on the resulting errors. If you do not have the cosine then all bets are off on the errors of the resulting function.

Yes, this is a good question ! My mathematical dictionary also defines Cebyshev polynomials by means of x=Cos \Theta . So, can we still talk of Chebyshev polynomials when x is any real ?

My goal is to understand the relationships between the Chebyshev polynomials and the Lucas Sequences: V_n = P V_{n-1} - Q V_{n-2} . I'm reading the book of Mr H. C. Williams : "Edouard Lucas and primality testing". Page 77, Mr Williams introduces the Chebyshev polynomials (C_n and S_n, not the T_n ! ) as a tool for building properties of the Lucas Sequences (U_n and V_n). He does not say what are the values of x ...

(It appears that Chebyshev polynomials and Lucas Sequence share several properties. As an example: V_{kn} = V_n V_{(k-1)n} - Q^n V_{(k-2)n} produces relationships very close (with k=2,3,...) to the ones of Chebyshev polynomials:V_{2n}=V_n^2-2Q^n ...)

The interesting part is that C_2(x) = x^2-2 appears in the Lucas Lehmer test and that C_3(x) = x^3-3x enables to find other valid values of S_0 than 4 . (Example, C_3(4)=52\equiv -10\pmod{M_5} . And, with L_0=-10, L_3=0 proving M_5 is prime.).

Reminder: The Lucas Lehmer Test (LLT) for Mersenne numbers is:
L_0=4 , L_i = L_{i-1}^2 - 2=C_2(L_{i-1}) ; M_q=2^q-1 is prime iff L_{q-2} \equiv 0\pmod{M_q} .

My questions are: 1) why C_3 produces numbers A (like 4) such that 2+A is a quadratic non residue used as L_0 ? 2) What are the properties of C_n polynomials about Lucas Sequences when n is a prime ?

Tony

I think what I call here as C_n is what I called as S_n in the previous posts ... C_n is the name used by Mr Williams.
C_0(x) = 2 ,<br /> C_1(x) = x ,<br /> C_i(x) = x C_{i-1}(x) - C_{i-2}(x) .