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.

From Antti Karttunen, Jul 29 2015: (Start)

The square array A(row,col) is read by downwards antidiagonals as: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.

A(n,m) (entry at row=n, column=m) gives the evaluation at x=n of the polynomial (with nonnegative integer coefficients) bijectively encoded in the prime factorization of m. See A206284, A206296 for the details of that encoding. (The roles of variables n and m were accidentally swapped in this description, corrected by Antti Karttunen, Oct 30 2016)

(End)

Each row is a completely additive sequence, row n mapping prime(m) to n^(m-1). - Peter Munn, Apr 22 2022

a(n) = Coefficient of x in the reduction under x^2->x+1 of the polynomial encoded in the prime factorization of n. (Assuming here only polynomials with nonnegative integer coefficients, see e.g. A206296 for the details).

Completely additive with a(prime(k)) = F(k-1), where F(k) denotes the k-th Fibonacci number, A000045(k). - Peter Munn, Mar 29 2021, incorporating comment by Antti Karttunen, Dec 15 2015

In terms of integers: apply A265398 as many times as necessary to n, until it gets 3-smooth, one of the terms of A003586.

Completely multiplicative with a(2) = 2, a(3) = 3, a(p) = a(A265398(p)) for p > 3. - Andrew Howroyd & Antti Karttunen, Aug 04 2018

The polynomials encoded by these numbers could also be called "Fernandez spiral polynomials" after Neil Fernandez, who discovered sequence A078510, which is obtained when they are evaluated at X=1.

The polynomial recurrence uses the same composition rules as the Fibonacci polynomials (A206296), but with the neighborhood rules of A078510, where the other polynomial is taken from the nearest inner neighbor (A265409) when the polynomials are arranged as a spiral into a square grid. See A265409 for the illustration.

Old definition was: constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined recursively by p(n,x) = x*p(n-1,x) + 4n+2 for n>0, with p(0,x)=1.

For discussions of polynomial reduction, see A192232 and A192744.

Old definition was: coefficient of x in the reduction under x^2->x+1 of the polynomial p(n,x) defined recursively by p(n,x) = x*p(n-1,x) + 4n+2 for n>0, with p(0,x)=1.

For discussions of polynomial reduction, see A192232 and A192744.