# A characterization of Gabor Riesz bases with separable time-frequency shifts

Christina Frederick  Azita Mayeli

(Last edit: ,
)

###### Abstract

A Gabor system generated by a window function $g\in L^{2}({\mathbb{R}}^{d})$
and a separable set $\Lambda\times\Gamma\subset{\mathbb{R}}^{2d}$ is the
collection of time-frequency shifts of $g$ given by
$\mathcal{G}(g,\Lambda\times\Gamma)=\left\\{e^{2\pi i\xi\cdot
t}g(t-x)\right\\}_{(x,\xi)\in\Lambda\times\Gamma}$. One of the fundamental
problems in Gabor analysis is to characterize all windows and time-frequency
sets that generate a Gabor frame or Gabor orthonormal basis. The case of Gabor
orthonormal bases generated by characteristic functions $g=\chi_{\Omega}$ has
been solved by Han and Wang [12, 23]. In this paper, we build on these results
and obtain a full characterization of Riesz Gabor systems of the form
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ when $\Omega$ is a tiling of
${\mathbb{R}}^{d}$ with respect to $\Lambda$. Furthermore, for a certain class
of lattices $\Lambda\times\Gamma$, we prove that a necessary condition for the
characteristic function of a multi-tiling set to serve as a window function
for a Riesz Gabor basis is that the set must be a tiling set. To prove this,
we develop new results on the zeros of the Zak transform and connect these
results to Gabor frames.

Keywords: Gabor Riesz bases, multi-tiling sets, Zak transforms.

###### Contents

  1. 1 Introduction
    1. 1.1 Main results
    2. 1.2 Relevant work, comments, and remarks
  2. 2 Notations and Preliminaries
  3. 3 Proof of Theorem 1.1 and Theorem 1.2
    1. 3.1 Multi-tiling sets and Gabor frames - Proof of Theorem 1.1
    2. 3.2 Tiling sets and Gabor Riesz bases - Proof of Theorem 1.2
    3. 3.3 Stability of Gabor Riesz bases
  4. 4 Lattice Zak transform
    1. 4.1 Common fundamental domains for lattices
    2. 4.2 The lattice Zak transform is isometric
    3. 4.3 Zeros of the lattice Zak transforms
  5. 5 Characterization of Gabor systems with lattice time-frequency shifts - Proofs of Theorem 1.3 and Theorem 1.4
    1. 5.1 Gabor systems for any window and lattice Zak transform
    2. 5.2 Multi-tiling and lattice Zak transform
    3. 5.3 Proofs of Theorem 1.3 and Theorem 1.4
    4. 5.4 Illustration of zeros of some lattice Zak transforms for multi-tiling sets
  6. 6 Open problems
  7. 7 Appendix

##  1 Introduction

We will assume that the sets $\Lambda$ and $\Gamma$ are countable subsets of
$\mathbb{R}^{d}$ and define the Gabor system
$\mathcal{G}(g,\Lambda\times\Gamma)$ with respect to the window function $g\in
L^{2}({\mathbb{R}}^{d})$ and the set $\Lambda\times\Gamma$ to be the
collection of functions

$\displaystyle\mathcal{G}(g,\Lambda\times\Gamma)=\left\\{e^{2\pi i\xi\cdot
t}g(t-x):\ (x,\xi)\in\Lambda\times\Gamma\right\\}.$ (1)

This system is also known as a Weyl-Heisenberg system. The set
$\Lambda\times\Gamma$ is called the set of time-frequency shifts or the Gabor
spectrum. If the Gabor system is a frame, Riesz basis or orthogonal basis, we
call it a Gabor frame, Gabor Riesz basis, or Gabor orthogonal basis,
respectively, for $L^{2}({\mathbb{R}}^{d})$.

Gabor systems, first introduced by Gabor in 1946 [9], now play a central role
in applied and computational harmonic analysis, engineering (signal and image
processing, communication theory), and physics (the phase-space and coherent
space representation). The Gabor analysis permits a time-frequency
representation of a signal $f(t)$ in the time domain, hence making it possible
to view the frequency spectrum locally in time. For more on the history of the
Gabor bases, we refer to [11].

Motivation: This study is inspired by the well-known characterization of Gabor
orthogonal bases of the form $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$
by Han and Wang in [12], where $\chi_{\Omega}$ is the characteristic function
of a measurable set $\Omega\subset\mathbb{R}^{d}$.

######  Han-Wang’s Theorem.

The system $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma$) is a Gabor
orthogonal basis for $L^{2}(\mathbb{R}^{d})$ if and only if the following two
conditions hold:

  1. 1.

$\Omega$ tiles $\mathbb{R}^{d}$ by $\Lambda$, i.e.,
$\sum_{\lambda\in\Lambda}\chi_{\Omega}(x-\lambda)=1$, for almost every
$x\in\mathbb{R}^{d}$, and,

  2. 2.

The family of exponentials $\mathcal{E}(\Gamma)=\\{e^{2\pi ix\cdot\gamma}:\
\gamma\in\Gamma\\}$ is an orthogonal basis for $L^{2}(\Omega).$

We aim to generalize these results to Gabor Riesz bases and Gabor frames for
two principal reasons. First, orthogonality is a strong condition that is
often not satisfied in practical applications. Moreover, the orthogonality of
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is unstable with respect to
small perturbations either in translation or modulation. This motivates the
need for the analysis of Gabor frames and Gabor Riesz bases, in which
orthogonality is relaxed and stability is improved.

One question that we ask ourselves here is: What are sufficient conditions on
$\Omega$, $\Lambda$, and $\Gamma$ that produce a Gabor Riesz basis? A natural
approach is to modify the two conditions in Han-Wang’s Theorem, and assume
that:

  1. 1.

$\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by $\Lambda$ at level $k$, i.e.,
$\sum_{\lambda\in\Lambda}\chi_{\Omega}(x-\lambda)=k$ for almost every
$x\in\mathbb{R}^{d}$, and,

  2. 2.

$\mathcal{E}(\Gamma)$ is a Riesz basis for $L^{2}(\Omega)$.

However, these modifications are not sufficient when $k>1$. This is
demonstrated in the next two examples that fail the necessary condition, given
in [25], that:

$\text{dens}(\Lambda\times\Gamma)=1\text{ when
}\mathcal{G}(g,\Lambda\times\Gamma)\text{ is a Gabor Riesz basis.}$

Here, dens$(\Lambda\times\Gamma)$ denotes the Beurling density of a set $S$.

######  Example 1.1.

If $\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by a lattice $\Lambda$ at level
$k>1$, it is known that there exist distinct vectors $\\{a_{i}\\}_{i=1}^{k}$
in ${\mathbb{R}}^{d}$ such $\mathcal{E}(\Gamma)$ is a Riesz basis for
$L^{2}(\Omega)$, where $\Gamma=\cup_{i=1}^{k}(\Lambda^{\perp}+a_{i})$ [10,
20]. However, dens$(\Lambda\times\Gamma)=k>1$.

######  Example 1.2.

Let $\Omega=[0,1]$, $\Lambda=2^{-1}\mathbb{Z}$ and $\Gamma=2\mathbb{Z}\cup
2\mathbb{Z}+a$ for $0<a<1$. Then, $\mathcal{E}(\Gamma)$ is Riesz basis for
$L^{2}(\Omega)$, however, dens$(\Lambda\times\Gamma)\neq 1$.

The goal of this paper is to obtain an analog of Han-Wang’s Theorem for Gabor
Riesz bases $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$. More precisely,
we address the following question:

######  Question A.

Given a Gabor Riesz basis of the form
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$, what can be inferred about
the relationship between the spectral and the geometry of $\Omega$, e.g.: Is
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ a Gabor Riesz basis if and
only if $\mathcal{E}(\Gamma)$ is a Riesz basis for $L^{2}(\Omega)$ and
$\Omega$ is a tiling of ${\mathbb{R}}^{d}$ by $\Lambda$?

In this paper, we answer Question A for special cases of $\Omega$ (tilings and
multi-tilings). Our main results are collected in Theorem 1.2, Theorem 1.3 and
Theorem 1.4, as we shall explain in the following section. Some stability
results are also obtained as an outcome of Theorem 1.2.

Establishing a complete characterization (even in lattice case) remains a
challenge, and we end with a discussion of open problems generated by this
work.

###  1.1 Main results

######  Theorem 1.1.

Let $\Omega\subset\mathbb{R}^{d}$ be a measurable set, and let $\Gamma$ and
$\Lambda$ be countable subsets of ${\mathbb{R}}^{d}$. Assume that
$(\Omega,\Lambda)$ is a multi-tiling pair. Then,

  1. (i)

If $(\Omega,\Gamma)$ is a frame spectral pair, then
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a frame for
$L^{2}(\mathbb{R}^{d})$.

  2. (ii)

The converse of (i) holds when $(\Omega,\Lambda)$ is a tiling pair.

Notice that in the present of conditions (i) and (ii) in the previous theorem,
one can explicitly determine the dual Gabor frame. Indeed, assume
$\\{g_{\gamma}\\}_{\gamma\in\Gamma}$ is a dual frame for the frame
$\\{e_{\gamma}\\}_{\gamma\in\Gamma}$ in $L^{2}(\Omega)$. Then the system
$\\{g_{\gamma}(\cdot-\lambda)\\}_{(\lambda,\gamma)}$ forms a dual frame for
the Gabor frame $\mathcal{G}(\Omega,\Lambda\times\Gamma)$.

The following theorem establishes the equivalence between the Riesz spectral
pair $(\Omega,\Gamma)$ and the Gabor Riesz basis
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$, provided that $\Omega$ is a
tiling set with respect to $\Lambda$.

######  Theorem 1.2.

Let $\Omega\subset\mathbb{R}^{d}$ be a measurable set with positive and finite
measure, and let $\Gamma$ and $\Lambda$ be countable subsets of
${\mathbb{R}}^{d}$. If $(\Omega,\Lambda)$ is a tiling pair, then the following
are equivalent:

  1. (i)

$(\Omega,\Gamma)$ is a Riesz spectral pair.

  2. (ii)

$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a Riesz basis for
$L^{2}(\mathbb{R}^{d})$.

Moreover, if $e_{\lambda}(\gamma)=1$ for all $\lambda,\gamma$, then the dual
Riesz basis can be expressed explicitly as the collection of all dual Riesz
bases on each $\Omega+\lambda$, $\lambda\in\Lambda$.

######  Remark 1.1.

The conclusion of Theorem 1.2 also holds when the Riesz condition is replaced
by completeness or frame condition.

If the tiling condition does not hold in Theorem 1.2 and
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a Gabor Riesz basis, then
$\mathcal{E}(\Gamma)$ is a Bessel sequence for $L^{2}(\Omega)$ with the
unified upper Riesz bound for the Gabor frame
$\mathcal{G}(\Omega,\Lambda\times\Gamma)$. By the completeness of the Gabor
system, $\Omega+\Lambda$ covers $\mathbb{R}^{d}$.

The condition that $\Omega$ tiles ${\mathbb{R}}^{d}$ by $\Lambda$ is a
sufficient condition in Theorem 1.2. The next result states that the tiling
condition is also a necessary condition for
$\mathcal{G}(\Omega,\Lambda\times\Gamma)$ to be a Gabor frame when $\Lambda$
and $\Gamma$ satisfy additional lattice assumptions.

######  Theorem 1.3.

Let $M$ and $N$ be full rank matrices such that $\det(MN)=1$ and $N^{T}M$ is
an integer matrix. Assume that $\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by
$M({\mathbb{Z}}^{d})$. If the system
$\mathcal{G}(\chi_{\Omega},M({\mathbb{Z}}^{d})\times N({\mathbb{Z}}^{d}))$ is
a Gabor frame, then 1) $\Omega$ tiles $\mathbb{R}^{d}$ by
$M({\mathbb{Z}}^{d})$, and 2) $\mathcal{E}(N({\mathbb{Z}}^{d}))$ is an
orthogonal basis for $L^{2}(\Omega)$.

It is known that for $\alpha\beta=1$, any Gabor frame with lattice spectrum of
the form $\mathcal{G}(g,\alpha\mathbb{Z}^{n}\times\beta\mathbb{Z}^{n})$ is
also a Gabor Riesz basis [13, 11]. Our next result gives conditions for which
not only is any Gabor frame $G(\chi_{\Omega},M({\mathbb{Z}}^{d})\times
N({\mathbb{Z}}^{d}))$ a Gabor Riesz basis but it is, surprisingly, also a
Gabor orthogonal basis.

######  Theorem 1.4.

Let $M$ and $N$ be full rank matrices such that $\det(MN)=1$ and $N^{T}M$ is
an integer matrix. Assume that $\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by
$M({\mathbb{Z}}^{d})$. Then, the following are equivalent:

  1. (i)

$\mathcal{G}(\chi_{\Omega},M({\mathbb{Z}}^{d})\times N({\mathbb{Z}}^{d}))$ is
a frame for $L^{2}(\mathbb{R}^{d})$.

  2. (ii)

$\mathcal{G}(\chi_{\Omega},M({\mathbb{Z}}^{d})\times N({\mathbb{Z}}^{d}))$ is
a Riesz basis for $L^{2}(\mathbb{R}^{d})$.

  3. (iii)

$\mathcal{G}(\chi_{\Omega},M({\mathbb{Z}}^{d})\times N({\mathbb{Z}}^{d}))$ is
an orthogonal basis for $L^{2}(\mathbb{R}^{d})$.

  4. (iv)

$\Omega$ tiles $\mathbb{R}^{d}$ by $M({\mathbb{Z}}^{d})$, and
$\mathcal{E}(N({\mathbb{Z}}^{d}))$ is an orthogonal basis for $L^{2}(\Omega)$.

###  1.2 Relevant work, comments, and remarks

The motivation of our study has grown from the results of three papers: [12],
[15] and [5]. In their paper in [12], Han and Wang proved that the necessary
and sufficient conditions for a Gabor systems
$\mathcal{G}(\Omega,\Lambda\times\Gamma)$ to be an orthogonal basis is that
$\Omega$ tiles $\mathbb{R}^{d}$ by translations by $\Lambda$ and
$\mathcal{E}(\Gamma)$ is an orthogonal basis for $L^{2}(\Omega)$. Han and
Wang’s result rules out the possibility that the characteristic function of a
unit ball in $\mathbb{R}^{d}$ can serve as a window function for a Gabor basis
with separable time-frequency shifts domain, as the unit ball neither tiles
nor it admits an exponential orthogonal basis [7]. In [15], the second author
and Iosevich proved that the characteristic function of the unit ball can
never serve as a window function for a Gabor orthogonal basis with respect to
any time-frequency shifts domain when $d\neq 1$ (mod 4). The results for $d=1$
(mod 4) is still an open question. As the Riesz bases are the next best bases
after the orthogonal bases, an immediate question that one can ask here is
whether or not the unit ball can serve as generator of a Gabor Riesz basis.
The answer to this question is still unknown. This is yet another motivating
fact for our research in this paper.

In [23], the second author and Lai have extended the Han and Wang’s
characterization to non-separable time-frequency shifts domain, i.e., the
Gabor orthogonal bases $\mathcal{G}(\Omega,S)$ where $S\subset\mathbb{R}^{2d}$
is a lattice but not in form of $\Lambda\times\Gamma\subset\mathbb{R}^{2d}$.
The authors have characterized the Gabor orthogonal bases for a large class of
lattices. The characterization in full generality is still open.

In the case where $\Omega$ multi-tiles ${\mathbb{R}}^{d}$, an analysis of the
connections between frame spectral pairs, Riesz spectral pairs, and spectral
pairs was done in [5]. When $\Omega$ multi-tiles by a lattice (Definition
2.4), it is well-known that the set admits an exponential Riesz basis [10,
20]. In the latter case, the first author and Okoudjou have computed the
explicit form of the dual Riesz basis [6]. In this context, one might believe
that if $\Omega$ is a multi-tiling (but not tiling) with $\Lambda$ and
$\mathcal{E}(\Gamma)$ is a Riesz basis for $L^{2}(\Omega)$, then an analog
comparable to Han-Wang’s Theorem may hold and
$\mathcal{G}(\Omega,\Lambda\times\Gamma)$ is a Riesz basis. Unfortunately, as
we observed in Example 1.1, the necessary density condition may fail, thus the
Gabor system $\mathcal{G}(\Omega,\Lambda\times\Gamma)$ is not a Riesz basis.

In the following remarks, we comment on the relations between our results and
the existing results for orthogonal bases.

######  Remark 1.2.

If $\Omega$ does not tile, then there is no countable set $\Lambda$ such that
the Gabor system (1) is an orthogonal basis [12, 23].

If $\Omega$ tiles by $\Lambda$ but $L^{2}(\Omega)$ does not admit any
exponential Riesz basis, in Theorem 1.2 we prove that for such set there is no
countable set $\Gamma\subset\mathbb{R}^{d}$ such that the system
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a Gabor Riesz basis for
$L^{2}(\mathbb{R}^{d})$. Notice that the existence of a domain with no
exponential Riesz basis has been recently proved in [21].

######  Remark 1.3.

While the tiling and spectral property of the set $\Omega$ are necessary for a
Gabor system (1) to be an orthogonal basis, the answer to the question of
whether or not the tiling and Riesz spectral criteria are also necessary for a
Gabor system to be a Riesz basis is yet unknown for general sets $\Omega$.
However, with prior knowledge on the geometry of $\Omega$ (i.e. multi-tiling
by a lattice), in Theorem 1.3 we prove the necessity of the criteria.

######  Remark 1.4.

Theorem 1.3 is an extension of Han-Wang’s Theorem to Gabor frames for a
special class of time-frequency shifts domains. As a result of the theorem,
$\Omega$ tiles by the lattice $M(\mathbb{Z}^{d})$. Thus, by the Fuglede
Conjecture, $\mathcal{E}(M^{-T}(\mathbb{Z}^{d})$ is an orthogonal basis for
$L^{2}(\Omega)$. However, in Theorem 1.3 the lattice $N({\mathbb{Z}}^{d})$
doesn’t have to be the dual lattice of $M({\mathbb{Z}}^{d})$. This result
links Fuglede’s conjecture to the study of Gabor bases as we have demonstrated
in Theorem 5.2. (For the statement of the Fuglede’s conjecture see Sec. 1.4 in
this paper. For the history of the conjecture we refer to [17, 3] and the
reference therein.)

######  Remark 1.5.

While the necessity of tiling of the set $\Omega$ by $\Lambda$ for a Gabor
Riesz basis $\mathcal{G}(\Omega,\Lambda\times\Gamma)$ is not known yet, for
the non-separable case the answer is in general negative. For example, in [8],
the authors construct a non-separable Gabor spectrum $S=\cup_{t\in
J}\\{t\\}\times S_{t}$ such that $\chi_{[0,1]^{2}}$ serves as a Gabor window
function for an orthogonal basis, however, the set $[0,1]^{2}$ does not tile
$\mathbb{R}^{2}$ by $J$.

##  2 Notations and Preliminaries

This section contains basic definitions and notations used in the proofs of
the main results.

######  Definition 2.1.

Given a measurable set $\Omega\subset\mathbb{R}^{d}$ with positive and finite
measure, and a discrete and countable set $\Gamma\subset\mathbb{R}^{d}$, we
say that the collection of functions
$\\{f_{\gamma}\\}_{\gamma\in\Gamma}\subset L^{2}(\Omega)$ constitutes a frame
for $L^{2}(\Omega)$ if there exist constants $0<\ell\leq u<\infty$ such that
for any $f\in L^{2}(\Omega)$ the following estimation holds:

$\displaystyle\ell\|f\|^{2}\leq\sum_{\gamma\in\Gamma}|\langle
f,f_{\gamma}\rangle|^{2}\leq u\|f\|^{2}.$ (2)

When the left-hand inequality in (2) holds, we say that the system has a lower
frame bound. When the right-hand inequality in (2) holds, but not necessarily
the left-hand inequality, we say that the system has an upper frame bound and
the sequence $\\{f_{\gamma}\\}_{\gamma\in\Gamma}$ is called a Bessel sequence.

######  Definition 2.2.

We say $\\{f_{\gamma}\\}_{\gamma\in\Gamma}\subset L^{2}(\Omega)$ is a Riesz
basis for $L^{2}(\Omega)$ if it is the image of an orthonormal basis under an
invertible linear map. This definition is equivalent to say that the sequence
$\\{f_{\gamma}\\}_{\gamma\in\Gamma}\subset L^{2}(\Omega)$ is a frame for
$L^{2}(\Omega)$ and for any sequence $\\{c_{\gamma}\\}\in\ell^{2}(\Gamma)$
with finite man non-zero elements, the following estimation holds:

$\displaystyle\ell\sum_{\gamma\in\Gamma}|c_{\gamma}|^{2}\leq\left\|\sum_{\gamma\in\Gamma}c_{\gamma}f_{\gamma}\right\|_{L^{2}(\Omega)}^{2}\leq
u\sum_{\gamma\in\Gamma}|c_{\gamma}|^{2},$ (3)

where $l$ and $u$ are the frame bounds in (2). The sequence
$\\{f_{\gamma}\\}_{\gamma\in\Gamma}$ is called a Riesz sequence in
$L^{2}(\Omega)$ if it satisfies the estimation (3) but the sequence
$\\{f_{\gamma}\\}_{\gamma\in\Gamma}$ is not complete in $L^{2}(\Omega)$.

######  Definition 2.3 (Analytical pairs).

We say $(\Omega,\Gamma)$ is a frame spectral pair if the collection of
exponential functions $\mathcal{E}(\Gamma)=\\{e^{2\pi ix\cdot\gamma}:\
\gamma\in\Gamma\\}$ forms a frame for $L^{2}(\Omega)$, a Riesz spectral pair,
if $\mathcal{E}(\Gamma)$ forms a Riesz basis for $L^{2}(\Omega)$, and a
spectral pair if $\mathcal{E}(\Gamma)$ is an orthogonal basis for
$L^{2}(\Omega)$.

For the analysis of analytical pairs related to multi-tiling domains see the
author’s previous paper [5].

######  Definition 2.4 (Multi-tiling sets).

A set $\Omega\subset\mathbb{R}^{d}$ with positive and finite measure is called
a multi-tiling set with respect to a countable set
$\Lambda\subset\mathbb{R}^{d}$ at level $k\in\mathbb{N}$ if almost every point
$x\in\mathbb{R}^{d}$ can be covered exactly by $k$ translations of $\Omega$ by
elements of $\Lambda$. That is, for a.e. $x\in\mathbb{R}^{d}$, there are
exactly $k$ vectors $\lambda_{1}(x),\cdots,\lambda_{k}(x)\in\Lambda$ such that
$x\in\cap_{i=1}^{k}\Omega+\lambda_{i}(x)$. The set is a tiling set when $k=1$.
That is, almost every point $x\in\mathbb{R}^{d}$ is covered exactly by one
$\Lambda$ translation of $\Omega$

######  Definition 2.5 (Full rank lattices).

A full rank lattice $\Lambda$ in $\mathbb{R}^{d}$ is given by
$M(\mathbb{Z}^{d})$ where $M$ is an $d\times d$ non-singular matrix. We denote
the volume of the lattice by $\text{Vol}(\Lambda)$ that is defined by
$\text{Vol}(\Lambda)=|\det(M)|$. The density of $\Lambda$ is given by
$\text{dens}(\Lambda)=|\det(M)|^{-1}$. The dual lattice of $\Lambda$ is
defined as

$\Lambda^{\perp}:=\\{x\in\mathbb{R}^{d}:\ \lambda\cdot x\in\mathbb{Z},\
\forall\lambda\in\Lambda\\}.$

Here, $\lambda\cdot x$ denotes the inner product of two vectors in
$\mathbb{R}^{d}$. A direct calculation shows that when
$\Lambda=M(\mathbb{Z}^{d})$, $\Lambda^{\perp}=M^{-T}(\mathbb{Z}^{d})$, and
$M^{-T}$ the inverse transpose of $M$.

In this paper, we assume all lattices are full rank lattices.

######  Definition 2.6 (Fundamental domain of a lattice).

Let $\Lambda=M(\mathbb{Z}^{d})$ be a full rank lattice in $\mathbb{R}^{d}$.
The fundamental domain of $\Lambda$ is a measurable set in $\mathbb{R}^{d}$,
denote it by $Q_{M}$, which contains distinct representatives (mod $\Lambda$)
in $\mathbb{R}^{d}$, so that any intersection of $Q_{M}$ with any coset
$x+\Lambda$ has only one element.

Equivalently, $Q_{M}$ is a fundamental domain of $\Lambda$ if it is a tiling
set with respect to $\Lambda$. The existence of fundamental domains is proved
in Theorem 1 in [4]. Any translation of a fundamental domain is also a
fundamental domain, and $\text{Vol}(\Lambda)=|Q_{M}|$.

Notation: For positive quantities $A$ and $B$, by $A\asymp B$ we mean that
there are constants $0<c_{1}\leq c_{2}<\infty$ such that $c_{1}B\leq A\leq
c_{2}B$.

##  3 Proof of Theorem 1.1 and Theorem 1.2

In this section, we connect properties of Gabor systems
$\mathcal{G}(\Omega,\Lambda\times\Gamma)$ with frame spectral pairs and Riesz
spectral pairs in the case where $\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by
$\Lambda$. Here, the sets $\Lambda$ and $\Gamma$ are countable sets that are
not necessarily lattices.

###  3.1 Multi-tiling sets and Gabor frames - Proof of Theorem 1.1

The proof of Theorem 1.2 (i) relies on the following result that describes how
multi-tiling sets can be used to express the norm of a function.

######  Lemma 3.1.

Assume that $(\Omega,\Lambda)$ is a multi-tiling pair of level
$k\in\mathbb{N}$. Then for any $f\in L^{2}(\mathbb{R}^{d})$,

$\displaystyle\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(\Omega+\lambda)}^{2}=k\|f\|^{2}_{L^{2}({\mathbb{R}}^{d})}.$
(4)

###### Proof.

We rewrite the left-hand side of (4) as

$\displaystyle\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(\Omega+\lambda)^{2}}=\sum_{\lambda\in\Lambda}\int_{\mathbb{R}^{d}}|f(x)\chi_{\Omega+\lambda}(x)|^{2}dx=\int_{\mathbb{R}^{d}}\sum_{\lambda\in\Lambda}|f(x)\chi_{\Omega+\lambda}(x)|^{2}dx.$
(5)

The exchange of the integral and series is justified by Fubini’s theorem. For
a.e. $x\in\mathbb{R}^{d}$ we formally define

$g(x):=\sum_{\lambda\in\Lambda}|f(x)\chi_{\Omega+\lambda}(x)|^{2}.$

Since $\Omega$ is a multi-tiling of ${\mathbb{R}}^{d}$ with respect to
$\Lambda$,

for a.e. $x\in\mathbb{R}^{d}$ there are lattice points
$\\{\lambda_{i}(x)\in\Lambda\\}_{1\leq i\leq k}$ such that
$x\in\cap_{i=1}^{k}\Omega+\lambda_{i}(x)$. Therefore, $g(x)$ is a finite sum
for almost every $x\in{\mathbb{R}}^{d}$ and

$g(x)=\sum_{i=1}^{k}|f(x)\chi_{\Omega+\lambda_{i}(x)}(x)|^{2}=\sum_{i=1}^{k}|f(x)|^{2}=k|f(x)|^{2}.$

Substituting this expression into (5), we obtain

$\displaystyle\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(\Omega+\lambda)}=\int_{\mathbb{R}^{d}}g(x)dx=k\int_{\mathbb{R}^{d}}|f(x)|^{2}dx=k\|f\|^{2}.$
(6)

This completes the proof. ∎

######  Remark 3.1.

With the additional assumption that $\Lambda$ is a lattice, Lemma 3.1 can also
be proved by expressing $\Omega$ as the finite union
$\Omega=\cup_{i=1}^{k}E_{i}\cup F$ where $|F|=0$ and $E_{i}$, $1\leq i\leq k$
are fundamental domains of $\Lambda$ (see [20]). Then,

$\displaystyle\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(\Omega+\lambda)}^{2}=\sum_{\lambda\in\Lambda}\sum_{i=1}^{k}\|f\|_{L^{2}(E_{i}+\lambda)}^{2}=\sum_{i=1}^{k}\left(\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(E_{i}+\lambda)}^{2}\right)=\sum_{i=1}^{k}\|f\|^{2}=k\|f\|^{2}.$

We are ready to prove Theorem 1.1.

###### Proof of Theorem 1.1..

(i) Let $(\Omega,\Lambda)$ be a multi-tiling pair and $(\Omega,\Gamma)$ be a
frame spectral pair. We show that
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a frame for
$L^{2}(\mathbb{R}^{d})$. Let $f\in L^{2}(\mathbb{R}^{d})$. For
$\lambda\in\Lambda$ we define $f_{\lambda}:=f\chi_{\Omega+\lambda}\in
L^{2}(\Omega+\lambda)$. By the frame spectral property of
$(\Omega+\lambda,\Gamma)$ we have

$\ell\|f\|_{L^{2}(\Omega+\lambda)}^{2}\leq\sum_{\gamma\in\Gamma}|\langle
f_{\lambda},e_{\gamma}\rangle|_{L^{2}(\Omega+\lambda)}^{2}\leq
u\|f\|_{L^{2}(\Omega+\lambda)}^{2},$

where $\ell$ and $u$ denote the frame constants for the exponential frame
$\\{e^{2\pi ix\cdot\gamma}\\}_{\gamma\in\Gamma}\subset L^{2}(\Omega)$. Summing
over $\Lambda$, we have

$\ell\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(\Omega+\lambda)}^{2}\leq\sum_{\lambda\in\Lambda}\sum_{\gamma\in\Gamma}|\langle
f_{\lambda},e_{\gamma}\rangle_{L^{2}(\Omega+\lambda)}|^{2}\leq
u\sum_{\lambda\in\Lambda}\|f\|_{L^{2}(\Omega+\lambda)}^{2}.$

The frame bounds are obtained using Lemma 3.1,

$k\ell\|f\|^{2}\leq\sum_{\lambda\in\Lambda}\sum_{\gamma\in\Gamma}|\langle
f,e_{\gamma}\chi_{\Omega+\lambda}\rangle_{L^{2}(\mathbb{R}^{d})}|^{2}\leq
ku\|f\|^{2}.$

$(\ref{thm1.1.ii})$

Assume that $\Omega$ is a tiling set and the Gabor system
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a frame. For a fixed
$\lambda_{0}\in\Lambda$ and $f\in L^{2}(\Omega+\lambda_{0})$, we have

$\displaystyle\ell\|f\|_{L^{2}(\mathbb{R}^{d})}^{2}\leq\sum_{(\lambda,\gamma)\in\Lambda\times\Gamma}\left|\langle
f,\chi_{\Omega+\lambda}e_{\gamma}\rangle_{L^{2}(\mathbb{R}^{d})}\right|^{2}\leq
u\|f\|_{L^{2}(\mathbb{R}^{d})}^{2},$ (7)

where $\ell$ and $u$ are the lower and upper frame constants, respectively,
for the Gabor frame $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$. Since
$\Omega$ tiles ${\mathbb{R}}^{d}$ by $\Lambda$, we have that $\langle
f,\chi_{\Omega+\lambda}e_{\gamma}\rangle=0$ for all $\lambda\neq\lambda_{0}$,
and therefore $(\Omega+\lambda_{0},\Gamma)$ is a frame spectral pair, i.e.,

$\displaystyle\ell\|f\|_{L^{2}(\Omega+\lambda_{0})}^{2}\leq\sum_{\gamma\in\Gamma}\left|\langle
f,e_{\gamma}\rangle_{L^{2}(\Omega+\lambda_{0})}\right|^{2}\leq
u\|f\|_{L^{2}(\Omega+\lambda_{0})}^{2}.$ (8)

Now, for any $g\in L^{2}(\Omega)$ take $f(x):=g(x-\lambda_{0})\in
L^{2}(\Omega+\lambda_{0})$ and apply (8), to prove that $(\Omega,\Gamma)$ is a
frame spectral pair. ∎

The converse of Theorem 1.1 does not hold in general. That is, when
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a frame and
$(\Omega,\Gamma)$ is a frame spectral pair, $\Omega$ does not necessarily tile
$\mathbb{R}^{d}$ with $\Lambda$. This is illustrated in the next example.

######  Example 3.1.

Take $\Omega=(0,1)$, $\Lambda=2^{-1}\mathbb{Z}$, and $\Gamma=\mathbb{Z}$. The
set $\Omega$ multi-tiles $\mathbb{R}$ at $k=2$. Also, $(\Omega,\mathbb{Z})$ is
a spectral pair. By Theorem 1.1 (i), the system
$\mathcal{G}(\chi_{\Omega},2^{-1}\mathbb{Z}\times\mathbb{Z})$ is a frame, and
$\Omega$ does not tile $\mathbb{R}$ by $\Lambda$.

###  3.2 Tiling sets and Gabor Riesz bases - Proof of Theorem 1.2

Assume that $(\Omega,\Gamma)$ is a Riesz spectral pair and that
$(\Omega,\Lambda)$ is a multi-tiling pair. We have seen in Example 1.2 that
these assumptions do not guarantee that
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a Gabor Riesz basis for
$L^{2}(\mathbb{R}^{d})$. However, by Theorem 1.1 (i), the system is a Gabor
frame, and, the Ron-Shen Duality Principle can be applied.

######  Example 3.2.

Consider the setting from Example 1.2:
$\Omega=(0,1),\Lambda=2^{-1}\mathbb{Z},\Gamma=\mathbb{Z}$. The system
$\mathcal{G}(\chi_{\Omega},2^{-1}\mathbb{Z}\times\mathbb{Z})$ is a frame by
Theorem 1.1 (i). By the Ron-Shen Duality Principle, the system
$\mathcal{G}(\chi_{\Omega},\mathbb{Z}\times 2\mathbb{Z})$ is a Riesz sequence
in $L^{2}(\mathbb{R}^{d})$. From the other hand,
$\mathcal{G}(\chi_{\Omega},\mathbb{Z}\times
2\mathbb{Z})\subset\mathcal{G}(\chi_{\Omega},\mathbb{Z}\times\mathbb{Z}).$
This implies that $\mathcal{G}(\chi_{\Omega},\mathbb{Z}\times 2\mathbb{Z})$ is
a Bessel sequence. However, the system
$\mathcal{G}(\chi_{\Omega},\mathbb{Z}\times 2\mathbb{Z})$ is not complete.

Theorem 1.2 states that to establish the equivalence of Riesz spectral pairs
and Gabor Riesz bases, a stronger condition is needed.

###### Proof of Theorem 1.2.

$(\ref{thm1.1.i})\Rightarrow(\ref{thm1.1.ii}):$ Assume that $(\Omega,\Gamma)$
is a Riesz spectral pair and $(\Omega,\Lambda)$ is a tiling pair. We show that
the Gabor system (1) is a Riesz basis. Assume that
$\\{a_{\lambda,\gamma}\\}_{(\lambda,\gamma)\in\Lambda\times\Gamma}$ is a
collection of scalar coefficients with finite many non-zero elements. Then, by
the tiling property of $\Omega$ by $\Lambda$, we have

$\displaystyle\left\|\sum_{(\lambda,\gamma)\in\Lambda\times\Gamma}a_{\lambda,\gamma}e_{\gamma}\chi_{\Omega+\lambda}\right\|_{L^{2}(\mathbb{R}^{d})}^{2}$
$\displaystyle=\sum_{\lambda^{\prime}\in\Lambda}\left\|\sum_{(\lambda,\gamma)\in\Lambda\times\Gamma}a_{\lambda,\gamma}e_{\gamma}\chi_{\Omega+\lambda}\right\|_{L^{2}(\Omega+\lambda^{\prime})}^{2}$
$\displaystyle=\sum_{\lambda\in\Lambda}\left\|\sum_{\gamma\in\Gamma}a_{\lambda,\gamma}e_{\gamma}\chi_{(\Omega+\lambda)}\right\|_{L^{2}(\Omega+\lambda)}^{2}$
(9)

By applying the Riesz inequalities for the inner summation we obtain (9)

$\eqref{eq:RZ}\asymp\sum_{\lambda}\sum_{\gamma\in\Gamma}|a_{\lambda,\gamma}|^{2}$

The calculations above prove that the Gabor system in (1) is a Riesz sequence
in $L^{2}(\mathbb{R}^{d})$. The completeness holds by Proposition 1.1.
Moreover, the Riesz frame constants coincide with the frame constants for the
Riesz spectral pair $(\Omega,\Gamma)$.

$(\ref{thm1.1.ii})\Rightarrow(\ref{thm1.1.i}):$ Assume that that
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a Riesz basis and
$(\Omega,\Lambda)$ is a tiling pair. We will prove that $(\Omega,\Gamma)$ is a
Riesz spectral pair. For this, fix $\lambda_{0}\in\Lambda$. By Proposition
1.1, the pair $(\Omega+\lambda_{0},\Gamma)$ is a frame pair. So, we only need
to prove that the set of exponential functions $\mathcal{E}(\Gamma)$ form a
Riesz sequence in $L^{2}(\Omega+\lambda_{0})$. Let
$\\{a_{\gamma}\\}_{\gamma\in\Gamma}$ be a sequence of scalars where only
finite many are none-zero. For any $(\lambda,\gamma)\in\Lambda\times\Gamma$,
define $b_{\lambda,\gamma}:=a_{\gamma}$ if $\lambda=\lambda_{0}$, and $0$
otherwise. Therefore $\\{b_{\lambda,\gamma}\\}_{\Lambda\times\Gamma}$ is a
sequence with finitely many non-zero elements. By the Riesz inequality for
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ with the frame constants
$0<\ell\leq u<\infty$, we then have

$\displaystyle\ell\sum_{\gamma\in\Gamma}|b_{\lambda_{0},\gamma}|^{2}\leq\left\|\sum_{\gamma\in\Gamma}b_{\lambda_{0},\gamma}\chi_{\Omega+\lambda_{0}}e_{\gamma}\right\|^{2}\leq
u\sum_{\gamma\in\Gamma}|b_{\lambda_{0},\gamma}|^{2},$ (10)

or,

$\displaystyle\ell\sum_{\gamma\in\Gamma}|a_{\gamma}|^{2}\leq\left\|\sum_{\gamma\in\Gamma}a_{\gamma}e_{\gamma}\right\|_{L^{2}(\Omega+\lambda_{0})}^{2}\leq
u\sum_{\gamma\in\Gamma}|a_{\gamma}|^{2}.$ (11)

This proves that $\mathcal{E}(\Gamma)$ is a Riesz sequence for
$L^{2}(\Omega+\lambda_{0})$ with the same Riesz constants as the Gabor Riesz
basis. The completeness of the exponentials $\mathcal{E}(\Gamma)$ is due to
Proposition 1.1. Thus, $(\Omega+\lambda_{0},\Gamma)$ is a Riesz spectral pair.
Since the Riesz basis property of $\mathcal{E}(\Gamma)$ is invariant under the
translation of the domain, we conclude that $(\Omega,\Gamma)$ is also a Riesz
spectral pair, and that completes the proof of the first part of the theorem.

Next we compute the biorthogonal basis for the Gabor Riesz basis. The
biorthogonal basis for a Gabor Riesz basis
$\mathcal{G}(\Omega,\Lambda\times\Gamma)$ is a unique family of functions
$\\{g_{\lambda,\gamma}\\}_{\Lambda\times\Gamma}$ such that for any pairs
$(\lambda,\gamma)$ and $(\lambda^{\prime},\gamma^{\prime})$

$\langle
e_{\gamma}\chi_{\Omega+\lambda},g_{\lambda,\gamma}\rangle=\delta_{\lambda,\lambda^{\prime}}\delta_{\gamma,\gamma^{\prime}}$

Let $(\Omega,\Gamma)$ be a Riesz spectral pair, and let
$\\{g_{\gamma}\\}_{\gamma\in\Gamma}$ denote the dual Riesz basis in
$L^{2}(\Omega)$. The dual Riesz basis for the Riesz spectral pair
$(\Omega+\lambda,\Gamma)$ is given as

$\displaystyle\\{e_{\gamma}(\lambda)g_{\gamma}(\cdot-\lambda)\chi_{\Omega+\lambda}\\}_{\gamma\in\Gamma}.$
(12)

We prove that, under the assumption $e_{\gamma}(\lambda)=1$ for all
$\gamma,\lambda$, the system

$\displaystyle\\{g_{\gamma}(\cdot-\lambda)\chi_{\Omega+\lambda}\\}_{\gamma\in\Gamma,\lambda\in\Lambda}$
(13)

is biorthogonal to $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$, thus it
is the dual basis. Let
$(\lambda,\gamma)\neq(\lambda^{\prime},\gamma^{\prime})$. If
$\lambda\neq\lambda^{\prime}$, due to the disjointess of the sets
$\Omega+\lambda$ and $\Omega+\lambda^{\prime}$, the functions
$e_{\gamma}\chi_{\Omega+\lambda}$ and
$g_{\gamma^{\prime}}(\cdot-{\lambda^{\prime}})\chi_{\Omega+\lambda^{\prime}}$
are orthogonal. Now assume that $\lambda=\lambda^{\prime}$, then we must have
$\gamma\neq\gamma^{\prime}$. Orthogonality also holds due the following
equality:

$\langle
e_{\gamma},g_{\gamma^{\prime}}(\cdot-\lambda)\rangle_{L^{2}(\Omega+\lambda)}=\langle
e_{\gamma}(\lambda)e_{\gamma},g_{\gamma^{\prime}}\rangle_{L^{2}(\Omega)}=\langle
e_{\gamma},g_{\gamma^{\prime}}\rangle_{L^{2}(\Omega)}=\delta_{\gamma,\gamma^{\prime}}.$

This completes the proof. ∎

###  3.3 Stability of Gabor Riesz bases

In this section, we show the stability results with respect to the time-
frequency shifts set $\Lambda\times\Gamma$.

######  Definition 3.1.

Given a countable set $\Gamma\subset{{\mathbb{R}}^{d}}$, we say the sequence
${\Gamma}_{p}=\\{\kappa_{\gamma}\\}_{\gamma\in\Gamma}\subset\mathbb{R}^{d}$ is
a perturbation of $\Gamma$ with constant $c>0$ if $|\gamma-\kappa_{\gamma}|<c$
for all $\gamma\in\Gamma$.

We recall the classical Paley-Wiener theorem (see e.g. [2]).

######  Theorem 3.1 (Paley-Wiener Theorem).

Let $\\{f_{i}\\}_{i\in I}$ be basis for the Banach space $X$, let
$\\{g_{i}\\}_{i\in I}$ be a family of vectors in $X$. Assume that there exists
a constant $\lambda\in[0,1)$ such that for any sequence $\\{c_{i}\\}_{i\in I}$
with finite many non-zero elements,

$\left\|\sum_{i}c_{i}(f_{i}-g_{i})\right\|\leq\lambda\left\|\sum_{i}c_{i}f_{i}\right\|.$

Then $\\{g_{i}\\}$ is a basis for $X$.

Applying the Paley-Wiener theorem, we obtain the following stability result in
terms of Kadec’s 1/4 theorem for exponential Riesz bases.

######  Proposition 3.1 (Kadec’s $1/4$ Theorem for exponential Riesz bases).

Assume that $\Omega\subset\mathbb{R}^{d}$ has finite and positive measure. Let
the system $\mathcal{E}({\Gamma})$ be a Riesz basis for $L^{2}(\Omega)$. Then
there is a positive constant $0<L<1$ such that for any $\Gamma_{p}$,
permutation of $\Gamma$, with $0<c\leq L$, the system of exponential functions
$\mathcal{E}(\Gamma_{p})$ is also a Riesz basis for $L^{2}(\Omega)$.

The set $\mathcal{E}(\Lambda)$ is called an unconditional basis for
$L^{2}(\Omega)$ if it is complete and each element in $f\in L^{2}(\Omega)$ can
be represented uniquely as $f=\sum_{\lambda]in\Lambda}c_{\lambda}e^{2\pi
i\lambda\cdot x}$ where the series converges in norm and unconditionally.

Proposition 3.1 is well-known in dimension $d=1$ for unconditional bases (see
e.g. [26]). The result extends to Riesz bases of exponentials in higher
dimensions as a consequence of the classical Paley-Wiener Theorem 3.1 as
follows:

###### Proof of Proposition 3.1.

Any Riesz basis is an unconditional basis, and by the assumptions of
Proposition 3.1 and the Paley-Wiener theorem, for any small perturbation
$\Gamma_{p}$ with $c$ sufficiently small (as in Definition 3.1),
$\mathcal{E}(\Gamma_{p})$ also is an unconditional basis for $L^{2}(\Omega)$.
To prove that $\mathcal{E}(\Gamma_{p})$ is a Riesz sequence, notice that any
mapping on $L^{2}(\Omega)$ defined by $e^{2\pi i\lambda}\to e^{2\pi
i\kappa_{\lambda}}$ can be extended to an isomorphism on $L^{2}(\Omega)$. This
proves that the Riesz inequalities hold for $\mathcal{E}(\Gamma_{p})$, whence
the claim. ∎

We conclude this section with a Paley-Wiener theorem for Gabor orthogonal
bases and prove the stability of Gabor Riesz bases with separable time-
frequency shifts domain.

######  Corollary 3.1 (Paley-Wiener theorem for Gabor orthogonal bases).

Assume that $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is an orthogonal
basis for $L^{2}(\mathbb{R}^{d})$. Assume that
$\Gamma_{p}=\\{\kappa_{\gamma}\\}_{\gamma\in\Gamma}\subset\mathbb{R}^{d}$ is a
countable set such that for some constant $0\leq L<1$ we have

$\displaystyle|\gamma-\kappa_{\gamma}|<L,\quad\forall\gamma\in\Gamma.$ (14)

If $L$ is small enough, then
$\mathcal{G}(\chi_{\Omega},(\Lambda+\alpha)\times\Gamma_{p})$ is a Gabor Riesz
basis for $L^{2}(\mathbb{R})$, $\alpha>0$.

###### Proof.

By the assumption that $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is an
orthogonal basis, the pair $(\Omega,\Lambda)$ is a tiling pair and
$(\Omega,\Gamma)$ is a spectral pair [23]. By Proposition 3.1 and the
condition (14), $\mathcal{E}(\Gamma_{p})$ is a Riesz basis for
$L^{2}(\Omega)$. By applying Theorem 1.2 to the tiling pair
$(\Omega,\Lambda+\alpha)$ and the Riesz spectral pair $(\Omega,\Gamma_{c})$,
the assertion of the corollary holds, i.e.
$\mathcal{G}(\chi_{\Omega},(\Lambda+\alpha)\times\Gamma_{c})$ is a Gabor Riesz
basis for $L^{2}(\mathbb{R})$. ∎

##  4 Lattice Zak transform

The classical Zak transform is associated with lattices of the form
$\alpha{\mathbb{Z}}^{d}$. The case $d=1$ was introduced in [19]. For the
definition of the classical Zak transform in higher dimensions see e.g. [11].
Here, we introduce an extension to the lattice $M(\mathbb{Z}^{d})$.

######  Definition 4.1 (Lattice Zak transform).

For a full rank lattice $M(\mathbb{Z}^{d})$, we formally define the lattice
Zak transform of a function $f$ by

$\displaystyle
Z_{M}f(x,\xi):=|Q_{M}|^{1/2}\sum_{n\in\mathbb{Z}^{d}}f(x+M(n))e^{2\pi
i\xi\cdot M(n)}\quad(x,\xi)\in\mathbb{R}^{d}\times\mathbb{R}^{d}.$ (15)

When $M=I$, where $I$ is the $d\times d$ identity matrix, we omit the
subscript and denote the Zak transform of $f$ by $Zf$.

Let $M$ and $N$ be any $d\times d$ full rank matrix such that $N^{T}M$ is a
matrix with integer entries. The Zak transform $Z_{M}$ clearly possesses
quasi-periodicity relations with respect to the lattices $M(\mathbb{Z}^{d})$
and $N(\mathbb{Z}^{d})$:

$\displaystyle Z_{M}f(x+M(m),\xi)$ $\displaystyle=e^{-2\pi i\xi\cdot
M(m)}Z_{M}f(x,\xi)$ (16) $\displaystyle Z_{M}f(x,\xi+N(m))$
$\displaystyle=Z_{M}f(x,\xi).$ (17)

The quasi-periodicity of the transform shows that the values of the transform
on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ is completely determined by its values
on $Q_{M}\times Q_{N}$.

######  Remark 4.1.

The definition of the lattice Zak transform in Definition 4.1 coincides with
the classical definition of the Zak transform when $M=\text{diag}(\alpha)$ is
a diagonal $d\times d$ matrix with $\alpha$ in diagonal entries. The quasi-
periodicity is an extension in the classical case when $N=\text{diag}(\beta)$
with $\alpha\beta=1$. For some properties of classical Zak transforms see e.g.
[18] and [13].

A generalized Zak transform in the setting of unitary group representation
theory was defined for arbitrary Hilbert spaces by Hernández and co-authors in
[14]. The definition relies on a unitary map that the authors termed the
Bracket map. The classical Zak transform is a restriction of the generalized
Zak transform to the case when the Hilbert transform is
$L^{2}(\mathbb{R}^{d})$ and the unitary representation (Gabor) is defined on
$\alpha\mathbb{Z}^{d}\times\beta\mathbb{Z}^{d}$. For non-commutative cases,
e.g. the Heisenberg group, see [1].

###  4.1 Common fundamental domains for lattices

Recall that two full rank lattices in ${\mathbb{R}}^{d}$ with the same volume
have a common fundamental domain that is a tiling with respect to both
lattices.

######  Theorem 4.1 (Theorem 1.1 in [12]).

Let $M(\mathbb{Z}^{d})$ and $N(\mathbb{Z}^{d})$ be two full rank lattices in
$\mathbb{R}^{d}$ such that
$\text{Vol}(M(\mathbb{Z}^{d}))=\text{Vol}(N(\mathbb{Z}^{d}))$. Then
$M(\mathbb{Z}^{d})$ and $N(\mathbb{Z}^{d})$ have a common fundamental domain.
That is, there exists a measurable set $Q\subset\mathbb{R}^{d}$ such that $Q$
is a tiling set with respect to both $M(\mathbb{Z}^{d})$ and
$N(\mathbb{Z}^{d})$.

An immediate corollary of this theorem is our next result that the same result
holds for lattices with the same density.

######  Corollary 4.1.

Let $M(\mathbb{Z}^{d})$ and $N(\mathbb{Z}^{d})$ be two full rank lattices in
$\mathbb{R}^{d}$ such that $den(M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))=1$.
Then $M(\mathbb{Z}^{d})$ and $(N(\mathbb{Z}^{d}))^{\perp}$ have common
fundamental domains.

###### Proof.

Note that $den(M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))=1$ implies
$\det(MN)=1$, or $\det(M)=\det(N^{-1})=\det(N^{-T})$. Since
$\text{Vol}(\Lambda)=|\det(M)|=|\det(N^{-T})|=\text{Vol}((N(\mathbb{Z}^{d}))^{\perp})$,
the claim follows by Theorem 4.1. ∎

Another consequence of Theorem 4.1 is our next result which states that
orthogonal Gabor bases can be constructed using two full-rank lattices that
have a common fundamental domain:

######  Corollary 4.2.

Let $M$ and $N$ be full rank $d\times d$ matrices such that $\det(MN)=1$ and
$N^{T}M$ is an integer matrix. Then $\mathcal{E}(N(\mathbb{Z}^{d}))$ is an
orthogonal basis for $L^{2}(Q)$, where $Q$ is the common fundamental domain
for the lattices $M(\mathbb{Z}^{d})$ and $N^{-T}(\mathbb{Z}^{d})$, and the
Gabor system $\mathcal{G}(\chi_{Q},M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$
is an orthogonal basis for $L^{2}(\mathbb{R}^{d})$.

The assumptions of Corollary 4.2 always hold for the choice $N:=M^{-T}$. In
one dimension, this is the only choice for $N$, but in higher dimensions,
there are examples of $N$ for which $N\neq M^{-T}$ and $M^{T}N$ is an integer
matrix. The next example illustrates this.

######  Example 4.1.

Figure 1: The fundamental domains for lattices $M({\mathbb{Z}}^{d})$ and
${{N}^{-T}}({\mathbb{Z}}^{d})$ coincide and are different than the fundamental
domain for the lattice ${M^{-T}}({\mathbb{Z}}^{d})$.

Let $M=\begin{bmatrix}\sqrt{2}&0\\\ 1&1\end{bmatrix}$ and
$N=\begin{bmatrix}\sqrt{2}^{-1}&-\sqrt{2}\\\ 0&1\end{bmatrix}$. Then $N\neq
M^{-T}$, however $N^{T}M$ is an integer matrix. The common fundamental domain
for the lattices $\Lambda=M(\mathbb{Z}^{d})$ and
$\Gamma^{\perp}=N^{-T}(\mathbb{Z}^{d})$ is given by the parallelogram with
vertices in the set $\\{(0,0),(0,1),(\sqrt{2},1),(\sqrt{2},2)\\}$. The
fundamental domains $Q=Q_{M}=Q_{N^{-T}}$ and $Q_{M^{-T}}$ are shown in Figure
1.

More generally, let $a$ and $d$ be any numbers such that $ad\neq 0$, and let
$k,\ell,m,n$ be integers such that $\ell\neq 0$, $n\neq m$. Take $M,N$ to be
the matrices

$M=\begin{bmatrix}a&0\\\ c&d\end{bmatrix},\quad
N=\begin{bmatrix}\cfrac{nd-k}{da}&\cfrac{md-\ell}{da}\\\
\cfrac{k}{d}&\cfrac{\ell}{d}\end{bmatrix}.$

Then, $\det(MN)=1$, $N^{T}M$ is an integer matrix, and $N\neq M^{-T}$.

###  4.2 The lattice Zak transform is isometric

Proposition 4.1 justifies the definition and isometry property of the lattice
Zak transform.

######  Proposition 4.1.

Let $M$ and $N$ be full rank $d\times d$ matrices such that $\det(MN)=1$ and
$MN^{T}$ is an integer matrix. Then the Zak transform is a unitary map from
$L^{2}(\mathbb{R}^{d})$ onto $L^{2}(Q_{M}\times Q_{N})$, and for any $f\in
L^{2}(\mathbb{R}^{d})$,

$\displaystyle\|Z_{M}f\|_{L^{2}(Q_{M}\times
Q_{N})}=\|f\|_{L^{2}(\mathbb{R}^{d})}.$ (18)

###### Proof.

We give a sketch of the proof here. First, we write the left side of (18) in
terms of the inner product. From Corollary 4.2, the exponentials
$\mathcal{E}(M({\mathbb{Z}}^{d}))$ are orthogonal on $Q_{N}$ and
$|Q_{M}|=|Q_{N}|^{-1}$. This proves the isometry, thus the injectivity of the
map. The proof of subjectivity can be obtained with a similar argument used in
Theorem 4.3.2 of [13]. Indeed, the image of the Gabor orthogonal basis
$\mathcal{G}(\chi_{Q_{M}},M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ for
$L^{2}(\mathbb{R}^{d})$ under the map $Z_{M}$ is the orthogonal exponential
basis $\mathcal{E}(M^{-T}(\mathbb{Z}^{d})\times N^{-T}(\mathbb{Z}^{d}))$ for
$L^{2}(Q_{M}\times Q_{N})$. This shows that $Z_{M}$ is surjective, completing
the proof. ∎

###  4.3 Zeros of the lattice Zak transforms

In one dimension, the continuity of the Zak transform implies the existence of
a zero on the domain (see e.g. [19] or Theorem 4.3.4 in [13] and the
references therein). In the following lemma we extend this result to lattice
Zak transforms. The proof follows from a modification of the argument used in
dimension $d=1$.

######  Lemma 4.1.

For $f\in L^{2}(\mathbb{R}^{d})$, if the Zak transform $Z_{M}f$ is continuous
on $\mathbb{R}^{d}\times{\mathbb{R}^{d}}$, then it must have a zero.

###### Proof.

Assume, for contradiction, that $Z_{M}f$ has no zeros. That is,
$Z_{M}f(x,\xi)\neq 0$ for all $(x,\xi)\in Q_{M}\times Q_{N}$. Consider the
mapping from $\mathbb{R}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$ given by

$(x,\xi)\mapsto\cfrac{Z_{M}f(x,\xi)}{|Z_{M}f(x,\xi)|}.$

The map is well-defined and continuous. Since
$\mathbb{R}^{d}\times\mathbb{R}^{d}$ is simply connected, there is a
continuous real-valued function
$\varphi:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$, also known as an
argument function, such that

$\displaystyle e^{2\pi
i\varphi(x,\xi)}=\cfrac{Z_{M}f(x,\xi)}{|Z_{M}f(x,\xi)|}\quad\quad\forall~{}(x,\xi)\in{\mathbb{R}}^{d}\times{\mathbb{R}}^{d},$
(19)

due to Lemma 7, Sec. VI.1 in [24].

The quasi-periodic properties (16) and (17) of the Zak transform then imply
that for all $(x,\xi)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$ and
$n\in\mathbb{Z}^{d}$,

$\displaystyle e^{2\pi i\varphi(x+M(n),\xi)}$ $\displaystyle=e^{-2\pi
i\xi\cdot M(n)}e^{2\pi i\varphi(x,\xi)}$ $\displaystyle e^{2\pi
i\varphi(x,\xi+N(n))}$ $\displaystyle=e^{2\pi i\varphi(x,\xi)}.$

Since $N^{T}M$ is an integer matrix, there are integers $k_{(x,\xi,n)}$ and
$\ell_{(x,\xi,n)}$ such that

$\displaystyle\varphi(x+M(n),\xi)-\varphi(x,\xi)+\xi\cdot M(n)$
$\displaystyle=k_{(x,\xi,n)}$ (20)
$\displaystyle\varphi(x,\xi+N(n))-\varphi(x,\xi)$
$\displaystyle=\ell_{(x,\xi,n)}.$ (21)

Both (20) and (21) equate a continuous function of $x$ and $\xi$ with a
discrete function of $x$ and $\xi$. This implies that for any
$n\in\mathbb{Z}^{d}$, $k_{n}:=k_{(x,\xi,n)}$ and $\ell_{n}:=\ell_{(x,\xi,n)}$
must be constant for all $(x,\xi)$. Let ${\bf 0}$ denote the zero vector, and
$e_{1}$ denote the first vector in standard basis for $\mathbb{R}^{d}$ (or
$e_{k}$, where $a_{kk}$ is the first nonzero diagonal entry of the matrix
$N^{T}M$). We can calculate $\varphi(M(e_{1}),N(e_{1}))$ in two different ways
using equations (20) and (21): First, for $x=0$, $n=e_{1}$ and $\xi=N(e_{1})$,

$\displaystyle\varphi(M(e_{1}),N(e_{1}))=\varphi({\bf 0}+M(e_{1}),N(e_{1}))$
$\displaystyle\overbrace{=}^{by~{}\eqref{eq:varphi1}}\varphi({\bf
0},N(e_{1}))+1+k_{e_{1}}\overbrace{=}^{by~{}\eqref{eq:varphi2}}\varphi({\bf
0},{\bf 0})+\ell_{e_{1}}+1+k_{e_{1}}.$

Secondly, $x=M(e_{1})$, $n=e_{1}$ and $\xi=0$, and therefore

$\displaystyle\varphi(M(e_{1}),N(e_{1}))=\varphi(M(e_{1}),{\bf 0}+N(e_{1}))$
$\displaystyle\overbrace{=}^{by~{}\eqref{eq:varphi2}}\varphi(M(e_{1}),{\bf
0})+\ell_{e_{1}}\overbrace{=}^{by~{}\eqref{eq:varphi1}}\varphi({\bf 0},{\bf
0})+k_{e_{1}}+\ell_{e_{1}}.$

This is a contradiction because the right-hand sides of the last two equations
can never be equal. Therefore, the Zak transform must have a zero. ∎

######  Example 4.2 (Gaussian).

Figure 4(b) shows plots of the one-dimensional Gaussian function $f(x)=e^{-\pi
x^{2}}$ and the magnitude of $Zg$. The Zak transform $Zg$ is a continues
function. By direct computation it is seen that $Zg$ has a zero at
$x=1/2,\xi=1/2$.

##  5 Characterization of Gabor systems with lattice time-frequency shifts -
Proofs of Theorem 1.3 and Theorem 1.4

This section aims to prove that for given pair of full rank matrices $M$ and
$N$ with $\det(MN)=1$ and $N^{T}M$ an integer matrix, for a given multi-tiling
set $\Omega$ with respect to lattice $M(\mathbb{Z}^{d})$, the necessary
condition of the Gabor system
$\mathcal{G}(\chi_{\Omega},M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ to be a
frame for $L^{2}(\mathbb{R}^{d})$ is that $\Omega$ is a tiling. We then
conclude that under the assumptions for $M$ and $N$, any Riesz Gabor basis
$\mathcal{G}(\chi_{\Omega},M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is an
orthogonal basis.

###  5.1 Gabor systems for any window and lattice Zak transform

We prove the following result which is similar to the result when the time-
frequency shift domain is in the form of
$\alpha\mathbb{Z}^{d}\times\beta\mathbb{Z}^{d}$, $\alpha\beta\neq 0$.

######  Proposition 5.1.

Assume that $M$ and $N$ are full rank $d\times d$ matrices such that
$\det(MN)=1$ and $N^{T}M$ is an integer matrix. Let $Z_{M}$ be the Zak
transform given by (15) with respect to $M(\mathbb{Z}^{d})$. Then for any
$g\in L^{2}(\mathbb{R}^{d})$ the following holds:

  1. (i)

$\mathcal{G}(g,M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is complete if and
only if $Z_{M}g(x,\xi)\neq 0$ for a.e. $x\in Q_{M}$ and $\xi\in Q_{N}$.

  2. (ii)

The following statements are equivalent:

    1. (a)

There are constants $0<\ell\leq u<\infty$ such that
$\ell\leq|Z_{M}g(x,\xi)|\leq u$ for. a.e. $x\in Q_{M}$ and $\xi\in Q_{N}$.

    2. (b)

$\mathcal{G}(g,M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is a frame.

    3. (c)

$\mathcal{G}(g,M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is a Riesz basis.

  3. (iii)

$\mathcal{G}(g,M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is an orthogonal
basis if and only if $|Z_{M}g(x,\xi)|=1$ for a.e. $x\in Q_{M}$ and $\xi\in
Q_{N}$.

###### Proof.

Here we only prove (i) as the rest can be obtained similarly. As before, take
$\Lambda=M(\mathbb{Z}^{d})$ and $\Gamma=N(\mathbb{Z}^{d})$. Assume that
$Z_{M}g\neq 0$ almost everywhere. We prove that the Gabor system is complete.
For this, assume that there is a function $h\in L^{2}(\mathbb{R}^{d})$ such
that $\langle h,g(\cdot-\lambda)e^{2\pi i\gamma\cdot(\cdot)}\rangle=0$ for all
$\lambda\in\Lambda$ and $\gamma\in\Gamma$. Since the Zak transform is a
unitary map, $\langle
Z_{M}h,e_{\lambda}e_{\gamma}Z_{M}g\rangle=\langle(Z_{M}h)(Z_{M}g),e_{\lambda}e_{\gamma}\rangle=0.$
Since $\\{e_{\lambda}e_{\gamma}\\}_{(\lambda,\gamma)\in\Lambda\times\Gamma}$
is a complete system in $L^{2}(Q_{M}\times Q_{N})$, then we must have
$(Z_{M}g)(Z_{M}h)=0$ a.e. Since $Z_{M}g\neq 0$ a.e., by the unitary property
of $Z_{M}$, the latter implies that $h=0$ a.e. Thus
$\mathcal{G}(g,M({\mathbb{Z}}^{d})\times N({\mathbb{Z}}^{d}))$ is complete.
The other direction holds because $g\neq 0$ and $Z_{M}$ is a unitary map. ∎

Our next result applies Proposition 5.1 to characteristic functions of multi-
tiling sets.

######  Corollary 5.1.

Let $M(\mathbb{Z}^{d})$ and $N(\mathbb{Z}^{d})$ be full rank lattices such
that $\det(MN)=1$ and $N^{T}M$ is an integer matrix. Assume that
$\Omega\subset{\mathbb{R}}^{d}$ is a multi-tiling set with respect to
$M(\mathbb{Z}^{d})$ at level $k$. Then
$\mathcal{G}(\chi_{\Omega},M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is
complete and has a positive upper Riesz bound.

###### Proof.

To prove our claim, it is sufficient to show that for $g=\chi_{\Omega}$ we
have

$0<|Z_{M}g(x,\xi)|\leq k\quad\text{for a.e. }(x,\xi)\in Q_{M}\times Q_{N}.$

By the multi-tiling property of $\Omega$ by lattice $M(\mathbb{Z}^{d})$, for
a.e. $x\in\mathbb{R}^{d}$, there are exactly $k$ multi-integers
$n_{1}(x),\cdots,n_{k}(x)\in\mathbb{Z}^{d}$ such that

$x\in\cap_{i=1}^{k}\Omega+M(n_{i}(x)),$

and there is no other $n$ such that $x\in\Omega+M(n)$. This implies that for
almost every $(x,\xi)\in Q_{M}\times Q_{N}$ we have

$\displaystyle Z_{M}g(x,\xi)=\sum_{i=1}^{k}\chi_{\Omega+M(n_{i}(x))}(x)e^{2\pi
i\xi\cdot M(n_{i}(x))}=\sum_{i=1}^{k}e^{2\pi i\xi\cdot M(n_{i}(x))}.$ (22)

Now the final result follows by taking the modulus of $Z_{M}g$, using the
triangle inequality, and applying Proposition 5.1 (i). ∎

Proposition 5.1 can be used more generally to characterize window functions
for Gabor frames, Gabor Riesz bases, and complete Gabor systems with spectrum
$M({\mathbb{Z}}^{d})\times N({\mathbb{Z}}^{d})$ (specific examples are given
later in Section 5.4).

###  5.2 Multi-tiling and lattice Zak transform

Suppose that $\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by a lattice $\Lambda$ at
level $k$.

The following key lemma gives the existence of an open set
$D\subset{\mathbb{R}}^{d}$ in the intersection of translates of $\Omega$ by
$k$ distinct points in $\Lambda$.

######  Lemma 5.1.

Let $\Omega$ be a multi-tiling set at level $k\geq 1$ with respect to a
lattice $M({\mathbb{Z}}^{d})$. Then, for each $x\in Q_{M}$ there is an open
set $D$ containing $x$ and lattice points $\lambda_{i}=\lambda_{i}(x)\in
M({\mathbb{Z}}^{d}),1\leq i\leq k$, for which $|D|>0$ and

$D\subset\cap_{i=1}^{k}\left(\Omega+\lambda_{i}\right).$

###### Proof.

Without loss of generality, assume that $\Omega$ is an open set. Let $Q_{M}$
denote a fundamental domain of the lattice, and let $x\in Q_{M}$. By the
$k-$tiling property there are exactly $k$ lattice points $\lambda_{i}(x)\in
M({\mathbb{Z}}^{d})$ such that $x\in\cap_{i=1}^{k}(\Omega+\lambda_{i}(x))$.
Since the intersection of finitely many open sets is an open set, there exists
an open neighborhood $N_{x}\subset Q_{M}$ of $x$ such that
$N_{x}\subset\cap_{i=1}^{k}\left(\Omega+\lambda_{i}(x)\right)$.

Now, assume for contradiction that there is a $\lambda\in
M({\mathbb{Z}}^{d})\backslash\\{\lambda_{i}(x)\\}_{i=1}^{k}$ such that
$N_{x}\cap(\Omega+\lambda)\neq\emptyset$. Let $t\in
N_{x}\cap(\Omega+\lambda)$. Since $N_{x}$ is open it contains a neighborhood
$N_{x,t}\subset N_{x}$ of $t$ such that $N_{x,t}\subset\Omega+\lambda$. This
implies that almost every point of $N_{x,t}$ is covered by at least $k+1$
translations of $\Omega$ by the set $M({\mathbb{Z}}^{d})$, contradicting the
$k$-tiling property of $\Omega$. Taking $D:=N_{x}$ and
$\lambda_{i}=\lambda_{i}(x)$, we have that $D\subset Q_{M}$ and
$D\subset\cap_{i=1}^{k}(\Omega+\lambda_{i})$. This completes the proof. ∎

######  Theorem 5.1.

Assume that $M$ and $N$ are full rank $d\times d$ matrices such that
$\det(MN)=1$ and $N^{T}M$ is an integer matrix. Let $g=\chi_{\Omega}$, where
$\Omega$ is a multi-tiling set at level $k\geq 1$ with respect to the lattice
$\Lambda=M(\mathbb{Z}^{d})$. If $k>1$, then $Z_{M}g$ given as in (15) has a
zero in $Q_{M}\times Q_{N}$.

###### Proof.

As before, $Q_{M}$ denote a fundamental domain of the lattice
$\Lambda=M(\mathbb{Z}^{d})$. By Lemma 5.1, for any $x\in Q_{M}$ there exists
an open set $x\in D\subset Q_{M}$ and lattice points
$\\{\lambda_{i}\\}_{i=1}^{k}\subset\Lambda$ such that
$D\subset\cap_{i=1}^{k}(\Omega+\lambda_{i})$, and $k$ is the maximum number of
lattice points $\lambda_{i}$ such that $D$ intersects $\Omega+\lambda$. Thus
for a.e. $\xi\in Q_{N}$ we have

$\displaystyle
Z_{M}g(x,\xi)=\sum_{n\in\mathbb{Z}^{d}}\chi_{\Omega+M(n)}(x)e^{2\pi
iM(n)\cdot\xi}=\sum_{i=1}^{k}\chi_{\Omega+M(n_{i})}(x)e^{2\pi
iM(n_{i})\cdot\xi}=\sum_{i=1}^{k}e^{2\pi iM(n_{i})\cdot\xi}.$ (23)

Therefore, the function $Zg$ is continuous in $Q_{M}\times Q_{N}$, and by
Lemma 4.1, its zero set is not empty. ∎

Remark: Notice that the continuity of the Zak transform in Theorem 5.1 is
directly obtained from the fact that for any point $(x_{0},\xi_{0})$ and small
neighborhood of it, the lattice points $M(n_{i})$ are same. Indeed, let
$(x_{n},\xi_{n})\to(x_{0},\xi_{0})$. Then for any $\epsilon>0$ there is an
$N_{0}>0$ such that for any $n>N_{0}$,
$|(x_{n},\xi_{n})-(x_{0},\xi_{0})|<\epsilon$, by Lemma 5.1 the set of finite
lattice points are the same: For all $n>N_{0}$,
$\\{M(n_{i}(x_{n}))\\}_{i=1}^{k}=\\{M(n_{i}(x_{0}))\\}_{i=1}^{k}$.

###  5.3 Proofs of Theorem 1.3 and Theorem 1.4

The Fuglede Conjecture asserts that any tiling set in $\mathbb{R}^{d}$ admits
an orthogonal basis of exponential forms and vice versa. In 1974, Fuglede
proved the assertion under the lattice assumption. Indeed, he proves that if
(T) $\Omega$ tiles $\mathbb{R}^{d}$ by translation of a lattice $\Lambda$,
then (S) $\mathcal{E}(\Lambda^{\perp})$ is an orthogonal exponential basis for
$L^{2}(\Omega)$ and vice versa. Below, in Theorem 5.2 we prove that if the set
tiles by a lattice, then it has exponential basis with respect to a class of
certain lattices. This can be considered as a slight extension of Fuglede’s
result for lattices in direction (T) $\Rightarrow$ (S).

######  Theorem 5.2 ($T\Rightarrow S$ direction of Fuglede Conjecture holds
for two lattices).

Let $M(\mathbb{Z}^{d})$ and $N(\mathbb{Z}^{d})$ be full rank lattices such
that $\det(MN)=1$ and $N^{T}M$ is an integer matrix. Let
$\Omega\subset\mathbb{R}^{d}$ be a domain with finite and positive measure. If
$\Omega$ tiles $\mathbb{R}^{d}$ by $M(\mathbb{Z}^{d})$, then
$\mathcal{E}(N(\mathbb{Z}^{d}))$ is an orthogonal exponential basis for
$L^{2}(\Omega)$.

###### Proof.

Let $g=\chi_{\Omega}$. If $\Omega$ is a tiling set, by a similar calculation
as in the proof of Corollary 5.1 we can show that $|Z_{M}g|=1$ a.e. on
$Q_{M}\times Q_{N}$. Thus by Proposition 5.1 the system
$\mathcal{G}(\chi_{\Omega},M(\mathbb{Z}^{d})\times N(\mathbb{Z}^{d}))$ is an
orthogonal basis. The Gabor basis is separable, thus by a result in [23]
$\mathcal{E}(N(\mathbb{Z}^{d}))$ is an orthogonal basis for $L^{2}(\Omega)$. ∎

Now we are ready to prove our two main results here.

###### Proof of Theorem 1.3.

If $\Omega$ multi-tiles ${\mathbb{R}}^{d}$ by $M(\mathbb{Z}^{d})$ at level
$k>1$, then by Theorem 5.1 the Zak transform has a zero, therefore it can not
be bounded from below. This contradicts the frame assumption of the Gabor
system. Therefore it has to tile. Since $\Omega$ tiles with the lattice
$\Lambda$, then by Theorem 5.2 the exponential set
$\mathcal{E}(N(\mathbb{Z}^{d}))$ form an orthogonal basis for $L^{2}(\Omega)$.
This completes the proof. ∎

###### Proof of Theorem 1.4.

We only prove that if $\mathcal{G}(\chi_{\Omega},M(\mathbb{Z}^{d})\times
N(\mathbb{Z}^{d}))$ is frame, then the orthogonality holds. Indeed, by the
lower frame bound and Theorem 1.3, the set $\Omega$ must tile $\mathbb{R}^{d}$
by $M(\mathbb{Z}^{d})$, and by Theorem 5.2 the exponentials set
$\mathcal{E}(N(\mathbb{Z}^{d}))$ is an orthogonal basis for $L^{2}(\Omega)$.
Therefore, $\mathcal{G}(\chi_{\Omega},M(\mathbb{Z}^{d})\times
N(\mathbb{Z}^{d}))$ is an orthogonal basis [23]. ∎

###  5.4 Illustration of zeros of some lattice Zak transforms for multi-tiling
sets

To illustrate the result of Theorem 5.1 and Lemma 4.1, in this section, we
find zeros of lattice Zak transform of window functions sets both analytically
and graphically. In the following examples, Theorem 5.1 guarantees that the
Zak transform $Z\chi_{\Omega}$ is a continuous function and its zero set is
not empty when $\Omega$ is a multi-tiling domain. MATLAB code that generates
the 2D plots is given in Section 7.

######  Example 5.1 (Domains that tile).

Let $\Omega=[0,1]$ and $M=1/k$, $N=k$ for an integer $k>1$. For $M=1,N=1$
(Figure 2(a)), $\Omega$ tiles ${\mathbb{R}}$ by ${\mathbb{Z}}$ and the Zak
Transform of $\chi_{[0,1]}$ is identically equal to one in the interior of
$Q_{M}\times Q_{N}$. For $k=2$ (Figure 2(b)) the Zak transform of
$\chi_{[0,1]}$ for $x\in Q_{M}$ is given by
$\sqrt{2}Z_{M}\chi_{[0,1]}(x,\xi)=\sum_{n\in\mathbb{Z}}f(x+\frac{1}{2}n)e^{\pi
i\xi n}=\left(1+e^{\pi i\xi}\right)$. Direct computation shows that
$Z_{1/2}\chi_{[0,1]}=0$ for $\xi\in 2\mathbb{Z}+1$. Figure 2(c) shows plots of
a tiling domain $\Omega$ and $Z{\chi_{\Omega}}\equiv 1$.

(a) $\Omega$ tiles ${\mathbb{R}}$ by ${\mathbb{Z}}$

$|Z\chi_{\Omega}|$

(b) $\Omega$ 2-tiles ${\mathbb{R}}$ by $2^{-1}{\mathbb{Z}}$

$|Z\chi_{\Omega}|$

(c) $\Omega$ tiles ${\mathbb{R}}^{2}$ by ${\mathbb{Z}}^{2}$

$|Z\chi_{\Omega}|$

Figure 2: Tiling and multi-tiling domains (top) and plots of the magnitude of
the Zak Transform $|Z_{M}{\chi_{\Omega}}(x,\xi)|$ (bottom), for (a) $M=1$, (b)
$M=1/2$, and (c) $M=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$. The illustrations
on bottom are made for fixed $x$.

(a) Parallelogram $P$ ($k=2$)

$|Z\chi_{P}|$

(b) L-shape $L$ ($k=3$)

$|Z\chi_{L}|$

(c) Octagon $O$ ($k=14$)

$|Z\chi_{O}|$

Figure 3:  Top: Multi-tilings of ${\mathbb{R}}^{2}$ at level $k$ by
$\Lambda={\mathbb{Z}}^{2}$ that are not 1-tilings . Bottom: the magnitude of
the Zak transform of the characteristic function for these domains. Here $x$
is fixed in ${\mathbb{R}}^{2}.$

######  Example 5.2 (Multi-tiling domains that do not tile).

Consider the parallelogram $P$ shown in Figure 3(a) with bottom left vertex
located at the origin. Then, for $x$ in the triangle $T$ with vertices
$(0,0),(1,0),(1,1)$, the Zak transform of the characteristic function is given
by $Z\chi_{P}(x,\xi)=1+e^{-2\pi i\xi_{1}}$ has zeros in
$\xi_{1}=2^{-1}{\mathbb{Z}}$. For the set $L$ shown in plot in Figure 3(b), is
seen that for $x\in[0,1]^{2}$ the Zak transform $Z\chi_{L}(x,\xi)$ is zero for
$\xi=(\xi_{1},\xi_{2})$ with $\xi_{1}-\xi_{2}\in\mathbb{Z}+1/3$. For the
octagon $O$ shown Figure 3(c) it can be shown through direct computation that
the Zak transform $Z\chi_{O}$ is zero at any $(\xi_{1},\xi_{2})$ for
$\xi_{1}=n+1/2$, and points $(1/6,1/2)$, $(5/6,1/2)$.

In the last two examples, we compute the magnitude of the Zak transform $Zg$
for functions $g\in L^{2}({\mathbb{R}})$ that are not characteristic functions
of tiling domains.

######  Example 5.3 (Intervals with an irrational gap).

Let $\Omega=(0,1/2)\cup(a,a+1/2)$ where $a>1/2$ is an irrational number. By
Laba’s result [22], $\Omega$ is not a tiling set and $L^{2}(\Omega)$ does not
admit an exponential orthogonal basis. Assume that $n_{0}\in\mathbb{Z}$ such
that $n_{0}<a<n_{0}+1/2$. (One can also assume that $n_{0}+1/2<a<n_{0}$ for
some other $n_{0}$, as the argument will be similar.) Consider the Zak
transform $Z:L^{2}(\mathbb{R})\to L^{2}([0,1]^{2})$
$Z\chi_{\Omega}(x,\xi)=\sum_{n\in\mathbb{Z}}\chi_{\Omega}(x-n)e^{2\pi
i\xi\cdot n}.$ Let $\Delta=(a-n_{0}+1/2,1)$. It is readily seen that
$Z\chi_{\Omega}(x,\xi)=0$ for any $(x,\xi)\in\Delta\times[0,1]$. The zeros of
$|Z\chi_{\Omega}|$ for $a=\sqrt{2}$ are plotted in Figure 4(a).

111plot characteristic function for (a) that is like (b) (a) Intervals with
irrational gap
$\Omega={[0,1/2]+\\{0,\sqrt{2}\\}}$

$|Z\chi_{\Omega}|$

(b) Gaussian window function $f(x)=e^{-\pi x^{2}}$

$|Zf|$

Figure 4: (a) (top) $\Omega={[0,\frac{1}{2}]+\\{0,2\\}}$ is the union of two
fundamental domains of $\frac{1}{2}{\mathbb{Z}}$ that does not form a tiling
of ${\mathbb{R}}$ with respect to any countable set, and (bottom) the Zak
transform of $f(x)=\chi_{\Omega}$, and (b) (top) a Gaussian function
$f(x)=e^{-\pi x^{2}}$ and (bottom) its Zak transform.

##  6 Open problems

######  Problem 6.1.

Our characterization in Theorem 1.2 shows that the statement that
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ forms a Riesz Gabor basis for
any time-frequency shift domain $\Lambda\times\Gamma$ is equivalent to the
statement that $\mathcal{E}(\Gamma)$ forms a Riesz basis for $L^{2}(\Omega)$,
provided that $\Omega$ tiles $\mathbb{R}^{d}$ by $\Lambda$. This result holds
under a prior assumption on the structure of $\Omega$. We also observed in
Theorem 1.3 that for certain lattices, if $\Omega$ multi-tiles
${\mathbb{R}}^{d}$ by $\Lambda$, for
$\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ to form a Gabor Riesz basis,
it is necessary that $\Omega$ tiles $\mathbb{R}^{d}$ by $\Lambda$. Can we
improve these results and find a necessary tiling condition for any separable
Riesz time-frequency domain $\Lambda\times\Gamma$ without any prior geometric
assumptions on the set $\Omega$?

The study of the following problem has been motivated by our observation in
Example 1.1.

######  Problem 6.2.

Let $\Omega$ be a multi-tiling set with respect to a lattice $\Lambda$ at
level $k>1$. Is it possible to find a countable set $\Gamma$ (not necessarily
a lattice) such that $\mathcal{G}(\chi_{\Omega},\Lambda\times\Gamma)$ is a
Riesz Basis for $L^{2}(\mathbb{R}^{d})$?

######  Problem 6.3.

There are domains $\Omega$ for which $\chi_{\Omega}$ can never serve as a
window function (or generator) for any Gabor orthogonal basis. For example, it
is known that if $\Omega$ is a convex body with a smooth boundary with
Gaussian curvature that does not vanish anywhere, then $\chi_{\Omega}$ does
not serve as the window function for any orthogonal Gabor basis, provided that
$d\neq 1\mod 4$ [16]. A challenging problem is, Can the characteristic
function of a ball can serve as a window function for a Gabor Riesz basis when
$d\neq 1\mod 4$?

##  7 Appendix

Listing 1: MATLAB code for an approximation of $Zf(x,\xi)$ using a truncated
sum.

⬇

function Z_f = ZakTransform(f,x,xi, N_1, N_2)

% ZakTransform returns an approximation of the Zak

% transform using a truncated sum

% Inputs

% f: function handle that takes 2x1 vector input

% x and xi : 2x1 vectors

% N_1, N_2 are integer bounds on the summation index

% Output:

% Z_f = \sum_{n\in [N_1 N_2]^2} f(x+n)e^{2*pi*i*xi*\cdot n}

[n1, n2] = meshgrid(N_1:N_2);

n1 = n1(:)’; n2=n2(:)’;

f_n = f([x+ [n1; n2]]’).*exp(2*pi*1i*xi’*[n1; n2])’;

Z_f = sum(f_n);

end

Listing 2: MATLAB code for plotting $|Zf(x,\xi)|$ when $f=\chi_{\Omega}$.

⬇

%Plots the magnitude of the Zak Transform corresponding to the characteristic
function of a specified shape

% Define and plot the domain Omega

Omega = polyshape(-1.5+[-.5 .5 2.5 3.5 3.5 2.5 .5 -.5 ], .5+[.5 1.5 1.5 .5
-1.5 -2.5 -2.5 -1.5]);

plot(Omega)

hold all;

axis equal;

[x,y] = meshgrid([-2:1:2]);

plot(x,y,’ko’,’MarkerFaceColor’,’k’);

set(gca, ’Xtick’,[-2:2], ’Ytick’,[-2:2]);

% let f be the indicator function of Omega

f = @(x) isinterior(Omega,x);

% Query for the zak transform at x=[1/4; 2]

NN = 200;

[X, Y] = meshgrid(linspace(-1,2,NN));

Xi = [X(:)’; Y(:)’];

x = [1/4; 2];

for j = 1:size(x,2)

for k=1:length(Xi)

Z(j,k) = ZakTransform(f, x, Xi(:,k), -5,5);

end

end

%% Plot |Zf|

figure;

Z = reshape(Z, [NN NN]);

surf(X, Y, abs(Z),’linestyle’, ’none’); view(0,-90); colorbar;

xlabel(’$\xi_1$’, ’interpreter’, ’latex’)

ylabel(’$\xi_2$’, ’interpreter’, ’latex’)

axis tight

## References

  * [1] Davide Barbieri, Eugenio Hernández, and Azita Mayeli.  Bracket map for the Heisenberg group and the characterization of cyclic subspaces.  Applied and Computational Harmonic Analysis, 37(2):218–234, 2014\.
  * [2] Ole Christensen.  A Paley-Wiener theorem for frames.  Proceedings of the American Mathematical Society, 123(7):2199–2201, 1995.
  * [3] Thomas Fallon, Gergely Kiss, and Gábor Somlai.  Spectral sets and tiles in $\mathbb{Z}_{p}^{2}\times\mathbb{Z}_{q}^{2}$.  arXiv preprint arXiv:2105.10575, 2021.
  * [4] Jacob Feldman and Frederick Greenleaf.  Existence of Borel transversals in groups.  Pacific Journal of Mathematics, 25(3):455–461, 1968.
  * [5] Christina Frederick and Azita Mayeli.  Frame spectral pairs and exponential bases.  Journal of Fourier Analysis and Applications, 27(5):1–21, 2021\.
  * [6] Christina Frederick and Kasso A Okoudjou.  Finding duality for Riesz bases of exponentials on multi-tiles.  Applied and Computational Harmonic Analysis, 51:104–117, 2021.
  * [7] Bent Fuglede.  Commuting self-adjoint partial differential operators and a group theoretic problem.  Journal of Functional Analysis, 16(1):101–121, 1974.
  * [8] Jean-Pierre Gabardo, Chun-Kit Lai, and Yang Wang.  Gabor orthonormal bases generated by the unit cubes.  Journal of Functional Analysis, 269(5):1515–1538, 2015.
  * [9] Dennis Gabor.  Theory of communication. part 1: The analysis of information.  Journal of the Institution of Electrical Engineers-Part III: Radio and Communication Engineering, 93(26):429–441, 1946.
  * [10] Sigrid Grepstad and Nir Lev.  Multi-tiling and Riesz bases.  Advances in Mathematics, 252:1–6, 2014.
  * [11] Karlheinz Gröchenig.  Foundations of time-frequency analysis.  Springer Science & Business Media, 2001.
  * [12] Deguang Han and Yang Wang.  Lattice tiling and the Weyl—Heisenberg frames.  Geometric & Functional Analysis GAFA, 11(4):742–758, 2001.
  * [13] Christopher E Heil and David F Walnut.  Continuous and discrete wavelet transforms.  SIAM review, 31(4):628–666, 1989.
  * [14] Eugenio Hernández, Hrvoje Šikic, Guido Weiss, and Edward Wilson.  Cyclic subspaces for unitary representations of lca groups; generalized Zak transform.  In Colloq. Math, volume 118, pages 313–332, 2010.
  * [15] Alex Iosevich and Azita Mayeli.  Gabor orthogonal bases and convexity.  arXiv preprint arXiv:1708.06397, 2017.
  * [16] Alex Iosevich and Azita Mayeli.  Gabor orthogonal bases and convexity.  Discrete Analysis, page 5952, 2018.
  * [17] Alexander Iosevich, Azita Mayeli, and Jonathan Pakianathan.  The Fuglede conjecture holds in $\mathbb{Z}_{p}\times\mathbb{Z}_{p}$.  Analysis & PDE, 10(4):757–764, 2017.
  * [18] Augustus JEM Janssen.  The Zak transform: a signal transform for sampled time-continuous signals.  Philips Journal of Research, 43(1):23–69, 1988.
  * [19] Augustus Josephus Elizabeth Maria Janssen.  Bargmann transform, Zak transform, and coherent states.  Journal of Mathematical Physics, 23(5):720–731, 1982.
  * [20] Mihail N. Kolountzakis.  Multiple lattice tiles and Riesz bases of exponentials.  Proceedings of the American Mathematical Society, 143(2):741–747, 2013.
  * [21] Gady Kozma, Shahaf Nitzan, and Alexander Olevskii.  A set with no Riesz basis of exponentials.  arXiv preprint arXiv:2110.02090, 2021.
  * [22] Izabella Łaba.  Fuglede’s conjecture for a union of two intervals.  Proceedings of the American Mathematical Society, 129(10):2965–2972, 2001.
  * [23] Chun-Kit Lai and Azita Mayeli.  Non-separable lattices, Gabor orthonormal bases and tilings.  Journal of Fourier Analysis and Applications, 25(6):3075–3103, 2019\.
  * [24] Tibor Radó and Paul V Reichelderfer.  Continuous transformations in analysis: with an introduction to algebraic topology, volume 75.  Springer Science & Business Media, 2012.
  * [25] Jayakumar Ramanathan and Tim Steger.  Incompleteness of sparse coherent states.  Applied and Computational Harmonic Analysis, 2(2):148–153, 1995\.
  * [26] Robert M. Young.  An introduction to nonharmonic Fourier series, revised first edition.  Academic Press, Inc., San Diego, CA, 2001.