[proofplan] We pass to a splitting field $K \supseteq \mathbb{F}_2$ in which the auxiliary polynomials $P(X)$ and $Q(X)$ associated with the two LFSRs factor with distinct roots; this converts each stream into a finite sum of geometric sequences $\alpha^n$. Sums of such geometric streams remain in the same class, and their auxiliary polynomial is a divisor of the product $P(X)Q(X)$, giving an LFSR of length at most $M + N$. For products, multiplying two sums of geometrics produces a sum of $MN$ geometrics with ratios $\alpha_i \beta_j$, and the corresponding auxiliary polynomial $\prod_{i,j}(X - \alpha_i\beta_j)$ has degree $MN$. In each case the recurrence certifying the LFSR length is extracted from the annihilating polynomial of the geometric expansion. [/proofplan] [step:Reduce to distinct-root auxiliary polynomials over an extension field] Let $P(X) \in \mathbb{F}_2[X]$ be the auxiliary polynomial of the first LFSR, $\deg P = M$, and $Q(X) \in \mathbb{F}_2[X]$ the auxiliary polynomial of the second, $\deg Q = N$. Fix a splitting field $K \supseteq \mathbb{F}_2$ for $P(X)Q(X)$. We assume, as specified in the statement, that $P$ and $Q$ each split with distinct roots in $K$; write \begin{align*} P(X) = \prod_{i=1}^{M}(X - \alpha_i), \qquad Q(X) = \prod_{j=1}^{N}(X - \beta_j), \end{align*} where $\alpha_1, \ldots, \alpha_M, \beta_1, \ldots, \beta_N \in K$ are pairwise distinct within each list. By the [general solution of a linear recurrence with distinct characteristic roots](/theorems/???), there exist constants $\lambda_1, \ldots, \lambda_M, \mu_1, \ldots, \mu_N \in K$ such that \begin{align*} x_n = \sum_{i=1}^{M} \lambda_i \alpha_i^{n}, \qquad y_n = \sum_{j=1}^{N} \mu_j \beta_j^{n} \qquad \text{for all } n \ge 0. \end{align*} [guided] The auxiliary polynomial of an LFSR is the polynomial whose coefficients encode the feedback taps. A sequence $(x_n)$ is the output of the LFSR with auxiliary polynomial $P(X) = X^M - a_{M-1}X^{M-1} - \cdots - a_0$ if and only if $x_{n+M} = a_{M-1}x_{n+M-1} + \cdots + a_0 x_n$ for every $n \ge 0$. Why pass to a splitting field? Over $\mathbb{F}_2$ an auxiliary polynomial may be irreducible, so working over $K$ lets us express each stream in a uniform "sum of geometrics" basis. The standard structure theorem for linear recurrences states that if $P(X) = \prod_{i=1}^{M}(X - \alpha_i)$ has $M$ distinct roots in $K$, then every solution $(x_n)$ of the recurrence encoded by $P$ has the form $x_n = \sum_{i=1}^{M}\lambda_i \alpha_i^n$ for some scalars $\lambda_i \in K$ determined by the initial conditions. The hypothesis of distinct roots of $P$ and $Q$ in the statement is exactly what this theorem requires. [/guided] [/step] [step:Annihilate the sum by the product polynomial $P(X)Q(X)$] For part (i), we show that the stream $(x_n + y_n)$ satisfies the linear recurrence with auxiliary polynomial $R(X) := P(X)Q(X)$. We have \begin{align*} x_n + y_n = \sum_{i=1}^{M}\lambda_i \alpha_i^{n} + \sum_{j=1}^{N}\mu_j \beta_j^{n}. \end{align*} Let $R(X) = \prod_{i=1}^{M}(X - \alpha_i) \prod_{j=1}^{N}(X - \beta_j)$ and expand $R(X) = \sum_{k=0}^{M+N} c_k X^k$ with $c_{M+N} = 1$ and $c_k \in \mathbb{F}_2$ (since $R = PQ$ with $P, Q \in \mathbb{F}_2[X]$). For each root $\gamma \in \{\alpha_1, \ldots, \alpha_M, \beta_1, \ldots, \beta_N\}$ we have $R(\gamma) = 0$, so for every $n \ge 0$, \begin{align*} \sum_{k=0}^{M+N} c_k \gamma^{n+k} = \gamma^n R(\gamma) = 0. \end{align*} Applying this to each $\alpha_i$ with weight $\lambda_i$ and each $\beta_j$ with weight $\mu_j$ and summing, \begin{align*} \sum_{k=0}^{M+N} c_k (x_{n+k} + y_{n+k}) = \sum_{i=1}^{M}\lambda_i \sum_{k=0}^{M+N} c_k \alpha_i^{n+k} + \sum_{j=1}^{N}\mu_j \sum_{k=0}^{M+N} c_k \beta_j^{n+k} = 0. \end{align*} Since $c_{M+N} = 1$, this is the feedback relation associated with the auxiliary polynomial $R(X)$ of degree $M + N$; moreover $R \in \mathbb{F}_2[X]$, so the feedback taps lie in $\mathbb{F}_2$. Hence $(x_n + y_n)$ is the output of an LFSR of length $M + N$, and after stripping any leading common factor between consecutive coefficients the length is at most $M + N$. [guided] The strategy is: exhibit a monic polynomial $R(X) \in \mathbb{F}_2[X]$ that annihilates $(x_n + y_n)$ in the sense that the coefficients of $R$ give a valid feedback recurrence. We claim $R(X) = P(X)Q(X)$ works. Why this polynomial? The roots of $R$ are $\alpha_1, \ldots, \alpha_M, \beta_1, \ldots, \beta_N$. The geometric sequence $\gamma^n$ satisfies any recurrence whose characteristic polynomial vanishes at $\gamma$; more precisely, if $R(\gamma) = 0$ then $\sum_k c_k \gamma^{n+k} = \gamma^n R(\gamma) = 0$. Linear combinations of such geometrics also satisfy the recurrence, by linearity of the relation. Since $x_n + y_n$ is a linear combination of $\alpha_i^n$ (with weights $\lambda_i$) and $\beta_j^n$ (with weights $\mu_j$), and $R$ vanishes at every $\alpha_i$ and $\beta_j$, the combination is annihilated: \begin{align*} \sum_{k=0}^{M+N} c_k (x_{n+k} + y_{n+k}) = \sum_i \lambda_i \alpha_i^n R(\alpha_i) + \sum_j \mu_j \beta_j^n R(\beta_j) = 0. \end{align*} Why are the coefficients $c_k$ in $\mathbb{F}_2$? Because $P, Q \in \mathbb{F}_2[X]$, their product $R = PQ$ also lies in $\mathbb{F}_2[X]$. Thus the recurrence is realisable over the LFSR's working field. The resulting LFSR has length $\deg R = M + N$. The length could be strictly smaller when the minimal polynomial of $(x_n + y_n)$ divides $R$ properly (for instance, if $P$ and $Q$ share a root), but $M + N$ is always an upper bound. [/guided] [/step] [step:Annihilate the product by the polynomial with roots $\alpha_i \beta_j$] For part (ii), expand the product \begin{align*} x_n y_n = \left(\sum_{i=1}^{M} \lambda_i \alpha_i^{n}\right)\left(\sum_{j=1}^{N} \mu_j \beta_j^{n}\right) = \sum_{i=1}^{M}\sum_{j=1}^{N} \lambda_i \mu_j (\alpha_i \beta_j)^{n}. \end{align*} Define \begin{align*} S(X) := \prod_{i=1}^{M} \prod_{j=1}^{N} (X - \alpha_i \beta_j) \in K[X], \qquad \deg S = MN. \end{align*} Write $S(X) = \sum_{k=0}^{MN} d_k X^k$ with $d_{MN} = 1$. For each pair $(i, j)$, $S(\alpha_i \beta_j) = 0$, so \begin{align*} \sum_{k=0}^{MN} d_k (x_{n+k} y_{n+k}) = \sum_{i,j} \lambda_i \mu_j \sum_{k=0}^{MN} d_k (\alpha_i \beta_j)^{n+k} = \sum_{i,j} \lambda_i \mu_j (\alpha_i \beta_j)^n S(\alpha_i \beta_j) = 0. \end{align*} It remains to verify that $S(X) \in \mathbb{F}_2[X]$. The set $\{\alpha_i \beta_j\}_{i,j}$ is stable under the action of the absolute Galois group $\mathrm{Gal}(K/\mathbb{F}_2)$ on $K$: for any Galois automorphism $\sigma$, the image $\sigma(\alpha_i \beta_j) = \sigma(\alpha_i)\sigma(\beta_j)$ is again of the form $\alpha_{i'} \beta_{j'}$ because the root sets $\{\alpha_i\}$ and $\{\beta_j\}$ are each Galois-stable (being root sets of polynomials in $\mathbb{F}_2[X]$). Hence $\sigma(S) = S$, which forces the coefficients $d_k$ to lie in the fixed field $\mathbb{F}_2$. Therefore $S \in \mathbb{F}_2[X]$ is a monic polynomial of degree $MN$ whose associated recurrence is satisfied by $(x_n y_n)$, so $(x_n y_n)$ is the output of an LFSR of length at most $MN$. [guided] To prove $(x_n y_n)$ is an LFSR stream of length $\le MN$, we need a monic polynomial in $\mathbb{F}_2[X]$ of degree $\le MN$ whose associated recurrence annihilates the product. The expansion $x_n y_n = \sum_{i,j} \lambda_i \mu_j (\alpha_i \beta_j)^n$ shows that the product stream is a linear combination of $MN$ geometric sequences with ratios $\alpha_i \beta_j$. A natural candidate polynomial is therefore \begin{align*} S(X) = \prod_{i,j}(X - \alpha_i \beta_j), \end{align*} which has the $MN$ products as roots. The annihilation computation is the same as in the sum case: for each geometric $(\alpha_i \beta_j)^n$, the polynomial $S$ vanishes at the ratio, so $\sum_k d_k (\alpha_i \beta_j)^{n+k} = (\alpha_i \beta_j)^n S(\alpha_i \beta_j) = 0$. Summing over $(i,j)$ with the weights $\lambda_i \mu_j$ yields $\sum_k d_k x_{n+k}y_{n+k} = 0$. Why is $S \in \mathbb{F}_2[X]$? A priori $S$ has coefficients in $K$. We use Galois theory. The absolute Galois group $G := \mathrm{Gal}(K/\mathbb{F}_2)$ acts on $K$ and fixes $\mathbb{F}_2$ pointwise. Because $P \in \mathbb{F}_2[X]$, its root set $\{\alpha_i\}$ is stable under $G$; similarly $\{\beta_j\}$ is $G$-stable. Thus $\{\alpha_i \beta_j\}$ is $G$-stable, since $\sigma(\alpha_i \beta_j) = \sigma(\alpha_i) \sigma(\beta_j) \in \{\alpha_{i'}\}\{\beta_{j'}\} = \{\alpha_{i'}\beta_{j'}\}$. A polynomial whose root multiset is preserved by $G$ has coefficients in the fixed field, which is $\mathbb{F}_2$. Hence $S \in \mathbb{F}_2[X]$ and defines a legitimate LFSR of length $MN$ over $\mathbb{F}_2$. Can the length be strictly less than $MN$? Yes, if some of the products $\alpha_i \beta_j$ coincide, or if the expansion of $x_n y_n$ has zero coefficients for some geometrics. Hence $MN$ is an upper bound, not always the minimal length. [/guided] [/step] [step:Conclude the closure properties] From the previous two steps, $(x_n + y_n)$ satisfies a linear recurrence over $\mathbb{F}_2$ of order at most $M + N$, and $(x_n y_n)$ satisfies one of order at most $MN$. Each such recurrence defines an LFSR of the corresponding length whose output matches the given stream once the initial $M + N$ (resp. $MN$) values are loaded. This proves both statements. [/step]