Lattice polytopes with distinct pair-sums

M. D. Choi University of Toronto Toronto, M5S 3G3, Canada

T. Y. Lam University of California Berkeley, CA 94720

Bruce Reznick University of Illinois Urbana, IL 61801

May 29, 2001

Let P be a lattice polytope in ℝ^{n}, the convex hull of a finite set in ℤ^{n}, and let

L(P) := P ∩ ℤ^{n} = {v_{1}, …, v_{N}},

where N = N(P) := |L(P)|. Suppose the N + \binom{N}{2} points in L(P) + L(P),

2v_{1}, …, 2v_{N}; v_{1} + v_{2}, v_{1} + v_{3}, …, v_{N−1} + v_{N}

are distinct. In this case, we say that P is a distinct pair-sum or dps polytope. Our interest in dps polytopes comes from the study of the representation of polynomials as a sum of squares of polynomials.

The following lemma offers two other geometrical characterizations of dps polytopes.

Lemma 1. Let P be a lattice polytope. Then the following are equivalent:

(1) L(P) is a dps polytope.

(2) L(P) does not contain the vertices of a (nondegenerate) parallelogram, and does not contain three collinear points.

(3) Suppose v ≠ v′ and w ≠ w′ are in L(P). Then v′ −v and w′ −w are parallel only if {v, v′} = {w, w′}.

Proof. (1) ⇒ (2). Suppose v_{1}, v_{2}, v_{3}, v_{4} ∈ L(P) are the vertices of a parallelogram. Then v_{1} −v_{2} = v_{3} −v_{4} implies v_{1} +v_{4} = v_{2} +v_{3}, so that P is not dps. Now suppose v_{1}, v_{2}, v_{3} ∈ L(P), and v_{2} is interior to the line segment \overline{v_{1}v_{3}}. If v_{2} is the midpoint of the segment, then v_{2} + v_{2} = v_{1} + v_{3}, so P is not dps. Otherwise, we may assume that v_{2} is closer to v_{1} than to v_{3}. Then v_{4} = v_{2} + (v_{2} − v_{1}) will also be a lattice point on the line segment \overline{v_{1}v_{3}}, and v_{2} is the midpoint of \overline{v_{1}v_{4}}; again, P is not dps.

(2) ⇒ (3). For u ∈ ℤ^{n}, let g(u) = gcd(u_{1}, …, u_{n}). Suppose g(u′ − u) = d > 1. Then u′ − u = du′′ for u′′ ∈ ℤ^{n}, and the line segment \overline{u u′} contains the lattice points u, u + u′′, …, u + du′′ = u′. Thus, if (2) holds and u, u′ ∈ L(P), u ≠ u′, we have g(u′ − u) = 1. Suppose w′ − w = α · (v′ − v). Then α = p/q for nonzero integers p, q, and q(w′ − w) = p(v′ − v). Hence |q| = g(q(w′ − w)) = g(p(v′ − v)) = |p|, so α = ±1. Now the parallelogram condition in (2) implies that {v, v′} = {w, w′}.

(3) ⇒ (1). If (3) holds for P, and v_{i}, v_{j}, v_{k}, v_{ℓ} ∈ L(P) with i ∉ {k, ℓ}, then v_{i} − v_{k} ≠ v_{ℓ} − v_{j}, and so v_{i} + v_{j} ≠ v_{k} + v_{ℓ}. This proves (1).

Our main results are these: if P in ℝ^{n} is a dps polytope, then N(P) ≤ 2^{n}, and, for every n, we construct dps polytopes in ℝ^{n} for which N(P) = 2^{n}.

Example 1. Let P ⊂ ℝ^{2} be the triangle with vertices {(0, 1), (1, 2), (2, 0)}. Then P is a dps polytope, because

L(P) = {(0, 1), (1, 2), (2, 0), (1, 1)},

and

L(P) + L(P) = {(0, 2), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (4, 0)}.

We can view P as the projection onto the first two coordinates of the triangle with vertices {(0, 1, 2), (1, 2, 0), (2, 0, 1)}, which lies in the hyperplane x_{1} + x_{2} + x_{3} = 3. (In this example, we could have just as well taken the triangle with vertices {(0, 0), (1, 2), (2, 1)}; again, L(P) will consist of the vertices of P and (1, 1).)

Example 2. Let

A = {(4, 1, 0, 0), (0, 4, 1, 0), (0, 0, 4, 1), (1, 0, 0, 4)},
B = {(2, 1, 1, 1), (1, 2, 1, 1), (1, 1, 2, 1), (1, 1, 1, 2)};

and let P = cvx(A ∪ B) ⊂ ℝ^{4} be the convex hull of A ∪ B. By construction, P is cyclically symmetric with respect to its coordinates. It is not hard to show that L(P) = A ∪ B. Suppose w = (w^{(1)}, w^{(2)}, w^{(3)}, w^{(4)}) ∈ L(P). Since w is a convex combination of A ∪ B, we have w^{(i)} ≥ 0 and ∑_{i} w^{(i)} = 5. If w^{(i)} ≥ 1 for all i, then w must be a permutation of (2, 1, 1, 1) and so lies in B. Otherwise, w^{(i)} = 0 for some i, and by cycling the coordinates, we may assume that w^{(1)} = 0. But then w must be a convex combination of (0, 4, 1, 0) and (0, 0, 4, 1) and so w ∈ A. A routine check, which we omit, shows that the 8 + \binom{8}{2} = 36 sums in L(P) + L(P) are distinct. By projecting P onto its first three coordinates, we obtain a dps polytope in ℝ^{3} with N(P) = 8.

Theorem 2. Suppose P is a dps polytope in ℝ^{n}. Then N(P) ≤ 2^{n}.

Proof. If N(P) > 2^{n}, then by the Pigeonhole Principle, there exist v_{i} ≠ v_{j} so that v_{i} and v_{j} are component-wise congruent modulo 2. This means that v_{k} = \frac{1}{2}(v_{i} + v_{j}) = v_{i} + \frac{1}{2}(v_{j} − v_{i}) is also a lattice point, and it follows from Lemma 1 that P is not a dps polytope.

This argument is essentially the same one used to solve Putnam Problem 1971-A1 (see [?]): “Let there be given nine lattice points (points with integral coordinates) in three dimensional Euclidean space. Show that there is a lattice point on the interior of one of the line segments joining two of these points.” The proof of Theorem 2 also applies to the less restrictive class of convex polytopes which do not contain three lattice points on a line. One such polytope is the n-cube C_{n} = {0, 1}^{n}, which has many lattice parallelograms.

We shall say that a dps polytope P ⊂ ℝ^{n} for which N(P) = 2^{n} is maximal. The proof of Theorem 2 implies that no two points in a dps polytope are componentwise congruent modulo 2; hence a maximal dps polytope contains one representative from every congruence class modulo 2 (and at most one representative from every congruence class modulo m, m ≥ 3).

Suppose M is an n×n unimodular matrix with integer entries. Then M defines a linear mapping on ℝ^{n} (viewed as column vectors) by matrix multiplication. Since linear mappings preserve inclusions and both M and M^{−1} have integer entries, it is easy to see that L(M(P)) = M(L(P)) for any lattice polytope P, and since linear mappings preserve sums, it is then clear that P is dps if and only if M(P) is dps.

Theorem 3. There exist maximal dps polytopes in ℝ^{n} for every n.

Proof. For n = 1, let P = [0, 1]; for n = 2, 3, consider Examples 1 and 2. Suppose now that P is a maximal dps polytope in ℝ^{n}, n ≥ 3. Write L = L(P) and define the (finite) set of differences

D = (L − L)^{∗} := {v − v′ : v, v′ ∈ L, v ≠ v′}.

Let M be a unimodular integer matrix such that if u ∈ D, then M(u) ∉ D. (We shall construct such an M below.)

We define the polytope P′ in ℝ^{n+1} as follows. Let

A = {(v, 0) ∈ ℝ^{n+1} : v ∈ L(P)}, B = {(M(v), 1) ∈ ℝ^{n+1} : v ∈ L(P)},

and let P′ = cvx(A ∪ B). If w = (w^{(1)}, …, w^{(n+1)}) ∈ L(P′), then 0 ≤ w^{(n+1)} ≤ 1, hence w^{(n+1)} equals 0 or 1. Thus, w lies either on the face determined by A, in which case w = (v, 0), or on the face determined by B, in which case w = (M(v), 1). It follows that L(P′) = A ∪ B, so N(P′) = 2^{n+1}.

Now consider L(P′) + L(P′); this consists of three disjoint sets of points:

{(v_{i}, 0) + (v_{j}, 0)},  {(v_{i}, 0) + (M(v_{j}), 1)},  {(M(v_{i}), 1) + (M(v_{j}), 1)},

where v_{i}, v_{j} ∈ L(P). Since both P and M(P) are dps, the sums in the first and the third set are distinct. For the second set, we suppose that

(v_{i}, 0) + (M(v_{j}), 1) = (v_{k}, 0) + (M(v_{ℓ}), 1),  (1)

or equivalently,

v_{i} − v_{k} = M(v_{ℓ}) − M(v_{j}) = M(v_{ℓ} − v_{j}).

If j = ℓ, then v_{i} − v_{k} = 0, so i = k, which is the only possible way for (??) to hold in a dps polytope. Otherwise, j ≠ ℓ, so M(v_{ℓ} − v_{j}) = v_{i} − v_{k} ∈ D, a contradiction to the choice of M. Thus, P′ is a maximal dps polytope in ℝ^{n+1}.

We now construct a matrix M with the desired properties. First, let

R = max {|u_{j}^{(k)}| : u_{j} ∈ D, 1 ≤ k ≤ n}.

and let M be the n × n matrix given below:

M = ( \begin{matrix}1 + (R + 1)^{2} & R + 1 & 0 & 0 & … & 0 & 0 \\ R + 1 & 1 & R + 1 & 0 & … & 0 & 0 \\ 0 & 0 & 1 & R + 1 & … & 0 & 0 \\ 0 & 0 & 0 & 1 & … & 0 & 0 \\ … & … & … & … & … & … & … \\ 0 & 0 & 0 & 0 & … & 1 & R + 1 \\ 0 & 0 & 0 & 0 & … & 0 & 1 \end{matrix} ) .

(In words, the only non-zero entries in M are the diagonal, the superdiagonal, and the first entry in the second row.) It is easy to see that M is unimodular.

We show now that for every u ∈ D, at least one entry of w = M(u) has absolute value greater than R. This implies that M(u) ∉ D, and will complete the proof. Write u = (u^{(1)}, …, u^{(n)}) and suppose that k is the smallest index such that u^{(k)} ≠ 0. (Such an index exists because 0 ∉ D.)

If k = 1, then w^{(1)} = (1 + (R + 1)^{2})u^{(1)} + (R + 1)u^{(2)}, and hence

|w^{(1)}| ≥ |(1 + (R + 1)^{2})u^{(1)}| − (R + 1)|u^{(2)}| ≥ 1 + (R + 1)^{2} − R(R + 1) = R + 2.

If k ≥ 2, then u^{(1)} = ⋯ = u^{(k−1)} = 0, so w^{(k−1)} = (R+1)u^{(k)} and |w^{(k−1)}| ≥ R+1. Finally, we remark that the same proof applies in the case n = 2, if we take as our matrix the 2 × 2 submatrix at the upper left of M.

Example 3. We illustrate the last construction by applying it to the polytope in Example 1, for which

D = {±(0, 1), ±(1, −2), ±(1, −1), ±(1, 0), ±(1, 1), ±(2, −1)},

so R = 2 and

M = ( \begin{matrix}10 & 3 \\ 3 & 1 \end{matrix} ) .

Thus, cvx(A ∪ B) is a maximal dps polytope in ℝ^{3}, where

A = {(0, 1, 0), (1, 1, 0), (1, 2, 0), (2, 0, 0)},
B = {(3, 1, 1), (13, 4, 1), (16, 5, 1), (20, 6, 1)}.

We could now apply the shear (x_{1}, x_{2}, x_{3}) ↦ (x_{1} −3x_{2} −5x_{3} +5, x_{2} −x_{3}, x_{3}), which maps A and B to

A′ := {(2, 1, 0), (3, 1, 0), (0, 2, 0), (7, 0, 0)}

and

B′ := {(0, 0, 1), (1, 3, 1), (1, 4, 1), (2, 5, 1)},

respectively, in order to reduce the magnitude of the coordinates in the example.

Since any translate of a dps polytope is also dps, we may always assume, as we have done in the examples, that P lies in the non-negative orthant of ℝ^{n}. In this case, we define s(P), the size of P:

s(P) = max{v_{j}^{(1)} + ⋯ + v_{j}^{(n)} : v_{j} ∈ L(P)}.

If s = s(P), then P can be viewed as a projection onto the first n coordinates of a polytope in ℝ^{n+1} which lies in the simplex

Δ_{n+1}(s) := {u = (u^{(1)}, …, u^{(n+1)}) : u^{(i)} ≥ 0, ∑_{i=1}^{n+1} u^{(i)} = s}.

Let s_{n} denote the minimum size of any maximal dps polytope in ℝ^{n}. Examples 1 and 2 show that s_{2} ≤ 3 and s_{3} ≤ 5. It is not difficult to show that these estimates are sharp. The first case can be done by hand: if P is a maximal dps polytope with size 2 in ℝ^{2}, then L(P) must consist of four points chosen from

{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0)}.

Since each congruence class is represented in L(P), it must contain (0, 1), (1, 0) and (1, 1). These three points form a parallelogram with each of the points (0, 0), (0, 2) and (2, 0). Hence no fourth point can exist in L(P) while preserving the dps property. The second case is similar, but much more complicated. Computeraided calculations can be used to conclude that no dps polytope in ℝ^{3} has size 4 or less. (We thank Dr. Bruce Carpenter for doing the Mathematica coding.)

It can also be shown, using the style of argument of [?, Ch. 3], that every maximal dps polytope in ℝ^{2} is the image of the triangle in Example 1 under an affine unimodular linear mapping, and consists of a triangle with area 3/2, and a single lattice point inside, which will always be the centroid of the triangle. The tetrahedron determined by B in Example 2 lies within the tetrahedron determined by A, whereas in Example 3, each point in L is on the boundary of the polytope.

Thus there are at least two distinct combinatorial types of maximal dps polytopes in ℝ^{3}.

We make no serious conjecture about the growth of s_{n}. On the one hand, any maximal dps polytope must contain a lattice point with odd coordinates, so s_{n} ≥ n. In the other direction, it is not difficult to use the proof of Theorem 3 to obtain a doubly-exponential bound for s_{n}. Since this bound is likely to be very crude, we do not present it explicitly. Another open question is to determine the minimum volume of a maximal dps polytope in ℝ^{n} for n ≥ 3. We also do not know the answer to the following question: is every dps polytope a subset of a maximal dps polytope?”

We now discuss our original interest in this subject. Given u ∈ ℤ_{+}^{n}, define the monomial x^{u} ∈ ℝ[x_{1}, …, x_{n}] by

x^{u} = x_{1}^{u^{(1)}} … x_{n}^{u^{(n)}}.

Suppose U ⊆ ℤ_{+}^{n} and consider the polynomial

p(x_{1}, …, x_{n}) = ∑_{u∈U} b_{u}x^{u}.

In [?], the present authors developed an algorithm for determining whether p can be written as a sum of squares of polynomials. A necessary condition is that p is psd; that is, p(x_{1}, …, x_{n}) ≥ 0 for all x ∈ ℝ^{n}. Suppose p is psd and let

C(p) = cvx{u : b_{u} ≠ 0}.

Then C(p) is a lattice polytope; in fact it can be shown that the vertices of C(p) lie in (2ℤ)^{n}, so that P := \frac{1}{2}C(p) is a lattice polytope. Let

L(P) = {v_{1}, …, v_{N}},

and for u ∈ C(p), let D(u) = {(i, j) : v_{i} + v_{j} = u}. It is proved in [?, Thm. 2.4] that p can be written as a sum of at most r squares of polynomials if and only if there is a real N × N symmetric psd matrix A = [a_{ij}] of rank at most r, so that

∑_{(i,j)∈D(u)} a_{ij} = b_{u} for all u ∈ C(p).

If P is a dps polytope in ℝ^{n}, then either |D(u)| ≤ 1 or D(u) = {(i, j), (j, i)}. In either case, a_{ij} is completely determined by b_{u}. In particular, if

h_{P}(x_{1}, …, x_{n}) := ∑_{i=1}^{N} (x^{v_{i}})^{2} ,  (2)

then A must equal I_{N}, the N ×N identity matrix, so that p is a sum of N squares, and no fewer.

Finally, we note that the homogenization of polynomials with n variables into forms with n + 1 variables is precisely analogous to the embedding of polytopes in ℝ_{+}^{n} into the hyperplane Δ_{n+1}(s).

Example 4. (See [?, Ex. 3.9])

We return to Example 1, in its homogeneous version. Let A = [a_{ij}] be a real symmetric 4 × 4 matrix and let

f(t_{1}, t_{2}, t_{3}, t_{4}) = ∑_{i=1}^{4} ∑_{j=1}^{4} a_{ij}t_{i}t_{j}

be its associated quadratic form. We use the substitution suggested by L(P) and define the ternary sextic form

p(x_{1}, x_{2}, x_{3}) = f(x_{2}x_{3}^{2}, x_{1}x_{2}^{2}, x_{1}^{2}x_{3}, x_{1}x_{2}x_{3}).

Then p is a sum of squares of polynomials (cubic forms) if and only if f is a psd quadratic form; that is,

f(t_{1}, t_{2}, t_{3}, t_{4}) ≥ 0 for all (t_{1}, t_{2}, t_{3}, t_{4}) ∈ ℝ^{4}.

Since t_{4}^{3} = t_{1}t_{2}t_{3}, the condition for p to be a psd form is weaker:

f(t_{1}, t_{2}, t_{3}, (t_{1}t_{2}t_{3})^{1/3}) ≥ 0 for all (t_{1}, t_{2}, t_{3}) ∈ ℝ^{3}.

If f(t_{1}, t_{2}, t_{3}, t_{4}) = t_{1}^{2}+t_{2}^{2}+t_{3}^{2}−3t_{4}^{2}, then f is not psd, but f(t_{1}, t_{2}, t_{3}, (t_{1}t_{2}t_{3})^{1/3}) ≥ 0 by the arithmetic-geometric inequality. It follows that

p(x_{1}, x_{2}, x_{3}) = x_{2}^{2}x_{3}^{4} + x_{1}^{2}x_{2}^{4} + x_{1}^{4}x_{3}^{2} − 3x_{1}^{2}x_{2}^{2}x_{3}^{2}

is a form which is psd, but not a sum of squares of polynomials. This particular example was discussed in [?]. For a history and bibliography of this subject and its relation to Hilbert’s 17th Problem, see [?].

More generally, the Pythagoras number of a ring A, P (A), is the smallest number n ≤ ∞ such that any sum of squares in A can be expressed as a sum of at most n squares in A. Pfister [?] proved in 1967 that P (ℝ(x_{1}, …, x_{n})) ≤ 2^{n}. It is easy to see that P (ℝ[x_{1}]) = 2. Since maximal dps polytopes exist in ℝ^{n} for every n, a consideration of h_{P} (c.f. (??)) shows that P (ℝ[x_{1}, …, x_{n}]) ≥ 2^{n}. This is not the strongest result possible: in [?, p.60], using other methods, Dai and the present authors have shown that P (ℝ[x_{1}, …, x_{n}]) = ∞ for n ≥ 2.

References

[1] G. L. Alexanderson, L. F. Klosinski, L. C. Larson (eds.), The William Lowell Putnam Mathematical Competition, Problems and Solutions: 1964–1984, Mathematical Association of America, 1985.

[2] M. D. Choi, Z. D. Dai, T. Y. Lam and B. Reznick, The pythagoras number of some affine algebras and local algebras, J. Reine. Angew. Math. 336 (1982), 45–82.

[3] M. D. Choi and T. Y. Lam, An old question of Hilbert, Queen’s Papers in Pure and Appl. Math. (Proceedings of Quadratic Forms Conference, Queen’s University (G. Orzech ed.)) 46 (1976), 385–405.

[4] M. D. Choi, T. Y. Lam and B. Reznick, Sums of squares of real polynomials, Proc. Symp. Pure Math. 58.2 (1995), 103–126.

[5] A. Pfister, Zur Darstellung definiter Funktionen als Summe von Quadraten, Invent. Math. 4 (1967), 229–237.

[6] B. Reznick, Lattice point simplices, Discrete Math. 60 (1986), 219–242.

[7] B. Reznick, Some concrete aspects of Hilbert’s 17th Problem, Contemp. Math. 253 (2000), 251–272.