Polynomials From Pascal's Triangle

```There are many interesting things about polynomials whose coefficients
are taken from slices of Pascal's triangle.  (These are a form of
what's called Chebyshev polynomials.)  For example, the numbers
1,9,28,35,15,1 are taken from the 11th diagonal of Pascal's triangle
as shown below:

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1/
1  6 15 20 15/
1  7 21 35/
1  8 28/
1  9/
1/

The polynomial with these coefficients is

x^5 + 9x^4 + 28x^3 + 35x^2 + 15x + 1  =  0

which has five roots given by

/ k pi \
x  =  -4 cos^2 |  ----  |      k=1,2,3,4,5
\  11  /

These same roots can also be expressed in terms of radicals, i.e.,
if Q denotes any 11th root of 1, then

(1 + Q)^2
x = - -----------
Q

To find the roots corresponding to the nth diagonal, simply replace
11 by n in the above formulas.

There's an interesting connection between these "diagonal polynomials"
and a special class of functions called Mobius transformations.  These
functions (also known as linear fractional transformations) have the
general form
ax + b
f(x) =  --------
cx + d

where a,b,c,d are constants.  If you iterate functions of this form
you find that some of them lead to periodic cycles.  For example, one
of the simplest Mobius transformations is f(x)=1/x, which we get by
setting a=d=0 and b=c=1.  Iterating this function obviously gives
a repeating cycle with a period of 2.

A slightly less obvious example is the function

1 + x
f(x)  =  --------
1 - x

Beginning with, say, x=2, you can repeatedly iterate on this function
to generate the sequence of values

2, -3, -1/2, 1/3, 2, -3, -1/2, 1/3, 2, ...

Thus, iterating this function gives a repeating cycle with a period
of 4.  If you play around with these for a while you can come up with
simple functions that have other periods.  However, most Mobius
functions do not give repeating cycles.  For example, the function

2 + x
f(x)  =  --------
2 - x

never repeates, the iterates just meander around in a seemingly
aimless way.  (It actually isn't aimless; the density of the
iterates on the real line approaches a Cauchy distribution, and
you can compute the value of pi from these iterates...but that's
another story.)

So the question is, which Mobius transformations give repeating
cycles of iterates?  Also, can we find functions whose iterates
repeat with any desired period?  It turns out that the iterates of
a Mobius transformation (az+b)/(cz+d) repeat with period N if and
only if the quantity
(a+d)^2
-------

equals one of the roots of the Nth "diagonal polynomial" from
Pascal's triangle.

Another interesting thing about "diagonal polynomials" is the way
they can be factored.  Let P_N[x] denote the Nth diagonal polynomial.
In general, if N = mn, then P_N[x] is divisible by P_n[x] and P_m[x].
On the other hand, if N is a prime, then P_N[x] is irreducible, i.e.,
it can't be factored.  However, if N is a prime, it IS possible to
factor the polynomial P_N[-x^2], which is the polynomial formed by
substituting -x^2 in place of x.  For example, the quintic polynomial
corresponding to the 11th diagonal becomes

x^10 - 9x^8 + 28x^6 - 35x^4 + 15x^2 - 1

= (x^5 - x^4 - 4x^3 + 3x^2 + 3x - 1)(x^5 + x^4 - 4x^3 - 3x^2 + 3x + 1)

=  (x^5 - 4x^3 + 3x)^2   -   (x^4 - 3x^2 + 1)^2

It shouldn't be surprising that this factors, remembering that the
roots of P_N[x] are -4cos^2(k pi/N), from which it follows that the
roots of P_N[-x^2] are just 2cos(k pi/N).

if we construct a polynomial whose coefficients are all the numbers
on the Nth horizontal row of Pascal's triangle, then the roots are
all -1's, because the polynomial is just (1+x)^N.  However, if
you take every OTHER number from a horizontal row, you get an
interesting result.  For example, the 7th row is

1   7  21  35  35  21  7  1

and if you take every other number from this row you have the cubic

f(x)  =  x^3 + 21x^2 + 35x + 7

The three roots of this polynomial are

x  =  -tan^2(k pi/7)          k = 1,2,3

tan^2(u) = 1/tan^2(pi/2 - u)

the roots of the two complementary polynomials from the 7th
"horizontal" row can be summarized as

/ k=1,3,5  for  7x^3 + 35x^2 + 21x + 1
-tan^2(k pi/14)    (
\ k=2,4,6  for   x^3 + 21x^2 + 35x + 7

Notice that we have 2N instead of N in the denominator.  This also
works nicely for even numbered rows.  For example, the 8th row of
Pascal's triangle is

1   8  28  56  70  56  28  8  1

and the roots of the two complementary polynomials from this row
are given by

/ k=1,3,5,7  for  x^4 + 28x^3 + 70x^2 + 28x + 1
-tan^2(k pi/16)   (
\ k=2,4,6   for  8x^3 + 56x^2 + 56x + 8

You can also define other arrays of integers, similar to Pascal's
triangle, and determine the roots of the corresponding diagonal
and horizontal polynomials.  It generally turns out that these
roots determine the values of some parameter for which a Mobius
transformation is periodic.
```