%LATEX
\documentstyle[12pt,amssymb,psfig]{article}

\topmargin 0pt
\headsep 0.25in
\textheight 9in
\textwidth 6in
\oddsidemargin 0in
\evensidemargin 0in


\newcommand{\beql}[1]{\begin{equation}\label{#1}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\comment}[1]{}
\newcommand{\Ds}{\displaystyle}
\newcommand{\eqref}[1]{(\ref{#1})}
\newcommand{\Fpart}[1]{{\left\{{#1}\right\}}}
\newcommand{\Abs}[1]{{\left|{#1}\right|}}
\newcommand{\Lone}[1]{{\left\|{#1}\right\|_{L^1}}}
\newcommand{\Linf}[1]{{\left\|{#1}\right\|_\infty}}
\newcommand{\Mean}{{\bf E}}
\newcommand{\Floor}[1]{{\left\lfloor{#1}\right\rfloor}}
\newcommand{\Ceil}[1]{{\left\lceil{#1}\right\rceil}}
%\newcommand{\Qed}{\newline\mbox{$\Box$}}
\newcommand{\Qed}{\newline\mbox{$\blacksquare$}}
\newcommand{\N}{{\bf N}}
\newcommand{\Z}{{\bf Z}}
\newcommand{\Prob}[1]{{{\bf{Pr}}\left[{#1}\right]}}
\newcommand{\Set}[1]{{\left\{{#1}\right\}}}
\newcommand{\given}{{\ |\ }}
\newcommand{\as}{{a.s.}}
\newcommand{\ToAppear}[1]{\raisebox{15mm}[10pt][0mm]{\makebox[0mm]{\makebox[\textwidth][r]{\small #1}}}}
\newcommand{\siirv}{{SIIRV}}
\newcommand{\PP}{{\bf P}}
\newcommand{\RR}{{\bf R}}
\newcommand{\CC}{{\bf C}}
\newcommand{\ZZ}{{\bf Z}}
\newcommand{\NN}{{\bf N}}
\newcommand{\TT}{{\bf T}}
\newcommand{\QQ}{{\bf Q}}
\newcommand{\One}[1]{{\bf 1}\left(#1\right)}
\newcommand{\one}{{\bf 1}}
\newcommand{\BAR}[1]{\overline{#1}}
\newcommand{\inner}[2]{{\langle #1, #2 \rangle}}
\newcommand{\Inner}[2]{{\left\langle #1, #2 \right\rangle}}

%%%%%%%%%%%%% Open Problems %%%%%%%%%%%%%%
\newcounter{open}
\setcounter{open}{0}
\newcommand{\open}[1]{
	\refstepcounter{open}
	\begin{quote} \noindent{\bf Problem \theopen.} #1 \end{quote}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%% My style %%%%%%%%%%%%%%%%%%%

\newcounter{mysec}
\setcounter{mysec}{-1}
\def\themysec{\arabic{mysec}}
\newcommand{\mysection}[1]{
  \vskip 0.25in
  \refstepcounter{mysec}\centerline{\large\bf \S\themysec.\ {#1}}
  \addcontentsline{toc}{section}{{\bf \themysec.}\ {#1}}
}

\newcounter{mysubsec}[mysec]
\setcounter{mysubsec}{-1}
\def\themysubsec{\arabic{mysec}.\arabic{mysubsec}}
\newcommand{\mysubsection}[1]{
  \vskip 0.125in
  \refstepcounter{mysubsec}\noindent{\bf \themysubsec\ \ \ {#1}}\par
  \addcontentsline{toc}{subsection}{\themysubsec.\ {#1}}
}

\renewcommand{\refname}{}
\newcommand{\Toc}{
 \def\contentsname{}
 \noindent\rule{6.5in}{0.5mm}
 \vspace{-2cm}
 {\small \tableofcontents}
 \noindent\rule{6.5in}{0.5mm}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}


\begin{document}


\title{\sc lattice tilings by cubes: whole, notched and extended}
 
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
 
\author{Mihail Kolountzakis\\
Department of Mathematics\\
1409 W. Green St.,\\
University of Illinois,\\
Urbana, IL 61801\\
{\tt kolount@math.uiuc.edu}\\
\ \\
{\em Current Address:}\\
Department of Mathematics\\
University of Crete\\
714 09 Iraklio, Greece\\
{\tt kolount@math.uch.gr}}
 
\date{Submitted: April 14, 1997; Accepted: February 14, 1998.}

\footnotetext{1991 {\em Mathematics Subject Classification}.  Primary 52C22;
Secondary 42.}
 
\maketitle

\pagestyle{myheadings} 
\markright{\sc the electronic journal of combinatorics 5 (1998), \#R14\hfill} 
\thispagestyle{empty} 

%\begin{center}
%Partially supported by NSF grant DMS 97-05775.\\
%\ \\
%Current address: Department of Mathematics, University of Crete,
%714 09 Iraklio Crete, Greece.\\
%E-mail: {\tt kolount@math.uch.gr}}}

%\renewcommand{\baselinestretch}{1.4}     %for double spaced text

\begin{abstract}
We discuss some problems of lattice tiling via Harmonic Analysis
methods.
We consider lattice tilings of $\RR^d$ by the unit cube in relation
to the Minkowski Conjecture (now a theorem of Haj\'os) and give
a new equivalent form of Haj\'os's theorem.
We also consider ``notched cubes'' (a cube from which
a reactangle has been removed from one of the corners)
and show that they admit lattice tilings.
This has also been been proved by S. Stein by a direct geometric method.
Finally, we exhibit a new class of simple shapes
that admit lattice tilings, the ``extended cubes'', which
are unions of two axis-aligned rectangles that share
a vertex and have intersection of odd codimension.

In our approach we consider the Fourier Transform of
the indicator function of the tile and try to exhibit a lattice
of appropriate volume in its zero-set.
\end{abstract}

\newpage

\mysection{Introduction}
\label{sec:intro}

\mysubsection{Results.}
\label{sec:results}
We obtain some results about translational tilings of $\RR^d$
with some simple classes of of polyhedra as tiles (cubes
as well as  ``notched'' and ``extended'' cubes--see \S\ref{sec:notched}
for a definition of the latter shapes).
The approach we use is to study the zero-set of the Fourier Transform
(FT) of the indicator function of the tile.
If that set contains a lattice except $0$ then the set tiles
$\RR^d$ when translated at the locations of the dual lattice.
This means that the translated copies of the tile cover (almost) every
point in $\RR^d$ a constant number of times--see
Theorem \ref{th:spectral-lattice}.

In \S\ref{sec:minkowski} we use our harmonic analysis approach to derive
a new equivalent form of the Minkowski conjecture (every lattice tiling
of $\RR^d$ with the unit cube contains two cubes which share an entire
$(d-1)$-dimensional face) which was proved by Haj\'os \cite{Hajos}
in 1941.
This new form of the Minkowski conjecture (Theorem \ref{th:3rd})
is an elementary number-theoretic statement that involves no
inequalities and could conceivably lead to a new, elementary proof
of the conjecture.

In \S\ref{sec:notched} we prove that certain classes of polyhedra tile
$\RR^d$ if translated by an appropriate lattice.
The notched cube (see Figure \ref{fig:notched}) has already been shown
by Stein \cite{Stein} to tile $\RR^d$ by a lattice (Conlan \cite{Conlan}
has done this in some cases). Stein's method was a direct geometric
one.
We give a new proof that the notched cube is a tile using our approach.
That is, we find lattices in the zero-set of the FT of the indicator
function of the notched cube, which is a very explicit function (see
\eqref{FT}).
We find all the tilings discovered by Stein, which, by a deeper theorem
of Schmerl \cite{Schmerl}, is the complete list of possible
translational tilings (lattice or not) of the notched cube.

However, our approach for the notched cube leads us to the discovery of
a whole class of simple tiles of $\RR^d$ (the ``extended cubes''--see Figure
\ref{fig:extended}), for which we know of no geometric proof of the fact
that they tile.
These tiles consist of two axis-aligned rectangles which share a vertex
and have intersection of odd codimension, and the lengths of their sides
can be completely arbitrary.
The tiling lattices for each of these tiles are very simple to describe.
Furthermore, the proof that the notched cube tiles essentially proves
that the extended cubes tile as well, as the FT of the two indicator
functions (that of the notched cube and of that of the extended cube)
have the same form and differ only at the values of some parameters.

\mysubsection{Translational tiling in $\RR^d$.}
Let $f \in L^1(\RR^d)$ and $A \subset \RR^d$ be a discrete point set.
We say that (the {\em tile}) $f$ tiles $\RR^d$
with (the {\em tile set}) $A$ and
with weight $w$ if for almost all
(Lebesgue) $x\in\RR^d$ we have
\beql{tiling}
\sum_{a\in A} f(x-a) = w,
\eeq
where the series above converges absolutely.
If $f$ is the indicator function of a (measurable) set $T \subset \RR^d$
then we also say that $T$ (the {\em tile}) tiles $\RR^d$ with weight $w$,
which then has to be a nonnegative integer. When $w=1$ we sometimes
write
\beql{direct}
\RR^d = T \oplus A.
\eeq
We restrict our attention to tile sets $A$ of {\em bounded density}.
That is, we demand that
\beql{bdd-density}
\#\left( A \cap (x+[0,1]^d) \right) \le C,
\eeq
for all $x\in\RR^d$ and for some constant $C$,
a requirement which is automatically fulfilled whenever $f \ge 0$. 

\mysubsection{A spectral condition for tiling.}
In \cite{KLa} a necessary and sufficient condition was given 
for \eqref{tiling} to hold.
It was proved for dimension $d=1$ only. Here we state it for
arbitrary $d$.
We ommit the proof as it is identical to
the one-dimensional case.

For a tempered distribution $\mu$ we denote by $\widehat{\mu}$
its Fourier Transform (see for example \cite{Strichartz}).
\begin{theorem}\label{th:spectral}
Assume that $f\in L^1(\RR^d)$ has Fourier Transform
$\widehat{f} \in C^\infty(\RR^d)$ and that the discrete set $A \subset \RR^d$
is of bounded density.
Write
\beql{A-measure}
\mu = \sum_{a \in A} \delta_a,
\eeq
where $\delta_a$ is a point mass at $a$.

{\rm (i)} If $f$ tiles $\RR^d$ with the tile set $A$ and some weight
$w$ then 
\beql{supp}
{\rm supp}\,\widehat{\mu} ~\subseteq~ Z := \Set{0} \cup
	\Set{\xi\in\RR^d:\ \widehat{f}(\xi) = 0}.
\eeq

{\rm (ii)} If $\widehat{\mu}$ is locally a finite measure
and ${\rm supp}\,\widehat{\mu}\subseteq Z$,
then $f$ tiles $\RR^d$ with the tile set $A$ and weight
$\Ds w=\widehat{\mu}(\Set{0}) \int_{\RR^d} f$.
\end{theorem}
Note that the requirement that $\widehat{f} \in C^\infty(\RR)$
is true for all $f$ of compact support.

\mysubsection{Fourier Transform and the Poisson Summation Formula.}
The definition of Fourier Transform we use throughout this paper
is
$$
\widehat{f}(\xi) = \int_{\RR^d} e^{-2\pi i\inner{\xi}{x}} f(x)~dx,
$$
for $f \in L^1(\RR^d)$.

Let $\Lambda = A \ZZ^d$, $A$ a non-singular $n\times n$ real matrix,
be a lattice in $\RR^d$ and write
$$
\Lambda^* = \Set{x\in\RR^d:\ \forall\lambda\in\Lambda\
		\inner{x}{\lambda} \in \ZZ}.
$$
It turns out that $\Lambda^* = A^{-\top}\ZZ^d$
is a lattice which we call the {\em dual} lattice of $\Lambda$.

The Poisson Summation Formula (PSF)
$$
\sum_{\lambda \in \Lambda} \varphi(x-\lambda) = 
  \Abs{\det A}^{-1} \sum_{\lambda^* \in \Lambda^*} \widehat\varphi(x-\lambda^*),
$$
valid for all smooth $\varphi$ of compact support, can be written
as a distribution identity as follows:
\beql{poisson}
\left( \sum_{\lambda \in \Lambda} \delta_\lambda \right)^\wedge = 
  \Abs{\det A}^{-1} \sum_{\lambda^* \in \Lambda^*} \delta_{\lambda^*}.
\eeq

Our spectral criterion for tiling (Theorem \ref{th:spectral}) then takes
the following simpler form for lattice tilings.
\begin{theorem}\label{th:spectral-lattice}
Assume that $f\in L^1(\RR^d)$.
Then $f$ tiles $\RR^d$ with a lattice $\Lambda$ and some weight $w$
if and only if
\beql{spectral-tiling}
\Lambda^* \setminus \Set{0} \subseteq \Set{\xi\in\RR^d:\
	\widehat{f}(\xi) = 0}.
\eeq
In this case we have $\Ds w = \Abs{\det\Lambda}^{-1}\int_{\RR^d} f$.
\end{theorem}
\noindent{\bf Proof.} (without using Theorem \ref{th:spectral})
Let $D$ be a fundamental parallelepiped of $\Lambda$.
The function
$$
g(x) = \sum_{\lambda\in\Lambda} f(x-\lambda)
$$
is defined as an absolutely convergent series
for almost all $x\in\RR^d$ (since $f\in L^1(\RR^d)$),
is $\Lambda$-periodic, and $g\in L^1(D)$.

The dual group of $D = \RR^d / \Lambda$ is identified with $\Lambda^*$.
That is the continuous characters of $\RR^d/\Lambda$ are the functions
$$
\phi_{\lambda^*}(x) = \exp(2\pi i\inner{\lambda^*}{x}),
 \ \ \ \lambda^* \in \Lambda^*,
$$
and $g$ is constant (i.e., $f$ tiles with $\Lambda$) if and only if
$$
\widehat{f}(\lambda^*) = \inner{g}{\phi_{\lambda^*}} = 0,
\ \ \ \forall \lambda^* \in \Lambda^*\setminus\Set{0}.
$$
\Qed

An alternative would be to prove Theorem \ref{th:spectral-lattice}
for $\Lambda=\ZZ^d$ using ordinary multiple Fourier series
and then use a linear transformation to get the general form of the
theorem.

Thus, a measurable  $T\subseteq \RR^d$ tiles with $\Lambda$ (in the
ordinary sense of weight $1$) if and only if
$\widehat{\one_T}$ vanishes on $\Lambda^*\setminus\Set{0}$ and
the volume of $\Lambda$ is equal to that of $T$.

All tilings in \S\ref{sec:minkowski} and \S\ref{sec:notched}
are tilings of weight $1$.

\mysection{The Minkowski Conjecture}
\label{sec:minkowski}

\mysubsection{Two equivalent forms of the conjecture.}
Minkowski's theorem on linear forms is the following statement.
\begin{theorem}\label{th:m-thm}
{\bf (Minkowski)}
If $A \in M_d(\RR)$ has $\det A = 1$ then
there is $x \in \ZZ^d\setminus\Set{0}$ such that
$$
\Linf{A x} \le 1.
$$
\end{theorem}
Minkowski conjectured around 1900 that one can always get
$\Linf{A x} < 1$ except when $A$ has an integral row.
This was proved by Haj\'os \cite{Hajos} in 1941.
\begin{theorem}\label{th:hajos-forms}
{\bf (Haj\'os)}
If $A \in M_d(\RR)$ has $\det A = 1$ then there is $x \in \ZZ^d$
such that
$$
\Linf{A x} < 1,
$$
unless $A$ has an integral row.
\end{theorem}
Haj\'os actually worked on the following equivalent form
of the Minkowski conjecture, which involves lattice tilings by a cube.
This form was already known to Minkowski and most results on Minkowski's
conjecture leading up to Haj\'os's eventual proof have used
this form.
\begin{theorem}\label{th:hajos-tilings}
If $Q = [-1/2, 1/2]^d$ is a cube of unit volume in $\RR^d$,
$\Lambda\subset\RR^d$ is a lattice, and
$$
\RR^d = Q \oplus \Lambda
$$
is a lattice tiling of $\RR^d$ then there are two cubes in the tiling
that share a $(d-1)$-dimensional face.
In other words,
for some $i=1,\ldots,d$, the standard basis vector
$e_i = (0,\ldots,0,1,0,\ldots,0)^\top \in \Lambda$.
\end{theorem}
Before going on to describe a new equivalent form of the Minkowski
conjecture (Theorem \ref{th:3rd}) we sketch a proof
of the equivalence of Theorems \ref{th:hajos-forms} and
\ref{th:hajos-tilings}.

\noindent{\bf Theorem \ref{th:hajos-forms} $\Longrightarrow$ Theorem
\ref{th:hajos-tilings}.}

\noindent
Let $\Lambda = A \ZZ^d$ with $\det A =1$, $Q\oplus\Lambda = \RR^d$.
Then, either there is a non-zero $\Lambda$-point in the interior
of $2Q$ or $A$ has an integral row.
The first cannot happen because of the tiling assumption.
Therefore $a_{ij} \in \ZZ$ for some $i$ and for all $j$.
Again because of tiling it follows that $\gcd(a_{i1},\ldots,a_{i,d})=1$.
Let $\RR^{d-1}$ be the subspace spanned by all $e_j$, $j\neq i$, and
define $\Lambda' = \Lambda \cap \RR^{d-1}$ and
$Q' = Q \cap \RR^{d-1}$.
It follows that $\RR^{d-1} = \Lambda' \oplus Q'$ is a tiling
of $\RR^{d-1}$. By induction then $\Lambda'$ contains some
vector of the standard basis and so does $\Lambda$.
\Qed

\noindent{\bf Theorem \ref{th:hajos-tilings} $\Longrightarrow$ Theorem
\ref{th:hajos-forms}.}

Theorem \ref{th:hajos-tilings} easily implies the
seemingly stronger statement that, if $A\ZZ^d \oplus Q = \RR^d$ is a
tiling then, after a permutation of the coordinate axes, the matrix $A$
takes the form
\beql{matrix-form}
\left(
\begin{array}{ccccc}
1 & 0 & 0 & \ldots & 0 \\
a_{2,1} & 1 & 0 & \ & 0 \\
\ldots & \ldots & \ldots & \ldots & \ldots\\
a_{d,1} & \ldots &\ldots &\ldots & 1
\end{array}
\right)
\eeq
Using this remark, if $A\ZZ^d \cap (-1,1)^d = \Set{0}$ we get, since
$\det A = 1$, that $A\ZZ^d \oplus Q = \RR^d$ and, therefore, $A$ is
(after permutation of the coordinate axes) of the type
\eqref{matrix-form}, and thus has an integral row (which property
is preserved under permutation similarity).
\Qed

\mysubsection{A new equivalent form.}
In this section we prove that the following is equivalent
to the Minkowski conjecture (Theorems \ref{th:hajos-forms} and
\ref{th:hajos-tilings}).
\begin{theorem}\label{th:3rd}
Let $B \in M_d(\RR)$ have $\det B = 1$ and the property that
for all $x\in\ZZ^d\setminus\Set{0}$ some coordinate
of the vector $Bx$ is a non-zero integer.
Then $B$ has an integral row.
\end{theorem}
{\bf Remark.}
One might think that Theorem \ref{th:3rd} can be proved
equivalent directly to Theorem \ref{th:hajos-forms}, which
it resembles most.
It is, indeed, clear that Theorem \ref{th:hajos-forms} implies
Theorem \ref{th:3rd}.
However, the proof that is given here is that of the equivalence
of Theorems \ref{th:3rd} and \ref{th:hajos-tilings} using our
spectral criterion for tilings (Theorem \ref{th:spectral-lattice})
and I do not know of a more direct proof that
Theorem \ref{th:3rd} implies Theorem \ref{th:hajos-forms}.

We shall need the following simple lemma.
\begin{lemma}\label{lm:matrix}
Let $A \in M_d(\RR)$ be a non-singular matrix.
The lattice $A^{-\top}\ZZ^d$ contains the basis vector $e_i$ 
if and only if the $i$-th row of $A$ is integral.
\end{lemma}
{\bf Proof.}
Without loss of generality assume $i=1$.

If $e_1 \in A^{-\top}\ZZ^d$ then $e_1 = A^{-\top} x$ for some
$x\in\ZZ^d$.
Therefore, for all $y\in\ZZ^d$ we have
$$
(Ay)_1 = e_1^\top A y = x^\top A^{-1} A y = x^\top y \in \ZZ.
$$
It follows that $(Ay)_1 \in \ZZ$ for all $y \in \ZZ^d$ and the
first row of $A$ is integral.

Conversely, if the first row of $A$ is integral, then,
for all $y\in\ZZ^d$
$$
\ZZ \ni (Ay)_1 = x^\top y,
$$
where $A^{-\top}x = e_1$ ($x\in\RR^d$).
It follows that $x\in\ZZ^d$ and $e_1 \in A^{-\top}\ZZ^d$.
\Qed

\noindent{\bf 
Proof of the equivalence of Theorems \ref{th:hajos-tilings}
and \ref{th:3rd}.
}

Let $f(x) = \One{x \in Q}$ be the indicator function
of the unit-volume cube $Q = [-1/2, 1/2]^d$.
A simple calculation shows that
\beql{FT-of-f}
\widehat{f}(\xi)  = \prod_{j=1}^d {\sin \pi \xi_j \over \pi \xi_j},
\eeq
so that
\beql{Z-of-f}
Z = \Set{\widehat{f} = 0} = \Set{\xi\in\RR^d:\ \mbox{some $\xi_j$ is
	a non-zero integer}}.
\eeq
Therefore, if $\Lambda = B^{-\top}\ZZ^d$ then (since $\Lambda$ has
volume $1$)
$$
Q\oplus\Lambda = \RR^d \Longleftrightarrow
	\Lambda^*\setminus\Set{0} \subseteq Z,
$$
where $\Lambda^* = B\ZZ^d$,
by Theorem \ref{th:spectral-lattice}.
In words, $Q$ tiles with $\Lambda$ if and only if
for every $x\in\ZZ^d\setminus\Set{0}$ the vector $Bx$ has
some non-zero integral coordinate.

\noindent{\bf Theorem \ref{th:hajos-tilings} $\Longrightarrow$
 Theorem \ref{th:3rd}}.

\noindent
Suppose $x\in\ZZ^d\setminus\Set{0}$ implies some $(Bx)_i\in\ZZ\setminus\Set{0}$.
Then $Q\oplus\Lambda = \RR^d$ and from Theorem \ref{th:hajos-tilings},
say, $e_1 \in \Lambda$, which, from Lemma \ref{lm:matrix},
implies that the first row of $B$ is integral.

\noindent{\bf Theorem \ref{th:3rd} $\Longrightarrow$
  Theorem \ref{th:hajos-tilings}}.

\noindent
Assume $Q\oplus\Lambda = \RR^d$. It follows that for every
$x\in\ZZ^d\setminus\Set{0}$ the vector $Bx$ has some non-zero integral
coordinate. By Theorem \ref{th:3rd} $B$ must have an integral row,
which, by Lemma \ref{lm:matrix}, implies that some $e_i \in \Lambda$.
\Qed

\newpage
\mysection{The notched and the extended cube}
\label{sec:notched}

\noindent
In this section we prove that some simple shapes (like those in Figures
\ref{fig:notched} and \ref{fig:extended}) admit lattice tilings.
That the ``extended cubes'' (Fig.\ \ref{fig:extended}--see Theorem
\ref{th:ext}) admit lattice tilings has not been shown before.

\mysubsection{The notched cube}
We now consider the unit cube
$$
Q = \left[-{1\over2},{1\over2}\right]^d
$$
 from whose corner (say in the positive orthant) a rectangle
$R$ has been removed with sides-lengths $\delta_1,\ldots,\delta_d$
($0\le\delta_j\le1$).
That is, we consider the ``notched cube'':
$$
N = Q \setminus R
$$
where
$$
R = \prod_{j=1}^d \left[{1\over2}-\delta_j,{1\over2}\right].
$$
It is shown in Figure \ref{fig:notched}.

\begin{figure}[t]
\centerline{\psfig{figure=notched.ps}}
\caption{\footnotesize A notched cube in $\RR^3$.}
\label{fig:notched}
\hrulefill
\end{figure}

We give a new proof of the following result of Stein \cite{Stein}.
\begin{theorem}\label{th:notched}
The notched cube $N$ admits a lattice tiling of $\RR^d$.
\end{theorem}

After a simple calculation we obtain
\beql{FT}
\widehat{\one_N}(\xi) = \prod_{j=1}^d {\sin\pi\xi_j \over \pi\xi_j} -
  F(\xi) \prod_{j=1}^d {\sin\pi\delta_j\xi_j \over \pi\xi_j},
\eeq
where $F(\xi) = \exp(\pi i K(\xi))$ with
\beql{K}
K(\xi) = \sum_{j=1}^d (\delta_j-1)\xi_j.
\eeq
Using Theorem \ref{th:spectral-lattice} it is enough
to exhibit a lattice $\Lambda \subset \RR^d$, of volume
equal to
$$
\Abs{N} = 1-\delta_1\cdots\delta_d,
$$
such that
$\widehat{\one_N}$ vanishes on $\Lambda^*\setminus\Set{0}$.

\mysubsection{Lattices in the zero-set}
\label{sec:zeros}
We define the lattice $\Lambda^*$ as those points $\xi$ for
which
\begin{eqnarray}\label{system}
\xi_1 - \delta_2\xi_2 &=& n_1,\nonumber\\
\xi_2 - \delta_3\xi_3 &=& n_2,\nonumber\\
 \ldots & & \\
\xi_d - \delta_1\xi_1 &=& n_d,\nonumber
\end{eqnarray}
for some $n_1,\ldots,n_d \in \ZZ$.
That is, $\Lambda^* = A^{-1} \ZZ^d$, where
\beql{matrix}
A = \left(
\begin{array}{cccccc}
1 & -\delta_2 & & & & \\
 & 1 & -\delta_3 & & & \\
 & & & \ddots & & \\
 & & & & 1 & -\delta_d \\
-\delta_1 & & & & & 1
\end{array} \right).
\eeq
Therefore $\Lambda = A^\top\ZZ^d$ and the volume of $\Lambda$
is equal to $\Abs{\det A}$.
Expanding $A$ along the first column we get easily
that $\det A = 1-\delta_1\cdots\delta_d$,
which is the required volume.

We now verify that $\widehat{\one_N}$ vanishes on
$\Lambda^*\setminus\Set{0}$.

Assume that $0 \neq \xi \in \Lambda^*$.
Adding up the equations in \eqref{system}
we get
$$
K = K(\xi) = -(n_1+\cdots+n_d).
$$
If all the coordinates of $\xi$ are non-zero
we can write
\beql{tmp1}
\widehat{\one_N}(\xi) = {1\over\pi^d\xi_1\cdots\xi_d} \left(
 \prod_{j=1}^d\sin\pi\xi_j - (-1)^K \prod_{j=1}^d\sin\pi\delta_j\xi_j \right).
\eeq
Observe from \eqref{system} that
$$
\sin\pi\xi_j = (-1)^{n_j} \sin\pi\delta_{j+1}\xi_{j+1},
$$
where the subscript arithmetic is done modulo $d$,
 from which we get $\widehat{\one_N}(\xi) = 0$,
since the factors in the two terms of \eqref{tmp1}
match one by one.

It remains to show that $\widehat{\one_N}(\xi) = 0$ even when
$\xi$ has some coordinate equal to $0$, say $\xi_1=0$.

Consider the numbers $\xi_1,\ldots,\xi_d$ arranged in a cycle
and let
$$
I = \Set{\xi_m, \xi_{m+1},\ldots,\xi_1,\ldots,\xi_{k-1},\xi_k}
$$
be an interval around $\xi_1$ which is maximal with the property
that all its elements are $0$.
Then $\xi_{m-1}\neq 0$ and $\xi_{k+1}\neq 0$
and from \eqref{system} we get
\beql{eqs}
\xi_{m-1} - \delta_m\xi_m = n_m
\ \ \mbox{and}\ \ 
\xi_k - \delta_{k+1}\xi_{k+1} = n_k.
\eeq
We deduce that $n_m$ and $n_k$ are both non-zero
and therefore that
$\xi_{m-1}$ and $\delta_{k+1}\xi_{k+1}$ are both
non-zero integers
and $\sin \pi\xi_{m-1} = \sin \pi\delta_{k+1}\xi_{k+1} = 0$.
This means that both terms in \eqref{FT} vanish and
so does $\widehat{\one_N}(\xi)$.
\Qed

So we proved that for the lattice $\Lambda = A^\top\ZZ^d$,
where $A$ is defined in \eqref{matrix},
we have $N\oplus\Lambda = \RR^d$.
Clearly, if $\sigma$ is a cyclic permutation
of $\Set{1,\ldots,d}$ and
if instead of the matrix $A$ we have the matrix $A'$ whose $i$-th
row has $1$ on the diagonal, $-\delta_{\sigma i}$ at column $\sigma i$ and
$0$ elsewhere, we get again a lattice tiling with
the lattice $(A')^\top\ZZ^d$.
Stein \cite{Stein} as well as Schmerl \cite{Schmerl}
have shown that these $(d-1)!$ lattice tilings of the notched
cube (one for each cyclic permutation of $\Set{1.,\ldots,d}$)
are all non-isometric when the side-lengths $\delta_j$ are
all distinct.

A deeper result of Schmerl \cite{Schmerl}
is that there are no other translational tilings of the notched cube,
lattice or not.
This is something that I cannot prove with the harmonic analysis
approach.

\mysubsection{Extended cubes}
\label{sec:ext}
Let us now allow the parameters $\delta_1,\ldots,\delta_d$
to take on any non-zero real value
subject only to the restriction
\beql{not-one}
\delta_1\cdots\delta_d \neq 1,
\eeq
and let the function $\varphi(\xi)$
be equal to the right-hand side of \eqref{FT}.
Let again the matrix $A$ be defined by \eqref{matrix}
and $\Lambda = A^\top\ZZ^d$ as before.
We have again $\det A = 1-\delta_1\cdots\delta_d$.

The calculations we did in \S\ref{sec:zeros} show
that $\varphi$ vanishes on $\Lambda^*\setminus\Set{0}$, hence,
if $\check{\varphi}$ is the inverse FT of $\varphi$, $\check{\varphi}$
tiles $\RR^d$ with $\Lambda$ and weight
\beql{weight}
{\varphi(0) \over \Abs{1-\delta_1\cdots\delta_d}} =
	{\rm sgn}(1-\delta_1\cdots\delta_d),
\eeq
where ${\rm sgn}(x)=\pm1$ is the sign of $x$.

The function $\check{\varphi}$ is given by
\beql{IFT}
\check{\varphi}(x) = \one_Q(x) - {\rm sgn}(\delta_1\cdots\delta_d)\psi(x),
\eeq
where
\beql{psi}
\psi(x) = 
 \one_Q\left({x_1-(1-\delta_1)/2 \over \Abs{\delta_1}},\ldots,
	     {x_d-(1-\delta_d)/2 \over \Abs{\delta_d}} \right).
\eeq
Notice that $\psi(x)$ is the indicator function
of a rectangle $R = R(\delta_1,\ldots,\delta_d)$ with
side-lengths $\Abs{\delta_1},\ldots,\Abs{\delta_d}$
centered at the point
\beql{ptP}
P = \left({1\over2},\ldots,{1\over2}\right) -
	{1\over2}\left(\delta_1,\ldots,\delta_d\right).
\eeq
The rectangle $R$ intersects the interior of $Q$ only in the case
$\delta_1>0,\ldots,\delta_d>0$ and when this happens
$\check{\varphi}$ is an indicator function only if we
also have $\delta_1\le1,\ldots,\delta_d\le1$, which is the case
of the notched cube that we examined in \S\ref{sec:zeros}.

\begin{figure}[t]
\centerline{\psfig{figure=extended.ps}}
\caption{\footnotesize Some extended cubes in $\RR^3$ that admit lattice tilings.
The codimension of the intersection is $1$ (left) and $3$ (right).}
\label{fig:extended}
\hrulefill
\end{figure}

Otherwise (not all the $\delta$s are non-negative)
$\check{\varphi}$ is an indicator function only when
${\rm sgn}(\delta_1\cdots\delta_d) = -1$, i.e.,
the number of negative $\delta$s is odd.
In this case we have that
$$
\check{\varphi} = \one_{Q\cup R}
$$
and from \eqref{weight} we get that $Q\cup R$
tiles with $\Lambda$ and weight $1$.
We can now prove the following.
\begin{theorem}\label{th:ext}
{\rm (Lattice tiling by extended cubes)}\\
Let $Q$ and $R$ be two axis-aligned rectangles in $\RR^d$
with sides of arbitrary length and disjoint interiors.
Assume also that $Q$ and $R$ have a vertex $K$ in common
and intersection of odd codimension.

Then $Q\cup R$ admits a lattice tiling of $\RR^d$ of weight $1$.
\end{theorem}
For example, the extended cubes shown in Figure \ref{fig:extended}
admit lattice tilings of $\RR^3$.

\noindent{\bf Proof.}
After a linear transformation we can assume
that $Q = [-1/2,1/2]^d$, that $Q$ and $R$ share the vertex
$K = (1/2,\ldots,1/2)$ and that
$Q\cap R$ has codimension $k$ (an odd number) and
$$
Q \cap R \ \subseteq\ \Set{x\in Q:\ x_1=\cdots=x_k={1\over2}}.
$$

Let the side-lengths of $R$ be $\gamma_1,\ldots,\gamma_d>0$.
Define
$$
\delta_j = \left\{\begin{array}{ll}
 -\gamma_j, & \mbox{if $1\le j \le k$},\\
 \gamma_j, & \mbox{if $k+1\le j \le d$.}
\end{array}\right.
$$
It follows that, with this assignment for the $\delta_j$,
the indicator function of $R$ is equal to the function
$-{\rm sgn}(\delta_1\cdots\delta_d)\psi(x)$
of \eqref{IFT} and tiling follows from the previous discussion.
\Qed

I believe that extended cubes with an intersection of even codimension
do not tile, at least not for general side-lengths.
This is clear in dimension two and it is conceivable that some
combinatorial argument could easily show this in any dimension.
The Harmonic Analysis approach does not seem to be very helpful
when one tries to disprove that something is a (translational) tile.


\mysection{Bibliography}
\begin{thebibliography}{{\bf XXX}}
\vspace{-1.5cm}

\bibitem[{\bf Con}]{Conlan} J.P Conlan, Derived tilings,
J. Comb.\ Th.\ (A) {\bf 20} (1976), 34-40.

\bibitem[{\bf Haj}]{Hajos} G. Haj\'os, \"Uber einfache und mehrfache
Bedeckung des $n$-dimensionalen Raumes mit einem W\"urfelgitter,
Math.\ Z. {\bf 47} (1941), 427-467.

\bibitem[{\bf K}]{Kolountzakis} M.N. Kolountzakis, A new estimate for a problem
of Steinhaus, Inter.\ Math.\ Res.\ Notices, 1996, {\bf 11}, 547-555.

\bibitem[{\bf KLa}]{KLa} M.N. Kolountzakis and J.C.
Lagarias, Tilings of the line by translates of a function,
Duke Math.\ J. {\bf 82} (1996), 3, 653-678.


\bibitem[{\bf Sch}]{Schmerl} J.H. Schmerl, Tiling space with notched
cubes, Discr.\ Math.\ {\bf 133} (1994), 225-235.

\bibitem[{\bf St}]{Stein} S. Stein, The notched cube tiles $\RR^n$,
Discr.\ Math.\ {\bf 80} (1990), 335-337.

\bibitem[{\bf Str}]{Strichartz} R. Strichartz, {\em A guide
to distribution theory and Fourier Transforms},
CRC Press, Boca-Raton, Florida (1994).

\end{thebibliography}


\end{document}