Nonembeddability theorems via Fourier analysis (Q2491108)

This interesting paper contains various new nonembeddability results proved by means of Fourier analysis. Let \(X\) and \(Y\) be metric spaces and \(f: X \rightarrow Y\) be one-to-one. The distortion of \(f\) is defined as \(\text{dist}(f)=\| f\| _{\text{Lip}} \cdot \| f^{-1}\| _{\text{Lip}},\) where \(f^{-1}: f(X) \rightarrow Y.\) Let us denote by \(c_{Y}(X)\) the infimum of \(\text{dist}(f)\) over all one-to-one mappings \(f: X \rightarrow Y.\) Hence \(c_{Y}(X)\) measures how well the metric structure of \(X\) can be embedded into \(Y.\) For applications (many of them explained in the paper) it is often necessary to estimate \(c_{p}(X):=c_{L_{p}}(X),\) the most important cases being \(p=1\) and \(p=2.\) The authors achieve significant progress in obtaining highly non-trivial \(c_{1}\) bounds. First, the authors deal with the discrete cube \(\{ 0,1 \}^{d}\) equipped with the Hamming's metric, i.e., \(\rho(x,y)=\sum_{i=1}^{d} | x_{i}-y_{i}| .\) They treat it as a linear space \({\mathbb F}_{2}^{d}\) over a finite field \({\mathbb F}_{2}=\{ 0,1\}.\) Let \(C \subseteq {\mathbb F}_{2}^{d}\) be a code, i.e., a linear subspace of \({\mathbb F}_{2}^{d}.\) Using some tools from coding theory combined with a discrete Fourier analytic approach the authors prove that there exist arbitrarily large finite metric spaces \(X\) for which \(c_{1}(X)=\Omega(\log | X| )\) -- namely, they prove this lower bound for the quotient space (with metric induced by the Hausdorff distance) \(X={\mathbb F}_{2}^{d}/C_{d}\) for some suitably chosen code \(C_{d}.\) Then the result is used to prove that the set of all probability measures on \({\mathbb F}_{2}^{d}\) equipped with the optimal transportation cost (Earthmover) distance also does not embed well into \(L_{1}.\) The next refinement deals with nonembeddability of \({\mathbb F}_{2}^{d}/G,\) where \(G\) is a transitive permutation group acting on \({\mathbb F}_{2}^{d}\) via permutations of the coordinates. Another theorem proved in the paper states that \[ c_{1}({\mathbb F}_{2}^{d}, ED) \geq \sqrt{\log d} \cdot 2^{-O(\sqrt{\log \log d \cdot \log \log \log d})}, \] where \(ED\) denotes the so-called Edit (or Levenstein) distance on \({\mathbb F}_{2}^{d}.\) The authors provide also examples of lattices \(\Lambda_{n} \subseteq {\mathbb R}^{n}\) of rank \(n\) such that the flat tori \({\mathbb R}^{n}/\Lambda_{n}\) satisfy \(c_{1}({\mathbb R}^{n}/\Lambda_{n})=\Omega(\sqrt{n}).\) Here the proof is based on Fourier analysis over \({\mathbb R}^{n}.\) The paper contains detailed references.