Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

Gennadiy Averkov, Jan Krümpelmann, Benjamin NillAdvances 2015 · DOI · arXiv

Introduction

In the field of discrete geometry, the study of lattice polytopes—shapes whose vertices lie on integer coordinates—provides a bridge between pure geometry, number theory, and optimization. A central question in this field concerns the constraints placed on a polytope when it is required to contain a specific number of interior lattice points. In 1983, Douglas Hensley conjectured specific bounds on the "lopsidedness" or asymmetry of such shapes. This paper, published in 2014, provides the definitive solution to Hensley’s conjecture and establishes sharp bounds for the volume and lattice diameter of $d$-dimensional integral simplices containing exactly one interior point.

The Geometry of Lattice Simplices

An integral simplex in $\mathbb{R}^d$ is the convex hull of $d+1$ points with integer coordinates. A well-known property of these shapes is that if they contain no interior lattice points (often called "empty" or "primitive" simplices), their volume can be arbitrarily large as they become increasingly thin. However, the geometric landscape changes dramatically when the simplex is constrained to contain exactly one interior lattice point. In this scenario, the volume becomes bounded by a function of the dimension $d$.

The challenge for mathematicians has been to identify the "maximal" such simplex—the one that stretches the limits of volume and asymmetry while still trapping only a single point.

Hensley's Conjecture and the Coefficient of Asymmetry

Hensley’s 1983 conjecture focused on the "coefficient of asymmetry." If $P$ is a convex body and $z$ is its unique interior lattice point, the coefficient of asymmetry measures how far $z$ is from the centroid or how "off-center" it is relative to the vertices. Specifically, for any chord through $z$, the ratio of the lengths of the two segments defined by $z$ must be bounded.

The authors prove that for a $d$-dimensional polytope with one interior point, the maximum coefficient of asymmetry is exactly $s_{d+1} - 2$, where $s_n$ represents the terms of the Sylvester sequence.

The Role of the Sylvester Sequence

The Sylvester sequence ($2, 3, 7, 43, 1807, \dots$) is defined by the recurrence $s_n = 1 + \prod_{i=1}^{n-1} s_i$, or equivalently $s_n = s_{n-1}^2 - s_{n-1} + 1$. This sequence appears frequently in problems involving Egyptian fractions and, as this paper demonstrates, is fundamental to the structure of maximal lattice simplices.

The "largest" simplices are not balanced or "round." Instead, they are characterized by extreme stretching. The unique interior point is positioned extremely close to one facet, with its barycentric coordinates defined by the reciprocals of the Sylvester sequence terms. This configuration allows the simplex to extend vast distances in certain directions without encompassing additional grid points.

Methodology: From Geometry to Optimization

The authors employ several sophisticated techniques to bridge geometry and number theory:

  • Barycentric Coordinates: By representing the interior point $z$ as a weighted average of the vertices $v_0, \dots, v_d$, such that $z = \sum \beta_i v_i$ (where $\sum \beta_i = 1$), the geometric problem is transformed into an algebraic one. The "one interior point" constraint imposes strict conditions on the values of $\beta_i$.
  • Izhboldin-Kurliandchik Problems: The proof relies on solving a specific class of analytical optimization problems. The authors seek to minimize the product of the weights $\beta_i$ under constraints, which directly relates to maximizing the volume of the simplex.
  • Duality and Polar Bodies: To extend the results from simplices to more general convex polytopes, the authors utilize the concept of polar bodies. This allows them to derive bounds that are applicable in the context of algebraic geometry, specifically regarding toric varieties.

Key Results and Implications

The paper provides several sharp (exact) bounds that settle long-standing questions:

  • Solution to Hensley's Conjecture: The maximum coefficient of asymmetry for a polytope with one interior point is confirmed as $s_{d+1} - 2$.
  • Sharp Volume Bound: For a $d$-dimensional integral simplex $S$ with one interior point, the volume is bounded by: $$\text{vol}(S) \le \frac{2}{d!}(s_d - 1)^2$$
  • Lattice Diameter: The authors determined that the lattice diameter of an integral polytope with $k$ interior points is at most $(k+1)(s_d - 1)$.
  • Toric Geometry: In the realm of algebraic geometry, these results translate to new bounds for the anticanonical degree of $\mathbb{Q}$-factorial toric Fano varieties with Picard number 1.

Conclusion and Future Directions

While the paper successfully resolves the case for $k=1$ interior point, it opens new avenues for research regarding $k > 1$. The authors propose a candidate simplex, $S^d_k$, which they suspect maximizes volume for multiple interior points, but a formal proof of its optimality remains an open challenge.

Furthermore, the results have practical implications for integer programming. The bounds on lattice diameter are directly relevant to "cutting-plane" methods, providing a theoretical limit on the complexity of certain optimization algorithms. As the dimension $d$ increases, the Sylvester sequence grows double-exponentially, indicating that these maximal shapes become astronomically large and asymmetric, presenting unique challenges for high-dimensional computational geometry.

Summary updated

BibTeX
@inproceedings{averkov2015largest,
  author = {Gennadiy Averkov and Jan Krümpelmann and Benjamin Nill},
  title = {{Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results}},
  booktitle = {Advances},
  year = {2015},
  doi = {10.1016/j.aim.2014.12.035},
}

Loading related content...

Figure