## Lower Bounds for Arithmetical Problems

**Lecturer:**
Prof. Yiannis N. Moschovakis
(University of California, Los Angeles).

About the lecturer | Course Summary | Lecture notes including the assignment

**About the lecturer:**
Yiannis Moschovakis has Bachelor's and Master's degrees from the
Massachusetts Institute of Technology (1960) and a Ph.D. from the
University of Wisconsin (1963), under the direction of Steven
Kleene. He has taught in the Mathematics Department of the
University of California, Los Angeles (UCLA) since 1964, and also
at the University of Athens from 1996 until 2005. He has worked
in various parts of definability and recursion theory,
including recursive analysis, recursion in higher types,
inductive definability and (especially, for many years)
descriptive set theory. More recently, he has worked in the
foundations of the theory of algorithms, has applied ideas from
recursive definability to philosophical logic and linguistics,
and (with Lou van den Dries) has obtained complexity lower bounds
in arithmetic.

**Course summary:**
The euclidean algorithm computes the * greatest common divisor*
of two natural numbers using only the division operation, and
can be described succinctly by the *recursive equation*

where the

*remainder*rem(x,y) is the unique r < y such that for some q, x = yq+r. It easy to show that if c(x,y) is the number of divisions required to compute gcd(x,y) by the euclidean, then

where the logarithms are taken in base 2. The converse is open:

*Main Conjecture.*The euclidean is optimal in the following sense: For any algorithm

**a**which computes gcd(x,y) using only divisions, if

**c**(x,y) is the number of divisions required by

**a**to compute gcd(x,y), then there is a rational r > 0 such that

**c**(x,y) > r log y.

The two aims of this minicourse are:

(1) To introduce the appropriate (logical) notions so that claims of

*absolute lower bounds*like the Main Conjecture (which apply to

*all algorithms*) can be made precise.

(2) To establish absolute lower bounds for several arithmetical problems, including a weak version of the Main Conjecture (with log log in place of log).

Equal emphasis will be placed on (1), which involves primarily logic and a bit of algebra, and (2) which involves primarily a little number theory (which will be covered). Lecture notes including the assignment

Please send the solutions to professor Moschovakis (ynm AT math DOT ucla DOT edu) by November 23.