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

直線上の点の情報内容と $k$ -平面拡張

基本情報

論文ID: 2510.11645
タイトル: The information content of points on lines and $k$ -plane extensions
著者: Jacob B. Fiedler (ウィスコンシン大学マディソン校)
分類: math.CA (古典解析と常微分方程式)、math.LO (論理学)
発表日: 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)$ 言い換えれば、直線上からランダムに選択された点は、少なくともその直線の複雑度の半分に加えて、その第1座標の複雑度を持つ。著者はこの有効性結果を、 $k$ -平面の正測度部分集合の和集合が完全な $k$ -平面に置き換えられたときのハウスドルフ次元増加に関する古典的な界を確立するために適用している。

研究背景と動機

中心的問題：本研究が解決しようとしているのは、アルゴリズム情報論における幾何学的対象の複雑度関係に関する基本的な問題である。すなわち、直線上の点はその直線についてどれだけの情報を含むべきか、という問題である。
問題の重要性：
- 情報論的観点から、2点が1本の直線を決定するため、直線上の点は直線情報の一部を含むべきである
- 点から集合への原理(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$ -平面拡張のハウスドルフ次元界を証明した： $\dim_H(F) \leq 2\dim_H(E) - k$
技術的革新：代理点技術を修正・拡張し、異なる精度における複雑度の不均一な分布を処理した
理論的洞察：アルゴリズム情報論の枠組みの下で、幾何学的対象とその構成要素の間の情報関係を初めて定量的に特性化した

方法の詳細

タスク定義

入力：

集合 $A \subseteq \mathbb{N}$ （オラクルとして）
$\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$ が大きな基数を持つことを証明する
- 補題5を適用する（Cholakら由来の組合補題）
- 特定の複雑度条件を満たす代理対 $(u,v)$ を見つける
矛盾の導出：
- 一方では： $l(u)$ と $l(v)$ の複雑度は低い（仮定による）
- 他方では：それらが決定する直線 $l$ は高い複雑度を持つ
- 情報対称性を利用して矛盾を得る

技術的革新点

代理点技術の拡張：4の原始的な技術と比較して、本論文では代理対 $(u,v)$ が $\ell$ と無関係な大量の情報も決定することを要求し、これが追加の「+r」項をもたらす
精度制御：パラメータ $t = \frac{\varepsilon r}{2n}$ を導入することで、異なる精度における複雑度関係を正確に制御する
計算可枚挙性の利用：関連する集合の計算可枚挙性を巧妙に利用して複雑度下界を確立する