GRÖBNER LATTICE-POINT ENUMERATORS AND SIGNED TILING BY k-IN-LINE POLYOMINOES

Abstract

Conway and Lagarias observed that a triangular region T<inf>2</inf>(n) in a hexagonal lattice admits a signed tiling by 3-in-line polyominoes (tribones) if and only if n ∈ {3²d−1,3²d}<inf>d</inf>∈N. We apply the theory of Gröbner bases over integers to show that T<inf>3</inf>(n), a three dimensional lattice tetrahedron of edge-length n, admits a signed tiling by tribones if and only if n ∈ {3³d−2,3³d−1,3³d}<inf>d</inf>∈N. More generally we study Gröbner lattice-point enumerators of lattice polytopes and show that they are (modular) quasipolynomials in the case of k-in-line polyominoes. As an example of the “unusual cancelation phenomenon”, arising only in signed tilings, we exhibit a configuration of 15 tribones in the 3-space such that exactly one lattice point is covered by an odd number of tiles.