Positive definite functions and stable random vectors

We say that a random vector X = (X ₁, …, X _n ) in ℝ ⁿ is an n-dimensional version of a random variable Y if, for any a ∈ ℝ ⁿ , the random variables Σa _i X _i and γ(a)Y are identically distributed, where γ: ℝ ⁿ → [0,∞) is called the standard of X. An old problem is to characterize those functions γ that can appear as the standard of an n-dimensional version. In this paper, we prove the conjecture of Lisitsky that every standard must be the norm of a space that embeds in L ₀. This result is almost optimal, as the norm of any finite-dimensional subspace of L _p with p ∈ (0, 2] is the standard of an n-dimensional version (p-stable random vector) by the classical result of P. Lèvy. An equivalent formulation is that if a function of the form f(‖ · ‖ _K ) is positive definite on ℝ ⁿ , where K is an origin symmetric star body in ℝ ⁿ and f: ℝ → ℝ is an even continuous function, then either the space (ℝ ⁿ , ‖·‖ _K ) embeds in L ₀ or f is a constant function. Combined with known facts about embedding in L ₀, this result leads to several generalizations of the solution of Schoenberg’s problem on positive definite functions.     

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.     

A logarithmic lower bound for multi-dimensional bohr radii

We prove that the Bohr radiusK _n of then-dimensional polydisc in ℂ ⁿ is up to an absolute constant ≥ √logn/log logn/n. This improves a result of Boas and Khavinson.     

Packing random rectangles

A random rectangle is the product of two independent random intervals, each being the interval between two random points drawn independently and uniformly from [0,1]. We prove that te number C _n of items in a maximum cardinality disjoint subset of n random rectangles satisfies

Multipliers for logarithmic Cauchy integrals in the ball

Let B _n denote the unit ball in \mathbbC \mathbb{C} ⁿ , n ≥ 1. Let K \mathcal{K} ₀(n) denote the class of functions defined for z ∈ B _n as a constant plus the integral of the kernel log(1/(1 −〈z, ζ〉)) against a complex Borel measure on the sphere {ζ ∈ \mathbbC \mathbb{C} ⁿ ,: |ζ| = 1}. Properties of holomorphic functions g such that fg ∈ K \mathcal{K} ₀(n) for all f ∈ K \mathcal{K} ₀(n) are studied. The extended Cesàro operators are investigated on the spaces K \mathcal{K} ₀(n), n ≥ 1. Bibliography: 15 titles.     

Bernoulli convolutions and an intermediate value theorem for entropies of<Emphasis Type="Italic">K</Emphasis>-partitions

We establish a strong regularity property for the distributions of the random sums Σ±λ ⁿ , known as “infinite Bernoulli convolutions”: For a.e. λ ∃ (1/2, 1) and any fixed ℓ, the conditional distribution of (w _n+1...,w _n+ℓ) given the sum Σ _n=0 ^∞ w _n λ ⁿ , tends to the uniform distribution on {±1}^ℓ asn → ∞. More precise results, where ℓ grows linearly inn, and extensions to other random sums are also obtained. As a corollary, we show that a Bernoulli measure-preserving system of entropyh hasK-partitions of any prescribed conditional entropy in [0,h]. This answers a question of Rokhlin and Sinai from the 1960’s, for the case of Bernoulli systems. The authors were partially supported by NSF grants DMS-9729992 (E. L.), DMS-9803597 (Y. P.) and DMS-0070538 (W. S.).     

Restricted Isometry Property of Matrices with?Independent Columns and Neighborly Polytopes by?Random Sampling

This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors ±X ₁,…,±X _N ∈ℝ ⁿ , (N≥n). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a subexponential tail inequality possess the restricted isometry property with overwhelming probability. We show that such “sensing” matrices are valid for the exact reconstruction process of m-sparse vectors via ℓ ₁ minimization with m≤Cn/log ²(cN/n). The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if K⊂ℝ ⁿ is a convex body and X ₁,…,X _N ∈K are i.i.d. random vectors uniformly distributed on K, then, with overwhelming probability, the symmetric convex hull of these points is an m-centrally-neighborly polytope with m∼n/log ²(cN/n).     

On the Diaconis-Shahshahani Method in Random Matrix Theory

If Γ is a random variable with values in a compact matrix group K, then the traces Tr(Γ^j) (j ∊ N) are real or complex valued random variables. As a crucial step in their approach to random matrix eigenvalues, Diaconis and Shahshahani computed the joint moments of any fixed number of these traces if Γ is distributed according to Haar measure and if K is one of U_n, O_n or Sp_n, where n is large enough. In the orthogonal and symplectic cases, their proof is based on work of Ram on the characters of Brauer algebras. The present paper contains an alternative proof of these moment formulae. It invokes classical invariant theory (specifically, the tensor forms of the First Fundamental Theorems in the sense of Weyl) to reduce the computation of matrix integrals to a counting problem, which can be solved by elementary means.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

Small generators of number fields

If K is a number field of degree n over Q with discriminant D _K and if α∈K generates K, i.e. K=Q(α), then the height of α satisfies with . The paper deals with the existence of small generators of number fields in this sense. We show: (1) For each $n$ there are infinitely many number fields K of degree $n$ with a generator α such that . (2) There is a constant d ² such that every imaginary quadratic number field has a generator α which satisfies .?(3) If K is a totally real number field of prime degree n then one can find an integral generator α with . Received: 10 January 1997 / Revised version: 13 January 1998     

Tubes and eigenvalues for negatively curved manifolds

We investigate the structure of the spectrum near zero for the Laplace operator on a complete negatively curved Riemannian manifoldM. If the manifold is compact and its sectional curvaturesK satisfy 1 ≤K < 0, we show that the smallest positive eigenvalue of the Laplacian is bounded below by a constant depending only on the volume ofM. Our result for a complete manifold of finite volume with sectional curvatures pinched between −a² and −1 asserts that the number of eigenvalues of the Laplacian between 0 and (n− 1)²/4 is bounded by a constant multiple of the volume of the manifold with the constant depending ona and the dimension only. Research supported in part by the Swiss National Science Foundation, the US National Science Foundation, and the PSC-CUNY Research Award Program.     

Large subspaces ofl ∞ n and estimates of the gordon-lewis constantand estimates of the gordon-lewis constant

Lower bounds are obtained for thegl constants and hence also for the unconditional basis constants of subspaces of finite dimensional Banach spaces. Sharp results are obtained for subspaces ofl _∞ ⁿ , while in the general case thegl constants of “random large” subspaces are related to the distance of “random large” subspaces to Euclidean spaces. In addition, a new isometric characterization ofl _∞ ⁿ is given, some new information is obtained concerningp-absolutely summing operators, and it is proved that every Banach space of dimensionn contains a subspace whose projection constant is of ordern ^1/2. The research for this paper was begun while both authors were guests of the Mittag-Leffler Institute. Supported in part by NSF-MCS 79-03042.     

Commutators in model spaces

Let θ be an inner function, let K _θ = H ² ⊖ θH ², and let S_θ : K_θ → S_θ be defined by the formula S_θf = P_θzf, where f ∈ K_θ is the orthogonal projection of H² onto K_θ. Consider the set A of all trace class operators L : K_θ → K_θ, L = ∑(·,u_n)v_n, ∑∥u_n∥∥v_n∥ < ∞ (u_n, v_n ∈ K_θ), such that ∑ū_n v_n ∈ H ₀ ¹ . It is shown that trace class commutators of the form XS_θ − S_θX (where X is a bounded linear operator on K_θ) are dense in A in the trace class norm. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 333, 2006, pp. 54–61.     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

Expectation of intrinsic volumes of random polytopes

Let K be a convex body in ℝ ^d , let j ∈ {1, …, d−1}, and let K(n) be the convex hull of n points chosen randomly, independently and uniformly from K. If ∂K is C ₊², then an asymptotic formula is known due to M. Reitzner (and due to I. Bárány if ∂K is C ₊³) for the difference of the jth intrinsic volume of K and the expectation of the jth intrinsic volume of K(n). We extend this formula to the case when the only condition on K is that a ball rolls freely inside K. Funded by the Marie-Curie Research Training Network “Phenomena in High-Dimensions” (MRTN-CT-2004-511953).     

Nonparametric estimation of mean and variance when a few “sample” values possibly outliers

The data (continuous) aren independent observations that are believed to be a random sample. The possibility exists, however, that as many asJ of the largest observations, and as many asK of the smallest observations, are outliers. That is, these observations are from populations that are different from the population yielding the other observations (which number at leastn−J−K). The interest is in obtaining suitable estimates for the mean and variance of the population yielding the other observations.J andK are given and relatively small, with both ≦2n ^A , whereA is specified and ≦1/4. When the population yielding the other observations is continuous, has moments of all orders, and is well-behaved in some other ways, estimates are developed that are unbiased if terms of ordern ^−1+A +2ɛ are neglected. Here, ɛ can be arbitrarily small but is positive. Research partially supported by NASA Grant NGR 44-007-028 and by Mobil Research and Development Corporation. Also associated with ONR Contract N00014-68-A-0515 and Dept. of Labor Grant 31-46-70-06.     

The structure of some classes of <Emphasis Type="Italic">K</Emphasis>-contact manifolds

We study projective curvature tensor in K-contact and Sasakian manifolds. We prove that (1) if a K-contact manifold is quasi projectively flat then it is Einstein and (2) a K-contact manifold is ξ-projectively flat if and only if it is Einstein Sasakian. Necessary and sufficient conditions for a K-contact manifold to be quasi projectively flat and φ-projectively flat are obtained. We also prove that for a (2n + 1)-dimensional Sasakian manifold the conditions of being quasi projectively flat, φ-projectively flat and locally isometric to the unit sphere S ²ⁿ⁺¹ (1) are equivalent. Finally, we prove that a compact φ-projectively flat K-contact manifold with regular contact vector field is a principal S ¹-bundle over an almost Kaehler space of constant holomorphic sectional curvature 4.     

From the Mahler Conjecture to Gauss Linking Integrals

We establish a version of the bottleneck conjecture, which in turn implies a partial solution to the Mahler conjecture on the product v(K)  = (Vol K)(Vol K°) of the volume of a symmetric convex body and its polar body K°. The Mahler conjecture asserts that the Mahler volume v(K) is minimized (non-uniquely) when K is an n-cube. The bottleneck conjecture (in its least general form) asserts that the volume of a certain domain is minimized when K is an ellipsoid. It implies the Mahler conjecture up to a factor of (π/4) ⁿ γ _n , where γ _n is a monotonic factor that begins at 4/π and converges to . This strengthens a result of Bourgain and Milman, who showed that there is a constant c such that the Mahler conjecture is true up to a factor of c ⁿ . The proof uses a version of the Gauss linking integral to obtain a constant lower bound on Vol K ^◇, with equality when K is an ellipsoid. It applies to a more general conjecture concerning the join of any two necks of the pseudospheres of an indefinite inner product space. Because the calculations are similar, we will also analyze traditional Gauss linking integrals in the sphere S ^n-1 and in hyperbolic space H ^n-1. Received: December 2006, Accepted: January 2007     

Polynomial bounds for Large Bernoulli sections of ℓ 1 N

We present a quantitative form of the result of Bai and Yin from [2], and use to show that the section of ℓ ₁ ^(1+δ)n spanned byn random independent sign vectors is with high probability isomorphic to euclidean with isomorphism constant polynomial in δ⁻¹. Partially supported by BSF grant 2002-006. Supported by the National Science Foundation under agreement No. DMS-0111298. Supported in part by the Israel Science Academy.     

On K 1,k -factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.