On maps between Hamming spaces that expand pairwise distances

We discuss interaction between metric and linear structures on a Hamming space (i.e. finite-dimensional vector space over field $GF(2)$ with Hamming metric). Namely, we consider linear maps between these spaces possessing the property that image of any heavy Hamming weight vector has itself a heavy weight. We prove an asymptotic upper-bound on the ratio of the dimensions of domain and co-domain. Our method builds upon an elegant idea of Tillich and Zemor (which we will review), as well as new results on harmonic analysis for the hypercube. More concretely, we show that a function whose energy is concentrated on a set of small size, and whose Fourier energy is concentrated on a small Hamming ball must be zero. This is a form of uncertainty principle for which we derive an asymptotically optimal tradeoff. In the course of the proof we establish a new log-Sobolev inequality and a new hypercontractivity result for functions on the hypercube with (exponentially) small support. Joint work with Alex Samorodnitsky (HUJI).