🔢 mathematics

On the discrete Heine-Shephard problem for four lattice polygons

This paper demonstrates that the Plücker-type inequalities, which characterize volume polynomials for arbitrary convex bodies, fail to fully describe the set of realizable square-free polynomials for four lattice polygons due to additional arithmetic constraints on their mixed areas.

Original authors: Darren Gerrity, Ivan Soprunov

Published 2026-02-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Darren Gerrity, Ivan Soprunov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an architect designing a city, but instead of buildings, you are building shapes out of grid points (like dots on a piece of graph paper). In the world of mathematics, these are called lattice polygons.

This paper is about a specific puzzle: How do these shapes interact when they overlap or combine?

The Big Picture: The "Intersection" Game

Imagine you have four different shapes drawn on a grid: a triangle, a square, a weird star, and a rectangle.

If you take two of these shapes and "mix" them together (mathematically, this is called a Minkowski sum), they create a new, larger shape.
The size of this new shape depends on how much the original two shapes "overlap" in a specific mathematical sense. This overlap size is called the Mixed Area.

The authors are asking a simple question: If you have four shapes, what are the possible "overlap scores" you can get between every pair of them?

There are six pairs of shapes (1-2, 1-3, 1-4, 2-3, 2-4, 3-4). So, you get six numbers. The paper investigates the rules that govern these six numbers.

The "Smooth" World vs. The "Grid" World

To understand the discovery, we need to look at two different worlds:

The Smooth World (Continuous): Imagine shapes made of smooth clay. You can stretch them by any amount (1.5 times, $\pi$ times, etc.). In this world, mathematicians already knew the rules. The six overlap numbers must satisfy a specific set of inequalities (called Plücker-type inequalities). Think of these as the "laws of physics" for smooth shapes. If you have six numbers that follow these laws, you can almost certainly build shapes to match them.
The Grid World (Discrete): Now, imagine your shapes are made of LEGO bricks or pixels. You can only move them or resize them by whole numbers. You can't have a "half-brick." This is the world of lattice polygons.

The Surprise Discovery

The authors asked: "Do the same 'laws of physics' (the Plücker inequalities) work for our LEGO shapes?"

The answer is: Mostly yes, but with a nasty surprise.

In the smooth world, if you have six numbers that pass the inequality test, you can build the shapes.
In the LEGO world, you can have six numbers that pass the inequality test, but it is still IMPOSSIBLE to build the shapes.

The Analogy: The "Gap" in the Elevator

Imagine an elevator that only stops on whole-number floors (1, 2, 3...).

The Smooth World: The elevator can stop at 1.5, 1.7, or 1.99.
The Grid World: The elevator skips the decimals.

The paper shows that in the Grid World, there are "invisible gaps" between the numbers. Even if your six overlap numbers look perfect on paper (they satisfy the big inequalities), the arithmetic of the grid might say, "Nope, you can't build this."

The "Discrete Diagram": The Secret Code

To find these gaps, the authors invented a tool they call a "Discrete Diagram."

Think of this as a security scanner for pairs of shapes. When you put two shapes through the scanner, it spits out three numbers:

The width of Shape A.
The width of Shape B.
The "overlap score" (Mixed Area) between them.

In the smooth world, if you know the widths, the overlap score can be anything in between.
In the grid world, the scanner reveals a gap. If the widths are, say, 30 and 50, the overlap score cannot be just any number. It has to be a specific type of number. If you try to force an overlap score of "7" with those specific widths, the grid says, "Impossible."

The Four-Shape Puzzle

The paper focuses on the case of four shapes.

The Boundary: If the shapes are "barely" touching the edge of the rules (the boundary of the inequality zone), the authors prove you can always build them with grid shapes.
The Interior: This is where the magic happens. Deep inside the zone of "allowed" numbers, there are specific combinations that look valid but are actually impossible to build with grid shapes.

They found an infinite family of these "fake" solutions. It's like having a recipe that lists ingredients in perfect proportions, but when you try to bake the cake, the oven (the grid) refuses to work because the temperature (the arithmetic) doesn't align with the grid's rules.

Why Does This Matter?

This isn't just about drawing shapes. These "overlap scores" correspond to the number of times curves intersect in a complex mathematical space (related to algebraic geometry and physics).

The Lesson: When you move from a smooth, continuous world to a discrete, pixelated world (like computer graphics, cryptography, or quantum physics), new rules appear. You can't just assume the smooth rules apply. There are hidden "arithmetic constraints" that act like invisible walls, preventing certain configurations from existing, even if they look mathematically possible.

Summary in One Sentence

The paper proves that when building shapes out of grid points, there are hidden arithmetic "gaps" that prevent certain combinations of overlaps from existing, even when those combinations look perfectly valid according to the standard rules for smooth shapes.

1. Problem Statement and Motivation

The paper addresses a discrete variation of the Heine-Shephard problem, which seeks to characterize the space of volume polynomials associated with collections of convex bodies.

Context: In algebraic geometry, the intersection numbers of curves in $(\mathbb{C}^*)^2$ defined by generic Laurent polynomials are determined by the mixed volumes of their Newton polytopes (via the Bernstein-Kushnirenko-Khovanskii theorem).
The Continuous Case: For arbitrary convex bodies $K_1, \dots, K_n$ in $\mathbb{R}^2$ , the set of possible mixed areas (pairwise intersection numbers) is fully characterized by non-negativity and Plücker-type inequalities. For $n=4$ , the six mixed areas $v_{ij}$ satisfy:
$v_{12}v_{34} + v_{13}v_{24} \geq v_{14}v_{23}$
(and its permutations). These inequalities define a convex cone known as the Plücker space.
The Discrete Question: The authors investigate whether this characterization holds when the convex bodies are restricted to lattice polytopes (polytopes with integer vertices). Specifically, they ask: Do the six integers $2v(P_i, P_j)$ (where $P_i$ are lattice polygons) satisfy only the Plücker inequalities and non-negativity, or are there additional arithmetic constraints?

2. Methodology

The authors employ a combination of convex geometry, lattice theory, and number theory to analyze the space of mixed areas.

Normalization: They work with the normalized mixed volume $V(P, Q) = 2v(P, Q)$ , which is guaranteed to be an integer for lattice polygons.
The Discrete Diagram: A central tool is the study of a map $\phi: \mathcal{P}(\mathbb{Z}^2) \times \mathcal{P}(\mathbb{Z}^2) \to \mathbb{Z}^3$ defined by:
$\phi(P, Q) = (w_u(P), V(P, Q), w_u(Q))$
where $w_u(P)$ is the lattice width of $P$ in a primitive direction $u$ . The image of this map, called the "discrete diagram," reveals gaps and saturation properties in the possible values of mixed areas given fixed widths.
Graph-Theoretic Representation: The coefficients of the square-free part of the volume polynomial are represented as edge weights on a complete graph $K_4$ . This allows the authors to use symmetry arguments (actions of $S_4$ ) and define $K_4$ -primitive vectors to reduce the problem to specific cases.
Constructive Proofs: The paper uses explicit constructions of lattice polygons (segments, triangles, parallelograms) to demonstrate realizability or non-realizability of specific integer tuples.

3. Key Contributions and Results

The paper establishes that the continuous characterization fails in the lattice setting due to arithmetic constraints.

A. The Case of Three Polygons ( $n=3$ )

Result: There are no additional relations for three lattice polygons.
Finding: The set of possible mixed areas $(V(P_1, P_2), V(P_1, P_3), V(P_2, P_3))$ is exactly the set of all non-negative integer triples. The Plücker inequalities are vacuous for $n=3$ .

B. The Case of Four Polygons ( $n=4$ )

The authors define:

$\text{Pl}_{4,2}(\mathbb{Z})$ : The set of integer vectors satisfying the Plücker inequalities.
$V^{sf}_{4,2}(\mathbb{Z})$ : The subset of $\text{Pl}_{4,2}(\mathbb{Z})$ actually realizable by four lattice polygons.

Key Finding 1: Boundary Points are Realizable

Theorem 6.2: Every boundary point of the discrete Plücker set (where at least one Plücker inequality becomes an equality) is realizable by lattice polygons.
Method: These points can be realized using four lattice segments (possibly degenerate).

Key Finding 2: Interior Points are NOT Fully Realizable

Theorem 7.1: A large class of interior points is realizable. Specifically, if an interior point has two adjacent coordinates equal to 1, it belongs to $V^{sf}_{4,2}(\mathbb{Z})$ .
Theorem 8.1 (Main Negative Result): There exist interior points in $\text{Pl}_{4,2}(\mathbb{Z})$ $Pl_{4, 2} (Z)$ that are not realizable by any collection of four lattice polygons.
- The Constraint: If $v_{12}=1$ , $v_{13}=a$ , $v_{14}=b$ , and $d = \gcd(a,b) > 1$ , then the mixed area $v_{34}$ cannot be arbitrarily small. Specifically, if $0 < r < \min\{d, a/d, b/d\}$ , the tuple is not realizable.
- Mechanism: This arises from the "gap" phenomenon in the discrete diagram (Theorem 4.5). If two polygons have widths $a$ and $b$ in a direction orthogonal to a primitive segment, their mixed area must be at least $\min\{d, a/d, b/d\}$ (unless it is zero). The continuous Plücker inequalities allow $v_{34}$ to be arbitrarily small, but the lattice structure forbids it.

4. Significance and Implications

Failure of Continuous Analogy: The paper proves that the Plücker-type inequalities, which completely characterize mixed volumes for general convex bodies, are insufficient for lattice polytopes. The space of lattice mixed volumes is a proper subset of the integer points in the Plücker cone.
Arithmetic Obstructions: The non-realizability of certain interior points highlights that arithmetic constraints (specifically related to the greatest common divisors of lattice widths) impose stricter conditions than geometric inequalities.
Discrete Diagrams: The introduction and analysis of the "discrete diagram" $(w_u(P), V(P, Q), w_u(Q))$ provide a new framework for understanding the interplay between lattice geometry and mixed volumes. The discovery of "gaps" in the possible values of mixed areas for fixed widths is a novel contribution to lattice geometry.
Algebraic Geometry Connection: Since these mixed volumes correspond to intersection numbers of curves in $(\mathbb{C}^*)^2$ , the results imply that not all integer solutions to the Plücker inequalities correspond to actual intersection numbers of curves with lattice Newton polytopes. This refines the understanding of the "discrete" aspect of the BKK theorem.

Summary Conclusion

Gerrity and Soprunov demonstrate that while the Plücker inequalities describe the geometric limits of mixed volumes, the arithmetic nature of lattice polytopes introduces additional "holes" in the space of possible values. The discrete Heine-Shephard problem for $n=4$ is thus characterized by the Plücker inequalities plus specific arithmetic conditions derived from the lattice widths and GCDs of the coefficients, a phenomenon absent in the continuous case.