Difference between families of weakly and strongly maximal integral lattice-free polytopes

Gennadiy AverkovarXiv 2018 · DOI · arXiv

Abstract

A $d$-dimensional closed convex set $K$ in $\mathbb{R}^d$ is lattice-free if its interior is disjoint from the integer lattice $\mathbb{Z}^d$. This paper investigates two families of lattice-free polytopes: $\mathcal{L}^d$, the family of integral lattice-free polytopes not properly contained in any other integral lattice-free polytope (weakly maximal), and $\mathcal{M}^d$, the subfamily of integral lattice-free polytopes not properly contained in any lattice-free set (strongly maximal). While these families are identical for $d \le 3$, they diverge for $d \ge 4$. We establish a super-exponential lower bound on the number of polytopes in the set difference $\mathcal{L}^d \setminus \mathcal{M}^d$, identifying them up to affine unimodular transformations.

Introduction

In discrete geometry and mixed-integer linear programming, lattice-free sets play a pivotal role. Specifically, maximal lattice-free sets are used to derive valid inequalities, or "cutting planes," which are essential for solving optimization problems. An integral polytope—a polytope whose vertices lie in $\mathbb{Z}^d$—is a natural candidate for such studies.

However, "maximality" can be defined in two distinct ways for an integral polytope $P$:

  1. Weak Maximality ($\mathcal{L}^d$): $P$ is maximal within the collection of all integral lattice-free polytopes.
  2. Strong Maximality ($\mathcal{M}^d$): $P$ is maximal within the collection of all lattice-free sets (including those with non-integral vertices).

It has been established that for dimensions $d=2$ and $d=3$, every weakly maximal integral lattice-free polytope is also strongly maximal. However, for $d \ge 4$, there exist polytopes that are weakly maximal but fail to be strongly maximal. This research quantifies this discrepancy, proving that the number of such "weakly-but-not-strongly" maximal polytopes grows at a super-exponential rate as the dimension increases.

Methodology: From Number Theory to Geometry

The proof relies on a sophisticated construction that links combinatorial number theory to the geometry of simplices.

Egyptian Fractions

The foundation of the construction is the Diophantine equation: $$\sum_{i=1}^d \frac{1}{a_i} = 1$$ where $a_i$ are positive integers. Solutions to this equation are known as Egyptian fractions. The number of such solutions grows extremely rapidly with $d$.

Axis-Aligned Simplices and Integer Hulls

The author utilizes these solutions to define axis-aligned simplices in $\mathbb{R}^d$. A key geometric property is that an axis-aligned simplex is lattice-free if and only if the sum of the reciprocals of its vertex coordinates is at least 1. By carefully selecting these coordinates based on Egyptian fraction solutions, the author constructs non-integral maximal lattice-free polytopes.

The next step involves the integer hull—the smallest integral polytope containing all integer points of a given set. By taking the integer hull of these specifically constructed non-integral sets, the author generates integral polytopes.

Ensuring Weak Maximality

To prove these hulls are in $\mathcal{L}^d \setminus \mathcal{M}^d$, the author introduces the concept of "strongly blocked" facets. A facet is blocked if it contains enough lattice points to prevent the polytope from being expanded in that direction without capturing an interior lattice point. If the facets of the integer hull are "clogged" in a specific manner, the resulting polytope is guaranteed to be weakly maximal.

Key Results

The primary contribution of the paper is the establishment of a lower bound on the size of the gap between $\mathcal{L}^d$ and $\mathcal{M}^d$.

Theorem: The number of equivalence classes (under affine unimodular transformations) of polytopes in $\mathcal{L}^{d+5} \setminus \mathcal{M}^{d+5}$ is at least the number of distinct solutions to the $d$-dimensional Egyptian fraction equation.

By applying known bounds on the number of Egyptian fraction representations (Konyagin, 2014), the author derives a super-exponential asymptotic bound: $$\ln \ln | \mathcal{L}^d \setminus \mathcal{M}^d | = \Omega\left(\frac{d}{\ln d}\right)$$

This result demonstrates that the divergence between weak and strong maximality is not a marginal phenomenon but a fundamental characteristic of high-dimensional lattice geometry.

Discussion and Open Questions

The findings suggest that the landscape of weakly maximal polytopes is far more complex than previously thought. The author highlights several avenues for future research:

  1. Tightness of the Bound: While the lower bound is super-exponential, the exact growth rate remains unknown. Existing literature suggests this bound might be optimal up to a logarithmic factor.
  2. Characterization: Can every weakly maximal polytope be viewed as the integer hull of a strongly blocked lattice-free set?
  3. Facet Irregularity: Do there exist weakly maximal polytopes where none of the facets are "blocked" by integer points? Such cases would represent a highly irregular class of lattice-free sets.

By bridging the gap between Egyptian fractions and lattice-free geometry, this work provides a quantitative foundation for understanding the limits of maximality in discrete optimization.

Summary updated

Abstract

A $d$-dimensional closed convex set $K$ in $\mathbb{R}^d$ is said to be lattice-free if the interior of $K$ is disjoint with $\mathbb{Z}^d$. We consider the following two families of lattice-free polytopes: the family $\mathcal{L}^d$ of integral lattice-free polytopes in $\mathbb{R}^d$ that are not properly contained in another integral lattice-free polytope and its subfamily $\mathcal{M}^d$ consisting of integral lattice-free polytopes in $\mathbb{R}^d$ which are not properly contained in another lattice-free set. It is known that $\mathcal{M}^d = \mathcal{L}^d$ holds for $d \le 3$ and, for each $d \ge 4$, $\mathcal{M}^d$ is a proper subfamily of $\mathcal{L}^d$. We derive a super-exponential lower bound on the number of polytopes in $\mathcal{L}^d \setminus \mathcal{M}^d$ (with standard identification of integral polytopes up to affine unimodular transformations).
BibTeX
@misc{averkov2018difference,
  author = {Gennadiy Averkov},
  title = {{Difference between families of weakly and strongly maximal integral lattice-free polytopes}},
  year = {2018},
  eprint = {1807.06327},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.06327},
}
Figure