skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 8:00 PM ET on Friday, March 21 until 8:00 AM ET on Saturday, March 22 due to maintenance. We apologize for the inconvenience.


Title: 𝐿₁-distortion of Wasserstein metrics: A tale of two dimensions

By discretizing an argument of Kislyakov, Naor and Schechtman proved that the 1-Wasserstein metric over the planar grid{0,1,…<#comment/>,n}2\{0,1,\dots , n\}^2hasL1L_1-distortion bounded below by a constant multiple oflog⁡<#comment/>n\sqrt {\log n}. We provide a new “dimensionality” interpretation of Kislyakov’s argument, showing that if{Gn}n=1∞<#comment/>\{G_n\}_{n=1}^\inftyis a sequence of graphs whose isoperimetric dimension and Lipschitz-spectral dimension equal a common numberδ<#comment/>∈<#comment/>[2,∞<#comment/>)\delta \in [2,\infty ), then the 1-Wasserstein metric overGnG_nhasL1L_1-distortion bounded below by a constant multiple of(log⁡<#comment/>|Gn|)1δ<#comment/>(\log |G_n|)^{\frac {1}{\delta }}. We proceed to compute these dimensions for⊘<#comment/>\oslash-powers of certain graphs. In particular, we get that the sequence of diamond graphs{Dn}n=1∞<#comment/>\{\mathsf {D}_n\}_{n=1}^\inftyhas isoperimetric dimension and Lipschitz-spectral dimension equal to 2, obtaining as a corollary that the 1-Wasserstein metric overDn\mathsf {D}_nhasL1L_1-distortion bounded below by a constant multiple oflog⁡<#comment/>|Dn|\sqrt {\log | \mathsf {D}_n|}. This answers a question of Dilworth, Kutzarova, and Ostrovskii and exhibits only the third sequence ofL1L_1-embeddable graphs whose sequence of 1-Wasserstein metrics is notL1L_1-embeddable.

 
more » « less
Award ID(s):
2055604 1800322
PAR ID:
10445185
Author(s) / Creator(s):
; ;
Publisher / Repository:
American Mathematical Society (AMS)
Date Published:
Journal Name:
Transactions of the American Mathematical Society, Series B
Volume:
10
Issue:
30
ISSN:
2330-0000
Page Range / eLocation ID:
p. 1077-1118
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. For each odd integern≥<#comment/>3n \geq 3, we construct a rank-3 graphΛ<#comment/>n\Lambda _nwith involutionγ<#comment/>n\gamma _nwhose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>n,γ<#comment/>n)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)is stably isomorphic to the exotic Cuntz algebraEn\mathcal E_n. This construction is optimal, as we prove that a rank-2 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda ,\gamma )can never satisfyCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)∼<#comment/>MEEnC^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda , \gamma )whose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )is stably isomorphic to the suspensionSRS \mathbb {R}. In the Appendix, we show that theii-fold suspensionSiRS^i \mathbb {R}is stably isomorphic to a graph algebra iff−<#comment/>2≤<#comment/>i≤<#comment/>1-2 \leq i \leq 1.

     
    more » « less
  2. In this paper we derive the best constant for the followingL∞<#comment/>L^{\infty }-type Gagliardo-Nirenberg interpolation inequality‖<#comment/>u‖<#comment/>L∞<#comment/>≤<#comment/>Cq,∞<#comment/>,p‖<#comment/>u‖<#comment/>Lq+11−<#comment/>θ<#comment/>‖<#comment/>∇<#comment/>u‖<#comment/>Lpθ<#comment/>,θ<#comment/>=pddp+(p−<#comment/>d)(q+1),\begin{equation*} \|u\|_{L^{\infty }}\leq C_{q,\infty ,p} \|u\|^{1-\theta }_{L^{q+1}}\|\nabla u\|^{\theta }_{L^p},\quad \theta =\frac {pd}{dp+(p-d)(q+1)}, \end{equation*}where parametersqqandppsatisfy the conditionsp>d≥<#comment/>1p>d\geq 1,q≥<#comment/>0q\geq 0. The best constantCq,∞<#comment/>,pC_{q,\infty ,p}is given byCq,∞<#comment/>,p=θ<#comment/>−<#comment/>θ<#comment/>p(1−<#comment/>θ<#comment/>)θ<#comment/>pMc−<#comment/>θ<#comment/>d,Mc∫<#comment/>Rduc,∞<#comment/>q+1dx,\begin{equation*} C_{q,\infty ,p}=\theta ^{-\frac {\theta }{p}}(1-\theta )^{\frac {\theta }{p}}M_c^{-\frac {\theta }{d}},\quad M_c≔\int _{\mathbb {R}^d}u_{c,\infty }^{q+1} dx, \end{equation*}whereuc,∞<#comment/>u_{c,\infty }is the unique radial non-increasing solution to a generalized Lane-Emden equation. The case of equality holds whenu=Auc,∞<#comment/>(λ<#comment/>(x−<#comment/>x0))u=Au_{c,\infty }(\lambda (x-x_0))for any real numbersAA,λ<#comment/>>0\lambda >0andx0∈<#comment/>Rdx_{0}\in \mathbb {R}^d. In fact, the generalized Lane-Emden equation inRd\mathbb {R}^dcontains a delta function as a source and it is a Thomas-Fermi type equation. Forq=0q=0ord=1d=1,uc,∞<#comment/>u_{c,\infty }have closed form solutions expressed in terms of the incomplete Beta functions. Moreover, we show thatuc,m→<#comment/>uc,∞<#comment/>u_{c,m}\to u_{c,\infty }andCq,m,p→<#comment/>Cq,∞<#comment/>,pC_{q,m,p}\to C_{q,\infty ,p}asm→<#comment/>+∞<#comment/>m\to +\inftyford=1d=1, whereuc,mu_{c,m}andCq,m,pC_{q,m,p}are the function achieving equality and the best constant ofLmL^m-type Gagliardo-Nirenberg interpolation inequality, respectively.

     
    more » « less
  3. In this paper we consider which families of finite simple groupsGGhave the property that for eachϵ<#comment/>>0\epsilon > 0there existsN>0N > 0such that, if|G|≥<#comment/>N|G| \ge NandS,TS, Tare normal subsets ofGGwith at leastϵ<#comment/>|G|\epsilon |G|elements each, then every non-trivial element ofGGis the product of an element ofSSand an element ofTT.

    We show that this holds in a strong and effective sense for finite simple groups of Lie type of bounded rank, while it does not hold for alternating groups or groups of the formPSLn(q)\mathrm {PSL}_n(q)whereqqis fixed andn→<#comment/>∞<#comment/>n\to \infty. However, in the caseS=TS=TandGGalternating this holds with an explicit bound onNNin terms ofϵ<#comment/>\epsilon.

    Related problems and applications are also discussed. In particular we show that, ifw1,w2w_1, w_2are non-trivial words,GGis a finite simple group of Lie type of bounded rank, and forg∈<#comment/>Gg \in G,Pw1(G),w2(G)(g)P_{w_1(G),w_2(G)}(g)denotes the probability thatg1g2=gg_1g_2 = gwheregi∈<#comment/>wi(G)g_i \in w_i(G)are chosen uniformly and independently, then, as|G|→<#comment/>∞<#comment/>|G| \to \infty, the distributionPw1(G),w2(G)P_{w_1(G),w_2(G)}tends to the uniform distribution onGGwith respect to theL∞<#comment/>L^{\infty }norm.

     
    more » « less
  4. We develop a higher semiadditive version of Grothendieck-Witt theory. We then apply the theory in the case of a finite field to study the higher semiadditive structure of theK(1)K(1)-local sphereSK(1)\mathbb {S}_{K(1)}at the prime22, in particular realizing the non-22-adic rational element1+ε<#comment/>∈<#comment/>π<#comment/>0SK(1)1+\varepsilon \in \pi _0\mathbb {S}_{K(1)}as a “semiadditive cardinality.” As a further application, we compute and clarify certain power operations inπ<#comment/>0SK(1)\pi _0\mathbb {S}_{K(1)}.

     
    more » « less
  5. The classical Maclaurin inequality asserts that the elementary symmetric meanssk(y)1(nk)∑<#comment/>1≤<#comment/>i1>⋯<#comment/>>ik≤<#comment/>nyi1…<#comment/>yik\begin{equation*} s_k(y) ≔\frac {1}{\binom {n}{k}} \sum _{1 \leq i_1 > \dots > i_k \leq n} y_{i_1} \dots y_{i_k} \end{equation*}obey the inequalitysℓ<#comment/>(y)1/ℓ<#comment/>≤<#comment/>sk(y)1/ks_\ell (y)^{1/\ell } \leq s_k(y)^{1/k}whenever1≤<#comment/>k≤<#comment/>ℓ<#comment/>≤<#comment/>n1 \leq k \leq \ell \leq nandy=(y1,…<#comment/>,yn)y = (y_1,\dots ,y_n)consists of nonnegative reals. We establish a variant|sℓ<#comment/>(y)|1ℓ<#comment/>≪<#comment/>ℓ<#comment/>1/2k1/2max(|sk(y)|1k,|sk+1(y)|1k+1)\begin{equation*} |s_\ell (y)|^{\frac {1}{\ell }} \ll \frac {\ell ^{1/2}}{k^{1/2}} \max (|s_k(y)|^{\frac {1}{k}}, |s_{k+1}(y)|^{\frac {1}{k+1}}) \end{equation*}of this inequality in which theyiy_iare permitted to be negative. In this regime the inequality is sharp up to constants. Such an inequality was previously known without thek1/2k^{1/2}factor in the denominator.

     
    more » « less