PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 98(112) (2015), 1–23 DOI: 10.2298/PIM1512001M

SYMMETRIC POLYOMINO TILINGS, TRIBONES, IDEALS, AND GRÖBNER BASES

Manuela Muzika Dizdarević and Rade T. Živaljević

Abstract. We apply the theory of Gröbner bases to the study of signed, symmetric polyomino tilings of planar domains. Complementing the results of Conway and Lagarias we show that the triangular regions T_{N} = T_{3k−1} and T_{N} = T_{3k} in a hexagonal lattice admit a signed tiling by three-in-line polyominoes (tribones) symmetric with respect to the 120^{∘} rotation of the triangle if and only if either N = 27r − 1 or N = 27r for some integer r ⩾ 0. The method applied is quite general and can be adapted to a large class of symmetric tiling problems.

1. Introduction and a summary of main results

Our general objective is to explore signed polyomino tilings which are symmetric with respect to a group of symmetries by the methods of standard (Gröbner) bases of polynomial ideals.

The tiling depicted in Figure 1, illustrating the case N = 8 of Theorem 1.1, shows that a triangular region in a hexagonal lattice may have a signed tiling by congruent copies of the three-in-line tile (tribone). In the same paper Conway and Lagarias showed [6, Theorem 1.2.] that neither this nor any other triangular region in the hexagonal lattice can be tiled by tribones (if ‘negative’ tiles are not permitted).

A very nice exposition of these and related results can be found in [15] and [9, Chapter 23].

Theorem 1.1 (Conway–Lagarias [6, Theorem 1.4]). The triangular region T_{N} in the hexagonal lattice has a signed tiling by congruent copies by three-in-line tiles (tribones) if and only if N = 9r or N = 9r + 8 for some integer r ⩾ 0.

Our main results (Theorems 5.1 and 5.2) say that the triangular regions T_{N} = T_{3k−1} and T_{N} = T_{3k} in a hexagonal lattice^{1} admit a tiling by tribones symmetric with respect to the rotation of the triangle through the angle of 120^{∘} degrees if and only if either N = 27r − 1 or N = 27r for some integer r ⩾ 0. In particular the triangle depicted in Figure 1 does not admit such a tiling.

2010 Mathematics Subject Classification: 52C20; 13P10.

Key words and phrases: signed polyomino tilings, Gröbner bases, tessellations.

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ć.

1In the remaining case N = 3k + 1 there is a hexagon in T_{N} fixed by the 120^{∘}-degrees rotation.

Figure 1. A signed tiling of a triangular region in the dual of the hexagonal lattice.

The method applied for the proof of this theorem is based on the observation that the tile homology group introduced by Conway and Lagarias in [6] (see also Reid [13, Section 2]) is naturally a module over the group ring of the associated group of translations. This group ring is a quotient of a polynomial ring which allows us to reduce the tiling problem to the ‘submodule membership problem’ and apply the theory of Gröbner bases.

1.1. Gröbner bases approach to polyomino tilings. Surprisingly enough there are very few applications of the algebraic method based on the Gröbner basis to problems of tilings and tessellations and the only reference we are aware of is the paper by Bodini and Nouvel [5]. The fact that the ‘tile homology group’ in the sense of [13] is a module over a polynomial ring offers some obvious technical advantages. One of our objectives is to advertise this approach in the context of signed tilings with symmetries. These problems seem to be particularly well adapted to the algebraic method in light of the fruitful relationship between the theory of Gröbner bases and the theory of invariants of group actions [7, 14].

We work with Göbner bases with integer coefficients. Standard references are [1, 4], see also [11] for an overview and some applications.

2. Generalities about lattice tilings

There are three regular lattice tilings of ℝ^{2}, the triangular lattice L_{Δ} , square lattice L_{□}, and the hexagonal lattice L_{hex}, depicted in Figure 2. If L is one of these lattice tilings, then the associated dual lattice (point set) L^{∘} is generated by all barycenters of the elementary cells of L.

Let A(L) be the free abelian group generated by all elementary cells of the lattice L. A ‘lattice tile’ P (informally a lattice figure in L), defined as a finite collection P = {c_{1}, …, c_{n}} of cells in L, is associated an element P = c_{1} + …+ c_{n} of the group A(L).

Figure 2. Three regular lattice tilings of the plane.

The problem if a given bounded lattice region (lattice figure) R admits a signed tiling with translates of prototiles R = {R_{1}, …, R_{k}} is an instance of the subgroup membership problem. Indeed, let B(R) be the subgroup of A(L) generated by all translates of prototiles R_{i} and let H(R) = A(L)/B(R) be the associated ‘homology group’. Then (following [6] and [13]) such a tiling exists if and only if R ∈ B(R) or equivalently if the coset R + B(R) is the zero element in H(R).

Let G = G(L) be the group of all affine transformations that keep the lattice tiling L invariant. Let Γ = Γ(L) be its subgroup of all translations with this property. By selecting 0 ∈ L^{∘} as the zero element, L^{∘} is turned into a group and there is a natural identification Γ = L^{∘}.

The group A(L) is a clearly a module over the group ring ℤ[Γ] (which is isomorphic to the ring ℤ[ℤ^{2}] of Laurent polynomials in two variables. This ring can be obtained (in many ways) as a quotient of the semigroup ring ℤ[ℕ^{d}] ≅ ℤ[x_{1}, …, x_{d}] (for some d).

This observation allows us to see the groups A(L), B(R) and H(R) as modules over the polynomial ring ℤ[x_{1}, …, x_{d}] and to reduce the tiling question to the submodule membership problem [8, Chapter 5]. In turn, in the spirit of [5], one can use the ideas and methods of Gröbner basis theory.

Here we put some emphasis on the use of the ‘submodule membership problem’ as a natural extension of the ‘ideal membership problem’, originally proposed and used by Bodini and Nouvel in [5]. This appears to be a more natural and conceptual approach to the general tiling problems since the module A(L) is no longer required to be monogenic (cyclic over ℤ[P]) which allows us a greater freedom in choosing the semigroup ring ℤ[P]. This property will be indispensable in the study of tilings symmetric with respect to a group of symmetries which is the main goal of this paper.

2.1. An example. The reader may find the following example, depicted in Figure 3, as a good illustration of the main problem studied in our paper.

The (3 × 3) checkerboard C_{3×3} (Figure 3) is supposed to be paved by translates of two types of prototiles. Each of the cells (elementary squares) is labelled (coordinatized) by a pair (i, j) ∈ ℕ^{2} of integers and each tile (polyomino) is formally a union of a finite number of elementary cells. In the example depicted in Figure 3, there are two types of prototiles, T_{1} = {(0, 0), (1, 0), (0, 1)} and T_{2} = {(1, 1), (1, 0), (0, 1)}.

The tiling depicted in Figure 3 satisfies the following conditions:

Figure 3. A signed tiling of a 3 × 3 square symmetric w.r.t. the main diagonal.

(1) The (3 × 3) chessboard C_{3×3} is covered by 3 translated copies of prototile T_{1} and 2 translated copies of prototile T_{2}. In general the translated prototiles are not required to be subsets of C_{3×3} .

(2) Each (translated) prototile is associated a weight (sign) and the total weight of each of the cells (i, j) ∈ C_{3×3} is equal to 1. (The condition that the total weight of cells outside C_{3×3} is zero is added if prototiles are not necessarily subsets of C_{3×3} .)

(3) The tiling is symmetric with respect to the main diagonal of C_{3×3} in the sense that if a translated prototile T + v (where T ∈ {T_{1}, T_{2}} and v ∈ ℕ^{2}) appears in the decomposition (tiling) with a weight w ∈ ℤ, then the diagonally symmetric prototile T′+ v′ is also present with the same weight.

A basic observation is that each polyomino P ⊂ ℕ^{2} can be associated a polynomial f_{P} = ∑ {x^{i}y^{j} | (i, j) ∈ P }, for example f_{T_{1}} = 1 + x + y and f_{T_{2}} = x + y + xy. The decomposition depicted in Figure 3 naturally corresponds to the following decomposition of polynomials in the ring ℤ[x, y] (or in the ring ℤ[σ_{1}, σ_{2}] of symmetric polynomials):

(2.1) f_{T_{1}} + [xf_{T_{1}} + yf_{T_{1}}] − f_{T_{2}} + xyf_{T_{2}} = (1 + x + x^{2})(1 + y + y^{2}) = f_{C_{3×3}} .

Our immediate objective is to use the theory of Gröbner bases to generate such identities. More generally we want to develop and study procedures and algorithms for the systematic analysis (existence and other properties) of decompositions similar to (2.1).

2.2. Basic facts about polyomino tilings. Informally a polyomino pattern P (or polyomino for short) is a (not necessarily connected) finite region consisting of cells in one of the three regular lattice tilings of the plane (Figure 2). It is sometimes more convenient to describe a polyomino as a collection P = {c_{1}, …, c_{k}} of elementary cells in the associated lattice L. Some authors use the generic name polyforms for all three types of polyominoes so the L_{□}-polyforms are polyominoes in the usual sense [10], L_{hex}-polyforms are referred to as polyhexes etc.

We frequently use a slightly more general (algebraic) definition of a polyomino as a multiset, subset of L, with multiple and possibly with negative elements. We will tacitly make a distinction between the geometric and algebraic definition by reserving the term ‘weighted polyomino’ for the algebraic version. However most of the time the term ‘polyomino’ is used interchangeably for both kinds of polyomino patterns.

Definition 2.1. A (weighted) polyomino P is a finite weighted subset of L (a multiset) which contains each elementary cell c ∈ L with some (positive or negative) multiplicity w_{c} ∈ ℤ. In other words P = ∑ w_{c}c is an element of the free abelian group A(L) generated by all cells of the lattice tiling L.

2.3. Geometric-algebraic dictionary of polyomino tilings. We have already seen in Section 2.1 an example of the correspondence between a geometric image (Figure 3) and an algebraic expression (equation (2.1)), based on the correspondence (i, j) ↔ x^{i}y^{j} between the cell labelled by (i, j) ∈ ℕ^{2} and the associated monomial x^{i}y^{j}.

More generally, let S ≅ ℕ^{d} be a semigroup which acts on the lattice L by translations, meaning that there exists a homomorphism ρ : S → Γ from S to the group Γ = Γ(L) of all translations that keep the lattice tiling L invariant. The group A(L) is naturally a module over the semigroup ring ℤ[S] ≅ ℤ[x_{1}, …, x_{d}]. For example if S = Γ then ℤ[S] ≅ ℤ[Γ] and A(L) is a ℤ[Γ]-module where ℤ[Γ] ≅ ℤ[x, x^{−1} ; y, y^{−1} ] is the ring of Laurent polynomials.

Let R = {P_{1}, …, P_{k}} be a collection of basic tiles (prototiles). Define B(R) as the subgroup of A(L) generated by all translates of the prototiles P_{i}, or equivalently as a ℤ[S]-submodule of A(L) generated by R.

The following tautological proposition links the idea of the tile homology group of Conway and Lagarias [6] and Reid [13] with the ‘submodule membership problem’ typical for applications of Gröbner bases (as proposed by Bodini and Nouvel in [5]).

Proposition 2.1. A polyomino P has a signed tiling by translates of prototiles R = {P_{1}, …, P_{k}} if and only if P ∈ B(R) where B(R) is the ℤ[S]-submodule of A(L) generated by R. The associated class [P] in the tile homology module

(2.2)  H(R) := A(L)/B(R)

is a ‘quantitative measure’ of how far is P from admitting a tiling by R.

A modified version of Proposition 2.1 applies to proper subsets of the lattice tiling L. The following proposition serves as an illustration of the simplest case where we restrict our attention to the first quadrant of the L_{□}-lattice tiling. In this case S = ℕ^{2} and ℤ[S] = ℤ[x, y]. As in Section 2.1, each polyomino P ⊂ ℕ^{2} is associated a polynomial f_{P} = ∑ {x^{i}y^{j} | (i, j) ∈ P }.

Proposition 2.2. A polyomino pattern P ⊂ ℕ^{2} admits a signed tiling by the first quadrant translates of polyomino patterns P_{1}, …, P_{k} if and only if,

f_{P} = h_{1}f_{P_{1}} + ⋯+ h_{k}f_{P_{k}}

for some polynomials h_{1}, …, h_{k} with arbitrary integer coefficients or equivalently if,

f_{P} ∈ ⟨f_{P_{1}} , …, f_{P_{k}} ⟩.

2.4. Equivariant polyomino tilings. The group G = G(L) was introduced in Section 2 as the group of all affine transformations that keep the lattice tiling L invariant. The abelian group A(L) is a module over the group ring ℤ[G]. Since Γ ⊂ G is a normal subgroup, we observe that G acts on A(L) preserving its ℤ[Γ]- module structure as well, provided G acts on the ‘scalars’ from ℤ[Γ] by conjugation.

Let Q ⊂ G be a (finite) subgroup of G. Assume that the set R of prototiles is invariant with respect to the group Q. Then Q acts on the submodule B(R) and the tile homology module (2.2). Again, one shouldn’t forget that the action of Q on scalars from ℤ[Γ] may be nontrivial. Define B(R)^{Q} = Hom_{Q}(ℤ, B(R)) as the subgroup (submodule) of B(R) of elements which are invariant under the action of Q.

If we restrict our attention to the subring ℤ[Γ]^{Q} ⊂ ℤ[Γ] of Q-invariant elements, then the action of Q on scalars from ℤ[Γ]^{Q} is trivial and the ℤ[Γ]^{Q}-module A(L) is a Q-module in the usual sense.

An element of the group A(L)^{Q} is referred to as an equivariant signed polyomino. The fundamental problem is to decide when a given polyomino P ∈ A(L)^{Q} admits a Q-symmetric signed tiling by translates of a Q-invariant family of prototiles R. The following criterion is an equivariant analogue of Proposition 2.1.

Proposition 2.3. Let R be a Q-invariant (finite) set of prototiles. A Qinvariant polyomino P ∈ A(L)^{Q} has an equivariant, signed tiling by translates of prototiles R if and only if P ∈ B(R)^{Q} where B(R) is the ℤ[Γ]^{Q}-submodule of A(L) generated by R.

The setting of Proposition 2.3 is exactly the same as before (Proposition 2.1), however the emphasis is now on the ℤ[Γ]^{Q}-module structure on A(L)^{Q} and B(R)^{Q}. In order to apply this criterion one is supposed to determine the ring of invariants ℤ[Γ]^{Q} and the structure of the module B(R)^{Q}. Both goals can be achieved with the aid of the theory of Gröbner bases, see [7, Section 7] for necessary tools.

3. Hexagonal polyomino with symmetries

3.1. Lattices and semigroup rings. Let G_{hex} be the group of symmetries of the hexagonal tiling L_{hex} of the plane depicted in Figure 4. Our objective is to study L_{hex} -tiling problems which are symmetric with respect to some (finite) subgroup of G_{hex} . Our initial focus is on subgroups which act without fixed points (invariant hexagons) so let S_{3} be the group of all elements in G_{hex} which keep the vertex o fixed, and let ℤ_{3} be its subgroup generated by the 120^{∘}-rotation.

The group G_{hex} has a free abelian subgroup D = Γ(L_{hex} ) ≅ ℤ^{2} of rank 2 which is generated by three translations (vectors) t_{x}, t_{y}, t_{y} satisfying the condition t_{x} + t_{y} + t_{z} = 0. The associated group ring P = ℤ[D] is isomorphic to the ring ℤ[x, y; x^{−1} , y^{−1} ] of Laurent polynomials in two variables. For our purposes a more convenient representation is P = ℤ[x, y, z]/⟨xyz − 1⟩ (Figure 4) where variables x, y, z correspond to vectors t_{x} = \overrightarrow{bc}4, t_{y} = \overrightarrow{ca}, t_{z} = \overrightarrow{ab}.

Figure 4. The hexagonal tiling group A_{hex} as a module over P = ℤ[x, y, z]/⟨xyz − 1⟩.

Figure 5. The lattice of black dots as a module over the lattice of white dots.

Let A_{hex} be the (infinite dimensional) free abelian group generated by all elementary hexagonal cells of the lattice L_{hex} . The group A_{hex} is a finitely generated module over the ring P, indeed it is generated by the three neighboring cells a, b, c with common vertex O, depicted in Figure 4.

For added clarity, from here on the lattice L_{hex} is represented by its dual lattice L_{hex}^{∘} of barycenters of all hexagons (the black dots in Figure 5). Consequently the ‘lattice’ L_{hex}^{∘} is a geometric object (a periodic set of points).

The lattice (discrete subgroup of ℤ^{2}) D, generated by vectors t_{x}, t_{y}, t_{z} is in this figure represented by white dots. The fact that A_{hex} is a module over P is simply a reformulation of the fact that the lattice of white dots acts on the set of black dots.

The lattice D is sometimes (Section 3.4) referred to as the xyz-lattice. The lattice (discrete group) E generated by black dots is referred to as the abc-lattice since it is generated by vectors t_{a}, t_{b}, t_{c}, where t_{a} + t_{b} + t_{c} = 0 (Figure 5). The group ring of E is Q = ℤ[a, b, c]/⟨abc − 1⟩.

Note that E has three types of points (Figure 5 on the right) which reflects the fact that the ‘white dot lattice’ D is a sublattice of E of index 3.

3.2. The actions of S_{3} and ℤ_{3} on ℤ[x, y, z]. Here we collect some basic facts about the symmetric group S_{3} and the cyclic group ℤ_{3} actions on ℤ[x, y, z] induced by the permutations of variables x, y, z. As usual for a given G-module M, the associated submodule of G-invariant elements is M^{G}. Elementary symmetric polynomials are σ_{1} = x + y + z, σ_{2} = xy + yz + zx, σ_{3} = xyz.

The S_{3}-invariant polynomials in ℤ[x, y, z] which form a ℤ-basis are σ_{3}^{p} = x^{p}y^{p}z^{p} (where p ⩾ 0), Δ(x^{p}y^{p}z^{q}) = x^{p}y^{p}z^{q} + y^{p}z^{p}x^{q} + z^{p}x^{p}y^{q} (for p ≠ q), and for p ≠ q ≠ r ≠ p,

(3.1) H(x^{p}y^{q}z^{r}) = x^{p}y^{q}z^{r} + y^{p}z^{q}x^{r} + z^{p}x^{q}y^{r} + y^{p}x^{q}z^{r} + x^{p}z^{q}y^{r} + z^{p}y^{q}x^{r}.

Basic ℤ_{3}-invariant polynomials in ℤ[x, y, z] are,

(3.2) x^{p}y^{p}z^{p} (where p ⩾ 0) and Δ(x^{p}y^{q}z^{r}) = x^{p}y^{q}z^{r} + y^{p}z^{q}x^{r} + z^{p}x^{q}y^{r},

where (p, q, r) ≠ (p, p, p). There is an involution I on the set ℤ[x, y, z]^{ℤ_{3}} of ℤ_{3}- invariant polynomials defined by I(p(x, y, z)) = p(y, x, z). The map α : ℤ[x, y, z]^{S_{3}} → ℤ[x, y, z]^{ℤ_{3}} is a monomorphism and the image Im(α) is the fixed point set of the involution I. More explicitly, α(x^{p}y^{p}z^{p}) = x^{p}y^{p}z^{p}, (3.3)

α(Δ(x^{p}y^{p}z^{q})) = Δ(x^{p}y^{p}z^{q}) and α(H(x^{p}y^{q}z^{r})) = Δ(x^{p}y^{q}z^{r}) + I(Δ(x^{p}y^{q}z^{r})).

From here we deduce the following proposition.

Proposition 3.1. There is a commutative diagram

(3.4)  \begin{matrix}0 −→ ⟨xyz − 1⟩^{S_{3}} −→ ℤ[x, y, z]^{S_{3}} −−−−−−−→ ℤ[σ_{1}, σ_{2}] −−−−−−−→ 0 \\ ↓ & α′ & ↓ & α & ↓ & α′′ \\ 0 −→ ⟨xyz − 1⟩^{ℤ_{3}} −→ ℤ[x, y, z]^{ℤ_{3}} −→ (ℤ[x, y, z]/⟨xyz − 1⟩)^{ℤ_{3}} −→ 0 \end{matrix}

where ⟨xyz −1⟩ ⊂ ℤ[x, y, z] is the principal ideal generated by xyz −1, with the split horizontal exact sequences and injective vertical homomorphisms α, α′ and α′′.

Proof. Since ℤ[x, y, z]^{S_{3}} = ℤ[σ_{1}, σ_{2}, σ_{3}] and ⟨xyz−1⟩^{S_{3}} = ℤ[σ_{1}, σ_{2}, σ_{3}](σ_{3}−1), the exactness of the first row in (3.4) is an immediate consequence.

More explicitly the description of S_{3}-invariant and ℤ_{3}-invariant polynomials in ℤ[x, y, z] ((3.1) and (3.2)) allows to describe in a similar fashion invariant polynomials in the ideal (submodule) ⟨xyz − 1⟩ = ⟨σ_{3} − 1⟩. For example the basic S_{3}-invariant polynomials in ⟨σ_{3} − 1⟩^{S_{3}} are,

(3.5)  σ_{3}^{p}(σ_{3} − 1), Δ(x^{p}y^{p}z^{q})(σ_{3} − 1), H(x^{p}y^{q}z^{r})(σ_{3} − 1).

Figure 6. 3d-representation of invariant polynomials (Proposition 3.1)

Similarly, the basic ℤ_{3}-invariant polynomials in ⟨σ_{3} − 1⟩^{ℤ_{3}} are

(3.6)  σ_{3}^{p}(σ_{3} − 1) and Δ(x^{p}y^{p}z^{q})(σ_{3} − 1).

There is an exact sequence of ℤ[ℤ_{3}]-modules,

0 → ⟨xyz − 1⟩ −→ ℤ[x, y, z] −→ ℤ[x, y, z]/⟨xyz − 1⟩ → 0

The ideal ⟨xyz − 1⟩ is as a ℤ-submodule of ℤ[x, y, z] freely generated by binomials x^{p}y^{q}z^{r}(xyz − 1) = x^{p+1} y^{q+1} z^{r+1} − x^{p}y^{q}z^{r}. This binomial is ℤ_{3}-invariant if and only if p = q = r. From here, we easily deduce the structure of ⟨xyz −1⟩ as a ℤ[ℤ_{3}]- module, in particular we observe that there is a decomposition ⟨xyz − 1⟩ ≅ T ⊕ F of ℤ[ℤ_{3}]-modules where T is a trivial and F a free ℤ[ℤ_{3}]-module.

It follows that H^{1}(ℤ_{3}; ⟨xyz − 1⟩) ≅ 0 and from the long exact sequence of cohomology we obtain the exactness of the second row of (3.4),

0 → ⟨σ_{3} − 1⟩^{ℤ_{3}} −→ ℤ[x, y, z]^{ℤ_{3}} −→ (ℤ[x, y, z]/⟨xyz − 1⟩)^{ℤ_{3}} → 0.

In particular,

(ℤ[x, y, z]/⟨xyz − 1⟩)^{ℤ_{3}} ≅ ℤ[x, y, z]^{ℤ_{3}}/⟨xyz − 1⟩^{ℤ_{3}}.

The injectivity of α and α′follows from (3.3). In order to establish the injectivity of α′′, we observe that (in light of (3.2) and (3.6)) ℤ[x, y, z]^{ℤ_{3}}/⟨xyz−1⟩^{ℤ_{3}} is isomorphic to the submodule of ℤ[x, y, z]^{ℤ_{3}} generated by 1 = x^{0}y^{0}z^{0}, Δ(x^{p}) = x^{p} + y^{p} + z^{p} and Δ(x^{p}y^{q}) = x^{p}y^{q} + y^{p}z^{q} + z^{p}x^{q} (where (p, q) ≠ (0, 0)). Similarly, in light of (3.1) and (3.5), we observe that ℤ[σ_{1}, σ_{2}] ≅ ℤ[x, y, z]^{S_{3}} /⟨xyz − 1⟩^{S_{3}} is generated by 1 = x^{0}y^{0}z^{0}, Δ(x^{p}), Δ(x^{p}y^{p}) and H(x^{p}y^{q}). For example, one of these Hpolynomials (or hexagons) is depicted in Figure 6. From here, we observe that α′′ is injective since it satisfies analogues of formulas (3.3). □

3.3. The ring P^{ℤ_{3}} of ℤ_{3}-invariant polynomials. We begin the analysis of ℤ_{3}-invariant hexagonal tilings by describing the structure of the ring P^{ℤ_{3}} = (ℤ[x, y, z]/⟨xyz − 1⟩)^{ℤ_{3}} of ℤ_{3}-invariant polynomials.

The ring P is as a ℤ-module freely generated by monomials x^{p}y^{q}z^{r} which are not divisible by xyz, that is monomials x^{p}y^{q}z^{r} which satisfy at least one of the conditions p = 0, q = 0, r = 0. Each of these monomials is associated a white dot in the XY Z-coordinate system (Figure 7).

The ring P^{ℤ_{3}} of ℤ_{3}-invariant polynomials is as a free ℤ-module generated by polynomials (‘triangles’) Δ(x^{p}y^{q}) = x^{p}y^{q}+y^{p}z^{q}+z^{p}x^{q}, where either p > 0 or q > 0, and the constant monomial 1 = x^{0}y^{0}z^{0}. Note that Δ(x^{p}y^{q}) is the ℤ_{3}-symmetrized version of x^{p}y^{q}; we also write Δ(1) = 3 = 1 + 1 + 1. Moreover, x^{p}y^{q} is the leading monomial of Δ(x^{p}y^{q}) in the graded reversed lexicographic monomial order such that x > y > z. Consequently, Δ(y^{k}) = Δ(z^{k}) is almost always recorded as Δ(x^{k}).

Figure 7. Polynomial Δ(x^{2}y) = x^{2}y+y^{2}z+z^{2}x as one of basic Δpolynomials which generate (over ℤ) all ℤ_{3}-invariant polynomials in P.

Lemma 3.1. The following identities hold in the ring P = ℤ[x, y, z]/⟨xyz − 1⟩.

(3.7) Δ(xy)Δ(x^{p−1} y^{q−1} )=Δ(x^{p}y^{q})+Δ(x^{p−1} y^{q−2} )+Δ(x^{p−2} y^{q−1} ) (p ⩾ 2, q ⩾ 2)
(3.8) Δ(x)Δ(x^{p−1} y^{q}) = Δ(x^{p}y^{q}) + Δ(x^{p−1} y^{q+1} ) + Δ(x^{p−2} y^{q−1} ) (p ⩾ 2, q ⩾ 1)
(3.9) Δ(x)Δ(x^{p}y^{q−1} ) = Δ(x^{p}y^{q}) + Δ(x^{p+1} y^{q−1} ) + Δ(x^{p−1} y^{q−2} ) (p ⩾ 1, q ⩾ 2)
(3.10)  Δ(x)Δ(x^{p−1} ) = Δ(x^{p}) + Δ(x^{p−1} y) + Δ(xy^{p−1} ) (p ⩾ 2)
(3.11)  Δ(xy)Δ(x^{p−1} ) = Δ(x^{p}y) + Δ(x^{p−2} ) + Δ(xy^{p}) (p ⩾ 2).

SYMMETRIC POLYOMINO TILINGS, TRIBONES, IDEALS, AND GRÖBNER BASES 11

By the injectivity of the map α′′(Proposition 3.1) the ring ℤ[σ_{1}, σ_{2}] can be seen as a subring of the ring P = ℤ[x, y, z]/⟨xyz − 1⟩, so both P and P^{ℤ_{3}} are modules over ℤ[σ_{1}, σ_{2}].

Theorem 3.1. The ring P^{ℤ_{3}} = (ℤ[x, y, z]/⟨xyz −1⟩)^{ℤ_{3}} of ℤ_{3}-invariant polynomials is isomorphic (as a module over P_{σ} = ℤ[σ_{1}, σ_{2}]) to the free module P_{σ} ·1⊕P_{σ} ·θ of rank two where θ = Δ(x^{2}y) (Figure 7). Moreover,

(3.12)  Θ = Θ(σ_{1}, σ_{2}, θ) := θ^{2} − (σ_{1}σ_{2} − 3)θ + (σ_{1}^{3} + σ_{2}^{3} − 6σ_{1}σ_{2} + 9) = 0

so there is an isomorphism of the rings

(3.13)  (ℤ[x, y, z]/⟨xyz − 1⟩)^{ℤ_{3}} ≅ ℤ[σ_{1}, σ_{2}, θ]/⟨Θ⟩

where ⟨Θ⟩ is the principal ideal in ℤ[σ_{1}, σ_{2}, θ] generated by Θ.

Proof. By definition Δ(x) = σ_{1}, Δ(xy) = σ_{2}, θ = Δ(x^{2}y) and θ′ = Δ(xy^{2}).

Let us show that the ring P^{ℤ_{3}} of ℤ_{3}-invariant polynomials in P is generated as a ℤ[σ_{1}, σ_{2}]-module by 1 and θ.

• If p ⩾ 2 and q ⩾ 2, then by identity (3.7) (Lemma 3.1) the polynomial Δ(x^{p}y^{q}) can be expressed in terms of lexicographically smaller Δpolynomials, multiplied by elements of ℤ[σ_{1}, σ_{2}].

• If p ⩾ 3 and q = 1, then by Lemma 3.1 (equation (3.8)) the polynomial Δ(x^{p}y) can be also reduced to lexicographically smaller Δ-polynomials.

• If p ⩾ 2, then Δ(x^{p}) is by Lemma 3.1 (equation (3.10)) reducible to

lexicographically smaller Δ-polynomials.

Using the symmetry to cover the cases of Δ(xy^{q}) for q ⩾ 3, we observe that all Δpolynomials can be expressed in terms of θ, θ′, σ_{1}, σ_{2} and 1. Since θ + θ′ = σ_{1}σ_{2} − 3 (equation (3.11)) we finally conclude that

(3.14)  P^{ℤ_{3}} = ℤ[σ_{1}, σ_{2}] · 1 + ℤ[σ_{1}, σ_{2}] · θ.

The sign + in formula (3.14) can be replaced by ⊕. Indeed, if P + Qθ = 0 for some P, Q ∈ ℤ[σ_{1}, σ_{2}], then (by interchanging variables x and y) we have P + Qθ′ = 0 which is possible only if P = Q = 0.

By (3.14) θ^{2} = P + Qθ for some P, Q ∈ ℤ[σ_{1}, σ_{2}] which by direct calculation leads to equation (3.12) and isomorphism (3.13). □

3.4. The abc-lattice E and the xyz-lattice D. The ‘white dot’ lattice or the xyz-lattice D (Section 3.1) is generated by vectors (translations) t_{x}, t_{y}, t_{z} (Figures 4 and 5). It is convenient to introduce the abc-lattice E as the lattice generated by the vectors t_{a}, t_{b}, t_{c} (Figures 8 and 9).

The lattice D is a sublattice of E of index 3. The set of black dots (Figures 5, 8 and 9) is clearly one of the cosets of the quotient lattice E/D ≅ ℤ_{3}.

The fact that E/D ≅ ℤ_{3} explains why there are three types of dots in these images. In order to avoid clutter, we will in subsequent sections continue to draw only black and white dots, however one should keep in mind the whole of the background lattice E and the presence of ‘invisible’ dots (circled asterisks in Figures 8 and 9).

Figure 8. The lattice E has three types of dots,black, white, and asterisks in circles.

Figure 9. Three types of dots correspond to the cosets of the sublattice D ⊂ E.

Let ι : E → ℤ/3ℤ be the homomorphism which sends the generators a, b, c to 1 ∈ ℤ. Then D = E_{0} = ι^{−1} (0) is the set of white dots and E_{1} = ι^{−1} (1) is the set of black dots.

3.5. The abc-ring Q and the xyz-ring P. Let Q = ℤ[a, b, c]/⟨abc − 1⟩ be the semigroup ring of the lattice E and let Q^{ℤ_{3}} = (ℤ[a, b, c]/⟨abc − 1⟩)^{ℤ_{3}} be the associated ring of ℤ_{3}-invariant polynomials. All structure results that apply to the ring P = ℤ[x, y, z]/⟨xyz − 1⟩ apply to the ring Q as well. In particular there is an isomorphism (Theorem 3.1),

(3.15)  (ℤ[a, b, c]/⟨abc − 1⟩)^{ℤ_{3}} ≅ ℤ[s_{1}, s_{2}, t]/⟨Θ⟩

where Θ = Θ(s_{1}, s_{2}, t) is the polynomial described in equation (3.12) and

s_{1} = a + b + c s_{2} = ab + bc + ca t = Δ(a^{2}b) = a^{2}b + b^{2}c + c^{2}a.

The homomorphism ι : E → ℤ/3ℤ introduced in Section 3.4 allows us to define a ℤ_{3}-grading in the rings Q and Q^{ℤ_{3}}. Indeed, the monomial m = a^{p}b^{q}c^{r} ∈ Q is graded by its ‘degree mod 3’ i.e., the mod 3 class of deg(m) = p + q + r.

The xyz-ring P, as the group ring of the lattice D of white dots, corresponds to the elements in the abc-ring Q graded by 0. Indeed, this follows from the fact (Figure 9) that x = ac^{2}, y = ba^{2}, z = cb^{2}.

Moreover, the P -submodule of Q of elements graded by 1 (monomials with the degree congruent to 1 mod 3) is precisely the submodule generated by the monomials associated with the black dots.

Recall that the P -module generated by black dots is precisely the module A_{hex} from Section 3.1. This observation allows us to reduce the “submodule membership problem” in the P -module A_{hex} to the corresponding “ideal membership problem” in the ring Q. We are primarily interested in ℤ_{3}-invariant polynomials, so in the following section, we show how the similar “submodule membership problem” in the P^{ℤ_{3}}-module A_{hex}^{ℤ_{3}} can be reduced to the corresponding “ideal membership problem” in the ring Q^{ℤ_{3}} (Proposition 3.2).

3.6. The ring Q^{ℤ_{3}} and A_{hex}^{ℤ_{3}} as a P^{ℤ_{3}}-module. The free abelian group A_{hex} ,

generated by all elementary 2-cells of the hexagonal lattice L_{hex} (or equivalently all 0-dimensional cells of its dual lattice L_{hex}^{∘} ), is a module over the ring P = ℤ[x, y, z]/⟨xyz − 1⟩.

Δ-polynomials already appeared in the description of the ring P^{ℤ_{3}} of ℤ_{3}- invariant polynomials in P (Figure 7). Following the idea of the ‘Newton polygon construction’, a polynomial Δ(x^{p}y^{q}) = x^{p}y^{q}+y^{p}z^{q}+z^{p}x^{q} is visualized as a triangle with vertices in the ‘white dot’-lattice, invariant with respect to the action of group ℤ_{3}.

Similarly the Δ-polynomials Δ(a^{p}b^{q}) = a^{p}b^{q} + b^{p}c^{q} + c^{p}a^{q} are, together with 1 = a^{0}b^{0}c^{0}, ℤ-generators of the ring Q^{ℤ_{3}}. An immediate consequence is that P^{ℤ_{3}} is a subring of Q^{ℤ_{3}}.

Finally, the ‘black dot’ Δ-polynomials Δ(x^{p}y^{q}a) = x^{p}y^{q}a + y^{p}z^{q}b + z^{p}x^{q}c (Figure 10) form a ℤ-basis of the group A_{hex}^{ℤ_{3}} of ℤ_{3}-invariant elements of A_{hex} .

The ring Q^{ℤ_{3}} inherits the ℤ_{3}-gradation from the ring Q. Moreover P^{ℤ_{3}} is precisely the subset of all elements graded by 0 ∈ ℤ_{3}, while A_{hex}^{ℤ_{3}} is generated by ‘black dot triangles’ which are precisely the triangles graded by 1 ∈ ℤ_{3}. This characterization is a basis of the following fundamental proposition.

Proposition 3.2. Let K ⊂ A_{hex}^{ℤ_{3}} be a P^{ℤ_{3}}-submodule of A_{hex}^{ℤ_{3}} . Let I_{K} ⊂ Q^{ℤ_{3}}

be the ideal in Q^{ℤ_{3}} generated by K. Suppose that p ∈ A_{hex}^{ℤ_{3}} . Then,

p ∈ K ⟺ p ∈ I_{K} .

In other words the ‘submodule membership problem’ is reduced to the ‘ideal membership problem’ in the ring Q^{ℤ_{3}}.

Proof. The implication p ∈ K ⇒ p ∈ I_{K} is clear. The reverse implication is equally easy. Indeed, if p = α_{1}p_{1} + ⋯+ α_{k}p_{k} for some elements p_{i} ∈ K and homogeneous (in the sense of the ℤ_{3}-gradation) elements α_{i} ∈ Q^{ℤ_{3}}, then we can assume that all α_{i} ∈ P^{ℤ_{3}} (the other terms cancel out). □

Figure 10. Δ-polynomials in the ‘black dot lattice’ generate the group A_{hex}^{ℤ_{3}} .

3.7. Submodule of A_{hex}^{ℤ_{3}} generated by tribones. A three-in-line hexagonal polyomino or a tribone is a translate of one of the following three types (Figure 10),

T_{x} = x^{−1} + 1 + x = ab^{2} + 1 + ac^{2}
T_{y} = y^{−1} + 1 + y = bc^{2} + 1 + ba^{2}
T_{z} = z^{−1} + 1 + z = ca^{2} + 1 + cb^{2}

If A = x^{p}y^{q}a is a ‘black dot’ in the angle XOY, then the three basic tribones centered at the point A are

(3.16)  T_{x}(A) = x^{p}y^{q}aT_{x}, T_{y}(A) = x^{p}y^{q}aT_{y}, T_{z}(A) = x^{p}y^{q}aT_{z}.

For example,

T_{x}(a) = (x^{−1} + 1 + x)a T_{y}(a) = (y^{−1} + 1 + y)a T_{z}(a) = (z^{−1} + 1 + z)a

The ℤ_{3}-symmetric triplets of tribones, associated to tribones (3.16), are

Δ(T_{x}(A)), Δ(T_{y}(A)), Δ(T_{z}(A))

where for example,

Δ(T_{y}(A)) = Δ(x^{p}y^{q}aT_{y}) = Δ(x^{p}y^{q−1} a) + Δ(x^{p}y^{q}a) + Δ(x^{p}y^{q+1} a).

Theorem 3.2. The submodule K_{trib} ⊂ A_{hex}^{ℤ_{3}} of ℤ_{3}-invariant polyominoes (polyhexes) which admit a signed, symmetric tiling by tribones is generated, as a module over P^{ℤ_{3}}, by the ℤ_{3}-symmetric triplets of tribones,

(3.17)  Δ(T_{x}(a)), Δ(T_{y}(a)), Δ(T_{z}(a)), Δ(T_{x}(ax)), Δ(T_{y}(ax)), Δ(T_{z}(ax)).

Figure 11. Δ-polynomials and the structure of the P_{3}^{ℤ}-module of ℤ_{3}-invariant tiles.

Proof. Let A = Ma = x^{p}y^{q}a ∈ A_{hex} be a ‘black dot’ in the angle ∠XOY where M = x^{p}y^{q} ∈ P is the corresponding ‘white dot’ (Figure 11). The three tribones centered at A are MaT_{x}, MaT_{y}, MaT_{z}. We want to show that each of the associated ℤ_{3}-symmetric triplets Δ(MaT_{x}), Δ(MaT_{y}), Δ(MaT_{z}) is in the P^{ℤ_{3}}-module generated by the six elements listed in the equation (3.17).

Figure 11 depicts the case where M = x^{4}y^{3} and the chosen tribone is MaT_{y} = x^{4}y^{3}(y^{−1} + 1 + y)a. Using this particular example, we describe a general reduction procedure which allows us to express the triplets Δ(MaT_{x}), Δ(MaT_{y}), Δ(MaT_{z}) by triplets strictly closer to the origin O.

Let Δ(x) = x + y + z = σ_{1} and Δ(xy) = xy + yz + zx = σ_{2} be the two basic ‘white dot’ triangles (Δ-polynomials) depicted at the center of Figure 11.

By translating these triangles we surround the point A by six triangles forming a regular hexagon.

Let us assume that the origin O is not contained in the interior of this hexagon. It follows that one of the six triangles (the shaded triangle ABC in Figure 11) has the property that the segment OA intersects the side BC opposite to A. (Observe that the origin O can be on the segment BC and this happens precisely if A ∈ {ya, xya}.)

An immediate consequence is that the lengths of all segments OB, OC, OX are strictly smaller than the length of OA. Indeed, by construction ∠ACO ⩾ 60^{∘} ⩾ ∠CAO, and at least one of these inequalities is strict. In our case, the triangle ABC is a translate of Δ(xy) (otherwise we would use Δ(x)). Since Δ(xy)X = A + B + C we observe that

(3.18) Δ(xy)(y^{−1} + 1 + y)X = (y^{−1} + 1 + y)A + (y^{−1} + 1 + y)B + (y^{−1} + 1 + y)C

Let Δ_{Y} = Δ((y^{−1} + 1 + y)Y). By symmetrizing equality (3.18) and adding (that is by applying the Δ-operator on both sides of (3.18)) we finally obtain,

Δ(xy)Δ_{X} = Δ_{A} + Δ_{B} + Δ_{C}.

Summarizing, we see that each ℤ_{3}-symmetric triplet of tribones Δ_{A} can be expressed in terms of triplets closer to the origin, provided the hexagon associated to A does not contain the origin O in its interior.

The only remaining possibilities are A′ = a and A′′= xa which accounts for the six ℤ_{3}-symmetric triplets of tribones listed in the theorem. □

3.8. The ideal I_{K_{trib}} . In this subsection, we express the generating polynomials for the ideal I_{K_{trib}} ⊂ Q^{ℤ_{3}} (listed in (3.17)) in terms of variables s_{1}, s_{2}, t which appear in the description of the ambient ring Q^{ℤ_{3}} (equation (3.15) in Section 3.5)).

Proposition 3.3. We have

Δ(T_{x}(a)) = −3s_{1} + 2s_{2}^{2},  Δ(T_{x}(ax)) = −s_{1}^{2}s_{2} + 2s_{2}^{2} − s_{1}t + s_{2}^{2}t,
Δ(T_{y}(a)) = 3s_{1} − s_{2}^{2} + s_{1}t,  Δ(T_{y}(ax)) = −3s_{1} + s_{1}^{2}s_{2} − s_{2}^{2},
Δ(T_{z}(a)) = s_{1}^{2}s_{2} − s_{2}^{2} − s_{1}t,  Δ(T_{z}(ax)) = 3s_{1} − 2s_{1}^{2}s_{2} − s_{2}^{2} + s_{1}s_{2}^{3} + s_{1}t − s_{2}^{2}t

Proof. The proof is by direct calculations which follow the algorithm described in the proof of Theorem 3.1. For example

Δ(T_{x}(a)) = Δ(a^{2}b^{2} + a + a^{2}c^{2}) = 2Δ(a^{2}b^{2}) + Δ(a) = 2s_{2}^{2} − 4s_{1} + s_{1} = 2s_{2}^{2} − 3s_{1}.

Similarly since

Δ(a^{3}b) = Δ(a)Δ(a^{2}b) − Δ(a^{2}b^{2}) − Δ(a) = s_{1}t − (s_{2}^{2} − 2s_{1}) − s_{1} = s_{1}t − s_{2}^{2} + s_{1}

we deduce that,

Δ(T_{y}(a)) = Δ(c + a + a^{3}b) = 2s_{1} + Δ(a^{3}b) = s_{1}t − s_{2}^{2} + 3s_{1}.

The proofs of other equalities follow the same pattern. □

4. Calculations

4.1. Auxiliary calculations. Let I ⊂ ℤ[x, y] be the ideal,

I = ⟨1 + x + x^{2}, 1 + y + y^{2}, 1 + xy + (xy)^{2}⟩.

If p − q ∈ I we say that p and q are congruent mod I and write p ≡_{I} q. In this section we collect some elementary congruences mod I which are needed for subsequent calculations.

Lemma 4.1. If m − n is divisible by 3 then,

x^{m} ≡_{I} x^{n}, y^{m} ≡_{I} y^{n}, (xy)^{m} ≡_{I} (xy)^{n}.

Lemma 4.2. We have

L_{k} := 1 + x + …x^{k−1} ≡_{I} \{ \begin{matrix}0 & if k ≡ 0 (mod 3) \\ 1 & if k ≡ 1 (mod 3) \\ 1 + x & if k ≡ 2 (mod 3). \end{matrix}

Lemma 4.3. We have

□_{k} := (1 + x + …x^{k−1} )(1 + y + …y^{k−1} ) ≡_{I} \{ \begin{matrix}0 & if k ≡ 0 (mod 3) \\ 1 & if k ≡ 1 (mod 3) \\ x^{2}y^{2} & if k ≡ 2 (mod 3). \end{matrix}

Figure 12. Pictorial proof of the relation Δ_{3n−1} ≡_{I} nΔ_{2}.

The Newton polygon of the polynomial □_{k} is the square with vertices (0, 0), (0, k − 1), (k − 1, 0), (k − 1, k − 1), which has precisely k integer points on each of its sides. Similarly the polynomial

Δ_{k} = L_{k} + xyL_{k−1} + (xy)^{2}L_{k−2} + ⋯+ (xy)^{k−1} L_{1}

collects all monomials associated to the integer points in the triangle with the vertices (0, 0), (k − 1, 0), (k − 1, k − 1)} (Δ_{8} is depicted in Figure 12).

Lemma 4.4. We have

Δ_{3n−1} ≡_{I} nΔ_{2} ≡_{I} n(1 + x + xy)
Δ_{3n} ≡_{I} Δ_{3n−1} ≡_{I} nΔ_{2}
Δ_{3n+1} ≡_{I} nΔ_{2} + 1

4.2. Δ-polynomial of a triangular region. We use the calculations from Section 4.1 to determine the Δ-polynomial of a triangular region T_{N} depicted in Figure 13, where N = 3k − 1 is the number of black dots on one of the edges of the triangle. By definition the vertices of the triangular region T_{N} are black dots which are associated to the monomials

ax^{k−1} y^{2k−2} by^{k−1} z^{2k−2} cz^{k−1} x^{2k−2} .

It is sufficient to determine the ≡_{I} class of the polynomial A_{k} described as the sum of all monomials in T_{N} which belong to the cone xOy. By inspection we see that A_{k} = B_{k} + C_{k} where B_{k} corresponds to the parallelogram with vertices a, ax^{k−1} , ay^{k−1} , a(xy)^{k−1} and C_{k} is the polynomial associated to the triangle with vertices axy^{k}, ax^{k−1} y^{k}, ax^{k−1} y^{2k−2} . Since B_{k} = a · □_{k} and C_{k} = axy^{k}Δ_{k−1} , we can use Lemmas 4.1, 4.3 and 4.4 to evaluate A_{k}.

Figure 13. Decomposition of T_{N} into blocks.

Proposition 4.1. We have

A_{k} = \{ \begin{matrix}daxΔ_{2} & if k = 3d \\ a + daxyΔ_{2} & if k = 3d + 1 \\ ax^{2}y^{2} + axy^{2}(dΔ_{2} + 1) & if k = 3d + 2. \end{matrix}

Proof.

(4.1)  B_{k} = a · □_{k} ≡_{I} \{ \begin{matrix}0 & if k = 3d \\ a & if k = 3d + 1 \\ ax^{2}y^{2} & if k = 3d + 2. \end{matrix}

Since

axy^{k} ≡_{I} \{ \begin{matrix}ax & if k = 3d \\ axy & if k = 3d + 1 \\ axy^{2} & if k = 3d + 2, \end{matrix}

(4.2)  C_{k} = axy^{k}Δ_{k−1} ≡_{I} \{ \begin{matrix}daxΔ_{2} & if k = 3d \\ daxyΔ_{2} & if k = 3d + 1 \\ axy^{2}(dΔ_{2} + 1) & if k = 3d + 2. \end{matrix}

Since A_{k} = B_{k} + C_{k} the result follows by adding equations (4.1) and (4.2). □

Proposition 4.2. The Δ-polynomial of A_{k} is equal to Δ(A_{k}) = P +dQ where,

P = 0, Q = 3s_{1} − 3s_{1}^{2}s_{2} + s_{1}s_{2}^{3}, (k = 3d)

P = s_{1}, Q = 9s_{1} − 6s_{1}^{2}s_{2} + s_{1}^{3}s_{2}^{2} + 4s_{1}t − 2s_{1}^{2}s_{2}t + s_{1}t^{2} (k = 3d + 1)

(k = 3d + 2)

\begin{matrix}P = 11s_{1} + s_{1}^{4} − 9s_{1}^{2}s_{2} + 5s_{2}^{2} + s_{1}^{3}s_{2}^{2} − s_{1}s_{2}^{3} + 4s_{1}t − 2s_{1}^{2}s_{2}t + s_{2}^{2}t + s_{1}t^{2} \\ Q = 24s_{1} + s_{1}^{4} − 11s_{1}^{2}s_{2} + s_{1}^{5}s_{2} − 3s_{1}^{3}s_{2}^{2} + 4s_{1}s_{2}^{3} + 8s_{1}t − s_{1}^{4}t − s_{1}^{2}s_{2}t + 3s_{1}t^{2}. \end{matrix}

Proof. It follows from Proposition 4.1 that,

A_{k} = \{ \begin{matrix}d(a^{2}c^{2} + a^{3}c^{4} + a^{4}c^{3}) & if k = 3d \\ a + d(a^{3}c + a^{4}c^{3} + a^{5}c^{2}) & if k = 3d + 1 \\ (a^{5}c^{2} + a^{4}) + d(a^{4} + a^{5}c^{2} + a^{6}c) & if k = 3d + 2. \end{matrix}

The rest of the proof is by direct calculation, by hand or preferably by a computer algebra system. □

4.3. Gröbner basis for the submodule K_{trib} ⊂ A_{hex}^{ℤ_{3}} . We want to test if

the polynomials Δ(A_{k}) described in Proposition 4.2 belong (for different values of k) to the submodule K_{trib} described in Theorem 3.2 (Section 3.7).

In light of Proposition 3.2, this question is reduced to the ‘ideal membership problem’ for the associated ideal I_{K_{trib}} in the ring Q^{ℤ_{3}} ≅ ℤ[s_{1}, s_{2}, t]/⟨Θ⟩ and in turn to the ‘ideal membership problem’ for the ideal

J_{K_{trib}} := I_{K_{trib}} + ⟨Θ⟩ ⊂ ℤ[s_{1}, s_{2}, t].

Here Θ is the polynomial defined in Theorem 3.1 (equation 3.13) and again, in the context of the abc-ring Q^{ℤ_{3}}, in Section 3.5.

With the aid of Wolfram Mathematica 9.0 we determine the Gröbner basis for the ideal J_{K_{trib}} .

Proposition 4.3. The Gröbner basis G = G_{trib} of the ideal J_{K_{trib}} ⊂ ℤ[s_{1}, s_{2}, t]

with respect to the lexicographic order of variables s_{1}, s_{2}, t is given by the following list of polynomials:

(4.3)  \begin{matrix}27 + 9t + 3t^{2} & −27 + t^{3} & 9s_{2} + 3s_{2}t + s_{2}t^{2} & 3s_{2}^{2} \\ s_{2}^{2}t & s_{2}^{4} & 3s_{1} + s_{2}^{2} & s_{2}^{2} + s_{1}t \\ s_{1}s_{2}^{3} & s_{1}^{2}s_{2} & 9 + s_{1}^{3} + s_{2}^{3} + 3t + t^{2} \end{matrix}

As the first application of Proposition 4.3 we calculate the remainders \overline{P}^{G} and \overline{Q}^{G} of polynomials P and Q introduced in Proposition 4.2 on division by the Gröbner basis G = G_{trib} .

Proposition 4.4. Let P_{i} and Q_{i} be the polynomials such that to Δ(A_{3d+i} ) = P_{i} + dQ_{i} (Proposition 4.2). Then the remainders of these polynomials on division by the Gröbner basis G = G_{trib} are

(4.4)  \begin{matrix}\overline{P_{0}}^{G} = 0 & \overline{Q_{0}}^{G} = −s_{2}^{2} \\ \overline{P_{1}}^{G} = s_{1} & \overline{Q_{1}}^{G} = −s_{2}^{2} \\ \overline{P_{2}}^{G} = −s_{1} & \overline{Q_{2}}^{G} = −s_{2}^{2} \end{matrix}

5. Main results

Theorem 5.1. Let T_{N} = T_{3k−1} be the ℤ_{3}-symmetric triangular region in the hexagonal lattice depicted in Figure 13 where N is the number of black dots (hexagons) on the edge of the triangle. Then T_{N} admits a ℤ_{3}-symmetric, signed tiling by three-in-line polyominoes (tribones) if and only if k = 9r for some integer r. The first such triangle is T_{26}, in particular the triangle T_{8} shown in Figure 1 does not have a ℤ_{3}-symmetric, signed tiling by tribones.

Proof. By Proposition 4.2 the polynomial Δ(A_{k}), equal to the sum of all monomials covered by the triangular region T_{N} = T_{3k−1} , can be expressed (as a polynomial in variables s_{1}, s_{2}, t) as the sum Δ(A_{k}) = P + dQ. More explicitly (taking into account the different cases of Proposition 4.2) we write Δ(A_{3d+i} ) = P_{i} + dQ_{i} where i ∈ {0, 1, 2}.

By Proposition 4.4 remainders of these polynomials on division by the Gröbner basis G = G_{trib} are displayed in Table (4.4).

The leading terms of the Gröbner basis (4.3) are

3t^{2} t^{3} s_{2}t^{2} 3s_{2}^{2}
s_{2}^{2}t s_{2}^{4} 3s_{1} s_{1}t
s_{1}s_{2}^{3} s_{1}^{2}s_{2} s_{1}^{3}

By inspection we see that the polynomial P_{i} + dQ_{i} can be reduced to zero if and only if i = 0 and d = 3r for some integer r, or in other words if and only if k = 3d = 9r (N = 27r − 1). □

5.1. The case N = 3k. The triangular region T_{N} in the case N = 3k + 1 has a fixed point (black dot) with respect to the ℤ_{3} action so we focus on the remaining case N = 3k. In this case, the convex hull of the set of all black dots in the intersection of T_{3k} with the angle xOy is the trapeze with vertices associated the monomials a, ax^{k}, ay^{k−1} , ax^{2k−1} y^{k−1} . We denote the sum of all these monomials by A_{k}. This trapeze is divided into a rhombus, with vertices at a, ax^{k−1} , ay^{k−1} , a(xy)^{k−1} and an equilateral triangle with vertices at ax^{k}, ax^{k}y^{k−1} , ax^{2k−1} y^{k−1} . The sums of monomials in these two regions are respectively B_{k} and C_{k}, so by definition A_{k} = B_{k} + C_{k}.

The mod I class of the polynomial B_{k} = a · □_{k} is as in the case N = 3k − 1 described by the equality (4.1). Similarly, C_{k} = ax^{k}∇_{k} where ∇_{k} is the sum of all monomials in the triangle with vertices at 1, y^{k−1} , (xy)^{k−1} . This triangle is obtained from Δ_{k} by interchanging variables x and y so the following lemma is an immediate consequence of Lemma 4.4.

Lemma 5.1. We have

∇_{3n−1} ≡_{I} n∇_{2} ≡_{I} n(1 + x + xy),
∇_{3n} ≡_{I} ∇_{3n−1} ≡_{I} n∇_{2},
∇_{3n+1} ≡_{I} n∇_{2} + 1.

Similarly,

ax^{k} ≡_{I} \{ \begin{matrix}a & if k = 3d \\ ax & if k = 3d + 1 \\ ax^{2} & if k = 3d − 1, \end{matrix} C_{k} = ax^{k}∇_{k} ≡_{I} \{ \begin{matrix}da∇_{2} & if k = 3d \\ ax(d∇_{2} + 1) & if k = 3d + 1 \\ dax^{2}∇_{2} & if k = 3d − 1. \end{matrix}

and finally,

Proposition 5.1. We have

A_{k} = \{ \begin{matrix}da∇_{2} & = d(a + a^{3}b + a^{3}c) & k & = 3d \\ a + ax(d∇_{2} + 1) & = (a + a^{2}c^{2}) + d(a^{2}c^{2} + a^{3}c + a^{4}c^{3}) & k & = 3d + 1 \\ ax^{2}y^{2} + dax^{2}Δ_{2} & = a^{5}c^{2} + d(a^{3}c^{4} + a^{4}c^{3} + a^{5}c^{5}) & k & = 3d − 1. \end{matrix}

The associated Δ-polynomials are given by the following proposition.

Proposition 5.2. The Δ-polynomial of A_{k} is equal to Δ(A_{k}) = P +dQ where,

P = 0 Q = s_{1}^{2}s_{2} − 2s_{2}^{2} (k = 3d)

P = −s_{1} + s_{2}^{2} Q = −s_{1}^{2}s_{2} − 2s_{2}^{2} + s_{1}s_{2}^{3} − s_{2}^{2}t (k = 3d + 1)

P = 7s_{1} − 5s_{1}^{2}s_{2} + 3s_{2}^{2} + s_{1}^{3}s_{2}^{2} − s_{1}s_{2}^{3} + 4s_{1}t − 2s_{1}^{2}s_{2}t + s_{2}^{2}t + s_{1}t^{2} (k = 3d − 1)

Q = 2s_{1}^{2}s_{2} + 4s_{2}^{2} − 4s_{1}s_{2}^{3} + s_{2}^{5}.

Proposition 5.3. Let P_{i} and Q_{i} be the polynomials such that to Δ(A_{3d+i} ) = P_{i} + dQ_{i} (Proposition 5.2). Then the remainders of these polynomials on division by the Gröbner basis G = G_{trib} are

\overline{P_{0}}^{G} = 0  \overline{Q_{0}}^{G} = s_{2}^{2}
\overline{P_{1}}^{G} = −s_{1} + s_{2}^{2}  \overline{Q_{1}}^{G} = s_{2}^{2}
\overline{P_{−1}} ^{G} = s_{1}  \overline{Q_{−1}} ^{G} = s_{2}^{2}

The analysis similar to the proof of Theorem 5.1 leads to the following result.

Theorem 5.2. Let T_{N} = T_{3k} be the ℤ_{3}-symmetric triangular region in the hexagonal lattice which has 3k hexagons on one of its sides. Then T_{N} admits a ℤ_{3}-symmetric, signed tiling by three-in-line polyominoes (tribones) if and only if k = 9r for some integer r. The first such triangle is T_{27}.

5.2. Examples illustrating Theorems 5.1 and 5.2. Here we describe explicit ℤ_{3}-invariant tilings predicted by Theorems 5.1 and 5.2. We begin with the case N = 3k − 1 = 27r − 1. Figure 13 describes a decomposition of the triangular region T_{N} into triangular and rhombic blocks. The side length of the triangle with the vertices axy^{k}, ax^{k−1} y^{k}, ax^{k−1} y^{2k−2} is k − 1 = 9r − 1 so by Theorem 1.1 this triangle admits a signed tiling by tribones. The side length of the rhombus with vertices a, ax^{k−1} , ay^{k−1} , a(xy)^{k−1} is k = 9r so it can be paved by tribones. This signed tiling is extended to the whole region T_{N} by rotations through the angle of 120^{∘} and 240^{∘}.

The case N = 3k = 27r is treated similarly. The intersection of T_{3k} with the angle xOy is the trapeze with vertices at a, ax^{k}, ay^{k−1} , ax^{2k−1} y^{k−1} (Section 5.1). This trapeze is divided into a rhombus, with vertices at a, ax^{k−1} , ay^{k−1} , a(xy)^{k−1} and an equilateral triangle with vertices at ax^{k}, ax^{k}y^{k−1} , ax^{2k−1} y^{k−1} . Both figures admit a (signed) tribone tiling. Indeed, the triangle has the side length k = 9r (and Theorem 1.1 applies) while the side length of the rhombus is as before k = 9r.

6. Concluding remarks, examples and questions

Our main objective was to illustrate the method of Gröbner bases in the case of equivariant tribone tilings of the hexagonal lattice. However the method has many other advantages and some of them were mentioned already in the original paper of Bodini and Nouvel [5].

Perhaps the main reason why this method is so well adapted for lattice tiling problem is its close connection with the already developed methods and tools used in lattice geometry.

6.1. Integer-point transform and Brion’s theorem. Following [2] and [3], we define the integer-point transform of a finite subset K ⊂ ℕ^{2} as the polynomial f_{K} = ∑ {x^{α} y^{β} | (α, β) ∈ ℕ^{2}}.

Brion’s formula, see [2, Chapter 8] and [3, Section 9.3], is a versatile tool for evaluating the integer-point transform of convex polytopes. It allows us to replace a polynomial with a large number of monomials by a very short expression involving only rational functions. It was tacitly used throughout the paper for an independent checking of some of the formulas. More systematic application of these ideas will be presented in [12].

6.2. Integer-point enumeration in polyhedra. Let P be a convex polytope with vertices in ℕ^{d} and let f_{P} be its integer-point transform. The ‘discrete volume’ of Q, defined as the number of integer points inside P, can be evaluated as the remainder of f_{P} 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 polynomial f_{Q} on division by the Gröbner basis G.

Acknowledgement. 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, 2007.

4. T. Becker, V. Weispfenning, Gröbner Bases, Springer-Verlag, New York, 1993.

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

6. J. H. Conway, J. C. Lagarias, Tiling with Polyominoes and Combinatorial Group Theory, J. Combin. 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, American Mathematical Society, Providence, 2007.

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

11. D. Lichtblau, Revisiting strong Gröbner bases over Euclidean domains, Wolfram Library Archive, http://library.wolfram.com/infocenter/MathSource/7522 .

12. M. Muzika Dizdarević, M. Timotijević, R. T. Živaljević, Signed polyomino tilings by n-in-line polyominoes and Gröbner bases, arXiv:1409.2745 [math.CO].

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

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

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

Faculty of Natural Sciences and Mathematics (Received 13 03 2015) Sarajevo Bosnia and Herzegovina

   mmuzika@me.com

Mathematical Institute SASA

Belgrade, Serbia

   rade@mi.sanu.ac.rs