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.     

On the range of the derivative of Gâteaux-smooth functions on separable banach spaces

We prove that there exists a Lipschitz function froml ¹ into ℝ² which is Gateaux-differentiable at every point and such that for everyx, y εl ¹, the norm off′(x) −f′(y) is bigger than 1. On the other hand, for every Lipschitz and Gateaux-differentiable function from an arbitrary Banach spaceX into ℝ and for everyε > 0, there always exist two pointsx, y εX such that ‖f′(x) −f′(y)‖ is less thanε. We also construct, in every infinite dimensional separable Banach space, a real valued functionf onX, which is Gateaux-differentiable at every point, has bounded non-empty support, and with the properties thatf′ is norm to weak* continuous andf′(X) has an isolated pointa, and that necessarilya ε 0. This work has been initiated while the second-named author was visiting the University of Bordeaux. The second-named author is supported by grant AV 1019003, A1 019 205, GA CR 201 01 1198.     

Analogues of the “zero-two” law for positive linear contractions inL p andC(X)

LetT be a positive linear contraction inL ^p (1≦p<∞), then we show that lim ‖T ^pf −T ⁿ⁺¹ f‖ _p ≦(1 − ε)2^1/p (f∈L _p ⁺ , ε>0 independent off) implies already lim_n n→∞ ‖T ⁿf −T ⁿ⁺¹ n+1f ‖_p p=0. Several other related results as well as uniform variants of these are also given. Finally some similar results inLsu/t8 andC(X) are shown.     

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 ₁.     

Norms of powers of absolutely convergent fourier series

Letf(t) = ∑a _k e ^ikt be infinitely differentiable on R, |f(t)|<1. It is known that under these assumptions ‖ⁿ‖ converges to a finite limitl asn → ∞ (l ² = sec(arga),a = (f′(0))² -f″(0)). We obtain here more precise results: (i) an asymptotic series (in powers ofn ^-1/2) for the Fourier coefficientsa _nk off ⁿ , which holds uniformly ink asn → ∞; (ii) an asymptotic series (this time only powers ofn ^-1 are present!) for ‖f ⁿ ‖; (iii) the fact that ifi ^j f ^(j)(0) is real forj = 1,2,..., 2h + 2 then ‖f ⁿ ‖ = l + o(n ^-h ),n → ∞. More generally, we obtain analogous finite asymptotic expansions whenf is assumed to be differentiable only finitely many times.     

Rearrangement invariant norms of symmetric sequence norms of independent sequences of random variables

LetX ₁,X ₂, …,X _n be a sequence of independent random variables, letM be a rearrangement invariant space on the underlying probability space, and letN be a symmetric sequence space. This paper gives an approximate formula for the quantity ‖‖(X _i )‖ _N ‖ _M wheneverL _q embeds intoM for some 1≤q<∞. This extends work of Johnson and Schechtman who tackled the case whenN=ℓ _p , and recent work of Gordon, Litvak, Schütt and Werner who obtained similar results for Orlicz spaces. The author was partially supported by NSF grant DMS 9870026, and a grant from the Research Office of the University of Missouri.     

Almost automorphic solutions to integral equations on the line

Given a∈L ¹(ℝ) and A the generator of an L ¹-integrable family of bounded and linear operators defined on a Banach space X, we prove the existence of almost automorphic solution to the semilinear integral equation u(t)=∫ _−∞ ^t a(t−s)[Au(s)+f(s,u(s))]ds for each f:ℝ×X→X almost automorphic in t, uniformly in x∈X, and satisfying diverse Lipschitz type conditions. In the scalar case, we prove that a∈L ¹(ℝ) positive, nonincreasing and log-convex is already sufficient.     

Convergence of mock Fourier series

For certain Cantor measures μ on ℝⁿ, it was shown by Jorgensen and Pedersen that there exists an orthonormal basis of exponentialse ^2πiγ·x for λεΛ. a discrete subset of ℝⁿ called aspectrum for μ. For anyL ¹ functionf, we define coefficientsc _γ(f)=∝f(y)e ^−2πiγiy dμ(y) and form the Mock Fourier series ∑_λ∈Λ^cλ(f)e ^2πiλ·x . There is a natural sequence of finite subsets Λ_n increasing to Λ asn→∞, and we define the partial sums of the Mock Fourier series by We prove, under mild technical assumptions on μ and Λ, thats _n(f) converges uniformly tof for any continuous functionf and obtain the rate of convergence in terms of the modulus of continuity off. We also show, under somewhat stronger hypotheses, almost everywhere convergence forfεL ¹. Research supported in part by the National Science Foundation, Grant DMS-0140194.     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Hardy spaces via distribution spaces

Let ℐ(ℝⁿ) be the Schwartz class on ℝⁿ and ℐ_∞(ℝⁿ) be the collection of functions ϕ ∊ ℐ(ℝⁿ) with additional property that

Multi-parameter singular radon transforms I: The <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript> theory

The purpose of this paper is to study the L ² boundedness of operators of the form f ↦ ψ(x) ∫ f (γ _t (x))K(t)dt, where γ _t (x) is a C ^∞ function defined on a neighborhood of the origin in (t, x) ∈ ℝ ^N × ℝ ⁿ , satisfying γ ₀(x) ≡ x, ψ is a C ^∞ cut-off function supported on a small neighborhood of 0 ∈ ℝ ⁿ , and K is a “multi-parameter singular kernel” supported on a small neighborhood of 0 ∈ ℝ ^N . The goal is, given an appropriate class of kernels K, to give conditions on γ such that every operator of the above form is bounded on L ². The case when K is a Calderón-Zygmund kernel was studied by Christ, Nagel, Stein, and Wainger; we generalize their conditions to the case when K has a “multi-parameter” structure. For example, when K is given by a “product kernel.” Even when K is a Calderón- Zygmund kernel, our methods yield some new results. This is the first paper in a three part series, the later two of which are joint with E. M. Stein. The second paper deals with the related question of L ^p boundedness, while the third paper deals with the special case when γ is real analytic.     

Asymptotic behavior of nonexpansive mappings in normed linear spaces

LetT be a nonexpansive mapping on a normed linear spaceX. We show that there exists a linear functional.f, ‖f‖=1, such that, for allx∈X, lim_n→x f(T ⁿ x/n)=lim_n→x‖T ⁿ x/n ‖=α, where α≡inf _y∈c ‖Ty-y‖. This means, ifX is reflexive, that there is a faceF of the ball of radius α to whichT ⁿ x/n converges weakly for allx (inf_z∈f g(T ⁿ x/n-z)→0, for every linear functionalg); ifX is strictly conves as well as reflexive, the convergence is to a point; and ifX satisfies the stronger condition that its dual has Fréchet differentiable norm then the convergence is strong. Furthermore, we show that each of the foregoing conditions on X is satisfied if and only if the associated convergence property holds for all nonexpansiveT. Supported by National Science Foundation Grant MCS-79-066.     

Estimates of the periods of periodic points for nonexpansive operators

Suppose thatE is a finite-dimensional Banach space with a polyhedral norm ‖·‖, i.e., a norm such that the unit ball inE is a polyhedron. ℝ ⁿ with the sup norm or ℝ ⁿ with thel ₁-norm are important examples. IfD is a bounded set inE andT:D→D is a map such that ‖T(y)−T(z)‖≤ ‖y−z‖ for ally andz inE, thenT is called nonexpansive with respect to ‖·‖, and it is known that for eachx ∈D there is an integerp=p(x) such that lim _j→∞ T ^jp (x) exists. Furthermore, there exists an integerN, depending only on the dimension ofE and the polyhedral norm onE, such thatp(x)≤N: see [1,12,18,19] and the references to the literature there. In [15], Scheutzow has raised a question about the optimal choice ofN whenE=ℝ ⁿ ,D=K ⁿ , the set of nonnegative vectors in ℝ ⁿ , and the norm is thel ₁-norm. We provide here a reasonably sharp answer to Scheutzow’s question, and in fact we provide a systematic way to generate examples and use this approach to prove that our estimates are optimal forn≤24. See Theorem 2.1, Table 2.1 and the examples in Section 3. As we show in Corollary 2.3, these results also provide information about the caseD=ℝ ⁿ , i.e.,T:ℝ ⁿ →ℝ ⁿ isl ₁-nonexpansive. In addition, it is conjectured in [12] thatN=2 ⁿ whenE=ℝ ⁿ and the norm is the sup norm, and such a result is optimal, if true. Our theorems here show that a sharper result is true for an important subclass of nonexpansive mapsT:(ℝ ⁿ ,‖ · ‖_∞)→(ℝ ⁿ ,‖ · ‖_∞). Partially supported by NSF DMS89-03018.     

The range of a projection of small norm inl 1 n

It is proved that there exists a positive function Φ(∈) defined for sufficiently small ∈ 〉 0 and satisfying lim_t→0 Φ(∈) =0 such that for any integersn 〉>0, ifQ is a projection ofl ₁ ⁿ onto ak-dimensional subspaceE with ‖|Q‖|≦1+∈ then there is an integerh〉=k(1−Φ(∈)) and anh-dimensional subspaceF ofE withd(F,l ₁ ^h ) 〈= 1+Φ (∈) whered(X, Y) denotes the Banach-Mazur distance between the Banach spacesX andY. Moreover, there is a projectionP ofl ₁ ⁿ ontoF with ‖|P‖| ≦1+Φ(∈). Author was partially supported by the N.S.F. Grant MCS 79-03042.     

Generalization of one Poletskii lemma to classes of space mappings

The paper is devoted to investigations in the field of space mappings. We prove that open discrete mappings f ∈ W ^1,n _loc such that their outer dilatation K _O (x, f) belongs to L ⁿ⁻¹ _loc and the measure of the set B _f of branching points of f is equal to zero have finite length distortion. In other words, the images of almost all curves γ in the domain D under the considered mappings f : D → ℝ ⁿ , n ≥ 2, are locally rectifiable, f possesses the (N)-property with respect to length on γ, and, furthermore, the (N)-property also holds in the inverse direction for liftings of curves. The results obtained generalize the well-known Poletskii lemma proved for quasiregular mappings.     

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 ∑.     

On functions with the cauchy difference bounded by a functional. III

We are going to discuss special cases of a conditional functional inequality

Recurrence in unipotent groups and ergodic nonabelian group extensions

LetT be a measure-preserving and ergodic transformation of a standard probability space (X,S, μ) and letf:X → SUT _d (ℝ) be a Borel map into the group of unipotent upper triangulard ×d matrices. We modify an argument in [12] to obtain a sufficient condition for the recurrence of the random walk defined byf, in terms of the asymptotic behaviour of the distributions of the suitably scaled mapsf(n,x)=(fT ⁿ⁻¹·fT ⁿ⁻²…fT·f). We give examples of recurrent cocycles with values in the continuous Heisenberg group H₁(ℝ)=SUT₃(ℝ), and we use a recurrent cocycle to construct an ergodic skew-product extension of an irrational rotation by the discrete Heisenberg group H₁(ℤ)=SUT₃(ℤ). The author was partially supported by the FWF research project P16004-MAT.     

Extension of Floquet''''s theory to nonlinear quasiperiodic differential equations

In this paper, we consider the following autonomous system of differential equations: x = Ax f(x,θ), θ = ω, where θ∈Rm, ω = (ω1,…,ωm) ∈ Rm, x ∈ Rn, A ∈ Rn×n is a constant matrix and is hyperbolic, f is a C∞ function in both variables and 2π-periodic in each component of the vector e which satisfies f = O(||x||2) as x → 0. We study the normal form of this system and prove that under some proper conditions this system can be transformed to an autonomous system: x = Ax g(x), θ = ω. Additionally, the proof of this paper naturally implies the extension of Chen's theory in the quasi-periodic case.     

The Fourier transform of order statistics with applications to Lorentz spaces

We present a formula for the Fourier transforms of order statistics in ℝ ⁿ showing that all these Fourier transforms are equal up to a constant multiple outside the coordinate planes in ℝ ⁿ . Fora ₁≥...≥a _n≥0 andq>0, denote by ℓ _w,q ⁿ then-dimensional Lorentz space with the norm ‖(x ₁,...,x _n)‖=(a ₁(x ₁ ^* ) ^q +...+a _n(x _n ^* ) ^q )^1/q , where (x ₁ ^* ,...,x _n ^* ) is the non-increasing permutation of the numbers |x ₁|,...,|x _n|. We use the above mentioned formula and the Fourier transform criterion of isometric embeddability of Banach spaces intoL _q [10] to prove that, forn≥3 andq≤1, the space ℓ _w,q ⁿ is isometric to a subspace ofL _q if and only if the numbersa ₁,...,a _n form an arithmetic progression. Forq>1, all the numbersa _i must be equal so that ℓ _w,q ⁿ = ℓ _q ⁿ . Consequently, the Lorentz function spaceL _w,q(0, 1) is isometric to a subspace ofL _q if and only ifeither 0<q<∞ and the weightw is a constant function (so thatL _w,q=L_q),or q≤1 andw(t) is a decreasing linear function. Finally, we relate our results to the theory of positive definite functions. Both authors were supported in part by the NSF Workshop in Linear Analysis and Probability held at Texas A&M University in August 1993. The work was done during the first author’s visit to Texas A&M University.