Bias in the number of steps in the Euclidean algorithm and a conjecture of Ito on Dedekind sums

Abstract

We investigate the number of steps taken by three variants of the Euclidean algorithm on average over Farey fractions. We show asymptotic formulae for these averages restricted to the interval (0, 1/2), establishing that they behave differently on (0, 1/2) than they do on (1/2, 1). These results are tightly linked with the distribution of lengths of certain continued fraction expansions as well as the distribution of the involved partial quotients. As an application, we prove a conjecture of Ito on the distribution of values of Dedekind sums. The main argument is based on earlier work of Zhabitskaya, Ustinov, Bykovskiĭ and others, ultimately dating back to Lochs and Heilbronn, relating the quantities in question to counting solutions to a certain system of Diophantine inequalities. The above restriction to only half of the Farey fractions introduces additional complications.

Keywords: 11J25; 11K50; Primary 11A55; Secondary 11F20.

Fig. 1

The number of steps of ${\mathrm{EA}}^{(\mathrm{sub})}$, ${\mathrm{EA}}^{(\mathrm{div})}$ & ${\mathrm{EA}}_{(\text{by-excess})}^{(\mathrm{div})}$ when applied to all reduced $a/b\in [0,1)\cap \mathbb{Q}$ with $1\le b\le 100$

Fig. 2

Plot of ${\Sigma }_{\pm }(a/b)$ when applied to all Farey fractions $a/b\in [0,1]\cap \mathbb{Q}$ with $1\le b\le 100$. Note that the average of the plotted values over the interval [0, 1/2) is clearly positive, whereas the average of the plotted values over the interval [1/2, 1) is negative