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.     

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.     

Onp-absolutely summing constants of banach spaces

Given 1≦p<∞ and a real Banach spaceX, we define thep-absolutely summing constantμ _p(X) as inf{Σ _i ^=1/m |x*(x _i)|^p p Σ _i ^=1/m ‖x _i‖^p p]¹ p}, where the supremum ranges over {x*∈X*; ‖x*‖≤1} and the infimum is taken over all sets {x ₁,x ₂, …,x _m} ⊂X such that Σ _i ^=1/m ‖x _i‖>0. It follows immediately from [2] thatμ _p(X)>0 if and only ifX is finite dimensional. In this paper we find the exact values ofμ _p(X) for various spaces, and obtain some asymptotic estimates ofμ _p(X) for general finite dimensional Banach spaces. This is a part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Prof. A. Dvoretzky and Prof. J. Lindenstrauss.     

On a problem of spencer

LetX ₁, ...,X _n be events in a probability space. Let ϱ_i be the probabilityX _i occurs. Let ϱ be the probability that none of theX _i occur. LetG be a graph on [n] so that for 1 ≦i≦n X _i is independent of ≈X _j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ₁, ..., ϱ _n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) ^d−1 d ^−d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ _i andG.     

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.     

Uniform boundedness of (<Emphasis Type="Italic">C</Emphasis>, 1) means of Jacobi expansions in weighted sup norms. I (The main theorems and ideas)

Lubinsky and Totik’s decomposition [11] of the Cesàro operators σ _n ^(α,β) of Jacobi expansions is modified to prove uniform boundedness in weighted sup norms, i.e., ‖w ^(a,b) σ _n ^(α,β) ‖_∞ ≦ C‖w ^(a,b) f‖_∞, whenever α,β ≧ −1/2 and a, b are within the square around (α/2 + 1/4, α/2 + 1/4) having a side length of 1. This approach uses only classical results from the theory of orthogonal polynomials and various estimates for the Jacobi weights. The present paper is concerned with the main theorems and ideas, while a second paper [7] provides some necessary estimations.      

L p − Lq estimates for convolution operators with n-Dimensional singular measures

Let S ⊂ ℜⁿ⁺¹ be the graph of the function ϕ :[−1, 1] ⁿ → ℜ defined by ϕ (x ₁ , …, x_n) = ∑ _j=1 ⁿ |x_j|^αj, with1<α ₁ ≤ … ≤ α_n, let σ the Euclidean area measure on S. In this article we study the L^p − L^q boundedness of convolution operators with the singular Borel measure on Rⁿ⁺¹ given by μ (E)=σ (E ∩ S)     

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.     

Universal PI-algebras and algebras of generic matrices

Let Ω[ξ] denote the polynomial algebra (with 1) in commutative indeterminates {ie65-1}, 1 ≦i, j ≦n, 1 ≦k < ∞, over a commutative ring Ω. Thealgebra of generic matrices Ω [Y] is defined to be the Ω-subalgebra ofM _n (Ω[ξ]) generated by the matricesY _k=({ie65-2}), 1 ≦i, j ≦n, 1 ≦k < ∞. This algebra has been studied extensively by Amitsur and by Procesi in particular Amitsur has used it to construct a finite dimensional, central division algebra Ω (Y) which is not a crossed product. In this paper we shall prove, for Ω a domain, that Ω(Y) has exponentn in the Brauer group (Amitsur may already know this fact); consequently, for Ω an infinite field andn a multiple of 4, iff(X ₁, …,X _m) is a polynomial linear in all theX _i but one (similar to Formanek’s central polynomials for matrix rings) andf ² is central forM _n (Ω), thenf is central forM _n (Ω). (The existence of a polynomial not central forM _n (Ω), but whose square is central forM _n(Ω) is equivalent to every central division algebra of degreen containing a quadratic extension of its center; well-known theory immediately shows this is the case of 4‖n and 8χn.) Also, information is obtained about Ω(Y) for arbitary Ω, most notably that the Jacobson radical is the set of nilpotent elements. Partial support for this work was provided by National Science Foundation grant NSF-GP 33591.     

An ergodic theorem on Banach lattices

E is a Banach lattice that is weakly sequentially complete and has a weak unitu. TLf _n=ϕ means that the infimum of |f _n−ϕ| andu converges strongly to zero.T is a positive contraction operator onE andA _n=(1/n)(I+T+...+T ⁿ⁻¹). Without an additional assumption onE, the “truncated limit” TLA _nf need not exist forf inE. This limit exists for eachf ifE satisfies the following additional assumption (C): For everyf inE ₊ and for every numberα>0, there is a numberβ=β(f, α) such that ifg is inE ₊, ‖g‖≦1, 0≦f′≦f and ‖f′‖>α then ‖f′+g‖≧‖g‖+β. Research of this author is partially supported by NSERC Grant A3974. Research of this author is partially supported by NSF Grant 8301619.     

Embeddings ofl p m intol ∞ n , 1≦p≦2

Isomorphic embeddings ofl _l ^m intol _∞ ⁿ are studied, and ford(n, k)=inf{‖T ‖ ‖T ⁻¹ ‖;T varies over all isomorphic embeddings ofl ₁ ^[klog2n] intol _∞ ⁿ we have that lim _n→∞ d(n, k)=γ(k)⁻¹,k>1, whereγ(k) is the solution of (1+γ)ln(1+γ)+(1 −γ)ln(1 −γ)=k ⁻¹ln4. Here [x] denotes the integer part of the real numberx.     

On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.     

The zero-two law in Banach lattice algebras

LetA be a unital Banach lattice algebra and leta εA ⁺ satisfy ‖a ‖≦1. Then either ‖a ⁿ⁺¹ −a ⁿ ‖=2 for alln≧0 or else ‖a ⁿ⁺¹ −a ⁿ ‖ → 0 asn → ∞. Cyclicity of the peripheral spectrum ofa is also established.     

Fixed point theorems for non-Lipschitzian mappings of asymptotically nonexpansive type

LetX be a Banach space,K a nonempty, bounded, closed and convex subset ofX, and supposeT:K→K satisfies: for eachx∈K, lim sup _i→∞{sup _y∈K ‖t ⁱx−Tⁱy∼−‖x−y‖}≦0. IfT ^N is continuous for some positive integerN, and if either (a)X is uniformly convex, or (b)K is compact, thenT has a fixed point inK. The former generalizes a theorem of Goebel and Kirk for asymptotically nonexpansive mappings. These are mappingsT:K→K satisfying, fori sufficiently large, ‖Tⁱx−Tⁱy‖≦k _i‖x−y∼,x,y∈K, wherek _i→1 asi→∞. The precise assumption in (a) is somewhat weaker than uniform convexity, requiring only that Goebel’s characteristic of convexity, ɛ₀ (X), be less than one. Research supported by National Science Foundation Grant GP 18045.     

On the ratio of the expected maximum of a martingale and theL p-norm of its last term

For eachp>1, the supremum,S, of the absolute value of a martingale terminating at a random variableX inL _p, satisfiesES≦(Γ(q))^1/q‖X‖_p (q=p(p-1)^-1).The maximum,M, of a mean-zero martingale which starts at zero and terminates atX, satisfiesES≦(Γ(q))^1/q‖X‖_p (q=p(p-1)^-1), whereσ _q is the unique solution of the equationt = ‖Z −t ‖ _q for an exponentially distributed random variableZ with mean 1.σ _p has other characterizations and satisfies lim _p‖ q ^{− 1} σ _q =c withc determined byce ^c+1 = 1. Equalities in (1) and (2) are attainable by appropriate martingales which can be realized as stopped segments of Brownian motion. A presumably new property of the exponential distribution is obtained en route to inequality (2).     

On the divisibility of power LCM matrices by power GCD matrices

Let S = {x ₁, ..., x _n } be a set of n distinct positive integers and e ⩾ 1 an integer. Denote the n × n power GCD (resp. power LCM) matrix on S having the e-th power of the greatest common divisor (x _i , x _j ) (resp. the e-th power of the least common multiple [x _i , x _j ]) as the (i, j)-entry of the matrix by ((x _i , x _j ) ^e ) (resp. ([x _i , x _j ] ^e )). We call the set S an odd gcd closed (resp. odd lcm closed) set if every element in S is an odd number and (x _i , x _j ) ∈ S (resp. [x _i , x _j ] ∈ S) for all 1 ⩽ i, j ⩽ n. In studying the divisibility of the power LCM and power GCD matrices, Hong conjectured in 2004 that for any integer e ⩾ 1, the n × n power GCD matrix ((x _i , x _j ) ^e ) defined on an odd-gcd-closed (resp. odd-lcm-closed) set S divides the n × n power LCM matrix ([x _i , x _j ] ^e ) defined on S in the ring M _n (ℤ) of n × n matrices over integers. In this paper, we use Hong’s method developed in his previous papers [J. Algebra 218 (1999) 216–228; 281 (2004) 1–14, Acta Arith. 111 (2004), 165–177 and J. Number Theory 113 (2005), 1–9] to investigate Hong’s conjectures. We show that the conjectures of Hong are true for n ⩽ 3 but they are both not true for n ⩾ 4. Research is partially supported by Program for New Century Excellent Talents in University, by SRF for ROCS, SEM, China and by the Lady Davis Fellowship at the Technion, Israel Research is partially supported by a UGC (HK) grant 2160210 (2003/05).     

Smooth convex bodies with proportional projection functions

For a convex body K ⊂ ℝⁿ and i ∈ {1, …, n − 1}, the function assigning to any i-dimensional subspace L of ℝⁿ, the i-dimensional volume of the orthogonal projection of K to L, is called the i-th projection function of K. Let K, K ₀ ⊂ ℝⁿ be smooth convex bodies with boundaries of class C ² and positive Gauss-Kronecker curvature and assume K ₀ is centrally symmetric. Excluding two exceptional cases, (i, j) = (1, n − 1) and (i, j) = (n − 2, n − 1), we prove that K and K ₀ are homothetic if their i-th and j-th projection functions are proportional. When K ₀ is a Euclidean ball this shows that a convex body with C ² boundary and positive Gauss-Kronecker with constant i-th and j-th projection functions is a Euclidean ball. The second author was supported in part by the European Network PHD, FP6 Marie Curie Actions, RTN, Contract MCRN-511953.     

Formulas for best extrapolation

We considern-point Lagrange-Hermite extrapolation forf(x), x>1, based uponf(x _i ),i=1(1)n, –1x _i 1, including non-distinct pointsx _i in confluent formulas involving derivatives. The problem is to find the pointsx _i that minimize the factor in the remainderP _n (x)f ⁽ⁿ⁾()/n, –1<<x subject to the condition|P _n (x)|M, –1x1,2^–n+1M2 ⁿ . The solution is significant only when a single set of pointsx _i suffices for everyx>1. The problem is here completely solved forn=1(1)4. Forn>4 it may be conjectured that there is a single minimal , 0 rn, whererr(M) is a non-decreasing function ofM, P _n (–1)=(–1) ⁿ M, and for 0rn–2, thej-th extremumP _n (x _{e, j} )=(–1) ^n–j M,j=1(1)n–r–1 (except forM=M _r ,r=1(1)n–1, whenj=1(1)n–r).     

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.     

The solution of graham’s greatest common divisor problem

The following conjecture of R. L. Graham is verified: Ifn≧n ₀, wheren ₀ is an explicitly computable constant, then for anyn distinct positive integersa ₁,a ₂, ...,a _n we have a _i /(a _i ,a _j ) ≧ ≧n, and equality holds only in two trivial cases. Here (a _i ,a _j ) stands for the greatest cnmmon divisor ofa _i anda _j .