UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

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

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. Gold open access

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