Jack Lutz (Iowa State University):
Randomness and Dimension
The two most important notions of fractal dimension are Hausdorff dimension
developed by Hausdorff (1919), and packing dimension
developed independently by Tricot (1982) and Sullivan (1984).
Both dimensions have the mathematical advantage of being defined from measures, and
both have yielded extensive applications in fractal geometry and dynamical systems.
In 2000, the speaker proved a simple characterization of
Hausdorff dimension in terms of gales, which are betting strategies that
generalize martingales. Imposing various computability and complexity
constraints on these gales produces a spectrum of effective versions of Hausdorff dimension,
including constructive, computable, polynomial- space,
polynomial-time, and finite-state dimensions. Work by several investigators has
already used these effective dimensions to shed light on a variety of
topics in theoretical computer science, including algorithmic information theory,
computational complexity, prediction, and data compression.
Constructive dimension has also been discretized, assigning a dimension dim(x)
to each finite, binary string x in a way that arises naturally from
Hausdorff and constructive dimensions and gives the unexpected characterization
K(x) = |x|*dim(x) +/- O(1) of Kolmogorov complexity. Very recent
work by Athreya, Hitchcock, Mayordomo and the speaker shows that packing dimension --
previously thought to be much more complex than
Hausdorff dimension -- admits a gale characterization that is an exact dual of that of
Hausdorff dimension. This characterization leads to a spectrum
of effective strong dimensions that are dual to the above effective dimensions and have a growing variety of applications. This talk surveys these
developments, with particular attention to the dimensions and strong dimensions of random objects. No prior knowledge of fractal dimensions will be
assumed.