Polynomial reduction: an introduction
...
We begin with an example. Suppose that p(x) is a polynomial, so that p(x)=(x^2)t(x)+r(x) for some polynomials t(x) and r(x), where r(x) has degree 0 or 1. Replace x^2 by x+1 to get (x+1)t(x)+r(x), which is (x^2)u(x)+v(x) for some u(x) and v(x), where v(x) has degree 0 or 1. Continuing in this manner results in a fixed polynomial w(x) of degree 0 or 1. If p(x)=x^n, then w(x)=x*F(n)+F(n1), where F=A000045, the sequence of Fibonacci numbers.
In order to generalize, write d(g) for the degree of an arbitrary polynomial g(x), and suppose that p, q, s are polynomials satisfying d(s)<d(q). By the division algorithm, there exists a unique pair t and r of polynomials such that p=q*t+r and d(r)<d(q). Replace q by s to get s*t+r, which is q*u+v for some u and v, where d(v)<d(q). Continue applying q>s in this manner until reaching w such that d(w)<d(q). We call w the reduction of p by q>s.
The coefficients of (reduction of p by q>s) comprise a vector of length d(q)1, so that a sequence p(n,x) of polynomials begets a sequence of vectors, such as (F(n), F(n1)) in the above example. We are interested in the component sequences (e.g., F(n1) and F(n)) for various choices of p(n,x).
Following are examples of reduction by x^2>x+1:
nth Fibonacci p(x) > A192232+x*A112576
nth cyclotomic p(x) > A192233+x*A051258
nth 1stkind Chebyshev p(x) > A192234+x*A071101
nth 2ndkind Chebyshev p(x) > A192235+x*A192236
x(x+1)(x+2)...(x+n1) > A192238+x*A192239
(x+1)^n > A001519+x*A001906
(x^2+x+1)^n > A154626+x*A087635
(x+2)^n > A020876+x*A030191
(x+3)^n > A192240+x*A099453
...
Suppose that b=(b(0), b(1),...) is a sequence, and let p(n,x)=b(0)+b(1)x+b(2)x^2+...+b(n)x^n. We define (reduction of sequence b by q>s) to be the vector given by (reduction of p(n,x) by q>s), with components in the order of powers, from 0 up to d(q)1. For k=0,1,...,d(q)1, we then have the "ksequence of (reduction of sequence b by q>s)". Continuing the example, if b is the sequence given by b(k)=1 if k=n and b(k)=0 otherwise, then the 0sequence of (reduction of b by x^2>x+1) is (F(n1)), and the 1sequence is (F(n)).
...
For selected sequences b, here are the 0sequences and 1sequences of (reduction of b by x^2>x+1):
b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields
0sequence A166536 and 1sequence A064831.
b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
0sequence A166516 and 1sequence A001654.
b=A000027, natural number sequence (1,2,3,4,...) yields
0sequence A190062 and 1sequence A122491.
b=A000032, Lucas sequence (1,3,4,7,11,...) yields
0sequence A192243 and 1sequence A192068.
b=(A000217, triangular sequence (1,3,6,10,...) yields
0sequence A192244 and 1sequence A192245.
b=(A000290, squares sequence (1,4,9,16,...) yields
0sequence A192254 and 1sequence A192255.
More examples: A192245A192257.
...
More comments:
(1) If s(n,x)=(reduction of x^n by q>s) and
p(x)=p(0)x^n+p(1)x^(n1)+...+p(n)x^0, then
(reduction of p by q>s)=p(0)s(n,x)+p(1)s(n1,x)
+...+p(n1)s(1,x)+p(n)s(0,x). See A192744.
(2) For any polynomial p(x), let P(x)=(reduction of p(x)
by q>s). Then P(r)=p(r) for each zero r of
q(x)s(x). In particular, if q(x)=x^2 and s(x)=x+1,
then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or
r=(1sqrt(5))/2.
