The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.     

The bicompletion of an asymmetric normed linear space

A biBanach space is an asymmetric normed linear space (X,‖·‖) such that the normed linear space (X,‖·‖^s) is a Banach space, where ‖x‖^s= max {‖x‖,‖-x‖} for all x∈X. We prove that each asymmetric normed linear space (X,‖·‖) is isometrically isomorphic to a dense subspace of a biBanach space (Y,‖·‖_Y). Furthermore the space (Y,‖·‖_Y) is unique (up to isometric isomorphism). This revised version was published online in August 2006 with corrections to the Cover Date.     

Embedding ofl ∞ k in finite dimensional Banach spaces

Letx ₁,x ₂, ...,x _n ben unit vectors in a normed spaceX and defineM _n =Ave{‖Σ _i=1 ⁿ ε₁ x _i ‖:ε₁=±1}. We prove that there exists a setA⊂{1, ...,n} of cardinality such that {x _i } _i∈A is 16M _n -isomorphic to the natural basis ofl _∞ ^k . This result implies a significant improvement of the known results concerning embedding ofl _∞ ^k in finite dimensional Banach spaces. We also prove that for every ∈>0 there exists a constantC(∈) such that every normed spaceX _n of dimensionn either contains a (1+∈)-isomorphic copy ofl ₂ ^m for somem satisfying ln lnm≧1/2 ln lnn or contains a (1+∈)-isomorphic copy ofl _∞ ^k for somek satisfying ln lnk>1/2 ln lnn−C(∈). These results follow from some combinatorial properties of vectors with ±1 entries. The contribution of the first author to this paper forms part of his Ph.D. Thesis written under the supervision of Prof. M. A. Perles from the Hebrew University.     

On order preserving contractions

Let (Ω,Σ,μ) be a measure space and letP be an operator onL ₂(Ω,Σ,μ) with ‖P‖≦1,Pf≧0 a.e. wheneverf≧0. If the subspaceK is defined byK={x| ||P ⁿ x||=||P ^*n x||=||x||,n=1,2,...} thenK=L ₂(Ω,Σ₁,μ), where Σ₁ ⊂ Σ and onK the operatorP is “essentially” a measure preserving transformation. Thus the eigenvalues ofP of modulus one, form a group under multiplication. This last result was proved by Rota for finiteμ here finiteness is not assumed) and is a generalization of a theorem of Frobenius and Perron on positive matrices. The research reported in this document has been sponsored in part by Air Force Office of Scientific Research, OAR through the European Office, Aerospace Research, United States Air Force.     

Feynman’s Operational Calculi: Decomposing Disentanglings

Let X be a Banach space and suppose that A ₁,…,A _n are noncommuting (that is, not necessarily commuting) elements in ℒ(X), the space of bounded linear operators on X. Further, for each i∈{1,…,n}, let μ _i be a continuous probability measure on ℬ([0,1]), the Borel class of [0,1]. Each such n-tuple of operator-measure pairs (A _i ,μ _i ), i=1,…,n, determines an operational calculus or disentangling map T_m1,...,mn{\mathcal{T}}_{\mu_{1},\dots,\mu_{n}} from a commutative Banach algebra \mathbbD(A₁,...,A_n){\mathbb{D}}(A_{1},\dots,A_{n}) of analytic functions, called the disentangling algebra , into the noncommutative Banach algebra ℒ(X). The disentanglings are the central processes of Feynman’s operational calculi.     

A geometrical property ofC(K) spaces

We introduce a geometrical property of norm one complemented subspaces ofC(K) spaces which is useful for computing lower bounds on the norms of projections onto subspaces ofC(K) spaces. Loosely speaking, in the dual of such a space ifx* is a w* limit of a net (x _a ^* ) andx*=x*₁+x*₂ with ‖x*‖=‖x*₁‖ + ‖x*₂‖, then we measure how efficiently thex _a ^* 's can be split into two nets converging tox*₁ andx*₂, respectively. As applications of this idea we prove that if for everyε>0,X is a norm (1+ε) complemented subspace of aC(K) space, then it is norm one complemented in someC(K) space, and we give a simpler proof that a slight modification of anl ₁-predual constructed by Benyamini and Lindenstrauss is not complemented in anyC(K) space. Research partially supported by a grant of the U.S.-Israel Binational Science Foundation. Research of the first-named author is supported in part by NSF grant DMS-8602395. Research of the second-named author was partially supported by the Fund for the Promotion of Research at the Technion, and by the Technion VPR-New York Metropolitan Research Fund.     

A strong law of large numbers for nonexpansive vector-valued stochastic processes

A mapT: X→X on a normed linear space is callednonexpansive if ‖Tx-Ty‖≤‖x-y‖∀x, y∈X. Let (Ω, Σ,P) be a probability space, an increasing chain of σ-fields spanning Σ,X a Banach space, andT: X→X. A sequence (x_n) of strongly -measurable and stronglyP-integrable functions on Ω taking on values inX is called aT-martingale if . LetT: H→H be a nonexpansive mapping on a Hilbert spaceH and let (x_n) be aT-martingale taking on values inH. If then x _n /n converges a.e. LetT: X→X be a nonexpansive mapping on ap-uniformly smooth Banach spaceX, 1<p≤2, and let (x_n) be aT-martingale (taking on values inX). If then there exists a continuous linear functionalf∈X ^* of norm 1 such that If, in addition, the spaceX is strictly convex, x _n /n converges weakly; and if the norm ofX ^* is Fréchet differentiable (away from zero), x _n /n converges strongly. This work was supported by National Science Foundation Grant MCS-82-02093     

Precise rates in the law of the logarithm for the moment convergence in Hilbert spaces

Let （X, Xn; n ≥1） be a sequence of i.i.d, random variables taking values in a real separable Hilbert space （H, ｜｜·｜｜） with covariance operator ∑. Set Sn = X1 ＋ X2 ＋ ... ＋ Xn, n≥ 1. We prove that, for b 〉 -1,
lim ε→0 ε^2（b＋1） ∞ ∑n=1 （logn）^b/n^3/2 E{｜｜Sn｜｜-σε√nlogn}=σ^-2（b＋1）/（2b＋3）（b＋1） B｜｜Y｜^2b＋3
holds if EX=0,and E｜｜X｜｜^2（log｜｜x｜｜）^3bv（b＋4）〈∞ where Y is a Gaussian random variable taking value in a real separable Hilbert space with mean zero and covariance operator ∑, and σ^2 denotes the largest eigenvalue of ∑.     

Inequalities and sphere-packing inl p

If 1<p<∞, there is a constantr _p <1/2 so that ifr>r _p only a bounded number of balls inl _p of radiusr can be packed into the unit ball ofl _p . We obtain the exact value of this bound for eachp andr as a consequence of several new inequalities relating the expressions Σλ _i λ _j ‖x _i –x _j ‖ ^p , Σλ _i ‖x _i ‖ ^p and Σλ _i ^/2 for sequences (x _i ) ₁ ⁿ ⊂l _p and (λ _i ) ₁ ⁿ ⊂R.     

Optimal properties of contraction semigroups in banach spaces

Suppose that(T _t )_t>0 is aC ₀ semi-group of contractions on a Banach spaceX, such that there exists a vectorx∈X, ‖x‖=1 verifyingJ ⁻¹(Jx)={x}, whereJ is the duality mapping fromX toP(X ^*). If |<T _t x,f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1 thenx is an eigenvector of the generatorA, associated with a purcly imaginary eigenvalue. Because of Lin's example [L], the hypothesis onx∈X is the best possible. If the hypothesisJ ⁻¹(Jx)={x} is not verified, we can prove that ifJx is a singleton and ifJ ⁻¹(Jx) is weakly compact, then if |<T _t x, f>|→1, whent→+∞ for somef∈X ^*, ‖f‖≤1, there existsy∈J ⁻¹(Jx) such thaty is an eigenvector of the generatorA, associated with a purely imaginary eigenvalue. We give also a counter-example in the case whereX is one of the spaces ℓ₁ orL ₁.     

On perturbations of differentiable semigroups

LetX be a Banach space and letA be the infinitesimal generator of a differentiable semigroup {T(t) |t ≥ 0}, i.e. aC ₀-semigroup such thatt ↦T(t)x is differentiable on (0, ∞) for everyx εX. LetB be a bounded linear operator onX and let {S(t) |t ≥ 0} be the semigroup generated byA +B. Renardy recently gave an example which shows that {S(t) |t ≥ 0} need not be differentiable. In this paper we give a condition on the growth of ‖T′(t)‖ ast ↓ 0 which is sufficient to ensure that {S(t) |t ≥ 0} is differentiable. Moreover, we use Renardy’s example to study the optimality of our growth condition. Our results can be summarized roughly as follows:

Symmetric block bases of sequences with large average growth

We show that if 0<ε≦1, 1≦p<2 andx ₁, …,x _n is a sequence of unit vectors in a normed spaceX such thatE ‖∑ _l ⁿ ε_i x _l‖≧n ^1/p, then one can find a block basisy ₁, …,y _m ofx ₁, …,x _n which is (1+ε)-symmetric and has cardinality at leastγn ^2/p-1(logn)⁻¹, where γ depends on ε only. Two examples are given which show that this bound is close to being best possible. The first is a sequencex ₁, …,x _n satisfying the above conditions with no 2-symmetric block basis of cardinality exceeding 2n ^2/p-1. This sequence is not linearly independent. The second example is a sequence which satisfies a lowerp-estimate but which has no 2-symmetric block basis of cardinality exceedingCn ^2/p-1(logn)^4/3, whereC is an absolute constant. This applies when 1≦p≦3/2. Finally, we obtain improvements of the lower bound when the spaceX containing the sequence satisfies certain type-condition. These results extend results of Amir and Milman in [1] and [2]. We include an appendix giving a simple counterexample to a question about norm-attaining operators.     

On set-valued cone absolutely summing maps

Spaces of cone absolutely summing maps are generalizations of Bochner spaces L ^p (μ, Y), where (Ω, Σ, μ) is some measure space, 1 ≤ p ≤ ∞ and Y is a Banach space. The Hiai-Umegaki space $ \mathcal{L}^1 \left[ {\sum ,cbf(X)} \right] $ \mathcal{L}^1 \left[ {\sum ,cbf(X)} \right] of integrably bounded functions F: Ω → cbf(X), where the latter denotes the set of all convex bounded closed subsets of a separable Banach space X, is a set-valued analogue of L ¹(μ, X). The aim of this work is to introduce set-valued cone absolutely summing maps as a generalization of $ \mathcal{L}^1 \left[ {\sum ,cbf(X)} \right] $ \mathcal{L}^1 \left[ {\sum ,cbf(X)} \right] , and to derive necessary and sufficient conditions for a set-valued map to be such a set-valued cone absolutely summing map. We also describe these set-valued cone absolutely summing maps as those that map order-Pettis integrable functions to integrably bounded set-valued functions.     

Orthogonal almost locally minimal projections on ℓ 1 n

A projectionP on a Banach spaceX with ‖P‖≤λ₀ is called almost locally minimal if, for every α>0 small enough, the ballB(P,α) in the space of operatorsL(X) does not contain a projectionQ with ‖Q‖≤‖P‖(1–Dα²), whereD=D(λ₀) is a constant independent of ‖P‖. It is shown that, for everyp≥1 and every compact abelian groupG, every translation invariant projection onL _p(G) is almost locally minimal. Orthogonal projections on ℓ ₁ ⁿ are investigated with respect to some weaker local minimality properties. Participant in Workshop in Linear Analysis and Probability, Texas A&M University, College Station, Texas 1998. Partially supported by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).     

Friabilité des valeurs d’un polynôme

Let F(X) be an absolutely irreducible polynomial in \mathbbZ [X₁,..., X_n]{\mathbb{Z} [X_{1},\dots, X_{n}]}, with degree d. We prove that, for any δ < 4/3, for any sufficiently large x, there exists a positive density of integral n-tuples m = (m ₁, . . . , m _n ) in the hypercube max |m _i | ≤ x such that every prime divisor of F(m) is smaller than x ^d–δ . This result is improved when F satisfies some geometrical hypotheses.     

Averaging distances in real quasihypermetric Banach spaces of finite dimension

The average distance theorem of Gross implies that for each realN-dimensional Banach space (N≥2) there is a unique positive real numberr(E) with the following property: For each positive integern and for all (not necessarily distinct)x ₁,x ₂, …,x _n inE with ‖x ₁‖=‖x ₂‖=…=‖x _n‖=1, there exists anx inE with ‖x‖=1 such that The main result of this paper shows, thatr(E)≤2−1/N for each realN-dimensional Banach spaceE (N≥2) with the so-called quasihypermetric property (which is equivalent toE isL ¹-embeddable). Moreover, equality holds if and only ifE is isometrically isomorphic to ℝ ^N equipped with the usual 1-norm.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Large deviations for heavy-tailed random sums of independent random variables with dominatedly varying tails

We prove large deviation results on the partial and random sums Sn = ∑i=1n Xi,n≥1; S(t) = ∑i=1N(t) Xi, t≥0, where {N(t);t≥0} are non-negative integer-valued random variables and {Xn;n≥1} are independent non-negative random variables with distribution, Fn, of Xn, independent of {N(t); t≥0}. Special attention is paid to the distribution of dominated variation.     

A general Hobby-Rice Theorem and cake cutting

LetX be a Borel subset of a separable Banach spaceE. Letμ be a non-atomic,σ-finite, Borel measure onX. LetG ⊆L ₁ (X, Σ,μ) bem-dimensional. Theorem:There is an l ∈ E* and real numbers −∞=x ₀<x ₁<x ₂<…<x _n<x _n+1=∞with n≤m, such that for all g ∈ G,      

Some path properties of generalized Lévy sheet

Let X(t) be an N parameter generalized Lévy sheet taking values in ℝ^d with a lower index α, ℜ = {(s, t] = ∏ _i=1 ^N (s _i, t _i], s _i < t _i}, E(x, Q) = {t ∈ Q: X(t) = x}, Q ∈ ℜ be the level set of X at x and X(Q) = {x: ∃t ∈ Q such that X(t) = x} be the image of X on Q. In this paper, the problems of the existence and increment size of the local times for X(t) are studied. In addition, the Hausdorff dimension of E(x, Q) and the upper bound of a uniform dimension for X(Q) are also established.