A Centrally Symmetric Version of the Cyclic Polytope

We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least for some c _j (d)>0 and at most as n grows. We show that c ₁(d)≥1−(d−1)⁻¹ and conjecture that the bound is best possible. Research of A. Barvinok partially supported by NSF grant DMS 0400617. Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748.     

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.     

A theorem on cyclic polytopes

LetC(ν, d) represent a cyclic polytope withν vertices ind dimensions. A criterion is given for deciding whether a given subset of the vertices ofC(ν, d) is the set of vertices of some face ofC(ν, d). This enables us to determine, in a simple manner, the number ofj-faces ofC(ν, d) for each value ofj (1≦j≦d−1).     

Polytopes with centrally symmetric facets

A new and conceptually simpler proof is given of the theorem of A. D. Aleksandrov and G. C. Shephard, that ad-polytope (d≧3), all of whose facets are centrally symmetric, is itself centrally symmetric.     

Sums of almost equal prime cubes

We prove that almost all integers N satisfying some necessary congruence conditions are the sum of j almost equal prime cubes with j = 5; 6; 7; 8, i.e., N = p ₁³ + ... + p _j ³ with |p _i − (N/j)^1/3| ≦ $ N^{1/3 - \delta _j + \varepsilon } $ N^{1/3 - \delta _j + \varepsilon } (1 ≦ i ≦ j), for δ _j = 1/45; 1/30; 1/25; 2/45, respectively.     

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.     

Convex polytopes without triangular faces

LetP be a convexd-polytope without triangular 2-faces. Forj=0,…,d−1 denote byf _j(P) the number ofj-dimensional faces ofP. We prove the lower boundf _j(P)≥f _j(C _d) whereC _d is thed-cube, which has been conjectured by Y. Kupitz in 1980. We also show that for anyj equality is only attained for cubes. This result is a consequence of the far-reaching observation that such polytopes have pairs of disjoint facets. As a further application we show that there exists only one combinatorial type of such polytopes with exactly 2d+1 facets.     

On integer and fractional parts of powers of Salem numbers

Let N be a positive rational integer and let P be the set of powers of a Salem number of degree d. We prove that for any α∈P the fractional parts of the numbers , when n runs through the set of positive rational integers, are dense in the unit interval if and only if N≦ 2d − 4. We also show that for any α∈P the integer parts of the numbers αⁿ are divisible by N for infinitely many n if and only if N≦ 2d − 3. Received: 27 April 2005     

On a problem of klee concerning convex polytopes

A non-simpliciald-polytope is shown to have strictly fewerk-faces ([(d−1)/2]≦k≦d−1) then some simpliciald-polytope with the same number of vertices; actual numerical bounds are given. This provides a strong affirmative answer to a problem of Klee.     

Matrices with the edmonds—Johnson property

A matrixA=(a _ij ) has theEdmonds—Johnson property if, for each choice of integral vectorsd ₁,d ₂,b ₁,b ₂, the convex hull of the integral solutions ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂ is obtained by adding the inequalitiescx≦|δ|, wherec is an integral vector andcx≦δ holds for each solution ofd ₁≦x≦d ₂,b ₁≦Ax≦b ₂. We characterize the Edmonds—Johnson property for integral matricesA which satisfy for each (row index)i. A corollary is that ifG is an undirected graph which does not contain any homeomorph ofK ₄ in which all triangles ofK ₄ have become odd circuits, thenG ist-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry. First author’s research supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).     

Characterization ofc 0 andl p among Banach spaces with symmetric basis

A Banach spaceX with symmetric basis {e _n} is isomorphic toc ₀ orl _p for some 1≦p<∞, if all symmetric basic sequences inX are equivalent to {e _n}, and all symmetric basic sequences in [f _n]≠X ^* are equivalent to {f _n} (wheref _n (e _j ) =δ _{n, j} ). The result proved in the paper is actually stronger, in the sense that it does not involve all symmetric basic sequences, but only the so called sequences generated by one vector. This is part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem under the supervision of Professor L. Tzafriri. I wish to thank Professor Tzafriri for his interest and advice.     

Classification of finite groups according to the number of conjugacy classes II

In the following,G denotes a finite group,r(G) the number of conjugacy classes ofG, β(G) the number of minimal normal subgroups ofG andα(G) the number of conjugate classes ofG not contained in the socleS(G). Let Φ _j = {G|β(G) =r(G) −j}. In this paper, the family Φ₁₁ is classified. In addition, from a simple inspection of the groups withr(G) =b conjugate classes that appear in ϒ _j ^=1/11 Φ _j , we obtain all finite groups satisfying one of the following conditions: (1)r(G) = 12; (2)r(G) = 13 andβ(G) > 1; …; (9)r(G) = 20 andβ(G) > 8; (10)r(G) =n andβ(G) =n −a with 1 ≦a ≦ 11, for each integern ≧ 21. Also, we obtain all finite groupsG with 13 ≦r(G) ≦ 20,β(G) ≦r(G) − 12, and satisfying one of the following conditions: (i) 0 ≦α(G) ≦ 4; (ii) 5 ≦α(G) ≦ 10 andS(G) solvable.     

Directed Projection Functions of Convex Bodies

For 1 ≤ i < j < d, a j-dimensional subspace L of and a convex body K in , we consider the projection K|L of K onto L. The directed projection function v _i,j (K;L,u) is defined to be the i-dimensional size of the part of K|L which is illuminated in direction u ∈ L. This involves the i-th surface area measure of K|L and is motivated by Groemer’s [17] notion of semi-girth of bodies in . It is well-known that centrally symmetric bodies are determined (up to translation) by their projection functions, we extend this by showing that an arbitrary body is determined by any one of its directed projection functions. We also obtain a corresponding stability result. Groemer [17] addressed the case i = 1, j = 2, d = 3. For j > 1, we then consider the average of v _1,j (K;L,u) over all spaces L containing u and investigate whether the resulting function determines K. We will find pairs (d,j) for which this is the case and some pairs for which it is false. The latter situation will be seen to be related to some classical results from number theory. We will also consider more general averages for the case of centrally symmetric bodies. The research of the first author was supported in part by NSF Grant DMS-9971202 and that of the second author by a grant from the Volkswagen Foundation.     

On extremal point distributions in the Euclidean plane

We ask for the maximum σ _n ^γ of Σ _i,j=1 ⁿ ‖x _i-x _j‖^γ, where x ₁,χ,x _n are points in the Euclidean plane R ² with ‖x_i-x_j‖ ≦1 for all 1≦ i,j ≦ n and where ‖.‖^γ denotes the γ-th power of the Euclidean norm, γ ≧ 1. (For γ =1 this question was stated by L. Fejes Tóth in [1].) We calculate the exact value of σ _n ^γ for all γ γ 1,0758χ and give the distributions which attain the maximum σ _n ^γ . Moreover we prove upper bounds for σ _n ^γ for all γ ≧ 1 and calculate the exact value of σ ₄ ^γ for all γ ≧ 1. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Trace formulas for a class of Toeplitz-like operators

LetP _T denote projection onto the space of entire functions of exponential type ≦T which are square summable on the line relative to a measuredΔ and letG denote multiplication by a suitably restricted complex valued function,g. For a reasonably large class of measuresdΔ, which includes Lebesgue measuredγ, it is shown that trace {(P _TGP_T)ⁿ−P_TGⁿP_T} tends boundedly to a limit asT↑∞ and that the limit isindependent of the choice ofdΔ within the permitted class. This extends the range of validity of a formula due to Mark Kac who evaluated this limit in the special casedΔ=dγ using a different formalism.     

On sperner families in which nok sets have an empty intersection III

LetR be anr-element set and ℱ be a Sperner family of its subsets, that is,X ⊈Y for all differentX, Y ∈ ℱ. The maximum cardinality of ℱ is determined under the conditions 1)c≦|X|≦d for allX ∈ ℱ, (c andd are fixed integers) and 2) nok sets (k≧4, fixed integer) in ℱ have an empty intersection. The result is mainly based on a theorem which is proved by induction, simultaneously with a theorem of Frankl.     

On Kalai’s Conjectures Concerning Centrally Symmetric Polytopes

In 1989, Kalai stated three conjectures A, B, C of increasing strength concerning face numbers of centrally symmetric convex polytopes. The weakest conjecture, A, became known as the “3 ^d -conjecture.” It is well known that the three conjectures hold in dimensions d≤3. We show that in dimension 4 only conjectures A and B are valid, while conjecture C fails. Furthermore, we show that both conjectures B and C fail in all dimensions d≥5.     

A new type of Littlewood-Paley partition

We define a partition of Z into intervals {I _j} and prove the Littlewood-Paley inequality ‖f‖ _p ≦C _p‖Sf‖ _p , 2≦p<∞. Heref is a function on [o, 2π) and . This is a new example of a partition having the Littlewood-Paley property since the {I _j} are not of the type obtained by iterating lacunary partitions finitely many times.     

A criterion for finite lattice coverings

For a centrally symmetric convex and a covering lattice L for K, a lattice polygon P is called a covering polygon, if . We prove that P is a covering polygon, if and only if its boundary bd(P) is covered by (L ∩ P) + K. Further we show that this characterization is false for non-symmetric planar convex bodies and in Euclidean d–space, d ≥ 3, even for the unit ball K = B ^d. This revised version was published online in June 2006 with corrections to the Cover Date.