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

Abstract: We prove that the regular

n i m e s n

square grid of points in the integer lattice

m a t h b b Z^{2}

cannot be recovered from an arbitrary

n^{2}

-element subset of

m a t h b b 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.

Review text

The authors answer negatively the following open question by U. Feige: Is there a constant \(L>0\) such that for every \(n\in\mathbb{N}\) and every set \(S\subset\mathbb{Z}^2\) with cardinality \(|S|=n^2\) there is a bijection \(f:S\to\{1,2,\dots,n\}^2\) with Lipschitz constant \(\text{Lip}(f)\leq L\)? The solution of the problem takes place largely in a continuous setting and is based on some new results for Lipschitz mappings falling into two broad areas of interest, studied independently. Firstly, they present detailed investigation on Lipschitz regular mappings on Euclidean spaces, with emphasis on their bi-Lipschitz decomposability. Secondly, they build on work of \textit{D. Burago} and \textit{B. Kleiner} [Geom. Funct. Anal. 8, No. 2, 273--282 (1998; Zbl 0902.26004)], as well as \textit{C. T. McMullen} [Geom. Funct. Anal. 8, No. 2, 304--314 (1998; Zbl 0941.37030)] on non-realisable densities. The results and proofs are too involved to be presented here.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Mapping \(n\) grid points onto a square forces an arbitrarily large Lipschitz constant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724264)