Can the Hamming metric live inside a Hilbert space?

-
Cosmas Kravaris, Princeton University
Fine Hall 314

No, not really. The Hamming cube of dimension n is the set of all 0-1 strings of length n. It is a metric space, where the distance of two strings is the number of bit locations they differ. Can we embed the Hamming cube isometrically into a Hilbert space? No. If we embed the Hamming cube into a Hilbert space, how low can we make the multiplicative distortion of the metric? (i.e. the Lipschitz constant divided by the Lipschitz constant of the inverse) We show the distortion is always at least the square root of n, which is sharp. The proof follows from a "diagonals vs edges" geometric inequality of Enflo which we prove via baby Fourier analysis on the Hamming cube.