Kvant Math Problem 476

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m08s
Source on kvant.digital

Problem

Prove that if the vertices of a convex $n$-gon lie on the nodes of graph paper, and there are no other nodes inside it or on its sides, then $n\le4$.
Let space be divided by three families of parallel planes into identical cubes. Call the vertices of the cubes nodes. Prove that if all $n$ vertices of a convex polyhedron lie on nodes, and there are no other nodes on its edges, faces, or inside the polyhedron, then $n\le8$.

S. Mironov

Exploration

For the planar statement, the condition that no lattice points lie on the boundary except the vertices means that every side joins two lattice points with relatively prime coordinate differences. Hence each side contributes exactly one lattice segment. If the polygon has vertices $A_1,\dots,A_n$, the number of lattice points on its boundary is exactly $B=n$.

Pick's theorem gives

$$S=I+\frac B2-1.$$

Since there are no lattice points inside the polygon, $I=0$, so

$$S=\frac n2-1.$$

A convex lattice polygon has area at least that of any triangulation into $n-2$ triangles formed by drawing diagonals from one vertex. Every triangle in such a triangulation is a lattice triangle. The smallest possible area of a lattice triangle is $\frac12$, because the doubled area is an integer. Hence

$$S\ge \frac{n-2}{2}.$$

Combining this with $S=\frac n2-1$ gives equality. Thus every triangle in the triangulation must have area exactly $\frac12$.

The crucial point is to understand what this implies. If every triangle $A_1A_iA_{i+1}$ has area $\frac12$, then each contains no lattice points other than its three vertices. Consecutive triangles share an edge. Looking at two adjacent ones, the quadrilateral $A_1A_iA_{i+1}A_{i+2}$ has area $1$. Pick's theorem then forces its boundary to contain four lattice points only, which means the diagonal $A_1A_{i+1}$ contains no lattice point besides its endpoints. Applying Pick again to the quadrilateral gives $I=0$.

Trying $n=5$, the triangulation consists of three primitive triangles. The middle diagonal then belongs to two quadrilaterals of area $1$, and one quickly gets that all three diagonals from $A_1$ are primitive. The determinant relations between successive edge vectors force the vertices to alternate on the two sides of a primitive parallelogram, leading to a contradiction with convexity. There should be a cleaner route.

A better idea is to use a theorem of Minkowski in dimension $2$ in a very elementary form. Since $S=\frac n2-1$, if $n\ge5$ then $S\ge\frac32$. Any centrally symmetric convex body in the plane of area exceeding $4$ contains a nonzero lattice point. Taking the difference body $P-P$, whose area is at least $4S$ by the Rogers-Shephard inequality in dimension $2$, gives a contradiction. This is too heavy for a Kvant solution.

A more elementary route is available. Since equality holds in

$$S\ge \frac{n-2}{2},$$

every triangle of the fan triangulation has area $\frac12$. Let

$$u_i=A_i-A_1.$$

Then

$$|\det(u_i,u_{i+1})|=1.$$

For a convex polygon, all determinants have the same sign; take them equal to $1$. From

$$\det(u_i,u_{i+1})=\det(u_{i+1},u_{i+2})=1$$

it follows that

$$u_{i+2}+u_i=k_i u_{i+1}$$

for some integer $k_i$. Convexity implies $k_i>0$. If $n\ge5$, there are at least three vectors $u_i$. The recurrence forces all $u_i$ to lie in the cone generated by $u_2,u_3$, and a short induction shows the slopes are monotone. Testing small examples reveals that the only possibility is $k_i=1$, producing a chain of Fibonacci-type vectors, but then the area of some fan triangle exceeds $\frac12$. This needs refinement.

There is a much simpler observation. Since every fan triangle has area $\frac12$, the union of any two adjacent fan triangles is a convex quadrilateral of area $1$. Pick's theorem yields $B=4$, hence the shared diagonal contains no lattice points. Thus every diagonal from $A_1$ is primitive. For $n\ge5$, consider the quadrilateral $A_1A_iA_{i+1}A_{i+2}$. Its area is $1$, so it is a primitive parallelogram. Then $A_{i+2}-A_{i+1}=A_i-A_1$. Repeating gives alternating equal edge vectors, forcing the polygon to be a parallelogram. Hence $n\le4$.

The spatial part suggests projecting. Let the polyhedron be $P$. Choose a vertex $V$. The edges from $V$ generate a convex cone. Project the boundary of $P$ from $V$ onto a plane not through $V$. The vertices adjacent to $V$ project to a convex lattice polygon with no extra lattice points on edges. Part (1) shows that at most four edges can emanate from $V$.

Now use Euler's formula. Every face is a lattice polygon satisfying part (1), so each face has at most four vertices. Let $V,E,F$ denote the numbers of vertices, edges, faces. Since every face has at most four edges,

$$2E=\sum \deg(\text{faces})\le4F,$$

hence $E\le2F$. Euler gives

$$V-E+F=2,$$

$$V\le F+2.$$

This is not enough.

A sharper count comes from vertex degrees. The argument at a vertex shows every vertex degree is at most $4$. Therefore

$$2E=\sum \deg(\text{vertices})\le4V,$$

so $E\le2V$. Combining with Euler and $2E\le4F$ yields

$$E\le2(V-2+E-V)=2(F)$$

which is tautological.

For a convex polyhedron all vertex degrees are at least $3$. Hence

$$3V\le2E\le4V.$$

Need $V\le8$.

The key is stronger: the projection argument gives degree at most $4$. If every vertex degree is at most $4$ and every face degree is at most $4$, then

$$2E\le4V,\qquad 2E\le4F.$$

Hence

$$E\le2V,\qquad E\le2F.$$

Using Euler,

$$2=V-E+F\ge V-E+\frac E2=V-\frac E2.$$

Since $E\ge\frac32V$,

$$2\ge V-\frac34V=\frac V4.$$

Thus $V\le8$.

That closes the second part.

Problem Understanding

This is a Type B problem.

In the planar case we are given a convex lattice polygon whose vertices are lattice points and whose boundary and interior contain no lattice points other than the vertices themselves. We must prove that such a polygon has at most four vertices.

In the spatial case we are given a convex polyhedron whose vertices are lattice points of the cubic lattice and whose edges, faces, and interior contain no lattice points other than its vertices. We must prove that such a polyhedron has at most eight vertices.

The core difficulty is extracting strong combinatorial information from the absence of lattice points. In the plane, Pick's theorem converts the lattice condition into a sharp area statement. In space, the planar result must be applied to suitable sections around each vertex in order to bound vertex degrees, after which Euler's formula finishes the argument.

Proof Architecture

Lemma 1. For the planar polygon, the number of lattice points on the boundary equals the number of vertices, because every side is a primitive lattice segment.

Lemma 2. The area of the planar polygon equals $\frac n2-1$, by Pick's theorem with no interior lattice points.

Lemma 3. The area of a convex lattice $n$-gon is at least $\frac{n-2}{2}$, because a triangulation into $n-2$ lattice triangles has each triangle of area at least $\frac12$.

Lemma 4. Equality in Lemma 3 forces every triangle of a fan triangulation to have area exactly $\frac12$; then every union of two adjacent fan triangles is a lattice quadrilateral of area $1$, hence a primitive parallelogram.

Lemma 5. A convex lattice polygon satisfying the hypotheses is a triangle or a parallelogram; consequently $n\le4$.

Lemma 6. For every vertex of the spatial polyhedron, the degree is at most $4$, obtained by intersecting a small plane near the vertex with the polyhedron and applying the planar result.

Lemma 7. Every face of the polyhedron has at most $4$ edges, because each face satisfies the planar statement.

Lemma 8. The bounds on vertex degrees and face degrees imply $V\le8$ through Euler's formula.

The most delicate point is Lemma 5, where one must show that the equality case in the planar area estimate forces the polygon to be a parallelogram when it has more than three vertices.

Solution

Let $P=A_1A_2\dots A_n$ be the convex lattice polygon of part (1).

Since no lattice point lies on any side except its endpoints, each side is a primitive lattice segment. Therefore the number $B$ of lattice points on the boundary equals the number of vertices:

$$B=n.$$

There are no interior lattice points, so $I=0$. Pick's theorem gives

$$S=I+\frac B2-1=\frac n2-1,$$

where $S$ is the area of $P$.

Draw all diagonals from $A_1$. This triangulates $P$ into $n-2$ lattice triangles

$$A_1A_iA_{i+1}\qquad (i=2,\dots,n-1).$$

For every lattice triangle, twice the area is an integer, hence the area is at least $\frac12$. Consequently

$$S\ge\frac{n-2}{2}.$$

Since

$$S=\frac n2-1=\frac{n-2}{2},$$

equality holds. Hence every triangle $A_1A_iA_{i+1}$ has area exactly $\frac12$.

Fix $i$ with $2\le i\le n-2$. The quadrilateral

$$Q=A_1A_iA_{i+1}A_{i+2}$$

is the union of two adjacent triangles of area $\frac12$, so

$$\operatorname{area}(Q)=1.$$

Its boundary consists only of its four vertices. Indeed, each side of $Q$ is a side of $P$ or a diagonal joining two vertices of a primitive triangle of area $\frac12$; such a diagonal is primitive. Hence $B(Q)=4$.

Applying Pick's theorem to $Q$,

$$1=I(Q)+\frac42-1,$$

so $I(Q)=0$.

A convex lattice quadrilateral with area $1$, boundary lattice points $4$, and no interior lattice points is necessarily a primitive parallelogram. To see this, let its vertices be $X,Y,Z,T$. The triangles $XYZ$ and $XZT$ each have area $\frac12$. Hence

$$|\det(Y-X,Z-X)|=1, \qquad |\det(Z-X,T-X)|=1.$$

The vectors $Y-X$ and $T-X$ lie on opposite sides of $Z-X$ and have determinant $\pm1$ with $Z-X$. Therefore

$$T-X=Z-Y,$$

which is equivalent to

$$X+Z=Y+T.$$

Thus the diagonals bisect one another and $Q$ is a parallelogram.

Applying this to every quadrilateral $A_1A_iA_{i+1}A_{i+2}$ yields

$$A_{i+2}-A_{i+1}=A_i-A_1 \qquad (2\le i\le n-2).$$

For $i=2$,

$$A_4-A_3=A_2-A_1.$$

For $i=3$,

$$A_5-A_4=A_3-A_1.$$

Subtracting successive relations shows that the edge vectors repeat with period $2$. A convex polygon with this property has at most four distinct vertices. If $n\ge5$, the fifth vertex is forced onto the translate of a previous edge, contradicting strict convexity. Hence

$$n\le4.$$

This proves part (1).

Now consider part (2). Let the convex polyhedron have $V$ vertices, $E$ edges, and $F$ faces.

Take any vertex $O$. Intersect the polyhedron by a plane sufficiently close to $O$ and separating $O$ from all other vertices. The intersection is a convex polygon whose vertices correspond exactly to the edges emanating from $O$. Because the original edges contain no lattice points other than their endpoints, the sides of this section polygon contain no lattice points other than their vertices. The section polygon also has no lattice points in its interior, for otherwise the corresponding lattice point would lie on a face or inside the polyhedron.

Hence the section polygon satisfies the hypotheses of part (1). By part (1), it has at most four vertices. Therefore the degree of every vertex of the polyhedron is at most $4$.

Summing degrees over all vertices,

$$2E\le4V,$$

hence

$$E\le2V.$$

Every face is a convex lattice polygon satisfying the hypotheses of part (1). Thus every face has at most four edges. Summing face degrees,

$$2E\le4F,$$

hence

$$E\le2F.$$

Since every vertex degree is at least $3$ in a convex polyhedron,

$$2E\ge3V.$$

Euler's formula gives

$$V-E+F=2.$$

From $E\le2F$ we obtain $F\ge \frac E2$. Substituting into Euler's formula,

$$2 =V-E+F \ge V-E+\frac E2 =V-\frac E2.$$

Using $E\ge\frac32V$,

$$2 \ge V-\frac34V = \frac V4.$$

Therefore

$$V\le8.$$

Thus the number of vertices of the polyhedron does not exceed $8$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the deduction that every triangle in the fan triangulation has area $\frac12$. The polygon area is

$$S=\frac n2-1.$$

The triangulation contains $n-2$ lattice triangles, each of area at least $\frac12$. Their total area is therefore at least $\frac{n-2}{2}$. Since these two quantities are equal, every summand must attain the minimum value $\frac12$. Any triangle with larger area would make the total area strictly larger.

The second delicate step is the use of the local section at a vertex of the polyhedron. The section polygon has one vertex for each edge incident to the chosen vertex. A lattice point in the interior of that section would correspond, after moving along the rays from the vertex, to a lattice point lying on a face or in the interior of the polyhedron. The hypothesis excludes such points, so the planar theorem applies.

The third delicate step is the final counting argument. From vertex degrees at least $3$ one gets

$$E\ge\frac32V.$$

From face degrees at most $4$ one gets

$$F\ge\frac E2.$$

Substituting the latter into Euler's formula yields

$$2\ge V-\frac E2.$$

Replacing $E$ by its lower bound $\frac32V$ gives

$$2\ge \frac V4,$$

which is exactly the desired estimate $V\le8$. Reversing either inequality would invalidate the conclusion.

Alternative Approaches

For part (1), one may proceed directly from Pick's theorem. Equality in the estimate

$$S\ge\frac{n-2}{2}$$

implies that every triangle of a fan triangulation is primitive. Using determinants of consecutive edge vectors, one obtains a sequence of unimodular pairs. The resulting linear relations force the polygon to be either a triangle or a parallelogram. This approach is more algebraic.

For part (2), another route is to prove first that every face must be either a triangle or a parallelogram. One then studies the polyhedral graph. Since all vertex degrees and face degrees are at most $4$, Euler's formula immediately restricts the combinatorial type. The counting argument used in the main proof is preferable because it avoids a classification of possible faces and reduces the problem to two short inequalities together with Euler's formula.