Generalized Chebyshev polynomials

found by Yuri MATIYASEVICH 

This HTML paper is written especially for Personal Journal of Yuri MATIYASEVICH.
The paper is updated when new results are found.
Last modified on April 7, 1998.

Generalized Chebyshev polynomials have been introduced in

G.B.Shabat and I.A.Voevodskii
Drawing curves over number fields
The Grothendieck Festschift, vol.3, Birkhäuser, 1990, pp. 199-227.
These polynomials are also known as Shabat polynomials.

In this brief introduction I reproduce only a few facts from this beatiful theory; these facts should be sufficient for understanding what I have done. More information can be found via WWW from site of J.Betrema and from thesis of Louis Granboulan. I also recommend survey paper
G.Shabat and A.Zvonkin
Plane trees and algebraic numbers
Contemporary Math., 1994, vol.178, pp.233--275.

Generalized Chebyshev polynomial (Shabat polynomials) can be defined as polynomials (in one complex variable with complex coefficients) for which there are two different complex numbers A and B (called the critical values) such that

P'(z)=0  => P(z)=A or P(z)=B 

EXAMPLE. The classical Chebyshev polynomials of the first kind
Tn(z)=cos(n arccos(z))
have critical values A=-1 and B=1.

The classical Chebyshev polynomials arose as a solution to the problem of finding a function with the least deviation from zero.
Generalized Chebyshev polynomials are of interest by different reasons.
Namely, let us look at a generalized Chebyshev polynomial P of degree n as a map from the complex plane into itself.
Let [A,B] denote the segment of a straight line with A and B as the end points.

FACT 1. The inverse image H=P-1([A,B]) is a tree (in graph-theoretical sense) with n+1 vertices at points P-1(A) and P-1(B).

The first natural question: what trees can be obtained in this way?

FACT 2. Every tree is the inverse image H=P-1([A,B]) for some generalized Chebyshev polynomial P with critical values A and B.

After such a nice answer, second question arises: how many polynomials can generate given tree?

It is easy to see that if P is a generalized Chebyshev Polynomial, then so is polynomial CP(cz+d)+D, moreover, it represents the same tree (of course, provided that both C and c are different from zero).
In some natural sense these two linear transformations exhaust the variety of polynomials representing given tree.
Namely, every drawing of a tree on the plane introduces an additional structure--circular order of edges around given vertex (say, clock-wise).
Dealing with Chebyshev polynomials, it is natural to speak about plane trees understanding by them trees with this additional structure.

FACT 3. A plane tree determines corresponding Chebyshev polynomial uniquely up to linear transformations.

Thus there is a striking natural one-to-one correspondence between plane trees and classes of linear equivalent generalized Chebyshev polynomials.

FACT 4. Among generalized Chebyshev polynomials representing given plane tree there is always a polynomial all coefficients of which are algebraic numbers.

A catalog of generalized Chebyshev polynomials for trees with small number of edges was constructed by J.Betrema.

Unfortunately, computational complexity grows quickly with the growth of the number of edges. To a great extend this is due to the growth of the smallest algebraic field containing the coefficients of the polynomial.

I wrote programs which first calculates the coefficients numerically with great precision. Then by well-known technique exact algebraic numbers can be found provided that the accuracy is large while the degree of numbers is small.

I will put on WWW trees and corresponding polynomials found by these programs.

Formats of files

Tree M23a Tree M23b
"True" picture:
.gif   .ps.gz   .dvi
[Tree M23a] [Tree M23b] "True" picture:
.gif   .ps.gz   .dvi
The polynomial:     .ascii   .gif   .ps.gz   .tex   .nb

The polynomial was found by a program written in MATHEMATICA.
These polynomial and pictures were put on WWW on March 10, 1998.

Tree M11
[Tree M11] Polynomial:   .gif   .ps.gz   .tex   .nb
"True" picture:   .gif   .ps.gz   .dvi   .tex

The polynomial was found by a program written in MAPLE.
These polynomial and picture were put on WWW on January 20, 1998.