From acute sets to centrally symmetric $2$-neighborly polytopes
Isabella Novik
math.CO



Kaonic deuterium and low-energy antikaon-nucleon interaction
    Wataru Horiuchi1whoriuchi@nucl.sci.hokudai.ac.jp Tetsuo Hyodo2hyodo@yukawa.kyoto-u.ac.jp Wolfram Weise3weise@tum.de
        

    December 30, 2023
=================================================================================================================================



 What is the maximum number of vertices that a centrally symmetric 2-neighborly polytope of dimension d can have? It is known that the answer does not exceed 2^d. Here we provide an explicit construction showing that it is at least 2^d-1+2.







§ INTRODUCTION

The goal of this note is to construct centrally symmetric 2-neighborly polytopes with many vertices. Recall that a polytope is the convex hull of a set of finitely many points in ^d. The dimension of a polytope P is the dimension of its affine hull. We say that P is a d-polytope if the dimension of P is equal to d. A polytope P is centrally symmetric (cs, for short) if for every x∈ P, -x belongs to P as well. 

A cs polytope P is called k-neighborly if every set of k of its vertices, no two of which are antipodes, is the vertex set of a face of P. In addition to being of intrinsic interest, the study of cs k-neighborly polytopes is motivated by the recently discovered tantalizing connections (initiated by Donoho and his collaborators <cit.>) between such polytopes and seemingly distant areas of error-correcting codes and sparse signal reconstruction. It is also worth mentioning that in contrast with the situation for polytopes without a symmetry assumption, a cs d-polytope with sufficiently many vertices cannot be even 2-neighborly <cit.>. 

A few more definitions are in order. A set S⊂^d is acute if every three points from S determine an acute triangle. A set S⊂^d is antipodal if for every two points x,y∈ S, there exist two (distinct) parallel hyperplanes H_x and H_y such that x∈ H_x, y∈ H_y, and all elements of S lie in the closed strip defined by H_x and H_y. 

It is well-known and easy to check that any acute set is antipodal. Similarly, as was observed in <cit.>, the vertex set of any cs 2-neighborly polytope P⊂^d is antipodal. Furthermore, according to a celebrated theorem of Danzer and Grünbaum  <cit.> (see also <cit.>), an antipodal subset of ^d has at most 2^d elements, and it has exactly 2^d elements if and only if it is the vertex set of a parallelepiped. Since the vertex set of a parallelepiped is not acute and since a d-parallelepiped (for d>2) is not cs 2-neighborly, it follows that any acute set S⊂^d has at most 2^d-1 elements, while any cs 2-neighborly d-polytope P with d≥ 3 has at most 2^d-2 vertices.

Although the size of the largest acute set in ^d remains a mystery, in a very recent breakthrough paper <cit.>, Gerencsér and Harangi constructed an acute set in ^d of size 2^d-1+1. The previous record size was F_d+2=Θ((1+√(5)/2)^d), where F_n is the n-th Fibonacci number, see <cit.>. 

Similarly, the current record size of the vertex set of a cs 2-neighborlly d-polytope is about √(3)^d, <cit.>. We modify the construction of Gerencsér and Harangi to establish the following result.

 
There exists a cs 2-neighborly d-polytope with 2^d-1+2 vertices.


We say that a (finite) set S⊂^d∖{0} is cs if for every x∈ S, the point -x is also in S. Observe that a cs set can never be acute: indeed, for any x,y∈^d, the parallelogram determined by x, y, -x, -y has a non-acute angle. The main insight of this note is the notion of an almost acute set: a set S is almost acute 
if it is cs and for every ordered triple (x,y,z) of distinct points in S, the angle ∠ xyz is acute as long as x and z are not antipodes. 

With this definition in hand, the following two results yield Theorem <ref>.
 
Let S⊂^d be a cs set that spans ^d, and let P=(S). If S is almost acute, then P is a cs 2-neighborly d-polytope whose vertex set is S.


 
There exists an almost acute subset of ^d of size 2^d-1+2.

To prove Lemma <ref> we modify the Gerencsér–Harangi construction: as in <cit.>, we start with the vertex set of the (d-1)-cube [-1,1]^d-1 embedded in the coordinate hyperplane ^d-1×{0} of ^d. We then use the extra dimension to perturb the vertices in such a way that the resulting set in ^d is almost acute. (In particular, any pair of antipodes is perturbed to a pair of antipodes.) Adding to this set a pair of antipodes of the form (0,…,0, c) and (0,…,0, -c), where c∈ is sufficiently large, completes the construction.


The proofs of Lemmas <ref> and <ref> are given in Sections 2 and 3, respectively. We close in Section 4 with some remarks and open problems. 




§ POLYTOPES WITH AN ALMOST ACUTE VERTEX SET

The goal of this section is to prove Lemma <ref>. For all undefined terminology pertaining to polytopes, we refer our readers to Ziegler's book <cit.>. Thus, assume that S⊂^d is an almost acute set that spans ^d. Then P:=(S) is a cs d-polytope whose vertex set is contained in S. To prove the lemma, we have to show that (i) every x∈ S is a vertex of P, and (ii) for every x,y∈ S with y∉{x,-x}, the line segment [x,y] is an edge of P.

Let x be any element of S. Let H be the hyperplane that contains x and is perpendicular to the line segment [-x,x]. Since S is an almost acute set, for every y∈ S∖{-x,x}, the angle ∠ (-x)xy is acute, so that y lies in the same open half-space of ^d defined by H as -x. It follows that H is a supporting hyperplane of P and that H∩ P={x}. Hence x is a vertex of P.

Now, let x,y be any elements of S with y∉{x,-x}. Consider parallelogram Q with vertices x,y,-x,-y. There are two possible cases:

Case 1: Q is a rectangle. Let H be the hyperplane perpendicular to the line segment [-y,x] and passing through x, and hence also through y. Since S is an almost acute set, for every z∈ S∖{x, -y, y}, the angle ∠(-y)xz is acute, so that z lies in the same open half-space of ^d defined by H as -y. We conclude that H is a supporting hyperplane of P and that H∩ P=(x,y)=[x,y]. Thus [x,y] is an edge of P. 

Case 2: Q is not a rectangle. In this case exactly one of the angles ∠ (-y)xy, ∠ (-x)yx is obtuse. Without loss of generality (by switching the roles of x and y if necessary), we may assume that ∠ (-y)xy is obtuse. As in Case 1, let H be the hyperplane perpendicular to the line segment [-y,x] and passing through x. Our assumption that S is almost acute then yields that all elements of S∖{x,y, -y} are contained in the same (open) side of H as -y, while y lies on the opposite side of H. Therefore, either [x,y] is an edge of P, in which case we are done, or all neighbors of x in P lie on the side of H that does not contain y. In this latter case, the cone based at x and spanned by the rays from x to the neighbors of x does not contain y. This however contradicts the well-known fact (see <cit.>) that such a cone must contain P, and hence also y. The lemma follows.



§ CONSTRUCTION OF AN ALMOST ACUTE SET
 
In this section we prove Lemma <ref>. To do so, we constract an almost acute set in ^d of size 2^d-1+2. We start with the set S^0 described below; we then perturb the points of S^0 to obtain an almost acute set. As our construction/proof is a simple modification of that in <cit.>, we only sketch the main ideas leaving out some of the details.

Pick a real number c>√(d-1) and consider the following subset of ^d of size 2^d-1+2:

    S^0:={(δ_1,…,δ_d-1,0) |δ_1,…,δ_d-1∈{± 1}}∪{(0,…,0,± c)}.

Thus, S^0 consists of the vertex set V^0 of the (d-1)-cube [-1,1]^d-1×{0}⊂^d
 and two additional points, x_0 and -x_0, positioned high above and far below the center of the cube, respectively. An easy computation shows that for all distinct y,z∈ V^0, the angles ∠(± x_0)yz, ∠ y(± x_0)z, ∠(± x_0)(∓ x_0)y are acute, and, assuming also that z≠ -y, so is ∠ y(-y)z. Hence there exists an ϵ_0>0 such that if all vertices of the cube are perturbed by no more than ϵ_0, then all of the above angles remain acute.  Therefore, to complete the proof, it suffices to perturb the vertices of V^0 in such a way that (i) antipodes are perturbed to antipodes, and (ii) for all x,y,z∈ V^0 no two of which are antipodes, the perturbed triangle is acute.

The key fact we will use is the following lemma from <cit.>:
 
Let V^0 be the vertex set of the (d-1)-cube  [-1,1]^d-1×{0}⊂^d. For every ϵ>0 and x∈ V^0, there exists x'∈^d such that x' is within distance ϵ from x and the angles ∠ x'yz and ∠ yx'z are acute for all y,z ∈  V^0∖{x}.


Arbitrarily order the elements of V^0, so that  V^0={x_1,-x_1,x_2,-x_2,…, x_2^d-2, -x_2^d-2}. We induct on 1≤ p≤ 2^d-2, to construct a set  V^p={x'_1,-x'_1, …, x'_p,-x'_p}∪{x_j, -x_j | p<j≤ 2^d-2} with the property that (a) for all 1≤ i≤ p, x'_i-x_i<ϵ_0, and (b) for every three points x, y, z of V^p no two of which are antipodes and such that x=± x'_i for some 1≤ i≤ p, the angles ∠ xyz and ∠ yxz are acute. We refer to (a) and (b) combined as the (*_p)-property.

Assume V^p-1 satisfies the (*_p-1)-property. In particular, for every three points x'_i, y, z of V^p-1 no two of which are antipodes, the angles ∠ (± x'_i)yz and ∠ y(± x'_i)z are acute. Hence there exists an 0<ϵ_p<ϵ_0, such that if x_p and -x_p are perturbed by no more than ϵ_p, then all of the above angles involving ± x_p (as y or z) remain acute. Furthermore, by Lemma <ref>, there exists x'_p within distance ϵ_p of x_p such that for all y,z∈{x_j, -x_j | p<j≤ 2^d-2}, the angles ∠ x'_pyz and ∠ yx'_pz are acute. Since the set {x_j, -x_j | p<j≤ 2^d-2} is cs, it follows that the angles ∠(-x'_p)yz and ∠ y(-x'_p)z are also acute. We conclude that V^p satisfies the (*_p)-property. The set S:=V^2^d-2∪{x_0,-x_0} is then an almost acute set of size 2^d-1+2. This completes the proof of Lemma <ref>, and hence also of Theorem <ref>.



§ CONCLUDING REMARKS AND OPEN PROBLEMS

We close with a few open problems.

The main result of this note together with <cit.> and the Danzer–Grünbaum theorem <cit.> implies that for d≥ 3, the maximum number of vertices that a cs 2-neighborly d-polytope can have lies in the interval [2^d-1+2, 2^d-2]. In dimension three, the only cs 2-neighborly polytope is the cross-polytope, which indeed has 6=2^2+2=2^3-2 vertices. In dimension four, the maximum is 10=2^3+2; this result is due to Grünbaum, see <cit.>. However, for d>4, the exact value of the maximum remains unknown. 

A related question is what is the maximum number of edges, (d;N), that a cs d-polytope with N vertices can have. At present, it is known that 

    (1-3^-⌊ d/2-1⌋)N  2≤(d;N) ≤(1-2^-d)N^2/2;

see <cit.> and <cit.> for the lower and the upper bound, respectively. However, the exact value of (d;N) or even its asymptotics remains a mystery. The main result of this paper makes us believe that (d;N) might be closer to the right-hand side of Eq. (<ref>) than to the left one.

Finally, it would be interesting to understand the maximum number of vertices that a cs 3-neighborly d-polytope can have. It is known that there exist cs 3-neighborly d-polytopes with ≈ 2^0.023d vertices, see <cit.>. On the other hand, an argument similar to the proof of <cit.>, shows that a cs d-polytope with ⌈ 2√(2)· 3^0.5d⌉ or more vertices cannot be 3-neighborly.



§ ACKNOWLEDGEMENTS
 The author is grateful to a participant of the mathematical forum dxdy.ru, who wished to remain anonymous, for bringing reference <cit.> to our attention.

plain

