A lemma on polyhedral sets of lattice points

Bruno Haible Mathematisches Institut II Universität Karlsruhe D – W 7500 Karlsruhe 1 (until 30 June 1993) D – 76131 Karlsruhe (from 1st July 1993 on)

                     Email: <haible@ma2s2.mathematik.uni-karlsruhe.de>

4 May 1993

This paper proves a lemma on decompositions of polyhedral sets of lattice points. It is a summary of the Lemma in section 4.1 of [1].

1. Results

Lemma 1: Let A ∈ ℤ^{m×n}, b ∈ ℤ^{m} and > = ; < be a set of m equality or inequality signs. Then the set {x ∈ IN_{0}^{n} : Ax > = ; < b} can

be written as disjoint union of finitely many sets of type u + V · IN_{0}^{k} with u ∈ IN_{0}^{n} and V ∈ ℤ^{n×k}, rank V = k.

Proof: For u ∈ IN_{0}^{n} and V ∈ ℤ^{n×k} we call the set u + V · IN_{0}^{k} = ⋃_{z∈IN_{0}^{k}} {u + V · z} a lattice cone if this union is

disjoint, i.e. if rank V = k. Every finite disjoint union of lattice cones is called a lattice cone union. Case 1: The case of one equality. We prove that {x ∈ IN_{0}^{n} : Ax = b} with A ∈ ℤ^{1×n} and b ∈ ℤ is a lattice cone union. Write A = (a_{1}, …, a_{n}). Case 1a: all a_{i} ∈ {−1, 0, 1}. Let r denote the number of i with a_{i} = 1 and s denote the number of i with a_{i} = −1. We prove the claim by induction on r + s. In the case s = 0, we have an equation x_{1} + ⋯ + x_{r} = b, which leads to a finite disjoint union of copies of IN_{0}^{n−r} (consider the cases b < 0; b = 0; b > 0, r = 0; b > 0, r > 0 separately). The case r = 0 is similar. In the case r ≥ 1, s ≥ 1 we may assume a_{1} = 1 and a_{2} = −1. We split the set {x ∈ IN_{0}^{n} : Ax = b} according to whether x_{1} ≥ x_{2} or x_{1} < x_{2} holds. To get {x ∈ IN_{0}^{n} : Ax = b, x_{1} ≥ x_{2}}, one has to multiply

{( y ; x_{2} ; ⋮ ; x_{n} ) ∈ IN_{0}^{n} : y + a_{3}x_{3} + ⋯ + a_{n}x_{n} = b} (which is a lattice cone union by induction hypothesis) by

( \begin{matrix}1 & 1 & & & & 0 \\ & 1 \\ & & . & . & . \\ 0 & & & & & 1 \end{matrix} ) ∈ GL_{n}(ℤ). The set \{x ∈ IN_{0}^{n} : Ax = b, x_{1} + 1 ≤ x_{2}\} is handled in a similar way.

{x ∈ IN_{0}^{n} : Ax = b} is the disjoint union of both. Case 1b: the general case A ∈ ℤ^{1×n}, A ≠ 0.

Let g be the least common multiple of those |a_{i}| that are non-zero. Put d_{i} = 1 if a_{i} = 0 and d_{i} = \frac{g}{|a_{i}|}

otherwise. We have d_{i} ∈ IN and a_{i} · d_{i} = g · sgn a_{i} for i = 1, …, n. We split the set {x ∈ IN_{0}^{n} : Ax = b} according to x_{i} mod d_{i}. For r = (r_{1}, …, r_{n}), 0 ≤ r_{1} < d_{1}, …,

0 ≤ r_{n} < d_{n} let X_{r} = \{x ∈ IN_{0}^{n} : Ax = b, ∀i : x_{i} ≡ r_{i} mod d_{i}\}. Then X_{r} = ( \begin{matrix}d_{1} & & & & 0 \\ & . & . & . \\ 0 & & & & d_{n} \end{matrix} ) · Y_{r} + ( r_{1} ; ⋮ ; r_{n} )

with Y_{r} = \{y ∈ IN_{0}^{n} : (sgn a_{1})y_{1} + ⋯ (sgn a_{n})y_{n} = \frac{b − a_{1}r_{1} − ⋯ − a_{n}r_{n}}{g} \} if g divides b − a_{1}r_{1} − ⋯ − a_{n}r_{n}

and Y_{r} = O / otherwise. Thus X_{r} is a lattice cone union, and so is X, the disjoint union of all these X_{r}. Case 2: The case of one inequality. Case 2a: Let L = {x ∈ IN_{0}^{n} : Ax ≤ b}. Introduce an auxiliary variable y and consider

M = {( x_{1} ; ⋮ ; x_{n} ; y ) ∈ IN_{0}^{n+1} : a_{1}x_{1} + ⋯ a_{n}x_{n} + y = b}.

M is a lattice cone union by case 1, and since the projection \{ \begin{matrix}M & → & L \\ ( \begin{matrix}x \\ y \end{matrix} ) & ↦ & x \end{matrix}\} is bijective, L is a lattice cone

union. Case 2b: {x ∈ IN_{0}^{n} : Ax < b} = {x ∈ IN_{0}^{n} : Ax ≤ b − 1}. Case 2c: {x ∈ IN_{0}^{n} : Ax ≥ b} = {x ∈ IN_{0}^{n} : (−A)x ≤ −b}. Case 2d: {x ∈ IN_{0}^{n} : Ax > b} = {x ∈ IN_{0}^{n} : Ax ≥ b + 1}. Case 3: The general case of several equations and inequalities. Proceed by induction on m, the number of equality/inequality signs. m = 0 is trivial: IN_{0}^{n}. Assume we have proven {x ∈ IN_{0}^{n} : Ax > = ; < b} to be a

disjoint union ⋃_{i} (u_{i} + V_{i} · IN_{0}^{k}) (with k depending on i), and we add one more equality/inequality A′x > = ; < b′.

What we get is ⋃_{i} (u_{i} + V_{i} · {z ∈ IN_{0}^{k} : A′V_{i}z > = ; < b′ − A′u_{i}}) which is a lattice cone union by cases 1 and 2:

⋃_{i} (u_{i} + V_{i} · ⋃_{j} (u_{i,j} + V_{i,j} · IN_{0}^{k_{i,j}})) = ⋃_{i} ⋃_{j} (u_{i} + V_{i}u_{i,j} + V_{i}V_{i,j} · IN_{0}^{k_{i,j}}). q.e.d.

Corollary 2: Let R be an integral domain and P (x) ∈ R[x_{1}, …, x_{n}] a polynomial. Then

F (Z) = ∑_{{x∈IN_{0}^{n} \atop Ax > = ; < b}} P (x)Z^{x}

is a rational function^{1}: F ∈ R(Z_{1}, …, Z_{n}). Proof: Case 1: The case F (Z) = ∑_{x∈IN_{0}^{n}} P (x)Z^{x}. This is proved to be rational by considering the derivatives of

∑_{x∈IN_{0}^{n}} Z^{x} = ∏_{i=1}^{n} \frac{1}{1 − Z_{i}} ,

namely

∑_{x∈IN_{0}^{n}} x_{1} ⋯ (x_{1} − c_{1} + 1) ⋯ x_{n} ⋯ (x_{n} − c_{n} + 1)Z^{x} = (\frac{∂}{∂Z_{1}} )^{c_{1}} ⋯ (\frac{∂}{∂Z_{n}} )^{c_{n}} ∏_{i=1}^{n} \frac{1}{1 − Z_{i}} = ∏_{i=1}^{n} \frac{1}{(1 − Z_{i})^{c_{i}+1}} .

1 ^{1}) R(Z_{1}, …, Z_{n}) denotes the quotient field of the polynomial ring R[Z_{1}, …, Z_{n}].

Case 2: The general case. By the lemma, F (Z) can be written as a finite sum of functions of the form

∑_{x∈IN_{0}^{k}} P (u + V · x)Z^{u+V ·x} = Z^{u} ∑_{x∈IN_{0}^{k}} Q(x)Z^{V ·x} = Z^{u}G(Z_{1}^{v_{11}} ⋯ Z_{n}^{v_{n1}}, …, Z_{1}^{v_{1k}} ⋯ Z_{n}^{v_{nk}})

where Q(x) := P (u + V · x) is a polynomial and G(T) = ∑_{x∈IN_{0}^{k}} Q(x)T^{x} is in R(T_{1}, …, T_{k}) by case 1. Since

V has rank k, the substitution T_{1} = Z_{1}^{v_{11}} ⋯ Z_{n}^{v_{n1}}, …, T_{k} = Z_{1}^{v_{1k}} ⋯ Z_{n}^{v_{nk}} gives rise to an injective ring homomorphism R[T_{1}, …, T_{k}] → R(Z_{1}, …, Z_{n}) and thus to a field homomorphism R(T_{1}, …, T_{k}) → R(Z_{1}, …, Z_{n}). This implies that F (Z) is rational. q.e.d.

2. Reference

[1] Bruno Haible: D-finite Potenzreihen in mehreren Variablen. Diplomarbeit, Universität Karlsruhe, June 1989.