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