A new proof technique shows distances and orthogonal projections retain at least half of a planar point's Kolmogorov complexity, improving pinned distance dimension bounds to 3/4 s and generalizing Bourgain's theorem.
Distance sets bounds for polyhedral norms via effective dimension
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove that, for every norm on $\mathbb{R}^d$ and every $E \subseteq \mathbb{R}^d$, the Hausdorff dimension of the distance set of $E$ with respect to that norm is at least $\dim_{\mathrm{H}} E - (d-1)$. An explicit construction follows, demonstrating that this bound is sharp for every polyhedral norm on $\mathbb{R}^d$. The techniques of algorithmic complexity theory underlie both the computations and the construction.
citation-role summary
background 1
citation-polarity summary
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
Algorithmic Information Bounds for Distances and Orthogonal Projections
A new proof technique shows distances and orthogonal projections retain at least half of a planar point's Kolmogorov complexity, improving pinned distance dimension bounds to 3/4 s and generalizing Bourgain's theorem.