## Asymptotic Behaviour of A Non-Commutative Rational Series With a Nonnegative Linear Representation

Philippe Dumas, Helger Lipmaa and Johan Wallén. Asymptotic Behaviour of A Non-Commutative Rational Series With a Nonnegative Linear Representation. Discrete Mathematics and Theoretical Computer Science, 9 (1):247--274, October 2007.

File: [.pdf (2093 KB)] pdf recommended.

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..

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

Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.