Mapping $n$ grid points onto a square forces an arbitrarily large Lipschitz constant

Abstract

We prove that the regular $n\times n$ square grid of points in the integer lattice ${\mathbb{Z}}^2$ cannot be recovered from an arbitrary $n^2$-element subset of ${\mathbb{Z}}^2$ via a mapping with prescribed Lipschitz constant (independent of $n$). This answers negatively a question of Feige from 2002. Our resolution of Feige's question takes place largely in a continuous setting and is based on some new results for Lipschitz mappings falling into two broad areas of interest, which we study independently. Firstly the present work contains a detailed investigation of Lipschitz regular mappings on Euclidean spaces, with emphasis on their bilipschitz decomposability in a sense comparable to that of the well known result of Jones. Secondly, we build on work of Burago and Kleiner and McMullen on non-realisable densities. We verify the existence, and further prevalence, of strongly non-realisable densities inside spaces of continuous functions.

60 pages (43 pages of the main part, 13 pages of appendices), 10 figures. This is a revised version according to referees' comments. Our version of the proof of the theorem about bilipschitz decomposition of Lipschitz regular mappings was greatly simplified. To appear in GAFA

References in corpus (1)

• Some examples of non-rectifiable, repetitive Delone sets

Cited by in corpus (3)

• Divergence of separated nets with respect to displacement equivalence
• Lipschitz constant $\log n$ almost surely suffices for mapping $n$ grid points onto a cube
• Highly irregular separated nets