%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{83}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}


\newcommand{\mbb}{\mathbb}
\newcommand{\mbf}{\mathbf}
\newcommand{\Z}{\mbb Z}
\renewcommand{\a}{\mf a}
\renewcommand{\b}{\mf b}
\newcommand{\p}{\mf p}
\newcommand{\q}{\mf q}
\newcommand{\m}{\mf m}
\newcommand{\R}{\mbb R}
\newcommand{\C}{\mbb C}
\newcommand{\Q}{\mbb Q}
\newcommand{\N}{\mbb N}
\newcommand{\E}{\mathcal E}
\newcommand{\B}{\mathcal B}
\newcommand{\I}{\mathcal I}
\DeclareMathOperator{\Ima}{Im}
\renewcommand{\S}{\mathcal S}
\renewcommand{\P}{\mbb P}
\renewcommand{\hat}{\widehat}
\newcommand{\F}{\mathcal F}
\newcommand{\lr}{\leftrightarrow}
\newcommand{\mf}{\mathfrak}
\newcommand{\im}{\text{im}}
\newcommand{\Tor}{\text{Tor}}
\newcommand{\hto}{\hookrightarrow}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\xto}{\xrightarrow}
\newcommand{\vp}{\varphi}
\newcommand{\ilim}{\varprojlim}
\newcommand{\verteq}{\rotatebox{90}{$\,=$}}
\newcommand{\what}{\widehat}
\newcommand{\oline}{\overline}
\newcommand{\w}{\mathbf w}
\newcommand{\wsplit}{\begin{bmatrix}\w' \\ \w''\end{bmatrix}}
\newcommand{\splitmat}[2]{\begin{bmatrix} #1 & #2 \end{bmatrix}} 
\newcommand{\supp}{\mathbbm{1}}

\newcommand{\FacetsetO}[2]{{\oline{\mathbf F}^{#1}_{(#2)}(M)}}
\newcommand{\Facetset}[2]{{\mathbf F^{#1}_{(#2)}(M)}}
\newcommand{\Facet}[3]{{F^{#1}_{#3}(S_{#2}(M))}}
\newcommand{\SFacet}[3]{{\widetilde F^{#1}_{#3}(S_{#2}(M))}}
\newcommand{\PFacet}[2]{{\mbf F^{+}_{(#1,#2)}(M)}}
\newcommand{\NFacet}[2]{{\mbf F^{-}_{(#1,#2)}(M)}}
\newcommand{\Ztope}[1]{Z_{\what #1}(M)}
\newcommand{\parp}{{\Pi}}
\newcommand{\jparp}{{\Pi_{\hat j}}}
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\isgn}{isgn}
\DeclareMathOperator{\osgn}{osgn}
\DeclareMathOperator{\dsgn}{dsgn}
\DeclareMathOperator{\tsgn}{tsgn}
\DeclareMathOperator{\wsgn}{{\mbf w}sgn}
\DeclareMathOperator{\cl}{cl}
%\DeclareMathOperator{\tsgn}{tsgn}
\newcommand{\proj}{p_r}
\newcommand{\nproj}{\what p_{k}}

\DeclareMathOperator{\slice}{slice}
\newcommand{\rRestrict}{\slice_r} % TO CHANGE
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{enumitem}
\usepackage{breqn} % Allows parentheses over multiple lines with dmath
\usepackage{amsmath,amssymb,amsthm}
\usepackage{graphicx}
\usepackage{blkarray, bigstrut} 
\usepackage{tikz}

%\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{calc}
\usetikzlibrary{patterns}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{algorithm}[theorem]{Algorithm}
\theoremstyle{definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}

\usepackage{array}
\newcolumntype{C}{>{\centering\arraybackslash}p{10pt}}
\newcolumntype{X}{>{\centering\arraybackslash}p{22pt}}



%Colors for colorblind equity
\definecolor{orange}{rgb}{0.898, 0.621, 0.0}
\definecolor{skyblue}{rgb}{0.336, 0.703, 0.910}
\definecolor{bluishgreen}{rgb}{0, 0.617, 0.449}
\definecolor{yellow}{rgb}{0.937, 0.890, 0.258}
\definecolor{blue}{rgb}{0, 0.445, 0.695}
\definecolor{red}{rgb}{0.832, 0.367, 0}
\definecolor{purple}{rgb}{0.797, 0.473, 0.652}





































\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{lipsum}

%% define your title in the usual way
\title{Fragmenting any Parallelepiped into a Signed Tiling}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Joseph Doolittle\thanks{\href{mailto:jdoolittle@tugraz.at}{jdoolittle@tugraz.at}. Joseph Doolittle was supported by the Austrian Science Fund FWF, Project P 33278. 
Their work was also supported by the ANR-FWF International Cooperation Project PAGCAP, funded by the FWF Project I 5788.}\addressmark{1} \and Alex McDonough\thanks{\href{mailto:amcd@ucdavis.edu}{amcd@ucdavis.edu}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Institute of Geometry, TU Graz, Graz, Austria \\ \addressmark{2}Department of Mathematics, University of California, Davis, CA, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{It is broadly known that any parallelepiped tiles space by translating copies of itself along its edges. 
In earlier work relating to higher-dimensional sandpile groups, the second author discovered a novel construction which fragments the parallelpiped into a collection of smaller tiles. 
These tiles fill space with the same symmetry as the larger parallelepiped.
Their volumes are equal to the components of the multi-row Laplace determinant expansion, so this construction only works when all these signs are non-negative (or non-positive).

In this work, we extend the construction to work for all parallelepipeds, without requiring the non-negative condition.
This naturally gives tiles with negative volume, which we understand to mean canceling out tiles with positive volume.
In fact, with this cancellation, we prove that every point in space is contained in exactly one more tile with positive volume than tile with negative volume.
This is a natural definition for a signed tiling.

Our main technique is to show that the net number of signed tiles doesn't change as a point moves through space.
This is a relatively indirect proof method, and the underlying structure of these tilings remains mysterious.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{periodic tiling, signed tiling, parallelepiped, determinant expansion}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction}

To motivate our work, we begin with an illustrative two-dimensional example of our main construction. 
Consider the matrices
\[K = \begin{bmatrix} 1 & 2 \\ -1 & 3\end{bmatrix}, \hspace{1cm} S_{\{1\}}(K) = \begin{bmatrix} 1 & 0 \\ 0 & -3 \end{bmatrix},\hspace{.5 cm} \text{ and }\hspace{.5cm}S_{\{2\}}(K) = \begin{bmatrix} 0 & 2 \\ 1 & 0 \end{bmatrix}.\]

The matrices $S_{\{1\}}(K)$ and $S_{\{2\}}(K)$ are called the \emph{fragment matrices} of $K$. 
They are obtained by negating the second row and then zeroing out a diagonal. 
Directly from the Laplace expansion for determinants, we can see that \[-\det(K) = \det(S_{\{1\}}(K)) + \det(S_{\{2\}}(K)).\]

Given a matrix $N$, let $\Pi(N)$ be the (half-open) \textit{fundamental parallelepiped} of $N$ (see Definition~\ref{def:halfopen} for details). It is broadly known that for any nonsingular matrix $N$, copies of $\parp(N)$ can be used to form a periodic tiling of space. For example, the tiling on the left of Figure~\ref{fig:basictile} is formed by copies of the parallelepiped $\parp(K)$ that are translated by the integer linear combinations of columns of $K$ (see Lemma~\ref{lem:basictiling}). 

Curiously, there also exists a tiling on the same lattice that is formed by the parallelepipeds $\parp(S_{\{1\}}(K))$, and $\parp(S_{\{2\}}(K))$. In particular, the tiling on the right of Figure~\ref{fig:basictile} is formed by $\parp(S_{\{1\}}(K))$ and $\Pi(S_{\{2\}}(K))$, along with their translates by all of the integer combinations of columns of $K$. 

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale = 0.45]
    \tikzstyle{every node} = [shape = none,fill=none,inner sep=1pt,minimum size = .1mm];
\begin{scope}
    \clip (-5,-5) rectangle (5,5);
    
\draw (-5,5) -- (5,-5);
\draw (-3,8) -- (7,-2);
\draw[fill=purple!60] (-5,-5) -- (5,-5) --(5,5) -- (-5,5) --cycle;

\foreach \i in {-5,-4,-3,-2,-1,0,1,2,3,4,5}{
\draw (-5+\i*2,5 + \i*3) -- (5+\i*2,-5+\i*3);
\draw (-20+\i,-30 - \i) -- (20+\i,30 - \i);}

\draw[line width = 1 mm] (0,0) -- (1,-1) --(3,2) -- (2,3) --cycle;
\node[shape = circle, minimum size = 2 mm, fill = black] at (0,0){};
\end{scope}
\begin{scope}[shift = {(12,0)}]
    \clip (-5,-5) rectangle (5,5);
    
\foreach \i in {-5,-4,-3,-2,-1,0,1,2,3,4,5}
\foreach \j in {-2,-1,0,1,2}
{
\begin{scope}[shift = {(\i +2*\j,-\i + 3*\j)}]
\draw[fill=red!70] (0,0) -- (1,0) --(1,-3) -- (0,-3) --cycle;
\draw[fill=blue!60] (0,0) -- (2,0) -- (2,1) -- (0,1) -- cycle;
\end{scope}}
\draw[line width = 1 mm] (0,0) -- (1,0) --(1,-3) -- (0,-3) --cycle;
\draw[line width = 1 mm] (0,0) -- (2,0) --(2,1) -- (0,1) --cycle;
\node[shape = circle, minimum size = 2 mm, fill = black] at (0,0){};

\foreach \i in {-5,-4,-3,-2,-1,0,1,2,3,4,5}{
\draw[dotted] (-5+\i*2,5 + \i*3) -- (5+\i*2,-5+\i*3);
\draw[dotted] (-20+\i,-30 - \i) -- (20+\i,30 - \i);}
\end{scope}
\end{tikzpicture}
\caption{On the left is the tiling given by translations of the parallelepiped $\prod(K)$. On the right is the tiling given by translations of the fundamental parallelepipeds of the \emph{fragment matrices} $S_{\{1\}}(K)$ and $S_{\{2\}}(K)$.}
\label{fig:basictile}
\end{center}
\end{figure}

%Given any $2 \times 2$ matrix $N$, one can define the matrices $S_{\{1\}}(N)$ and $S_{\{2\}}(N)$ by negating the second row of $N$ and zeroing a diagonal. One can show that whenever $\det(S_{\{1\}}(N))$ and $\det(S_{\{2\}}(N))$ have the same sign, one can use these matrices to give a periodic tiling of $\R^2$. In particular, the translates of $\Pi(S_{\{1\}}(N))$ and $\Pi(S_{\{1\}}(N))$ by integer linear combinations of the columns of $N$ cover $\R^2$ with no gaps or overlaps.  

This tiling is a two dimensional example of a construction which was introduced by the second author to define \textit{matrix-tree multijections}~\cite{multijections,alexthesis}. 
This construction can be applied to any invertible $(r+k)\times(r+k)$ matrix $M$, and produces a collection of $\binom{r+k}{r}$ \emph{fragment matrices} of $M$. 
When the determinants of the fragment matrices are all non-negative (or all non-positive), translating them by integer linear combinations of the columns of $M$ produces a periodic tiling of $\R^{r+k}$. 

In this paper, we prove that the elegant tiling structure of the fragment matrices is still present even without the restriction on $M$ that all the fragment matrices have non-negative determinant. 
In particular, while the translates do not always form a traditional tiling with no overlap or gaps, they always produce a \emph{signed tiling}.

To illustrate this signed version of the tiling, we give another $2$-dimensional example. 
This time, the determinants of the fragment matrices have opposite signs. 

Let
\[L = \begin{bmatrix} 1 & 2 \\ 1 & 5\end{bmatrix}, \hspace{1cm} S_{\{1\}}(L) = \begin{bmatrix} 1 & 0 \\ 0 & -5 \end{bmatrix},\hspace{.5 cm} \text{ and }\hspace{.5cm}S_{\{2\}}(L) = \begin{bmatrix} 0 & 2 \\ -1 & 0 \end{bmatrix}.\]

As in the previous example, the fragment matrices $S_{\{1\}}(L)$ and $S_{\{2\}}(L)$ are formed by negating the second row and zeroing a diagonal. 
Next, we consider translates of the fragment matrices by integer linear combinations of the columns of $L$. 
In this case, the tiles no longer perfectly fill space, and instead overlap, see Figure~\ref{fig:signedtile}.

In our previous example, the determinants of $S_{\{1\}}(K)$ and $S_{\{2\}}(K)$ were both negative.
In this example, $S_{\{1\}}(L)$ is negative, but $S_{\{2\}}(L)$ is positive.
Moreover, the positively signed tiles overlap.
Nevertheless, an elegant tiling structure can still be found. %the union of the negative tiles occupies exactly the same part of space as the overlapping portion of the positive tiles.
%By adding the negative tiles and preserving their negative nature, we cancel out the overlapping parts of the positive tiles, and once again have exactly one (signed) tile in every point in the plane.



\begin{figure}
\begin{center}
\begin{tikzpicture}[scale = 0.5]
    \tikzstyle{every node} = [shape = none,fill=none,inner sep=1pt,minimum size = .1mm];
    
\begin{scope}
    \clip (-5,-5) rectangle (5,5);
\foreach \i in {-20,...,20}
\foreach \j in {-4,...,4}
{
\begin{scope}[shift = {(\i +2*\j,\i + 5*\j)}]
\draw[fill=red!40] (0,0) -- (0,1) --(1,1) -- (1,0) --cycle;
\draw[fill=red!40] (1,3) -- (1,4) --(0,4) -- (0,3) --cycle;
\draw[fill=red!100] (0,1) -- (0,3) -- (1,3) -- (1,1) -- cycle;
\end{scope}}
\node[shape = circle, minimum size = 2 mm, fill = black] at (0,0){};
\draw[line width = 1 mm] (0,0) -- (1,0) --(1,-5) -- (0,-5) --cycle;

\foreach \i in {-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10}{
\draw[dotted] (-20+\i*2,-20 + \i*5) -- (20+\i*2,20 + \i*5);
\draw[dotted] (-20+\i,-50 + \i) -- (20+\i,50 + \i);}
\end{scope}

\begin{scope}[shift = {(12,0)}]
    \clip (-5,-5) rectangle (5,5);
\foreach \i in {-20,...,20}
\foreach \j in {-4,...,4}
{
\begin{scope}[shift = {(\i +2*\j,\i + 5*\j)}]
\draw[fill=blue!40] (0,0) -- (2,0) -- (2,-1) -- (0,-1) -- cycle;
\end{scope}}
\node[shape = circle, minimum size = 2 mm, fill = black] at (0,0){};
\draw[line width = 1 mm] (0,0) -- (2,0) --(2,-1) -- (0,-1) --cycle;

\foreach \i in {-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10}{
\draw[dotted] (-20+\i*2,-20 + \i*5) -- (20+\i*2,20 + \i*5);
\draw[dotted] (-20+\i,-50 + \i) -- (20+\i,50 + \i);}
\end{scope}

\end{tikzpicture}
\caption{On the left is the tiling obtained by translating the fundamental parallelepipeds of $S_{\{1\}}(L)$ by integer combinations of columns of $L$. 
The darker regions indicate where two parallelepipeds overlap, while the lighter region is the portion covered by a single parallelepiped. 
On the right is the tiling obtained by translating the fundamental parallelepipeds of $S_{\{2\}}(L)$ by integer combinations of columns of $L$. 
This time, there are no overlaps, but the white region is formed by gaps between parallelepipeds. 
By Theorem~\ref{thm:mainthm}, the shaded region on the right precisely corresponds to the darker region on the left.}
\label{fig:signedtile}
\end{center}
\end{figure}


Consider the two partial tilings given in Figure~\ref{fig:signedtile}. Every point in the plane is covered by either one translate of $\Pi(S_{\{1\}}(L))$ or two translates of $\Pi(S_{\{1\}}(L))$ and one translate of $\Pi(S_{\{2\}}(L))$. 
This means that if we define translates of $\Pi(S_{\{1\}}(L))$ to be \textit{positive} tiles and translates of $\Pi(S_{\{2\}}(L))$ to be \textit{negative} tiles, then for any point $\mbf p \in \R^2$, the signed total of all tiles containing $\mbf p$ is always $1$. 

This surprising alignment of positive and negative tiles works in general. 
Reiterating the previous setting, we let \(M\) be an invertible \((r+k)\times (r+k)\) matrix.
We break this matrix into two parts, the first \(r\) rows and the last \(k\) rows.
The two tiles from the two dimensional case become \(\binom{r+k}{r}\) many tiles, indexed by which \(r\) columns are preserved in the top $r$ rows (see Definition~\ref{def:fragment} for details). 

We generalize the cancellation observed in the example with \(L\) by introducing a function \(f\). This function counts the number of positively signed tiles at a point, minus the number of negatively signed tiles at that point. Our main result is the following. 


\vspace{2 ex}
\noindent\textbf{Theorem~\ref{thm:mainthm}.} \textit{
 The function \(f: \R^{r+k} \to \Z\), defined by
    \begin{equation*}f(\mbf p) := \left(\sum_{T \in \mathbf T^+(M)}  \supp_{T}(\mbf p)\right) - \left(\sum_{T \in \mathbf T^-(M)}  \supp_{T}(\mbf p)\right),\end{equation*}
    is constant with value $(-1)^{k}\sgn(\det(M))$. 
}\vspace{2 ex}

In Section~\ref{sec:construction}, we describe the general construction and introduce the notation necessary to understand the statement of Theorem~\ref{thm:mainthm}. In Section~\ref{sec:proof}, we give a high level description of the general proof argument. In Section~\ref{sec:examples}, we give an example of a four dimensional signed tiling, which we visualize in 2 dimensions. Finally, in Section~\ref{sec:questions}, we consider future extensions and pose questions we think will be interesting to explore. For more details, see our full paper on ArXiv~\cite{OurPaper}. 

\section{Signed Tiling Construction}\label{sec:construction}

Fix positive integers $r$ and $k$ as well as an $(r+k)\times (r+k)$ matrix $M$ with real entries. Additionally, fix a generic direction vector $\mbf w \in \R^{r+k}$. More precisely, $\mbf w$ can be anything but a set of measure 0 that depends on $N$. 

\begin{remark}\label{rem:generic}
    Even more precisely, $\mbf w$ is sufficiently generic for our purposes if it is not spanned by any collection of $r+k-1$ column vectors of any of the $(r+k) \times (r+k)$ matrices we will be working with. Specifically, these matrices are $M$ along with $S_\sigma(M)$ for $\sigma \in \binom{[r+k]}{r}$ (See Definition~\ref{def:fragment}). 
\end{remark}

In this paper, we work extensively with parallelepipeds. The vector $\mbf w$ gives a consistent way to define \emph{half-open parallelepipeds}. 
\begin{definition}\label{def:halfopen} 
Let $N$ be an $(r+k) \times (r+k)$ matrix with real entries. Define $\parp(N)$ to be the set of $\mbf p \in \R^{r+k}$ such that for all sufficiently small $\epsilon >0$, the point $\mbf p + \epsilon\w$ is in 
\begin{equation*}\label{eq:closure}\sum_{i \in [r+k]}\left\{x_iN_i: 0 \le x_i \le 1\right\}.\end{equation*}
The set $\parp(N)$ is called the \emph{(half-open) parallelepiped of $N$ (with respect to $\w$)}. 
\end{definition}

Although Definition~\ref{def:halfopen} depends on $\mbf w$, we omit it in our notation for conciseness. 

\begin{remark}The genericity conditions for $\mbf w$ (which are discussed in Remark~\ref{rem:generic}) are precisely the conditions necessary to ensure the following condition. For all matrices $N$ that we will be working with and all points $\mbf p\in \mathbb R^{r+k}$, there exists some $\epsilon>0$ such that the segment from $\mbf p$ to $\mbf p + \epsilon \mbf w$ does not intersect the boundary of the fundamental parallelepiped of $N$ (except possibly at $\mbf p$). \end{remark}

Before we get to our first lemma, let us quickly clarify some confusing notation. The term \emph{disjoint union} can be used in two different ways in mathematics, so we will denote these with two different symbols. For sets $A$ and $B$, we write $A\bigsqcup B$ for the set $A\cup B$ with the added restriction that $A\cap B = \emptyset$. We use the notation $A \biguplus B$ to indicate the other kind of disjoint union, where $A$ and $B$ are considered as separate objects.

We now present a simple observation about translating parallelepipeds, which will be the foundation of our construction. 

\begin{lemma}\label{lem:basictiling}
    For any choice of $M$, we have 
    \begin{equation*}\label{eq:basictiling}
    \mbb{R}^{r+k} = \bigsqcup_{\mbf {z} \in \mbb {Z}^{r+k}} \left(\parp(M) + M\mbf z\right).
    \end{equation*}
\end{lemma}

This lemma follows from the fact that the unit cube tiles space, and the displacement between cubes in this tiling is all \(\mbb Z\)-valued vectors.
The lemma describes this same tiling, after applying \(M\) as a linear transformation. Our main construction is of a more complicated tiling under the same translation lattice, which is formed by \emph{fragmenting} $M$. 

\begin{definition}\label{def:fragment}
Let $\sigma \in \binom{[r+k]}{r}$, i.e., $\sigma \subset [r+k]$ with $|\sigma| = r$. The \emph{\(\sigma\)-fragment matrix} of \(M\), written $S_\sigma(M)$, is the matrix obtained from $M$ by the following $3$ step process: 
\begin{enumerate}
    \item For each $i \not\in \sigma$, replace the \emph{first} $r$ entries of column $i$ with $0$. 
    \item For each $i \in \sigma$, replace the \emph{last} $k$ entries of column $i$ with $0$. 
    \item Negate all of the entries in the last $k$ rows. 
\end{enumerate}
\end{definition}

\begin{example}\label{ex:first}

Let $r=k = 2$. Any $(r+k) \times (r+k)$ matrix $M$ has $6$ associated fragment matrices corresponding to the subsets of $\binom{[4]}{2}$. For example, if \[M = \begin{bmatrix} 
3 & 2 & -4 & 1\\
1 & 0 & 2 & 2\\
2 & 0 & -1 & 1\\
0 & 1 & -2 & 3\\
\end{bmatrix} \text{ and } \sigma = \{1,4\} \text{, then }S_{\sigma}(M) =\begin{bmatrix} 
3 & 0 & 0 & 1\\
1 & 0 & 0 & 2\\
0 & 0 & 1 & 0\\
0 & -1 & 2 & 0\\
\end{bmatrix}.\]
\end{example}

To form a signed tiling, we parameterize tiles formed by translating the fundamental parallelepiped of fragment matrices by integer combinations of the columns of $M$. 

\begin{definition}\label{def:tile}
For any $\mbf z \in \Z^{r+k}$ and $\sigma \in \binom{[r+k]}{r}$, the \emph{tile} parameterized by the pair \((\mbf z, \sigma)\) is defined as
    \[\mathcal T(\mbf z, \sigma) := \parp(S_{\sigma}(M))+M\mbf z.\]
\end{definition}

Note that since $\parp(S_{\sigma}(M))$ depends on $\w$, the tile $\mathcal T(\mbf z,\sigma)$ will depend on $\w$ as well. Nevertheless, the precise choice of $\w$ is not important for our results as long as it remains fixed (and sufficiently generic, see Remark~\ref{rem:generic}). Also, note that we usually think of a tile $\mathcal T(\mbf z, \sigma)$ as a polytope made up of a collection of points, not the points themselves. With this perspective in mind, we introduce the following definition. 

\begin{definition}\label{def:tilesets} 
Consider the sets of tiles
\begin{align*}{\mathbf T}^+(M) :&= \biguplus_{\mbf z \in \Z^{r+k}} \left( \biguplus_{\sigma \in \binom{[r+k]}{r},~\det(S_\sigma(M))>0} \mathcal T(\mbf z, \sigma) \right),\\
\text{and }{\mathbf T}^-(M) :&=  \biguplus_{\mbf z \in \Z^{r+k}}  \left( \biguplus_{ \sigma \in \binom{[r+k]}{r},~\det(S_\sigma(M))<0} \mathcal T(\mbf z, \sigma) \right). \end{align*}
The set ${\mathbf T}^+(M)$ is called the set of \emph{positive tiles}, while  ${\mathbf T}^-(M)$ is called the set of \emph{negative tiles}. 
We also write ${\mathbf T}(M) := {\mathbf T}^+(M) \biguplus {\mathbf T}^-(M)$. 
Note that we don't include the tiles where \(\det(S_\sigma(M))=0\), but in this case, \(S_\sigma(M)\) is not invertible, and \(\parp(S_\sigma(M))\) is empty.
\end{definition}

Definition~\ref{def:tilesets} allows us to cleanly state our main result. Note that we write $\supp_{T}$ for the \emph{indicator function} of a tile $T$. 

\begin{theorem}\label{thm:mainthm} The function \(f: \R^{r+k} \to \Z\), defined by
    \begin{equation*}\label{eq:mainthm}f(\mbf p) := \left(\sum_{T \in {\mathbf T}^+(M)}  \supp_{T}(\mbf p)\right) - \left(\sum_{T \in {\mathbf T}^-(M)}  \supp_{T}(\mbf p)\right),\end{equation*}
    is constant with value $(-1)^{k}\sgn(\det(M))$. 
\end{theorem} 

When one of  ${\mathbf T}^+(M)$ or ${\mathbf T}^-(M)$ is empty, Theorem~\ref{thm:mainthm} specializes to a result about more traditional tilings. For this result, we will treat each $\mathcal T(\mbf z,\sigma)$ as a collection of points in $\R^{r+k}$.
We state only the version where ${\mathbf T}^-(M)$ is empty, but the same statement holds if ``non-negative'' is replaced with ``non-positive''. 

\begin{corollary}\label{cor:traditionaltiling}
{\cite[Corollary~9.2.8]{alexthesis}}
    If the sign of $\det(S_\sigma(M))$ is non-negative for each $\sigma \in \binom{[r+k]}{r}$, then
    \[\R^{r+k} = \bigsqcup_{\mbf z \in \mbb Z} \left( \bigsqcup_{\sigma \in \binom{[r+k]}{r}} \mathcal T(\mbf z, \sigma) \right).\] 
\end{corollary}

\begin{remark}
    The conditions required on $M$ for Corollary~\ref{cor:traditionaltiling} to apply are discussed in~\cite[Section~6.7]{alexthesis}. 
    The original proof of the corollary relies on these properties, so we needed different methods to prove the more general Theorem~\ref{thm:mainthm}. 
    A special case of Corollary~\ref{cor:traditionaltiling} was used in~\cite{multijections} to define a family of \emph{multijections} between the \emph{sandpile group} and \emph{cellular spanning forests} for a large class of cell complexes. This generalizes a construction of Backman Baker and Yuen which used \emph{zonotopal tilings} to answer questions about \emph{chip-firing} on \emph{regular matroids}\cite{BBY}. 
\end{remark}
 
\section{An Outline of the Proof}\label{sec:proof}
Our proof of Theorem~\ref{thm:mainthm} is structured in the following way. 
\begin{enumerate}
    \item First, we show that the average value of $f$ is $(-1)^k\sgn(\det(M))$. 
    \item Next, we group the facets of the tiles into collections that lie in the same hyperplane. 
    \item After this, we imagine a particle crossing a point contained in one of these collections of facets. We show that when doing so, it crosses exactly two facets. Furthermore, in one crossing it \emph{enters} a \emph{positive} tile or \emph{exits} a \emph{negative} tile, while in the other crossing, it \emph{exits} a \emph{positive} tile or \emph{enters} a \emph{negative} tile.
    \item From these observations, we conclude that $f$ is constant. Theorem~\ref{thm:mainthm} then follows from our first observation. 
\end{enumerate}

To find the average value of $f$, we use the multiple row version of Laplace's determinant expansion formula as well as some basic calculus techniques. One important observation is the following chain of equalities, which holds for any $\sigma \in \binom{[r+k]}{r}$. 

\begin{equation*}\sum_{\mbf z \in \Z^{r+k}} \int_{\parp(M)}\supp_{\mathcal T(\mbf z,\sigma)}(\mbf x) \mathrm d \mbf x 
= \int_{\R^{r+k}}\supp_{\mathcal T(\mbf 0,\sigma)}(\mbf x) \mathrm d\mbf x =
 \int_{\R^{r+k}}\supp_{\parp(S_\sigma(M))}(\mbf x) \mathrm d\mbf x  
= |\det(S_\sigma(M))|.
\end{equation*}


The longest and most technical part of our proof is the facet grouping result. This argument required careful bookkeeping and several applications of Cramer's rule. 

\section{Lower Dimensional Slices} \label{sec:examples}

While Theorem~\ref{thm:mainthm} gives a signed tiling of $\R^{r+k}$, it is also possible to visualize the tiling in $\R^k$ or $\R^r$ by fixing the first $r$ or last $k$ entries respectively. We conclude with an example of a 2-dimensional slice of a 4-dimensional signed tiling. 


\begin{example} \label{ex:posnegtiles} 
For the matrix $M$ from Example~\ref{ex:first}, the set ${\mathbf T}(M)$ consists of $6$ families of $4$-dimensional parallelepipeds, where each family contains infinitely many translations of a single fragment. 

By taking the determinant of each fragment, we find that \begin{align*}{\mathbf T}^+(M) &= \bigsqcup_{\mbf z \in \Z^{r+k}} \left( \bigsqcup_{\sigma \in \{(1,2),(1,3),(1,4),(2,3),(2,4)\}} \mathcal T(\mbf z, \sigma) \right),\text{ and}\\
{\mathbf T}^-(M) &= \bigsqcup_{\mbf z \in \Z^{r+k}} \mathcal T(\mbf z, \{3,4\}). \end{align*}


Confirming that Theorem~\ref{thm:mainthm} holds for this example is not a completely straightforward task, even with the help of a computer. Nevertheless, regardless of the choice of $\w$, one can show that each $\mbf p \in\R^4$ is contained in 
\begin{itemize}
    \item one tile in ${\mathbf T}^+(M)$ and no tiles in ${\mathbf T}^-(M)$,
    \item two tiles in ${\mathbf T}^+(M)$ and one tile in ${\mathbf T}^-(M)$, or
    \item three tiles in ${\mathbf T}^+(M)$ and two tiles in ${\mathbf T}^-(M)$.
\end{itemize}
In each case, the value of $f(\mbf p)$ is $1$, which is also the sign of $\det(M)$. 

It is possible to visualize this tiling by taking a 2-dimensional slice which fixes the last $2$ coordinates in $\R^4$. Each of the six families of tiles are given in Figure~\ref{fig:6projectedtiles}. In Figure~\ref{fig:phonecase}, we combine the positive tiles and the negative tiles. Notice that if the negative tiles are ``subtracted'' from the positive tiles, the region formed by the difference covers the plane. This demonstrates Theorem~\ref{thm:mainthm}. 

\end{example}

\begin{figure}
\begin{center}
\begin{tabular}{ccc}
    
\includegraphics[width=.3\linewidth]{emphtile0.png} & 
\includegraphics[width=.3\linewidth]{emphtile1.png}&
\includegraphics[width=.3\linewidth]{emphtile2.png} \\
$\det(S_{\{1,2\}}(M)) = 2$ & $\det(S_{\{1,3\}}(M)) = 10$ & $\det(S_{\{1,4\}}(M)) = 5$ \\

   
\includegraphics[width=.3\linewidth]{emphtile3.png}  & 
\includegraphics[width=.3\linewidth]{emphtile4.png} &
\includegraphics[width=.3\linewidth]{emphtile5.png}\\
$\det(S_{\{2,3\}}(M)) = 24$ & $\det(S_{\{2,4\}}(M)) = 16$ & $\det(S_{\{3,4\}}(M)) = -20$ \\

\end{tabular}
\caption{Here we show the contributions of each of the six classes of tiles in Example~\ref{ex:posnegtiles} to a 2-dimensional slice of the tiling. Notice that the proportion of the plane that is covered by a specific class of tiles (with multiplicity for any overlapping tiles) is proportional to the magnitude of the determinant of the corresponding fragment matrix. }
\label{fig:6projectedtiles}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{cc}
\includegraphics[width = .4\linewidth]{emphtile12340.png}& \includegraphics[width=.4\linewidth]{emphtile5.png}
\end{tabular}
\caption{This image on the left is formed by overlapping the 5 positive tiles in Figure~\ref{fig:6projectedtiles} while the image on the right is given by the single negative tile. By Theorem~\ref{thm:mainthm}, each point is covered by exactly one more positive tile than negative tile.}\label{fig:phonecase}
\end{center}
\end{figure}

\section{Open Problems}\label{sec:questions}

The main motivation for this project was an attempt to gain a deeper understanding of a curious phenomenon (in particular Corollary~\ref{cor:traditionaltiling}). While we were successful at generalizing this statement to Theorem~\ref{thm:mainthm}, this new result is just as surprising. We expect that a deeper exploration of this problem will lead more surprises in the future, and we have several specific directions in mind the explore. 

Our initial approach when attempting to prove Theorem~\ref{thm:mainthm} was to consider an arbitrary point in $\R^{r+k}$ (or $\Pi(M)$) and compute which tiles contain this point. A direct proof of this form would give additional insight about the tiling, since it would allow us to calculate the number and type of tiles containing a given point. However, this method was more challenging than we expected, and we ended up relying on an indirect method by focusing on the facets and proving that $f$ is constant. 
\begin{open} What is the best algorithm to determine which tiles contain a given point? Can such an algorithm be used to give a more direct proof of Theorem~\ref{thm:mainthm}? \end{open}

Another promising method to prove Theorem~\ref{thm:mainthm} is to use Fourier analysis, applying similar methods to those used in~\cite{Ehrhart} (see also~\cite{Robins}). Perhaps these ideas could lead to a more elegant proof once the background is established. 

\begin{open} Is there a proof for Theorem~\ref{thm:mainthm} using Fourier analysis?\end{open} 

In addition to an alternate proof of the main theorem, we would also be interested in generalizing this result. As written, our construction relies on a choice of coordinates. While it should be possible to translate the statement into coordinate-free language, this is not a trivial task. Nevertheless, such a generalization would likely provide additional insight into the underlying phenomenon behind our construction. 

\begin{open} Is there a coordinate-free analogue to Theorem~\ref{thm:mainthm} or Corollary~\ref{cor:traditionaltiling}?\end{open}

\acknowledgements{We would first like to thank the organizers of the 33rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), which is where our exploration of this signed tiling began. 

The first author would like to thank the organizers of the Combinatorial Coworkspace in Kleinwalsertal for providing an engaging environment to discuss this with many people, especially Marie-Charlotte Brandenburg.
They would also like to thank Bennet Goeckner for helpful comments on an earlier draft of this work.

The second author would like to thank Milen Ivanov and Sinai Robins for helping him to understand the analytic perspective as well as Julia Schedler for many lively discussions about the construction and visualizations.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
