# Demonstration Definition 1

Abstract. Given a lattice polytope $`P`$ (with underlying lattice $`𝕃`$), the universal counting function $`𝒰_P(𝕃^{})=|P𝕃^{}|`$ is defined on all lattices $`𝕃^{}`$ containing $`𝕃`$. Motivated by questions concerning lattice polytopes and the Ehrhart polynomial, we study the equation $`𝒰_P=𝒰_Q`$.

Mathematics Subject Classification: 52B20, 52A27, 11P21

1. The universal counting function

We will denote by $`V`$ a vector space of dimension $`n`$, by $`𝕃`$ a lattice in $`V`$, of rank $`n`$. Let

$$𝒢_𝕃=𝕃GL(𝕃)$$

be the group of affine maps of $`V`$ inducing isomorphism of $`V`$ and $`𝕃`$ into itself; in case

$$𝕃=^nV=^n,𝒢_n=^nGL(^n)$$

corresponds to affine unimodular maps. An $`𝕃`$–polytope is the convex hull of finitely many points from $`𝕃`$; $`𝒫_𝕃`$ denotes the set of all $`𝕃`$–polytopes. For a finite set $`A`$ denote by $`|A|`$ its cardinality. Finally, let $`_𝕃`$ be the set of all lattices containing $`𝕃`$.

###### Demonstration Definition 1

Given any $`𝕃`$–polytope $`P`$, the function $`𝒰_P:_𝕃`$ defined by

$$𝒰_P(𝕃^{})=|P𝕃^{}|$$

is called the universal counting function of $`P`$.

This is just the restriction of another function $`𝒰:𝒫_𝕃\times _𝕃`$ to a fixed $`P𝒫_𝕃`$, where $`𝒰`$ is given by

$$𝒰(P,𝕃^{})=|P𝕃^{}|.$$

Note, further, that $`𝒰_P`$ is invariant under the group, $`𝒢_{tr}`$, generated by $`𝕃`$–translations and the reflection with respect to the origin, but, of course, not invariant under $`𝒢_𝕃`$.

Example 1. Take for $`𝕃^{}`$ the lattices $`𝕃_k=\frac{1}{k}𝕃`$ with $`k`$. Then

$$𝒰_P(𝕃_k)=|P\frac{1}{k}𝕃|=|kP𝕃|=E_P(k)$$

where $`E_P`$ is the Ehrhart polynomial of $`P`$ (see \[Ehr\]). We will need some of its properties that are described in the following theorem (see for instance \[Ehr\],\[GW\]). Just one more piece of notation: if $`F`$ is a facet of $`P`$ and $`H`$ is the affine hull of $`F`$, then the relative volume volume of $`F`$ is defined as

$$rvol(F)=\frac{\underset{n1}{Vol}(F)}{\underset{n1}{Vol}(D)}$$

where $`D`$ is the fundamental parallelotope of the $`(n1)`$–dimensional sublattice of $`H𝕃`$. For a face $`F`$ of $`P`$ that is at most $`(n2)`$–dimensional let $`rvol(F)=0`$. Note that the relative volume is invariant under $`𝒢_𝕃`$ and can be computed, when $`𝕃=^n`$, since then the denominator is the euclidean length of the (unique) primitive outer normal to $`F`$ (when $`F`$ is a facet).

###### Theorem 1

Assume $`P`$ is an $`n`$–dimensional $`𝕃`$–polytope. Then $`E_P`$ is a polynomial in $`k`$ of degree $`n`$. Its main coefficient is $`Vol(P)`$, and its second coefficient equals

$$\frac{1}{2}\underset{F\text{ a facet of }P}{}rvol(F).$$

It is also known that $`E_P`$ is a $`𝒢_𝕃`$–invariant valuation, (for the definitions see \[GW\] or \[McM\]). The importance of $`E_P`$ is reflected in the following statement from \[BK\]. For a $`𝒢_𝕃`$–invariant valuation $`\varphi `$ from $`𝒫_𝕃`$ to an abelian group $`G`$, there exists a unique $`\gamma =(\gamma _i)_{i=0,\mathrm{},n}`$ with $`\gamma _iG`$ such that

$$\varphi (P)=\gamma _ie_{P,i}$$

where $`e_{P,i}`$ is the coefficient of $`k^i`$ of the Ehrhart polynomial.

It is known that $`E_P`$ does not determine $`P`$, even within $`𝒢_𝕃`$ equivalence. \[Ka\] gives examples lattice–free $`𝕃`$–simplices with identical Ehrhart polynomial that are different under $`𝒢_𝕃`$. The aim of this paper is to investigate whether and to what extent the universal counting function determines $`P`$.

We give another description of $`𝒰_P`$. Let $`\pi VV`$ be any isomorphism satisfying $`\pi (𝕃)𝕃`$. Define, with a slight abuse of notation,

$$𝒰_P(\pi )=|\pi (P)𝕃|=|P\pi ^1(𝕃)|.$$

Set $`𝕃^{}=\pi ^1(𝕃)`$. Since $`𝕃^{}`$ is a lattice containing $`𝕃`$ we clearly have

$$𝒰_P(\pi )=𝒰_P(𝕃^{}).$$

Conversely, given a lattice $`𝕃^{}_𝕃`$, there is an isomorphism $`\pi `$ satisfying the last equality. (Any linear $`\pi `$ mapping a basis of $`𝕃`$ to a basis of $`𝕃^{}`$ suffices.) The two definitions of $`𝒰_P`$ via lattices or isomorphisms with $`\pi (𝕃)𝕃`$ are equivalent. We will use the common notation $`𝒰_P`$.

Example 2. Anisotropic dilatations. Take $`\pi :^n^n`$ defined by

$$\pi (x_1,\mathrm{},x_n)=(k_1x_1,\mathrm{},k_nx_n),$$

where $`k_1,\mathrm{},k_n`$. The corresponding map $`𝒰_P`$ extends the notion of Ehrhart polynomial and Example 1.

Simple examples show that $`𝒰_P`$ is not a polynomial in the variables $`k_i`$.

2. A necessary condition

Given a nonzero $`z𝕃^{}`$, the dual of $`𝕃`$, and an $`𝕃`$–polytope $`P`$, define $`P(z)`$ as the set of points in $`P`$ where the functional $`z`$ takes its maximal value. As is well known, $`P(z)`$ is a face of $`P`$. Denote by $`H(z)`$ the hyperplane $`zx=0`$ (scalar product). $`H(z)`$ is clearly a lattice subspace.

###### Theorem 2

Assume $`P,Q`$ are $`𝕃`$–polytopes with identical universal counting function. Then, for every primitive $`z𝕃^{}`$,

$$rvolP(z)+rvolP(z)=rvolQ(z)+rvolQ(z).$$
$``$   
The theorem shows, in particular, that if $`P(z)`$ or $`P(z)`$ is a facet of $`P`$, then $`Q(z)`$ or $`Q(z)`$ is a facet of $`Q`$. Further, given an $`𝕃`$–polytope $`P`$, there are only finitely many possibilities for the outer normals and volumes of the facets of another polytope $`Q`$ with $`𝒰_P=𝒰_Q`$. So a well–known theorem of Minkowski implies,

###### Corollary 1

Assume $`P`$ is an $`𝕃`$–polytope. Then, apart from lattice translates, there are only finitely many $`𝕃`$–polytopes with the same universal counting functions as $`P`$.

###### Demonstration Proof of Theorem 2

We assume that $`P,Q`$ are full–dimensional polytopes. It is enough to prove the theorem in the special case when $`𝕃=^n`$ and $`z=(1,0,\mathrm{},0)`$. There is nothing to prove when none of $`P(z),P(z),Q(z)`$, $`Q(z)`$ is a facet since then both sides of (\*) are equal to zero. So assume that, say, $`P(z)`$ is a facet, that is, $`rvolP(z)>0`$.

For a positive integer $`k`$ define the linear map $`\pi _kVV`$ by

$$\pi _k(x_1,\mathrm{},x_n)=(x_1,kx_2,\mathrm{},kx_n).$$

The condition implies that the lattice polytopes $`\pi _k(P)`$ and $`\pi _k(Q)`$ have the same Ehrhart polynomial. Comparing their second coefficients we get,

$$\underset{F\text{ a facet of }P}{}rvol\pi _k(F)=\underset{G\text{ a facet of }Q}{}rvol\pi _k(G),$$

since the facets of $`\pi _k(P)`$ are of the form $`\pi _k(F)`$ where $`F`$ is a facet of $`P`$.

Let $`\zeta =(\zeta _1,\mathrm{},\zeta _n)^n`$ be the (unique) primitive outer normal to the facet $`F`$ of $`P`$. Then $`\zeta ^{}=(k\zeta _1,\zeta _2,\mathrm{},\zeta _n)`$ is an outer normal to $`\pi _k(F)`$, and so it is a positive integral multiple of the unique primitive outer normal $`\zeta ^{\prime \prime }`$, that is $`\zeta ^{}=m\zeta ^{\prime \prime }`$ with $`m`$ a positive integer. When $`k`$ is a large prime and $`\zeta `$ is different from $`z`$ and $`\zeta _10`$, then $`m=1`$ and $`rvol\pi _k(F)=O(k^{n2})`$. When $`\zeta _1=0`$, then $`m=1`$, again, and the ordinary $`(n1)`$–volume of $`\pi _k(F)`$ is $`O(k^{n2})`$. Finally, when $`\zeta =\pm z`$, $`Vol\pi _k(F)=k^{n1}VolF`$.

So the dominant term, when $`k\mathrm{}`$, is $`k^{n1}(rvolP(z)+rvolP(z))`$ since by our assumption $`rvolP(z)>0`$. ∎

3. Dimension two

Let $`P`$ be an $`𝕃`$–polygon in $`V`$ of dimension two. Simple examples show again that $`𝒰_P`$ is not a polynomial in the coefficients of $`\pi `$.

In the planar case we abbreviate $`rvolP(z)`$ as $`|P(z)|`$. Extending (and specializing) Theorem 1 we prove

###### Proposition 3

Suppose $`P`$ and $`Q`$ are $`𝕃`$–polygons. Then $`𝒰_P=𝒰_Q`$ if and only if the following two conditions are satisfied:

(i) $`Area(P)=Area(Q)`$,

(ii) $`|P(z)|+|P(z)|=|Q(z)|+|Q(z)|`$ for every primitive $`z𝕃^{}`$.

###### Demonstration Proof

The conditions are sufficient: (i) and (ii) imply that, for any $`\pi `$, $`Area(\pi (P))=Area(\pi (Q))`$ and $`|\pi (P)(z)|+|\pi (P)(z)|=|\pi (Q)(z)|+|\pi (Q)(z)|`$. We use Pick’s formula for $`\pi (P)`$, (see \[GW\], say):

$$|\pi (P)𝕃|=Area\pi (P)+\frac{1}{2}\underset{z\text{ primitive}}{}|\pi (P)(z)|+1.$$

This shows that $`𝒰_P=𝒰_Q`$, indeed.

The necessity of (i) follows from Theorem 1 immediatley, (via the main coefficient of $`E_P`$), and the necessity of (ii) is the content of Theorem 2.∎

###### Corollary 2

Under the conditions of Proposition 3 the lattice width of $`P`$ and $`Q`$, in any direction $`z𝕃^{}`$ are equal.

###### Demonstration Proof

The lattice width, $`w(z,P)`$, of $`P`$ in direction $`z𝕃^{}`$ is, by definition (see \[KL\],\[Lo\]),

$$w(z,P)=\mathrm{max}\{z(xy)x,yP\}.$$

In the plane one can compute the width along the boundary of $`P`$ as well which gives

$$w(z,P)=\frac{1}{2}\underset{e}{}|ze|$$

where the sum is taken over all edges $`e`$ of $`P`$. This proves the corollary.∎

###### Theorem 3

Suppose $`P`$ and $`Q`$ are $`𝕃`$–polygons. Then $`𝒰_P=𝒰_Q`$ if and only if the following two conditions are satisfied:

(i) $`Area(P)=Area(Q)`$,

(ii) there exist $`𝕃`$–polygons $`X`$ and $`Y`$ such that $`P`$ resp. $`Q`$ is a lattice translate of $`X+Y`$ and $`XY`$ (Minkowski addition).

Remark. Here $`X`$ or $`Y`$ is allowed to be a segment or even a single point. In the proof we will ignore translates and simply write $`P=X+Y`$ and $`Q=XY`$.

###### Demonstration Proof

Note that (ii) implies the second condition in Proposition 3. So we only have to show the necessity of (ii).

Assume the contrary and let $`P,Q`$ be a counterexample to the statement with the smallest possible number of edges. We show first that for every (primitive) $`z𝕃^{}`$ at least one of the sets $`P(z),P(z),Q(z),Q(z)`$ is a point.

If this were not the case, all four segments would contain a translated copy of the shortest among them, which, when translated to the origin, is of the form $`[0,t]`$. But then $`P=P^{}+[0,t]`$ and $`Q=Q^{}+[0,t]`$ with $`𝕃`$–polygons $`P^{},Q^{}`$.

We claim that $`P^{},Q^{}`$ satisfy conditions (i) and (ii) of Proposition 3. This is obvious for (ii). For the areas we have that $`AreaPAreaP^{}`$ equals the area of the parallelogram with base $`[0,t]`$ and height $`w(z,P)`$. The same applies to $`AreaQAreaQ^{}`$, but there the height is $`w(z,Q)`$. Then Corollary 2 implies the claim.

So the universal counting functions of $`P^{},Q^{}`$ are identical. But the number of edges of $`P^{}`$ and $`Q^{}`$ is smaller than that of $`P`$ and $`Q`$. Consequently there are polygons $`X^{}`$, $`Y`$ with $`P^{}=X^{}+Y`$, and $`Q^{}=X^{}Y`$. But then, with $`X=X^{}+[0,t]`$, $`P=X+Y`$ and $`Q=XY`$, a contradiction.

Next, we define the polygons $`X,Y`$ by specifying their edges. It is enough to specify the edges of $`X`$ and $`Y`$ that make up the edges $`P(z),P(z),Q(z)`$, $`Q(z)`$ in $`X+Y`$ and $`XY`$. For this end we orient the edges of $`P`$ and $`Q`$ clockwise and set

$$P(z)=[a_1,a_2],P(z)=[b_1,b_2],Q(z)=[c_1,c_2],Q(z)=[d_1,d_2]$$

each of them in clockwise order. Then

$$a_2a_1=\alpha t,b_2b_1=\beta t,c_2c_1=\gamma t,d_2d_1=\delta t$$

where $`t`$ is orthogonal to $`z`$ and $`\alpha ,\gamma 0`$, $`\beta ,\delta 0`$ and one of them equals $`0`$. Moreover, by condition (ii) of Proposition 3, $`\alpha \beta =\gamma \delta `$.

Here is the definition of the corresponding edges, $`x,y`$ of $`X,Y`$:

$`x=\alpha t,y=\beta t\text{ if}`$ $`\delta =0,`$   
$`x=\beta t,y=\alpha t\text{ if}`$ $`\gamma =0,`$   
$`x=\gamma t,y=\delta t\text{ if}`$ $`\beta =0,`$   
$`x=\delta t,y=\gamma t\text{ if}`$ $`\alpha =0.`$   
With this definition, $`X+Y`$ and $`XY`$ will have exactly the edges needed. We have to check yet that the sum of the $`X`$ edges (and the $`Y`$ edges) is zero, otherwise they won’t make up a polygon. But $`(x+y)=0`$ since this is the sum of the edges of $`P`$, and $`(xy)=0`$ since this is the sum of the edges of $`Q`$. Summing these two equations gives $`x=0`$, subtracting them yields $`y=0`$. ∎

4. An example and a question

Let $`X`$, resp. $`Y`$ be the triangle with vertices $`(0,0),(2,0),(1,1)`$, and $`(0,0),(1,1),(0,3)`$. As it turns out the areas of $`P=X+Y`$ and $`Q=XY`$ are equal. So Theorem 3 applies: $`𝒰_P=𝒰_Q`$. At the same time, $`P`$ and $`Q`$ are not congruent as $`P`$ has six vertices while $`Q`$ has only five.

However, it is still possible that polygons with the same universal counting function are equidecomposable. Precisely, $`P_1,\mathrm{},P_m`$ is said to be a subdivision of $`P`$ if the $`P_i`$ are $`𝕃`$–polygons with pairwise relative interior, their union is $`P`$, and the intersection of the closure of any two of them is a face of both. Recall from section 1 the group $`𝒢_{tr}`$ generated by $`𝕃`$–translations and the reflection with respect to the origin. Two $`𝕃`$–polygons $`P,Q`$ are called $`𝒢_{tr}`$–equidecomposable if there are subdivisions $`P=P_1\mathrm{}P_m`$ and $`Q=Q_1\mathrm{}Q_m`$ such that each $`P_i`$ is a translate, or the reflection of a translate of $`Q_i`$ with the extra condition that $`P_i`$ is contained in the boundary of $`P`$ if and only if $`Q_i`$ is contained in the boundary of $`Q`$.

We finish the paper with a question which has connections to a theorem of the late Peter Greenberg \[Gr\]. Assume $`P`$ and $`Q`$ have the same universal counting function. Is it true then that they are $`𝒢_{tr}`$–equidecomposable? In the example above, as in many other examples, they are.

References

\[BK\] U. Betke, M. Kneser, Zerlegungen und Bewertungen von Gitterpolytopen, J. Reine ang. Math. 358 (1985), 202–208.

\[Eh\] E. Ehrhart, Polinomes arithmétiques et métode des polyédres en combinatoire, Birkhauser, 1977.

\[Gr\] P. Greenberg, Piecewise $`SL_2`$–geometry, Transactions of the AMS, 335 (1993), 705–720.

\[GW\] P. Gritzmann, J. Wills, Lattice points, in: Handbook of convex geometry, ed. P. M. Gruber, J. Wills, North Holland, Amsterdam, 1988.

\[KL\] R. Kannan, L. Lovász, Covering minima and lattice point free convex bodies, Annals of Math. 128 (1988), 577–602.

\[Ka\] J–M. Kantor, Triangulations of integral polytopes and Ehrhart polynomials, Beiträge zur Algebra und Geometrie, 39 (1998), 205–218.

\[Lo\] L. Lovász, An algorithmic theory of numbers, graphs and convexity, Regional Conference Series in Applied Mathematics 50, 1986.

\[McM\] P. McMullen, Valuations and dissections, in: Handbook of convex geometry, ed. P. M. Gruber, J. Wills, North Holland, Amsterdam, 1988.