Month: October 2018

Patricia Olivella writes about Verónica Becher’s research during Oliver Carton’s visit, in the cover of Nexciencia:
http://nexciencia.exactas.uba.ar/secuencias-normales-azar-problemas-algoritmos-modelos-computacionales-veronica-becher

Mario Valencia Pabon will be in Argentina from December 3rd, to December 18th, 2018. The first week (from the 3rd to the 9th December), will be at Rosario, working with Pablo Torres. From the 10th to the 12th, will participate as invited speaker at the “IX Seminario de la Red Latinoamericana de Optimización Discreta y Grafos” (SODYG 2018), organised by Martin Safe (Universidad del Sur) at Bahía Blanca. Finally, from the 13th to the 18th, will be at Buenos Aires working with Flavia Bonomo, Luciano Grippo and Nina Pardal.

Alejandro Díaz-Caro from UNQ and ICC (CONICET-Universidad de Buenos Aires) will visit Gilles Dowek at LSV, ENS Paris-Cachan and Benoît Valiron at LRI, Université Paris-Sud, from the 1st to the 15th of December 2018.

Prof. Gérald Tenenbaum (Institut Élie Cartan, Faculté des Sciences, Université de Lorraine), recognised specialist in Analytic and Probabilistic Number Theory visits Exactas-UBA from the 13th to the 27th of November, 2018.

He will give two talks at the Mathematics Department:

• On arithmetical processes, on November 14.
• On probabilistic models in number theory, on November 15.

Organises: Verónica Becher.

Malena Ivnisky, a student at Universidad de Buenos Aires, visits Benoît Valiron from the 12th to the 24th of November 2018. Malena is working at UBA under the direction of Alejandro Díaz-Caro and Hernán Melgratti on the study of “semantics of a fixed point operator for a quantum lambda calculus with density matrices”.

Elisa Orduna presented joint work with Olivier Carton “Deciding preservation of normality for transducers” in GT ALGA Annual Meeting 2018, October 15-16, 2018 – Lille. More information here.

Elisa Orduna, a student at University of Buenos Aires, visits  IRIF  Université Paris Diderot during the month of October 2018, to work with Professor Olivier Carton on “Preservation of Normality in Transducers”.

Pablo ROTONDO successfully defended his PhD thesis on September 27th, 2018, at Université Paris-Diderot.

Title: Probabilistic studies in Number Theory and Word Combinatorics: instances of dynamical analysis

Directors:

• Brigitte VALLÉE, Université de Caen, France
• Valérie BERTHÉ, IRIF, Université Paris-Diderot, France
• Alfredo VIOLA, Universidad de la República, Uruguay

Evaluation committee:

• Bruno SALVY     (rapporteur)
• Pierre ARNOUX (rapporteur)
• Cyril NICAUD     (examiner)
• Franco ROBLEDO     (examiner)
• Thomas STOLL     (examiner)

Abstract.
Dynamical Analysis incorporates tools from dynamical systems, namely the  Transfer Operator, into the framework of Analytic Combinatorics, permitting the analysis of numerous algorithms and objects naturally associated with an underlying dynamical system. This dissertation presents, in the integrated framework of Dynamical Analysis, the probabilistic analysis of seemingly distinct problems in a unified way: the probabilistic study of the recurrence function of Sturmian words, and the probabilistic study of the Continued Logarithm algorithm.

Sturmian words are a fundamental family of words in Word Combinatorics. They are in a precise sense the simplest infinite words that are not eventually periodic. Sturmian words have been well studied over the years, notably by Morse and Hedlund (1940) who demonstrated that they present a notable number theoretical characterization as discrete codings of lines with irrational slope, relating them naturally to dynamical systems, in particular the Euclidean dynamical system. These words have never been  studied from a probabilistic perspective.   Here, we quantify the  recurrence properties of  a “random” Sturmian word,    which  are dictated by the so-called “recurrence function”;  we perform a complete asymptotic probabilistic study of this function,  quantifying its mean and describing  its distribution  under two different probabilistic models, which present different virtues: one is a naturaly choice from an algorithmic point of view (but is innovative from the point of view of dynamical analysis), while the other allows a natural quantification of the worst-case growth of the recurrence function. We discuss  the relation between these two distinct models and their respective techniques, explaining also how the two seemingly different techniques employed could be linked through the use of the Mellin transform.  In this dissertation we also discuss our ongoing work regarding two special families of Sturmian words:  those associated with a quadratic irrational slope, and those with a rational slope (not properly Sturmian). Our work seems to show the possibility of a unified study.

The Continued Logarithm Algorithm, introduced by Gosper in Hakmem (1978) as a mutation of classical continued fractions, computes the greatest common divisor of two natural numbers by performing division-like steps involving only binary shifts and substractions. Its worst-case performance was studied recently by Shallit (2016), who showed a precise upper-bound for the number of steps and gave a family of inputs attaining this bound. In this dissertation we employ dynamical analysis to study the average running time of the algorithm, giving precise mathematical constants for the asymptotics, as well as other parameters of interest. The underlying dynamical system is akin to the Euclidean one, and was first studied by Chan (around 2005) from an ergodic, but the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying this system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the algorithm by Dynamical Analysis.

Raúl Fervari (Universidad Nacional de Córdoba & CONICET) visits Stéphane Demri at LSV, ENS Paris-Cachan from August 31 to September 12, 2018. From this visit, a joint publication entitled “On the complexity of modal separation logics” has been issued.