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

gcd(x,y) = if (rem(x,y)=0) then y else gcd(y,rem(x,y))     (x >= y > 0),

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

for all x >=y>=2,     c(x,y)<=2 log y

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

for infinitely many y and suitable x > y,     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.