PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 99(113) (2016), 31–42 DOI: 10.2298/PIM1613031M

SIGNED POLYOMINO TILINGS BY n-IN-LINE POLYOMINOES AND GRÖBNER BASES

Manuela Muzika Dizdarević, Marinko Timotijević, and Rade T. Živaljević

Abstract. Conway and Lagarias observed that a triangular region T (m) in a hexagonal lattice admits a signed tiling by three-in-line polyominoes (tribones) if and only if m ∈ {9d − 1, 9d}_{d∈ℕ} . We apply the theory of Gröbner bases over integers to show that T (m) admits a signed tiling by n-in-line polyominoes (n-bones) if and only if

m ∈ {dn^{2} − 1, dn^{2}}_{d∈ℕ} .

Explicit description of the Gröbner basis allows us to calculate the ‘Gröbner discrete volume’ of a lattice region by applying the division algorithm to its ‘Newton polynomial’. Among immediate consequences is a description of the tile homology group for the n-in-line polyomino.

1. Introduction

An n-bone is by definition an n-in-line polyomino (polyhex) in a hexagonal lattice. For example a 3-bone is the same as the tribone in the sense of [16]. One initial objective is to determine when a triangular region T (m) in a hexagonal lattice admits a signed tiling by n-bones.

By a theorem of Conway and Lagarias [6, Theorem 1.4.], T (m) admits a signed tiling by 3-bones if and only if m = 9d or m = 9d − 1 for some integer d ⩾ 1, the case m = 8 is exhibited in Figure 1. Our central result is Theorem 7.1, which claims that T (m) admits a signed tiling by n-bones if and only if m = dn^{2} or m = dn^{2} − 1 for some integer d ⩾ 1.

The Gröbner basis approach to signed polyomino tilings was originally proposed by Bodini and Nouvel [5], see also [11] for an application to tilings with symmetries. The knowledge of the Gröbner basis (Theorem 5.1) offers a deeper insight into the (signed) tiling problem and provides a powerful tool for analyzing general behavior

2010 Mathematics Subject Classification: 52C20; 13P10. Key words and phrases: signed polyomino tilings, Gröbner bases. R. Živaljević was supported by the Grants 174020 and 174034 of the Ministry of Education,

Science and Technological Development of the Republic of Serbia.

Communicated by Žarko Mijajlović.

Figure 1. A signed tiling of a triangular region by 3-bones.

and selected particular cases. It is well adopted to other methods of lattice geometry and we illustrate this by examples involving Brion’s theorem (Example 8.2).

Computing the Gröbner basis of a tiling problem yields, as a byproduct, complete information about the associated tile homology group [6, 14]. In general computing homology classes by a ‘division algorithm’ may offer an interesting new computational paradigm, which deserves further exploration.

2. Gröbner bases

The notion of a strong Gröbner base [1, 12] (called a D-Gröbner base in [4]) allows us to apply the Gröbner basis theory to polynomials with integer coefficients. Here is a brief outline of some basic definitions and theorems with pointers to some of the key references.

A term is a product t = cx^{α} where c is the coefficient and x^{α} = x_{1}^{α_{1}} ⋯ x_{k}^{α_{k}} is the associated monomial (power product). For a given polynomial f ∈ ℤ[x_{1}, x_{2}, …, x_{k}] the associated remainder on division by a Gröbner basis G is \overline{f} ^{G} and f reduces to zero f −→^{G} 0 if \overline{f} ^{G} = 0. lm(f) and lc(f) are respectively the leading monomial and the leading coefficient with respect to the chosen term order ⪯. We write lcm(a, b) and gcd(a, b) respectively for the least common multiple and the greatest common divisor of a and b.

For other basic notions of Gröbner basis theory (over integers), such as Spolynomial, standard representation etc., the reader is referred to [1, 4, 12] (see also [7, 8, 15] for related results for coefficients in a field).

2.1. Gröbner bases over principal ideal domains. Let Λ = R[x_{1}, …, x_{k}] be the ring of polynomials with coefficients in a principal ideal domain R. For a given ideal I ⊂ Λ the associated strong Gröbner basis, called also the D bases in [4], may be introduced as follows (see [1, p. 251] and [4, p. 455]).

Definition 2.1. A finite set G ⊂ I is a strong Gröbner basis of I (with respect to the chosen term order ⪯) if for each f ∈ I ∖ {0} there exists g ∈ G such that the leading term of f is divisible by the leading term of g, lt(g) | lt(f), meaning that lt(f) = t lt(g) for a term t.

The following theorem provides a useful criterion for testing whether a finite set of polynomials is a Gröbner basis of the ideal generated by them, see [4, Chapter 10, Corollary 10.12] and [13, Theorem 2.1.].

Theorem 2.1. Let G be a finite collection of nonzero polynomials which generate an ideal I_{G}. Suppose that,

(1) For each pair g_{1}, g_{2} ∈ G there exists an h ∈ G such that,

lm(h) | lcm(lm(g_{1}), lm(g_{2})) and lc(h) | gcd(lc(g_{1}), lc(g_{2}))

(2) For each pair g_{1}, g_{2} ∈ G the associated S-polynomial reduces to zero,

S(g_{1}, g_{2}) −→^{G} 0.

Then G is a strong Gröbner basis of I_{G}.

2.2. Gröbner bases over Euclidean domains. The general theory is further simplified if one works with Euclidean domains. Aside from standard references [1, 4], a selfcontained account can be found in [12]. In the case of integers, one usually chooses the linear ordering,

(2.1)  ⋯ 0 < +1 < −1 < +2 < −2 < +3 < −3 < ⋯

which allows us to define unambiguously remainders, S-polynomials etc. For example following (2.1) the reduction of 8 mod 5 is −2 rather than +3. Caveat: We find it convenient in Section 6 to stick to positive remainders and write that +3 is, rather than −2, the remainder of 8 on division by 5. In other words we use the following term order for coefficients,

(2.2)  ⋯ 0 < +1 < +2 < +3 < ⋯< −1 < −2 < −3 < · · ·.

Example 2.1. In agreement with (2.1) many standard computer algebra packages (including Wolfram Mathematica 9.0) would yield −x−y −1 as the remainder of T (6) (Section 4) on division by GBI_{3}. In Section 6 we would (following (2.2)) reduce this polynomial further by the element g_{3}(3) = 3T (2) = 3(x+y+1) (Section 5) and obtain the polynomial 2(x + y + 1).

3. From polyominoes to polynomials

Each polyomino P ⊂ ℤ^{2} is associated to the corresponding Laurent–Newton polynomial f_{P} := ∑ _{(p,q)∈P} x^{p}y^{q} ∈ ℤ[x, y; x^{−1} , y^{−1} ]. For example the shaded tribone P in Figure 1 is associated to the trinomial x^{2}y^{2} + x^{3}y^{2} + x^{4}y^{2}. More generally if P is a (not necessarily finite) subset of ℤ^{d}, then the associated ‘integer-point transform’ [3, p. 60] is the formal power series f_{P} := ∑ _{α∈P} x^{α} ∈ ℤ[[x_{1}^{±1} , …, x_{d}^{±1} ]].

From here on we tacitly assume that all polyominoes are subsets of ℕ^{2} (or ℕ^{d} in the general case). As a consequence, the associated Laurent–Newton polynomial has only monomials with nonnegative exponents, f_{P} ∈ ℤ[x, y] (respectively f_{P} ∈ ℤ[x_{1}, …, x_{d}]).

Proposition 3.1. A polyomino P admits a signed tiling by translates of prototiles P_{1}, P_{2}, …, P_{k} if and only if for a monomial x^{α} = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} with a nonnegative exponent α ∈ ℕ^{d}, the polynomial x^{α} f_{P} is in the ideal generated by polynomials f_{P_{1}} , …, f_{P_{k}} ,

x^{α} f_{P} ∈ ⟨f_{P_{1}} , f_{P_{2}} , …, f_{P_{k}} ⟩.
Proof. Let J ⊂ ℤ[x_{1}^{±1} , …, x_{d}^{±1} ] be the extension of the ideal
I = ⟨f_{P_{1}} , f_{P_{2}} , …, f_{P_{k}} ⟩ ⊂ ℤ[x_{1}, …, x_{d}]

in the ring of Laurent polynomials with coefficients in ℤ. P admits a signed tiling by translates of prototiles P_{1}, P_{2}, …, P_{k} if and only if f_{P} ∈ J. The proposition is an immediate consequence of the relation

(3.1)  J = ⋃_{x^{α} ∈ℕ^{d}} x^{−α} ⟨f_{P_{1}} , f_{P_{2}} , …, f_{P_{k}} ⟩.

Note that in union (3.1) is not changed if the exponents of monomials x^{α} range in a set T ⊂ ℕ^{d} which is cofinal in ℕ^{d} in the sense that for each α ∈ ℕ^{d} there exists a β ∈ T such that α ⩽ β. □

The following proposition is essentially a restatement of the definition of the tile homology group, as introduced in [6] and [14, Definition 2.4.].

Proposition 3.2. Given a system P = {P_{1}, P_{2}, …, P_{k}} of prototiles, the associated tile homology group H(P) is isomorphic to the group ℤ[x_{1}^{±1} , …, x_{d}^{±1} ]/J where J is the ideal described in equation (3.1).

4. The n-bone ideal I_{n}

Let I_{n} = ⟨b_{1}(n), b_{2}(n), b_{3}(n)⟩ ⊂ ℤ[x, y] be the ideal generated by polynomials,

b_{1}(n) = 1+x+⋯ +x^{n−1} , b_{2}(n) = 1+y+⋯ +y^{n−1} , b_{3}(n) = x^{n−1} +x^{n−2} y+⋯ +y^{n−1}

These polynomials correspond to three types of n-in-line polyominoes in a hexagonal lattice.

We denote by T (m) the ‘integer-point transform’ [3, p. 60] (Laurent–Newton polynomial) of a triangular region with the side-length equal to m,

T (m) = ∑_{\begin{matrix}0⩽i,j⩽m−1 \\ i+j⩽m−1 \end{matrix}} x^{i}y^{j} .

5. Gröbner basis for the n-bone ideal

Let GBI_{n} = {g_{1}(n), g_{2}(n), g_{3}(n), g_{4}(n)} be the following set of polynomials,

g_{1}(n) = b_{1}(n), g_{2}(n) = b_{2}(n), g_{3}(n) = nT (n − 1), g_{4}(n) = b_{3}(n) − b_{1}(n) − b_{2}(n).

Lemma 5.1. The leading terms of polynomials g_{1}, g_{2}, g_{3}, g_{4} with respect to the lexicographical term order are the following,

(5.1) lt(g_{1}(n)) = x^{n−1} , lt(g_{2}(n)) = y^{n−1} , lt(g_{3}(n)) = nx^{n−2} , lt(g_{4}(n)) = x^{n−2} y.

The relations listed in Proposition 5.1 will be needed in the sequel. The first equality is trivial, while the rest follow from an iterated application of the identity a^{d} − b^{d} = a^{d−1} + a^{d−2} b + ⋯+ b^{d−1} for suitable a and b.

Proposition 5.1. We have

T (n)= T (n − 1) + b_{3}(n),
(x − 1)T (n − 1) = b_{3}(n) − b_{2}(n),
(x − y)T (n − 1) = b_{1}(n) − b_{2}(n),
(y − 1)g_{1}(n) + (y − x)g_{4}(n) = (x − 1)g_{2}(n).

Proposition 5.2. The set GBI_{n} is a basis of the ideal I_{n}.

Proof. Let ⟨GBI_{n}⟩ be the ideal generated by GBI_{n}. It is obvious that

I_{n} = ⟨g_{1}(n), g_{2}(n), g_{4}(n)⟩ ⊆ ⟨GBI_{n}⟩

so it is sufficient to show that g_{3}(n) ∈ I_{n}. As a consequence of the second identity in Proposition 5.1, we have

(x − 1)T (n − 1), (x^{2} − 1)T (n − 1), …, (x^{n−1} − 1)T (n − 1) ∈ I_{n}

By suming these polynomials, we obtain b_{1}(n)T (n − 1) − nT (n − 1) ∈ I_{n} and g_{3} = nT (n − 1) ∈ I_{n}, which is the desired conclusion. □

Theorem 5.1. The set of polynomials GBI_{n} is a strong Gröbner basis (over the base ring ℤ) of the ideal I_{n}, n ⩾ 2, with respect to lexicographic term order.

Proof. The case n = 2 is elementary, so we assume that n ⩾ 3. By Proposition 5.2, the set GBI_{n} is a basis of the ideal I_{n}. In order to show that this is indeed a strong Gröbner basis of the ideal I_{n} ⊂ ℤ[x, y], we apply the ℤ-version of the Buchberger criterion.

Following [12, Theorem 2], it is sufficient to show that for every pair of polynomials g_{i}(n), g_{j} (n) ∈ GBI_{n}, their S-polynomial reduces to 0 by the set GBI_{n}. Equivalently, one can use Theorem 2.1 by observing that condition (1) is (in light of Lemma 5.1) readily satisfied.

Since the leading monomials of the polynomials g_{1}(n), g_{2}(n) and g_{2}(n), g_{3}(n) are pairwise coprime (Lemma 5.1) and (at least) one of the leading coefficients is equal to 1, we conclude from [12, Theorem 3] that

S(g_{1}(n), g_{2}(n)) −−−−⟶^{GBI_{n}} 0 and S(g_{2}(n), g_{3}(n)) −−−−⟶^{GBI_{n}} 0.

Let us consider the polynomials g_{1}(n) and g_{4}(n). By Lemma 5.1, we have

S(g_{1}(n), g_{4}(n)) = yg_{1}(n) − xg_{4}(n).

Since

lt(S(g_{1}(n), g_{4}(n))) = lt(x^{n−1} + x^{n−2} y − x^{n−2} + ⋯) = x^{n−1}

we can reduce this polynomial by g_{1}(n). The reduction leads to the polynomial

S(g_{1}(n), g_{4}(n)) − g_{1}(n) = yg_{1}(n) − xg_{4}(n) − g_{1}(n)

which has the leading term

lt(S(g_{1}(n), g_{4}(n)) − g_{1}(n)) = lt(−x^{n−2} y^{2} + x^{n−2} y − ⋯) = −x^{n−2} y^{2}

and which, in light of Lemma 5.1, can be reduced by g_{4}(n). This reduction leads to the polynomial

S(g_{1}(n), g_{4}(n)) − g_{1}(n) + yg_{4}(n) = (y − 1)g_{1}(n) + (y − x)g_{4}(n).

By using the last equality in Proposition 5.1, we finally get a strong representation of S(g_{1}(n), g_{4}(n)) by the set GBI_{n},

S(g_{1}(n), g_{4}(n)) = g_{1}(n) − yg_{4}(n) + (x − 1)g_{2}(n).

The reducibility of polynomials S(g_{1}(n), g_{3}(n)) and S(g_{3}(n), g_{4}(n)) can be established in a similar manner.

By Lemma 5.1, S(g_{1}(n), g_{3}(n))= ng_{1}(n)−xg_{3}(n) has the leading term −nx^{n−2} y. Consequently it can be reduced by the polynomial g_{4}(n) and we focus our attention to the polynomial, ng_{1}(n) − xg_{3}(n) + ng_{4}(n). It is reducible to zero since, in light of the second equality in Proposition 5.1, it is equal to −ng_{3}(n). In particular it has the strong representation in terms of the basis GBI_{n},

S(g_{1}(n), g_{3}(n)) = −ng_{4}(n) − g_{3}(n).

A similar calculation shows that S(g_{3}(n), g_{4}(n)) = g_{3}(n) + ng_{2}(n) is a strong representation of S(g_{3}(n), g_{4}(n)).

Together with the case of the S-polynomial S(g_{2}(n), g_{4}(n)), which is separately treated in Lemma 5.2, this concludes the proof. □

Figure 2. Reduction of S(g_{2}(n), g_{4}(n)).

Lemma 5.2. The S-polynomial S(g_{2}(n), g_{4}(n)) can be reduced to 0 by GBI_{n}.

Proof. By Lemma 5.1, we have S(g_{2}(n), g_{4}(n)) = x^{n−2} g_{2}(n) − y^{n−2} g_{4}(n). The terms x^{n−2} y and −x^{n−2} are the leading two terms of the polynomial g_{4}(n) and they are the only terms in the lexicographically leading column {x^{n−2} y^{i}}_{i⩾0} (Figure 2). This observation indicates that one should begin with the reduction of the S-polynomial S(g_{2}(n), x^{n−2} y −x^{n−2} ) = x^{n−2} S(b_{2}(n), y −1). From the identity,

(5.2)  b_{2}(n) − n = ∑_{j=0}^{n−1} (y^{j} − 1) = (y − 1)B_{2}(n)

where B_{2}(n) = b_{2}(n − 1) + b_{2}(n − 2) + ⋯+ b_{2}(1), we observe that S(g_{2}(n), g_{4}(n)) can be reduced to the polynomial x^{n−2} g_{2}(n) − B_{2}(n)g_{4}, which has the monomial nx^{n−2} as the leading term. This is precisely the leading term of the polynomial g_{3}(n) = nT (n − 1), so we turn our attention to the polynomial

(5.3)  x^{n−2} g_{2}(n) − B_{2}(n)g_{4}(n) − g_{3}(n).

Since by definition b_{3}(n) − b_{1}(n) = ∑ _{k=1}^{n−1} x^{n−k−1} (y^{k} − 1), we observe (in light of (5.2)) that,

B_{2}(n)[b_{3}(n)−b_{1}(n)] = [ ∑_{k=1}^{n−1} x^{n−k−1} ( ∑_{j=0}^{k−1} y^{j})][b_{2}(n)−n] = T (n−1)b_{2}(n)−nT (n−1).

It follows that B_{2}(n)g_{4} + g_{3}(n) = [T (n − 1) − B_{2}(n)]b_{2}(n) which implies that the polynomial (5.3) can be reduced by g_{2}(n) = b_{2}(n) with zero remainder. □

6. Evaluation of remainders

Our objective in this section is to calculate the remainder \overline{T (n)}^{GBI^{n}} of T (n) on division by the Gröbner basis GBI_{n}.

Lemma 6.1. Suppose that

(6.1)  p(x) = q(x)(x^{n} − 1) + r(x)

is the equality arising from the division of a polynomial p(x) ∈ ℤ[x] by x^{n} − 1 where q(x) is the quotient and r(x) the remainder. If P (x, y) = \frac{p(x)−p(y)}{x−y} and

R(x, y) = \frac{r(x)−r(y)}{x−y} , then

\overline{P (x, y)}^{GBI^{n}} = \overline{R(x, y)}^{GBI^{n}} .

Moreover, if R(x, y) cannot be further reduced by the Gröbner basis GBI_{n}, then the remainder of P (x, y) on division by GBI_{n} is,

\overline{P (x, y)}^{GBI^{n}} = \overline{R(x, y)}^{GBI^{n}} = R(x, y) = \frac{r(x) − r(y)}{x − y} .

Proof. From (6.1) we deduce the equality

\frac{p(x) − p(y)}{x − y} = \frac{q(x) − q(y)}{x − y} (x^{n} − 1) + q(y)\frac{x^{n} − y^{n}}{x − y} + \frac{r(x) − r(y)}{x − y} .

Both x^{n} −1 = (x−1)b_{1}(n) and \frac{x^{n} −y^{n}}{x−y} = b_{3}(n) are in the ideal I_{n}, so \overline{P (x, y)}^{GBI^{n}} =

\overline{R(x, y)}^{GBI^{n}} . The second part of the lemma is an immediate consequence. □

Lemma 6.2. Let b_{3}(m) = x^{m−1} +x^{m−2} y+⋯ +y^{m−1} and assume by convention that b_{3}(0) = 0. Then

(6.2)  \overline{b_{3}(m)}^{GBI^{n}} = b_{3}(r_{m})

where r_{m} = r_{m}^{n} = m − ⌊m/n⌋n is the remainder of the division of m by n.

Proof. Observe that b_{3}(m) = P (x, y) = \frac{p(x)−p(y)}{x−y} for p(x) = x^{m}. For this choice of p(x), the equation corresponding to (6.1) is

x^{m} = (x^{m−n} + x^{m−2n} + ⋯+ x^{r_{m}} )(x^{n} − 1) + x^{r_{m}} .

Since lt(R(x, y)) = lt(b_{3}(r_{m})) = x^{r_{m} −1} is not divisible by any of the leading terms of the Gröbner basis GBI_{n} listed in (5.1), we note that \overline{b_{3}(r_{m})}^{GBI^{n}} = b_{3}(r_{m}) and the result follows from the second half of Lemma 6.1. □

Since T (m) = T (m − 1) + b_{3}(m), Lemma 6.2 may be used for an inductive evaluation of \overline{T (m)}^{GBI^{n}} . In the following proposition we write p ≡_{I_{n}} q (congruence mod I_{n}) as an abbreviation for p − q ∈ I_{n}. As before r = r_{m} = r_{m}^{n} = m − ⌊m/n⌋n.

Remark 6.1. Before reading the proof of Proposition 6.1, it is quite instructive to check relation (6.5) for some small values of n and m.

Proposition 6.1. For each integer n ⩾ 1 the sequence of polynomials α_{m} = α_{m}^{n} = α_{m}^{n}(x, y) = \overline{T (m)}^{GBI^{n}} is periodic with the period n^{2}. For 1 ⩽ m ⩽ n^{2} − 2, T (m) = ∑ _{k=1}^{m} b_{3}(k) and

(6.3)  \overline{T (m)}^{GBI^{N}} = ∑_{k=1}^{m} b_{3}(r_{k}^{n}) ≠ 0.

For m ∈ {n^{2} − 1, n^{2}},

(6.4)  \overline{T (m)}^{GBI^{N}} = 0.

Moreover if m = pn + q where 0 ⩽ p ⩽ n − 1 and 1 ⩽ q ⩽ n, then

(6.5)  \overline{T (m)}^{GBI^{N}} ≡_{I_{n}} pT (n − 1) + T (q).

Proof. To establish the periodicity of the sequence α_{m} = α_{m}^{n} = \overline{T (m)}^{GBI^{n}} , it is sufficient to establish equalities (6.3) and (6.4). Indeed, assume that (6.3) and (6.4) are true and that α_{m} is periodic with the period n^{2} in the interval [1, jn^{2}] for some integer j ⩾ 1. Note that for each d ∈ [jn^{2} + 1, (j + 1)n^{2}],

α_{d} = \overline{T (d)}^{GBI^{n}} = \overline{A + B} ^{GBI^{n}}

where A = T (jn^{2}) and B = ∑ _{k=jn^{2} +1}^{d} b_{3}(k). Since by the inductive hypothesis

\overline{A}^{GBI^{n}} = 0, we note that

(6.6)  α_{d} = \overline{B}^{GBI^{n}} ≡_{I_{n}} ∑_{k=jn^{2} +1}^{d} b_{3}(r_{k}) ≡_{I_{n}} ∑_{k=1}^{d′} b_{3}(r_{k})

where d′ = d − ⌊d/n^{2}⌋n^{2}. Following (6.3), the right-hand sum in (6.6) is a reduced polynomial, hence α_{d} = ∑ _{k=1}^{d′} b_{3}(r_{k}) which proves that the sequence α_{m} repeats the same pattern in the interval [jn^{2} + 1, (j + 1)n^{2}].

Since T (m) = ∑ _{k=1}^{m} b_{3}(k), in light of the equality (6.2), we note that

α_{m} = \overline{T (m)}^{GBI^{n}} = \overline{∑_{k=1}^{m} b_{3}(r_{k}^{n})}^{GBI^{n}} .

Equality (6.3) claims more than that, it says that the right-hand side of (6.3) is reduced with respect to the Gröbner basis GBI_{n}. Indeed, for m ⩽ n^{2} − 2, if Cx^{p}y^{q} is the leading term of ∑ _{k=1}^{m} b_{3}(r_{k}^{n}), then either p < n − 2 or C ⩽ n − 1.

A similar analysis shows that T (n^{2} − 1) ≡_{I_{n}} nT (n − 1) = g_{3}(n) ∈ I_{n}. This together with the fact b_{3}(n^{2}) ∈ I_{n} establishes equality (6.4). Finally (6.5) is just a restatement of (6.3) and (6.4) suitable for applications. □

7. Signed tilings by n-bones

Theorem 7.1. A triangular region T (m) in a hexagonal lattice admits a signed tiling by n-in-line polyominoes (n-bones) if and only if

(7.1)  m ≡ −1 (mod n^{2})  or  m ≡ 0 (mod n^{2}).

Proof. By Proposition 3.1, it is sufficient to check if at least one of the polynomials,

T (m), x^{n}y^{n}T (m), x^{2n} y^{2n} T (m), x^{3n} y^{3n} T (m), …

is in the ideal I_{n} generated by n-bones. Since x^{kn} y^{kn} − 1 ∈ I_{n} for each k, the triangular region T (m) admits a signed tiling by n-in-line polyominoes if and only if T (m) ∈ I_{n}.

By Proposition 6.1 this happens if and only if the condition (7.1) is satisfied. This observation completes the proof of the theorem. □

8. Tile homology groups and Brion’s theorem

For tile homology groups the reader is referred to [6] and [14] (see also Proposition 3.2). In this section we show how one can read off the tile homology group from the Gröbner basis. We begin with the definition of ‘standard’ d-dimensional polyominoes.

Definition 8.1. We say that a polyomino P = {P_{1}, …, P_{k}} in ℕ^{d} is standard if,

(8.1)  ℤ[x_{1}^{±1} , …, x_{d}^{±1} ] = ℤ[x_{1}, …, x_{d}] + J_{P}

where J = J_{P} is the ideal described in (3.1).

Example 8.1. Condition (8.1) says that each Laurent monomial x^{α} is congruent modulo J_{P} to a polynomial p ∈ ℤ[x_{1}, …, x_{d}]. In particular the n-bone polyomino is standard since each x^{α} can be (mod J_{P}) replaced by negative sums of monomials x^{β} where β are positioned to the right of α (alternatively above α).

Proposition 8.1. The tile homology group H(P) (Proposition 3.2) of a standard polyomino (Definition 8.1) with prototiles P and the associated ideal I_{P} ⊂ ℤ[x_{1}, …, x_{d}] = ℤ[\overline{x}] can be computed as the direct limit,

(8.2)  lim_{−→}A_{α} ≅ H(P) ≅ lim_{−→}B_{α}

of two isomorphic direct systems A = (A_{α}; a_{α,β} ) and A = (B_{α}; b_{α,β} ) over the directed poset (ℕ^{d}, ⩽) where

(a) A_{α} = ℤ[\overline{x}]/(ℤ[\overline{x}] ∩ x^{−α} I) and a_{α,β} is induced by the inclusion map

(8.3)  ℤ[\overline{x}] ∩ x^{−α} I ↪ ℤ[\overline{x}] ∩ x^{−β} I
(b) B_{α} = x^{α} ℤ[\overline{x}]/(x^{α} ℤ[\overline{x}] ∩ I) and b_{α,β} is the multiplication by x^{β−α} .

Proof. By Proposition 3.2, there is an isomorphism H(P) ≅ ℤ[\overline{x}^{±1} ]/J_{P} where J_{P} = ⋃ _{α∈ℕ^{d}} x^{−α} I_{P} and ℤ[\overline{x}^{±1} ] = ℤ[x_{1}^{±1} , …, x_{d}^{±1} ]. Since P is standard (Definition 8.1),

H(P) ≅ (ℤ[\overline{x}] + J_{P})/J_{P} = ℤ[\overline{x}]/(ℤ[\overline{x}] ∩ J_{P})

and the first isomorphism in (8.2) follows from the observation that ℤ[\overline{x}] ∩ J_{P} = ⋃ _{α∈ℕ^{d}} (ℤ[\overline{x}] ∩ x^{−α} I_{P}). The commutative diagram

A_{α} −−−−→^{a_{α,β}} A_{β}
×x^{α} ↓  ↓_{×x^{β}}
B_{α} −−−−→_{b_{α,β}} B_{β}

establishes the second isomorphism in (8.2). □

It is clear that the direct system described in Proposition 8.1 can be in principle calculated if a Gröbner basis of the ideal I is known. In favorable cases, such as the case of the n-in-line polyomino, all connecting maps are isomorphisms.

Proposition 8.2. The tile homology group of the n-in-line polyomino is isomorphic to the group,

(8.4)  ℤ^{(n−1)(n−2)} ⊕ ℤ/nℤ.

Proof. By Proposition 8.1, the tile homology group H(P) of the n-in-line polyomino can be computed as the direct limit of the direct system A = (A_{α}; a_{α,β} ). We want to show that H(P) ≅ A_{0} = ℤ[x, y]/I_{n}, which follows from the observation that the inclusion map (8.3) is an isomorphism for each pair α ⩽ β in ℕ^{2}. This is in turn reduced to the claim that

a_{0,α_{k}} : ℤ[x, y] ∩ I_{n} = I_{n} ↪ ℤ[x, y] ∩ x^{−α_{k}} I_{n}

is an epimorphism where α_{k} = k(n, n) ∈ ℕ^{2}. Let p ∈ ℤ[x, y] ∩ x^{−α_{k}} I_{n}. Then x^{α_{k}} · p = q for some q ∈ I_{n}, which implies that p = (1 − x^{α_{k}} )p + q ∈ I_{n}.

The formula (8.4) is a direct consequence of Lemma 5.1 in light of the fact that ℤ[x, y]/I_{n} is generated by monomials, which are reduced with respect to the Gröbner basis. □

Knowledge of a short Gröbner basis provides powerful experimental tool, which is particularly well adopted to methods of lattice geometry. Theorem 7.1 was discovered by experiments which involved Brion’s theorem. Indeed, Brion’s theorem and its relatives [2, 3] provide a short rational form for the integer-point transform, which is an ideal input for a division algorithm. The following example from Mathematica 9.0 exhibits the short rational form for the Newton polynomial (integer-point transform) of the triangular region T (n).

Example 8.2. T [n_] := Together[ \frac{1}{(1−x)∗(1−y)} + \frac{x^{∧} (n+1)}{(x−1)∗(x−y)} + \frac{y^{∧} (n+1)}{(y−1)∗(y−x)} ]

9. Gröbner discrete volume

Let Q be a convex polytope with vertices in ℕ^{d} and let f_{Q} be its Newton polynomial (integer-point transform). The usual ‘discrete volume’ of Q, defined in [2, 3] as the number of integer points inside Q, can be evaluated as the remainder of f_{Q} on division by the ideal I = ⟨x_{1} −1, x_{2} −1, …, x_{d}−1⟩. Let J ⊂ ℤ[x_{1}, …, x_{d}] be an ideal, say the ideal associated to a set R of prototiles in ℕ^{d}. Let G = G_{J} be the Gröbner basis of J with respect to some term order. It may be tempting to ask (at least for some carefully chosen ideals J) what is the geometric and combinatorial significance of the remainder \overline{f} _{Q}^{G} of the integer-point transform f_{Q} on division by the Gröbner basis G.

Definition 9.1. The polynomial valued function Q ↦ \overline{f} _{Q}^{G} is referred to as Gröbner or G-discrete volume of Q with respect to the Gröbner basis G,

Definition 9.1 may look somewhat artificial at first sight. Note however that the basic geometric idea of a volume of a geometric object Q involves approximation, or rather exhaustion (tiling!) of Q by a set of prototiles R. The fact that the G-volume is a polynomial valued (rather than integer valued) function reflects the idea that there may be more than one object in R used for ‘measurements’ of Q.

As in the case of integer-point enumeration in polyhedra, Brion’s theorem is a powerful tool for calculation of the G-discrete volume. It may be expected that some aspects of the Ehrhart theory can be extended in an interesting way to Gröbner volumes, in particular the results from Section 6 can be interpreted as the evaluation of the GBI_{n}-discrete volume of the triangular region T (m).

Acknowledgements. The authors would like to acknowledge useful comments and suggestions by Daniel Lichtblau and the anonymous referee of our paper. The symbolic algebra computations in the paper were performed with the aid of Wolfram Mathematica 9.0.

References

1. W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, Grad. Stud. Math. 3, American Mathematical Society, Providence, 1994.

2. A. Barvinok, Integer Points in Polyhedra, European Mathematical Society, 2008.

3. M. Beck, S. Robins, Computing the Continuous Discretely, Springer-Verlag, New York, 2007.

4. T. Becker, V. Weispfenning, Gröbner Bases: a Computational Approach to Commutative Algebra, Springer-Verlag, New York, 1993.

5. O. Bodini, B. Nouvel, Z-Tilings of Polyominoes and Standard Basis; in: Combinatorial Image Analysis, Lect. Notes Comput Sci. 3322, Springer-Verlag, 2004, 137–150.

6. J. H. Conway, J. C. Lagarias, Tiling with Polyominoes and Combinatorial Group Theory, J. Comb. Theory, Ser. A 53 (1990), 183–208.

7. D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, Third edition, Springer-Verlag, New York, 2007.

8. Using Algebraic Geometry, Second edition, Springer-Verlag, New York, 2005.

9. D. Fuchs, S. Tabachnikov, Mathematical Omnibus: Thirty Lectures on Classic Mathematics, Am. Math. Soc., Providence, 2007.

10. S. W. Golomb, Polyominoes: Puzzles, Patterns, Problems, and Packings, Princeton Univ. Press, Princeton, New Jersey, 1996.

11. M. Muzika Dizdarević, R. T. Živaljević, Symmetric polyomino tilings, tribones, ideals, and Gröbner bases, arXiv:1407.2015 [math.CO].

12. D. Lichtblau, Revisiting strong Gröbner bases over Euclidean domains, Ill. J. Math. 56:1 (2012), 177–194; Wolfram Library Archive, http://library.\discretionary- wolfram. com/ infocenter/ MathSource/ 7522.

13. B. Prvulović, Gröbner bases for complex Grassmann manifolds, Publ. Inst. Math., Nouv. Sér., 90(104) (2011), 23Ű-46.

14. M. Reid, Tile Homotopy Groups, Enseign. Math. 49(1–2) (2003), 123–155.

15. B. Sturmfels, Algorithms in Invariant Theory, (2nd ed.), Springer-Verlag, New York, 2008.

16. W. Thurston, Conway’s tiling groups, Am. Math. Mon. 97 (1990), 757–773.

Faculty of Natural Sciences and Mathematics (Received 21 10 2015) Sarajevo Bosnia and Herzegovina

 mmuzika@me.com

Department of Mathematics and Informatics Faculty of Science, University of Kragujevac, Serbia

 timotijevicmarinko@yahoo.com

Mathematical Institute SASA Belgrade Serbia

 rade@mi.sanu.ac.rs