Аннотация:
Алгоритм Евклида оказал огромное влияние на развитие математики. В частности, на его основе был создан аппарат цепных дробей – один из важнейших инструментов в теории чисел и других областях математики. Одной из важнейших характеристик алгоритма Евклида является количество шагов в нем $l(a,d)$. На языке цепных дробей это эквивалентно вопросу: какова длина цепной дроби для рационального числа $a/d$. Для конкретной пары $(a,d)$ величина $l(a,d)$ может принимать значения от единицы до $O(\log d)$.
Со статистической точки зрения большой интерес представляет изучение среднего значения $l(a,d)$ по всем $a$ от $1$ до $d$. В 1969 г. Х. Хейльбронном для данного среднего была доказана асимптотическая формула с логарифмическим понижением в остаточном члене. Позднее, в 1975 г. с помощью оценок Вейля сумм Клостермана Дж. Портер доказал асимптотическую формулу со степенным понижением в остаточном члене, которая была улучшена А. В. Устиновым в 2008 г. на некоторую степень логарифмического множителя.
В докладе будет рассказано как об основных идеях и методах из работ Хейльбронна–Портера–Устинова, так и об нововведениях, позволивших существенно улучшить результат Портера.
Данный доклад основан на совместной статье с В. А. Быковским.
Обратная связь: