ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 19 (2020) 95-124 https://doi.org/10.26493/1855-3974.2120.085 (Also available at http://amc-journal.eu) Balancing polyhedra * Gabor Domokos MTA-BME Morphodynamics Research Group and Department of Mechanics, Materials and Structures, Budapest University of Technology, Muegyetem rakpart 1-3., Budapest, Hungary, 1111 Florian Kovacs © MTA-BME Morphodynamics Research Group and Department ofStructural Mechanics, Budapest University of Technology, Muegyetem rakpart 1-3., Budapest, Hungary, 1111 MTA-BME Morphodynamics Research Group and Department of Geometry, Budapest University of Technology, Egry Jozsef utca 1., Budapest, Hungary, 1111 Received 18 September 2019, accepted 20 May 2020, published online 10 November 2020 We define the mechanical complexity C(P) of a 3-dimensional convex polyhedron P, interpreted as a homogeneous solid, as the difference between the total number of its faces, edges and vertices and of its static equilibria; and the mechanical complexity C(S,U) of primary equilibrium classes (S, U)E with S stable and U unstable equilibria as the infimum of the mechanical complexity of all polyhedra in that class. We prove that the mechanical complexity of a class (S, U)E with S, U > 1 is the minimum of 2(f + v - * The authors acknowledge the support of the BME Water Sciences & Disaster Prevention TKP2020 IE grant of NKFIH Hungary (BME IE-VIZ TKP2020) and the NKFIH grant K119245. The authors thank Mr. Otto Albrecht for backing the prize for the complexity of the Gomboc-class. Any solution should be sent to the corresponding author as an accepted publication in a mathematics journal of worldwide reputation and it must also have general acceptance in the mathematics community two years after. The authors are indebted to Dr. Norbert Krisztian Kovacs for his invaluable advice and help in printing the 9 tetrahedra and 7 pentahedra, and the two referees for their valuable comments and one of them for posing Problems 5.2 and 5.4. 1 Corresponding author. The author has been supported by the Bolyai Fellowship of the Hungarian Academy of Sciences and partially supported by the UNKP-20-5 New National Excellence Program of the Ministry of Innovation and Technology. Zsolt Lángi t © Krisztina Regos, Péter T. Varga MTA-BME Morphodynamics Research Group, Muegyetem rakpart 1-3., Budapest, Hungary, 1111 Dedicated to the memory of John Horton Conway. Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 96 Ars Math. Contemp. 19 (2020) 125-145 S - U) over all polyhedral pairs (f, v), where a pair of integers is called a polyhedral pair if there is a convex polyhedron with f faces and v vertices. In particular, we prove that the mechanical complexity of a class (S, U)E is zero if and only if there exists a convex polyhedron with S faces and U vertices. We also give asymptotically sharp bounds for the mechanical complexity of the monostatic classes (1, U)E and (S, 1)E, and offer a complexity-dependent prize for the complexity of the Gomboc-class (1,1)E. Keywords: Polyhedron, static equilibrium, monostatic polyhedron, f -vector. Math. Subj. Class. (2020): 52B10, 70C20, 52A38 1 Introduction 1.1 Basic concepts and the main result Polyhedra may be regarded as purely geometric objects, however, they are also often intuitively identified with solids. Among the most obvious sources of such intuition are dice which appear in various polyhedral shapes: while classical, cubic dice have 6 faces, a large diversity of other dice exists as well: dice with 2, 3,4,6,8,10,12,16,20,24,30 and 100 faces appear in various games [37]. The key idea behind throwing dice is that each of the aforementioned faces is associated with a stable mechanical equilibrium point where dice may be at rest on a horizontal plane. Dice are called fair if the probabilities to rest on any face (after a random throw) are equal [10], otherwise they are called loaded [9]. The concept of mechanical equilibrium may also be defined in purely geometric terms: Definition 1.1. Let P be a 3-dimensional convex polyhedron, let int P and bd P denote its interior and boundary, respectively and let c G int P. We say that q G bd P is an equilibrium point of P with respect to c if the plane H through q and perpendicular to [c, q] supports P at q. In this case q is nondegenerate, if H n P is the (unique) vertex, edge, or face of P, respectively, that contains q in its relative interior. A nondegenerate equilibrium point q is called stable, saddle-type or unstable, if dim(H n P) = 2,1 or 0, respectively. Throughout this paper we deal only with equilibrium points with respect to the center of mass of polyhedra, assuming uniform density. A support plane is a generalization of the tangent plane for non-smooth objects. While it is a central concept of convex geometry its name may be related to the mechanical concept of equilibrium. If c coincides with the center of mass of P, then equilibrium points gain intuitive interpretation as locations on bd P where P may be balanced if it is supported on a horizontal surface (identical to the support plane) without friction in the presence of uniform gravity. Equilibrium points may belong to three stability types: faces may carry stable equilibria, vertices may carry unstable equilibria and edges may carry saddle-type equilibria. Denoting their respective numbers by S, U, H, by the Poincare-Hopf formula [25] for a convex polyhedron one obtains the following relation for them: S + U - H = 2, (1.1) E-mail addresses: domokos@iit.bme.hu (Gabor Domokos), kovacs.florian@epito.bme.hu (Florian Kovacs), zlangi@math.bme.hu (Zsolt Langi), regoskriszti@gmail.com (Krisztina Regos), petercobbler@gmail.com (Peter T. Varga) G. Domokos et al.: Balancing polyhedra 97 which is strongly reminiscent of the well-known Euler formula f + v — e = 2, (1.2) relating the respective numbers f, v and e of the faces, vertices and edges of a convex polyhedron. In the case of regular, homogeneous, cubic dice the formulae (1.1) and (1.2) appear to express the same fact, however, in case of irregular polyhedra the connection is much less apparent. While the striking similarity between (1.1) and (1.2) can only be fully explained via deep topological and analytic ideas [25], our goal in this paper is to demonstrate an interesting connection at an elementary, geometric level. To this end, we define N = S + U + H, n = f + v + e. Figure 1 shows three polyhedra where the values for all these quantities can be compared. Figure 1: (a): Three polyhedra interpreted as homogeneous solids with given numbers for faces (f), vertices (v), edges (e), stable equilibria (S), unstable equilibria (U) and saddle-type equilibria (H), their respective sums n = f + v + e, N = S + U + H and mechanical complexity C = n — N (given in Definition 1.2). (b): Polyhedron in column (a3) shown on the overlay of the (S, U) and (f, v) grids, complexity obtained from distance between corresponding diagonals. The numbers S, U, H may serve, from the mechanical point of view, as a first-order characterization of P and via (1.1) the triplet (S, U, H) maybe uniquely represented by the pair (S, U), which is called primary equilibrium class of P [35]. Based on this, we denote by (S, U)E the family of all convex polyhedra having S stable and U unstable equilibrium points with respect to their centers of mass. In an analogous manner, the numbers (v, e, f) (also called the f-vector of P) serve as a first-order combinatorial characterization of P, 98 Ars Math. Contemp. 19 (2020) 125-145 and via (1.2) they may be uniquely represented by the pair (f, v). Here, we call the family of all convex polyhedra having v vertices and f faces the primary combinatorial class of P, and denote it by (f, v)C. The face structure of a convex polyhedron P permits a finer combinatorial description of P .In the literature, the family of convex polyhedra having the same face lattice is called a combinatorial class; here we call it a secondary combinatorial class, and discuss it in Section 5. In an entirely analogous manner, one can define also secondary equilibrium classes of convex bodies, for more details the interested reader is referred to [16]. While it is immediately clear that for any polyhedron P we have f > S, v > U, (1.3) inverse type relationships (e.g. defining the minimal number of faces and vertices for given numbers of equilibria) are much less obvious. A trivial necessary condition for any die to be fair can be stated as f = S and it is relatively easy to construct a polyhedron with this property. The opposite extreme case (when a polyhedron is stable only on one of its faces) appears to be far more complicated. John H. Conway was first to notice this curious fact [5] and ever since, his idea has been expanded in various ways [2, 28]. In broader terms, it appears that, as the number of equilibria in a given equilibrium class gets smaller, it is getting increasingly difficult to identify the corresponding geometry. In other words, the difference (n - N) between the topological and mechanical characteristics of the polyhedron appears to indicate some kind of complexity of the geometry. Motivated by this intuition we define the mechanical complexity of polyhedra. Definition 1.2. Let P be a convex polyhedron and let N(P), n(P) denote the total number of its equilibria and the total number of its k-faces (i.e., faces of k dimensions) for all values k = 0,1, 2, respectively. Then C(P) = n(P) — N(P) is called the mechanical complexity of P. We remark that the term mechanical complexity has been used in various contexts, ranging from robotics [1] to cell biology [21], to describe phenomena where the observed complexity is rooted in the mechanical properties of the investigated subject. In our case we witness the same phenomenon: the apparent complexity of some polyhedral shapes arises from the mechanical constraint that the number of static equilibria is kept, compared to the number of vertices, edges and faces, very low. Mechanical complexity may not only be associated with individual polyhedra but also with primary equilibrium classes. Definition 1.3. If (S, U)E is a primary equilibrium class, then the quantity C(S, U) = min{C(P) : P G (S, U)E} is called the mechanical complexity of (S, U )E. Our goal is to find the values of C(S, U) for all primary equilibrium classes. For S, U > 1 we will achieve this goal while for S =1 or U = 1 we provide some partial results. To formulate our main results, we introduce the following concept: Definition 1.4. Let x, y be positive integers. We say that (x, y) is a polyhedral pair if and only if x > 4 and x + 2 < y < 2x — 4. G. Domokos et al.: Balancing polyhedra 99 The combinatorial classification of convex polyhedra was established by Steinitz [30, 31] (for a proof, see also [20]), who proved, in particular, the following. Theorem 1.5. For any positive integers f, v, there is a convex polyhedron P with f faces and v vertices if and only if (f, v) is a polyhedral pair. Based on this theorem, we call a primary equilibrium class (S, U)E a polyhedral (primary equilibrium) class if (S, U) is a polyhedral pair, and the remaining primary equilibrium classes non-polyhedral classes. Definition 1.6. For any primary equilibrium class (S, U)E with S, U > 1, let R(S, U) = min{f + v - S - U : (f, v) is a polyhedral pair and f, v satisfy (1.3)}. The geometric interpretation of R(S, U) is given in the left panel of Figure 2. Since (1.3) holds for any polyhedron P G (S, U)E, we immediately have the trivial lower bound for mechanical complexity: Remark 1.7. Based on Definition 1.4, the function R(S, U) can be expressed as Our main result is Theorem 1.8, stating that this bound is sharp if S, U > 1: Theorem 1.8. Let S, U > 2 be positive integers. Then C(S, U) = 2R(S, U). We remark that, as a consequence of Theorem 1.8, C(S, U) = 0 if and only if (S, U) is a polyhedral pair. For monostatic equilibrium classes (S = 1 or U = 1) we cannot provide a sharp value for their mechanical complexity. However, we will provide an upper bound for their complexity, which differs from 2R(S, U) only by a constant: Theorem 1.9. If S > 4 then C(S, 1) < 59 + (-1)S + 2R(S, 1); if U > 4 then C(1,U) < 90 + 2R(1,U). We also improve the lower bound (1.4) in some of these classes by generalizing a theorem of Conway [7] about the non-existence of a homogeneous tetrahedron with only one stable equilibrium point. We state our result in the following form: Theorem 1.10. Any homogeneous tetrahedron has S > 2 stable and U > 2 unstable equilibrium points. We summarize all results (including those about monostatic classes) in Figure 2. C(S,U) > 2R(S, U). (1.4) (1.5) 100 Ars Math. Contemp. 19 (2020) 125-145 1 2 3 4 5 6 7 8 9 10 1 2 2)=4 3 u /\ 4 in ii 5 a. 6 m 7 3 8 9 10 1 with mechanical complexity C(P) = 2R(S, U), in class (S, 1)E, S > 4 with C(P) = 59 + (-1)S + 2R(S, 1), and in class (1, U)E, U > 4 with C(P) = 90 + 2R(1, U). By Definition 1.3, such a construction establishes an upper bound for C(S, U). In case of S > 1 and U > 1, by Definition 1.6, this coincides with the lower bound while for S = 1 or U = 1 the bounds remain separate. Our proof consists of five parts: (a) for classes (S, S)E with S > 4, suitably chosen pyramids have zero mechanical complexity (Section 3); (b) for classes 1 < S < 5 and 1 < U < 5, (S, U)E = (4,4)E, (5, 5)E, we provide examples found by computer search (Subsection 3.2, Tables 1 and 2); (c) for polyhedral classes with S = U, we construct examples by recursive, local manipulations of the pyramids mentioned in (a) (Subsection 3.1); (d) for non-polyhedral classes with U > S > 6, we construct examples by recursive, local manipulations starting with polyhedral classes containing simple polyhedra (Subsection 3.2); (e) for non-polyhedral classes with 6 < U < S we provide examples by using the G. Domokos et al.: Balancing polyhedra 101 polyhedra obtained in (d) and the properties of polarity proved in Section 2. We also show how to modify the construction in (d) for this case (Subsection 3.2); (f) for monostatic classes with S =1 or U = 1 we provide examples using Conway's polyhedron PC in class (1,4)E, we also construct a polyhedron P3 in class (3,1) and subsequently we apply recursive, local truncations (Section 4). In Section 2, we prove a number of lemmas which help us keep track of the change of the center of mass of a convex polyhedron under local deformations and establish a connection between equilibrium points of a convex polyhedron and its polar. The local manipulations in our proof may be regarded as generalizations of the algorithm of Steinitz [20]. Figure 3 and Figure 4 summarize the steps outlined above. CONSTRUCTION SYMBOLS FOR EQUILIBRIUM CLASSES p Lot 1 2 3 4 5 6 7 8 9 10 1 - Pr Pb Pc L4 L3 L3 L3 L3 L3 2 Pi Pa Pa Pa Ps L3 L4 L3 L4 L3 3 P3 Pt Pa Pa Ps L3 L4 L3 L4 L3 4 LG Pi Pa P4{h) Ps L3 L4 L3 L4 L3 5 L5 Ps Ps Ps Ps(h) L1 L4 L3 L4 L3 6 L5 R, 1 5 R,' A 5 R 1 5 L2 P6(H) L1 L1 L4 L3 7 L5 R,a R|fi R|fi R,R L2 PM L1 L1 L1 8 L5 R, 1 5 R, A 5 R, i 5 R, 1 5 L2 L2 pm L1 L1 9 L5 A B R|fi RIB R. A B Rffi L2 L2 P*i(h) L1 10 L5 R, 1 S R, A 5 R/ A R, 1 S R, I 5 L2 L2 L2 CONSTRUCTION SYMBOL DESCRIPTION SECTION, SUBSECTION ?ECT CONSTRUCTION ANALYTICAL P„( h) PYRAMIDS WITH REGULAR n-GONAL BASE AND SUFTABLY CHOSEN HEIGHT SS 3.1 Pc.Pb MONOSTABLE POLYHEDRA BY CONWAY & GUY, BEZDEK SS 4.1 S1 P2.P3 MONO-UNSTABLE POLYHEDRA CONSTRUCTED USING THE IDEA OF CONWAY & GUY £ ii Pr Pa MONOSTABLE POLYHEDRON FOUND BY RESHETOV TETRAHEDRA a POU O » o 1RITY Ps R PENTAHEDRA Construction of polyhedra via polarity, resulting in (s,u) -* (u,s) SS 3.2 S 2 LOCAL MANIPULATION POLYHEDRAL CLASSES L1 Construction of minimal polyhedra via steps (s,u) -» {S+1, u+2] SS 3.1 L2 Constmctlon of minimal polyhedra via steps (s,u) (S+2, u+1 ] NON-POLYHEDRAL CLASSES L3 Constmctlon of polyhedra via steps (S,U) (s, u+2) SS 3.2, S 4 L4 Construction of polyhedra via steps (s,u) (S, u+1) L5 Construction of polyhedra via steps (S,U) —> (S+2, u) L6 Constmctlon of polyhedra via steps (s,u) —> (S+1, u) Figure 3: Summary of the proof. Left panel: Symbols on the (S, U) grid indicate how polyhedra in the given equilibrium class (S, U)E have been constructed. Dark background corresponds to classes where polyhedra have been identified by computer search. Light grey background corresponds to polyhedral pairs. Symbols are explained in the right panel. For S, U > 1 the indicated constructions provide minimal complexity and thus the complexity of the class itself. Hyphen indicates that no polyhedron is known in that class. Right panel: Symbols in the left panel explained briefly with reference to sections, subsections and sub-subsections of the paper. 2 Preliminaries Before we prove some lemmas that we need for Theorem 1.8, we make a general remark about small perturbations: Remark 2.1. Observe that (i) a nondegenerate (stable) equilibrium point sF on face F of a convex polyhedron P exists if and only if the orthogonal projection sF of c(P) (the center of mass of P) onto F is in the relative interior of F; (ii) a vertex q is a nondegenerate (unstable) equilibrium point of P if and only if the plane perpendicular to q - c(P) and containing q contains no other point of P; 102 Ars Math. Contemp. 19 (2020) 125-145 (a) STEP L1 (Lemma 3.1) (b) STEP L4 (Lemma 3.6) STEP L2 (Lemma 3.2) pp. p p< XA AA STEP L5 (Lemma 3.9) STEP L3 (Lemma 3.6) . p^i p; j V -o \ V b-'4- Mxi V V p p p p• P' P' V f f U U p P' p p P' p• ▼s s s u STEP L6 (Lemma 3.9) Figure 4: Summary of the proof. (a)-(b): Upper row: schematic picture of local manipulations L1 - L6, showing local face structure and equilibria on original and manipulated polyhedra P and P', respectively. Lower rows: Original and manipulated polyhedra P and P' shown on the (f, v) and (S, U) grids. (iii) a nondegenerate equilibrium point sE on an edge E of P exists if and only if the orthogonal projection sE of c(P) onto E is in the relative interior of E, and the angle between c(P) - sE and any of the two faces of P containing E is acute. The subject of our investigation is the family of 3-dimensional convex polyhedra which have only nondegenerate equilibria, and all polyhedra appearing in the paper satisfy this property. Then the following observation is used many times in the paper for some 3-dimensional convex polyhedron P: If all equilibria are nondegenerate then we will find the same number of equilibria (a) after applying any sufficiently small perturbation of vertices which leaves the com- G. Domokos et al.: Balancing polyhedra 103 binatorial structure unchanged on all vertices, edges and faces, (b) after applying a truncation to the polyhedron with sufficiently small volume, on vertices, edges or faces left unchanged by the truncation and (c) after applying an augmentation (inverse of truncation) to the polyhedron with sufficiently small volume, on vertices, edges or faces left unchanged by the augmentation. In the following, conv X, aff X, int X and cl X denote the convex hull, the affine hull, the interior and the closure of the set X c Rd, respectively. The origin is denoted by o. For any convex polytope P in Rd, we denote by V (P) the set of vertices of P, and the volume and the center of mass of P by w(P) and c(P), respectively. The polar of the set X is denoted by X °. The first three lemmas investigate the behavior of the center of mass of a convex polyhedron under local deformations. Lemma 2.2. Let P be a convex polyhedron and let q be a vertex of P. Let Pe be a convex polyhedron such that Pe c P, and every point of P \ Pe is contained in the e-neighborhood of q. Let c = c(P) and cE = C(PE). Then there is a constant y > 0, independent of e, such that \ce — c\ < je3 holds for every polyhedron Pe satisfying the above conditions. Proof. Without loss of generality, let c = o, ce = c(cl(P \ Pe)), w = w(P) and wE = w(Pe). Then o = wece + (w — we)ce, implying that cE = — w-we ce. Note that for some Y' > 0 independent of e, we have 0 < < 2< y'e3. Furthermore, for some Y'' > 0, \q — ce\ < y"e, which yields that \ce\ is bounded. Thus, the assertion readily follows. □ Lemma 2.3. Let F be a triangular face of the convex polyhedron P, and assume that each vertex of P lying in F has degree 3. Let q1, q2 and q3 be the vertices of P on F, and for i = 1, 2, 3, let Li denote the line containing the edge of P through qi that is not contained in F. For i = 1, 2, 3 and t g R, let qi(r) denote the point of Li at the signed distance t from qi, where we orient each Li in such a way that qi(T) is a point of P for any sufficiently small negative value of t. Let U be a neighborhood of o, and for any t = (ti ,t2,t3) g U, let W (t) = w(P (t)) and C (t) = c(P (t)), where P (t) = conv ((V (P) \ {qi, q2, q3}) U {qi(n), q2(T2), q3(T3)}). Then the Jacobian of the function W(t)C(t) is nondegenerate at t = o. Proof. It is sufficient to show that the partial derivatives of the examined function span R3. Without loss of generality, we may assume that qi, q2 and q3 are linearly independent. Consider the polyhedron P(t1, 0,0) for some t1 > 0, and let WW(t1) = w(T(t1)), (C(t1) = c(T(t1)) and T(Ti) = conv{q1, q2,q3, q^n)}. Let A be the area of the triangle conv{q1, q2,q3}. If t1 > 0 is sufficiently small, then d - W (t)C (t) t=( 0,0,0) 12 sin a1A (2qi + q2 + q3), W(t1, 0, 0)C(t1, 0, 0) = w(P)c(P) + W(t1)CC(t1). Since C(ti) = 4(qi + q2 + q3 + qi(n)), it follows that 4 sin a1A d — W (t)C (t) t=( 0,0,0) 12 (2qi + q2 + q3), 104 Ars Math. Contemp. 19 (2020) 125-145 where a denotes the angle between L and the plane through qi, q2, q3. Using a similar consideration, we obtain the same formula if t1 < 0, and similar formulas, where q2 or q3 plays the role of q1, in the partial derivatives with respect to t2 or t3, respectively. Note that 0 < a1, a2, a3 < n • Thus, to show that the three partial derivatives are linearly independent, it suffices to show that the vectors 2q1 + q2 + q3, q1 + 2q2 + q3 and q1 + q2 + 2q3 are linearly independent. To show it under the assumption that q1, q2, q3 are linearly independent can be done using elementary computations, which we leave to the reader. □ Remark 2.4. We remark that Lemma 2.3 can be 'dualized' in the following form: Assume that q is a 3-valent vertex of P, and each face of P that q lies on is a triangle. Furthermore, let Y be a neighborhood of q, and for any x e Y, let W(x) = w (conv ((V(P) \ {q}) U {x})) , and C(x) = c (conv ((V(P) \ {q}) U {x})). Then the Jacobian matrix of the function W(-)C(•): Y ^ R3 is nondegenerate at q. Remark 2.5. If the Jacobian of a smooth vector-valued function in R3 is nondegenerate, by the Inverse Function Theorem it follows that the function is surjective. Thus, a geometric interpretation of Lemma 2.3 and Remark 2.4 is that under the given conditions, by slight modifications of a vertex or a face of P the function w(P)c(P) moves everywhere within a small neighborhood of its original position. In the forthcoming two lemmas we investigate the connection between polarity and equilibrium points. Lemma 2.6. Let S be a d-dimensional simplex in the Euclidean space Rd such that o e int S. Then o = c(S°) if and only if o = c(S). Proof. Let the vertices of S be denoted by p1,p2,... ,pd+1. For i = 1, 2,..., d + 1, let n denote the orthogonal projection of o onto the facet hyperplane Hi of S not containing pi, and let Hj be the hyperplane through o and parallel to Hi. We remark that since o e int S, none of the pis and the nis is zero. Finally, let ai denote the angle between pi and ni. Assume that o = c(S). Then for all values of i, we have dist(pi, Hi) = ddist(Hi, Hi), where dist(A, B) = inf{|a - b| : a e A, b e B} is the distance of the sets A and B. This implies that the projection of pi onto the line through o and ni is — dni for all values of i, or in other words, cos «i|pi| = —d|Hi| (2.1) for all values of i. On the other hand, it is easy to see that if (2.1) holds for all values of i, then o = c(S). The vertices of S° are the points p* = , where i = 1,2,..., d +1, and the projection of o onto the facet hyperplane of P° not containing p* is n* = yp^. Hence, the angle between p* and n* is ai. Similarly like in the previous paragraph, o = c(S°) if and only if cos ai|p*| = — d|n*| (2.2) holds for all values of i. On the other hand, if cos ai|pi| = — d|ni| for some value of i, then cos ai|p*| = = — yp^ = —d|n*|, and vice versa. Thus, (2.1) and (2.2) are equivalent, implying Lemma 2.6. □ G. Domokos et al.: Balancing polyhedra 105 Lemma 2.7. Let P be a convex d-polytope in the Euclidean space Rd such that o G int P, and let P° be its polar. Let F be a k-face of P, where 0 < k < d — 1, and let F* denote the corresponding (d — k — 1)-face of P°. Then F contains a nondegenerate equilibrium point of P with respect to o if and only if F* contains a nondegenerate equilibrium point of P° with respect to o. Proof. Let F = convjpj : i G I}, where I is the set of the indices of the vertices of P such that pi is contained in F, and let p be the orthogonal projection of o onto aff F. Let L = aff(F U {o}), and let Lc denote the orthogonal complement of L passing through o. For any facet hyperplane of P containing F, let nj, j G J denote the projection of o onto this hyperplane. Let H+ be the closed half space {q G Rd : (q, nj} < (nj, nj}}. Let H+ = H+ n H for any i G I. Finally, let ni be the component of ni parallel to H. Before proving the lemma, we observe that for any given vectors ni,n2,... ,nu spanning Rd, the following are equivalent: (a) o is an interior point of a polytope Q in Rd with outer facet normals ni,n2,... ,nu. (b) There are some Ai, A2,..., Au > 0 such that o G int Q', where Q' = conv{Aini, A2n2,..., Afc nu}. (c) We have o g intconv{Aini, A2n2,..., Aunu} for any Ai, A2,... ,Au > 0. We note that if a polytope Q satisfies the conditions in (a), then its polar Q' = Q° satisfies the conditions in (b), and vice versa. Finally, observe that if F contains an equilibrium point, then by exclusion it is p. We show that p is a nondegenerate equilibrium point of F if and only if it is contained in the relative interiors of the conic hulls of the pis as well as those of the nj s. First, let p be a nondegenerate equilibrium point. Then p G relint F, that is, it is in the relative interior of the conic hull (in particular, the convex hull) of the pis. Observe that since the projection of o onto aff F is p, for any j G J, the projection of nj onto aff F is p. In other words, nj G L' = aff (Lc U {p}) for all j G J. Since p is a vertex of the polytope P n L', the vectors nj, j G J span this linear subspace, or equivalently, the vectors n,j span Lc. Observe that the intersection of P with the affine subspace (1 — e)p + Lc, for sufficiently small values of e > 0, is a (d — k — 1)-polytope, with outer facet normals nj, j G J, which contains (1 — e)p in its relative interior. By the observation in the previous paragraph, it follows that o is contained in the relative interior of the convex hull of the n,j s, which implies that p is contained in the relative interior of the conic hull of the nj s. On the other hand, if p is contained in the relative interior of the conic hull of the pis, then the fact that p G aff F implies that p G relint F. Furthermore, if p is contained in the relative interior of the conic hull of the nj s, then o is contained in the relative interior of the convex hull of the njs. Thus, the only solution for q G Lc of the system of linear inequalities (q, n,j} < 0, where j G J, is q = p, which implies that the only point of P in p + Lc is p. This means that p is a nondegenerate equilibrium point of P. Finally, observe that the vertices of F* are the points r-^j^, and the projections of o i nj i onto the facet hyperplanes of P° containing F* are the points |. Furthermore, aff F* = |-pPj2 + Lc, which yields that the projection of o onto aff F* is . Combining it with the consideration in the previous paragraph, this yields the assertion. □ 106 Ars Math. Contemp. 19 (2020) 125-145 The next corollary is an immediate consequence of Lemmas 2.6 and 2.7 and, together with the result of Conway [7], implies Theorem 1.10. Corollary 2.8. Every homogeneous tetrahedron has at least two vertices which are equilibrium points. Furthermore, there are inhomogeneous tetrahedra with exactly one vertex which is an equilibrium point. 3 Polyhedra with many stable or unstable equilibria: proof of Theorem 1.8 3.1 Proof of Theorem 1.8 for polyhedral pairs We need to show that if (S, U)E is a polyhedral class (see the remark after Theorem 1.5), then there is a polyhedron with S faces and U vertices. For brevity, we call such a polyhedron a minimal polyhedron in class (S, U)E. We do the construction separately in several cases. 3.1.1 Case 1: S = U > 4 Let S > 4, and consider a regular (S -1)-gon RS in the (x, y)-plane, centered at o and with unit inradius. Let Pv (h) be the pyramid with base Rv and apex (0,0, h). By its symmetry properties, PS(h) is a minimal polyhedron in the class (S, S)E for all h > 0. 3.1.2 Case 2: S > 4 and S < U < 2S - 4 In this case the proof is based on Lemma 3.1. Lemma 3.1. Assume that P is a minimal polyhedron in class (S, U)E having a vertex of degree 3. Then there is a minimal polyhedron in class (S + 1, U + 2)E having a vertex of degree 3. Proof. Let P be a minimal polyhedron in class (S, U)E with a vertex q of degree 3. For sufficiently small e > 0, let P£ c P be the intersection of P with the closed half space with inner normal vector c - q, at the distance e from q. We show that if e is sufficiently small, then P£ satisfies the conditions in the lemma. If e is sufficiently small, the boundary of this half space intersects only those edges of P that start at q. Thus, P£ has one new triangular face F, and three new vertices qi, q2, q3 on F. Since q is not a vertex of P£, P£ has S +1 faces and U + 2 vertices. Furthermore, q1, q2 and q3 have degree 3, which means that we need only to show that P£ is a minimal polyhedron. To do it, we set c = c(P) and c£ = c(P£). Note that by (1.2) and (1.1), every edge of a minimal polyhedron contains an equilibrium point. Thus, by Remark 2.1, if e is sufficiently small, then every edge of P£, apart from those having at least one common point with F, contains an equilibrium point with respect to c£. For a sufficiently small e, clearly, |c - c£| is also small enough such that the edges starting at (but not contained by) F still contain equilibrium points with respect to c£. We intend to show that if e is sufficiently small, then the edges of P£ in F also contain equilibrium points with respect to c£, which, by (1.2) and (1.1) clearly implies that P£ is a minimal polyhedron. Consider, e.g. the edge E = [q1, q2], and let F3 be the face of P£ different from F and containing E. Let h and s be the equilibrium point on E and on F3, respectively, with G. Domokos et al.: Balancing polyhedra 107 respect to c. Let a and p denote the dihedral angles between the planes aff(E U {c}) and aff F, and the planes aff(E U {c}) and aff F3, respectively. The fact that h is an equilibrium point with respect to c is equivalent to saying that the orthogonal projection of c onto the line of E is h, and that 0 < a, p < |. Since h is contained in the plane aff{q, c, s} for all values of e, and it is easy to see that there is some constant y' > 0 independent of e such that |qi - h|, |q2 - h| > 7'e. Similarly, an elementary computation shows that for some constant 7'' > 0 independent of e, we have 0 < a, p < 2 - Y''e. Thus, Lemma 2.2 implies that for small values of e, E contains an equilibrium point with respect to ce, implying that Pe is a minimal polyhedron. □ Now, consider some class (S, U)E with S > 4 and S < U < 2S - 4. Then, if we set k = U - S and S0 = S - k, we have 0 < k < S - 4 and 4 < S0. In other words, (S, U)E = (So+k, So+2k)E for some So > 4 and k > 0. Now, by the proof in Case 1, the class (S0, S0)E contains a minimal polyhedron, e.g. a right pyramid PSo (h) with a regular (S0 - 1)-gon as its base, where h > 0 is arbitrary. Note that the degree of every vertex of PSo (h) on its base is 3, and thus, applying Lemma 3.1 yields a minimal polyhedron in class (S0 +1, S0 + 2)e having a vertex of degree 3. Repeating this argument (k -1) times, we obtain a minimal polyhedron in class (S, U)E. 3.1.3 Case 3: S > 4 and f + 2 < U < S Note that these inequalities are equivalent to U > 4 and U < S < 2U - 4. For the proof in this case we need Lemma 3.2. Lemma 3.2. Assume that there is a minimal polyhedron P in class (S, U)E having a triangular face. Then there is a minimal polyhedron P' in class (S + 2, U + 1)E having a triangular face F'. Proof. Let c = c(P), and let cF be its orthogonal projection on the plane of F. Since P is a minimal polyhedron, cF is a relative interior point of F, and an equilibrium point with respect to c (see also Figure 5 for illustration). Let c be the centroid of F and define the vector u as c - cF. Let v be the outer unit normal vector of F, and for any 0 < e and 0 < a < 1, let Tea denote the tetrahedron with base F and apex q = cF + ev + au such that Tea n P = F. Let Pea = Tea U P, c' = c(Pea), and c'F be the orthogonal projection of c' on the plane of F. By Remark 2.1, for a sufficiently small e, equilibrium points on all vertices of Pea except q, as well as on all edges and faces of Pea not containing q will be preserved. It is also easy to see from simple geometric considerations that for small values of e, every face and vertex of Pea contains an equilibrium point with respect to c' if q, c'F and c' are collinear. In the special case of u = 0, those points are obviously collinear. In any other case, it is also straightforward to see that c'F e relintconv{cF, cF/4 + 3c/4}. Let us define d(a) = (cF + au - c'F) • u. Since d continuously varies with a and d(0) < 0, d(1) > 0, for any small e > 0 there is an a0 such that apex q and all edges and faces it is contained in have equilibrium points. □ Remark 3.3. Note that the argument also yields a polyhedron P' such that there is an equilibrium point on each face and at every vertex of P' with respect to the original reference point: in this case we may choose the value of a in the proof simply as a = 0. 108 Ars Math. Contemp. 19 (2020) 125-145 Figure 5: Building a tetrahedron on a triangular face of a convex polyhedron. Now we prove Theorem 1.8 for Case 3. Like in Case 2, if we set k = S - U and S0 = U - k, then S0 > 4, k > 0, and (S, U)E = (S0 + 2k, S0 + k)E. Consider the right pyramid PSo (h) in Case 1. This pyramid has S0 faces consisting of S0 - 1 triangles and one regular (S0 - 1)-gon shaped face. Thus, applying the construction in Lemma 3.2 k times subsequently yields the desired polyhedron. 3.2 Proof of Theorem 1.8 for non-polyhedral pairs 3.2.1 Case 1: 2 < S < 4 and 2 < U < 4 Lemma 3.4. Let S, U G {2,3,4}. Then C(S, U) = 2R(S, U). Proof. Table 1 contains an example for a tetrahedron in each of the 9 classes (illustrated in Figure 6) and for the tetrahedron we have n = f + v + e =14, consequently an upper bound for complexity can be computed as C(S, U) < 14 - S - U - H =16 - 2S - 2U. Since from (1.5) we have the same for the lower bound we proved the claim. □ 3.2.2 Case 2: 2 < S < 4, U = 5 or 2 < U < 4, S = 5 This case follows from Lemma 3.5. Lemma 3.5. Let 2 < S < 4, U = 5 or 2 < U < 4, S = 5. Then C(S, U) = 2R(S, U). Proof. Table 2 contains an example for a pentahedron in each of the 6 classes (illustrated in Figure 6) and for the pentahedron we have n = f + v + e =18, consequently an upper bound for complexity can be computed as C(S, U) < 18 - S - U - H = 20 - 2S - 2U. From (1.5) we obtain the same lower bound for all 6 classes so we proved the claim. □ 3.2.3 Case 3: S > 5 and U > 2S - 4, or 2 < S < 4 and U > 6 First, we prove the following lemma. Lemma 3.6. Let P G (S, U)E be a convex polyhedron with f faces and v vertices. Let qit i = 1,... ,j, be successive vertices of an m-gonal (m >, j > 3) face F of P such that (i) the lines aff({qi, q2}) and aff({qj_i, qj }) intersect at some point q with the property |q - qil > |q - q21; Non-constant vertex coordinates Equilibria on faces vertices edges Class C 0 (the term 'sufficiently small' is explained in the next paragraph) and truncates the vertices q2, q3,..., qj-1. For i = 2, 3,..., j — 1, let q^s, t) be the intersection of G(s, t) with the edge of P starting at qj and not contained in F. Finally, let P(s, t) be the truncation of P by G(s, t), that is, P(s, t) = cl(P \ conv{y0(s), y6(t), q2, .. ., qj-i, q2(s, t),. .., qj-i (s, t)}. We denote the center of mass of P(s, t) by c(s, t), and the projection of c and c(s, t) onto the plane of F by cF and cF(s, t), respectively. Furthermore, we denote the new edge of P(s,t) starting at ya(s) and different from [ya(s),yb(t)] by Ya(s, t), and define Yb(s,t) similarly. Figure 7: Increasing the number of unstable equilibria by two. Views perpendicular to the plane F (a) and edge [ua, ub] (b). We choose some e > 0 to satisfy the following conditions: with respect to any point c' € V, the original polyhedron P has equilibrium points on the same faces and edges, and at the same vertices, as with respect to the center of mass c of P, where V is the locus of the centers of mass of all truncations of P by the plane G(s, t), s, t € [0,1] (for a sufficiently small e, clearly, |c—c'| and the volume removed by truncation are also small enough for the number of original equilibrium points on vertices, edges and faces to be preserved as well; new face and edges included in G(s, t) have no equilibrium points). Furthermore, we assume also that G(s, t) truncates no vertex or equilibrium point of P other than those on F, and that there is some arbitrarily small, fixed value S > 0 (independent of (s, t)) such that c(s, t) is a Lipschitz function at every (s, t) with Lipschitz constant S, i.e. |c(s + As,t + At) — c(s,t)| < S^(As)2 + (At)2 for all s,t € [0,1]. First, we show that for some suitable choice of s and t, the orthogonal projections of c(s, t) onto the lines of Ea and Eb are ya(s) and yb(t), respectively. To do this, we use a consequence of Brouwer's fixed point theorem, the so-called Cube Separation Theorem from [27], which states the following: Let the pairs of opposite facets of a d-dimensional cube K be denoted by Fj and F/', i = 1, 2,..., d, and let G^ i = 1, 2,..., d, be compact sets such that Gj 'separates' F/ and F/', or in other words, K \ Gj is the disjoint union of two open sets Q', Q'' such that F' c Q', and F'' c Q''. Then p|f=1 Gj = 0. To apply this theorem, we set K = {(s,t) : 0 < s,t < 1}, and define Qi, C1 and Qi' as the set of pairs (s,t) such that the orthogonal projection of c(s,t) onto the line of (a) 112 Ars Math. Contemp. 19 (2020) 125-145 Ea is a relative interior point of [ya(s), qi], coincides with ya(s), or does not belong to [ya(s), q1], respectively. We define Q2, C2 and Q2' similarly. Then these sets satisfy the conditions of theorem, and we obtain a pair (s, t) with the desired property. Note that by the choice of e > 0, it holds that in a neighborhood of (s, t), the orthogonal projection of c(s, t) onto the line of Ya(s, t) is in the relative interior of Ya(s, t), and the same holds also for the projection onto the line of Yb(s, t). Now we choose some (s', t') sufficiently close to (s, t) such that the intersections of G(s', t') and G(s, t) with F are parallel, and that of G(s', t') is closer to q2 and qj-1 than that of G(s, t). By the Lipschitz property of c(s, t), we have that the distance of the two intersection lines is greater than |c(s',t') - c(s, t)|, and hence, the projections of c(s', t') onto the lines of Ea and Eb lie in the relative interior of the segments [ya(s'), q1] and [yb(t'), qj], respectively. From this it readily follows that both these edges of P' = P(s', t') and also Ya(s', t') and Yb(s', t') contain saddle points with respect to c(s', t'). This implies also that ya(s') and yb(t') are vertices of P' carrying unstable equilibrium points, and the assertion follows. □ Corollary 3.7. Let conditions (i) and (iii) of Lemma 3.6 hold and (ii) be modified as follows: (ii) q1 contains an unstable and Eb = [qj_1,qj ] contains a saddle-type equilibrium point. Then there exists a polyhedron P'' G (S, U + 1)E with f + 1 faces and v + 1 vertices. Remark 3.8. A simplified version of the proof of Lemma 3.6 can be used to prove the same statement for a fixed reference point c. To prove Theorem 1.8 in Case 3, we construct a simple polyhedron with U vertices that has S stable and U unstable points. Since any polyhedron in class (S, U)E has at least U vertices, and among polyhedra with U vertices those with a minimum number of faces are the simple ones, such a polyhedron clearly has minimal mechanical complexity in class (S, U)E. First, consider the case that S > 5 and U > 2S - 4. Let Uo = 2S - 4. By the construction in Subsection 3.1, class (S, U0)E contains a simple polyhedron P0 with U0 vertices and S faces. Remember that to construct P0 we started with a tetrahedron T in class (4, 4)e, and in each step we truncated a vertex of the polyhedron sufficiently close to this vertex. Throughout the process, the vertex can be chosen as one of those created during the previous step. Since in this case the conditions of Lemma 3.6 are satisfied for any face of P0, applying Lemma 3.6 to it we obtain a polyhedron P1 with two more vertices, one more face, two more unstable and the same number of stable points. By subsequently applying the same procedure, we can construct a convex polyhedron in class (S, U)E for every even value of U. To obtain a polyhedron in class (S, U)E where U is odd, we can modify a polyhedron in class (S, U - 1)E according to Corollary 3.10. Now, consider the case that 2 < S < 4, and U > 6. Then, starting with a tetrahedron in class (S, 4)E (based on the data of Table 1, all three tetrahedra meet the conditions of Lemma 3.6) we can repeat the argument in the previous paragraph. 3.2.4 Case 4: U > 5 and S > 2U - 4, or 2 < U < 4 and S > 6 Theorem 1.8 in Case 4 can be deduced from Case 3 using direct geometric properties of polarity. Nevertheless, also the proof in Case 3 via Lemma 3.6 can be dualized as well. In G. Domokos et al.: Balancing polyhedra 113 Lemma 3.9 and Corollary 3.10 we prove dual versions of Lemma 3.6 and Corollary 3.7, respectively, which we are going to use also in Section 4, in our investigation of monostatic polyhedra. Since Theorem 1.8 follows from Lemma 3.9 and Corollary 3.10 similarly like in the proof of Case 3, we leave it to the reader. We start with the proof using polarity. Considering a tetrahedron T centered at o, a straightforward modification of the construction in Lemma 3.1 and by Remark 3.8, we may construct a simple polyhedron P with U vertices that has S stable and U unstable equilibrium points with respect to o. Using small truncations, we may assume that P is arbitrarily close to T measured in Hausdorff distance. Furthermore, without loss of generality, we may assume that a face of T, and all vertices of this face have degree 3 in P. Let this face of T be denoted by F. Recall that P° denotes the polar of P. By Lemma 2.6, c(T°) = o, and by the continuity of polar and the center of mass, c(P°) is 'close' to o. On the other hand, since the vertex q of P° corresponding to F has degree 3, and each face containing q is a triangle, Lemma 2.3 implies that by a slight modification of q we obtain a polyhedron Q such that c(Q) = o, and a face/edge/vertex of Q contains an equilibrium point with respect to o if and only if the corresponding vertex/edge/face of P contains an equilibrium point with respect to o. Thus, Q satisfies the required properties. As we mentioned, an alternative way to prove Theorem 1.8 in Case 4 is using Lemma 3.9 and Corollary 3.10. Lemma 3.9. Let P G (S, U)E be a convex polyhedron with f faces and v vertices. Let qit i = 1,..., j — 1, j,..., m (j > 3), be successive vertices of an m-gonal (m > 3) face F of P such that (i) P has a stable equilibrium point cF on F, which is contained in the relative interior of the triangle T = conv{qi, qj-i, qj }; (ii) the edge E = [qj-1qj ] contains a saddle-type equilibrium point cE; (iii) the vertices qj, i = 2,..., j — 1 and i = j + 1,..., m, are trivalent; (iv) q1, cF and cE are not collinear. Then there exists a polyhedron P' G (S + 2, U)E with f + 2 faces and v + 1 vertices. Proof. In the proof, we show that for a sufficiently small pyramid erected over the triangle T = conv{q1, qj -1, qj } (which is contained by F and carries a stable equilibrium point) followed by a truncation of P by the plane of the three new faces of the pyramid, results in three new faces instead of F all carrying stable equilibrium and two new edges both carrying saddle-type equilibrium, see Figure 8 (subfigure (a)). Let the intersection point of the line through q1 and cF with E be denoted by x. We choose the apex q of the pyramid from a fixed, sufficiently small neighborhood V of x. Let U be the set of the centers of mass of the modified convex polyhedra, which we denote by P(q). We choose V in such a way that, apart from the three new faces and edges, and the new vertex, P(q) and P have equilibrium points on the same faces and edges, and at the same vertices. Furthermore, we choose V such that for all q G V, the face structure of the resulting polyhedron P(q) is the one described in the previous paragraph, and for any y G U, the Euclidean distance function from y on [qj-1,q] U [q, qj] has a unique 114 Ars Math. Contemp. 19 (2020) 125-145 (a) (b) Figure 8: Increasing the number of stable equilibria by two. Schematic view of the pyramid with three light faces instead of the original dark one denoted as F (a); view perpendicular to face F: full circles mean stable equilibrium points, the empty circle is the projection of c(a, fi, y) onto F (b); illustration for the application of the Cube Separation Theorem for compact sets Xa and X^ (c). local minimum, and this point is different from q, for all q G V. Note that the latter condition implies that the new vertex q is not an unstable equilibrium point. Thus, we need to prove only that, with a suitable choice of q, all the three new faces contain a new stable equilibrium point. We parametrize q using the following parameters: • the angle a of the plane of conv{qj_i, qj, q} and the plane of F. Here we assume that 0 < a < a0, where the sum of a0 and the dihedral angle of P at E is n; • the angle fi between two rays, both starting at q1, and containing qj_ 1 and the orthogonal projection qF of q onto the plane of F, respectively. Here we set < fi < fi2, where [fi1, fi2] is a sufficiently small interval containing the angle Zqj_1q1cF; • the angle y between the ray starting at q1 and containing q, and the plane of F. Here we assume that 0 < y < Yo for some small, fixed value y0. We choose the values of fi1, fi2, y0 such that in the permitted range of the parameters, q G V. For brevity, we may refer to P(q(a, fi, y)) as P(a, fi, y), c(P(a, fi, y)) as c(a, fi, y) and observe that these three quantities determine q. G. Domokos et al.: Balancing polyhedra 115 Note that, using the idea of the proof of Lemma 2.2, we have that |c(P(q)) - c(P)| = O(Y), and for some constant C > 0 independent of a, #,7, if |a' - a| < 7, then |c(a',#,7) - c(a,#,7)| < C72. Fix some 7 > 0, and let Xa be the set of pairs (a, #) G [0, a0] x [^1, #2] such that the planes through E, and containing c(a, 7) and q(a, 7), respectively, are perpendicular. Furthermore, let X^ be the set of pairs (a, #) G [0, a0] x , #2] such that q1, and the projections of c(a, 7) and q(a, 7) onto the plane of F are collinear. If 7 > 0 is sufficiently small, the property |c(P(q)) - c(P) | = O(7) implies that Xa strictly separates the sets {(0, #) : # G [^1, #2]} and {(a0, #) : # G [A, #2]}, and X^ strictly separates the sets {(a, : a G [0, a0]} and {(a, #2) : a G [0, a0]}. Since Xa and X^ are compact, we may apply the Cube Separation Theorem [27] as in the proof of Lemma 3.6. From this, it follows that there is some (aY, ) G Xa n X^. It is easy to see that (aY, ) G Xa implies that for sufficiently small values 7, the polyhedron P(aY, ,7) has stable equilibrium points on both faces containing the new edge [q1, q(aY, , 7)]. Furthermore, the orthogonal projection of c(aY, , 7) onto the plane containing E and q = q(aY, , 7) lies on E. Now, let us replace aY by a' = aY -7. Then, since in this case |c(a', , 7) -c(aY, , 7) | < C72, we have that if 7 is sufficiently small, then the orthogonal projection of c(a', , 7) onto the face conv{qj_1, qj, q(a', , 7)} lies inside the face; that is, P has a stable equilibrium point on this face. This yields the assertion. □ Corollary 3.10. If all conditions (i)-(iv) of Lemma 3.9 hold, then there is a polyhedron P'' G (S +1, U)E with f + 2faces and v + 1 vertices. 4 Monostatic polyhedra: proof of Theorem 1.9 Our theory of mechanical complexity highlights the special role of polyhedra in the first row and first column of the (S, U) grid. These objects have either only one stable equilibrium point (first row) or just one unstable equilibrium point (first column) and therefore they are called collectively monostatic. In particular, the first row is sometimes referred to as mono-stable and the first column as mono-unstable. Our theory provided only a rough lower bound for their mechanical complexity. While no general upper bound is known, individual constructions provide upper bounds for some particular classes; based on these values one might think that the mechanical complexity of these classes, in particular when both S and U are relatively low, is very high. Monostatic objects have peculiar properties, apparently the overall shape in these equilibrium classes is constrained. In [35] the thinness T and the flatness F of convex bodies is defined (1 < T, F < to) and it is shown that, for nondegenerate convex bodies, T =1 if and only if U = 1, and F =1 if and only if S =1. This constrained overall geometry may partly account for the high mechanical complexity of monostatic polyhedra. 4.1 Known examples The first (and probably best) known such object is the monostatic polyhedron PC constructed by Conway and Guy in 1969 [19] (cf. Figure 9) having mechanical complexity C(PC) = 96. Recently, there have been two additions: the polyhedron PB by Bezdek [2] (cf. Figure 10) and the polyhedron PR by Reshetov [28] with respective mechanical complexities C(PB) = 64 and C(PR) = 70. It is apparent that all of these authors were 116 Ars Math. Contemp. 19 (2020) 125-145 primarily interested in minimizing the number of faces on the condition that there is only one stable equilibrium, so, if one seeks minimal complexity in any of these classes it is possible that these constructions could be improved. Also, as we show below, the same ideas can be used to construct examples of mono-unstable polyhedra. The construction in [1 ] relies on a delicate calculation for a certain discretized planar spiral, defining a planar polygon P, serving as the basis of a prism which is truncated in an oblique manner (cf. Figure 9). The spiral consists of 2m similar right triangles, each having an angle ft = n/m at the point o. The cathetus of the smallest pair of triangles has length r0, and this will be the vertical height of o when the solid stands in stable equilibrium. Pc Figure 9: Schematic view of the monostatic polyhedron PC G (1,4)E, (19, 34)C constructed by Conway and Guy in 1969 [ ]. Stable, unstable and saddle-type equilibria are marked with sj, uj, , i =1, j = 1,2, 3,4, k = 1, 2,3, respectively. Complexity can be computed as C(pc) = 2(19 + 34 - 1 - 4) = 96. We denote the height of the center of mass c by r in the same configuration. It is evident from the construction that if P is a homogeneous planar disc then we have r > r0 since such a disc cannot be monostatic [17]. However, it is also clear that for a non-uniform mass distribution resulting in r < r0, P would be monostatic (cf. Figure 9). In the construction of Conway and Guy we can regard r as a function r(a, b) of the geometric parameters a, b (cf. Figure 9). Apparently, r(0, b) = ri and r(a, 0) = r2 are constants. If P is the aforementioned homogeneous disc then we have r = r2 > r0. Next we state a corollary to the main result of [ ]: Corollary 4.1. If m > 9 then r1 < r0. 4.2 Examples in (3,1)E and (2,1)E Consider a Conway construction with b = 0 and denote its vertical centroidal coordinate by r3: it equals the centroidal coordinate of a plane polygon depicted on the right of Figure 9. Now erect a mirror-symmetric pyramid over the polygon with its apex close to the bottom edge: the vertical coordinate of the body centre of the pyramid will then be close to 3r3/4. G. Domokos et al.: Balancing polyhedra 117 Figure 10: Schematic view of the monostotic polyhedron PB G (1, 3)E, (18,18)C constructed by Bezdek in 2011 [2]. Stable, unstable and saddle-type equilibria are marked with sj, uj, hk, i = 1, j = 1, 2, 3, k = 1,2, respectively. Complexity can be computed as C(PB) = 2(18 + 18 - 1 - 3) = 64. It can be shown that for a sufficiently flat pyramid (we call it P3) will be in classes (3,1)E and (18,18)C. Introducing a small asymmetry to P3 by moving the apex off the symmetry plane, apolyhedron P2 is obtained which belongs to classes (2,1)E and (18,18)C. These 'mono-unstable' polyhedra are illustrated in Figure 11. An overview of the discussed monostatic polyhedra is shown in Figure 12 on an overlay of the (f, v)C and (S, U)E grids. 4.3 Proof of Theorem 1.9 Proof. Consider the case C (1, U) first. The polyhedron PC has a narrow rectangular face with a stable point and two saddle points on opposite short edges of the same face. They do not satisfiy condition (i) of Lemma 3.6 because of being collinear, but both 17-gonal faces of PC can slightly be rotated to get PC according to Remark 2.1 in a way that no equilibrium points appear or disappear but the two edges with saddle points become nonparallel, and thus Lemma 3.6 turns to be applicable. Since the same face of PC contains four unstable points as well (and none of them is collinear with the stable and any saddle point), Corollary 3.7 can directly be applied to get Pd with C(Pd) = C(Pc) + 2 = 98. It means that C(1,4) < 2R(1,4) + 90 and C(1, 5) < 2R(1,5) + 90. Applying now Lemma 3.6 on both PC and PD successively, the assertion readily follows. Note that PB could not be used as departure instead of PC, since its saddle points are not on edges of the same face. A similar path is taken for the case C(S, 1). Depart now P3 with C(P3) = 64: that polyhedron has a 17-gonal face with a stable equilibrium and there is a vertex and an edge on its perimeter having an unstable and a saddle point, respectively. Now it is possible again to slightly rotate the plane of the symmetric triangular face about an axis which is perpendicular to the 17-gon and runs through the apex of the pyramid, making the stable (s3) and saddle (h1) point to move off the symmetry axis of the 17-gon, so that they become non-collinear with ui (Remark 2.1 guarantees that it can always be done without changing the number of equilibrium points of any kind). Applying or not Corollary 3.10 first then 118 Ars Math. Contemp. 19 (2020) 125-145 P3 P2 Figure 11: Schematic view of two polyhedra P3 G (3,1)E, (18,18)C and P2 € (2,1)E, (18,18)C, obtained by using the ideas of the Conway and Bezdek constructions. Stable, unstable and saddle-type equilibria are marked with sj, uj, . In case of P3 we have i = 1,2,3, j = 1, k =1,2 and in case of P2 we have i = 1,2, j = 1, k =1. Complexity can be computed as C(P3) = 2(18+18-3-1) = 64, C(P2) = 2(18+18-2-1) = 66. Lemma 3.9 successively gives C(S, 1) < S + 61 and C(S, 1) < S + 62 for odd and even S, respectively, which is equivalent to the second statement of the theorem. □ 4.4 Gombocedron prize While the construction of monostatic polyhedra with less than 34 edges appears to be challenging (cf. Figure 12), the only case which has been excluded is the tetrahedron with e = 6 edges. It also appears to be very likely that Gomboc-like polyhedra in class (1,1)E do exist, however, based on this chart and the previous results, one would expect polyhedra with high mechanical complexity. To further motivate this research we offer a prize for establishing the mechanical complexity C(1,1), the amount p of the prize is given in US dollars as _ 106 p = C (1,1). 5 Generalizations and applications 5.1 Complexity of secondary equilibrium classes A special case of Theorem 1.8 states that for any polyhedral pair (f, v) one can construct a homogeneous polyhedron P with f faces and v vertices in such a manner that C(P) = 0. In other words, in any primary combinatorial class there exist polyhedra with zero complexity. A natural generalization of this statement is to ask whether this is also true for any secondary combinatorial class of convex polyhedra. While we do not have this result, G. Domokos et al.: Balancing polyhedra 119 1 18 24 34 Figure 12: Polyhedra with a single stable or unstable equilibrium point. The grid shown is an overlay of the (f, v) and the (S, U) grids. White squares correspond to polyhedral pairs. Location of monostatic polyhedra is shown with black capital letters on the (f, v) grid and white capital letters on the (S, U) grid. Abbreviations: PC: Conway and Guy, 1969 [19], PB: Bezdek, 2011 [2], PR: Reshetov, 2014 [28]. P2,P3: current paper, Figure 11. Complexity for these polyhedra can be readily computed as c(pc) = 96, C(pB) = 64, C(pR) = 70, C(P3) = 64, C(P2) = 66. we present an affirmative statement for the inhomogeneous case: Proposition 5.1. Let P be a Koebe polyhedron, i.e. a convex polyhedron midscribed (edge-circumscribed) about the unit sphere S2 with center o. Then every face, edge and vertex of P carries an equilibrium point with respect to o. Proof. By (1.1) and (1.2) it is sufficient to show that every edge of P contains an equilibrium point with respect to o. Let E be an edge of P that touches S2 at a point q, and let H be the plane touching S2 at q. Clearly, H is orthogonal to q, and since every face of P intersects the interior of the sphere, we have H n P = E. Thus, q is an equilibrium point of P with respect to o. □ Here it might be worth noting that for any convex body K and any point p G int K there is a density function p: K ^ [0, to) such that the center of mass of K with respect to this density function is p, implying that Proposition 5.1 can indeed be reformulated in terms of Koebe polyhedra with inhomogeneous densities. Thus, since a variant of the Circle Packing Theorem [4] states that every combinatorial class contains a Koebe polyhedron, it follows that every combinatorial class contains an inhomogeneous polyhedron with zero mechanical complexity. To find a homogeneous representative appears to be a challenge. In [24], the author strengthened the result in [4] by showing the existence of a Koebe polyhedron P in each combinatorial class such that the center of mass of the k-dimensional skeleton of P, where k = 0,1 or 2, coincides with o. This result and Proposition 5.1 imply that replacing c(P) by the center of mass of the k-skeleton of a polyhedron with 0 < k < 2, every combinatorial class contains a polyhedron with zero mechanical complexity. 120 Ars Math. Contemp. 19 (2020) 125-145 5.2 Inverse type questions The basic goal of this paper is to explore the nontrivial links between the combinatorial (f,v)C and the mechanical (S,U)E classification of convex polyhedra. The concept of mechanical complexity (Definition 1.2) helps to explore the (S, U)E ^ (f, v)C direction of this link. Inverse type questions may be equally useful to understand this relationship: for example, a natural question to ask is the following: Is it true that any equilibrium class (S, U)E intersects all but at most finitely many combinatorial classes (f, v)C? Here it is worth noting that it is easy to carry out local deformations on a polyhedron that increase the number of faces and vertices, but not the number of equilibria. Alternatively, one may ask to provide the list of all (S, U)E classes represented by homogeneous polyhedra in a given combinatorial class (f,v)C. A similar question may be asked for a secondary combinatorial class of polyhedra. In general, we know little about the answers, however we certainly know that (1.3) holds and we also know that S = f,U = v is a part of this list. The minimal values for S and U are less clear. In particular, based on our previous results it appears that the values S = 1 and U = 1 can be only achieved for sufficiently high values of f,v. On the other hand, Theorem 1.10 and Lemma 3.4 resolve this problem at least for the (4,4)C class. The latter is based on a global numerical search and this could be done at least for some polyhedral classes, although the computational time grows with exponent (f + v). 5.3 Inhomogeneity and higher dimensions While here we described only 3D shapes, the generalization of Definitions 1.2 and 1.3 to arbitrary dimensions is straightforward. While the actual values of mechanical complexity are trivial in the planar case (class (2)E has mechanical complexity 2 and every other equilibrium class has mechanical complexity zero), the d > 3 dimensional case appears an interesting question in the light of the results of Dawson et al. on monostatic simplices in higher dimensions [6, 7, 8]. We formulated all our results for homogeneous polyhedra, nevertheless, some remain valid in the inhomogeneous case which also offers interesting open questions. In particular, the universal lower bound (1.3) is independent of the material density distribution so it remains valid for inhomogeneous polyhedra and as a consequence, so does Theorem 1.8. However, our other results (in particular the bounds for monostatic equilibrium classes) are only valid for the homogeneous case. In the latter context it is interesting to note that Conway proved the existence of inhomogeneous, monostatic tetra-hedra [7]. 5.4 Classification of centric minimal polyhedra Recall from Subsection 3.1 that a 3-dimensional convex polyhedron is called a minimal polyhedron if its every vertex, edge and face contains an equilibrium point. To further specify these polyhedra, we define a centric minimal polyhedron P as a minimal polyhedron with the additional property that the orthogonal projection of the center of mass of P onto the affine hull of every face/edge of P coincides with the center of mass of the corresponding face/edge of P. It is worth noting that the notions of both minimal polyhedra and centric minimal polyhedra can be defined for d-dimensional convex polytopes in an analogous manner for any d > 2. Then, for any centric minimal d-polytope P and k-face F, F is a centric minimal k-polytope. G. Domokos et al.: Balancing polyhedra 121 Problem 5.2. Characterize the family of centric minimal polyhedra in R3. In Proposition 5.3 we collect some elementary properties of centric minimal polyhedra. Proposition 5.3. Let P C Rd with d > 2 be a d-dimensional convex polytope. (i) If d = 2, then P is a centric minimal polygon if and only if every vertex of P is at the same distance from the center of mass of P. (ii) If d > 3 and P is a centric minimal polytope, then every vertex of P is at the same distance from the center of mass of P. Proof. Let o be the center of mass of P. Then the orthogonal projection of o onto the line through any edge of P is the midpoint of the edge, which yields that the two endpoints of the edge are at the same distance from o. Thus, both (i) and (ii) follow from the connectedness of the edge graph of P. □ By relaxing the definition of centric minimal polyhedra, we may define a weakly centric d-dimensional minimal polytope P as a minimal polytope such that the orthogonal projection of the center of mass of P onto the affine hull of every (d - 1)-face of P coincides with the center of mass of the corresponding (d - 1)-face of P. Problem 5.4. Characterize the family of weakly centric minimal polyhedra in R3. 5.5 Applications Here we describe some problems in mineralogy, geomorphology and industry where the concept of mechanical complexity could potentially contribute to the efficient description and the better understanding of the main phenomena. 5.5.1 Crystal shapes Crystal shapes are probably the best known examples of polyhedra appearing in Nature and the literature on their morphological, combinatorial and topological classification is substantial [22]. However, as crystals are not just geometric objects but also (nearly homogeneous) 3D solids, their equilibrium classification appears to be relevant. The number of static balance points has been recognized as a meaningful geophysical shape descriptor [11, 18, 33] and it has also been investigated in the context of crystal shapes [32]. The theory outlined in our paper may help to add new aspects to their understanding. While the study of a broader class of crystal shapes is beyond the scope of this paper, we can illustrate this idea in Figure 13 by two examples of quartz crystals with identical number of faces displaying a large difference in mechanical complexity. The length a of the middle, prismatic part of the hexagonal crystal shape (appearing on the left side of Figure 13) is not fixed in the crystal. As we can observe, for sufficiently small values of the length a the crystal will be still in the same combinatorial class (18,14)C, however, its mechanical complexity will be reduced to zero. 5.5.2 Random polytopes, chipping models and natural fragments There is substantial literature on the shape of random polytopes [29] which are obtained by successive intersections of planes at random positions. Under rather general assumptions 122 Ars Math. Contemp. 19 (2020) 125-145 Figure 13: Quartz crystals. Left: Hexagonal habit in classes (18,14)C and (6, 2)E, C(P) = 48. Right: Cumberland habit [36] in classes(18, 32)C and (12,8)E, C(P) = 60. Picture source [26]. on the distribution of the intersecting planes it can be shown that the expected primary combinatorial class of such a random polytope is (6,8)C (see Theorem 10.3.1 in [29]), however, there are no results on the mechanical complexity. A very special limit of random poly-topes can be created if we use a chipping model [13, 23] where one polytope is truncated with planes in such a manner that the truncated pieces are small compared to the polytope. Although not much is known about the combinatorial properties of these polytopes, it can be shown [15] that under a sufficiently small truncation the mechanical complexity either remains constant or it increases (this is illustrated in Figure 1). Apparently, random poly-topes can be used to approximate natural fragments [12, 14]. There is data available on the number and type of static equilibria of the latter, so any result on the mechanical complexity of random polytopes could be readily tested and also used to identify fragmentation processes. 5.5.3 Assembly processes In industrial assembly processes parts are processed by a feeder and often these parts can be approximated by polyhedra. These polyhedra arrive in a random orientation on a horizontal surface (tray) and end up ultimately on one of their faces carrying a stable equilibrium. Based on the relative frequency of this position, one can derive face statistics and the throughput of a part feeder is heavily influenced by the face statistics of the parts processed by the feeder. Design algorithms for feeders are often investigated from this perspective [3, 34]. It is apparent that one key factor determining the entropy of the face statistics is the mechanical complexity of the polyhedron, in particular, higher mechanical complexity leads to better predictability of the assembly process so this concept may add a useful aspect to the description of this industrial problem. 5.6 Concluding remarks We showed an elementary connection between the Euler and Poincare-Hopf formulae (1.1) and (1.2): the mechanical complexity of a polyhedron is determined jointly by its equilib- G. Domokos et al.: Balancing polyhedra 123 rium class (S, U)E and combinatorial class (f, v)C. Mechanical complexity appears to be a good tool to highlight the special properties of monostatic polyhedra and offers a new approach to the classification of crystal shapes. We defined polyhedral pairs (x, y) of integers (cf. Definition 1.4) and showed that they play a central role in both classifications: they define all possible combinatorial classes (f, v)C while in the mechanical classification they correspond to classes with zero complexity. ORCID iDs Florian Kovacs S> https://orcid.org/0000-0002-8374-8035 Zsolt Langi © https://orcid.org/0000-0002-5999-5343 References [1] J. E. Auerbach and J. C. Bongard, On the relationship between environmental and mechanical complexity in evolved robots, Artif. Life 13 (2012), 309-316, doi:10.7551/ 978-0-262-31050-5-ch041. [2] A. Bezdek, On stability of polyhedra, 2011, a lecture given at the Fields Institute, Canada, on September 14, 2011 as part of the Workshop on Discrete Geometry (September 13 - 16, 2011), https://www.fields.utoronto.ca/audio/11-12/wksp_ geometry/bezdek/. [3] K. F. Bohringer, B. R. Donald, L. E. Kavraki and F. Lamiraux, Part orientation with one or two stable equilibria using programmable vector fields, IEEE Trans. Robot. Automat. 16 (2000), 157-170, doi:10.1109/70.843172. [4] G. R. Brightwell and E. R. Scheinerman, Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), 214-229, doi:10.1137/0406017. [5] J. H. Conway and R. K. Guy, Stability of polyhedra, SIAM Rev. 8 (1966), 381-381, doi:10. 1137/1008075. [6] R. Dawson, W. Finbow and P. Mak, Monostatic simplexes II, Geom. Dedicata 70 (1998), 209219, doi:10.1023/a:1004941706441. [7] R. J. MacG. Dawson, Monostatic simplexes, Amer. Math. Monthly 92 (1985), 541-546, doi: 10.2307/2323158. [8] R. J. MacG. Dawson and W. Finbow, Monostatic simplexes III, Geom. Dedicata 84 (2001), 101-113, doi:10.1023/a:1010339220243. [9] R. J. MacG. Dawson and W. A. Finbow, What shape is a loaded die?, Math. Intelligencer 21 (1999), 32-37, doi:10.1007/bf03024844. [10] P. Diaconis and J. B. Keller, Fair dice, Amer. Math. Monthly 96 (1989), 337-339, doi:10.2307/ 2324089. [11] G. Domokos, Natural numbers, natural shapes, Axiomathes (2018), doi:10.1007/ s10516-018-9411-5. [12] G. Domokos, D. J. Jerolmack, F. Kun and J. Torok, Plato's cube and the natural geometry of fragmentation, Proc. Natl. Acad. Sci. USA 117 (2020), 18178-18185, doi:10.1073/pnas. 2001037117. [13] G. Domokos, D. J. Jerolmack, A. A. Sipos and A. Torok, How river rocks round: Resolving the shape-size paradox, PLoS One 9 (2014), 1-7, doi:10.1371/journal.pone.0088657. [14] G. Domokos, F. Kun, A. A. Sipos and T. Szab6, Universality of fragment shapes, Sci. Rep. 5 (2015), Article 9147, doi:10.1038/srep09147. [15] G. Domokos and Z. Langi, The robustness of equilibria on convex solids, Mathematika 60 124 Ars Math. Contemp. 19 (2020) 125-145 (2014), 237-256, doi:10.1112/s0025579313000181. [16] G. Domokos, Z. Langi and T. Szabo, A topological classification of convex bodies, Geom. Dedicata 182 (2016), 95-116, doi:10.1007/s10711-015-0130-4. [17] G. Domokos, J. Papadopulos and A. Ruina, Static equilibria of planar, rigid bodies: is there anything new?, J. Elasticity 36 (1994), 59-66, doi:10.1007/bf00042491. [18] G. Domokos, A. A. Sipos, T. Szabo and P. L. Varkonyi, Pebbles, shapes and equilibria, Math. Geosci. 42 (2010), 29-47, doi:doi.org/10.1007/s11004-009-9250-4. [19] M. Goldberg and R. K. Guy, Problem 66-12, Stability of polyhedra (by J. H. Conway and R. K. Guy), SIAMRev. 11 (1969), 78-82, doi:10.1137/1011014. [20] B. Grunbaum, Convex Polytopes, volume 221 of Graduate Texts in Mathematics, SpringerVerlag, New York, 2nd edition, 2003, doi:10.1007/978-1-4613-0019-9. [21] S. Huang and D. Ingber, The structural and mechanical complexity of cell-growth control, Nat. Cell Biol. 1 (1999), E131-E138, doi:10.1038/13043. [22] C. Klein, Minerals and Rocks: Exercises in Crystal and Mineral Chemistry, Crystallography, X-ray Powder Diffraction, Mineral and Rock Identification, and Ore Msineralogy, Wiley, 3rd edition, 2007. [23] P. L. Krapivsky and S. Redner, Smoothing a rock by chipping, Phys. Rev. E 75 (2007), 031119 (7 pages), doi:10.1103/physreve.75.031119. [24] Z. Langi, Centering Koebe polyhedra via Mobius transformations, Groups Geom. Dyn. (2020), in press. [25] J. W. Milnor, Topology from the Differentiable Viewpoint, The University Press of Virginia, Charlottesville, Virginia, 1965. [26] Mindat.org, Quartz, About Quartz, https://www.mindat.org/min-33 37.html. [27] M. M. Postnikov, Lectures in Geometry, Semester III, Smooth Manifolds, MIR Publishers, Moscow, 1989, translated from Russian by V. V. Shokurov. [28] A. Reshetov, A unistable polyhedron with 14 faces, Internat. J. Comput. Geom. Appl. 24 (2014), 39-59, doi:10.1142/s0218195914500022. [29] R. Schneider and W. Weil, Stochastic and Integral Geometry, Probability and its Applications (New York), Springer-Verlag, Berlin, 2008, doi:10.1007/978-3-540-78859-1. [30] E. Steinitz, Uber die Eulersche Polyederrelationen, Arch. Math. Phys. 11 (1906), 86-88. [31] E. Steinitz, Polyeder und Raumeinteilungen, in: W. F. Meyer and H. Mohrmann (eds.), Encyk-lopadie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, Band III.1.2, Teubner, Leipzig, pp. 1-139, 1922. [32] T. Szabo and G. Domokos, A new classification system for pebble and crystal shapes based on static equilibrium points, Cent. Eur. Geol. 53 (2010), 1-19, doi:10.1556/ceugeol.53.2010.1.1. [33] T. Szabo, S. Fityus and G. Domokos, Abrasion model of downstream changes in grain shape and size along the Williams River, Australia, J. Geophys. Res. Earth Surf. 118 (2013), 20592071, doi:10.1002/jgrf.20142. [34] P. L. Varkonyi, Estimating part pose statistics with application to industrial parts feeding and shape design: New metrics, algorithms, simulation experiments and datasets, IEEE Trans. Au-tom. Sci. Eng. 11 (2014), 658-667, doi:10.1109/tase.2014.2318831. [35] P. L. Varkonyi and G. Domokos, Static equilibria of rigid bodies: Dice, pebbles and the Poincare-Hopf theorem, J. Nonlinear Sci. 16 (2006), 255-281, doi:10.1007/ s00332-005-0691-8. [36] J. S. White, Let's get it right: The cumberland habit, Rocks Miner. 78 (2003), 196-197, doi: 10.1080/00357529.2003.9926720. [37] Wikipedia contributors, Dice — Wikipedia, The Free Encyclopedia, http://en. wikipedia.org/wiki/Dice.