An example of a convex body without symmetric projections

Many crucial results of the asymptotic theory of symmetric convex bodies were extended to the non-symmetric case in recent years. That led to the conjecture that for everyn-dimensional convex bodyK there exists a projectionP of rankk, proportional ton, such thatPK is almost symmetric. We prove that the conjecture does not hold. More precisely, we construct ann-dimensional convex bodyK such that for everyk >C√nlnn and every projectionP of rankk, the bodyPK is very far from being symmetric. In particular, our example shows that one cannot expect a formal argument extending the “symmetric” theory to the general case. This author holds a Lady Davis Fellowship.     

Inspheres and inner products

Among normed linear spacesX of dimension ≧3, finite-dimensional Hilbert spaces are characterized by the condition that for each convex bodyC inX and each ballB of maximum radius contained inC,B’s center is a convex combination of points ofB ∩ (boundary ofC). Among reflexive Banach spaces of dimension ≧3, general Hilbert spaces are characterized by a related but weaker condition on inscribed balls. Research of the first author was partially supported by the U.S. National Science Foundation. Research of the second and third authors was supported by the Consiglio Nazionale delle Ricerche and the Ministero della Pubblica Istruzione of Italy, while they were visiting the University of Washington, Seattle, USA.     

Contact points of convex bodies

LetB be a convex body in ? ⁿ and let ? be an ellipsoid of minimal volume containingB. By contact points ofB we mean the points of the intersection between the boundaries ofB and ?. By a result of P. Gruber, a generic convex body in ? ⁿ has (n+3)·n/2 contact points. We prove that for every ?>0 and for every convex bodyB ? ? ⁿ there exists a convex bodyK having $$m \leqslant C(\varepsilon ) \cdot n\log ^3 n$$ contact points whose Banach-Mazur distance toB is less than 1+?. We prove also that for everyt>1 there exists a convex symmetric body Γ ? ? ⁿ so that every convex bodyD ? ? ⁿ whose Banach-Mazur distance to Γ is less thant has at least (1+c ₀/t ²)·n contact points for some absolute constantc ₀. We apply these results to obtain new factorizations of Dvoretzky-Rogers type and to estimate the size of almost orthogonal submatrices of an orthogonal matrix.     

Expectation of random polytopes

A random polytopeP _n in a convex bodyC is the convex hull ofn identically and independently distributed points inC. Its expectation is a convex body in the interior ofC. We study the deviation of the expectation ofP _n fromC asn→∞: while forC of classC ^k+1,k≥1, precise asymptotic expansions for the deviation exist, the behaviour of the deviation is extremely irregular for most convex bodiesC of classC ¹. Dedicated to my teacher and friend Professor Edmund Hlawka on the occasion of his 80^th birthday     

The lower dimensional Busemann-Petty problem for bodies with the generalized axial symmetry

The lower dimensional Busemann-Petty problem asks, whether n-dimensional centrally symmetric convex bodies with smaller i-dimensional central sections necessarily have smaller volumes. For i = 1, the affirmative answer is obvious. If i > 3, the answer is negative. For i = 2 or i = 3 (n > 4), the problem is still open, however, when the body with smaller sections is a body of revolution, the answer is affirmative. The paper contains a solution to the problem in the more general situation, when the body with smaller sections is invariant under rotations, preserving mutually orthogonal subspaces of dimensions ℓ and n − ℓ, respectively, so that i + ℓ ≤ n. The answer essentially depends on ℓ. The argument relies on the notion of canonical angles between subspaces, spherical Radon transforms, properties of intersection bodies, and the generalized cosine transforms.     

On reduced convex bodies

A convex bodyK ⊂R ^d is called reduced if for each convex bodyK′ ⊂K,K′ ≠K, the width ofK′ is less than the width ofK. We prove that reduced bodyK is of constant width if (i) the bodyK has a supporting sphere almost everywhere in ∂K. (The radius of the sphere may vary with the point in ∂K; the condition (i) and strict convexity do not imply each other.) Supported by an N.S.E.R.C. Grant of Canada.     

The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization

We show the existence of a sequence (λ _n ) of scalars withλ _n =o(n) such that, for any symmetric compact convex bodyB ⊂R ⁿ , there is an affine transformationT satisfyingQ ⊂T(B) ⊂λ _n Q, whereQ is then-dimensional cube. This complements results of the second-named author regarding the lower bound on suchλ _n . We also show that ifX is ann-dimensional Banach space andm=[n/2], then there are operatorsα:l ₂ ^m →X andβ:X→l _∞ ^m with ‖α‖·‖β‖≦C, whereC is a universal constant; this may be called “the proportional Dvoretzky-Rogers factorization”. These facts and their corollaries reveal new features of the structure of the Banach-Mazur compactum. Research performed while this author was visiting IHES. Supported in part by the NSF Grant DMS-8702058 and the Sloan Research Fellowship.     

Rigidity of commutators and elementary operators on Calkin algebras

LetA=(A ₁,...,A _n ),B=(B ₁,...,B _n )εL(ℓ ^p ) ⁿ be arbitraryn-tuples of bounded linear operators on (ℓ ^p ), with 1<p<∞. The paper establishes strong rigidity properties of the corresponding elementary operators ε _a,b on the Calkin algebraC(ℓ ^p )≡L(ℓ ^p )/K(ℓ ^p ); , where quotient elements are denoted bys=S+K(ℓ ^p ) forSεL(ℓ ^p ). It is shown among other results that the kernel Ker(ε _a,b ) is a non-separable subspace ofC(ℓ ^p ) whenever ε _a,b fails to be one-one, while the quotient is non-separable whenever ε _a,b fails to be onto. These results extend earlier ones in several directions: neither of the subsets {A ₁,...,A _n }, {B ₁,...,B _n } needs to consist of commuting operators, and the results apply to other spaces apart from Hilbert spaces. Supported by the Academy of Finland, Project 32837.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Subdivision algorithms and the kernel of a polyhedron

The kernelK of a convex polyhedronP ₀, as defined by L. Fejes Tóth, is the limit of the sequence (P _n), whereP _n is the convex hull of the midpoints of the edges ofP _n−1. The boundary ∂K of the convex bodyK is investigated. It is shown that ∂K contains no two-dimensional faces and that ∂K need not belong toC ². The connection with similar algorithms from CAD (computer aided design) is explained and utilized. R. J. Gardner was supported in part by a von Humboldt fellowship.     

Steiner symmetrals and their distance from a ball

It is known that given any convex bodyK ⊂ ℝ ⁿ there is a sequence of suitable iterated Steiner symmetrizations ofK that converges, in the Hausdorff metric, to a ball of the same volume. Hadwiger and, more recently, Bourgain, Lindenstrauss and Milman have given estimates from above of the numberN of symmetrizations necessary to transformK into a body whose distance from the equivalent ball is less than an arbitrary positive constant. In this paper we will exhibit some examples of convex bodies which are “hard to make spherical”. For instance, for any choice of positive integersn≥2 andm, we construct ann-dimensional convex body with the property that any sequence ofm symmetrizations does not decrease its distance from the ball. A consequence of these constructions are some lower bounds on the numberN.     

Dynamics of non-expansive maps on strictly convex Banach spaces

This paper concerns the dynamics of non-expansive maps on strictly convex finite dimensional normed spaces. By using results of Edelstein and Lyubich, we show that if X = (ℝ ⁿ , ∥ · ∥) is strictly convex and X has no 1-complemented Euclidean plane, then every bounded orbit of a non-expansive map f: X → X, converges to a periodic orbit. By putting extra assumptions on the derivatives of the norm, we also show that the period of each periodic point of a non-expansive map f: X → X is the order, or, twice the order of a permutation on n letters. This last result generalizes a theorem of Sine, who proved it for ℓ _p ⁿ where 1 < p < ∞ and p ≠ 2. To obtain the results we analyze the ranges of non-expansive projections, the geometry of 1-complemented subspaces, and linear isometries on 1-complemented subspaces. B. Lemmens acknowledges the support by Marie Curie Intra European Fellowship (MEIF-CT-2005-515391) of the European Commission. O. van Gaans acknowlegdes the support by “Vidi subsidie” (639.032.510) of the Netherlands Organisation for Scientific Research (N.W.O.).     

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

Sausages are good packings

LetB ^d be thed-dimensional unit ball and, for an integern, letC _n ={x ¹,...,x ⁿ } be a packing set forB ^d , i.e.,|x ⁱ −x ^j |≥2, 1≤i<j≤n. We show that for every a dimensiond(ρ) exists such that, ford≥d(ρ),V(conv(C _n )+ρB ^d )≥V(conv(S _n )+ρB ^d ), whereS _n is a “sausage” arrangement ofn balls, holds. This gives considerable improvement to Fejes Tóth's “sausage” conjecture in high dimensions. Further, we prove that, for every convex bodyK and ρ<1/32d ⁻²,V(conv(C _n )+ρK)≥V(conv(S _n )+ρK), whereC _n is a packing set with respect toK andS _n is a minimal “sausage” arrangement ofK, holds.     

Some characterisations of the ellipsoid

We show that a convex bodyK of dimensiond≧3 is an ellipsoid if it has any of the following properties: (1) the “grazes” of all points close toK are flat, (2) all sections of small diameter are centrally symmetric, (3) parallel (d−1)-sections close to the boundary are width-equivalent, (4)K is strictly convex and all (d−1)-sections close to the boundary are centrally symmetric; the last two results are deduced from their 3-dimensional cases which were proved by Aitchison.     

Uniformly cross intersecting families

Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P _e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P _e (n) is Θ(2 ⁿ ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $ \left( {{*{20}c} {2\ell } \\ \ell \\ } \right) $ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) 2 ^n−2ℓ = Θ(2 ⁿ /$ \sqrt \ell $ \sqrt \ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P _e (n) decreases with ℓ.     

Remarks on the geometry of coordinate projections in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We study geometric properties of coordinate projections. Among other results, we show that if a bodyK⊂ℝ ⁿ has an “almost extremal” volume ratio, then it has a projection of proportional dimension which is close to the cube. We also establish a sharp estimate on the shattering dimension of the convex hull of a class of functions in terms of the shattering dimension of the class itself.     

On a question of K. Bezdek and T. Odor on Γ-parallelotops

K. Bezdek and T. Odor proved the following statement in [1]: If a covering ofE ³ is a lattice packing of the convex compact bodyK with packing lattice Λ (K is a Λ-parallelotopes) then there exists such a 2-dimensional sublattice Λ′ of Λ which is covered by the set ∪(K+z∣z ∈ Λ′). (K ∪L(Λ′) is a Λ′-parallelotopes). We prove that the statement is not true in the case of the dimensionsn=6, 7, 8. Supported by Hung. Nat. Found for Sci. Research (OTKA) grant no. 1615 (1991).     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

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