Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

Efim D. Gluskin, Alexander E. LitvakDiscret. Comput. Geom 2008 · OpenReview

Abstract

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.

Introduction

In convex geometry, the degree of symmetry of a convex body $K$ is a fundamental property often quantified by its Banach–Mazur distance to a symmetric body. Previous research established that polytopes with a relatively small number of vertices—specifically those where the number of vertices $m$ is close to the dimension $d$—are inherently asymmetric. However, the Banach–Mazur distance is essentially a "worst-case" measure, defined by the most asymmetric point of the shape.

This paper investigates whether this asymmetry is a localized defect or a systemic property. By introducing an averaging-type functional, $\delta_K$, the authors explore the "average-case" asymmetry across all vertices. The results demonstrate a striking geometric rigidity: in high-dimensional space, if a polytope has few vertices, its asymmetry is not merely concentrated in a few "bad" corners but is distributed across the entire structure.

The Averaging Functional and Systemic Asymmetry

The core of this research is the introduction of $\delta_K$, a parameter designed to measure the average distance of a polytope's vertices from symmetry. The authors utilize Minkowski functionals (gauges) to define these distances relative to the convex body $K$.

The study's primary theoretical contribution is Theorem 3.2, which addresses $d$-dimensional polytopes with $m = d + k$ vertices. The authors prove that the average asymmetry $\delta_K$ is at least $m / 2k$. Remarkably, this lower bound is identical to the one previously established for the worst-case Banach–Mazur distance. This leads to the "Bad Average" phenomenon: if a convex polytope with a small number of vertices is positioned as close to a symmetric body as possible, most of its vertices are mathematically forced to be as asymmetric as the worst one.

Mathematical Methodology

The proofs rely on a combination of functional analysis and linear algebra. Key techniques include:

  • Matrix Theory: The authors utilize properties of singular values and eigenvalues, specifically drawing on Weil’s Theorem and Stinespring’s result to bound the sums of matrix entries in Lemma 3.1.
  • Duality: The proof of Theorem 3.2 employs the relationship between a convex body $K$ and its polar $K^\circ$, transforming the geometric problem into an optimization problem over linear operators.
  • Combinatorial Averaging: To transition from worst-case to average-case analysis, the authors use averaging arguments over subsets of the polytope's vertices.

Applications: Illumination and Vertex Index

These findings have significant implications for the "illumination problem" in geometry—determining the minimum number of light sources required to fully illuminate the boundary of a convex body.

The paper provides a definitive answer to a conjecture by K. Bezdek regarding the quantitative illumination of centrally symmetric convex bodies. The authors establish that for any $d$-dimensional centrally symmetric convex body $K$, the illumination parameter $ill(K)$ is at least $2d$.

Furthermore, the results provide a lower bound for the vertex index ($vein(K)$), a measure of how efficiently a polytope can wrap around a symmetric body. The authors show that $vein(K) \ge 2d$. Both of these bounds are shown to be "sharp," as they are exactly met by specific shapes such as the cross-polytope, meaning these estimates represent the absolute physical and mathematical limits for these parameters.

Conclusion

By proving that asymmetry is a systemic property of polytopes with few vertices, this work bridges the gap between abstract measures of symmetry and practical geometric problems like illumination. The resolution of Bezdek’s conjecture confirms that the structural constraints of low-vertex polytopes impose strict limits on how they can be illuminated or approximated by symmetric bodies. While the study focuses on centrally symmetric bodies and polytopes with few vertices, it opens the door for future research into the behavior of these functionals as the vertex count increases or when symmetry assumptions are relaxed.

Summary updated

Abstract

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.
BibTeX
@inproceedings{gluskin2008asymmetry,
  author = {Efim D. Gluskin and Alexander E. Litvak},
  title = {{Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies}},
  booktitle = {Discret. Comput. Geom},
  year = {2008},
  url = {https://openreview.net/forum?id=6oJV48eBRv7},
}
Figure