Generalized Chebyshev polynomials

found by Yuri MATIYASEVICH 

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.

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 

T_n(z)=cos(n arccos(z))

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.

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

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.

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

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 .tex			"True" picture: .gif   .ps.gz   .dvi .tex
The polynomial:     .ascii   .gif   .ps.gz   .tex   .nb
Comments

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

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

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