Powers X^n are naturally associated with circles in the complex plane (contours on which |X^n| is constant). Chebyshev polynomials, are naturally associated with the ellipses with foci at +1 and -1. Chebyshev polynomials actually are powers -- in the sense that define the 2x2 matrix [2X, 1] [-1, 0] call it M, and then ( Chebyshev[n](X), Chebyshev[n-1](X) ) = V M^n where V is the row vector (1,x). [This is just the recurrence relation, rewritten.] This fact allows one to view cheb series as power series, find continued fractions (of matrices) that are good approximants over the real interval [-1,1] in the Chebyshev sense, etc. (Which I discovered about 30 years ago...) Cheb series as power series in a different way: use the eigendecomposition of that matrix to see 2*Chebyshev[n](X) = (X-sqrt(X^2-1))^n + (X+sqrt(X^2-1))^n the ellipses I was speaking of are |Z+sqrt(Z^2-1)|=const in the complex Z-plane, halfplane Re(Z)>0 anyhow. Try typing Modulus[ x+I*y+Sqrt[(x+I*y)^2-1] ] contour plot x=0..10, y=-10..10 into http://www.wolframalpha.com . So perhaps these facts give you some insight about why/how/when Chebyshev polynomials, as well as powers X^n, can be permutation polynomials if we work within finite fields. The fact the nonzeros in finite fields form a cyclic multiplicative group explains why X^n is a perm-poly if GCD(n, q-1)=1 where q=cardinality of field. It just, with respect to the cycle of powers of the generator, multiplies the discrete log by n modulo q-1. In the complex plane, R^(1-n)*Z^n as a map, maps the circle |Z|=R to itself but wound round n times not once. I claim Chebyshev[n](Z) as a map, must do the same thing about those ellipses, it just winds them n times, if scaled right. Any finite field either contains I=sqrt(-1) or not -- for example GF(5) has 2^2=-1, but GF(3) has no I. If there is no I, we can consider those "ellipses" in the "complex plane" as subsets of 2-tuples of finite field elements. Also, one can regard them just as elements of the extension field got by extending our field by adjoining I. If there is I, then the finite field "already is the complex plane" without need to take 2-tuples. Anyhow, presumably the reason Chebyshev[n] can be a perm-poly is that it walks finite field elements, or extension field elements, round ellipses. Provided all the ellipses have cardinalities coprime to n, you get a permuting effect. Now, see https://en.wikipedia.org/wiki/Dickson_polynomial#Permutation_polynomials_and... where it appears that Chebyshev polynomials and linear polynomials (and view powers as a degenerate case of chebyshev) are essentially the only useful thing there is, in the land of perm-polys. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)