Multidimensional Recurrence Relation

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 16, March 12 Scribe: Virgínia Rodrigues

Let $s=\{s_i\}_{i\geq 0}$ be an infinite sequence, where $s_i \in {\mathbb F}.$ A polynomial

$$f=\sum_{i=0}^mf_ix^i \in {\mathbb F}[x]$$

is a recurrence relation for the sequence s if

$$s_{r+m}f_m+s_{r+m-1}f_{m-1}+\dots+s_{r+1}f_1+s_rf_0 = 0,\ \ \forall r\geq 0.$$ (21)

Certainly the zero polynomial is a recurrence relation for any sequence s. Suppose f is a nonzero polynomial of degree m. Write f as

$$f=x^m-(a_{m-1}x^{m-1}+\dots+a_1x+a_0).$$

Then (22) is equivalent to

$$s_{r+m}=s_{r+m-1}a_{m-1}+\dots+s_{r+1}a_1+s_ra_0, \ \ \forall r\geq 0.$$

Hence, the whole sequence s can be generated by f from $s_0,s_1,\dots,s_{m-1}$. We say that f generates s.

It is well-known that the set of all recurrence relations for s form an ideal in ${\mathbb F}[x]$. Computing a minimal generator of the ideal is equivalent to finding the shortest recurrence relation for s. Berlekamp-Massey algorithm is designed to solve this problem.

Now we generalize recurrence relation to higher dimension. An n-dimensional sequence s is a map

$$\begin{array}{llcl} s: & {\mathbb N}^n & \longrightarrow & {\mathbb F}\\ & \alpha & \longmapsto & s_{\alpha} \end{array}$$

For n=2 we may visualize s in the Euclidean plane as in Figures 16.1 and 16.2 where each lattice point represents an entry of s.

Fix a monomial order on ${\mathbb F}[x_1, \dots, x_n]$. For a polynomial $f\in {\mathbb F}[x_1,\dots,x_n]$, write its terms in decreasing order:

$$f=f_{{\alpha}_{m}}x^{{\alpha}_{m}}+f_{{\alpha}_{m-1}}x^{{\alpha}_{m-1}}+ \dots+f_{\alpha_1}x^{{\alpha}_1},$$

where $\alpha_i \in {\mathbb N}^n$ and $\alpha_m>\alpha_{m-1}>\dots>\alpha_{1}.$ We call f a recurrence relation of s if

$$s_{\beta+\alpha_{m}}f_{\alpha_{m}}+s_{\beta+\alpha_{m-1}}f_{... ...ha_{1}}f_{\alpha_{1}} = 0,\ \ \forall \beta \in {\mathbb N}^n.$$ (22)

Denote by I(s) the set of all recurrence relations of s.

Example (for n=2). Use lex order with y>x on ${\mathbb F}[x,y]$.

If $f=f_1=y^4-yx-x^2+1 \in {\mathbb F}[x,y]$, then (23) becomes

$$s_{i,j+4}-s_{i+1,j+1}-s_{i+2,j}+s_{i,j} = 0,\ \ \forall i,j \in {\mathbb N},$$

or, equivalently,

$$s_{i,j}=s_{i+1,j-3}+s_{i+2,j-4}-s_{i,j-4},\ \ \forall i \geq 0, j \geq 4.$$

This means all the entries s_i,j with $j \geq 4$ can be generated by f₁ from entries s_i,j with $j\leq 3$. In Figure 16.1, the shaded region represents all the entries that can be generated by f₁.

Figure 16.1: Entries generated by f₁

If f=f₂=x³y²-x²y-y+x+1 then the recurrence relation is

$$s_{i,j}=s_{i-1,j-1}+s_{i-3,j-1}-s_{i-2,j-2}-s_{i-3,j-2}, \ \ \forall i \geq 3, j \geq 2.$$

This means all the entries s_i,j with $i \geq 3, j \geq 2$, can be generated from entries s_i,j with i<3 or j<2, as reppresented by the shaded region in Figure 16.2.

Figure 16.2: Entries generated by f₂

If f=f₃ = x⁶ + x -1, the recurrence relation is

$$s_{i,j} = -s_{i-5, j} + s_{i-6,j}, \ \ \forall i \geq 6, j \geq 0.$$

If f₁, f₂ and f₃ are all recurrence relations for s, then the shaded region in Figure 16.3 represents all entries of sthat can be generated by them. Hence, in this case, all the entries of s can be generated by f₁, f₂ and f₃ from finitely many of them as indicated in the unshaded region.

Figure 16.3: Entries generated by f₁, f₂, f₃

Lemma 16.1   I(s) is an ideal in ${\mathbb F}[x_1, \dots, x_n]$.

Proof. We need to prove that $f,g \in I(s)$ implies $f+g \in I(s)$ and $h\cdot f \in I(s)$ for any $h \in {\mathbb F}[x_1, \dots, x_n]$. Note that in (23) it is not necessary that all the coeeficients of f be nonzero, so one can drop any zero terms in f or add any finite number of terms with zero coefficient to f (the ``leading term $x^{\alpha_m}$'' of f may change then), (23) still holds. Hence we may assume that f and g contain the same collection of monomials and write them as

$$\begin{eqnarray*}f & = & f_{{\alpha}_{m}}x^{{\alpha}_{m}}+f_{{\alpha}_{m-1}}x^{{... ...ha}_{m-1}}x^{{\alpha}_{m-1}}+ \dots+g_{\alpha_1} x^{{\alpha}_1} \end{eqnarray*}$$

where $\alpha_i \in {\mathbb N}^n$ and $\alpha_m>\alpha_{m-1}>\dots>\alpha_{1}.$Since $f,g \in I(s)$, f satisfies (23) and g satisfies

$$s_{\beta+\alpha_{m}}g_{\alpha_{m}}+s_{\beta+\alpha_{m-1}}g_{\... ...pha_{1}}g_{\alpha_{1}} = 0,\ \ \forall \beta \in {\mathbb N}^n.$$

Adding this equation to (23) yields

$$s_{\beta+\alpha_{m}}(f_{\alpha_{m}}+g_{\alpha_{m}}) +s_{\beta... ...{1}}+ g_{\alpha_{1}}) = 0, \ \ \forall \beta \in {\mathbb N}^n.$$

Hence f+g is a recurrence relation for s, i.e., $f+g \in I(s)$.

Now let $ax^{\gamma}$ be any term in ${\mathbb F}[x_1, \dots, x_n]$ and $f \in I(s)$. We show that $ax^{\gamma}f \in I(s)$. Certainly,

$$ax^{\gamma}f = af_{{\alpha}_{m}}x^{{\alpha}_{m}+\gamma}+ \cdots + a f_{\alpha_1} x^{{\alpha}_1 +\gamma}.$$

Multiplying (23) by a on both sides and substituting $\beta$ by $\beta+\gamma$, we have

$$s_{\beta+\alpha_{m}+\gamma}f_{\alpha_{m}} +s_{\beta+\alpha_{m... ...\gamma}f_{\alpha_{1}} = 0, \ \ \forall \beta \in {\mathbb N}^n.$$

This means that $ax^{\gamma}f$ is a recurrence relation for s.

Finally, the above two facts implies that, for any $f \in I(s)$ and $h \in {\mathbb F}[x_1, \dots, x_n]$, $h\cdot f \in I(s)$ as $h\cdot f$ is just a sum of $ax^{\gamma}f$ for terms $ax^{\gamma}$ in h. Therefore I(s) is an ideal. $\Box$

Let I be a radical ideal in ${\mathbb F}[x_1, \dots, x_n]$. Suppose that |B(I)|=|V(I)|=t. Order the points in V(I) as

$$P_1,P_2,\dots,P_t,$$

where $P_i \in {\mathbb F}^n.$Let $e=(e_1,\dots,e_n) \in {\mathbb F}^t$ (an error vector). Define an n-dimensional array s as follows: For $\beta \in {\mathbb N}^n$,

$$s_{\beta}=\sum_{i=1}^{t}e_iP_{i}^{\beta} \in {\mathbb F}.$$

This is a generalized Fourier transform of e, called the syndrome of e. The support of e is defined as

$$\mbox{Supp}(e)=\{P_i:\ e_i \neq 0,\ 1\leq i\leq t\}.$$

Theorem 16.2   Let $e \in {\mathbb F}^t$ and let s be the syndrome of e. Then a polynomial $f\in {\mathbb F}[x_1,\dots,x_n]$ is a recurrence relation for s if and only if $f(P)=0, \forall P \in \mbox{Supp}(e).$ That is, $I(s)=I(\mbox{Supp}(e))$. So I(s) is called the error locator ideal of e.

Proof. Suppose $f= \sum_{i=1}^{m} f_{\alpha_i} x^{\alpha_i}$. Note that

$$\begin{eqnarray*}\sum_{i=1}^{m} s_{\beta+\alpha_i} f_{\alpha_i} & = & \sum_{i=1}... ...\alpha_i} P_j^{\alpha_i} = \sum_{j=1}^{t}e_j P_j^{\beta} f(P_j), \end{eqnarray*}$$

i.e.,

$$\sum_{i=1}^{m} s_{\beta+\alpha_i} f_{\alpha_i} = \sum_{j=1}^{t} e_j f(P_j) \cdot P_j^{\beta}.$$ (23)

If f(P)=0 for all $P\in \mbox{Supp}(e)$ then (23) holds for all $\beta \in {\mathbb N}^n$, so $f \in I(s)$. Conversely, if $f \in I(s)$ then (23) and (24) imply that

$$\sum_{j=1}^{t} e_j f(P_j) \cdot P_j^{\beta} = 0, \ \ \ \forall \beta \in N^n.$$

This means that the Fourier transform of the vector $E=(e_1 f(P_1), \cdots, e_t f(P_t))$ is identically zero, so E itself must be zero. Hence f(p_j) =0 whenever $e_j\ne 0$, that is, if $P\in \mbox{Supp}(e)$ then f(P)=0. This completes the proof. $\Box$