On Lipschitz extension from finite subsets

Lipschitz (Hölder) classes (26A16) Geometric embeddings of metric spaces (30L05) Theorems of Hahn-Banach type; extension and lifting of functionals and operators (46A22) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Extension of maps (54C20)

Abstract: We prove that for every

n i n m a t h b b N

there exists a metric space

(X, d_{X})

, an

n

-point subset

S s u b s e t e q X

, a Banach space

(Z, | c d o t |_{Z})

and a

1

-Lipschitz function

f : S o Z

such that the Lipschitz constant of every function

F : X o Z

that extends

f

is at least a constant multiple of

s q r t l o g n

. This improves a bound of Johnson and Lindenstrauss. We also obtain the following quantitative counterpart to a classical extension theorem of Minty. For every

a l p h a i n (1 / 2, 1]

and

n i n m a t h b b N

there exists a metric space

(X, d_{X})

, an

n

-point subset

S s u b s e t e q X

and a function

f : S o e l l_{2}

that is

a l p h a

-H"older with constant

1

, yet the

a l p h a

-H"older constant of any

F : X o e l l_{2}

that extends

f

satisfies

|F|_{mathrm{Lip}(alpha)}gtrsim (log n)^{frac{2alpha-1}{4alpha}}+left(frac{log n}{loglog n} ight)^{alpha^2-frac12}.

We formulate a conjecture whose positive solution would strengthen Ball's nonlinear Maurey extension theorem, serving as a far-reaching nonlinear version of a theorem of K"onig, Retherford and Tomczak-Jaegermann. We explain how this conjecture would imply as special cases answers to longstanding open questions of Johnson and Lindenstrauss and Kalton.

Review text

The paper contains two main results. The first main result is the estimate \(\mathfrak{ae}(n)\geq c\sqrt{\log n}\) (\(c>0\) is an absolute constant), where \(\mathfrak{ae}(n)\) is the absolute extendability constant. This improves the previous estimate \(\mathfrak{ae}(n)\geq c\sqrt{\log n/\log\log n}\) of \textit{W. B. Johnson} and \textit{J. Lindenstrauss} [Contemp. Math. 26, 189--206 (1984; Zbl 0539.46017)]. Without the \(\mathfrak{ae}\) notation, the result can be stated as: ``for every \(n\in\mathbb{N}\) there exists a metric space \((X,d_X)\), an \(n\)-point subset \(S\subset X\), a Banach space \((Z,\|\cdot\|_Z)\) and a \(1\)-Lipschitz function \(f:S\to Z\) such that the Lipschitz constant of every function \(F:X\to Z\) that extends \(f\) is at least a constant multiple of \(\sqrt{\log n}\). The importance of this result is not only in the removal of the \(\log\log n\) term in the denominator, but also in the designing of a different approach. The approach of Johnson and Lindenstrauss was based on discretization of a result on non-existence of an extension for linear maps. The authors of the present paper show that such a discretization-of-linear approach cannot lead to the lower bound \(c\sqrt{\log n}\). In this paper, the space \(X\) is an expander graph with \(k\) vertices and \(S\) is any of its subsets of size \(k/\sqrt{\log k}\) (the size of \(S\) is denoted by \(n\)). The metric of \(X\) is the so-called magnification of the graph distance of \(X\) at \(S\) (this means that distances between pairs containing elements of \(X\) are somewhat increased if one or both elements of the pair are in \(S\)), the Banach space \(Z\) is the space of real-valued functions on \(S\) with zero sum, endowed with the Wasserstein \(1\) norm (this space is also known as the Lipschitz free space on \(S\) or the Arens-Eells space on \(S\)). The second main result of the paper is a quantitative counterpart to the extension theorem of \textit{G. J. Minty} [Bull. Amer. Math. Soc. 76, 334--339 (1970; Zbl 0191.34603)]. Namely, the authors prove that, for every \(\alpha\in (1/2,1]\) and \(n\in \mathbb{N}\), there exists a metric space \((X,d_X)\), an \(n\)-point subset \(S\subset X\) and a function \(f:S\to \ell_2\) that is \(\alpha\)-Hölder with constant~\(1\), yet the \(\alpha\)-Hölder constant of any \(F:X\to \ell_2\) that extends \(f\) is at least \[ (\log n)^{\frac{2\alpha-1}{4\alpha}}+\left(\frac{\log n}{\log\log n}\right)^{\alpha^2-\frac12}. \] This part uses the discretization approach of Johnson and Lindenstrauss [loc. cit], twisted hypercubes in the spirit of \textit{W. B. Johnson} et al. [Isr. J. Math. 54, 129--138 (1986; Zbl 0626.46007)] and the Bourgain-Begun almost extension lemma [\textit{J. Bourgain}, Lect. Notes Math. 1267, 157--167 (1987; Zbl 0633.46018); \textit{B. Begun}, Isr. J. Math. 109, 151--155 (1999; Zbl 0944.46038)]. The second part of Section 1 contains a very interesting extensive discussion of related open problems and conjectures.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: On Lipschitz extension from finite subsets

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