2025-11-22T04:16:19.790938

The information content of points on lines and $k$-plane extensions

Fiedler

We prove a new lower bound on the algorithmic information content of points lying on a line in $\mathbb{R}^n$. More precisely, we show that a typical point $z$ on any line $\ell$ satisfies \begin{equation*} K_r(z)\geq \frac{K_r(\ell)}{2} + r - o(r) \end{equation*} at every precision $r$. In other words, a randomly chosen point on a line has (at least) half of the complexity of the line plus the complexity of its first coordinate. We apply this effective result to establish a classical bound on how much the Hausdorff dimension of a union of positive measure subsets of $k$-planes can increase when each subset is replaced with the entire $k$-plane. To prove the complexity bound, we modify a recent idea of Cholak-CsÃ¶rnyei-Lutz-Lutz-Mayordomo-Stull.

academic

The information content of points on lines and $k$ -plane extensions

基本信息

论文ID: 2510.11645
标题: The information content of points on lines and $k$ -plane extensions
作者: Jacob B. Fiedler (University of Wisconsin-Madison)
分类: math.CA (Classical Analysis and ODEs), math.LO (Logic)
发表时间: 2025年10月13日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.11645

摘要

本文证明了关于 $\mathbb{R}^n$ 中直线上点的算法信息含量的新下界。具体地，作者证明了任意直线 $\ell$ 上的典型点 $z$ 在每个精度 $r$ 下都满足： $K_r(z) \geq \frac{K_r(\ell)}{2} + r - o(r)$ 换言之，直线上随机选择的点至少具有该直线复杂度的一半加上其第一坐标的复杂度。作者将这一有效性结果应用于建立关于 $k$ -平面正测度子集的并集在被替换为整个 $k$ -平面时其Hausdorff维数增长上界的经典界。

研究背景与动机

核心问题：该研究要解决的是算法信息论中关于几何对象复杂度关系的基本问题——直线上的点应该包含多少关于该直线的信息？
问题重要性：
- 从信息论角度，两点确定一条直线，因此直线上的点理应包含直线信息的一部分
- 通过点到集合原理(point-to-set principle)，这种复杂度界可以转化为几何测度论中的经典问题
- 连接了算法信息论与分形几何学的深层关系
现有方法局限性：
- 虽然通过原点的随机方向直线具有很高复杂度，但其上存在非常简单的点
- 缺乏对典型点复杂度的定量刻画
- 传统方法难以处理复杂度在不同精度下的分布不均问题
研究动机：
- 建立直线复杂度与其上点复杂度之间的定量关系
- 将算法信息论的工具应用于几何测度论的经典问题
- 扩展Cholak-Csörnyei-Lutz-Lutz-Mayordomo-Stull的代理点技术

核心贡献

主要算法结果：证明了定理1，建立了直线上典型点复杂度的新下界 $K_r(z) \geq \frac{K_r(\ell)}{2} + r - o(r)$
几何应用：利用算法结果证明了 $k$ -平面扩展的Hausdorff维数界： $\dim_H(F) \leq 2\dim_H(E) - k$
技术创新：修改并扩展了代理点技术，处理了复杂度在不同精度下分布不均的问题
理论洞察：首次在算法信息论框架下定量刻画了几何对象与其组成部分之间的信息关系

方法详解

任务定义

输入：

集合 $A \subseteq \mathbb{N}$ （作为oracle）
$\mathbb{R}^n$ 中的直线 $\ell$
实数 $s \in \mathbb{R}$ （相对于 $A$ 是随机的）

输出：点 $\ell(s)$ 的复杂度下界

约束条件：

$s$ 相对于 $A$ 是随机的
$K^A_r(\ell|s) \geq K^A_r(\ell) - O(\log r)$

核心定理架构

定理1（主要算法结果）

设 $A \subseteq \mathbb{N}$ ， $\ell$ 为 $\mathbb{R}^n$ 中的直线， $s \in \mathbb{R}$ 。假设 $s$ 相对于 $A$ 随机且 $K^A_r(\ell|s) \geq K^A_r(\ell) - O(\log r)$ 则 $K^A_r(\ell(s)) \geq \frac{K^A_r(\ell)}{2} + r - o(r)$

定理2（几何应用）

设 $E \subseteq \mathbb{R}^n$ ， $F$ 为 $E$ 与所有与 $E$ 有正测度交集的 $k$ -平面的并集。则要么 $E = F$ ，要么 $\dim_H(F) \leq 2\dim_H(E) - k$

证明策略

定理2的证明思路

点到集合原理应用：利用有效维数的点到集合原理，将问题转化为单点复杂度估计
径向切片论证：通过Fubini定理选择具有正测度交集的直线
复杂度传递：利用对称信息原理和定理1建立复杂度界

定理1的证明核心技术

代理点技术的应用：

问题设定：假设结论不成立，即存在 $\ell$ 和 $s$ 使得 $K^A_r(\ell(s)) < \frac{K^A_r(\ell)}{2} + r - \varepsilon r$
关键集合定义：
- $L = \{d \in D(A(n,1), r) \cap B_1(\ell_x) : K^A(d) \leq K_r(\ell) + C_1\log r\}$
- $N_v = \{d \in L : K^A_r(d(v)) < \frac{K^A_r(\ell)}{2} + r - \varepsilon r + C_5\log r\}$
组合论证：
- 证明"许多" $N_v$ 具有大基数
- 应用Lemma 5（来自Cholak等人的组合引理）
- 找到代理对 $(u,v)$ 满足特定复杂度条件
矛盾推导：
- 一方面： $l(u)$ 和 $l(v)$ 的复杂度较低（由假设）
- 另一方面：它们确定的直线 $l$ 具有高复杂度
- 利用信息对称性得到矛盾