[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
1668.0. "Chebyshev polynomials" by DESIR::BUCHANAN (The was not found.) Thu Sep 24 1992 17:24
A neat question cropped up on the net recently.
Take the function:
h(x) = x^2 - 2
and repeatedly apply it. Can you find an elegant expression for the general
form?
--------------------------------------------------------------------------------
Try setting x = a + 1/a. Then
h(x) = a^2 +1/(a^2)
h(h(x)) = a^4 + 1/(a^4)
...
Why should this work? Someone pointed out the connection to Chebyshev
polynomials (of the first kind). This is a sequence of polynomials T(n,x)
defined by:
T(0,x) = 1
T(1,x) = x
T(n,x) = 2*x*T(n-1,x) - T(n-2,x) (n >= 2)
These are incidentally orthogonal polys, under:
/+1 f(x)*g(x)dx
<f,g> = | -----------
/-1 sqrt(1-x^2)
<T(0),T(0)> = pi
<T(n),T(n)> = pi/2 (n >= 1)
<T(n),T(m)> = 0 (n <> m)
Now h(x) = 2*T(2,x/2).
So the result we had for h translates to:
T(2,(a+1/a)/2) = (a^2+1/a^2)/2
which generalizes to:
T(n,(a+1/a)/2) = (a^n+1/a^n)/2
Now, why should *that* be so? Well, if T(1,x) = x = cos(�), then
T(n,x) = cos(n�). So a is just e^(i�). That's it.
Are there any similar games that can be played with the Chebyshev
polynomials of the second kind, I wonder? This is a related sequence of
polynomials U(n,x) defined by:
U(0,x) = 1
U(1,x) = 2*x <--- the only difference wrt T(n,x)
U(n,x) = 2*x*U(n-1,x) - U(n-2,x) (n >= 2)
These are orthogonal polys, under:
/+1
[f,g] = | sqrt(1-x^2)*f(x)*g(x)dx
/-1
[U(n),U(n)] = pi/2
[U(n),U(m)] = 0 (n <> m)
Now if x = cos(�) as before, U(n,x) = sin((n+1)�) / sin(�). Can we
find some function h', sort of analogous to h? Or not?
See MAPLE, help(orthopoly) for more information
Cheers,
Andrew.
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1668.1 | link | 53099::BUCHANAN | The was not found. | Fri Sep 25 1992 12:10 | 16 |
| The Lucas-Lehmer test for Mersenne primes (see note 2.5) is based on
the same function that .0 begins with:
x -> x^2 - 2
but over Z_q rather than Z. Again:
x = a + 1/a
where:
a = 2 � _/3
If q is a Mersenne prime, then 3 is a quadratic non-residue mod q.
Andrew.
|
| 1668.2 | ll proof | DESIR::BUCHANAN | The was not found. | Wed Sep 30 1992 11:39 | 41 |
| > The Lucas-Lehmer theorem:
>
> Let p be an odd prime, and define the sequence <u(n)>
> by the rule
> u(0) = 4
> u(n+1) = (u(n)^2 - 2) mod (2^p - 1)
>
> Then 2^p - 1 is prime if and only if u(p-2) = 0
Why does this work?
Suppose that q = 2^p - 1 is prime. Then 3 is not a quadratic residue
in Z_q, so adjoin _/3 to Z to get a finite field of order q^2. Write:
u(0) = a + 1/a (where a = 2 + _/3)
then:
u(n) = a^2^n + 1/a^2^n
What is the order of a? It's easy to see that:
a^2^p = 1. (Use a^q = 2^q + _/3^q = 2 - _/3 = a^(-1).)
x^2 = a has two solutions x = �(1+_/3)*2^((p-1)/2).
y^2 = �x has no solutions. So x has order 2^(p+1), and a has order
2^p. Hence a^2^(p-1) = -1, and u(p-2) = 0.
On the other hand, suppose that 2^p - 1 is composite, divisible by some
prime r. We can define a as before, but now we don't know whether _/3 lies
in Z, or whether is must be adjoined. But in any case, let's assume that
u(p-2) == 0 mod r, ie that a has order 2^p. The order of an element divides
the order of the group, so:
2^p | r-1 or 2^p | r^2-1
but in either case this implies:
2^(p-1) =< r+1
(Note that r^2-1 = (r+1)(r-1) and (r+1,r-1)=2.)
But r =< (2^p - 1)/3 (since 2^p - 1 is composite odd)
=> contradiction. So u(p-2) does not vanish mod r. So u(p-2) is not 0.
Andrew.
|
| 1668.3 | (3+_/5)/2 | HERON::BUCHANAN | The was not found. | Tue Nov 10 1992 07:03 | 36 |
| >Note 1692.1 American Math Monthly 10259
>RUSURE::EDP "Always mount a scratch monkey."
>
> Let <r[k]> for k in the natural numbers be defined by r[0] = 3 and
> r[k+1] = r[k]^2-2. Evaluate
>
> limit as K goes to infinity of
>
> [product from k=0 to K-1 of r[k]] ^ [1/2^K].
Let a = (3 + _/5)/2.
Then r[k] = a^2^k + 1/a^2^k.
So [product from k=0 to K-1 of r[k]]
= sum from l= -(2^K-1) to 2^K-1 of a^l
K+1
2 -1
a - 1
= -----------
K
2 -1
(a-1)*a
Now ignoring the smaller term in the numerator, and taking the rest to
the power 2^(-K), we get:
a
-----------
(a-1)^2^(-K)
As K goes to infinity, the denominator goes to unity.
Andrew.
|