Distance sets bounds for polyhedral norms via effective dimension

Abstract: We prove that, for every norm on

m a t h b b R^{d}

and every

E s u b s e t e q m a t h b b R^{d}

, the Hausdorff dimension of the distance set of

E

with respect to that norm is at least

d i m_{m a t h r m H} E - (d - 1)

. An explicit construction follows, demonstrating that this bound is sharp for every polyhedral norm on

m a t h b b R^{d}

. The techniques of algorithmic complexity theory underlie both the computations and the construction.

This page was built for publication: Distance sets bounds for polyhedral norms via effective dimension