Two Arithmetical Sources and Their AssociatedTries

VALÉRIE BERTHÉ; EDA CESARATTO; FRÉDÉRIC PACCAUT; PABLO ROTONDO; MARTÍN D. SAFE; BRIGITTE VALLÉE

Conferencia; 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020); 2020

This article is devoted to the study of two arithmetical sources associated with classical partitions,that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominatoris ?not too large?. Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how theyinfluence the behaviour of tries built on words they emit, and we notably focus on the trie depth.The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, thatare usually used and studied in the case of good sources with positive entropy. To the best ofour knowledge, the present study is the first one where these powerful methods are applied to azero-entropy context. In our context, the generating function associated with each source is explicitand related to classical functions in Number Theory, as theζfunction, the doubleζfunction orthe transfer operator associated with the Gauss map. We obtain precise asymptotic estimates forthe mean value of the trie depth that prove moreover to be quite different for each source. Then,these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.