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