Search

Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few. The mathematical theory of metric embedding is well studied in both pure and applied analysis and has more recently been a source of interest for computer scientists as well. Most of this work is focused on the development of bi-Lipschitz mappings between metric spaces. In this paper we present new concepts in metric embeddings as well as new embedding methods for metric spaces. We focus on finite metric spaces, however some of the concepts and methods are applicable in other settings as well.One of the main cornerstones in finite metric embedding theory is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with O(logn) distortion. Bourgainʼs result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is natural to ask: can an embedding do much better in terms of the average distortion? Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgainʼs theorem. In fact, our embedding possesses a much stronger property. We define the ℓq-distortion of a uniformly distributed pair of points. Our embedding achieves the best possible ℓq-distortion for all 1⩽q⩽∞ simultaneously.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension of the host space. The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgainʼs embedding. Our embedding methods achieve better dimension, and in fact, shed new light on another fundamental question in metric embedding, which is: whether the embedding dimension of a metric space is related to its intrinsic dimension? I.e., whether the dimension in which it can be embedded in some real normed space is related to the intrinsic dimension which is reflected by the inherent geometry of the space, measured by the spaceʼs doubling dimension. The existence of such an embedding was conjectured by Assouad,44Assouad (1983) [10] conjectured that the distortion would be a function only of the doubling dimension as well, but this stronger conjecture was disproved (Semmes, 1996) [86].and was later posed as an open problem in several papers. Our embeddings give the first positive result of this type showing any finite metric space obtains a low distortion (and constant average distortion) embedding in Euclidean space in dimension proportional to its doubling dimension.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary finite metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results.The results presented in this paper55This paper is a full version based on the conference papers: (Abraham et al., 2005, 2006, 2008) [1,2,5].have been the basis for further developments both within the field of metric embedding and in other areas such as graph theory, distributed computing and algorithms. We present a comprehensive study of the notions and concepts introduced here and provide additional extensions, related results and some examples of algorithmic applications.

This is the second paper of a series (started by Braverman and Finkelberg, 2010 [2] ) which describes a conjectural analog of the affine Grassmannian for affine Kac–Moody groups (also known as the double affine Grassmannian). The current paper is dedicated to describing a conjectural analog of the convolution diagram for the double affine Grassmannian. In the case when G = SL ( n ) our conjectures can be derived from Nakajima (2009) [12] .

In this paper, we interpret the Gindikin–Karpelevich formula and the Casselman–Shalika formula as sums over Kashiwara–Lusztigʼs canonical bases, generalizing the results of Bump and Nakasuji (2010) [7] to arbitrary split reductive groups. We also rewrite formulas for spherical vectors and zonal spherical functions in terms of canonical bases. In a subsequent paper Kim and Lee (preprint) [14], we will generalize these formulas to p-adic affine Kac–Moody groups.

On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. In each case, there are three possible interpretations for the double series. In an earlier paper, two of the present authors proved the first identity under one possible interpretation. In the present paper, the second identity is proved under a similar interpretation, with one additional assumption. Moreover, under a second interpretation, entirely different proofs of both identities, depending on weighted (or twisted) divisor sums, are offered. The two identities are intimately connected with the classical circle and divisor problems, respectively.

The aim of this paper is to introduce and study Lie algebras and Lie groups over noncommutative rings. For any Lie algebra $\gg$ sitting inside an associative algebra $A$ and any associative algebra $\FF$ we introduce and study the algebra $(\gg,A)(\FF)$, which is the Lie subalgebra of $\FF \otimes A$ generated by $\FF \otimes \gg$. In many examples $A$ is the universal enveloping algebra of $\gg$. Our description of the algebra $(\gg,A)(\FF)$ has a striking resemblance to the commutator expansions of $\FF$ used by M. Kapranov in his approach to noncommutative geometry. To each algebra $(\gg, A)(\FF)$ we associate a ``noncommutative algebraic'' group which naturally acts on $(\gg,A)(\FF)$ by conjugations and conclude the paper with some examples of such groups., Comment: Introduction is improved and some typos corrected. To appear in "Advances"

We consider a Dirac-type operator D P on a vector bundle V over a compact Riemannian manifold ( M , g ) with a non-empty boundary. The operator D P is specified by a boundary condition P ( u | ∂ M ) = 0 where P is a projector which may be a non-local, i.e., a pseudodifferential operator. We assume the existence of a chirality operator which decomposes L 2 ( M , V ) into two orthogonal subspaces X + ⊕ X − . Under certain conditions, the operator D P restricted to X + and X − defines a pair of Fredholm operators which maps X + → X − and X − → X + correspondingly, giving rise to a superstructure on V. In this paper we consider the questions of determining the index of D P and the reconstruction of ( M , g ) , V and D P from the boundary data on ∂M. The data used is either the Cauchy data, i.e., the restrictions to ∂ M × R + of the solutions to the hyperbolic Dirac equation, or the boundary spectral data, i.e., the set of the eigenvalues and the boundary values of the eigenfunctions of D P . We obtain formulae for the index and prove uniqueness results for the inverse boundary value problems. We apply the obtained results to the classical Dirac-type operator in M × C 4 , M ⊂ R 3 .

Here we study an amazing phenomenon discovered by Newhouse [S. Newhouse, Non-density of Axiom A(a) on S 2 , in: Proc. Sympos. Pure Math., vol. 14, Amer. Math. Soc., 1970, pp. 191–202; S. Newhouse, Diffeomorphisms with infinitely many sinks, Topology 13 (1974) 9–18; S. Newhouse, The abundance of wild hyperbolic sets and nonsmooth stable sets of diffeomorphisms, Publ. Math. Inst. Hautes Etudes Sci. 50 (1979) 101–151]. It turns out that in the space of C r smooth diffeomorphisms Diff r ( M ) of a compact surface M there is an open set U such that a Baire generic diffeomorphism f ∈ U has infinitely many coexisting sinks. In this paper we make a step towards understanding “how often does a surface diffeomorphism have infinitely many sinks.” Our main result roughly says that with probability one for any positive D a surface diffeomorphism has only finitely many localized sinks either of cyclicity bounded by D or those whose period is relatively large compared to its cyclicity. It verifies a particular case of Palis' Conjecture saying that even though diffeomorphisms with infinitely many coexisting sinks are Baire generic, they have probability zero. One of the key points of the proof is an application of Newton Interpolation Polynomials to study the dynamics initiated in [V. Kaloshin, B. Hunt, A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms I, Ann. of Math., in press, 92 pp.; V. Kaloshin, A stretched exponential bound on the rate of growth of the number of periodic points for prevalent diffeomorphisms II, preprint, 85 pp.].

In this paper we study the group $A_0(X)$ of zero dimensional cycles of degree 0 modulo rational equivalence on a projective homogeneous algebraic variety $X$. To do this we translate rational equivalence of 0-cycles on a projective variety into R-equivalence on symmetric powers of the variety. For certain homogeneous varieties, we then relate these symmetric powers to moduli spaces of \'etale subalgebras of central simple algebras which we construct. This allows us to show $A_0(X) = 0$ for certain classes of homogeneous varieties, extending previous results of Swan / Karpenko, of Merkurjev, and of Panin., Comment: Significant revisions made to simplify exposition, also includes results for symplectic involution varieties. Main arguments now rely on Hilbert schemes of points and are valid with only mild characteristic assumptions. 32 pages

As is well known, h-vectors of simple (or simplicial) convex polytopes are characterized. In fact, those h-vectors must satisfy Dehn-Sommerville equations and some other inequalities. Simple convex polytopes determine Gorenstein* simplicial posets and h-vectors are defined for simplicial posets. It is known that h-vectors of Gorenstein* simplicial posets must satisfy Dehn-Sommerville equations and that every component in the h-vectors must be non-negative. In this paper we will show that h-vectors of Gorenstein* simplicial posets must satisfy one more subtle condition conjectured by R. Stanley and complete characterization of those h-vectors. Our proof is purely algebraic but the idea of the proof stems from topology., 12 pages

A special case of Haimanʼs identity [M. Haiman, Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002) 371–407] for the character of the quotient ring of diagonal coinvariants under the diagonal action of the symmetric group yields a formula for the bigraded Hilbert series as a sum of rational functions in q,t. In this paper we show how a summation identity of Garsia and Zabrocki for Macdonald polynomial Pieri coefficients can be used to transform Haimanʼs formula for the Hilbert series into an explicit polynomial in q,t with integer coefficients. We also provide an equivalent formula for the Hilbert series as the constant term in a multivariate Laurent series.

The homotopy limit problem for Karoubiʼs Hermitian K-theory (Karoubi, 1980) [26] was posed by Thomason (1983) [44] . There is a canonical map from algebraic Hermitian K-theory to the Z / 2 -homotopy fixed points of algebraic K-theory. The problem asks, roughly, how close this map is to being an isomorphism, specifically after completion at 2. In this paper, we solve this problem completely for fields of characteristic 0 (Theorems 16, 20). We show that the 2-completed map is an isomorphism for fields F of characteristic 0 which satisfy cd 2 ( F [ i ] ) ∞ , but not in general.

In this paper we consider deformations of an algebroid stack on an etale groupoid. We construct a differential graded Lie algebra (DGLA) which controls this deformation theory. In the case when the algebroid is a twisted form of functions we show that this DGLA is quasiisomorphic to the twist of the DGLA of Hochschild cochains on the algebra of functions on the groupoid by the characteristic class of the corresponding gerbe.

We introduce the_Brauer loop scheme_ E := {M in M_N(C) : M\cp M = 0}, where \cp is a certain degeneration of the ordinary matrix product. Its components of top dimension, floor(N^2/2), correspond to involutions \pi in S_N having one or no fixed points. In the case N even, this scheme contains the upper-upper scheme from [Knutson '04] as a union of (N/2)! of its components. One of those is a degeneration of the_commuting variety_ of pairs of commuting matrices. The_Brauer loop model_ is a quantum integrable stochastic process introduced in [de Gier--Nienhuis '04], and some of the entries of its Perron-Frobenius eigenvector were observed (conjecturally) to match the degrees of the components of the upper-upper scheme. We extend this, with proof, to_all_ the entries: they are the degrees of the components of the Brauer loop scheme. Our proof of this follows the program outlined in [Di Francesco--Zinn-Justin '04]. In that paper, the entries of the Perron-Frobenius eigenvector were generalized from numbers to polynomials, which allowed them to be calculated inductively using divided difference operators. We relate these polynomials to the multidegrees of the components of the Brauer loop scheme, defined using an evident torus action on E. In particular, we obtain a formula for the degree of the commuting variety, previously calculated up to 4x4 matrices., Comment: 31 pages, 4 figures; v2 has tiny edits and an extra circle action

International audience; In this article, we generalize a localization theorem of Lovasz and Simonovits [Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms 4-4 (1993) 359-412] which is an important tool to prove dimension-free functional inequalities for log-concave measures. In a previous paper [Fradelizi and Guedon, The extreme points of subsets of s-concave probabilities and a geometric localization theorem, Discrete Comput. Geom. 31 (2004) 327-335], we proved that the localization may be deduced from a suitable application of Krein-Milman's theorem to a subset of log-concave probabilities satisfying one linear constraint and from the determination of the extreme points of its convex hull. Here, we generalize this result to more constraints, give some necessary conditions satisfied by such extreme points and explain how it may be understood as a generalized localization theorem. Finally, using this new localization theorem, we solve an open question on the comparison of the volume of sections of non-symmetric convex bodies in R-n by hyperplanes. A surprising feature of the result is that the extremal case in this geometric inequality is reached by an unusual convex set that we manage to identify. (C) 2005 Elsevier Inc. All rights reserved.

In this paper, we prove that in small parameter regions, arbitrary unitary matrix integrals converge in the large $N$ limit and match their formal expansion. Secondly we give a combinatorial model for our matrix integral asymptotics and investigate examples related to free probability and the HCIZ integral. Our convergence result also leads us to new results of smoothness of microstates. We finally generalize our approach to integrals over the othogonal group., 41 pages, important modifications, new section about orthogonal integrals

Given an affine hyperplane arrangement with some additional structure, we define two finite-dimensional, noncommutative algebras, both of which are motivated by the geometry of hypertoric varieties. We show that these algebras are Koszul dual to each other, and that the roles of the two algebras are reversed by Gale duality. We also study the centers and representation categories of our algebras, which are in many ways analogous to integral blocks of category O., Comment: 55 pages; v2 contains significant revisions to proofs and to some of the results. Section 7 has been deleted; that material will be incorporated into a later paper by the same authors

We prove that for any partition $(\lambda_1,...,\lambda_{d^2})$ of size $\ell d$ there exists $k\ge 1$ such that the tensor square of the irreducible representation of the symmetric group $S_{k\ell d}$ with respect to the rectangular partition $(k\ell,...,k\ell)$ contains the irreducible representation corresponding to the stretched partition $(k\lambda_1,...,k\lambda_{d^2})$. We also prove a related approximate version of this statement in which the stretching factor $k$ is effectively bounded in terms of $d$. This investigation is motivated by questions of geometric complexity theory., Comment: Added Section 1.1 containing motivation coming from geometric complexity theory. Added a result on symmetric Kronecker coefficients. Fixed a bug that made the paper appear twice in v3

A long-standing conjecture of Erdős and Simonovits is that ex ( n , C 2 k ) , the maximum number of edges in an n -vertex graph without a 2 k -gon is asymptotically 1 2 n 1 + 1 / k as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n , we prove that ex ( n , C 6 ) > 3 ( 5 - 2 ) ( 5 - 1 ) 4 / 3 n 4 / 3 + O ( n ) > 0.5338 n 4 / 3 . We also show that ex ( n , C 6 ) ⩽ λ n 4 / 3 + O ( n ) 0.6272 n 4 / 3 if n is sufficiently large, where λ is the real root of 16 λ 3 - 4 λ 2 + λ - 3 = 0 . This yields the best-known upper bound for the number of edges in a hexagon-free graph. The same methods are applied to find a tight bound for the maximum size of a hexagon-free 2 n × n bipartite graph.

In this paper we study fully nonlinear obstacle-type problems in Hilbert spaces. We introduce the notion of Q-elliptic equation and prove existence, uniqueness, and regularity of viscosity solutions of Q-elliptic obstacle problems. In particular we show that solutions of concave problems with semiconvex obstacles are in the space WQ2,∞.

In previous work, we showed that the solution of certain systems of discrete integrable equations, notably $Q$ and $T$-systems, is given in terms of partition functions of positively weighted paths, thereby proving the positive Laurent phenomenon of Fomin and Zelevinsky for these cases. This method of solution is amenable to generalization to non-commutative weighted paths. Under certain circumstances, these describe solutions of discrete evolution equations in non-commutative variables: Examples are the corresponding quantum cluster algebras [BZ], the Kontsevich evolution [DFK09b] and the $T$-systems themselves [DFK09a]. In this paper, we formulate certain non-commutative integrable evolutions by considering paths with non-commutative weights, together with an evolution of the weights that reduces to cluster algebra mutations in the commutative limit. The general weights are expressed as Laurent monomials of quasi-determinants of path partition functions, allowing for a non-commutative version of the positive Laurent phenomenon. We apply this construction to the known systems, and obtain Laurent positivity results for their solutions in terms of initial data., 46 pages, minor typos corrected

In 1963 Fisher and Stephenson \cite{FS} conjectured that the monomer-monomer correlation on the square lattice is rotationally invariant. In this paper we prove a closely related statement on the hexagonal lattice. Namely, we consider correlations of two quadromers (four-vertex subgraphs consisting of a monomer and its three neighbors) and show that they are rotationally invariant., 28 pages

We define a Floer-homology invariant for knots in an oriented three-manifold, closely related to the holomorphic disk Floer homologies for three-manifolds defined in an earlier paper. We set up basic properties of these invariants, including an Euler characteristic calculation, behaviour under connected sums. Then, we establish a relationship with $HF^+$ for surgeries along the knot. Applications include calculation of $HF^+$ of three-manifolds obtained by surgeries on some special knots in $S^3$, and also calculation of $HF^+$ for certain simple three-manifolds which fiber over the circle., 64 pages, 17. Revised version

In \cite{Pe1}, \cite{Pe2}, \cite{AP1}, \cite{AP2}, and \cite{AP3} sharp estimates for $f(A)-f(B)$ were obtained for self-adjoint operators $A$ and $B$ and for various classes of functions $f$ on the real line $\R$. In this paper we extend those results to the case of functions of normal operators. We show that if a function $f$ belongs to the H\"older class $\L_\a(\R^2)$, $0, Comment: 32 pages

In the Lost Notebook, Ramanujan presents a truly enigmatic infinite product expansion for the two variable Rogers–Ramanujan series. In this paper, we prove this formula by a careful analysis of the Stieltjes–Wigert polynomials.

In this paper we prove an analogue of a recent result of Gordon and Stafford that relates the representation theory of certain noncommutative deformations of the coordinate ring of the n-th symmetric power of C^2 with the geometry of the Hilbert scheme of n points in C^2 through the formalism of Z-algebras. Our work produces, for every regular noncommutative deformation O^\lambda of a Kleinian singularity X=C^2/\Gamma, as defined by Crawley-Boevey and Holland, a filtered Z-algebra which is Morita equivalent to O^\lambda, such that the associated graded Z-algebra is Morita equivalent to the minimal resolution of X. The construction uses the description of the algebras O^\lambda as quantum Hamiltonian reductions, due to Holland, and a GIT construction of minimal resolutions of X, due to Cassens and Slodowy., Comment: LaTeX, 24 pages. Version 2 (some misprints fixed)

Let F be a local field. The action of GL(n,F) on the Grassmann variety Gr(m,n,F) induces a continuous representation of the maximal compact subgroup of GL(n,F) on the space of L^2-functions on Gr(m,n,F). The irreducible constituents of this representation are parameterized by the same underlying set both for Archimedean and non-Archimedean fields. This paper connects the Archimedean and non-Archimedean theories using the quantum Grassmannian. In particular, idempotents in the Hecke algebra associated to this representation are the image of the quantum zonal spherical functions after taking appropriate limits. Consequently, a correspondence is established between some irreducible representations with Archimedean and non-Archimedean origin., Comment: 24 pages, final version, to appear in Advances in Mathematics

The principle “ambient cohomology of a Kaehler manifold annihilates obstructions” has been known and exploited since pioneering work of Kodaira. This paper unifies and modestly extends known results in the context of abstract deformations of compact Kaehler manifolds and submanifolds.

This paper shows that each of the sharp (endpoint) Sobolev inequality and the isoperimetric inequality can be split into two sharp and stronger inequalities through either the 1-variational capacity or the 1-integral affine surface area. Furthermore, some related sharp analytic and geometric inequalities are also explored.

Let H_c be the rational Cherednik algebra of type A_{n-1} with spherical subalgebra U_c = eH_ce. Then U_c is filtered by order of differential operators, with associated graded ring gr U_c = C[h+h*]^W, where W is the n-th symmetric group. We construct a filtered Z-algebra B such that, under mild conditions on c: (1) The category B-qgr of graded noetherian B-modules modulo torsion is equivalent to U_c-mod; (2) The associated graded Z-algebra gr(B) has gr(B)-qgr equivalent to Coh Hilb(n), the category of coherent sheaves on the Hilbert scheme of points in the plane. This can be regarded as saying that U_c simultaneously gives a noncommutative deformation both of (h+h*)/W and of its resolution of singularities Hilb(n) --> (h+h*)/W. As our forthcoming companion paper [GS] shows, this result is a powerful tool for studying the representation theory of H_c and its relationship to Hilb(n)., Minor changes: proof of Corollary 4.13 adjusted; typos corrected

In this paper we use large cardinals to address some problems about generic continuity and generic selection that occur in the study of fragmentability and differentiability in the context of Banach spaces.

In this paper we study the complete reducibility of representations of infinite- dimensional Lie algebras from the perspective of representation theory of vertex algebras., Israel Science Foundation (grant No. 1142/07), National Science Foundation (U.S.) (Grant No. DMS-0501395)

We introduce the notion of a projectively simple ring, which is an infinite-dimensional graded k-algebra A such that every 2-sided ideal has finite codimension in A (over the base field k). Under some (relatively mild) additional assumptions on A, we reduce the problem of classifying such rings (in the sense explained in the paper) to the following geometric question, which we believe to be of independent interest. Let X is a smooth irreducible projective variety. An automorphism f: X -> X is called wild if it X has no proper f-invariant subvarieties. We conjecture that if X admits a wild automorphism then X is an abelian variety. We prove several results in support of this conjecture; in particular, we show that the conjecture is true if X is a curve or a surface. In the case where X is an abelian variety, we describe all wild automorphisms of X. In the last two sections we show that if A is projectively simple and admits a balanced dualizing complex, then Proj(A) is Cohen-Macaulay and Gorenstein., Some new material has been added in Section 1; to appear in Advances in Mathematics

In this paper, we study a geodesic equation in the space of Sasakian metrics H . The equation leads to the Dirichlet problem of a complex Monge–Ampere type equation on the Kahler cone. This equation differs from the standard complex Monge–Ampere equation in a significant way, with gradient terms involved in the ( 1 , 1 ) symmetric tensor of the operator. We establish appropriate regularity estimates for this complex Monge–Ampere type equation. As geometric application, we show that the space of Sasakian metrics H is a metric space, and the constant transversal scalar curvature metric realizes the global minimum of K -energy if the first basic Chern class C 1 B ⩽ 0 . We also prove that the constant transversal scalar curvature metric is unique in each basic Kahler class if the first basic Chern class is either strictly negative or zero.

A group G ⩽ Sym ( N ) is cofinitary if g has finitely many fixed points for every g ∈ G except the identity element. In this paper, we discuss the definability of maximal cofinitary groups and some related structures. More precisely, we show the following two results: (1) Assuming V = L , there is a Π 1 1 set of permutations on N which generates a maximal cofinitary group. (2) Assuming V = L , there is a Π 1 1 mad permutation family in Sym ( N ) .