Hi everyone!

Let $$$R$$$ be a ring, $$$d_0, d_1, d_2, \dots \in R$$$ and $$$e_0, e_1, e_2, \dots \in R$$$ be linear recurrence sequences, such that

In some applications, the following two sequences arise:

Today I'd like to write about the framework that allows to prove that both the sequences defined above are also linear recurrences. It would also allow to compute their characteristic polynomials in $$$O(kl \log kl)$$$, which is optimal as their degrees are $$$O(kl)$$$ in both cases.

### Umbral calculus

Generally, a linear recurrence $$$f_k$$$ can be described and analyzed with the help of the linear functional $$$T : R[f] \mapsto R$$$ such that

For such functional, $$$T(P(f)) = 0$$$ when $$$P(f)$$$ is a multiple of the characteristic polynomial of $$$f_k$$$. The existence of the characteristic polynomial is the criterion of $$$f_k$$$ being a linear recurrence. So, we need to prove that there is such a polynomial for $$$f_k$$$ defined above.

#### Joint umbral calculus

To analyze joint properties of $$$d_k$$$ and $$$e_k$$$, we define a linear functional $$$T: R[d, e] \to R$$$ such that

Similarly to the case of a single recurrence, $$$T(f(d, e))=0$$$ whenever $$$f(d, e)$$$ is a linear combination of $$$a(d)$$$ and $$$b(e)$$$, where

are the characteristic polynomials of $$$d_i$$$ and $$$e_j$$$. In other words, $$$T(f(d, e))=0$$$ whenever $$$f(d, e)$$$ lies in the ideal $$$\langle a(d), b(e) \rangle$$$.

### Composed sum

For the binomial convolution let $$$f=d+e$$$, then

To show that $$$f_k$$$ is a linear recurrence obeying to the rule

it is sufficient to show that there is a characteristics polynomial $$$c(f)$$$ such that $$$c(f) \in \langle a(d), b(e) \rangle$$$.

Assume that $$$R$$$ is an integral domain. Then the polynomial exists and can be defined explicitly as

where

The fact that $$$c(d+e) \in \langle a(d), b(e) \rangle$$$ is proven as follows:

In the sum above, there are $$$2^{kl}$$$ summands, each of them is divisible by either $$$a(d)$$$ or $$$b(e)$$$, so $$$c(d+e) \in \langle a(d), b(e)\rangle$$$.

The polynomial $$$c(f)$$$ defined above is called the composed sum of $$$a(d)$$$ and $$$b(e)$$$.

### Composed product

Now the question is, how to prove that the Hadamard product $$$f_k = d_k e_k$$$ is a linear recurrence?

Using similar logic as above, one would define $$$f = de$$$ and then look for $$$c(f) \in \langle a(d), b(e) \rangle$$$. Let

This one is a bit trickier to prove. Let's start with $$$k=l=1$$$:

Rewriting it in the same way for arbitrary $$$k$$$ and $$$l$$$, we get

Then the same logic applies as to $$$c(d+e)$$$ in the binomial convolution case.

The polynomial $$$c(f) = c(de)$$$ defined above is called the composed product of $$$a(d)$$$ and $$$b(e)$$$.

### Computing composed products and sums

Let $$$s_i$$$ be the sum of $$$i$$$-th powers of all $$$\lambda$$$ and $$$t_j$$$ be the sum of $$$j$$$-th powers of all $$$\mu$$$, that is

The roots of the composed sum are $$$\lambda_i + \mu_j$$$ for all $$$i$$$ and $$$j$$$ and of the composed product are $$$\lambda_i \mu_j$$$, from which we can see that

So, if we're able to transform from $$$a(d)$$$ to $$$s_i$$$, then from $$$b(e)$$$ to $$$t_j$$$, compute the transforms above on them and then recover the characteristics polynomials from the result, it would solve the problem.

Next thing we should note is that the generating function of $$$s_i$$$ is

It can be further expanded as

where

is the reversed characteristic polynomial of $$$d_k$$$. Its log-derivative is indeed

Finally, to inverse this transform, we could make use of the fact that $$$\frac{A'}{A} = (\log A)'$$$, hence for

it holds that

The resulting $$$f(x)$$$ has degree $$$kl$$$, so only $$$kl$$$ terms of $$$\frac{A'}{A}$$$ and $$$\exp$$$ are needed and they may be computed in $$$O(kl \log kl)$$$.

The problem of computing first few terms of the composed product of two polynomials appeared before as a problem H in XVIII Open Cup. Stage 9. Grand Prix of Peterhof (statements), solution to which was explained in e.g. this comment.

ok

Another way to arrive to composed sums and products is via the explicit formula:

Taking Hadamard product or binomial convolution of $$$d_m$$$ and $$$e_m$$$ in this representation, you would indeed see that roots combine to $$$\lambda_i \mu_j$$$ and $$$\lambda_i + \mu_j$$$ correspondingly for the Hadamard product and the binomial convolution.

This should hint at composed sum and composed product, however doesn't seem to be rigorous enough and doesn't seem to cover all the cases (e.g. when the characteristic polynomial has roots with multiplicities), so I decided to stick with the umbral calculus explanation.

I was thinking just recently if a Hadamard power of a linear recurrence is also a linear recurrence (though I didn't know the name "Hadamard power"). I came to a conclusion that it indeed is, because we kind of know how to linearly transform all $$$k$$$-products of last $$$d$$$ members into the corresponding products of the next members, but decided to just berlekamp the coefficients.

Anyway, thank you for delivering what I needed

I'll pretend that I understood that thanks

In the article, I assume that $$$R$$$ is an integral domain, so that the decomposition

exists in the algebraic closure of the field of fractions of $$$R$$$.

However, composed sum and product always have coefficients in $$$R$$$ and can be defined in the following way:

Let $$$A$$$ be a matrix that has characteristic polynomial $$$a(d)$$$ and $$$B$$$ be a matrix that has characteristic polynomial $$$b(e)$$$. Then the composed sum $$$f(d+e)$$$ is the characteristic polynomial of $$$A \oplus B$$$ and the composed product $$$f(de)$$$ is the characteristic polynomial of $$$A \otimes B$$$, where $$$A \otimes B$$$ is the Kronecker product of $$$A$$$ and $$$B$$$, and $$$A \oplus B$$$ is the Kronecker sum of $$$A$$$ and $$$B$$$.

This leads me to the assumption that the composed product and composed sum would be the characteristic polynomials of the Hadamard product and the binomial convolution for any ring $$$R$$$, but I'm uncertain how to prove it without using the decomposition of characteristic polynomials into the product of monomials.

clyring, I wonder if you have any ideas on this?

Perhaps, the following rationale would work for the composed product:

In the Kronecker product terms it means that

where

and

And for the Kronecker sum $$$A \oplus B = A \otimes I + I \otimes B$$$, it generally holds that

Therefore,

Thus, if we look specifically on

we'll notice that

hece $$$C_{00}$$$ is the $$$m$$$-th element of the binomial convolution of $$$d_i$$$ and $$$e_j$$$.

I'm not yet convinced that some version of this works even over general non-commutative rings. (But maybe you know something I don't.) It indeed works nicely over any commutative ring.

Since $$$a$$$ and $$$b$$$ are monic, it's easy to show that as $$$R$$$-modules, $$$R[d] / \langle a(d) \rangle \cong R^l$$$, $$$R[e] / \langle b(e) \rangle \cong R^k$$$, and $$$R[d,e] / \langle a(d),b(e) \rangle \cong R^{l \times k}$$$, with multiplication in $$$R[d,e]$$$ witnessing the resulting isomorphism between the tensor product $$$(R[d] / \langle a(d) \rangle) \otimes_R (R[e] / \langle b(e) \rangle)$$$ and $$$R[d,e] / \langle a(d),b(e) \rangle$$$. So the Kronecker sum and product have all of the desired properties even when $$$R$$$ is not a field.

It's also straightforward (if a bit tedious) to directly show using the fundamental theorem of symmetric polynomials that all of the coefficients generated by your construction of $$$c$$$ and the (omitted) construction of the decomposition of $$$c(de)$$$ into a sum of a multiple of $$$a(d)$$$ and a multiple of $$$b(e)$$$ will yield coefficients in the subring of $$$R$$$ generated by the coefficients of $$$a$$$ and $$$b$$$ if $$$R$$$ is an algebraically closed field. And since this decomposition can be seen as $$$kl$$$ identities each valid in any algebraically closed field, it is automatically valid in any commutative ring $$$R$$$: $$$R$$$ is obviously isomorphic to a quotient ring of the integral domain of polynomials in $$$|R|$$$ variables over the integers, and the algebraic closure of the field of fractions of the latter exists.

I doubt I know anything you do not...

I didn't even understand much of your comment, unfortunately >.<

By the way, mango_lassi told me today about Hilbert's Nullstellensatz.

It seems that from Nullstellensatz it follows immediately that $$$c(de) \in \langle a(d), b(e)\rangle$$$ for the composed product and $$$c(d+e) \in \langle a(d), b(e) \rangle$$$ for the composed sum, as $$$c(de)$$$ and $$$c(d+e)$$$ vanish on the cartesian product of roots of $$$a(d)$$$ and roots of $$$b(e)$$$.

The nullstellensatz only proves membership in the radical of the ideal, which can be a strict superset of $$$\langle a(d), b(e) \rangle$$$ when there are repeated roots. So I'm not sure it's directly useful here, although of course it contributes to the intuitive expectation that things should "just work."

one suggestion sir if you don't mind => Adding list prerequisite in tutorial blog can be very helpful and user friendly (like monogon's blog)