Hadamard product and binomial convolution of linear recurrences

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

$$$\begin{gather} d_m = \sum\limits_{i=1}^k a_i d_{m-i}\text{ for }m \geq k, \\ e_m = \sum\limits_{i=1}^l b_i e_{m-i}\text{ for }m \geq l. \end{gather}$$$

In some applications, the following two sequences arise:

$$$\begin{gather} f_k &=& d_k e_k & \text{(Hadamard product)}, \\ f_k &=& \sum\limits_{i+j=k} \binom{k}{i} d_i e_j & \text{(binomial convolution)}. \end{gather}$$$

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

$$$ T(f^k) = f_k. $$$

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

$$$ T(d^i e^j) = d_i e_j. $$$

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

$$$\begin{gather} a(d) &=& d^k - \sum\limits_{i=1}^k a_i d^{k-i}, \\ b(e) &=& e^l - \sum\limits_{j=1}^l b_j e^{l-j}. \end{gather}$$$

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

$$$ T(f^k)=T((d+e)^k) = T\left(\sum\limits_{i=0}^k \binom{k}{i} d^i e^{k-i}\right) = \sum\limits_{i=0}^k \binom{k}{i} T(d^ie^{k-i}) = f_k $$$

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

$$$ f_m = \sum\limits_{i=1}^t c_i f_{m-i}\text{ for }m \geq t, $$$

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

$$$ c(d+e) = \prod\limits_{i=1}^k \prod\limits_{j=1}^l ((d+e)-(\lambda_i + \mu_j)), $$$

where

$$$\begin{gather} a(d) &=& \prod\limits_{i=1}^k (d-\lambda_i),\\ b(e) &=& \prod\limits_{j=1}^l (e-\mu_j). \end{gather}$$$

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

$$$\begin{align} c(d+e) = & \prod\limits_{i=1}^k \prod\limits_{j=1}^l ((e-\mu_j) + (d - \lambda_i )) = \\ = \sum\limits_{r_{ij} \in \{0,1\}} & \prod\limits_{i=1}^k \prod\limits_{j=1}^l (e-\mu_j)^{r_{ij}}(d-\lambda_i)^{1-r_{ij}}. \end{align}$$$

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

$$$ c(de) = \prod\limits_{i=1}^k \prod\limits_{j=1}^l (de - \lambda_i \mu_j). $$$

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

$$$ c(de) = de-\lambda \mu = d(e-\mu) + (d - \lambda)\mu. $$$

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

$$$\begin{align} c(de) = & \prod\limits_{i=1}^k \prod\limits_{j=1}^l (d(e-\mu_j) + (d - \lambda_i )\mu_j) = \\ = \sum\limits_{r_{ij} \in \{0,1\}} & \prod\limits_{i=1}^k \prod\limits_{j=1}^l d^{r_{ij}}\mu_j^{1-r_{ij}}(e-\mu_j)^{r_{ij}}(d-\lambda_i)^{1-r_{ij}}. \end{align}$$$

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

$$$\begin{align} s_i = \lambda_1^i + \dots + \lambda_k^i, \\ t_j = \mu_1^j + \dots + \mu_l^j. \end{align}$$$

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

$$$\begin{gather} \sum\limits_{i=1}^k \sum\limits_{j=1}^l (\lambda_i \mu_j)^z &=& \sum\limits_{i=1}^k \lambda_i^z \sum\limits_{j=1}^l \mu_j^z &=& s_z t_z, \\ \sum\limits_{i=1}^k \sum\limits_{j=1}^l (\lambda_i + \mu_j)^z &=& \sum\limits_{x+y=z} \binom{z}{x} \sum\limits_{i=1}^k \lambda_i^x \sum\limits_{j=1}^l \mu_j^y &=& \sum\limits_{x+y=z} \binom{z}{x} s_x t_y. \\ \end{gather}$$$

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

$$$ \sum\limits_{i=0}^\infty s_i x^i = \sum\limits_{i=0}^\infty \sum\limits_{j=1}^k \lambda_j^i x^i = \sum\limits_{j=1}^k \frac{1}{1-\lambda_i x}. $$$

It can be further expanded as

$$$ \sum\limits_{j=1}^k \frac{1}{1-\lambda_i x} = k + \sum\limits_{j=1}^k \frac{\lambda_i x}{1-\lambda_i x} = k - x \frac{A'(x)}{A(x)}. $$$

where

$$$ A(x) = 1 - \sum\limits_{i=1}^k a_i x^i = \prod\limits_{i=1}^k (1-\lambda_i x) $$$

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

$$$ \frac{A'(x)}{A(x)} = \sum\limits_{i=1}^k \frac{-\lambda_i}{1-\lambda_i x}. $$$

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

$$$ B(x) = k - x \frac{A'(x)}{A(x)} $$$

it holds that

$$$ A(x) = \exp \int \frac{k-B(x)}{x}dx. $$$

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

Комментарии (11)

Показать архивные | Написать комментарий?

adamant

2 года назад, # |

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.

→ Ответить

k1ngash

2 года назад, # ^ |

-9

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

$$$\begin{gather} d_m = \sum\limits_{i=1}^k \alpha_i \lambda_i^m, \\ e_m = \sum\limits_{j=1}^l \beta_j \mu_j^m. \end{gather}$$$

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.

Golovanov399

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

shadow9236

+24

I'll pretend that I understood that thanks

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

$$$ a(d) = \prod\limits_{i=1}^k (d-\lambda_i) $$$

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?

← Rev. 4 →

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

$$$ d_m e_m = \sum\limits_{i=1}^k \sum\limits_{j=1}^l a_i b_j d_{m-i} e_{m-j}. $$$

In the Kronecker product terms it means that

$$$ {\bf d}_m \otimes {\bf e}_m = \left(A^m {\bf d}_{0}\right) \otimes \left( B^m {\bf e}_{0}\right) = (A \otimes B)^m ({\bf d}_0 \otimes {\bf e}_0), $$$

$$$\begin{gather} {\bf d}_{m+1} = \begin{pmatrix}d_{m+k} \\ \dots \\ d_{m+2} \\ d_{m+1}\end{pmatrix}, & {\bf e}_{m+1} = \begin{pmatrix}e_{m+l} \\ \dots \\ e_{m+2} \\ e_{m+1}\end{pmatrix} \end{gather}$$$

and

$$$\begin{gather} A = \begin{pmatrix} a_1 & a_2 & \dots & a_{k-1} & a_k \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 & 0 \end{pmatrix}, & B = \begin{pmatrix} b_1 & b_2 & \dots & b_{l-1} & b_l \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 & 0 \end{pmatrix}. \end{gather}$$$

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

$$$ (A \oplus B) (x \otimes y) = (Ax)\otimes y + x \otimes (By). $$$

Therefore,

$$$ (A \oplus B)^m (x \otimes y) = \sum\limits_{z=0}^m \binom{m}{z} (A^z x) \otimes (B^{m-z}y). $$$

Thus, if we look specifically on

$$$ C = (A \oplus B)^m ({\bf d}_{0} \otimes {\bf e}_{0}), $$$

we'll notice that

$$$ C_{ij} = \sum\limits_{z=0}^m \binom{m}{z} d_{z+i} e_{m-z+j}, $$$

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

clyring

← Rev. 3 →

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

+18

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