betaFeedback

WorksMathematics

Wills' (1981) conjecture holds if and only if the dimension is at most 4

Abstract

Let PP be a lattice polytope in Rn\mathbb R^n that is symmetric about the origin and has the origin as its only interior lattice point. In 1981 Wills conjectured that each coefficient gi(P)g_i(P) of the Ehrhart polynomial of PP is at most the corresponding coefficient of the cube [−1,1]n[-1,1]^n, that is, gi(P)≤2i(ni)g_i(P)\le 2^i\binom ni. Wills proved this for n≤3n\le3, and Henze showed in 2014 that it fails for every n≥7n\ge7; the dimensions 44, 55 and 66 remained open. We settle them. In dimension 44 the conjecture holds; the new bounds are g1(P)≤8g_1(P)\le8 and g2(P)≤24g_2(P)\le24, and, up to unimodular equivalence, g1(P)=8g_1(P)=8 only for the cube, one explicit 2424-cell and one explicit cross-polytope. In dimension 55 we give a polytope with 5050 vertices in [−1,1]5[-1,1]^5 whose linear Ehrhart coefficient is 101/10>10101/10>10; products with segments then give counterexamples in every dimension n≥6n\ge6. Hence Wills' conjecture holds in Rn\mathbb R^n if and only if n≤4n\le4. The proof in dimension 44 combines Ehrhart reciprocity, the lower bound theorem for triangulated 33-spheres and an exhaustive computer enumeration of about three million sets of lattice points, listed up to symmetry.

Introduction

A lattice polytope in Rn\mathbb{R}^n is the convex hull of finitely many points of Zn\mathbb{Z}^n. Ehrhart [6] proved that for a lattice polytope PP of dimension nn the number of lattice points in the dilate kPkP is a polynomial in the integer k≥0k \ge0,

LP(k)=#(kP∩Zn)=g0(P)+g1(P)k+⋯+gn(P)kn,L_P(k) = \#(kP \cap\mathbb{Z}^n) = g_0(P) + g_1(P) k + \cdots+ g_n(P) k^n,

the Ehrhart polynomial of PP. Here g0(P)=1g_0(P) = 1, the leading coefficient gn(P)g_n(P) is the volume of PP, and gn−1(P)g_{n-1}(P) is half the lattice surface area of PP (§ 2); the remaining coefficients have no such simple description and may be negative [3].

Minkowski’s first theorem [14] states that a convex body K⊂RnK \subset\mathbb{R}^n that is symmetric about the origin and has no lattice point other than 0 in its interior has volume at most 2n2^n, the volume of the cube Cn=[−1,1]nC_n = [-1,1]^n. Wills [20] looked for a discrete analog of this theorem, one that bounds every Ehrhart coefficient of a lattice polytope. Let On\mathcal{O}^n be the set

An expanded version of this paper, with further results, is [7], at https://doi.org/10.5281/zenodo.239555454 of lattice polytopes P⊂RnP \subset\mathbb{R}^{n} with P=−PP=-P whose only interior lattice point is the origin. The cube CnC_{n} belongs to On\mathcal{O}^{n}, and LCn(k)=(2k+1)nL_{C_{n}}(k)=(2k+1)^{n}, so gi(Cn)=2i(ni)g_{i}(C_{n})=2^{i}\binom{n}{i}. Wills called these numbers the expected values of the coefficients [20 Remark (b)], and the following statement is known as Wills’ conjecture. We state it as in [11 Conjecture 1.1]; see also [8].

Conjecture 1.1 (Wills’ conjecture). For every n≥1n \ge1, every P∈OnP \in\mathcal{O}^{n} and every i∈{0,1,…,n}i \in\{0,1,\ldots,n\},

gi(P)≤gi(Cn)=2i(ni).g_{i}(P) \le g_{i}(C_{n})=2^{i}\binom{n}{i}.

For i=0i=0 there is equality, and for i=ni=n the inequality is Minkowski’s theorem. Wills proved the case i=n−1i=n-1 in every dimension [20 Theorem (i)]; hence the conjecture holds for n≤2n \le2. Wills also proved it for n=3n=3 [20 Theorem (i), (ii)], and, in dimension 4, the bounds g1(P)<21g_{1}(P)<21, g2(P)<31g_{2}(P)<31 and g2(P)≤g1(P)+16g_{2}(P)\le g_{1}(P)+16 [20 Theorem (iii)]. A discrete version of Minkowski’s first theorem by Betke, Henk and Wills [4 Theorem 2.1] implies that LP(k)≤LCn(k)L_{P}(k)\le L_{C_{n}}(k) for every P∈OnP \in\mathcal{O}^{n} and every integer k≥0k \ge0, which is the inequality of the conjecture for the values of the two polynomials instead of their coefficients. For i=n−1i=n-1, a bound in terms of the successive minima that implies Wills’ bound is due to Henk, Schürmann and Wills [10]. Henze [11] constructed a family of polytopes PnP_{n} and showed that P7∈O7P_{7}\in\mathcal{O}^{7} has g1(P7)=1534/105>14g_{1}(P_{7})=1534/105>14; taking products with segments, he obtained counterexamples in every dimension n≥7n \ge7. On the positive side, Henze proved the conjecture for every P∈OnP \in\mathcal{O}^{n} whose Ehrhart roots all have real part −1/2-1/2 [11 Corollary 3.3]; by a theorem of Bey, Henk and Wills [5], every such polytope is reflexive. About the remaining dimensions, Henze wrote [11 Remark 2.2]: “In dimensions 4, 5 and 6 we tested Wills’ conjecture on lattice polytopes that have a similar structure to PnP_{n}. [. . . ] None of these examples turned out to be a counterexample.” We settle these three dimensions.

Results. Our main results are Theorems 1.2 and 1.3 and Corollary 1.4 below, and Theorem 7.1 in § 7, which determines the polytopes P∈O4P \in\mathcal{O}^{4} with g1(P)=8g_{1}(P)=8. Table 1 compares them with the best earlier results, and Figure 1 shows the status of the conjecture in each dimension. Two of the three polytopes with g1(P)=8g_{1}(P)=8 have Ehrhart roots off the line Re⁡z=−12\operatorname{Re} z=-\frac{1}{2}, so Henze’s theorem does not cover them (Remark 7.3).

Best result before this paperNew result
g1(P)<21g_{1}(P)<21 [20 Theorem (iii)]g1(P)≤8g_{1}(P)\le8 for every P∈O4P\in\mathcal{O}^{4}, with equality exactly for C4C_{4}, a 24-cell TT and a cross-polytope XX, up to unimodular equivalence (Theorems 1.2 and 7.1)
g2(P)<31g_{2}(P)<31 and g2(P)≤g1(P)+16g_{2}(P)\le g_{1}(P)+16 [20 Theorem (iii)]g2(P)≤24g_{2}(P)\le24 for every P∈O4P\in\mathcal{O}^{4}, with equality exactly for C4C_{4}, up to unimodular equivalence (Theorem 1.2 and Corollary 7.2)
no counterexample known for n≤6n\le6; the tested families in dimensions 4, 5, 6 contain none [11 Remark 2.2]the polytope WW of Table 2 is in O5\mathcal{O}^{5} and has g1(W)=101/10>10g_{1}(W)=101/10>10; counterexamples in every dimension n≥5n\ge5 (Theorem 1.3)
true for n≤3n\le3 [20]; false for n≥7n\ge7 [11]Conjecture 1.1 holds in Rn\mathbb{R}^{n} if and only if n≤4n\le4 (Corollary 1.4)

Table 1. The best results before this paper and the results of this paper.

Status of Wills’ conjecture in each dimension

Figure 1. The status of Wills’ conjecture in each dimension nn. Before this paper the conjecture was known to hold for n≤3n\leq3 (Wills [20]) and to fail for n≥7n\geq7 (Henze [11]); the dimensions 4, 5 and 6 (hatched) were open. This paper proves it for n=4n=4 (Theorem 1.2 and Corollary 1.4) and disproves it for every n≥5n\geq5 (Theorem 1.3); the dimensions settled here are drawn in full colour, inside the thick frame.

Theorem 1.2. Every P∈O4P \in\mathcal{O}^{4} satisfies g1(P)≤8g_{1}(P)\leq8 and g2(P)≤24g_{2}(P)\leq24.

Theorem 1.3. The polytope W⊂R5W \subset\mathbb{R}^{5} of Table 2 belongs to O5\mathcal{O}^{5}, and

LW(k)=1+10110k+12712k2+1396k3+55712k4+38615k5.L_{W}(k)=1+\frac{101}{10}k+\frac{127}{12}k^{2}+\frac{139}{6}k^{3}+\frac{557}{12}k^{4}+\frac{386}{15}k^{5}.

In particular g1(W)=101/10>10=g1(C5)g_{1}(W)=101/10>10=g_{1}(C_{5}). For every n≥6n\geq6 the polytope W×Cn−5W\times C_{n-5} belongs to On\mathcal{O}^{n} and has g1=2n+1/10>2n=g1(Cn)g_{1}=2n+1/10>2n=g_{1}(C_{n}).

(0,0,1,1ˉ,1ˉ)(0,0,1,\bar{1},\bar{1})(0,0,1,1,1ˉ)(0,0,1,1,\bar{1})(0,1,1ˉ,0,0)(0,1,\bar{1},0,0)(0,1,0,1,1ˉ)(0,1,0,1,\bar{1})(0,1,0,1,1)(0,1,0,1,1)
(0,1,1,1ˉ,1ˉ)(0,1,1,\bar{1},\bar{1})(0,1,1,1ˉ,0)(0,1,1,\bar{1},0)(1,1ˉ,1ˉ,1ˉ,0)(1,\bar{1},\bar{1},\bar{1},0)(1,1ˉ,0,1,0)(1,\bar{1},0,1,0)(1,1ˉ,0,1,1)(1,\bar{1},0,1,1)
(1,1ˉ,1,0,1ˉ)(1,\bar{1},1,0,\bar{1})(1,0,1ˉ,0,1ˉ)(1,0,\bar{1},0,\bar{1})(1,0,1ˉ,1,1ˉ)(1,0,\bar{1},1,\bar{1})(1,0,1ˉ,1,1)(1,0,\bar{1},1,1)(1,0,0,1ˉ,1)(1,0,0,\bar{1},1)
(1,0,0,1,1)(1,0,0,1,1)(1,0,1,1ˉ,0)(1,0,1,\bar{1},0)(1,0,1,1ˉ,1)(1,0,1,\bar{1},1)(1,0,1,0,1ˉ)(1,0,1,0,\bar{1})(1,1,1ˉ,1ˉ,1ˉ)(1,1,\bar{1},\bar{1},\bar{1})
(1,1,1ˉ,1ˉ,0)(1,1,\bar{1},\bar{1},0)(1,1,1ˉ,1,0)(1,1,\bar{1},1,0)(1,1,1,1ˉ,0)(1,1,1,\bar{1},0)(1,1,1,1ˉ,1)(1,1,1,\bar{1},1)(1,1,1,1,0)(1,1,1,1,0)

Table 2. The polytope W⊂R5W \subset\mathbb{R}^{5} is the convex hull of the 50 points ±p\pm p, where pp runs over the 25 points below (1ˉ\bar{1} stands for −1-1). All 50 points are vertices of WW, and WW has 92 facets.

Corollary 1.4. Wills’ conjecture holds in Rn\mathbb{R}^{n} if and only if n≤4n\leq4.

Proof. For n≤3n\leq3 this is Wills’ theorem [20]. For n=4n=4, g0=1g_{0}=1 by (E1) of § 2, g3≤32g_{3}\leq32 by [20 Theorem (i)], g4≤16g_{4}\leq16 by Minkowski’s theorem, and g1g_{1}, g2g_{2} are bounded by Theorem 1.2. For n≥5n\geq5, Theorem 1.3 gives a counterexample. □

Idea of the proofs. Theorem 1.3 is a computation. The polytope WW is given by its 50 vertices, and since WW has only one interior lattice point, its linear coefficient is determined by four numbers: the numbers of lattice points in WW, in 2W2W and in the interior of 2W2W, and the volume of W(Proposition3.1)W (Proposition 3.1). Products with segments carry the example to every higher dimension.

For Theorem 1.2 we use Ehrhart reciprocity. Since P∈O4P\in\mathcal{O}^{4} has exactly one interior lattice point, LP(−1)=1L_{P}(-1)=1; comparing this with LP(1)=#(P∩Z4)L_{P}(1)=\#(P\cap\mathbb{Z}^{4}) shows that g1(P)≤8g_{1}(P)\leq8 is equivalent to the inequality

#(P∩Z4)≤σ(P)+17\#(P\cap\mathbb{Z}^{4})\leq\sigma(P)+17

between the number of lattice points of PP and its lattice surface area σ(P)=2g3(P)\sigma(P)=2g_{3}(P), and that this inequality also gives g2(P)≤24g_{2}(P)\leq24 (Proposition 4.2). A triangulation of the boundary of PP that uses every boundary lattice point, together with Walkup’s lower bound theorem for triangulated 3-spheres [19], proves the inequality when PP has at most 29 lattice points (Lemma 4.3).

For PP with at least 31 lattice points (their number is odd, since they come in pairs ±x\pm x together with 0) we look at the integer linear functionals that take values in [−1,1][-1,1] on PP. Either they contain a basis of Z4\mathbb{Z}^{4}, and then PP is unimodularly equivalent to a polytope in the cube C4C_{4}; or they span R4\mathbb{R}^{4} without containing a basis, and then a linear map carries PP, together with its lattice, onto a polytope in C4C_{4} with vertices in a sublattice of index 2; or they span a proper subspace. In the last case we fix four lattice points of PP whose determinant is as large as possible; in their coordinates the lattice points of PP lie in [−1,1]4[-1,1]^{4}, in one of 39 lattices, up to signed permutations of the coordinates (§ 5). This reduction, by four lattice points of largest determinant, follows Averkov and Schymura [2], who used it to compute the largest number of columns of a Δ\Delta-modular integer matrix for small parameters; their enumeration builds on that of Averkov, Borger and Soprunov [1]. In each case only finitely many sets of lattice points remain, and they are enumerated by computer (§ 6).

Section 2 collects the facts we use from Ehrhart theory. Section 3 proves Theorem 1.3. Sections 4–6 prove Theorem 1.2, and Section 7 identifies the equality cases. The expanded version [7] of this paper also gives a second proof of Case III of Section 5, determines the second largest value of g2g_{2} in dimension 4, and describes the computations in more detail.

Preliminaries

Ehrhart polynomials

Let n≥1n \ge1, let Λ⊂Rn\Lambda\subset\mathbb{R}^{n} be a lattice (a discrete subgroup of rank nn), and let PP be a polytope of dimension nn whose vertices lie in Λ\Lambda. Then LP,Λ(k)=#(kP∩Λ)=∑igi(P)kiL_{P,\Lambda}(k)=\#(kP\cap\Lambda)=\sum_i g_i(P)k^i is a polynomial in kk of degree nn [6]; its coefficients gi(P)g_i(P) depend on Λ\Lambda, which will be clear from the context, and we write LPL_P when Λ=Zn\Lambda=\mathbb{Z}^{n}. We call two pairs (P,Λ)(P,\Lambda) and (P′,Λ′)(P',\Lambda') isomorphic if a linear isomorphism ϕ\phi of Rn\mathbb{R}^{n} satisfies ϕ(P)=P′\phi(P)=P' and ϕ(Λ)=Λ′\phi(\Lambda)=\Lambda'; then ϕ(kP)∩Λ′=ϕ(kP∩Λ)\phi(kP)\cap\Lambda'=\phi(kP\cap\Lambda) for every kk, so LP′,Λ′=LP,ΛL_{P',\Lambda'}=L_{P,\Lambda}. When Λ=Λ′=Zn\Lambda=\Lambda'=\mathbb{Z}^{n}, the map ϕ\phi lies in GL⁡n(Z)\operatorname{GL}_{n}(\mathbb{Z}), and the two lattice polytopes are called unimodularly equivalent. We use four standard facts [3 Chapters 3–5].

(E1) g0(P)=1g_0(P)=1 and gn(P)=vol⁡(P)/det⁡Λg_n(P)=\operatorname{vol}(P)/\det\Lambda.

(E2) Reciprocity (Ehrhart, Macdonald): LP,Λ(−k)=(−1)n#(int⁡(kP)∩Λ)L_{P,\Lambda}(-k)=(-1)^n\#(\operatorname{int}(kP)\cap\Lambda) for every integer k≥1k\ge1.

(E3) For a facet FF of PP let uFu_F be the primitive vector of the dual lattice Λ∗\Lambda^* that is an outer normal of FF, and let bFb_F be the integer with F⊂{x:⟨uF,x⟩=bF}F\subset\{x:\langle u_F,x\rangle=b_F\}. Let relvol⁡(F)\operatorname{relvol}(F) be the (n−1)(n-1)-dimensional volume of FF, measured so that a fundamental domain of the lattice Λ∩aff⁡(F−F)\Lambda\cap\operatorname{aff}(F-F) has volume 1. Then gn−1(P)=12σ(P)g_{n-1}(P)=\frac{1}{2}\sigma(P), where σ(P)=∑Frelvol⁡(F)\sigma(P)=\sum_F\operatorname{relvol}(F) is the lattice surface area. If 0∈int⁡P0\in\operatorname{int}P, then vol⁡(P′)/det⁡Λ=1n∑FbFrelvol⁡(F)\operatorname{vol}(P')/\det\Lambda=\frac{1}{n}\sum_F b_F\operatorname{relvol}(F), by cutting PP into the pyramids with apex 0 over its facets.

(E4) LP×Q=LPLQL_{P\times Q}=L_PL_Q for lattice polytopes P⊂RpP\subset\mathbb{R}^{p} and Q⊂RqQ\subset\mathbb{R}^{q}, with the lattice Zp+q\mathbb{Z}^{p+q}, since k(P×Q)∩Zp+q=(kP∩Zp)×(kQ∩Zq)k(P\times Q)\cap\mathbb{Z}^{p+q}=(kP\cap\mathbb{Z}^{p})\times(kQ\cap\mathbb{Z}^{q}).

In (E3), bFb_F is an integer because FF contains points of Λ\Lambda; when 0∈int⁡P0\in\operatorname{int}P it is positive, and it is the lattice distance of FF from the origin.

The class Wn\mathcal{W}^{n}

Let OΛn\mathcal{O}_{\Lambda}^{n} be the set of polytopes PP with vertices in Λ\Lambda, P=−PP=-P and int⁡P∩Λ={0}\operatorname{int}P\cap\Lambda=\{0\}; so On=OZnn\mathcal{O}^{n}=\mathcal{O}_{\mathbb{Z}^{n}}^{n}. A polytope in OΛn\mathcal{O}_{\Lambda}^{n} has dimension nn, because 0 is an interior point. We write G(P)=#(P∩Λ)G(P)=\#(P\cap\Lambda). Since the lattice points of PP other than 0 come in pairs ±x\pm x, G(P)G(P) is odd.

Lemma 2.1. Let Y⊂{−1,0,1}nY \subset\{-1,0,1\}^{n} be a set with Y=−YY=-Y whose convex hull PP has dimension nn. Then P∈OnP \in\mathcal{O}^{n}.

Proof. The polytope PP is a lattice polytope with P=−PP=-P. It has an interior point xx, so −x-x is interior too, and so is 0=12x+12(−x)0=\frac{1}{2}x+\frac{1}{2}(-x). Finally int⁡P⊂int⁡Cn=(−1,1)n\operatorname{int} P \subset\operatorname{int} C_n=(-1,1)^{n}, whose only lattice point is 00.

The same proof applies to a sublattice Γ⊆Zn\Gamma\subseteq\mathbb{Z}^{n} in place of Zn\mathbb{Z}^{n}: if S⊆Γ∩CnS \subseteq\Gamma\cap C_n is symmetric and spans Rn\mathbb{R}^{n}, then conv⁡S∈On\operatorname{conv} S \in\mathcal{O}^{n}. We use this in § 5 and § 6.

Lemma 2.2 (cf. [11 Proposition 2.3]). If P∈OpP \in\mathcal{O}^{p} and Q∈OqQ \in\mathcal{O}^{q}, then P×Q∈Op+qP \times Q \in\mathcal{O}^{p+q} and g1(P×Q)=g1(P)+g1(Q)g_1(P \times Q)=g_1(P)+g_1(Q).

Proof. The product P×QP \times Q is a symmetric lattice polytope, and int⁡(P×Q)=int⁡P×int⁡Q\operatorname{int}(P \times Q)=\operatorname{int} P \times\operatorname{int} Q contains only the lattice point 00. By (E4) and (E1), the coefficient of kk in LPLQL_P L_Q is g1(P)⋅1+1⋅g1(Q)g_1(P)\cdot1+1\cdot g_1(Q).

A counterexample in dimension five

We compute four numbers for the polytope WW of Table 2, three lattice-point counts and the volume; by Proposition 3.1 they determine g1(W)g_1(W).

Proposition 3.1. Let P∈O5P \in\mathcal{O}^{5}. Then

g1(P)=4(G(P)+1)+24vol⁡(P)−A(P)6,A(P)=12(#(2P∩Z5)+#(int⁡(2P)∩Z5)).g_1(P)=\frac{4(G(P)+1)+24\operatorname{vol}(P)-A(P)}{6},\qquad A(P)=\frac{1}{2}\left(\#(2P\cap\mathbb{Z}^{5})+\#(\operatorname{int}(2P)\cap\mathbb{Z}^{5})\right).

Proof. Write L=LPL=L_P and gi=gi(P)g_i=g_i(P). By (E2) with n=5n=5, L(−1)=−1L(-1)=-1 and L(−2)=−#(int⁡(2P)∩Z5)L(-2)=-\#(\operatorname{int}(2P)\cap\mathbb{Z}^{5}). Hence

L(1)−L(−1)=2(g1+g3+g5)=G(P)+1,L(2)−L(−2)=2(2g1+8g3+32g5)=2A(P).L(1)-L(-1)=2(g_1+g_3+g_5)=G(P)+1,\qquad L(2)-L(-2)=2(2g_1+8g_3+32g_5)=2A(P).

Eliminating g3g_3 and using g5=vol⁡(P)g_5=\operatorname{vol}(P) (E1) gives 6g1=4(G(P)+1)+24vol⁡(P)−A(P)6g_1=4(G(P)+1)+24\operatorname{vol}(P)-A(P).

Proof of Theorem 1.3. The 50 points of Table 2 lie in {−1,0,1}5\{-1,0,1\}^{5}, form a symmetric set and span R5\mathbb{R}^{5}; by Lemma 2.1, W∈O5W \in\mathcal{O}^{5}. Direct computation gives

G(W)=117,#(2W∩Z5)=1815,#(int⁡(2W)∩Z5)=243,vol⁡(W)=38615,G(W)=117,\qquad\#(2W\cap\mathbb{Z}^{5})=1815,\qquad\#(\operatorname{int}(2W)\cap\mathbb{Z}^{5})=243,\qquad\operatorname{vol}(W)=\frac{386}{15},

so A(W)=1029A(W)=1029 and, by Proposition 3.1, g1(W)=(4⋅118+24⋅38615−1029)/6=10110g_1(W)=(4\cdot118+24\cdot\frac{386}{15}-1029)/6=\frac{101}{10}. The whole polynomial is determined by LW(0)=1L_W(0)=1 and the values LW(k)L_W(k) for k=1,…,5k=1,\ldots,5, namely 117, 1815, 10765, 39927 and 112639. All numbers in this proof can be computed with Normaliz [16] or LattE [12]; the input files are in [17].

For n≥6n \ge6, Lemma 2.2 gives W×Cn−5∈OnW \times C_{n-5} \in\mathcal{O}^{n} and g1(W×Cn−5)=10110+2(n−5)=2n+110g_{1}(W \times C_{n-5}) = \frac{101}{10} + 2(n-5) = 2n + \frac{1}{10}, since g1(Cm)=2mg_{1}(C_{m}) = 2m. □

Dimension four: the key inequality and polytopes with few lattice points

From now on n=4n = 4. For P∈OΛ4P \in\mathcal{O}^{4}_{\Lambda} we write G=G(P)G = G(P), gi=gi(P)g_i = g_i(P) (with respect to Λ\Lambda) and σ=σ(P)\sigma= \sigma(P).

Lemma 4.1. For P∈OΛ4P \in\mathcal{O}^{4}_{\Lambda}, g1+g3=g2+g4=G−12g_1 + g_3 = g_2 + g_4 = \frac{G-1}{2}.

Proof. We have L(1)=G=1+g1+g2+g3+g4L(1) = G = 1 + g_1 + g_2 + g_3 + g_4, and by (E2) L(−1)=#(int⁡P∩Λ)=1=1−g1+g2−g3+g4L(-1) = \#(\operatorname{int} P \cap\Lambda) = 1 = 1 - g_1 + g_2 - g_3 + g_4. Subtracting the second equation from the first, and adding the two, gives the two identities. □

Proposition 4.2. Let P∈OΛ4P \in\mathcal{O}^{4}_{\Lambda}. Then g4≤16g_4 \le16 and g3≤2g4≤32g_3 \le2g_4 \le32. Moreover

g1≤8⟺G≤σ+17.g_1 \le8 \Longleftrightarrow G \le\sigma+ 17.

and if g1≤8g_1 \le8 then g2≤g4+8≤24g_2 \le g_4 + 8 \le24.

Proof. The bound g4=vol⁡(P)/det⁡Λ≤16g_4 = \operatorname{vol}(P) / \det\Lambda\le16 is Minkowski’s theorem, applied in the coordinates of a basis of Λ\Lambda. Since every bF≥1b_F \ge1, (E3) gives 2g3=σ≤∑FbFrelvol⁡(F)=4g42g_3 = \sigma\le\sum_F b_F \operatorname{relvol}(F) = 4g_4; this is Wills’ argument for gn−1g_{n-1} [20 Theorem (i)]. By Lemma 4.1, g1=G−12−g3g_1 = \frac{G-1}{2} - g_3, so g1≤8g_1 \le8 if and only if G≤2g3+17=σ+17G \le2g_3 + 17 = \sigma+ 17. If this holds, then G≤4g4+17G \le4g_4 + 17, and Lemma 4.1 gives g2=G−12−g4≤g4+8≤24g_2 = \frac{G-1}{2} - g_4 \le g_4 + 8 \le24. □

So Theorem 1.2 is equivalent to the key inequality G≤σ+17G \le\sigma+ 17 on O4\mathcal{O}^{4}. Let NVol⁡(F)=3!relvol⁡(F)\operatorname{NVol}(F) = 3! \operatorname{relvol}(F) be the normalized volume of a facet, so that a lattice tetrahedron in aff⁡F\operatorname{aff} F has normalized volume a positive integer. The inequality reads

∑FNVol⁡(F)≥6G−102.(1)\sum_F \operatorname{NVol}(F) \ge6G - 102. \tag*{(1)}

Lemma 4.3. If P∈OΛ4P \in\mathcal{O}^{4}_{\Lambda} and G≤29G \le29, then (1) holds with strict inequality; hence g1<8g_1 < 8.

Proof. Take a triangulation Δ\Delta of the boundary of PP whose vertex set is the set of all G−1G - 1 boundary lattice points and in which every tetrahedron lies in a facet. To construct one, take a triangulation of PP whose vertices are exactly the points of P∩ΛP \cap\Lambda; one exists, for example by strong pulling ([9 Lemma 2.1(2)], applied in the coordinates of a basis of Λ\Lambda). Its faces that lie in the boundary of PP form Δ\Delta. Then Δ\Delta is a triangulated 33-sphere with f0=G−1f_0 = G - 1 vertices. Each of its f3f_3 tetrahedra is a lattice tetrahedron in the affine hull of a facet, so it has normalized volume at least 11, and ∑FNVol⁡(F)≥f3\sum_F \operatorname{NVol}(F) \ge f_3. Walkup’s lower bound theorem [19 Theorem 1] gives f1≥4f0−10f_1 \ge4f_0 - 10 for every triangulated 33-sphere, and the Dehn–Sommerville relations f0−f1+f2−f3=0f_0 - f_1 + f_2 - f_3 = 0, 2f2=4f32f_2 = 4f_3 give f3=f1−f0f_3 = f_1 - f_0. Hence ∑FNVol⁡(F)≥3f0−10=3G−13\sum_F \operatorname{NVol}(F) \ge3f_0 - 10 = 3G - 13, and 3G−13>6G−1023G - 13 > 6G - 102 because G≤29G \le29. □

:::

The proof gives a bound on g1g_1 for every P∈OΛ4P \in\mathcal{O}^{4}_{\Lambda}: by Lemma 4.1 and (E3), g1=G−12−σ2g_1 = \frac{G-1}{2} - \frac{\sigma}{2}, and σ=16∑FNVol⁡(F)≥3G−136\sigma= \frac{1}{6}\sum_F \operatorname{NVol}(F) \ge\frac{3G-13}{6}, so g1≤3G+712g_1 \le\frac{3G+7}{12} (the solid line in Figure 3).

Figure 3. The largest values of g1g_1 in Case I, and the three equality cases of Theorem 7.1, against the number GG of lattice points. The small grey dots show, for each odd G≥31G\ge31, the largest value of g1g_1 in Case I (Computation 1). The three larger green dots mark the polytopes C4C_4, TT and XX of Theorem 7.1: C4C_4 belongs to Case I, and TT and XX belong to Case III. For Cases II and III only the largest value of g1g_1 over all GG is recorded: at most 6 in Case II (Computation 3), and at most 8 in Case III, attained only by TT and XX (Computation 5). The dashed line is g1=8g_1=8. In the shaded region G≤29G\le29, the solid line is the bound g1≤3G+712g_1\le\frac{3G+7}{12} stated after the proof of Lemma 4.3.

Remark 4.4. With Euler’s formula in place of Walkup’s theorem, a similar triangulation argument gives Wills’ theorem in dimension 3 (see [7]). In dimension 4 the lower bound theorem proves (1) only when G≤29G \le29; this is why the computations of § 6 are needed.

Dimension four: three cases

By Lemma 4.3 it remains to prove (1) for P∈O4P \in\mathcal{O}^{4} with G≥31G \ge31. For such PP let

M(P)={u∈Z4:∣⟨u,x⟩∣≤1 for all x∈P},r(P)=dim⁡span⁡M(P).M(P)=\{u\in\mathbb{Z}^{4}:|\langle u,x\rangle|\le1\text{ for all }x\in P\},\qquad r(P)=\dim\operatorname{span}M(P).

The set M(P)M(P) is finite (since PP contains a ball around 0) and symmetric, and ⟨u,x⟩∈{−1,0,1}\langle u,x\rangle\in\{-1,0,1\} for u∈M(P)u\in M(P) and x∈P∩Z4x\in P\cap\mathbb{Z}^{4}. We distinguish three cases: M(P)M(P) contains a basis of Z4\mathbb{Z}^{4} (Case I); r(P)=4r(P)=4 but M(P)M(P) contains no basis (Case II); r(P)≤3r(P)\le3 (Case III). Figure 2 shows how each case is settled.

Proof structure for Theorem 1.2

Figure 2. The proof of Theorem 1.2 splits O4\mathcal{O}^{4} into four parts. Polytopes with at most 29 lattice points are handled by Lemma 4.3 (the blue box, on the left); for the others (the three orange boxes), the integer functionals bounded by 1 in absolute value on PP decide which finite enumeration of Section 6 contains PP, up to isomorphism (Section 2). The frame lattices are defined after Lemma 5.1.

Case I

For a lattice Γ\Gamma, a set S⊆ΓS\subseteq\Gamma is called Γ\Gamma-saturated if conv⁡S∩Γ=S\operatorname{conv}S\cap\Gamma=S; when the lattice is clear, we say saturated. If M(P)M(P) contains a basis u1,…,u4u_{1},\ldots,u_{4} of Z4\mathbb{Z}^{4}, let U∈GL⁡4(Z)U\in\operatorname{GL}_{4}(\mathbb{Z}) have rows uiu_{i}. Then UP⊂C4UP\subset C_{4}, so UP=conv⁡SUP=\operatorname{conv}S for the set S=UP∩Z4⊂{−1,0,1}4S=UP\cap\mathbb{Z}^{4}\subset\{-1,0,1\}^{4}, which is symmetric and saturated.

Case II

Let r(P)=4r(P)=4, and let u1,…,u4∈M(P)u_{1},\ldots,u_{4}\in M(P) be linearly independent, with UU the matrix of rows uiu_{i} and d=∣det⁡U∣d=|\det U|. Then d≥2d\ge2, since otherwise M(P)M(P) would contain a basis. The map x↦Uxx\mapsto Ux carries Z4\mathbb{Z}^{4} onto the sublattice Γ=UZ4\Gamma=U\mathbb{Z}^{4} of index dd and carries PP into C4C_{4}; so (P,Z4)(P,\mathbb{Z}^{4}) is isomorphic to (UP,Γ)(UP,\Gamma), UP∈O4UP\in\mathcal{O}^{4}, LUP,Γ=LPL_{UP,\Gamma}=L_{P}, and UP=conv⁡SUP=\operatorname{conv}S for the Γ\Gamma-saturated symmetric set S=UP∩Γ⊂Γ∩{−1,0,1}4S=UP\cap\Gamma\subset\Gamma\cap\{-1,0,1\}^{4}. In particular

31≤G(P)≤#(Γ∩{−1,0,1}4).31\le G(P)\le\#(\Gamma\cap\{-1,0,1\}^{4}).

Moreover d≤16d\le16: the set SS spans R4\mathbb{R}^{4}, so it contains four linearly independent points of Γ∩{−1,0,1}4\Gamma\cap\{-1,0,1\}^{4}; their determinant is a nonzero multiple of dd, and it is at most 16 in absolute value by Hadamard’s inequality.

The sublattices of index 2 are ΓI={x:∑i∈Ixi even}\Gamma_{I}=\{x:\sum_{i\in I}x_{i}\text{ even}\} for nonempty I⊂{1,2,3,4}I\subset\{1,2,3,4\}. A point of {−1,0,1}4\{-1,0,1\}^{4} lies in ΓI\Gamma_{I} exactly when an even number of its coordinates in II are nonzero, so

#(ΓI∩{−1,0,1}4)=34−m⋅3m+(−1)m2=27, 45, 39, 41(m=∣I∣=1,2,3,4).\#(\Gamma_{I}\cap\{-1,0,1\}^{4})=3^{4-m}\cdot\frac{3^{m}+(-1)^{m}}{2}=27,\ 45,\ 39,\ 41\qquad(m=|I|=1,2,3,4).

Computation 2 shows that a sublattice of index 3≤d≤163\le d\le16 contains at most 27 points of {−1,0,1}4\{-1,0,1\}^{4} whenever these points span R4\mathbb{R}^{4}. Since 27<3127<31, in Case II we have d=2d=2 and Γ=ΓI\Gamma=\Gamma_{I} with ∣I∣∈{2,3,4}|I|\in\{2,3,4\}.

Case III: the frame

Now let r(P)≤3r(P) \le3. Choose lattice points v1,…,v4v_1,\ldots,v_4 of PP for which D=∣det⁡(v1,…,v4)∣D = \lvert\det(v_1,\ldots,v_4)\rvert is as large as possible, and let VV be the matrix with columns viv_i. We call (v1,…,v4)(v_1,\ldots,v_4) a frame of PP. Since PP spans R4\mathbb{R}^4, D≥1D \ge1. The map x↦V−1xx \mapsto V^{-1}x carries Z4\mathbb{Z}^4 onto the lattice Λ=V−1Z4⊇Z4\Lambda= V^{-1}\mathbb{Z}^4 \supseteq\mathbb{Z}^4, of index DD over Z4\mathbb{Z}^4, and carries P∩Z4P \cap\mathbb{Z}^4 onto a set SS.

Lemma 5.1. In this situation:

(i) S⊂Λ∩C4S \subset\Lambda\cap C_4, S=−SS = -S, and SS contains the unit vectors ±e1,…,±e4\pm e_1,\ldots,\pm e_4;

(ii) ∣det⁡(s1,…,s4)∣≤1\lvert\det(s_1,\ldots,s_4)\rvert\le1 for all s1,…,s4∈Ss_1,\ldots,s_4 \in S;

(iii) conv⁡S∩Λ=S\operatorname{conv} S \cap\Lambda= S and int⁡(conv⁡S)∩Λ={0}\operatorname{int}(\operatorname{conv} S) \cap\Lambda= \{0\};

(iv) Λ\Lambda contains no point c≠0c \ne0 with ∣c1∣+⋯+∣c4∣<1\lvert c_1\rvert+ \cdots+ \lvert c_4\rvert< 1;

(v) D≤23D \le23.

Proof. For x1,…,x4∈P∩Z4x_1,\ldots,x_4 \in P \cap\mathbb{Z}^4 we have ∣det⁡(V−1x1,…,V−1x4)∣=∣det⁡(x1,…,x4)∣/D≤1\lvert\det(V^{-1}x_1,\ldots,V^{-1}x_4)\rvert= \lvert\det(x_1,\ldots,x_4)\rvert/D \le1 by the choice of v1,…,v4v_1,\ldots,v_4, which gives (ii). For (i), write a lattice point xx of PP as x=∑civix = \sum c_i v_i; by Cramer’s rule ∣ci∣=∣det⁡(v1,…,x,…,v4)∣/D≤1\lvert c_i\rvert= \lvert\det(v_1,\ldots,x,\ldots,v_4)\rvert/D \le1. Property (iii) holds because x↦V−1xx \mapsto V^{-1}x carries conv⁡(P∩Z4)∩Z4=P∩Z4\operatorname{conv}(P \cap\mathbb{Z}^4) \cap\mathbb{Z}^4 = P \cap\mathbb{Z}^4 and int⁡P∩Z4={0}\operatorname{int} P \cap\mathbb{Z}^4 = \{0\} to the corresponding statements for SS and Λ\Lambda. For (iv), the open cross-polytope {c:∣c1∣+⋯+∣c4∣<1}\{c : \lvert c_1\rvert+ \cdots+ \lvert c_4\rvert< 1\} lies in the interior of conv⁡{±ei}⊆conv⁡S\operatorname{conv}\{\pm e_i\} \subseteq\operatorname{conv} S, so by (iii) its only point of Λ\Lambda is 00.

For (v), PP contains the cross-polytope conv⁡{±vi}\operatorname{conv}\{\pm v_i\} of volume 244!D=23D\frac{2^4}{4!}D = \frac{2}{3}D, and vol⁡(P)≤16\operatorname{vol}(P) \le16, so D≤24D \le24. If D=24D = 24, then P=conv⁡{±vi}P = \operatorname{conv}\{\pm v_i\} and vol⁡P=16\operatorname{vol} P = 16. The translates 12P+z\frac{1}{2}P + z, z∈Z4z \in\mathbb{Z}^4, have disjoint interiors (an overlap would put a nonzero lattice point in int⁡P\operatorname{int} P) and total density vol⁡(12P)=1\operatorname{vol}(\frac{1}{2}P) = 1, so they tile R4\mathbb{R}^4: the union of the translates is closed, and its complement is open, invariant under Z4\mathbb{Z}^4 and of density 00; a nonempty such set would contain a ball and all its Z4\mathbb{Z}^4-translates, hence have positive density. A convex polytope that tiles space by lattice translations has centrally symmetric facets (Minkowski [15]; see Venkov [18] and McMullen [13]), but the facets of a cross-polytope are tetrahedra. So D≤23D \le23. □

Let L\mathcal{L} be the set of lattices Λ⊇Z4\Lambda\supseteq\mathbb{Z}^4 of index at most 2323 over Z4\mathbb{Z}^4 that satisfy (iv); a lattice of index DD over Z4\mathbb{Z}^4 lies in 1DZ4\frac{1}{D}\mathbb{Z}^4, so L\mathcal{L} is finite. We call the lattices in L\mathcal{L} the frame lattices. For Λ∈L\Lambda\in\mathcal{L} let S(Λ)\mathcal{S}(\Lambda) be the family of sets SS satisfying (i)–(iii). The signed permutation matrices act on L\mathcal{L}, and Computation 4 shows that L\mathcal{L} consists of 39 orbits; we fix one representative in each. Integer functionals transfer as well. For a set S⊂ΛS \subset\Lambda let M(S)={w∈Λ∗:∣⟨w,s⟩∣≤1 for s∈S}M(S) = \{w \in\Lambda^* : \lvert\langle w,s\rangle\rvert\le1 \text{ for } s \in S\} and r(S)=dim⁡span⁡M(S)r(S) = \dim\operatorname{span} M(S). Since ⟨u,Vs⟩=⟨VTu,s⟩\langle u, Vs\rangle= \langle V^{T}u,s\rangle and VTZ4=Λ∗V^{T}\mathbb{Z}^4 = \Lambda^*, a vector u∈Z4u \in\mathbb{Z}^4 lies in M(P)M(P) if and only if VTuV^{T}u lies in M(S)M(S); so r(P)=r(S)r(P) = r(S). In Case III we therefore have a lattice Λ\Lambda among the 39 representatives and a set S∈S(Λ)S \in\mathcal{S}(\Lambda) with #S≥31\#S \ge31 and r(S)≤3r(S) \le3 such that (P,Z4)(P,\mathbb{Z}^4) is isomorphic to (conv⁡S,Λ)(\operatorname{conv} S,\Lambda) (by x↦V−1xx \mapsto V^{-1}x, followed by a signed permutation of the coordinates); in particular Lconv⁡S,Λ=LPL_{\operatorname{conv} S,\Lambda} = L_P. Lemma 5.1 does not use r(P)≤3r(P) \le3, so this reduction applies to every P∈C4P \in C^4. We use it only in Case III, where the condition r(S)≤3r(S) \le3 shortens the search of Computation 5; the polytopes with r(P)=4r(P) = 4 are listed directly, in Cases I and II.

The computations

All enumerations below are exhaustive and use exact integer and rational arithmetic; the repository [17] contains the programs and, for each computation, its output. Computations 1, 3 and 5 list sets of lattice points up to the symmetries named. For each set SS the Ehrhart polynomial of conv⁡S\operatorname{conv} S is computed exactly: in Computations 1 and 3 from $G = #S and the volume and the lattice surface area of conv⁡S\operatorname{conv} S (taken from a triangulation of its boundary), by Lemma 4.1, (E1) and (E3); in Computation 5 from the numbers of lattice points of kconv⁡Sk\operatorname{conv} S for k=1,2,3k=1,2,3 and of the interior of kconv⁡Sk\operatorname{conv} S for k=1,2k=1,2, which give its values at k=−2,…,3k=-2,\ldots,3 by (E1) and (E2) and so determine it. Figure 3 shows, for each G≥31G\ge31, the largest value of g1g_1 in Case I (Computation 1) and the three equality cases of Theorem 7.1, and, for G≤29G\le29, the bound on g1g_1 stated after the proof of Lemma 4.3.

Computations 1 and 3 walk downward from the full set, {−1,0,1}4\{-1,0,1\}^4 or ΓI∩{−1,0,1}4\Gamma_I\cap\{-1,0,1\}^4, deleting one pair of opposite vertices at a time. By the next lemma, such a walk reaches every saturated symmetric subset of the full set. Sets that a symmetry carries onto each other form a class, and the walk keeps one set of each class; classes are recognized by a canonical form, the least image of the set under the symmetry group in a fixed total order. This loses no class: a symmetry γ\gamma maps saturated symmetric sets to saturated symmetric sets and the vertices of conv⁡Q\operatorname{conv} Q to those of conv⁡γQ\operatorname{conv}\gamma Q, so the sets obtained from γQ\gamma Q by deleting a pair of opposite vertices are the images under γ\gamma of those obtained from QQ. Computation 5 uses a different method, a sandwich search, described after its statement.

Lemma 6.1. Let Λ\Lambda be a lattice and Q⊂ΛQ\subset\Lambda a finite symmetric set with conv⁡Q∩Λ=Q\operatorname{conv} Q\cap\Lambda=Q.

(i) If vv is a vertex of conv⁡Q\operatorname{conv} Q, then Q′=Q∖{v,−v}Q'=Q\setminus\{v,-v\} is symmetric and satisfies conv⁡Q′∩Λ=Q′\operatorname{conv} Q'\cap\Lambda=Q'.

(ii) If S⊊QS\subsetneq Q is symmetric with conv⁡S∩Λ=S\operatorname{conv} S\cap\Lambda=S, then some vertex vv of conv⁡Q\operatorname{conv} Q is not in SS, and S⊆Q∖{v,−v}S\subseteq Q\setminus\{v,-v\}.

Proof. (i) Since vv is a vertex, v∉conv⁡(Q∖{v})⊇conv⁡Q′v \notin\operatorname{conv}(Q \setminus\{v\}) \supseteq\operatorname{conv} Q', and by symmetry −v∉conv⁡Q′-v \notin\operatorname{conv} Q'; as conv⁡Q′∩Λ⊆Q\operatorname{conv} Q' \cap\Lambda\subseteq Q, it equals Q′Q'. (ii) If every vertex of conv⁡Q\operatorname{conv} Q were in SS, then Q=conv⁡Q∩Λ⊆conv⁡S∩Λ=SQ = \operatorname{conv} Q \cap\Lambda\subseteq\operatorname{conv} S \cap\Lambda= S. A vertex v∉Sv \notin S has −v∉S-v \notin S by symmetry. □

So every saturated symmetric S⊆QS \subseteq Q is reached from QQ through saturated symmetric sets that contain SS; in particular a search that stops at 31 points misses no set with at least 31 points.

Computation 1. Case I. We list all symmetric sets S⊆{−1,0,1}4S \subseteq\{-1,0,1\}^{4} with conv⁡S∩Z4=S\operatorname{conv} S \cap\mathbb{Z}^{4} = S and #S≥31\#S \geq31, up to the 384 signed permutations of the coordinates. Each such SS spans R4\mathbb{R}^{4} (a hyperplane through 00 contains at most 27 points of {−1,0,1}4\{-1,0,1\}^{4}, since on it one coordinate is determined by the other three), so conv⁡S∈O4\operatorname{conv} S \in\mathcal{O}^{4} by Lemma 2.1. There are 2,547,694 classes; for all of them the linear coefficient g1g_{1} of conv⁡S\operatorname{conv} S is at most 8, with equality only for S={−1,0,1}4S = \{-1,0,1\}^{4}.

Computation 2. Index bound. We list every sublattice Γ⊂Z4\Gamma\subset\mathbb{Z}^{4} of index dd with 2≤d≤162 \leq d \leq16 once, as Γ=BZ4\Gamma= B\mathbb{Z}^{4} with BB in Hermite normal form under column operations (B↦BUB \mapsto BU); there are 40,406 of them. For each Γ\Gamma whose points in {−1,0,1}4\{-1,0,1\}^{4} span R4\mathbb{R}^{4} we count these points. The maximum is 45 for d=2d = 2, and it is at most 27 for every d≥3d \geq3.

Computation 3. Case II. A permutation of coordinates carries ΓI\Gamma_{I} onto ΓJ\Gamma_{J} when ∣I∣=∣J∣\lvert I\rvert= \lvert J\rvert, so it suffices to take Γm=Γ{1,…,m}={x:x1+⋯+xm even}\Gamma_{m} = \Gamma_{\{1,\ldots,m\}} = \{x : x_{1} + \cdots+ x_{m}\ \text{even}\} for m=2,3,4m = 2,3,4. For each of these three lattices we list all Γm\Gamma_{m}-saturated symmetric sets S⊆Γm∩{−1,0,1}4S \subseteq\Gamma_{m} \cap\{-1,0,1\}^{4} that span R4\mathbb{R}^{4} and have #S≥31\#S \geq31, up to the signed permutations that preserve Γm\Gamma_{m}; each such conv⁡S\operatorname{conv} S lies in OΓm4\mathcal{O}^{4}_{\Gamma_{m}} (see the paragraph after Lemma 2.1). There are 531, 58 and 27 classes for m=2,3,4m = 2,3,4, and for all of them the linear coefficient g1g_{1} of conv⁡S\operatorname{conv} S with respect to Γm\Gamma_{m} is at most 6.

Computation 4. The frame lattices. We list all lattices in L\mathcal{L}. For U∈GL⁡4(Z)U \in\operatorname{GL}_{4}(\mathbb{Z}) the frame matrices VV and UVUV give the same lattice Λ=V−1Z4\Lambda= V^{-1}\mathbb{Z}^{4}, so it suffices to take VV in Hermite normal form under row operations (V↦UVV \mapsto UV), with determinant D≤23D \leq23, and to keep the lattices Λ\Lambda that satisfy (iv). There are 1,040 frame lattices, in 39 orbits under signed permutations, with indices D∈{1,…,10,12,16,18}D \in\{1,\ldots,10,12,16,18\}.

Computation 5. Case III. For each of the 39 representatives Λ\Lambda we list all S∈S(Λ)S \in\mathcal{S}(\Lambda) with #S≥31\#S \geq31 and r(S)≤3r(S) \leq3, up to the signed permutations that preserve Λ\Lambda. There are 588,592 classes; for all of them the linear coefficient g1g_{1} of conv⁡S\operatorname{conv} S with respect to Λ\Lambda is at most 8, with equality for exactly two of them, one with G=49G = 49 and one with G=33G = 33.

The search follows [2 Algorithm 1]. It keeps a lower set S−∈S(Λ)S^{-} \in\mathcal{S}(\Lambda) and an upper set S+⊇S−S^{+} \supseteq S^{-}, and it starts from S−=conv⁡{±e1,…,±e4}∩ΛS^{-} = \operatorname{conv}\{\pm e_{1},\ldots,\pm e_{4}\} \cap\Lambda and S+=Λ∩C4S^{+} = \Lambda\cap C_{4}. Every member of S(Λ)\mathcal{S}(\Lambda) lies between these two sets: it lies in S+S^{+} by (i), and it contains S−S^{-} by (i) and (iii). The set S−S^{-} is itself a member: its points cc have ∣c1∣+⋯+∣c4∣≤1\lvert c_{1}\rvert+ \cdots+ \lvert c_{4}\rvert\leq1, so (ii) holds by Hadamard’s inequality and (iii) by (iv).

For a pair ±v\pm v in S+∖S−S^{+} \setminus S^{-} the search branches: either ±v\pm v is excluded and S+S^{+} is replaced by S+∖{±v}S^{+} \setminus\{\pm v\}, or ±v\pm v is included and S−S^{-} is replaced by conv⁡(S−∪{±v})∩Λ\operatorname{conv}(S^{-} \cup\{\pm v\}) \cap\Lambda; every saturated set between S−S^{-} and S+S^{+} lies in exactly one branch. An include branch is abandoned when the new S−S^{-} is not contained in S+S^{+}, violates (ii), or has a nonzero point of Λ\Lambda in the interior of its convex hull, since then no set in the branch satisfies (i)–(iii). A pair ±y\pm y in S+S^{+} for which S−∪{±y}S^{-} \cup\{\pm y\} violates (ii) is removed from S+S^{+}, since no member contains it together with S−S^-. A branch is abandoned when #S+<31\#S^+ < 31 or r(S+)=4r(S^+) = 4; the second rule uses that MM reverses inclusion, that is, M(Q′)⊆M(Q)M(Q') \subseteq M(Q) whenever Q⊆Q′Q \subseteq Q', so that every subset of a set Q′Q' with r(Q′)=4r(Q') = 4 also has r=4r = 4. The search stops at the pairs (S−,S+)(S^-, S^+) with S−=S+S^- = S^+. Each include step keeps S−S^- in S(Λ)\mathcal{S}(\Lambda), so these sets are members, and they are the sets found. A pair (S−,S+)(S^-, S^+) that a signed permutation preserving Λ\Lambda carries onto a pair met earlier in the search is discarded, since the permutation carries the sets between the two pairs onto each other; the sets found are then reduced to one of each class by the canonical form described before Lemma 6.1.

Proof of Theorem 1.2. Let P∈O4P \in\mathcal{O}^4. If G(P)≤29G(P) \leq29, Lemma 4.3 gives g1(P)<8g_1(P) < 8. If G(P)≥31G(P) \geq31, then by Section 5 the pair (P,Z4)(P, \mathbb{Z}^4) is isomorphic to (conv⁡S,ΛS)(\operatorname{conv} S,\Lambda_S) for a set SS listed in Computation 1 (Case I), in Computation 3 (Case II, using Computation 2), or in Computation 5 (Case III, using Computation 4), where ΛS\Lambda_S is the lattice of that computation (Z4\mathbb{Z}^4, Γm\Gamma_m or a frame lattice); so LP=Lconv⁡S,ΛSL_P = L_{\operatorname{conv} S,\Lambda_S}. In each list g1≤8g_1 \leq8. Hence g1(P)≤8g_1(P) \leq8, and Proposition 4.2 gives g2(P)≤24g_2(P) \leq24. □

The equality cases

Let T⊂R4T \subset\mathbb{R}^4 be the convex hull of the 24 points ±fa±fb\pm f_a \pm f_b, 1≤a<b≤41 \leq a < b \leq4, where fi=eif_i = e_i for i≤3i \leq3 and f4=(−1,−1,−1,2)f_4 = (-1,-1,-1,2). This is the 24-cell conv⁡{±ea±eb}\operatorname{conv}\{\pm e_a \pm e_b\} written in the basis e1,e2,e3,12(1,1,1,1)e_1,e_2,e_3,\frac{1}{2}(1,1,1,1) of the lattice Z4∪(Z4+12(1,1,1,1))\mathbb{Z}^4 \cup(\mathbb{Z}^4 + \frac{1}{2}(1,1,1,1)); in other words, (T,Z4)(T,\mathbb{Z}^4) is isomorphic to the pair formed by this 24-cell and this lattice. Let

X=conv⁡{±(1,0,0,0), ±(0,1,0,0), ±(1,1,3,0), ±(2,4,3,6)}.X = \operatorname{conv}\{\pm(1,0,0,0),\ \pm(0,1,0,0),\ \pm(1,1,3,0),\ \pm(2,4,3,6)\}.

Theorem 7.1. A polytope P∈O4P \in\mathcal{O}^4 has g1(P)=8g_1(P) = 8 if and only if it is unimodularly equivalent to C4C_4, TT or XX.

We first check that TT and XX lie in O4\mathcal{O}^4, that C4C_4, TT and XX have g1=8g_1 = 8, and that M(T)=M(X)={0}M(T) = M(X) = \{0\}.

The polytope conv⁡{±ea±eb}\operatorname{conv}\{\pm e_a \pm e_b\} is the set of points xx with ∣xi∣≤1|x_i| \leq1 for all ii and ∣x1∣+⋯+∣x4∣≤2|x_1|+\cdots+|x_4| \leq2, so its lattice points in Z4∪(Z4+12(1,1,1,1))\mathbb{Z}^4 \cup(\mathbb{Z}^4 + \frac{1}{2}(1,1,1,1)) other than 0 are the 24 vertices, the 8 points ±ei\pm e_i and the 16 points (±12,±12,±12,±12)(\pm\frac{1}{2},\pm\frac{1}{2},\pm\frac{1}{2},\pm\frac{1}{2}); each has a coordinate ±1\pm1 or all four coordinates ±12\pm\frac{1}{2}, so it lies on one of the facets {xi=±1}\{x_i = \pm1\} or {±x1±x2±x3±x4=2}\{\pm x_1 \pm x_2 \pm x_3 \pm x_4 = 2\}. Hence T∈O4T \in\mathcal{O}^4 and G(T)=49G(T) = 49. The dual lattice of Z4∪(Z4+12(1,1,1,1))\mathbb{Z}^4 \cup(\mathbb{Z}^4 + \frac{1}{2}(1,1,1,1)) is {y∈Z4:y1+⋯+y4 even}\{y \in\mathbb{Z}^4 : y_1+\cdots+y_4 \text{ even}\}; its primitive vectors normal to these facets are ±2ei\pm2e_i and (±1,±1,±1,±1)(\pm1,\pm1,\pm1,\pm1), and they take the value 2 on them, so every facet of TT has lattice distance 2 from the origin. Moreover vol⁡(T)=16\operatorname{vol}(T) = 16, since conv⁡{±ea±eb}\operatorname{conv}\{\pm e_a \pm e_b\} has volume 8 and the lattice has determinant 12\frac{1}{2}.

For XX, a direct computation (see [17]) shows that 0 is its only interior lattice point, that G(X)=33G(X) = 33, and that each of its 16 facets has lattice distance 3 from the origin; and vol⁡(X)=244!⋅18=12\operatorname{vol}(X) = \frac{2^4}{4!} \cdot18 = 12, since the vectors (1,0,0,0)(1,0,0,0), (0,1,0,0)(0,1,0,0), (1,1,3,0)(1,1,3,0), (2,4,3,6)(2,4,3,6) have determinant 18.

If every facet of P∈O4P \in\mathcal{O}^4 has lattice distance ℓ\ell, then (E3) gives g3=12σ=2g4ℓg_3 = \frac{1}{2}\sigma= \frac{2g_4}{\ell}, and Lemma 4.1 gives g1=G−12−g3g_1 = \frac{G-1}{2} - g_3 and g2=G−12−g4g_2 = \frac{G-1}{2} - g_4. For C4C_4 we have G=81G = 81 and vol⁡(C4)=16\operatorname{vol}(C_4) = 16, and its facets {xi=±1}\{x_i = \pm1\} have lattice distance 1. With (G,g4,ℓ)=(81,16,1),(49,16,2)(G,g_4,\ell) = (81,16,1),(49,16,2) and (33,12,3)(33,12,3) this gives

LC4=1+8k+24k2+32k3+16k4,LT=1+8k+8k2+16k3+16k4,L_{C_4}=1+8k+24k^2+32k^3+16k^4,\qquad L_T=1+8k+8k^2+16k^3+16k^4,
LX=1+8k+4k2+8k3+12k4.L_X=1+8k+4k^2+8k^3+12k^4.

For TT, let u∈M(T)u\in M(T) and wa=⟨u,fa⟩∈Zw_a=\langle u,f_a\rangle\in\mathbb{Z}. Then ∣wa±wb∣≤1|w_a\pm w_b|\leq1 for a≠ba\ne b, so at most one waw_a is nonzero, and it is ±1\pm1. Here wa=uaw_a=u_a for a≤3a\leq3 and w4=2u4−u1−u2−u3w_4=2u_4-u_1-u_2-u_3. If w1=w2=w3=0w_1=w_2=w_3=0, then u1=u2=u3=0u_1=u_2=u_3=0 and w4=2u4w_4=2u_4 is even, so u4=0u_4=0. Otherwise wa=ua=±1w_a=u_a=\pm1 for one a≤3a\leq3 and w4=0w_4=0, so 2u4=ua=±12u_4=u_a=\pm1, which is impossible. So M(T)={0}M(T)=\{0\}.

For XX, the conditions ∣⟨u,v⟩∣≤1|\langle u,v\rangle|\leq1 for the first three vertices, namely ∣u1∣≤1|u_1|\leq1, ∣u2∣≤1|u_2|\leq1 and ∣u1+u2+3u3∣≤1|u_1+u_2+3u_3|\leq1, leave nine triples (u1,u2,u3)(u_1,u_2,u_3), one for each (u1,u2)(u_1,u_2). The fourth condition, ∣2u1+4u2+3u3+6u4∣≤1|2u_1+4u_2+3u_3+6u_4|\leq1, requires 2u1+4u2+3u3≡−1,02u_1+4u_2+3u_3\equiv-1,0 or 1(mod6)1\pmod{6}. Of the nine triples only (0,0,0)(0,0,0) satisfies this, and then u4=0u_4=0. So M(X)={0}M(X)=\{0\}.

Proof of Theorem 7.1. The three polytopes have g1=8g_1=8, and they are pairwise inequivalent because they have 81, 49 and 33 lattice points. Conversely, let g1(P)=8g_1(P)=8. By Lemma 4.3, G(P)≥31G(P)\geq31, so, as in the proof of Theorem 1.2, (P,Z4)(P,\mathbb{Z}^4) is isomorphic to (conv⁡S,ΛS)(\operatorname{conv} S,\Lambda_S) for a set SS with g1=8g_1=8 in one of Computations 1, 3, 5. In Computation 1 this is the cube, and the isomorphism lies in GL⁡4(Z)\operatorname{GL}_4(\mathbb{Z}); Computation 3 has none; in Computation 5 it is one of the two sets with G=49G=49 and G=33G=33. Now TT and XX have M(T)=M(X)={0}M(T)=M(X)=\{0\}, so they fall under Case III, and (T,Z4)(T,\mathbb{Z}^4) and (X,Z4)(X,\mathbb{Z}^4) are isomorphic to pairs (conv⁡S,ΛS)(\operatorname{conv} S,\Lambda_S) with SS in Computation 5 and g1=8g_1=8; comparing GG, these are the two sets found there. If (P,Z4)(P,\mathbb{Z}^4) and (T,Z4)(T,\mathbb{Z}^4) are both isomorphic to the same pair (after a signed permutation fixing its lattice, if needed), then composing the two isomorphisms gives a linear map that carries PP onto TT and Z4\mathbb{Z}^4 onto Z4\mathbb{Z}^4, that is, a map in GL⁡4(Z)\operatorname{GL}_4(\mathbb{Z}), and in the same way for XX. Hence, in this case, PP is unimodularly equivalent to TT or to XX. □

Corollary 7.2. A polytope P∈O4P\in\mathcal{O}^4 has g2(P)=24g_2(P)=24 if and only if it is unimodularly equivalent to C4C_4.

Proof. The cube has g2(C4)=24g_2(C_4)=24. Conversely, let g2(P)=24g_2(P)=24. Since g1(P)≤8g_1(P)\leq8 by Theorem 1.2, Proposition 4.2 gives 24=g2≤g4+8≤2424=g_2\leq g_4+8\leq24, so g4=16g_4=16, and then G=2(g2+g4)+1=81G=2(g_2+g_4)+1=81 by Lemma 4.1. The same lemma gives g1+g3=40g_1+g_3=40, and g1≤8g_1\leq8, g3≤32g_3\leq32 force g1=8g_1=8. By Theorem 7.1, PP is unimodularly equivalent to C4C_4, TT or XX, and of these only C4C_4 has 81 lattice points. □

Remark 7.3. Henze’s theorem [11 Corollary 3.3] covers C4C_4 but neither TT nor XX. All roots of LC4=(1+2k)4L_{C_4}=(1+2k)^4 have real part −12-\frac{1}{2}, but those of LTL_T and LXL_X do not: if all four roots of LPL_P, for P∈O4P\in\mathcal{O}^4, have real part −12-\frac{1}{2}, they sum to −2-2, so g3(P)=2g4(P)g_3(P)=2g_4(P) by Vieta’s formulas; but LTL_T has g3=16≠2⋅16g_3=16\ne2\cdot16 and LXL_X has g3=8≠2⋅12g_3=8\ne2\cdot12. Alternatively, by [5] such a PP would be reflexive, that is, all its facets would have lattice distance 1 from the origin, while the facets of TT and XX have lattice distance 2 and 3.

Acknowledgments

This work was done overwhelmingly by AI models, steered by the author in a continuous critical dialogue, alternating between Anthropic’s Claude and OpenAI’s ChatGPT. The author takes full responsibility for the paper.

References

Email address: [email protected]

References

  1. [1]G. Averkov, C. Borger and I. Soprunov, Classification of triples of lattice polytopes with a given mixed volume, Discrete Comput. Geom. 66 (2021), no. 1, 165–202.DOI
  2. [2]G. Averkov and M. Schymura, On the maximal number of columns of a Δ-modular integer matrix: bounds and computations, Math. Program. 206 (2024), 61–89.arxiv.org/abs/2111.06294
  3. [3]M. Beck and S. Robins, Computing the Continuous Discretely, 2nd ed., Springer, New York, 2015.
  4. [4]U. Betke, M. Henk and J. M. Wills, Successive-minima-type inequalities, Discrete Comput. Geom. 9 (1993), 165–175.
  5. [5]C. Bey, M. Henk and J. M. Wills, Notes on the roots of Ehrhart polynomials, Discrete Comput. Geom. 38 (2007), 81–98.DOI
  6. [6]E. Ehrhart, Sur les polyèdres rationnels homothétiques à n dimensions, C. R. Acad. Sci. Paris 254 (1962), 616–618.
  7. [7]D. Goel, Wills’ (1981) conjecture holds if and only if the dimension is at most 4, and other miscellanea, Zenodo, 2026, https://doi.org/10.5281/zenodo.23955454
  8. [8]P. Gritzmann and J. M. Wills, Lattice points, in: Handbook of Convex Geometry, Vol. B, North-Holland, Amsterdam, 1993, 765–797.DOI
  9. [9]C. Haase, A. Paffenholz, L. C. Piechnik and F. Santos, Existence of unimodular triangulations—positive results, Mem. Amer. Math. Soc. 270 (2021), no. 1321; arXiv:1405.1687.
  10. [10]M. Henk, A. Schürmann and J. M. Wills, Ehrhart polynomials and successive minima, Mathematika 52 (2005), 1–16.DOI
  11. [11]M. Henze, On counterexamples to a conjecture of Wills and Ehrhart polynomials whose roots have equal real parts, Electron. J. Combin. 21(1) (2014), #P1.28.arxiv.org/abs/1309.0725
  12. [12]J. A. De Loera, R. Hemmecke, J. Tauzer and R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004), 1273–1302.
  13. [13]P. McMullen, Convex bodies which tile space by translation, Mathematika 27 (1980), 113–121.
  14. [14]H. Minkowski, Geometrie der Zahlen, Teubner, Leipzig, 1896.
  15. [15]H. Minkowski, Allgemeine Lehrsätze über die convexen Polyeder, Nachr. Ges. Wiss. Göttingen (1897), 198–219.
  16. [16]W. Bruns, B. Ichim, C. Söger and U. von der Ohe, Normaliz. Algorithms for rational cones and affine monoids, available at https://www.normaliz.uni-osnabrueck.de
  17. [17]D. Goel, Supporting materials for “Wills’ (1981) conjecture holds if and only if the dimension is at most 4”, GitHub repository, https://github.com/david44hello/paper_wills-1981-conjecture
  18. [18]B. A. Ven’kov, On a class of Euclidean polyhedra, Vestnik Leningrad. Univ. Ser. Mat. Fiz. Him. 9 (1954), 11–31.
  19. [19]D. W. Walkup, The lower bound conjecture for 3- and 4-manifolds, Acta Math. 125 (1970), 75–107.DOI
  20. [20]J. M. Wills, On an analog to Minkowski’s lattice point theorem, in: The Geometric Vein (C. Davis, B. Grünbaum, F. A. Sherk, eds.), Springer, New York, 1981, 285–288.DOI

Paper details

vlnc:W_28c3tjxr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, ChatGPT

View statement
Looking for related papers…
Contents