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

在数学的许多领域，对数值进行估计是有用的。在数学分析中，这可能是描述集合大小的维数的概念。在遍历理论和动力系统的背景下，这包括，例如，李雅普诺夫指数，其测量典型的附近轨道如何随着系统的演变而分离。在双曲群上的随机游动（在一维中推广了著名的“酒鬼漫步”）中，它是一个相关测度的维数（测量测度的“扩展”程度）。虽然这些值在每一个这些设置中提供定性信息，但当我们需要精确了解其值时，会有特别有趣的应用。也就是说，我们需要知道它们的值确实满足一些不等式，这有两个因素。第一，有一个方法来近似的数字，这是高效和准确的。其次，这个结果是有效的-在某种程度上，我们可以完全相信这些结果来自基础的抽象数学。在这里强调的是少的问题上的计算和更多的发展一个有效的算法，并作出连接的应用。使用明确的数值估计和他们令人惊讶的应用其他领域的数学是说明了密度一Zaremba定理的领域奖章获得者布尔甘和Kontorovich在数论。通过欧几里德算法，已知任何有理数p/q都可以写成有限连分数，即，存在自然数a_1，...，a_n，p/q = 1/（a_1+1/（a_2+...））。Bourgain和Kontorovich证明，对于典型的q，存在p和a_1，...，a_n取1，2，3，4或5之一，p/q = 1/（a_1+1/（a_2+...））。这主要取决于单位区间中的某个相关联的康托集具有大于5/6的维度。

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.