Validated numerics for Iterated Function Schemes, Dynamical Systems and Random Walks

点击翻译按钮获取中文摘要

In many areas of mathematics its is useful to have estimates for numerical values. In mathematical analysis this may be the notion of dimension which describes the size of sets. In the context of Ergodic Theory and dynamical systems this includes, for example, the Lyapunov exponents which measure how typical nearby orbits separate as the system evolves. In the setting of random walks on hyperbolic groups (generalizing the famous "drunkard's walk" in one dimension) it is the dimension of an associated measure (which measures how "spread out" the measure is). Whereas these values give qualitative information in each of these settings, there are particularly interesting applications when we require a precise knowledge of their values. That is, we need to know their values really do satisfy some inequality and this has two ingredients. Firstly, having a method to approximate the number which is efficient and accurate. Secondly, this result is validated - to the extent that we can have complete confidence in these results that comes from the underpinning abstract mathematics. Here the emphasis is less on the problem of computation and more on the development of an efficient algorithm and making the connection with the applications.The use of explicit numerical estimates and their surprising applications other areas of mathematics is illustrated by the density one Zaremba theorem of Fields medallist Bourgain and Kontorovich in number theory. By the Euclidan algorithm it is known that any rational number p/q can be written as a finite continued fraction, i.e., there exist natural numbers a_1, ..., a_n with p/q = 1/(a_1+1/(a_2+...)). Bourgain and Kontorovich showed that for typical q there exists a p and a_1, ..., a_n taking one of the values 1,2,3,4 or 5, with p/q = 1/(a_1+1/(a_2+...)). This crucially depends on a certain associated Cantor set in the unit interval having dimension greater than 5/6.