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)$$ .