Algorithmic Information Bounds for Distances and Orthogonal Projections
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912573399498752 |
|---|---|
| author | Cholak, Peter Csörnyei, Marianna Lutz, Neil Lutz, Patrick Mayordomo, Elvira Stull, D. M. |
| author_facet | Cholak, Peter Csörnyei, Marianna Lutz, Neil Lutz, Patrick Mayordomo, Elvira Stull, D. M. |
| contents | We develop quantitative algorithmic information bounds for orthogonal projections and distances in the plane. Under mild independence conditions, the distance $|x-y|$ and a projection coordinate $p_e x$ each retain at least half the algorithmic information content of $x$ in the sense of finite-precision Kolmogorov complexity, up to lower-order terms. Our bounds support conditioning on coarser approximations, enabling case analyses across precision scales. The proofs introduce a surrogate point selection step. Via the point-to-set principle we derive a new bound on the Hausdorff dimension of pinned distance sets, showing that every analytic set $E\subseteq\mathbb{R}^2$ with $\dim_H(E)\leq 1$ satisfies
\[\sup_{x\in E}\dim_H(Δ_x E)\geq \frac{3}{4}\dim_H(E).\]
We also extend Bourgain's theorem on exceptional sets for orthogonal projections to all sets that admit optimal Hausdorff oracles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05211 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithmic Information Bounds for Distances and Orthogonal Projections Cholak, Peter Csörnyei, Marianna Lutz, Neil Lutz, Patrick Mayordomo, Elvira Stull, D. M. Computational Complexity Classical Analysis and ODEs We develop quantitative algorithmic information bounds for orthogonal projections and distances in the plane. Under mild independence conditions, the distance $|x-y|$ and a projection coordinate $p_e x$ each retain at least half the algorithmic information content of $x$ in the sense of finite-precision Kolmogorov complexity, up to lower-order terms. Our bounds support conditioning on coarser approximations, enabling case analyses across precision scales. The proofs introduce a surrogate point selection step. Via the point-to-set principle we derive a new bound on the Hausdorff dimension of pinned distance sets, showing that every analytic set $E\subseteq\mathbb{R}^2$ with $\dim_H(E)\leq 1$ satisfies \[\sup_{x\in E}\dim_H(Δ_x E)\geq \frac{3}{4}\dim_H(E).\] We also extend Bourgain's theorem on exceptional sets for orthogonal projections to all sets that admit optimal Hausdorff oracles. |
| title | Algorithmic Information Bounds for Distances and Orthogonal Projections |
| topic | Computational Complexity Classical Analysis and ODEs |
| url | https://arxiv.org/abs/2509.05211 |