Distance Sets Bounds for Polyhedral Norms via Effective Dimension

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_{\rm 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.