Bourgain’s discretization Theorem
Bourgain’s discretization Theorem
复制标题
布尔干离散化定理
DOI：
10.14288/1.0043579
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
G. Schechtman
中科院分区：
文献类型：
--
作者：
Ohad Giladi;A. Naor;G. Schechtman
布尔甘的离散化定理断言存在一个全称常数C∈(0,∞)，它具有如下性质。设X，Y为dimX = n的Banach空间，固定D∈(1,∞)，集δ = e−nCn。假设N是X的单位球中的一个δ-网，并且N允许双利普希茨嵌入Y，最大失真为d，那么整个空间X允许双利普希茨嵌入Y，最大失真为CD。这篇主要是解释性的文章致力于布尔甘定理的一个详细证明。对于某些p∈[1，∞]，当Y = Lp时，我们也得到了布尔甘定理的一个改进：在这种情况下，取δ = C−1n−5/2足以使同样的结论成立。这种改进的离散化结果p = 1的情况有以下后果。对于任意大的n∈n，存在一个包含{1，…的n点子集的族Y。， n}，当我们记|Y | = n时，在Y的任意L1嵌入中，加上推土机度量（即运输成本度量或最小重量匹配度量），其变形量至少为√log logN的常数倍；之前最著名的下界是√log log logN的常数倍。
Bourgain’s discretization theorem asserts that there exists a universal constant C ∈ (0,∞) with the following property. Let X,Y be Banach spaces with dimX = n. Fix D ∈ (1,∞) and set δ = e−nCn . Assume that N is a δ-net in the unit ball of X and that N admits a bi-Lipschitz embedding into Y with distortion at most D. Then the entire space X admits a bi-Lipschitz embedding into Y with distortion at most CD. This mostly expository article is devoted to a detailed presentation of a proof of Bourgain’s theorem. We also obtain an improvement of Bourgain’s theorem in the important case when Y = Lp for some p ∈ [1,∞): in this case it suffices to take δ = C−1n−5/2 for the same conclusion to hold true. The case p = 1 of this improved discretization result has the following consequence. For arbitrarily large n ∈ N there exists a family Y of n-point subsets of {1, . . . , n} ⊆ R such that if we write |Y | = N then any L1 embedding of Y , equipped with the Earthmover metric (a.k.a. transportation cost metric or minimumum weight matching metric) incurs distortion at least a constant multiple of √ log logN ; the previously best known lower bound for this problem was a constant multiple of √ log log logN .