Wednesday, September 6
Milner 317, 12:30 PM
Title: How many steps are needed to execute the Euclidean algorithm?
Abstract: The Euclidean algorithm, executed on integer
inputs $(a,b)$ both less than $N$, runs to completion in at most $C
\log N$ steps. This much has long been known.
During the 20th century, it was proved first that the average
number of steps is asymptotic to $(12\log 2/\pi^2)\log N$, then that
the number of steps is almost always close to that, and then that it
has an approximately Gaussian distribution about that average value,
with a variance of roughly $C\log N$. Early in this century, V. Baladi
and B. Vall\'ee established a far-reaching generalization of
this, treating various `costs' in addition to the classical case which
prices each quotient and remainder procedure at 1, and obtaining
best-possible bounds for how tightly the actual distribution fits the
approximating Gaussian distribution. The methods are in the spirit of
what was done to prove the prime number theorem, but in place of the
Riemann zeta function which takes as input a complex number $s$ and
returns another complex number, one inputs a complex number $s$
and what is returned is a linear operator acting on a certain Banach
space; the leading eigenvalue of this operator is crucial to the story.