Signed Polyomino Tilings By $n$-in-Line Polyominoes and Gröbner Bases


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




Conway and Lagarias observed that a triangular region $T(m)$ in a hexagonal lattice admits a \emph{signed tiling} by three-in-line polyominoes (tribones) if and only if $m\in\{9d-1,9d\}_{d\in\mathbb{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ı \{dn^2-1,dn^2\}_{dı\mathbb{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 \emph{tile homology group} for the $n$-in-line polyomino.