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.     

Orthogonal factorizations of digraphs

Let G be a digraph with vertex set V(G) and arc set E(G) and let g = (g ⁻, g ⁺) and ƒ = (ƒ ⁻, ƒ ⁺) be pairs of positive integer-valued functions defined on V(G) such that g ⁻(x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ ƒ ⁺(x) for each x ∈ V(G). A (g, ƒ)-factor of G is a spanning subdigraph H of G such that g ⁻(x) ⩽ id _H (x) ⩽ ƒ ⁻(x) and g ⁺(x) ⩽ od _H (x) ⩽ ƒ ⁺(x) for each x ∈ V(H); a (g, ƒ)-factorization of G is a partition of E(G) into arc-disjoint (g, ƒ)-factors. Let = {F ₁, F ₂,…, F _m} and H be a factorization and a subdigraph of G, respectively. is called k-orthogonal to H if each F _i , 1 ⩽ i ⩽ m, has exactly k arcs in common with H. In this paper it is proved that every (mg+m−1,mƒ−m+1)-digraph has a (g, f)-factorization k-orthogonal to any given subdigraph with km arcs if k ⩽ min{g ⁻(x), g ⁺(x)} for any x ∈ V(G) and that every (mg, mf)-digraph has a (g, f)-factorization orthogonal to any given directed m-star if 0 ⩽ g(x) ⩽ f(x) for any x ∈ V(G). The results in this paper are in some sense best possible.      

Penultimate limiting forms in extreme value theory

Summary Let {X _n}_n≧1 be a sequence of independent, identically distributed random variables. If the distribution function (d.f.) ofM _n=max (X ₁,…,X _n), suitably normalized with attraction coefficients {α_n}_n≧1(α_n>0) and {b _n}_n≧1, converges to a non-degenerate d.f.G(x), asn→∞, it is of interest to study the rate of convergence to that limit law and if the convergence is slow, to find other d.f.'s which better approximate the d.f. of(M _n−b_n)/a_n thanG(x), for moderaten. We thus consider differences of the formF ⁿ(a_nx+b_n)−G(x), whereG(x) is a type I d.f. of largest values, i.e.,G(x)≡Λ(x)=exp (-exp(−x)), and show that for a broad class of d.f.'sF in the domain of attraction of Λ, there is a penultimate form of approximation which is a type II [Ф _α(x)=exp (−x^−α), x>0] or a type III [Ψ _α(x)= exp (−(−x)^α), x<0] d.f. of largest values, much closer toF ⁿ(a_nx+b_n) than the ultimate itself.     

Regression of polynomial statistics on the sample mean and natural exponential families

A polynomial Q = Q(X ₁, …, X _n ) of degree m in independent identically distributed random variables with distribution function F is an unbiased estimator of a functional q(α ₁(F), …, α _m (F)), where q(u ₁, …, u _m ) is a polynomial in u ₁, …, u _m and α _j (F) is the jth moment of F (assuming the necessary moment of F exists). It is shown that the relation E(Q | X ₁ + … + X n) = 0 holds if and only if q(α ₁(θ), …, α _m (θ)) ≡ 0, where α _j (θ) is the jth moment of the natural exponential family generated by F. This result, based on the fact that X ₁ + … + X n is a complete sufficient statistic for a parameter θ in a sample from a natural exponential family of distributions F _θ(x) = ∫_−∞ ^x e ^θu−k(θ) dF(u), explains why the distributions appearing as solutions of regression problems are the same as solutions of problems for natural exponential families though, at the first glance, the latter seem unrelated to the former.     

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     

Affine cross-polytopes inscribed in a convex body

Let X be an affine cross-polytope, i.e., the convex hull of n segments A ₁ B ₁,…, A _n B _n in \mathbbRⁿ {\mathbb{R}^n} that have a common midpoint O and do not lie in a hyperplane. The affine flag F(X) of X is the chain O ∈ L ₁ ⊂⋯ ⊂ L _n = \mathbbRⁿ {\mathbb{R}^n} , where L _k is the k-dimensional affine hull of the segments A ₁ B ₁,…, A _k B _k , k ≤ n. It is proved that each convex body K ⊂ \mathbbRⁿ {\mathbb{R}^n} is circumscribed about an affine cross-polytope X such that the flag F(X) satisfies the following condition for each k ∈{2,…, n}:the (k−1)-planes of support at A _k and B _k to the body L _k ∩ K in the k-plane L _k are parallel to L _k −1.Each such X has volume at least V(K)/2 ^n(n−1)/2. Bibliography: 5 titles.     

On Hong’s conjecture for power LCM matrices

A set S={x ₁,...,x _n } of n distinct positive integers is said to be gcd-closed if (x _i , x _j ) ∈ S for all 1 ⩽ i, j ⩽ n. Shaofang Hong conjectured in 2002 that for a given positive integer t there is a positive integer k(t) depending only on t, such that if n ⩽ k(t), then the power LCM matrix ([x _i , x _j ] ^t ) defined on any gcd-closed set S={x ₁,...,x _n } is nonsingular, but for n ⩾ k(t) + 1, there exists a gcd-closed set S={x ₁,...,x _n } such that the power LCM matrix ([x _i , x _j ] ^t ) on S is singular. In 1996, Hong proved k(1) = 7 and noted k(t) ⩾ 7 for all t ⩾ 2. This paper develops Hong’s method and provides a new idea to calculate the determinant of the LCM matrix on a gcd-closed set and proves that k(t) ⩾ 8 for all t ⩾ 2. We further prove that k(t) ⩾ 9 iff a special Diophantine equation, which we call the LCM equation, has no t-th power solution and conjecture that k(t) = 8 for all t ⩾ 2, namely, the LCM equation has t-th power solution for all t ⩾ 2.     

On the weak non-defectivity of veronese embeddings of projective spaces

Fix integers n, x, k such that n≥3, k>0, x≥4, (n, x)≠(3, 4) and k(n+1)<( _n ^n+x ). Here we prove that the order x Veronese embedding ofP ⁿ is not weakly (k−1)-defective, i.e. for a general S⊃P ⁿ such that #(S) = k+1 the projective space | I _2S (x)| of all degree t hypersurfaces ofP ⁿ singular at each point of S has dimension ( _n ^/n+x )−1− k(n+1) (proved by Alexander and Hirschowitz) and a general F∈| I _2S (x)| has an ordinary double point at each P∈ S and Sing (F)=S. The author was partially supported by MIUR and GNSAGA of INdAM (Italy).     

Random copy of a segment within a convex domain

Under the assumption that S is a segment of the length l and D is a bounded, convex domain in the Euclidean plane ℝ², the paper considers the randomly moving copy L of S, under the condition that it hits D. Denote by L| the length of L ∩ D. In the paper an elementary expression for the distribution function F _L (x) of the random variable L| is obtained. Note that F _L (x) can have a jump at the point l or can be a continuous function depending on l and the domainD. In particular, a relation between chord length distribution functions of D and F _L (x) is given. Moreover, we derive explicit forms of F _L (x) for the disk and regular n-gons with n = 3÷7.     

Multidimensional version of M. A. Krasnoseľskii’s generalized contraction principle

Let M be a complete K-metric space with n-dimensional metric ρ(x, y): M × M → R ⁿ , where K is the cone of nonnegative vectors in R ⁿ . A mapping F: M → M is called a Q-contraction if ρ (Fx,Fy) ⩽ Qρ (x,y), where Q: K → K is a semi-additive absolutely stable mapping. A Q-contraction always has a unique fixed point x* in M, and ρ(x*,a) ⩽ (I - Q)^-1 ρ(Fa, a) for every point a in M. The point x* can be obtained by the successive approximation method x _k = Fx _k-1, k = 1, 2,..., starting from an arbitrary point x ₀ in M, and the following error estimates hold: ρ (x*, x _k ) ⩽ Q ^k (I - Q)^-1ρ(x ₁, _x ⁰) ⩽ (I - Q)^-1 Q ^k ρ(x ₁, x ₀), k = 1, 2,.... Generally the mappings (I - Q)^-1 and Q ^k do not commute. For n = 1, the result is close to M. A. Krasnosel’skii’s generalized contraction principle.     

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 convergence of a generalized Pál interpolation process

Let f∈C _[−1,1] ^″ (r≥1) and R_n(f,α,β,x) be the generalized Pál interpolation polynomials satisfying the conditions R_n(f,α,β,x_k)=f(x_k),R_n ^′(f,α,β,x_k)=f′(x_k)(k=1,2,…,n), where {x_k} are the roots of n-th Jacobi polynomial P_n(α,β,x),α,β>−1 and {x _k ^″ } are the roots of (1−x²)P_n″(α,β,x). In this paper, we prove that holds uniformly on [0,1]. In Memory of Professor M. T. Cheng Supported by the Science Foundation of CSBTB and the Natural Science Foundatioin of Zhejiang.     

Fractional Poisson equations and ergodic theorems for fractional coboundaries

For a given contractionT in a Banach spaceX and 0<α<1, we define the contractionT _α=Σ _j=1 ^∞ a _j T ^j , where {a _j } are the coefficients in the power series expansion (1-t)^α=1-Σ _j=1 ^∞ a _j t ^j in the open unit disk, which satisfya _j >0 anda _j >0 and Σ _j=1 ^∞ a _j =1. The operator calculus justifies the notation(I−T) ^α :=I−T _α (e.g., (I−T _1/2)²=I−T). A vectory∈X is called an, α-fractional coboundary for T if there is anx∈X such that(I−T) ^α x=y, i.e.,y is a coboundary forT _α . The fractional Poisson equation forT is the Poisson equation forT _α . We show that if(I−T)X is not closed, then(I−T) ^α X strictly contains(I−T)X (but has the same closure). ForT mean ergodic, we obtain a series solution (converging in norm) to the fractional Poisson equation. We prove thaty∈X is an α-fractional coboundary if and only if Σ _k=1 ^∞ T ^k y/k ^1-α converges in norm, and conclude that lim _n ‖(1/n ^1-α)Σ _k=1 ⁿ T ^k y‖=0 for suchy. For a Dunford-Schwartz operatorT onL ₁ of a probability space, we consider also a.e. convergence. We prove that iff∈(I−T) ^α L ₁ for some 0<α<1, then the one-sided Hilbert transform Σ _k=1 ^∞ T ^k f/k converges a.e. For 1<p<∞, we prove that iff∈(I−T) ^α L _p with α>1−1/p=1/q, then Σ _k=1 ^∞ T ^k f/k ^1/p converges a.e., and thus (1/n ^1/p ) Σ _k=1 ⁿ T ^k f converges a.e. to zero. Whenf∈(I−T) ^1/q L _p (the case α=1/q), we prove that (1/n ^1/p (logn)^1/q )Σ _k=1 ⁿ T ^k f converges a.e. to zero.     

Possible limit laws for entrance times of an ergodic aperiodic dynamical system

LetG denote the set of decreasingG: ℝ→ℝ withGэ1 on ]−∞,0], and ƒ ₀ ^∞ G(t)dt⩽1. LetX be a compact metric space, andT: X→X a continuous map. Let μ denone aT-invariant ergodic probability measure onX, and assume (X, T, μ) to be aperiodic. LetU⊂X be such that μ(U)>0. Let τ _U (x)=inf{k⩾1:T ^k xεU}, and defineG _U (t)=1/u(U)u({xεU:u(U)τU(x)>t),tεℝ We prove that for μ-a.e.x∈X, there exists a sequence (U _n ) _n≥1 of neighbourhoods ofx such that {x}=∩ _n U _n , and for anyG ∈G, there exists a subsequence (n _k ) _k≥1 withG _{U n k} ↑U weakly. We also construct a uniquely ergodic Toeplitz flowO(x ^∞,S, μ), the orbit closure of a Toeplitz sequencex ^∞, such that the above conclusion still holds, with moreover the requirement that eachU _n be a cylinder set. In memory of Anzelm Iwanik     

A Lower Bound of <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> Norms in the CLT for Strongly Mixing Random Variables

We derive a lower bound of L _p norms, 1 ⩽ p ⩽ ∞, in the central limit theorem for strongly mixing random variables X ₁,..., X _n with under the boundedness condition ℙ{|X _i | ⩽ M} = 1 with a nonrandom constantM > 0 and condition ∑ _r⩾1 r ²α(r) < ∞, where α(r) are the Rosenblatt strong mixing coefficients. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 4, pp. 587–602, October–December, 2005.     

The density of rational points on non-singular hypersurfaces

LetF(x) =F[x₁,…,x_n]∈ℤ[x₁,…,x_n] be a non-singular form of degree d≥2, and letN(F, X)=#{xεℤ ⁿ ;F(x)=0, |x|⩽X}, where . It was shown by Fujiwara [4] [Upper bounds for the number of lattice points on hypersurfaces,Number theory and combinatorics, Japan, 1984, (World Scientific Publishing Co., Singapore, 1985)] thatN(F, X)≪X ^n−2+2/n for any fixed formF. It is shown here that the exponent may be reduced ton - 2 + 2/(n + 1), forn ≥ 4, and ton - 3 + 15/(n + 5) forn ≥ 8 andd ≥ 3. It is conjectured that the exponentn - 2 + ε is admissable as soon asn ≥ 3. Thus the conjecture is established forn ≥ 10. The proof uses Deligne’s bounds for exponential sums and for the number of points on hypersurfaces over finite fields. However a composite modulus is used so that one can apply the ‘q-analogue’ of van der Corput’s AB process. Dedicated to the memory of Professor K G Ramanathan     

A family of counterexamples in ergodic theory

LetT _α be the translationx↦x+α (mod 1) of [0, 1), α irrational. LetT be the Lebesgue measure-preserving automorphism ofX=[0, 3/2) defined byTx = x + 1 forx∈[0, 1/2),Tx=T _α(x−1) forx∈[1,3/2) andTx = T _α x forx∈[1/2, 1), i.e.T isT _α with a tower of height one built over [0, 1/2). If α is poorly approximable by rationals (there does not exist {p _n /q _n } with |α−p _n /q _n |=o(q _n ⁻²)) and λ is a measure onX ^k all of whose one-dimensional marginals are Lebesgue and which is ⊗ _{i − 1} ^k T ¹ invariant and ergodic (l>0) then λ is a product of off-diagonal measures. This property suffices for many purposes of counterexample construction. A connection is established with the POD (proximal orbit dense) condition in topological dynamics. Research supported in part by NSF contract MCS-8003038.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.