adamant's blog

By adamant, history, 22 months ago, In English

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)$$$ to find $$$f(x+a)$$$, there you have to calculate


to find a 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 a linear operators in the space of formal power series such that $$$[x^k] = \frac{x^k}{k!}$$$ and $$$\{x^k\} = k! x^k$$$.

The transforms $$$[\cdot]$$$ and $$$\{\cdot \}$$$ are called the Borel transform and the Laplace transform correspondingly.

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,

$$$f(x+a) = e^{aD} f(x) = [e^{ax^{-1}}\{f(x)\}],$$$

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)\}$$$ as formal power series. More generally, for arbitrary formal power series $$$g(D)$$$, it holds that

$$$g(D) f(x) = [g(x^{-1})\{f(x)\}],$$$

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.


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:

$$$\begin{gather} F(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_k x^k + \dots\\ G(x) = a_0 + a_1 x + a_2 \frac{x^2}{2} + \dots + a_k \frac{x^k}{k!} + \dots \end{gather}$$$

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,

$$$\begin{gather} D F = a_1 + 2 a_2 x + \dots + k a_k x^{k-1} + \dots\\ D G = a_1 + a_2 x + a_3 \frac{x^2}{2} + \dots + a_{k} \frac{x^{k-1}}{(k-1)!} + \dots \end{gather}$$$

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

$$$(x+a)^k = \sum\limits_{i=0}^k \binom{k}{i} a^i x^{k-i} = k!\sum\limits_{i=0}^k \frac{a^i}{i!}\frac{x^{k-i}}{(k-i)!},$$$

or in a symmetric form

$$$\frac{(x+a)^k}{k!} = \sum\limits_{i+j=k} \frac{a^i}{i!} \frac{x^j}{j!}.$$$

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

$$$\frac{(x+a)^k}{k!} = \sum\limits_{i=0}^{k} \frac{a^i}{i!} \left(D^i \frac{x^k}{k!}\right) =\left(\sum\limits_{i=0}^{\infty} \frac{a^i D^i}{i!} \right) \frac{x^k}{k!} = e^{aD} \frac{x^k}{k!}.$$$

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

$$$e^{aD} = \sum\limits_{i=0}^\infty \frac{(aD)^i}{i!}.$$$

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$$$.


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

$$$D^i[x^j] = \frac{x^{j-i}}{(j-i)!} = [x^{j-i}],$$$

which can be written generically as

$$$D^i [f(x)] = [x^{-i}f(x)]$$$

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

$$$g(D)[f(x)] = [g(x^{-1})f(x)]$$$

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

$$$g(D) f(x) = g(D) [\{f(x)\}] = [g(x^{-1})\{f(x)\}].$$$

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

$$$f(x+a) = e^{aD}f(x) = [e^{ax^{-1}}\{f(x)\}],$$$

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.

  • Vote: I like it
  • +136
  • Vote: I do not like it

22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Thanks for the shout-out. I'd like to emphasize that this Taylor shift operation is a one-parameter continuous symmetry, so the $$$e^{a\mathrm{D}}$$$ formula is equivalent to the statement that the derivative operator $$$\mathrm{D}$$$ is the infinitesimal generator of that symmetry, which makes great intuitive sense even without any coefficient manipulation.

  • »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I have no idea what infinitesimal generator of the symmetry is :(

  • »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    A fellow physicist explained the following idea behind $$$e^{aD}$$$ to me:

    We want to find an operator $$$T_a$$$ such that $$$T_a f(x) = f(x+a)$$$. We can perceive this operator as the limit

    $$$T_a = \lim\limits_{n \to \infty} T_{a/n}^n.$$$

    On the other hand, for an infinitesimal $$$a$$$, it holds that $$$f(x+a) = f(x) + af'(x) + O(a^2)$$$, thus

    $$$T_a = \lim\limits_{n \to \infty} (1+\frac{aD}{n})^n = e^{aD},$$$

    per the limit definition of the exponential function.

    Another meaningful observation is that

    $$$\frac{d}{da}f(x+a) = \frac{d}{dx} f(x+a) = Df(x+a).$$$

    Generally, $$$\frac{d}{dx} f(x) = kf(x)$$$ has a solution

    $$$f(x) = e^{kx}f(0).$$$

    Applying it to $$$\frac{d}{da} f(x, a) = D f(x, a)$$$, we obtain

    $$$f(x, a) = e^{aD}f(x, 0)$$$

    for a pretty much arbitrary function $$$f(x, a)$$$ and a number or even an operator $$$D$$$, if it doesn't depend on $$$a$$$...

    As I understand, it is somewhat related to what you refer to?

    • »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, that's one way of getting at exactly what I'm referring to. (And the second meaningful observation you added with your edit is very close how I described this idea in this comment.) See also, for example, 1, 2, 3, in addition to the first of the two links in my last comment.

      Unfortunately, there isn't that much to say about continuous symmetries before the scary abstractions and scarier calculations start to appear. So, even the ideas (like this one) that don't require much of that abstraction aren't that widely known.

  • »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It just came to my attention that another, much simpler way to look at it is just

    $$$ \left[\frac{z^k}{k!}\right] e^{zD} f(x) =D^k f(x) = \left[\frac{z^k}{k!}\right]f(x+z) $$$

    Left-hand identity is the series definition of exponent, right-hand identity is the Taylor expansion at $$$x$$$ for $$$z \to 0$$$.

22 months ago, # |
  Vote: I like it +99 Vote: I do not like it

Now i understand what the post is about.

While $$$D = \dfrac{d}{dx}$$$, you can simplify it by cancelling $$$d$$$ to get $$$D = \dfrac{1}{x}$$$, right?

22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a feeling that the trick (is it a trick?) is somehow related to Umbral Calculus. However, I don't know much about the topic so I am not that certain.

  • »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hm, now that you mentioned it, the way to compute the $$$m$$$-th term of the linear recurrence resembles the umbral calculus to me. Like, you have a recurrence

    $$$F_m = \sum\limits_{k=1}^n F_{m-k} a_k,$$$

    to solve it you substitute $$$F_m = b^m$$$, treating $$$b$$$ as umbra, so it's now

    $$$b^n = \sum\limits_{k=1}^n b^{n-k} a_k.$$$

    With this relationship, one can derive $$$b^m$$$ as a linear combination of $$$b^0, b^1, \dots, b^{n-1}$$$ and then change umbra back to $$$F_m$$$ and $$$F_0, F_1, \dots, F_{n-1}$$$ and it "magically" works.

    AFAIK, the most common explanation is to analyze the linear functional $$$T : \mathbb R[b] \to \mathbb R$$$ defined as

    $$$T(b^m) = F_m.$$$

    According to the Wikipedia article, linear functional studies are the core of umbral calculus, so it should be the bridge between it and linear recurrences. As I also pointed in comments, the explicit formula for the functional is

    $$$T(p) = [b^0] p(b) g(b^{-1}),$$$

    where $$$g(x)=F_0 + F_1 x + F_2 x^2 + \dots$$$ is the generating function of $$$F_0, F_1, \dots$$$, so it might be possible to find out some functional to analyze for Taylor shifts as well, given that we have $$$g(x^{-1})$$$ appearing in the formulas here too...