论文标题
欧几里得算法中的步骤数量和iTo的猜想偏差
Bias in the number of steps in the Euclidean algorithm and a conjecture of Ito on Dedekind sums
论文作者
论文摘要
我们调查了欧几里得算法的三种变体所采取的步骤数量，平均而言是Farey分数。我们显示这些平均值的渐近公式仅限于间隔$（0,1/2）$，证明它们对$（0,1/2）$的行为与$（1/2,1）$不同。这些结果与某些持续分数扩展的长度的分布以及所涉及的部分商的分布紧密相关。 作为一个应用程序，我们证明了ITO的猜想是关于Dedekind总和的值的分布。 主要论点是基于Zhabitskaya，Ustinov，Bykovskiĭ和其他人的早期工作，最终可以追溯到Heilbronn，将所讨论的数量与将解决方案计算到某种养分剂不平等系统中。上述仅对Farey部分的一半限制引入了其他并发症。
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 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.
