Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
复制标题
算法信息、平面挂屋集和条件维度
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Neil Lutz
中科院分区：
文献类型：
--
作者：
J. H. Lutz;Neil Lutz
我们以精度r公式化给定y的x的条件柯尔莫戈洛夫复杂度，其中x和y是欧几里得空间中的点，r是自然数。我们从两个方面证明了这个概念的实用性：（1）我们证明了一个点到集原理，它使人们能够使用欧几里得空间中集合E中单个点的（相对化的，建设性的）维数来建立E的（经典的）Hausdorff维数的下界。然后，我们使用这一原则，连同条件柯尔莫哥洛夫复杂性在欧几里得空间，给一个新的证明已知的，二维情况下的挂谷猜想。这个定理的几何措施理论，证明了戴维斯在1971年，说，每一个平面集包含一个单位线段在每一个方向有豪斯多夫维数2。(2)We在欧几里得空间中使用条件柯尔莫哥洛夫复杂度来开发下和上条件维数dim（x| y）和Dim（x| y），其中x和y是欧几里得空间中的点。直观地说，这些是以y中的信息为条件的x的上、下渐近算法信息密度。我们证明了这些条件维数是鲁棒的，并且它们与已研究的维数dim（x）和Dim（x）以及互维数mdim（x：y）和Mdim（x：y）具有正确的信息论关系。
We formulate the conditional Kolmogorov complexity of x given y at precision r, where x and y are points in Euclidean spaces and r is a natural number. We demonstrate the utility of this notion in two ways; (1) We prove a point-to-set principle that enables one to use the (relativized, constructive) dimension of a single point in a set E in a Euclidean space to establish a lower bound on the (classical) Hausdorff dimension of E. We then use this principle, together with conditional Kolmogorov complexity in Euclidean spaces, to give a new proof of the known, two-dimensional case of the Kakeya conjecture. This theorem of geometric measure theory, proved by Davies in 1971, says that every plane set containing a unit line segment in every direction has Hausdorff dimension 2. (2)We use conditional Kolmogorov complexity in Euclidean spaces to develop the lower and upper conditional dimensions dim(x|y) and Dim(x|y) of x given y, where x and y are points in Euclidean spaces. Intuitively, these are the lower and upper asymptotic algorithmic information densities of x conditioned on the information in y. We prove that these conditional dimensions are robust and that they have the correct information-theoretic relationships with the well-studied dimensions dim(x) and Dim(x) and the mutual dimensions mdim(x : y) and Mdim(x : y).