{"id":1247,"date":"2018-10-21T11:35:55","date_gmt":"2018-10-21T14:35:55","guid":{"rendered":"http:\/\/infinis.org\/?p=1247"},"modified":"2019-04-15T13:48:44","modified_gmt":"2019-04-15T16:48:44","slug":"pablo-rotondo-defended-his-phd-thesis-september-2018","status":"publish","type":"post","link":"http:\/\/www.irp-sinfin.org\/?p=1247","title":{"rendered":"Pablo ROTONDO defended his PhD thesis, September 2018"},"content":{"rendered":"<p><strong><span class=\"lG\">Pablo<\/span>\u00a0<span class=\"lG\">ROTONDO<\/span><\/strong>\u00a0successfully defended his PhD thesis on September 27th, 2018, at Universit\u00e9 Paris-Diderot.<\/p>\n<p>Title: <strong>Probabilistic studies in Number Theory and Word Combinatorics: instances of dynamical analysis<\/strong><\/p>\n<p>Directors:<\/p>\n<ul>\n<li>Brigitte VALL\u00c9E, Universit\u00e9 de Caen, France<\/li>\n<li>Val\u00e9rie BERTH\u00c9, IRIF, Universit\u00e9 Paris-Diderot, France<\/li>\n<li>Alfredo VIOLA, Universidad de la Rep\u00fablica, Uruguay<\/li>\n<\/ul>\n<p>Evaluation committee:<\/p>\n<ul>\n<li>Bruno SALVY\u00a0 \u00a0 \u00a0(rapporteur)<\/li>\n<li>Pierre ARNOUX (rapporteur)<\/li>\n<li>Cyril NICAUD\u00a0 \u00a0 \u00a0(examiner)<\/li>\n<li>Franco ROBLEDO\u00a0 \u00a0 \u00a0(examiner)<\/li>\n<li>Thomas STOLL\u00a0 \u00a0 \u00a0(examiner)<\/li>\n<\/ul>\n<p><strong>Abstract.<\/strong><br \/>\nDynamical Analysis incorporates tools from dynamical systems, namely the\u00a0 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.<\/p>\n<p>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\u00a0 studied from a probabilistic perspective.\u00a0 \u00a0Here, we quantify the\u00a0 recurrence properties of\u00a0 a &#8220;random&#8221; Sturmian word,\u00a0 \u00a0 which\u00a0 are dictated by the so-called &#8220;recurrence function&#8221;;\u00a0 we perform a complete asymptotic probabilistic study of this function,\u00a0 quantifying its mean and describing\u00a0 its distribution\u00a0 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\u00a0 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.\u00a0 In this dissertation we also discuss our ongoing work regarding two special families of Sturmian words:\u00a0 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.<\/p>\n<p>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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Pablo\u00a0ROTONDO\u00a0successfully defended his PhD thesis on September 27th, 2018, at Universit\u00e9 Paris-Diderot. Title: Probabilistic studies in Number Theory and Word Combinatorics: instances of dynamical analysis Directors: Brigitte VALL\u00c9E, Universit\u00e9 de Caen, France Val\u00e9rie BERTH\u00c9, IRIF, Universit\u00e9 Paris-Diderot, France Alfredo VIOLA, Universidad de la Rep\u00fablica, Uruguay Evaluation committee: Bruno SALVY\u00a0 \u00a0 \u00a0(rapporteur) Pierre ARNOUX (rapporteur) Cyril &hellip; <a href=\"http:\/\/www.irp-sinfin.org\/?p=1247\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Pablo ROTONDO defended his PhD thesis, September 2018<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1247","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=\/wp\/v2\/posts\/1247","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1247"}],"version-history":[{"count":3,"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=\/wp\/v2\/posts\/1247\/revisions"}],"predecessor-version":[{"id":1254,"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=\/wp\/v2\/posts\/1247\/revisions\/1254"}],"wp:attachment":[{"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1247"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1247"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.irp-sinfin.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1247"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}