Dumas, P; Lipmaa, H; Wallén, J; (2007) Asymptotic Behaviour of A Non-Commutative Rational Series With a Nonnegative Linear Representation. **Discrete Mathematics and Theoretical Computer Science** , 9 (1) 247 - 274.

## Abstract

We analyse the asymptotic behaviour in the mean of a non-commutative rational series, which originates from differential cryptanalysis, using elementary tools from analysis and linear algebra, and more sophisticated tools from analytic number theory. We show that a probability distribution function describes the asymptotic behaviour of the rational series according to the length of words. As a result, the non-classical rational sequence, obtained by interpreting this rational series via the octal numeration system, admits an oscillating asymptotic behaviour for its first-order summation function. The distribution function and the periodic function are differentiable almost everywhere and not differentiable on an everywhere dense set. We compute the moments of the distribution function using a functional equation, which brings to light a self-similarity phenomenon, and we derive a Fourier representation of the periodic function using a Dirichlet series with vector coefficients. The method is applicable to a wide class of sequences rational with respect to a numeration system essentially under the condition that they admit a linear representation with nonnegative coefficients.

Type: | Article |
---|---|

Title: | Asymptotic Behaviour of A Non-Commutative Rational Series With a Nonnegative Linear Representation |

Open access status: | An open access publication |

Publisher version: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs |

Keywords: | rational series, rational sequence, numeration system, self-similarity, asymptotics |

UCL classification: | UCL > School of BEAMS > Faculty of Engineering Science > Adastral Park |

Archive Staff Only: edit this record