Multisequences with almost perfect linear complexity profile and function fields over finite fields (Q5925969): Difference between revisions

Let \(A=\{a_{1}, a_{2},\cdots,a_{m}\}\) be a multisequence over the finite field \(\mathbb{F}_{q}\) where \(a_{i}=\{a_{i1},a_{i2},\cdots \}\) is an infinite sequence, and let \(\{l_{n}(A)\}_{n=1}^{\infty}\) be the linear complexity profile of \(A\). If \(l_{n}(A)\geq\lceil \frac{m(n+1)-d}{m+1}\rceil\) for all \(n\), \(A\) is called \(d\)-perfect for a positive integer \(d\). \(A\) is called perfect if \(A\) is \(m\)-perfect. It is proved in this paper that \(A\) is perfect if and only if \( l_{n}(A)=\lceil \frac{mn}{m+1}\rceil\). A construction of \(d\)-perfect multisequences is given in this paper by using a function field over a finite field. Let \(\mathbf{F}\) be a global function field with the full constant field \(\mathbb{F}_{q}\). For a place \(\mathbb{Q}\) of degree \(m\) of \(\mathbf{F}\), let \(\mathbf{F}_{\mathbb{Q}}=\mathcal{O}_{\mathbb{Q}}/\mathcal{P}_{\mathbb{Q}}\) be the residue field of \(\mathbb{Q}\), where \(\mathcal{O}_{\mathbb{Q}}\), \(\mathcal{P}_{\mathbb{Q}}\) are the integral ring and maximal ideal at \(\mathbb{Q}\) respectively. Assume that \(t\) is a local parameter of \(\mathbb{Q}\) with \(\text{deg}(t)_{\infty}=m+1\). Choose \(m\) elements \(x_{1}, x_{2},\cdots, x_{m} \in \mathcal{O}_{\mathbb{Q}}\) such that \(x_{1}(\mathbb{Q}), x_{2}(\mathbb{Q}),\cdots, x_{m}(\mathbb{Q})\) form an \(\mathbb{F}_{q}\)-basis of \(\mathbf{F}_{\mathbb{Q}}\). For an element \(y\in \mathcal{O}_{\mathbb{Q}}\), it can be expressed by a formal series \[ y=\sum_{j=0}^{\infty}\Biggl(\sum_{i=1}^{m}a_{ij}x_{i}\Biggr)t^{j}. \] Put \(a_{i}(y)=(a_{i1}, a_{i2}, \cdots)\) (\(1\leq i\leq m\)). Then it is proved that \(A=(a_{1}, a_{2},\cdots,a_{m})\) is \(d\)-perfect where \(d=\text{deg} ((y)_{\infty}\vee (x_{1})_{\infty}\vee\cdots\vee(x_{m})_{\infty}).\) Some examples of this construction are given in the paper.