Chapter 18

Show that the only sequence for which 1 is a generating polynomial is the "all zero" sequence.

Let \(\Psi=\left\\{\alpha_{i}\right\\}_{i=0}^{\infty}\) be a sequence of elements of an \(F\) -vector space \(V\). Further, suppose that \(\Psi\) has non- zero minimal polynomial \(\phi .\) (a) Show that for all polynomials \(g, h \in F[X],\) if \(g \equiv h(\bmod \phi),\) then \(g \star \Psi=h \star \Psi\). (b) Let \(m:=\operatorname{deg}(\phi) .\) Show that if \(g \in F[X]\) and \(\left(X^{i} g\right) \star \Psi=0\) for all \(i=0, \ldots, m-1,\) then \(g\) is a generating polynomial for \(\Psi\).

EXERCISE \(18.3 .\) This exercise develops an alternative characterization of linearly generated sequences. Let \(\Psi=\left\\{z_{i}\right\\}_{i=0}^{\infty}\) be a sequence of elements of \(F\). Further, suppose that \(\Psi\) has minimal polynomial \(\phi=\sum_{j=0}^{m} c_{j} X^{j}\) with \(m>0\) and \(c_{m}=1\). Define the matrix $$ A:=\left(\begin{array}{cccc} z_{0} & z_{1} & \cdots & z_{m-1} \\ z_{1} & z_{2} & \cdots & z_{m} \\ \vdots & \vdots & \ddots & \vdots \\ z_{m-1} & z_{m} & \cdots & z_{2 m-2} \end{array}\right) \in F^{m \times m} $$ and the vector $$ w:=\left(z_{m}, \ldots, z_{2 m-1}\right) \in F^{1 \times m} $$ Show that $$ v=\left(-c_{0}, \ldots,-c_{m-1}\right) \in F^{1 \times m} $$ is the unique solution to the equation $$ v A=w . $$.

Let \(V\) be a vector space over \(F,\) and consider the set \(V^{\times \infty}\) of all infinite sequences \(\left\\{\alpha_{i}\right\\}_{i=0}^{\infty},\) where the \(\alpha_{i}\) 's are in \(V .\) Let us define the scalar product of \(g \in F[X]\) and \(\Psi \in V^{\times \infty}\) as $$ g \cdot \Psi=\left\\{\left(X^{i} g\right) \star \Psi\right\\}_{i=0}^{\infty} \in V^{\times \infty} $$ Show that with this scalar product, and addition defined component-wise, \(V^{\times \infty}\) is an \(F[X]\) -module, and that a polynomial \(g \in F[X]\) is a generating polynomial for \(\Psi \in V^{\times \infty}\) if and only if \(g \cdot \Psi=0 .\)

Suppose \(F\) is a finite field and that \(\Psi:=\left\\{z_{i}\right\\}_{i=0}^{\infty}\) is linearly generated, with minimal polynomial \(\phi .\) Further, suppose \(X \nmid \phi .\) Show that \(\Psi\) is purely periodic with period equal to the multiplicative order of \([X]_{\phi} \in(F[X] /(\phi))^{*}\). Hint: use Exercise 17.12 and Theorem 18.2 .

If \(|F|=q\) and \(\phi \in F[X]\) is monic and factors into monic irreducible polynomials in \(F[X]\) as \(\phi=\phi_{1}^{e_{1}} \cdots \phi_{r}^{e_{r}},\) show that $$ \Lambda_{F}^{\phi}(1)=\prod_{i=1}^{r}\left(1-q^{-\operatorname{deg}\left(\phi_{i}\right)}\right) \geq 1-\sum_{i=1}^{r} q^{-\operatorname{deg}\left(\phi_{i}\right)} $$ From this, conclude that the probability that Algorithm MP terminates after just one loop iteration is \(1-O(m / q),\) where \(m=\operatorname{deg}(\phi) .\) Thus, if \(q\) is very large relative to \(m,\) it is highly likely that Algorithm MP terminates after just one iteration of the main loop.

Let \(f \in F[X]\) be a monic polynomial of degree \(\ell>0\) over a field \(F,\) and let \(E:=F[X] /(f) .\) Also, let \(\xi:=[X]_{f} \in E .\) For computational purposes, we assume that elements of \(E\) and \(D_{F}(E)\) are represented as coordinate vectors with respect to the usual "polynomial" basis \(\left\\{\xi^{i-1}\right\\}_{i=1}^{\ell} .\) For \(\beta \in E,\) let \(M_{\beta}\) denote the \(\beta\) -multiplication map on \(E\) that sends \(\alpha \in E\) to \(\alpha \beta \in E,\) which is an \(F\) -linear map from \(E\) into \(E\). (a) Given as input the polynomial \(f\) defining \(E,\) along with a projection \(\pi \in \mathcal{D}_{F}(E)\) and an element \(\beta \in E,\) show how to compute the projection \(\pi \circ M_{\beta} \in D_{F}(E),\) using \(O\left(\ell^{2}\right)\) operations in \(F\). (b) Given as input the polynomial \(f\) defining \(E,\) along with a projection \(\pi \in D_{F}(E),\) an element \(\alpha \in E,\) and a parameter \(k>0,\) show how to compute \(\left(\pi(1), \pi(\alpha), \ldots, \pi\left(\alpha^{k-1}\right)\right)\) using just \(O\left(k \ell+k^{1 / 2} \ell^{2}\right)\) operations in \(F,\) and space for \(O\left(k^{1 / 2} \ell\right)\) elements of \(F\). Hint: use the same hint as in Exercise 17.3

Let \(f \in F[X]\) be a monic polynomial of degree \(\ell>0\) over a field \(F\) (not necessarily finite), and let \(E:=F[X] /(f) .\) Further, suppose that \(f\) is irreducible, so that \(E\) is itself a field. Show how to compute the minimal polynomial of \(\alpha \in E\) over \(F\) deterministically, using algorithms that satisfy the following complexity bounds: (a) \(O\left(\ell^{3}\right)\) operations in \(F\) and space for \(O(\ell)\) elements of \(F\); (b) \(O\left(\ell^{2.5}\right)\) operations in \(F\) and space for \(O\left(\ell^{1.5}\right)\) elements of \(F\).

Let \(\tau \in \mathcal{L}_{F}(V)\) have non-zero minimal polynomial \(\phi\) of degree \(m,\) and let \(\phi=\phi_{1}^{e_{1}} \cdots \phi_{r}^{e_{r}}\) be the factorization of \(\phi\) into monic irreducible polynomials in \(F[X] .\) Let \(\odot\) be the scalar multiplication associated with \(\tau .\) Show that \(\beta \in V\) has minimal polynomial \(\phi\) under \(\tau\) if and only if \(\phi / \phi_{i} \odot \beta \neq 0\) for \(i=1, \ldots, r\)

Let \(\tau \in \mathcal{L}_{F}(V)\) have non-zero minimal polynomial \(\phi .\) Show that \(\tau\) is bijective if and only if \(X \nmid \phi\)

Let \(F\) be a finite field, and let \(V\) have finite dimension \(\ell>0\) over \(F\). Let \(\tau \in \mathcal{L}_{F}(V)\) have minimal polynomial \(\phi,\) with \(\operatorname{deg}(\phi)=m(\) and of course, by Theorem \(18.13,\) we have \(m \leq \ell) .\) Suppose that \(\alpha_{1}, \ldots, \alpha_{s}\) are randomly chosen elements of \(V\). Let \(g_{j}\) be the minimal polynomial of \(\alpha_{j}\) under \(\tau,\) for \(j=\) \(1, \ldots, s .\) Let \(Q\) be the probability that \(\operatorname{lcm}\left(g_{1}, \ldots, g_{s}\right)=\phi .\) The goal of this exercise is to show that \(Q \geq \Lambda_{F}^{\phi}(s),\) where \(\Lambda_{F}^{\phi}(s)\) is as defined in \(\S 18.3 .\) (a) Using Theorem 18.12 and Theorem \(18.11,\) show that if \(m=\ell,\) then \(Q=\) \(\Lambda_{F}^{\phi}(s)\) (b) Without the assumption that \(m=\ell,\) things are a bit more challenging. Adopting the matrix-oriented point of view discussed at the end of 818.3 , and transposing everything, show that \(-\) there exists \(\pi \in \mathcal{D}_{F}(V)\) such that the sequence \(\left\\{\pi \circ \tau^{i}\right\\}_{i=0}^{\infty}\) has minimal polynomial \(\phi,\) and \(-\) if, for \(j=1, \ldots, s,\) we define \(h_{j}\) to be the minimal polynomial of the sequence \(\left\\{\pi\left(\tau^{i}\left(\alpha_{j}\right)\right)\right\\}_{i=0}^{\infty},\) then the probability that \(\operatorname{lcm}\left(h_{1}, \ldots, h_{s}\right)=\) \(\phi\) is equal to \(\Lambda_{F}^{\phi}(s)\) (c) Show that \(h_{j} \mid g_{j},\) for \(j=1, \ldots, s,\) and conclude that \(Q \geq \Lambda_{F}^{\phi}(s)\).

Let \(f, g \in F[X]\) with \(f \neq 0,\) and let \(h:=f / \operatorname{gcd}(f, g) .\) Show that \(g \cdot F[X] /(f)\) and \(F[X] /(h)\) are isomorphic as \(F[X]\) -modules.

In this exercise, you are to derive the fundamental theorem of finite dimensional \(F[X]\) -modules, which is completely analogous to the fundamental theorem of finite abelian groups. Both of these results are really special cases of a more general decomposition theorem for modules over a principal ideal domain. Let \(V\) be an \(F[X]\) -module. Assume that as an \(F\) -vector space, \(V\) has finite dimension \(\ell>0,\) and that the \(F[X]\) -exponent of \(V\) is generated by the monic polynomial \(\phi \in F[X]\) (note that \(1 \leq \operatorname{deg}(\phi) \leq \ell\) ). Show that there exist monic, non- constant polynomials \(\phi_{1}, \ldots, \phi_{t} \in F[X]\) such that $$ \text { - } \phi_{i} \mid \phi_{i+1} \text { for } i=1, \ldots, t-1, \text { and } $$ \- \(V\) is isomorphic, as an \(F[X]\) -module, to the direct product of \(F[X]\) -modules $$ V^{\prime}:=F[X] /\left(\phi_{1}\right) \times \cdots \times F[X] /\left(\phi_{t}\right) $$ Moreover, show that the polynomials \(\phi_{1}, \ldots, \phi_{t}\) satisfying these conditions are uniquely determined, and that \(\phi_{t}=\phi .\) Hint: one can just mimic the proof of Theorem \(6.45,\) where the exponent of a group corresponds to the \(F[X]\) -exponent of an \(F[X]\) -module, and the order of a group element corresponds to the \(F[X]\) -order of an element of an \(F[X]\) -module - everything translates rather directly, with just a few minor, technical differences, and the previous exercise is useful in proving the uniqueness part of the theorem.

Let us adopt the same assumptions and notation as in Exercise \(18.15,\) and let \(\tau \in \mathcal{L}_{F}(V)\) be the map that sends \(\alpha \in V\) to \(X \odot \alpha .\) Further, let \(\sigma: V \rightarrow V^{\prime}\) be the isomorphism of that exercise, and let \(\tau^{\prime} \in \mathcal{L}_{F}\left(V^{\prime}\right)\) be the \(X\) -multiplication map on \(V^{\prime}\). (a) Show that \(\sigma \circ \tau=\tau^{\prime} \circ \sigma\). (b) From part (a), derive the following: there exists a basis for \(V\) over \(F\), with respect to which the matrix of \(\tau\) is the "block diagonal" matrix $$ T=\left(\begin{array}{llll} C_{1} & & & \\ & C_{2} & & \\ & & \ddots & \\ & & & C_{t} \end{array}\right), $$ where each \(C_{i}\) is the companion matrix of \(\phi_{i}\) (see Example 14.1 ).