Hi everyone!

Today I'd like to write another blog about polynomials. Consider the following problem:

You're given $$$P(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}$$$, you need to compute $$$P(x+a) = b_0 + b_1 x + \dots + b_{n-1} x^{n-1}$$$.

There is a well-known solution to this, which involves some direct manipulation with coefficients. However, I usually prefer approach that is more similar to synthetic geometry when instead of low-level coordinate work, we work on a higher level of abstraction. Of course, we can't get rid of direct coefficient manipulation completely, as we still need to do e.g. polynomial multiplications.

But we can restrict direct manipulation with coefficients to some minimal number of black-boxed operations and then strive to only use these operations in our work. With this goal in mind, we will develop an appropriate framework for it.

Thanks to clyring for inspiring me to write about it with this comment. You can check it for another nice application of calculating $$$g(D) f(x)$$$ for a specific series $$$g(D)$$$ over the differentiation operator:

While this article mostly works with $$$e^{aD} f(x)$$$, there you have to calculate

to find polynomial $$$f(x)$$$ such that $$$f(x) = p(0)+p(1)+\dots+p(x)$$$ for a given polynomial $$$p(x)$$$.

Key results

Let $$$[\cdot]$$$ and $$$\{ \cdot \}$$$ be linear operators in the space of formal power series such that $$$[x^k] = \frac{x^k}{k!}$$$ and $$$\{x^k\} = k! x^k$$$.

As we also work with negative coefficients here, we define $$$\frac{1}{k!}=0$$$ for $$$k < 0$$$, hence $$$[x^k]=0$$$ for such $$$k$$$.

In this notion,

where $$$D=\frac{d}{d x}$$$ is the differentiation operator. Thus, $$$\{f(x+a)\}$$$ is a part with non-negative coefficients of the cross-correlation of $$$e^{ax}$$$ and $$$\{f(x)\}$$$. More generally, for arbitrary formal power series $$$g(D)$$$, it holds that

that is $$$\{g(D) f(x)\}$$$ is exactly the non-negative part of the cross-correlation of $$$g(x)$$$ and $$$\{f(x)\}$$$.

Detailed explanation is below.

OGF and EGF

Let $$$a_0, a_1, \dots$$$ be a sequence of numbers. In analytic combinatorics, there are two ways to represent it with a generating function:

Functions $$$F$$$ and $$$G$$$ are called ordinary generating function and exponential generating function correspondingly.

Example. OGF for the sequence $$$1,1,\dots$$$ is $$$1+x+x^2+\dots = \frac{1}{1-x}$$$, while its EGF is $$$1+x+\frac{x^2}{2!}+\dots = e^x$$$.

Differentiation operator

The differentiation operator $$$D = \frac{d}{dx}$$$ is formally defined as a linear operator such that $$$D x^k = k x^{k-1}$$$. In other words,

Thus, if looked through underlying sequence perspective, $$$D$$$ on EGF corresponds to a simple shift of $$$a_0, a_1, \dots$$$.

Operator exponent

Returning to our original problem, a single power of $$$x+a$$$ is given as

or in a symmetric form

Knowing that $$$\frac{d}{dx}\frac{x^k}{k!} = \frac{x^{k-1}}{(k-1)!}$$$, we may rewrite it as

Here $$$e^{aD}$$$ is an exponent of operator $$$D$$$, formally defined as

When $$$a$$$ is constant, $$$a$$$ and $$$D$$$ commute, thus $$$(aD)^i = a^i D^i$$$. It also means that we can get rid of $$$k!$$$ and obtain $$$(x+a)^k = e^{aD} x^k$$$ which, in turn, generalizes to $$$e^{aD} F(x) = F(x+a)$$$ for an arbitrary formal power series $$$F$$$.

Transitions

With the definitions above in mind, let's introduce operations $$$[\cdot]$$$ and $$$\{\cdot\}$$$ such that $$$G = [F]$$$ and $$$F = \{G\}$$$. The operations can be computed for any power series by multiplying or dividing its coefficients with $$$k!$$$ correspondingly.

There are two essential observations we should make that hold for any formal power series $$$F$$$.

First of all, $$$\{[F]\} = [\{F\}] = F$$$ for any formal power series $$$F$$$.

The second important observation is

which can be written generically as

for arbitrary formal power series $$$f(x)$$$. Here we define $$$(j-i)! = \infty$$$ for $$$i > j$$$, thus $$$[x^k]$$$ is $$$0$$$ for negative $$$k$$$.

The second property, due to linearity of $$$[\cdot]$$$ is further generalized as

for the arbitrary formal power series $$$g(D)$$$. Combining it with the first property, we get

In particular, for $$$g(D)=e^{aD}$$$, we obtain

thus $$$\{f(x+a)\}$$$ is the non-negative part of the cross-correlation of $$$e^{ax}$$$ and $$$\{f(x)\}$$$.

Check your understanding

You can implement and check your solution for it on this Library Checker problem.