cp's OEIS Frontend

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(n-1), 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)s in this manner until reaching w such that d(w)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(n-1)) in the above example. We are interested in the component sequences (e.g., F(n-1) and F(n)) for various choices of p(n,x).

Following are examples of reduction by x^2->x+1:

n-th Fibonacci p(x) -> A192232+x*A112576

n-th cyclotomic p(x) -> A192233+x*A051258

n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101

n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236

x(x+1)(x+2)...(x+n-1) -> 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 "k-sequence 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 0-sequence of (reduction of b by x^2->x+1) is (F(n-1)), and the 1-sequence is (F(n)).

...

For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):

b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields

0-sequence A166536 and 1-sequence A064831.

b=(1,A000045)=(1,1,1,2,3,5,8,...) yields

0-sequence A166516 and 1-sequence A001654.

b=A000027, natural number sequence (1,2,3,4,...) yields

0-sequence A190062 and 1-sequence A122491.

b=A000032, Lucas sequence (1,3,4,7,11,...) yields

0-sequence A192243 and 1-sequence A192068.

b=A000217, triangular sequence (1,3,6,10,...) yields

0-sequence A192244 and 1-sequence A192245.

b=A000290, squares sequence (1,4,9,16,...) yields

0-sequence A192254 and 1-sequence A192255.

More examples: A192245-A192257.

...

More comments:

(1) If s(n,x)=(reduction of x^n by q->s) and

p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then

(reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)

+...+p(n-1)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=(1-sqrt(5))/2.

Table starts

....4......10.........25...........65.............169................442

....9......48........256.........1280............6400..............32000

...25.....305.......3721........40626..........443556............4861800

...64....1800......50625......1143000........25806400..........600090240

..169...10933.....707281.....33729146......1608491236........80568542340

..441...65856....9834496....981994496.....98054154496.....10563801093680

.1156..397970..137007025..28735927165...6027088830169...1398071103483637

.3025.2402455.1908029761.839596650695.369450492999025.184549492112860840

Let p(n)=p(n,x) be the characteristic polynomial of the n-th principal submatrix. The zeros of p(n) are positive, and they interlace the zeros of p(n+1). See A202605 for a guide to related sequences.

If we omit the main diagonal of this array and ignore the signs of the entries then the resulting array, reading the rows in reverse order, appears to equal the Riordan array (1/((1 + x)*(1 - x)^3), x/(1 - x)^2), whose generating function begins 1 + (2 + t)*x + (4 + 4*t + t^2)*x^2 + (6 + 11*t + 6*t^2 + t^3)*x^3 + (9 + 24*t + 22*t^2 + 8*t^3 + t^4)*x^4 + .... - Peter Bala, Sep 17 2019

Warren Weaver (1938): "In a familiar geometrical paradox a square of area 8 X 8 = 64 square units is cut into four parts which may be refitted to form a rectangle of apparent area 5 X 13 = 65 square units.... Lewis Carroll generalized this paradox...."

Carroll cuts a F(2n+2) X F(2n+2) square into four parts, where F(n) is the n-th Fibonacci number. Two parts are right triangles with legs F(2n) and F(2n+2); two are right trapezoids three of whose sides are F(2n), F(2n+1), and F(2n+1). (Thus n > 0.) The paradox (or dissection fallacy) depends on Cassini's identity F(2n+1) * F(2n+3) = F(2n+2)^2 + 1.

For an extension of the paradox to a F(2n+1) X F(2n+1) square using Cassini's identity F(2n) * F(2n+2) = F(2n+1)^2 - 1, see Dudeney (1970), Gardner (1956), Horadam (1962), Knott (2014), Kumar (1964), and Sillke (2004). Sillke also has many additional references and links.