Towards a General Theory of Simultaneous Diophantine Approximation of Formal Power Series: Multidimensional Linear Complexity
<|reference_start|>Towards a General Theory of Simultaneous Diophantine Approximation of Formal Power Series: Multidimensional Linear Complexity: We model the development of the linear complexity of multisequences by a stochastic infinite state machine, the Battery-Discharge-Model, BDM. The states s in S of the BDM have asymptotic probabilities or mass Pr(s)=1/(P(q,M) q^K(s)), where K(s) in N_0 is the class of the state s, and P(q,M)=\sum_(K in\N0) P_M(K)q^(-K)=\prod_(i=1..M) q^i/(q^i-1) is the generating function of the number of partitions into at most M parts. We have (for each timestep modulo M+1) just P_M(K) states of class K \.   We obtain a closed formula for the asymptotic probability for the linear complexity deviation d(n) := L(n)-\lceil n\cdot M/(M+1)\rceil with Pr(d)=O(q^(-|d|(M+1))), for M in N, for d in Z. The precise formula is given in the text. It has been verified numerically for M=1..8, and is conjectured to hold for all M in N.   From the asymptotic growth (proven for all M in N), we infer the Law of the Logarithm for the linear complexity deviation, -liminf_{n\to\infty} d_a(n) / log n = 1 /((M+1)log q) = limsup_{n\to\infty} d_a(n) / log n, which immediately yields L_a(n)/n \to M/(M+1) with measure one, for all M in N, a result recently shown already by Niederreiter and Wang. Keywords: Linear complexity, linear complexity deviation, multisequence, Battery Discharge Model, isometry.<|reference_end|>
@article{vielhaber2006towards,
    title={Towards a General Theory of Simultaneous Diophantine Approximation of
  Formal Power Series: Multidimensional Linear Complexity},
    author={Michael Vielhaber, Monica del Pilar Canales},
    journal={arXiv preprint arXiv:cs/0607030},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607030},
    primaryClass={cs.IT math.IT}
}