Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences (Q841240)

Let \(g_1,\dots,g_s\in{\mathbb F}_q\) be arbitrary monic polynomials each of degree at least one. Let \({\mathcal M}(g_1,\dots,g_s)\) denote the set of \(s\)-fold multisequences \((\sigma_1,\dots,\sigma_s)\) such that \(\sigma_i\) is a linear recurring sequence over \({\mathbb F}_q\) with characteristic polynomial \(g_i\) for each \(1\leq i\leq s\). Let \(\Phi(d;g_1,\dots,g_s)\) denote the number of multisequences from \({\mathcal M}(g_1,\dots,g_s)\) with joint minimal polynomial \(d\in{\mathbb F}_q\). The main results of the paper give a formula for the counting function \(\Phi(d;g_1,\dots,g_s)\) and the expectation and the variance of the joint linear complexity of random multisequences that are uniformly distributed over \({\mathcal M}(g_1,\dots,g_s)\), where \(g\)'s are arbitrary nonconstant monic polynomials over \({\mathbb F}_q\) all in terms of parameters involving the factorizations of \(g_1,\dots,g_s\) and \(d\).