Convolution of integer sequences

4.9k Views Asked by At

I read this somewhere:

$U$ and $V$ are defined on the set $\mathbb{Z}$ of integers. The convolution of $u$ and $v$, noted as $(u*v) (k)\,\theta$ or $ (u \otimes v) (k)\theta$, is a new sequence whose general term is given by $(u*v) (k) = (u \otimes v) (k) = \sum_{i=-\infty}^{\infty} u(i)v(k-i)\theta$

Can I take $\{-1, -2, -3, \ldots\}$ for $U$ and $\{1, 2, 3, \ldots\}$ for $V$?

How to interpret this: $(u*v) (k)\,\theta$

Why do we insert this part $ (k) \,\theta$ in the formula?

Why does $i$ go from $-\infty$ to $\infty$?

Could someone give me an example of this formula?

2

There are 2 best solutions below

18
On

The $k$ in the formula indicates that you are talking about the $k$th term in the sequence $u\ast v$.

I do not know for sure what the $\theta$ adds anything, unless that is part of the author's notation for making a modification of these sequences.

If summed from $-\infty$ to $\infty$, that sum is often going to be divergent: is it possible the $\theta$ is some restriction that zeros out all but finitely many terms of the series? Please consult your source.

As for "give me an example":

Take $u(x)$ and $v(x)$ to be integer polynomials, and then interpret them as sequences in the obvious way: i.e. you put the $i$th term to be the coefficient of $x^i$. Then you'll find that $u\ast v$ is the sequence representing the coefficients of $u(x)v(x)$!

Example: $u(x)=x-2$, $v(x)=3x^2+x$. The sequences are: $$ \dots u_{-2}=u_{-1}=0;\ \ u_0=-2;\ \ u_1=1; \ \ u_2=u_3=\dots=0 $$ $$ \dots v_{-2}=v_{-1}=v_0=0;\ \ v_1=1;\ \ v_2=3;\ \ v_3=v_4=\dots=0 $$

The convoluted sequence is:

$$ \dots (v\ast u)_{-2}=(v\ast u)_{-1}=(v\ast u)_0=0;\ \ (v\ast u)_1=-2;\ \ (v\ast u)_2=-5;\ \ (v\ast u)_3=3;\ \ (v\ast u)_4=(v\ast u)_5=\dots=0 $$

And that turns out to be exactly the sequence for $u(x)v(x)=3x^3-5x^2-2x$.

You can use this to show that the sequences of finite support contained in the nonnegative integers, equipped with the $\ast$ operation are isomorphic to $\Bbb{Z}[x]$. If you consider all sequences of finite support, then that is isomorphic to the "Laurent polynomials" $\Bbb Z[x,x^{-1}]$.

5
On

I'd write $$ (u*v)(k) = \sum_{i=-\infty}^\infty u(i)v(k-i). $$

I have no idea what the letter $\theta$ is doing there. As to why the $k$ is there, it's because you want to define $$ \ldots\ldots, (u*v)(-3), (u*v)(-2), (u*v)(-1), (u*v)(0), (u*v)(1), (u*v)(2), (u*v)(3), \ldots\ldots $$ etc. The number in the parentheses is $k$. Thus, for example, when $k=4$, we have \begin{align} (u*v)(4) = \sum_{i=-\infty}^\infty u(i)v(4-i) \end{align} $$ = \cdots\cdots+u(-3)v(7)+u(-2)v(6)+u(-1)v(5)+u(0)v(4)+u(1)v(3)+u(2)v(2) $$ $$ \phantom{={}} {}+u(3)v(1)+ u(4)v(0) + u(5) v(-1) + u(6)v(-2)+u(7)v(-3)+u(8)v(-4)+\cdots\cdots. $$