mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2017-07-07, 12:44   #1
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·857 Posts
Default The Fibonacci-Chebyshev connection

Sounds like a lurid headline: "Investigators probe Fibonacci-Chebyshev connection!" Fibonacci (Leonardo of Pisa, or Leonardo Pisano Fibonacci, 1170-1250) is famous for his mathematical work, which predated the printing press. The sequence named for him arose from a question he posed with regard to the reproduction of rabbits.

Pafnuty Lvovich Chebyshev, May 4 [May 16, New Style], 1821, Okatovo, Russia — November 26 [December 8], 1894, St. Petersburg, was a Russian mathematician, known for his work on the distribution of prime numbers, and also in real analysis.

Obviously, the two men never met. They worked in different areas of mathematics. And yet, there is a connection between things named for them. On the one hand, we have the Fibonacci numbers. We can generalize these as follows: If a and b are integers, the quadratic polynomial

x^2 - a*x + b

gives rise to two integer sequences

(*F) Fn: F0 = 0, F1 = 1, Fn+2 = a*Fn+1 - b*Fn

(*L) Ln: L0 = 2, L1 = a, Ln+2 = a*Ln+1 - b*Ln

If the quadratic factors as (x - r)*(x - r') we may write these as

(**) Fn = (r^n - r'^n)/(r - r'). and Ln = r^n + r'^n.

These sequences are generalizations of the Fibonacci and Lucas numbers; they are polynomials in a and b.

Where's the connection to Chebyshev? Well, once upon a time, long long ago, I was thinking about "reciprocal polynomials" F(z), for which

F(z) = z^n*F(1/z), where n is the degree of F(z).

It is easy to see that, if n is odd, then F(-1) = 0; so, with irreducibility in mind, we assume that n is even, n = 2*k. Clearly the lead coefficient is 1. The quadratic case is

F(z) = z^2 - a*z + 1, which is irreducible for integers a other than 2 or -2.

Anyway, it seemed clear to me (as I'm sure has been known for centuries) that

F(z)/z^k

can be expressed as a polynomial in X = z + 1/z. All that is needed is to express z^n + 1/z^n as a polynomial in z + 1/z,

z^n + 1/z^n = Tn(z + 1/z) = Tn(X)

That this is possible is easily shown by induction, using T0(X) = 2, T1(X) = X, and

(z^n + 1/z^n)*(z + 1/z) = z^(n+1) + 1/z^(n+1) + z^(n-1) + 1/z^(n-1), or

Tn+1(X) = X*Tn(X) - Tn-1(X). We have

T0(X) = 2, T1(X) = X, T2(X) = X^2 - 2, T3(X) = X^3 - 3*X, etc

This is a sequence of monic polynomials with integer coefficients. Now, I was sure that these polynomials had been well known for a long time, but how? Then, it suddenly occurred to me: If you take

z = exp(i*t), z + 1/z = 2*cos(t) and z^n + 1/z^n = 2*cos(n*t). That is,

Tn(2*cos(t)) = 2*cos(n*t).

In other words, the Tn(X) are (up to a change of scale and a constant multiplier) "Chebyshev polynomials of the first kind." They give the sequence Ln for the quadratic x^2 - X*x + 1. The sequence Fn obviously gives the polynomials in X = z + 1/z for

(z^n - 1/z^n)/(z - 1/z),

which with z = exp(i*t) becomes sin(n*t)/sin(t). Thus, for the quadratic x^2 - X*x + 1, the sequence Fn expresses sin(n*t)/sin(t) as polynomials in 2*cos(t). These are also monic with integer coefficients. They are (up to a change of scale and a constant multiplier) the "Chebyshev polynomials of the second kind." We have

F0(X) = 0, F1(X) = 1, F2(X) = X, F3(X) = X^2 - 1, etc.

Now, what happens if the constant term 1 is replaced by another constant b? As (*F) and (*L) show, we obtain a sequence of polynomials in two variables. One also has r' = b/r in (**), and we can write

r + r' = sqrt(b)*(r/sqrt(b) + sqrt(b)/r).

The (perhaps) most curious case is b = -1. In this case, the effect is simply to change the (rescaled) Chebyshev polynomials Tn and Fn by making all the coefficients positive. These (particularly the transformed Fn) are called the "Fibonacci polynomials," giving the formulas in (*L) and (*F) with b = -1 for x^2 - a*x - 1.

Notes:

The (rescaled) Chebyshev polynomials above allow very simple proofs by induction, that cos(n*t) is a polynomial with rational coefficients in cos(t), and that sin(n*t) is sin(t) times a polynomial in cos(t).

The coefficients of the (rescaled) Chebyshev polynomials may easily be found using the well known power series method on the second-order differential equation satisfied by the cosine, to develop a recursion relation.

The formulas (*) give (perhaps) interesting composition formulas. Let n = a*b. Then

Tn(X) = Ta(Tb(X)), and Fn(X) = Fa(X*Fb(X))*Fb(X).

Last fiddled with by Dr Sardonicus on 2017-07-07 at 12:48
Dr Sardonicus is offline   Reply With Quote
Old 2017-07-07, 14:06   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

175910 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
...Clearly the lead coefficient is 1...
I'm not sure I follow you there...
Nick is offline   Reply With Quote
Old 2017-07-08, 01:39   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10100000101102 Posts
Default

Quote:
Originally Posted by Nick View Post
(Originally Posted by Dr Sardonicus)
Quote:
...Clearly the lead coefficient is 1...
I'm not sure I follow you there...
That's because I didn't state my hypotheses clearly


It's clearly true if the reciprocal polynomial F(z) is irreducible in Q[x] and has degree greater than 1. In this case, the zeroes occur in reciprocal pairs, so the constant term is 1. The lead coefficient is therefore also 1.
Dr Sardonicus is offline   Reply With Quote
Old 2017-07-08, 13:04   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·3·857 Posts
Default

Quote:
Originally Posted by Nick View Post
Originally Posted by Dr Sardonicus
Quote:
...Clearly the lead coefficient is 1...
I'm not sure I follow you there...
[After a decent amount of sleep]

Fascinating, how I messed that up. I didn't even mean to post that last response. I must have hit "Submit reply" by mistake...

What is clear about a reciprocal polynomial, is that the lead coefficient is equal to the constant term. [The coefficients of any two terms of complementary degree are always equal.]

Beyond that... well, the zero polynomial is a reciprocal polynomial, and there's no way to make its lead coefficient equal to 1. So, you have to assume F(z) is not the zero polynomial. Given that, you can, of course, always assume it's monic, since it will have a non-zero lead coefficient, and you can just divide by it. And then, F(z) has lead coefficient and constant term both equal to 1.

But that's not really what I had in mind. I'm only interested here in monic polynomials with integer coefficients. And there's no way around having to assume that F(z) is monic with integer coefficients -- after all, e.g. z^2 - (5/2)*z + 1 is a reciprocal polynomial.

Last fiddled with by Dr Sardonicus on 2017-07-08 at 13:07
Dr Sardonicus is offline   Reply With Quote
Old 2017-07-09, 10:59   #5
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

6DF16 Posts
Default

It's a nice tale!
Perhaps it would be a good idea to consider the link to the fundamental theorem of symmetric polynomials.
Nick is offline   Reply With Quote
Old 2017-07-09, 13:18   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×857 Posts
Default

Quote:
Originally Posted by Nick View Post
It's a nice tale!
Thanks for the kind words!
Quote:
Perhaps it would be a good idea to consider the link to the fundamental theorem of symmetric polynomials.
Hmm. The expressions (**) in the OP clearly are symmetric in r and r', so by that theorem, are expressible as polynomials in the coefficients (which, for a monic polynomial F(z)) are, up to sign, the elementary symmetric polynomials in the roots of F(z) = 0. (If F(z) isn't monic, you have to divide by the lead coefficient to get the elementary symmetric polynomials.)

The expression for Ln obviously generalizes to polynomials of any degree; the sum of the nth powers of the roots of a monic polynomial in Z[x] forms a sequence of integers with interesting divisibility properties; perhaps the best known case with degree greater than 2 is Perrin's sequence for x3 - x - 1.

The sum of the nth powers of the roots is the subject of Newton's identities, which I invite the interested reader to look up.

Last fiddled with by Dr Sardonicus on 2017-07-09 at 13:18
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Requestion for fast chebyshev theta function danaj Computer Science & Computational Number Theory 9 2018-03-31 14:59
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Chebyshev's Estimates brownkenny Math 2 2009-01-22 17:21
connection failed musos Information & Answers 1 2008-12-12 14:29
Fibonacci modulo Fibonacci robert44444uk Math 3 2007-05-19 07:15

All times are UTC. The time now is 07:07.


Tue Dec 7 07:07:22 UTC 2021 up 137 days, 1:36, 0 users, load averages: 1.50, 1.45, 1.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.