Signed polyomino tilings by n-in-line polyominoes and Gröbner bases

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 ∈ 2 {9d-1, 9d}d∈N. 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 ∈ {dn2 - 1, dn2}d∈N. 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.