22footnotetext: Pontificia Universidad Católica de Chile, Facultad de
Matematicas, Avda. Vicuña Mackenna 4860, Santiago, 6904441, Chile

# Effective recovery of Fourier spectra and spectral approximation by finite
groups

Mircea Petrache111PUC<EMAIL_ADDRESS>ORCID id: 0000-0003-2181-169X and
Rodolfo Viera222PUC<EMAIL_ADDRESS>ORCID id: 0000-0002-0810-6374

(date)

###### Abstract

We prove a result on approximate recovery, with high probability, of subgroups
of a finite nonabelian group $\Gamma$ from their random perturbations. We use
this for ad-hoc sequences of $\Gamma_{n}$ while passing to the continuum
limit, in order to obtain asymptotic almost sure recovery for rational lcsc
nilpotent Lie groups. By comparison to limit theorems for groups of polynomial
growth, it turns out that this setting is the natural general setting for
recovery results, under polynomial growth assumptions on the $\Gamma_{n}$.
This approach makes effective the convergence rate in previous Fourier
recovery theorems in Euclidean space, and extends them to the nonabelian
setting. A series of interesting further directions are highlighted by this
approach.

##  1 Introduction

Motivated by problems in signal denoising [14], hyperuniform point
configurations [13] and diffraction theory [11, 2], to mention a few, in the
last years there has been a lot of activity in random perturbations on
discrete structures. Roughly speaking, the general framework is that, starting
with a discrete set, one is concerned with how a structure of interest defined
on it is affected by random perturbations of the set; for instance, in [13]
the authors relate by a very precise formula the structure factors of a
(randomized) lattice and a perturbed version of it. Very recently, [21, 17]
addressed the problem of studying the effect of random perturbations on the
Fourier transform of a discrete set $X$ in the Euclidean space, proving
robustness-type results for the Fourier transform in lattices [21] and more
general quasi-periodic subsets of Euclidean spaces, such as quasicrystals
[17]. The above works leave open the following natural research questions,
which we tackle here:

  * •

In defining Fourier transform on countable uniformly discrete subsets of
Euclidean space, one makes an implicit idealization, since in (numerical and
physics) applications we never directly work with infinite sets, but are bound
to do only _approximations_ to Fourier transforms on infinite spaces. It is
thus natural to develop effective approximation error bounds for recovery
results of structures such as the Fourier spectrum.

  * •

While lattices and quasicrystals in Euclidean spaces are structures relevant
to crystallographic applications, it is natural to ask general structure
recovery results of the same kind, in general geometries, as done in [14] in a
different framework. In particular, it is natural to generalize such questions
to the framework of nonabelian groups of polynomial growth.

In this work, we tackle both questions for the first time, and at the same
time, we set a basis for applying geometric group theory tools to recovery
questions. In this way, through robustness-type results, we intend to
contribute to understanding how probabilistic aspects in a group are
determined by its geometry; we refer the reader to [16] for an introduction to
these topics. While there is a large and deep theory for the possible limits
of discrete groups of polynomial growth [4, 15], the question of how to
perform approximations that allows to ensure also convergence of further
structures (such as Fourier transforms) is to our knowledge not developed. We
hope that this work will motivate further advances towards a Fourier theory of
approximate groups, by providing a concrete use case for such theory in the
setting of recovery problems.

### Setting and overview

We first define the property that a ”fingerprint” map $\mathcal{F}$ applied to
a random perturbation of a subgroup $H$ of a group $G$, has a deterministic
effect. Consider the following situation:

  * •

Let $(G,\cdot)$ be a topological group and $H\subset G$ be a subgroup.

  * •

We let $\mathcal{D}$ be a fixed set of probability measures over $G$.

  * •

We consider a fixed injective linear $*$-homomorphism
$\mathcal{F}:\mathcal{M}_{b}(G)\to\mathcal{B}$ where $\mathcal{B}$ is a
$C^{*}$-algebra and $\mathcal{M}_{b}(G)$ is the space of $G$-shift-bounded
measures on $G$, which are defined as Borel measures $\mu$ on $G$ such that
for every compact $K\subset G$ there holds $\sup_{g\in G}|\mu|(g\cdot
K)<\infty$, $|\mu|$ being the total mass of $\mu$.

For fixed $\mu\in\mathcal{D}$ we perturb $H\subset G$ as follows. Consider a
family of i.i.d $G$-valued random variables $\xi=(\xi_{h})_{h\in H}$, defined
over a probability space $(\Omega,\mathcal{T},\mathbb{P})$, with fixed common
law $\mathbb{P}_{\xi}=\mu$, and consider the realization set

$\begin{split}H_{\mu}(\omega)&:=\\{h\cdot\xi_{h}(\omega):h\in H\\}\subset
G\qquad\omega\in\Omega.\end{split}$ (1.1)

We then use the abbreviated notation

$\delta_{H_{\xi}(\omega)}:=\sum_{h\in H_{\xi}(\omega)}\delta_{h},$

where $\delta_{h}$ is the Dirac delta at $h\in H_{\xi}(\omega)$. Below we give
the definitions of interest in this paper, within an abstract setting, which
will be sepecialized in 1.2.

######  Definition 1.1.

With notations and definitions as above, we introduce the following notions:

  1. (A)

For real numbers $\mathsf{err}\geq 0$ and $\delta\in[0,1)$ we say that _the
$\mathcal{F}$-action on $H\subset G$ is $(\mathsf{err},\delta)-$probably
approximately determined (PAD) for $\mathcal{D}-$perturbations_ if there
exists a (deterministic) function

$\Phi_{H}:\mathcal{D}\to\mathcal{B}$ (1.2)

such that, for all $\mu\in\mathcal{D}$ for $H_{\mu}(\omega)$ as in (1.1),

$\mathbb{P}\left\\{\left\|\mathcal{F}(\delta_{H_{\mu}})-\Phi_{H}(\mu)\right\|_{\mathcal{B}}>\mathsf{err}\right\\}\leq\delta.$
(1.3)

  2. (B)

We say that the $\mathcal{F}$-action on $H\subset G$ is almost-surely
determined (ASD) for $\mathcal{D}-$perturbations if there exists a
(deterministic) function $\Phi$ as in (1.2) such that for all
$\mu\in\mathcal{D}$ for $H_{\mu}(\omega)$ as in (1.1) we have

$\mathcal{F}(\delta_{H_{\mu}(\omega)})=\Phi_{H}(\mu),\quad\text{for
$\mathbb{P}$-almost every $\omega$.}$ (1.4)

In particular, the notion of $(0,0)-$PAD coincides with the one of ASD.

Motivation for our hypotheses on $\mathcal{F}$. While working with noise-
robustness of fingerprints $\mathcal{F}$ in high generality may be
interesting, some extra structure on $\mathcal{F}$ is crucial for being able
to prove explicit recovery results. This is also true in different settings
for signal recovery problems such as [14]. For our work, a good reason to work
with the $*$-morphism hypothesis on $\mathcal{F}$ is that it actually allows
to find explicit formulas on $\Phi_{H}$ and to prove at the same time
determination to recovery properties (see 1.2 below). Rather than working with
general $*$-morphisms, we chose to restrict to the case of Fourier transforms
in this work as a first step, and it is an interesting direction of future
research to extend the results to more general $\mathcal{F}$.

Explicit formulas for $\Phi_{H}$. In case $G,H$ are finite groups, it seems to
be more often the case that only $(\mathsf{err},\delta)-$PAD properties hold.
But it is instructive to keep in mind that if almost-sure deterministic action
(1.4) holds for this case, then the underlying deterministic $\Phi_{H}$ can be
made more explicit. Indeed, by taking the expected value in (1.4) we get the
following:

$\Phi_{H}(\mu)=\mathbb{E}\left[\mathcal{F}(\delta_{H_{\mu}})\right]=\mathcal{F}\left(\mathbb{E}[\delta_{H_{\mu}}]\right)=\mathcal{F}(\delta_{H}*\mu)=\mathcal{F}(\delta_{H})\mathcal{F}(\mu).$
(1.5)

Above, we interpret $\delta_{H_{\mu}}$ as a random measure, we used linearity
of expectation and of $\mathcal{F}$, and the fact that $\mathcal{F}$ is a
$*$-morphism from finite measures on $G$ with convolution product to
$\mathcal{B}$.

For the case of infinite $G$ and $H$, we can prove almost-sure recoverability
via ergodicity of $H$-action in combination with a law of large numbers.
However in general the manipulations as in the finite case are not warranted,
and due to this, we focus on specific $\mathcal{F}$ defined as the Fourier
transform on translation-bounded measures. To define $\mathcal{F}$ we fix a
distance compatible with the metric on $G$ and let $B_{R}$ be the ball of
radius $R$ centered at the identity. Then, for fixed $X\subset G$, we define

$\mathcal{F}(\delta_{X})(\pi):=\lim_{R\to\infty}\frac{1}{f_{X}(R)}\sum_{x\in
X\cap B_{R}}\pi(x),$ (1.6)

where $f_{X}(R)\sim|X\cap B_{R}|$ denotes the asymptotic ball growth in $X$.
If $H\subset G$ is a discrete infinite group or a lattice in a nilpotent $G$,
then $f_{H}(R)=C_{H}R^{k}$, in which $k$ is the dimension of $H$. Then we
consider the case of tame $\mu$, which have the moment condition
$\mathbb{E}_{\mu}[|\xi|^{k+\epsilon}]<\infty$ for some positive $\epsilon$.
Then for $\mathbb{P}$-almost all $\omega\in\Omega$ we may take
$f_{H_{\mu}(\omega)}=f_{H}$.

In the above case, we can build an explicit description of the function $\Phi$
in 1.1 (B). Indeed, assuming (1.4) holds, we get, for fixed
$\mu\in\mathcal{D}$ and $\pi\in\widehat{G}$:

$\displaystyle\Phi_{H}(\mu)(\pi)$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathcal{F}(\delta_{H_{\mu}})(\pi)\right]=\mathbb{E}\left[\lim_{R\to\infty}\frac{1}{C_{H}R^{k}}\sum_{x\in
H_{\mu}(\omega)\cap B_{R}}\pi(x)\right]$ (1.7) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\lim_{R\to\infty}\frac{1}{C_{H}R^{k}}\sum_{h\in
H\cap
B_{R}}\pi(h\cdot\xi_{h})\right]=\lim_{R\to\infty}\frac{1}{C_{H}R^{k}}\sum_{h\in
H\cap B_{R}}\pi(h)\mathbb{E}\left[\pi(\xi_{h})\right]$ $\displaystyle=$
$\displaystyle\mathcal{F}(\delta_{H})(\pi)\int_{G}\pi(x)d\mu(x),$

with the integral taken in the sense of Bochner. The first equality in the
above second line is based again on the moment hypothesis on $\mu$, and will
be justified in Lemma 4.6. Then we used the fact that unitary representations
$\pi$ are group homomorphisms, and the fact that the $\xi_{h}$ are i.i.d. with
law $\mu$.

Main Results. We now specialize to the setting of our main results. In the
above paragraphs we have seen that $\Phi_{H}$ has an explicit expression, with
which the property in 1.1 amounts to an – approximate in case (A) and almost
sure in case (B) – factorization property of the noise. If the factors
multiplying $\mathcal{F}(\delta_{H})$ on the right in (1.5) or (1.7) are
invertible, then we can actually recover (approximately or almost-surely)
$\mathcal{F}(\delta_{H})$ from a single noisy measurement. Further, if we
restrict to $\mathcal{F}$ as the above Fourier transforms, then we have
natural choices of $\mathcal{B}$ as mentioned in the below definition.

######  Definition 1.2.

  1. (A)

If $H<G$ are finite groups and $\mathcal{F}:L^{2}(G)\to L^{2}(\widehat{G})$ is
the normalized Fourier transform, we say that $\mathcal{F}$ can be
$(\mathsf{err},\delta)-$approximately recovered on $H$ from
$\mathcal{D}-$perturbations if case (A) of 1.1 with holds with $\Phi_{H}$ as
in (1.5).

  2. (B)

If $G$ is an abelian or nilpotent, locally compact, simply connected Lie
group, $H<G$ is a $k$-dimensional discrete infinite subgroup, and
$\mathcal{F}:\mathcal{M}_{p}(G)\to L^{\infty}(\widehat{G})$ is defined as in
(1.6), we say that $\mathcal{F}$ can be almost-surely recovered on $H$ from
$\mathcal{D}-$perturbations if case (B) of 1.1 holds with $\Phi_{H}$ as in
(1.7).

Then our main results are summarized in the next two theorems.

######  Theorem A.

Let $G$ be a finite group and $H\subset G$ be a normal subgroup with $|H|\geq
24$. Let $\mathcal{F}$ be the (normalized) Discrete Fourier Transform of $G$.
Let $\mathcal{D}$ be the class of probability measures $\mu$ on $G$ for which
$C=C(\mu,G):=\sup_{\pi\in\widehat{G}}\mathsf{Var}_{\xi\sim\mu}[\pi(\xi)]<\infty$,
where $\widehat{G}$ is the space of all unitary irreducible representations of
$G$. Then for fixed $\delta\in(0,1)$, we have that the laws from $\mathcal{D}$
are $(\mathsf{err},\delta)$-probably approximately recoverable through
$\mathcal{F}$ from perturbations with law in $\mathcal{D}$, where

$\mathsf{err}=4C\frac{|H|^{7/2}}{|G|^{2}}\left(\sqrt{\frac{3}{\delta}}+\frac{C}{|H|^{1/2}}\right)\max_{\pi\in\widehat{G}}d_{\pi}.$
(1.8)

Note that $C=C(\mu,G)$ represents the main dependence of our estimates on the
geometry of $G$.

Possible application cases of Theorem A. In numerical applications, such as
for numerical simulations of materials, or for signal processing via finite
codes, amongst others, one most commonly one has to control error bounds for
finite discretizations, with special focus on asymptotics and scalability of
such bounds. For the question of robustness to random perturbations, A
provides such control, and allows to find what relationships between the
cardinalities of $H$ and $G$ allow small error in asymptotics of interest.
Thus this result is of independent interest, and in this paper we use this
theorem for our B below.

Our second main result is concerned with extending the known recovery results
for lattices in Euclidean spaces to more general groups. We consider the
natural case of infinite discrete subgroups of nilpotent Lie groups:

######  Theorem B.

Let $G$ be a $d$-dimensional lcsc nilpotent Lie group, and assume that $H<G$
is a $k$-dimensional lattice with averaged Fourier transform denoted
$\mathcal{F}_{k}$. For fixed $\varepsilon>0$, let $\mathcal{D}$ be the set of
probability measures on $G$ with finite $k+\varepsilon$ moment. Then $H$ is
almost-surely recoverable through $\mathcal{F}_{k}$ from perturbations with
law in $\mathcal{D}$.

We obtain B from the result of A, via a suitable discrete to-continuum
approximation process. Precisely, let $H<G$ be as in B. In Section 5.2,
Section 5.3 and Section 4 below, we prove that there is a sequence of finite
groups $H_{n}\subset G_{n}$ which converge to $H$ and $G$ respectively, in
Gromov-Hausdorff topology, and such that the Fourier transforms
$\mathcal{F}(\delta_{X})$ and $\mathcal{F}(\delta_{X_{\xi}})$ can be
approximated by $\mathcal{F}_{\Gamma_{n}}(\delta_{H_{n}})$ and
$\mathcal{F}_{\Gamma}(\delta_{(H_{n})_{\xi}})$, respectively; for more details
see Lemma 5.5, Lemma 5.8, Lemma 5.9 and Lemma 4.5 below. Thus, from a
computational viewpoint, A not only gives us, in the limit, a noise-recovery
such as B but also allows us to obtain approximations of the recovery of
$\mathcal{F}(\delta_{X})$ by $\mathcal{F}_{\Gamma_{n}}(\delta_{H_{n}})$ with a
control for the error bounds due to its explicit (and computable) form (1.8).

Motivation for the hypothesis that $G$ is nilpotent in Theorem B. Theorem B
describes recovery of discrete subgroups in a class of Lie groups $G$, which
is a second important model case besides the result of A for finite $G$. The
motivation for the hypotheses of Theorem B is based on the following
restriction of our proofs:

  1. 1.

For the good definition of $\mathcal{F}$ as in (1.6), we require $X\subset G$
to have polynomial growth.

  2. 2.

Our almost-sure recovery proof is based on a version of the central limit
theorem to $\xi_{p}$ for $p\in H$, which ensures (1.4) almost surely. For
this, we require $H$ to be infinite.

  3. 3.

In order use an averaging property of groups $H$, and to formulate the bound
on $k+\epsilon$ moments for the law of $\xi$, we require that $H$ have
polynomial growth $|B_{H}(x,R)|=O(R^{k})$.

  4. 4.

In order to apply the general result of A, we approximate $G$ via finite
groups $G_{n}$ as $n\to\infty$. We also require that there exist subgroups
$H_{n}<G_{n}$ converging to $H$.

Due to points 2. and 4. we require that $|G_{n}|,|H_{n}|\to\infty$ and due to
1. and 3. we require that $G$ is of polynomial growth. These conditions on the
$G_{n}$, and the fact that $G$ is not discrete, already imply that $G$ should
be a finite-dimensional nilpotent Lie group, due to the following known
result:

######  Theorem 1.1 (Corollary of Thm. 3.2.2 from [4]).

Suppose that $0<r_{n}\leq R_{n}$ are two unbounded sequences and consider a
sequence $(G_{n},d)$ of discrete metric groups with ball growth
$|B_{G_{n}}(x,R_{n})|=O(R_{n}^{q})$. Then $(G_{n},d/r_{n})$ have a subsequence
converging for the pointed Gromov-Hausdorff topology to a connected nilpotent
Lie group equipped with the left-invariant Carnot-Caratheodory metric.

Possible application cases of Theorem B. The special case of
$G=\mathbb{R}^{d}$ and $H$ a lattice describes the stability of spectral
properties of a crystal under perturbations (in case $d\leq 3$ especially),
and other directions for application may come from the case that $H$ is
interpreted as a _code_ , or as the discretization of a signal with values in
$G$. This setup for $G=\mathbb{R}^{d}$ with large $d$ is the traditional setup
for lattice-based cryptography, which covers an important percentage of
successful quantum-resistant cryptography algorithms [1]. We point out here
that the same applications also may be extended to the more general case that
$G$ is a nilpotent group. To see why this may be interesting to develop, it is
worth mentioning that Heisenberg groups (in the simplest case) and in fact all
nilpotent Lie groups represent the state space of quantum systems in the
presence of external magnetic fields (see e.g. [20] for an introduction, and
formalism for an interpretation for the Engel group in [3], as well as [5] for
a broader description). For these general $G$, similarly to $G=\mathbb{R}^{d}$
the role of $H$ is that of a possible discretization of signals encoded as
quantum states of a system, and B gives a possible way to recover corrupted
signals of this type.

Some natural open directions. Note that a direct extension of B, would be to
include the case that $G$ is itself a lattice in a nilpotent Lie group
$G^{\prime}$, and $H$ is a sublattice. In this case we can work with B
directly in $G^{\prime}$ itself. A second extension, which seems
straightforward but for which we did not find good enough motivations to
include it in this work, would be to consider the product of $H,G$ with finite
groups $H^{\prime}<G^{\prime}$.

We now indicate some natural extensions of the result of B, which seem
interesting to pursue in future work, but would require fundamental changes in
our proof strategy.

  * •

Quasicrystals $H$ in a nilpotent Lie group.

  * •

Sublattices of infinite lattices in a nilpotent Lie group.

  * •

Infinite groups in amenable groups of intermediate or exponential growth.

Some short words on notation.  Now we include some basic definitions and
notations which we will use throughout this work. We use the notation
$|\cdot|$ indistinguishably for the Euclidean norm in $\mathbb{R}^{d}$, for
the module of a complex number, for the Lebesgue measure, and the cardinality
of a finite set; this will be clear in each context. As usual we denote by
$B(x,R):=\\{y\in\mathbb{R}^{d}:|x-y|<R\\}$ the euclidean open ball centered at
$x\in\mathbb{R}^{d}$ with radius $r>0$ and we use the notation
$B_{R}:=B(0,R)$.

For a Banach space $\mathcal{B}$, we write $\|\cdot\|_{\mathcal{B}}$ for a
norm in $\mathcal{B}$. If $\mathcal{H}$ is a Hilbert space, we write
$\langle\cdot,\cdot\rangle_{\mathcal{H}}$ for the inner product in
$\mathcal{H}$. Given a measure space $\mathcal{M}$, we use the notation
$L^{p}(\mathcal{M})$ for the Banach space of $p$-integrable functions; in the
case when $\mathcal{M}$ is finite, to emphasize its discrete nature we write
$\ell^{p}(\mathcal{M})$.

We usually denote a diffeomorphism between manifolds or an isomorphism between
Hilbert spaces by $\cong$. This also will be clear in each situation where we
use $\cong$ as an equivalence. Finally, the expression $C_{1}(M)\ll C_{2}(N)$
and $\varepsilon\lesssim 1$ will mean that $C_{2}(N)/C_{1}(M)\to\infty$ from
sufficiently large values of $M,N$, and that $\varepsilon<C$ for some suitable
constant $C$, respectively.

Organization of the paper. In Section 2, we consider the problem of
quantitative recovery in the most general setting. In Section 2.1 we review
basic material on representations of finite groups and then, in Section 2.2,
we give some basics about the Fourier transform in finite groups, which will
be necessary to state our recovery results. The core of this section is
Section 2.3, where we prove A (see 2.8).

In Section 3 and Section 4, we are dedicated to proving B. We provide some
necessary facts about nilpotent Lie groups, induced representations, and
Kirillov’s orbit method as machinery to obtain irreducible representations in
these Lie groups. Then we state and prove the main result in this section,
namely, 4.1.

Finally in Section 5 we provide examples of the above in the most canonical
abelian and non-abelian instances, namely, the Euclidean space and the
Heisenberg group, where some explicit computations are done.

##  2 Approximate recovery in finite groups

###  2.1 Background on Representations of Finite Groups

This section establishes some basic terminology and the necessary machinery of
Fourier Analysis in Finite (non-Abelian) Groups. Given a finite-dimensional
vector space $V$ over $\mathbb{C}$, define by $GL(V)$ be the vector space of
all the linear invertible linear transformations $T:V\to V$; this space is
naturally identified with the space of invertible matrices $GL(n,\mathbb{C})$,
where $n=\mathsf{dim}(V)$. Throughout this section, $\Gamma$ will denote a
finite group. A homomorphism $\pi:\Gamma\to GL(V)$ is called a (finite
dimensional) representation of $\Gamma$. Thus, for every $g\in\Gamma$,
$\pi(g)$ is a matrix whose complex entries are denoted by $\pi_{ij}(g)$. The
dimension of $V$ is denoted by $d_{\pi}$ and is called the degree (or
dimension) of the representation $\pi$. If $\pi$ takes values into the set of
unitary operators $\mathcal{U}(V)\cong\mathcal{U}(n,\mathbb{C}):=\\{A\in
GL(n,\mathbb{C}):\ AA^{*}=I\\}$, then $\pi$ is called a unitary representation
of $\Gamma$; in particular the Hermitian inner product $\langle
u,v\rangle:=uv^{t},\ u,v\in\mathbb{C}^{n}$ is preserved under unitary
transformations.

The building blocks of Fourier Analysis in (nonabelian) groups are the
irreducible representations. Given a representation $\pi:\Gamma\to GL(V)$ and
a subspace $W\leq V$ which is $\pi$-invariant, i.e, $\pi(g)W\subset W$ for
every $g\in\Gamma$, the map $\pi^{\prime}:\Gamma\to GL(W)$ given by
$\pi^{\prime}(g):=\pi(g)|_{W}$ is called a subrepresentation of $\pi$. A
representation $\pi$ is called irreducible if its only subrepresentations are
the trivial one and $\pi$ itself.

We say that two representations $\pi_{1}:\Gamma\to GL(V_{\pi_{1}})$ and
$\pi_{2}:\Gamma\to GL(V_{\pi_{2}})$ are equivalent if there is a isomorphism
$T:V_{\pi_{1}}\to V_{\pi_{2}}$ such that $T\pi_{1}(g)=\pi_{2}(g)T$ for every
$g\in\Gamma$; we denote this equivalence relation by $\pi_{1}\cong\pi_{2}$.
The following Proposition says that every unitary representation can be
decomposed into irreducible components (see Proposition [19, Chapter 15]).

######  Proposition 2.1.

  1. 1.

Every representation is equivalent to a unitary representation.

  2. 2.

Every unitary representation $\pi:\Gamma\to\mathcal{U}(V_{\pi})$ is equivalent
to

$\pi_{1}\oplus\pi_{2}\oplus\ldots\oplus\pi_{r}:=\begin{pmatrix}\pi_{1}&&0\\\
&\ddots&\\\ 0&&\pi_{r}\end{pmatrix}$

where each block $\pi_{j}$ is an irreducible subrepresentation of $\pi$.

Given two representations $\pi:\Gamma\to GL(V_{\pi})$ and $\rho:\Gamma\to
GL(V_{\rho})$, consider the space $I(\pi,\rho)$ of intertwining operators
defined by

$I(\pi,\rho):=\\{T:V_{\pi}\to V_{\rho}:\text{T is linear and
}T\circ\pi(g)=\rho(g)\circ T,\text{ for every }g\in\Gamma\\};$

In particular, $I(\pi):=I(\pi,\pi)$ is the set of linear operators
$T:V_{\pi}\to V_{\pi}$ which commute (under composition) with $\pi(g)$ for
every $g\in\Gamma$. The condition that two representations $\pi,\rho$ are
equivalent can now be reformulated by requiring that $I(\pi,\rho)$ contains an
isomorphism.

The following Lemma is one of the cornerstones in Fourier Analysis in non-
abelian groups; we refer to [19, Chapter 15] for further details.

######  Lemma 2.2 (Schur’s Lemma).

  1. 1.

A unitary representation $\pi$ of $\Gamma$ is irreducible if and only if
$I(\pi)$ contains only scalars multiples of the identity.

  2. 2.

If $\pi$ and $\rho$ are unitary irreducible representations of $\Gamma$, then

$\mathsf{dim}(I(\pi,\rho))=\left\\{\begin{array}[]{lc}1&\text{if }\pi\text{
and }\rho\text{ are equivalent,}\\\ \\\ 0&\text{otherwise.}\end{array}\right.$

By identifying representations under equivalence, we define the dual space
$\widehat{\Gamma}$ of $\Gamma$ as the set of equivalence classes of
irreducible unitary representations of $\Gamma$, i.e

$\widehat{\Gamma}:=\\{[\pi]:\ \pi:\Gamma\to U(V_{\pi})\text{ is an irreducible
unitary representation of }\Gamma\\},$

where $[\pi]$ denotes the equivalence class of $\pi$; we simply write
$\pi\in\widehat{\Gamma}$ when there is no confusion about the notation. It is
well-known that

$\sum_{\pi\in\widehat{\Gamma}}d_{\pi}^{2}=|\Gamma|.$ (2.1)

For a given $\pi\in\widehat{\Gamma}$ and a unitary representation $\rho$ of
$\Gamma$, we denote by $m(\pi,\rho)$ be the number of times that $\pi$ occurs
in the decomposition in irreducible components of $\rho$ given in 2.1.

The entries $\pi_{ij}$ of a representation $\pi:\Gamma\to GL(V)$ can be
regarded as elements of $L^{2}(\Gamma)$ with the usual inner product

$\langle\phi,\psi\rangle_{L^{2}(\Gamma)}:=\sum_{g\in\Gamma}\phi(g)\overline{\psi(g)}\qquad\text{
for every }\phi,\psi\in L^{2}(\Gamma).$

The following theorem establishes orthogonality relations for the entries of
irreducible unitary representations (see Theorem 1 in [19, Chapter 15]).

######  Theorem 2.3 (The Schur Orthogonality relations).

If $\pi,\rho$ are two inequivalent irreducible finite dimensional unitary
representations of $\Gamma$, then

$\langle\pi_{ij},\rho_{rs}\rangle=0\qquad\text{ for all }i,j,r,s.$

Moreover, if $\delta_{ij}$ denotes the Kronecker delta function, there holds

$\langle\pi_{ij},\pi_{rs}\rangle=\frac{|\Gamma|}{d_{\pi}}\delta_{ij}\delta_{rs}.$

######  Theorem 2.4 (Clifford’s Theorem).

Suppose that $H$ is a normal subgroup of $\Gamma$ and let
$\pi\in\widehat{\Gamma}$. Denote by $\pi|_{H}$ be the restriction of $\pi$ to
$H$ and consider its decomposition in irreducible components

$\pi|_{H}\cong\pi_{1}\oplus\ldots\oplus\pi_{k}\qquad\text{where
}\pi_{i}\in\widehat{H}\text{ for every }1\leq i\leq k.$ (2.2)

Then for each $1\leq j\leq k$ there exists $g_{j}\in G$ such that for all
$h\in H$ we have $\pi_{j}(h)=\pi_{1}(g_{j}^{-1}hg_{j})$. Moreover, the
following hold:

  1. 1.

All the irreducible components in (2.2) have the same degree, i.e, for every
$1\leq i\leq k$ there holds that $d_{\pi_{1}}=d_{\pi_{i}}$.

  2. 2.

All the irreducible components in (2.2) have the same multiplicity, i.e, for
every $1\leq i\leq k$ there holds that
$m(\pi_{1},\pi|_{H})=m(\pi_{i},\pi|_{H})$.

###  2.2 Fourier Transform on Finite groups

Define the Fourier Transform of a function $f\in L^{1}(\Gamma)$ by

$\mathcal{F}(f)(\pi):=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}f(g)\pi(g),\qquad\text{
for every }\pi\in\widehat{\Gamma}.$ (2.3)

For $\phi,\psi\in L^{2}(\Gamma)$ define the convolution $\phi*\psi$ as follows

$\phi*\psi(g):=\sum_{h\in\Gamma}\phi(h)\psi(h^{-1}g).$

Then with the above definitions, we get that

$\mathcal{F}(\phi*\psi)(\pi)=|\Gamma|\mathcal{F}(\phi)(\pi)\mathcal{F}(\psi)(\pi).$
(2.4)

Denote by $L^{2}(\widehat{\Gamma})$ be the vector space

$L^{2}(\widehat{\Gamma}):=\left\\{f:\widehat{\Gamma}\to\bigsqcup_{\pi\in\widehat{\Gamma}}\mathbb{C}^{d_{\pi}\times
d_{\pi}}:\ f(\pi)\in\mathbb{C}^{d_{\pi}\times d_{\pi}}\text{ for every
}\pi\in\widehat{\Gamma}\right\\}.$

We endow $L^{2}(\widehat{\Gamma})$ with the inner product
$\langle\cdot,\cdot\rangle_{L^{2}(\widehat{\Gamma})}$ given by

$\langle
f,g\rangle_{L^{2}(\widehat{\Gamma})}:=\frac{1}{|\Gamma|}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\mathsf{Tr}(f(\pi)g(\pi)^{*}).$
(2.5)

Here $\mathsf{Tr}(T)$ is the trace of a linear operator $T:V\to V$, and is
defined by $\mathsf{Tr}(T):=\sum_{j=1}^{d_{\pi}}\langle Te_{j},e_{j}\rangle$,
where $(e_{i})$ ranges over any orthonormal basis of $V$. In particular, for
all $f\in L^{2}(\widehat{\Gamma})$ there holds that

$\|f\|_{L^{2}({\widehat{\Gamma}})}^{2}=\frac{1}{|\Gamma|}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}|f_{ij}(\pi)|^{2},$
(2.6)

where $f_{ij}(\pi)$, $i,j=1,\ldots,d_{\pi}$ are the entries of the matrix
$f(\pi)$ in a basis $(e_{i}^{(\pi)})_{i=1}^{d_{\pi}}$ of $V_{\pi}$.

By the Plancherel Theorem, we have that the Fourier Transform is an isometric
isomorphism between $L^{2}(\Gamma)$ and $L^{2}(\widehat{\Gamma})$, i.e., that
for any $f,g\in L^{2}(\Gamma)$ there holds

$|\Gamma|^{2}\langle\mathcal{F}(f),\mathcal{F}(g)\rangle_{L^{2}(\widehat{\Gamma})}=\langle
f,g\rangle_{L^{2}(\Gamma)}.$ (2.7)

By the Peter-Weyl Theorem, the matrix entries $\pi_{ij}\in L^{2}(\Gamma)$ of
$\pi\in\widehat{\Gamma}$ form a complete orthogonal set in $L^{2}(\Gamma)$. In
particular, (2.7) can be written as

$\langle
f,g\rangle_{L^{2}(\Gamma)}=\frac{1}{|\Gamma|}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}\langle
f,\pi_{ij}\rangle_{L^{2}(\Gamma)}\overline{\langle
g,\pi_{ij}\rangle}_{L^{2}(\Gamma)}.$ (2.8)

Finally, the Fourier inversion formula says that every $f\in L^{2}(\Gamma)$
can be reconstructed from its Fourier transform as follows

$f(h)=\frac{1}{|\Gamma|}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\mathsf{Tr}(\pi(h^{-1})\mathcal{F}(\pi))=\frac{1}{|\Gamma|}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}\langle
f,\pi_{ij}\rangle\pi_{ij}(h).$ (2.9)

###  2.3 Estimating the Fourier Transform under random perturbations

Let $\Gamma$ be a non-simple finite group and $H$ a normal subgroup of
$\Gamma$. Recall that the Fourier Transform of a function $f\in L^{2}(\Gamma)$
by

$\mathcal{F}(f)(\pi)=\widehat{f}(\pi):=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}f(g)\pi(g),\qquad\text{for
}\pi\in\widehat{\Gamma}.$ (2.10)

Consider the Dirac delta of $H$ defined by

$\delta_{H}(g):=\left\\{\begin{array}[]{lc}1&\text{if }g\in H\\\ \\\
0&\text{otherwise.}\end{array}\right.$

As in the Euclidean case, our first goal is to relate the Fourier Transform of
$\delta_{H}\in L^{2}(\Gamma)$ with the annihilator set $H^{\perp}$ defined by

$H^{\perp}:=\\{\pi\in\widehat{\Gamma}:\ \pi(h)=\mathsf{ld}_{V_{\pi}}\text{ for
every }h\in H\\}$ (2.11)

We also have the following characterization, which must be a classical result,
but for which we were not able to find an explicit reference:

######  Lemma 2.5.

$H^{\perp}\cong\widehat{\Gamma/H}$.

###### Sketch of the proof. .

Let $i:\Gamma\to\Gamma/H$ be the canonical map associating to every
$g\in\Gamma$ its equivalence class $i(g)\in\Gamma/H$. The natural map
$\phi:H^{\perp}\to\widehat{\Gamma/H}$ given by

$\phi(\pi)(i(g)):=\pi(g)$

is well-defined and determines a group isomorphism between $H^{\perp}$ and
$\widehat{\Gamma/H}$. We leave the details to the reader. ∎

For the next discussion, we will study the unitary representations $\pi\not\in
H^{\perp}$. Given a representation $\pi\in\widehat{\Gamma}\setminus
H^{\perp}$, by 2.1 we can decompose $\pi|_{H}$ (modulo equivalence) in
irreducible components

$\pi|_{H}=\pi_{1}\oplus\ldots\oplus\pi_{k},\qquad\text{ where
}\pi_{i}\in\widehat{H}\text{ for every }i=1,\ldots,k.$

In this setting, consider the matrix $\widehat{\delta_{H}}(\pi)_{i}$ as the
the $d_{i}\times d_{i}$-block of $\widehat{\delta_{H}}(\pi)$ defined by

$\left(\widehat{\delta_{H}}(\pi)\right)_{i}:=P_{i}^{T}\widehat{\delta_{H}}(\pi)P_{i}=\frac{1}{|\Gamma|}\sum_{h\in
H}\pi_{i}(h),$ (2.12)

where $P_{i}$ is the projection onto the subspace of $V_{i}$ where $\pi_{i}$
acts, and $d_{i}$ is the degree of $\pi_{i}$. Note that in the above
definition, we use an abuse of notation: we have $\widehat{\delta_{H}}\in
L^{2}(\widehat{\Gamma})$ and in general 2.1 cannot be applied to
$\widehat{\delta_{H}}(\pi)$ directly.

######  Lemma 2.6.

We have that

  1. 1.

If $\pi\in H^{\perp}$, then
$\widehat{\delta_{H}}(\pi)=\frac{|H|}{|\Gamma|}\mathsf{Id}_{V_{\pi}}$.

  2. 2.

If $\pi\in\widehat{\Gamma}\setminus H^{\perp}$, then when we decompose
$\widehat{\delta_{H}}(\pi)$ as in (2.12), for all $i=1,\ldots,k$ for which
$\pi_{i}\neq\mathsf{Id}_{V_{\pi_{i}}}$, the block
$\left(\widehat{\delta_{H}}(\pi)\right)_{i}$ vanishes.

In particular, if $H$ is a normal subgroup of $\Gamma$, then

$\widehat{\delta_{H}}(\pi)=\frac{|H|}{|\Gamma|}\mathsf{Id}_{d_{\pi}}\delta_{H^{\perp}}(\pi)=\left\\{\begin{array}[]{lc}\frac{|H|}{|\Gamma|}\mathsf{Id}_{d_{\pi}}&\text{if
}\pi\in H^{\perp}\\\ \\\ 0&\text{otherwise.}\end{array}\right.$

###### Proof.

Firstly, by the definition of the Fourier Transform, we get that

$\widehat{\delta_{H}}(\pi)=\frac{1}{|\Gamma|}\sum_{h\in H}\pi(h).$ (2.13)

If $\pi\in H^{\perp}$ then it is direct that
$\widehat{\delta_{H}}(\pi)=\frac{|H|}{|\Gamma|}\mathsf{ld}_{V_{\pi}}$. Thus we
concentrate on the case $\pi\not\in H^{\perp}$. In this case, there must
exists $h^{\prime}\in H$ such that $\pi(h^{\prime})\neq\mathsf{Id}_{V_{\pi}}$.
For this choice of $h^{\prime}$, there holds

$\begin{split}\pi(h^{\prime})\widehat{\delta_{H}}(\pi)=\frac{1}{|\Gamma|}\sum_{h\in
H}\pi(h^{\prime}h)=\widehat{\delta_{H}}(\pi)=\widehat{\delta_{H}}(\pi)\pi(h^{\prime}).\end{split}$
(2.14)

In particular for each block in the decomposition of $\pi|_{H}$ from 2.1, we
have that the operator $\widehat{\delta_{H}}(\pi)_{i}$ belongs to $I(\pi_{i})$
(if $\pi(h^{\prime})=\mathsf{Id}_{V_{\pi}}$) then
$\widehat{\delta_{H}}(\pi)_{i}$ obviously commutes with
$\pi_{i}(h^{\prime})$). By Schur’s Lemma, there is a scalar $c_{i}$ such that
$\widehat{\delta_{H}}(\pi)_{i}=c_{i}\cdot\mathsf{Id}_{V_{\pi_{i}}}$. If $1\leq
i\leq k$ satisfies that $\pi_{i}(h^{\prime})\neq\mathsf{Id}_{V_{\pi_{i}}}$,
then from (2.14) we get that $c_{i}=0$, otherwise
$\pi_{i}(h^{\prime})=\mathsf{Id}_{V_{\pi_{i}}}$ contradicting the choice of
$\pi$ and $h^{\prime}\in H$. Therefore the matrix
$\widehat{\delta_{H}}(\pi)_{i}$ vanishes as claimed.

Now, assume that $H$ is a normal subgroup of $\Gamma$. In this case, consider
the matrix

$P_{\pi}:=\sum_{g\in\Gamma}\pi(g)\widehat{\delta_{H}}(\pi)\pi(g^{-1}).$

There holds $P_{\pi}\in I(\pi)$, since for every $g^{\prime}\in\Gamma$ we can
write

$\begin{split}\pi(g^{\prime})P_{\pi}&=\sum_{g\in\Gamma}\pi(g^{\prime}g)\widehat{\delta_{H}}(\pi)\pi(g^{-1})=\sum_{p\in\Gamma}\pi(p)\widehat{\delta_{H}}(\pi)\pi(p^{-1}g^{\prime})=P_{\pi}\pi(g^{\prime}).\end{split}$

Hence, by Schur’s Lemma, there is a constant $\lambda$ such that

$P=P_{\pi}=\lambda\cdot\mathsf{Id}_{d_{\pi}}.$ (2.15)

On the other hand, since $H$ is a normal subgroup of $\Gamma$, we have

$P_{\pi}=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}\pi(g)\left(\sum_{h\in
H}\pi(h)\right)\pi(g^{-1})=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}\sum_{h\in
H}\pi(ghg^{-1})=\sum_{g\in\Gamma}\widehat{\delta_{gHg^{-1}}}(\pi)=|\Gamma|\widehat{\delta_{H}}(\pi).$
(2.16)

Thus, from (2.15) and (2.16) we get that

$\widehat{\delta_{H}}(\pi)=\frac{\lambda}{|\Gamma|}\mathsf{Id}_{d_{\pi}}.$
(2.17)

For $\pi\in H^{\perp}$, by applying the above to the the identity of $\Gamma$,
we obtain that $\lambda=|H|$. For $\pi\in\widehat{\Gamma}\setminus H^{\perp}$,
we have that the values $c_{i}$ from the paragraph following (2.17) are all
equal to $c_{i}=\frac{\lambda}{|\Gamma|}$, and therefore $\lambda=0$. This
finishes the proof. ∎

######  Remark 2.7.

The last formula of Lemma 2.6 is a consequence of a more general result, which
says that $f\in L^{2}(\Gamma)$ is a class function (i.e., if
$f(ghg^{-1})=f(h)$ for every $h,g\in\Gamma$) if and only if $\widehat{f}(\pi)$
is a scalar multiple of $\mathsf{Id}_{d_{\pi}}$. See for instance Tao’s
Lecture notes of Representation Theory [18].

Now, to describe random perturbations of a subgroup $H$ of a group $\Gamma$ as
above, let $(\xi_{h})_{h\in H}$ be independent identically distributed random
vectors defined in a probability space $(\Omega,\mathcal{T},\mathbb{P})$,
where for each $h\in H$ the random variable $\xi_{h}$ is $\Gamma$-valued. Like
in the euclidean case, consider the realization set $H_{\xi}$ as the subset of
$\Gamma$ defined by

$H_{\xi}:=\\{h\xi_{h}:\ h\in H\\}.$ (2.18)

Equivalently, if $\mu_{e}$ denotes the law of $\xi_{\mathsf{id}}$, then the
law of $h\xi_{h}$ is the image measure of $\mu_{e}$ under the $H$-left
translations $L_{h}(h^{\prime}):=hh^{\prime}$.

The main result of this section is an approximate recovery of
$\widehat{\delta_{H}}$ from $\widehat{\delta_{H_{\xi}}}$ as follows.

######  Theorem 2.8.

Let $L>3$ and let $H$ be a normal subgroup of $\Gamma$ with cardinality $|H|$
at least $6L/(L-3)$. Consider $\xi_{h},h\in H$ be i.i.d. $\Gamma$-valued
random variables with $\xi_{h}\sim\xi$ and
$C_{\xi,\Gamma}:=\sup_{\pi\in\widehat{\Gamma}}\mathsf{Var}[\pi(\xi)]<\infty$,
and assume that $\varepsilon>\left(\frac{12C^{2}L}{|H|}\right)^{1/2}$. Then
with probability at least $1-\frac{12C^{2}L}{\varepsilon^{2}|H|}$ we have

$\left\|\widehat{\delta_{H_{\xi}}}-\widehat{\delta_{H}}\cdot\mathbb{E}[\xi(\cdot)]\right\|_{L^{2}(\widehat{\Gamma})}^{2}\leq\frac{|H|^{4}}{|\Gamma|^{2}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)\max_{\pi\in\widehat{\Gamma}}d_{\pi},$
(2.19)

where
$\xi(\cdot):\widehat{\Gamma}\to\bigsqcup_{\pi\in\widehat{\Gamma}}\mathbb{C}^{d_{\pi}\times
d_{\pi}}$ stands for the map $\xi(\pi):=\pi(\xi)$.

By the definition of $|\cdot|_{L^{2}(\widehat{\Gamma})}$ fixed in (2.5), the
left-hand side of (2.19) can be written as

$\begin{split}\left\|\widehat{\delta_{H_{\xi}}}-\widehat{\delta_{H}}\cdot\mathbb{E}[\xi(\cdot)]\right\|^{2}_{L^{2}(\widehat{\Gamma})}&=\frac{1}{|\Gamma|}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{j=1}^{d_{\pi}}\left\|\left(\widehat{\delta_{H_{\xi}}}(\pi)-\widehat{\delta_{H}}(\pi)\mathbb{E}(\xi(\pi))\right)e_{j}^{(\pi)}\right\|_{V_{\pi}}^{2}\\\
&=\frac{1}{|\Gamma|^{3}}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}\left|\sum_{l=1}^{d_{\pi}}\sum_{h\in
H}\pi_{il}(h)\left(\pi_{lj}(\xi_{h})-\mathbb{E}[\pi_{lj}(\xi)]\right)\right|^{2}\\\
&=\frac{1}{|\Gamma|^{3}}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}\left|\sum_{l=1}^{d_{\pi}}\langle\pi_{il},\overline{\pi_{lj}(\xi_{h})-\mathbb{E}[\pi_{lj}(\xi)]}\rangle_{L^{2}(H)}\right|^{2},\end{split}$
(2.20)

and where $\\{e_{1}^{(\pi)},\dots,e_{d_{\pi}}^{(\pi)}\\}$ is an orthonormal
basis for $V_{\pi}$. Now for fixed $\pi\in L^{2}(\widehat{\Gamma})$ we define
$f_{il},g_{lj}\in L^{2}(H)$ and their extensions by zero $F_{il},G_{lj}\in
L^{2}(\Gamma)$ by

$f_{il}^{(\pi)}(h)=f_{il}(h):=\pi_{il}(h)\qquad\text{and}\qquad
g_{lj}^{(\pi)}(h)=g_{lj}(h):=\overline{\pi_{lj}(\xi_{h})-\mathbb{E}[\pi_{lj}(\xi)]},$
$F_{il}^{(\pi)}=F_{il}=f_{il}\delta_{H}\qquad\text{and}\qquad
G_{lj}^{(\pi)}=G_{lj}=g_{lj}\delta_{H}.$

With this notation, our main goal for estimating (2.20) is to find a suitable
bound for $\sum_{l=1}^{d_{\pi}}\langle f_{il},g_{lj}\rangle_{L^{2}(H)}$,
possibly depending on $i,j$, since (2.20) can be rewritten as:

$\left\|\widehat{\delta_{H_{\xi}}}-\widehat{\delta_{H}}\cdot\mathbb{E}[\xi(\cdot)]\right\|^{2}_{L^{2}(\widehat{\Gamma})}=\frac{1}{|\Gamma|^{3}}\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}\left|\sum_{l=1}^{d_{\pi}}\langle
f_{il},g_{lj}\rangle_{L^{2}(H)}\right|^{2}.$ (2.21)

Observe that $f_{il}$ is deterministic and $g_{lj}$ is random.

By triangle inequality, Cauchy-Schwarz inequality and the Plancherel formula
(2.7), we rewrite the summands in (2.21) via the Fourier transforms of
$F_{il},G_{lj}$ (compare with (5.8)):

$\begin{split}\left|\sum_{l=1}^{d_{\pi}}\langle
F_{il},G_{lj}\rangle_{L^{2}(\Gamma)}\right|&=|\Gamma|^{2}\left|\sum_{l=1}^{d_{\pi}}\left\langle\widehat{F_{il}},\widehat{G_{lj}}\right\rangle_{L^{2}(\widehat{\Gamma})}\right|\leq|\Gamma|^{2}\sum_{l=1}^{d_{\pi}}\left\|\widehat{F_{il}}\right\|_{L^{2}(\widehat{\Gamma})}\left\|\widehat{G_{lj}}\right\|_{L^{2}(\widehat{\Gamma})}.\end{split}$
(2.22)

We concentrate first on determining $\|\widehat{F_{il}}\|_{L^{2}(\Gamma)}$. We
now fix our orthonormal basis of $V_{\pi}$ so that it is adapted to the
decomposition

$\pi|_{H}=\pi_{1}\oplus\ldots\oplus\pi_{l(\pi)},\qquad\text{where
}\pi_{k}\in\widehat{H}\text{ for every }k=1,\ldots,l(\pi).$

Therefore $\pi_{il}\delta_{H}\in L^{2}({H})$ appears as a matrix-entry of some
irreducible component, whose index we denote $k(i,l)=k,1\leq k\leq l(\pi)$; we
denote by $\pi_{pq}^{(k)}$ the matrix entry of $\pi_{k}$ corresponding to
$\pi_{il}\delta_{H}$.

######  Lemma 2.9.

As before, let $\pi\in\widehat{\Gamma}$, let $\pi_{il}$ be a matrix entry of
$\pi$ such that $\pi_{il}$ is not constantly zero over $H$, and let
$\pi_{k(i,l)}=\pi_{k}\in\widehat{H}$ be the irreducible component of
$\pi|_{H}$ in which $\pi_{il}$ appears. Then the following holds:

  1. 1.

The support of $\widehat{F_{il}}$ is the set of all irreducible unitary
representations $\rho\in\widehat{\Gamma}$ for which $\pi_{k}$ occurs in the
decomposition in irreducible components of $\rho|_{H}$.

  2. 2.

If $m(\pi_{k},\rho|_{H})$ is the number of times that $\pi_{k}$ appears in the
decomposition of $\rho|_{H}$ in irreducible components, then

$\|\widehat{F_{il}}\|_{L^{2}(\Gamma)}^{2}=\frac{|H|^{2}}{d_{\pi_{k}}^{2}|\Gamma|^{3}}\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\cdot
m(\pi_{k},\rho|_{H})$ (2.23)

where $\chi_{\rho}(h):=\mathsf{Tr}(\rho(h))$ is the character of the
representation $\rho:H\to GL(V_{\rho})$.

###### Proof point 1. of Lemma 2.9.

Let $\rho\in\widehat{\Gamma}$. By 2.1 $\rho|_{H}$ decomposes as

$\rho|_{H}=\rho_{1}\oplus\ldots\oplus\rho_{l(\rho)},\qquad\text{where
}\rho_{k}\in\widehat{H}\text{ for every }1\leq k\leq l(\rho).$

With these notations, we will prove that

$\widehat{F_{il}}(\rho)\neq 0\qquad\text{if and only if}\qquad\exists\ 1\leq
m\leq l(\rho)\text{ such that }\rho_{m}=\pi_{k}.$

With respect to bases of $V_{\pi},V_{\rho}$ adapted to the decompositions of
$\pi|_{H},\rho|_{H}$, we have

$\widehat{F_{il}}(\rho)=\frac{1}{|\Gamma|}\sum_{h\in
H}\pi_{il}(h)\rho(h)=\frac{1}{|\Gamma|}\sum_{h\in
H}\pi_{pq}^{(k)}(h)\rho(h)=\left(\frac{1}{|\Gamma|}\langle\pi_{pq}^{(k)},\overline{\rho_{rs}}\rangle_{L^{2}(H)}\right)_{r,s=1}^{d_{\rho}}.$

If a component $\rho_{m}$ of $\rho|_{H}$ is not equivalent to $\pi_{k}$, then
Schur’s orthogonality relations (2.3) give

$\langle\pi_{pq}^{(k)},\overline{\rho_{rs}^{(m)}}\rangle_{L^{2}(H)}=0\qquad\text{for
every entry $\rho_{rs}^{(m)}$ of $\rho_{m}$}.$ (2.24)

In particular, if this is true for all $m$, we get

$\left(\langle\pi_{pq}^{(k)},\overline{\rho_{rs}}\rangle_{L^{2}(H)}\right)_{r,s=1}^{d_{\rho}}=0\qquad\text{for
every }1\leq r,s\leq d_{\rho}.$

This shows one direction of the claimed implication. Assume now that there is
$1\leq m\leq l(\rho)$ such that $\rho_{m}=\pi_{k}$. Then again, by 2.3 up to a
change of basis of $V_{\rho}$ we get

$\langle\pi_{pq}^{(k)},\overline{\rho_{rs}^{(m)}}\rangle_{L^{2}(H)}=\frac{|H|}{d_{\pi_{k}}}\delta_{pr}\delta_{qs},$

which in particular implies that $\widehat{F_{il}}(\rho)\neq 0$. Summarizing,
under our assumption that $\pi_{il}$ is not constantly zero over $H$, we have

$\mathsf{supp}(\widehat{F_{il}})=\\{\rho\in\widehat{\Gamma}:\ \pi_{k}\text{
appears in the decomposition in irred. components of }\rho|_{H}\\}.$

∎

######  Remark 2.10.

Consider the abelian case
$\Gamma=\mathbb{T}_{M,N}^{d}=\left(\frac{1}{M}\mathbb{Z}/N\mathbb{Z}\right)^{d}$,
$X=(\mathbb{Z}/N\mathbb{Z})^{d}$. By a dimensionality argument, every
irreducible representation $e^{-2\pi i\langle\cdot,\lambda\rangle}$ of
$\widehat{\mathbb{T}}_{M,N}^{d}\cong\mathbb{T}_{N,M}^{d}$ restricted to $X$ is
in fact an irreducible representation of $\widehat{X}=X$. Thus, for
$F_{\lambda}:=e^{-2\pi i\langle\cdot,\lambda\rangle}\delta_{X}$, from Lemma
2.9 part 1 we get that

$\mathsf{supp}(\widehat{F_{\lambda}})=\\{\alpha\in\mathbb{T}_{N,M}^{d}:\
N\alpha+N\lambda\equiv 0(mod\ M)\\}=\mathbb{T}_{M}^{d}-\lambda=X^{*}-\lambda,$

which coincides with the support of $\widehat{F_{\lambda}}$ given in (5.9)
below.

###### Proof of point 2. of Lemma 2.9.

We now use point 1. of Lemma 2.9 to compute
$|\widehat{F_{il}}|_{L^{2}(\Gamma)}$. If
$\rho\in\mathsf{supp}(\widehat{F_{il}})$, then by 2.3 we obtain a coordinate
expression

$\widehat{F_{il}}(\rho)=A_{1}\oplus A_{2}\oplus\ldots\oplus
A_{l(\rho)},\qquad\text{where }A_{m}\in M(d_{\rho_{m}}\times
d_{\rho_{m}},\mathbb{C})\text{ for every }1\leq m\leq l(\rho),$

and where from (2.24) there holds that $A_{m}=0$ if
$\rho_{m}\not\cong\pi_{k}$, whereas for $\rho_{m}\cong\pi_{k}$ we have

$A_{m}=(A_{rs}^{(m)})_{r,s=1}^{d_{\pi_{k}}}\qquad\text{where
}A_{rs}^{(m)}=\frac{|H|}{d_{\pi_{k}}|\Gamma|}\delta_{pr}\delta_{qs}.$

Then, by definition of $|\cdot|_{L^{2}(\Gamma)}$ and the previous
characterization of $\widehat{F_{il}}$, we get

$\begin{split}\|\widehat{F_{il}}\|_{L^{(}\widehat{\Gamma})}^{2}&=\frac{1}{|\Gamma|}\sum_{\rho\in\mathsf{supp}(\widehat{F_{il}})}d_{\rho}\mathsf{Tr}(\widehat{F_{il}}(\rho)\widehat{F_{il}}(\rho)^{*})\\\
&=\frac{1}{|\Gamma|}\sum_{\rho\in\mathsf{supp}(\widehat{F_{il}})}d_{\rho}\frac{|H|^{2}}{d_{\pi_{k}}^{2}|\Gamma|^{2}}\cdot
m(\pi_{k},\rho|_{H})\\\
&=\frac{|H|^{2}}{d_{\pi_{k}}^{2}|\Gamma|^{3}}\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\cdot
m(\pi_{k(i,l)},\rho|_{H}).\end{split}$

This implies the claimed equality (2.23), concluding the proof. ∎

To estimate the value of $|\widehat{G_{lj}}|_{L^{2}(\Gamma)}$, we set
$\widetilde{G_{lj}}(g):=\overline{G_{lj}(g^{-1})}$, and from the formula for
the Fourier Transform of a convolution (2.4), the definition of
$\widetilde{G_{lj}}$ and the property $\rho(g^{-1})=\rho(g)^{*}$ for every
unitary representation $\rho$, we get

$\mathcal{F}(G_{lj}*\widetilde{G_{lj}})=|\Gamma|\widehat{G_{lj}}\widehat{G_{lj}}^{*},$
(2.25)

and as we have $|A|^{2}=\mathsf{Tr}(AA^{*})$ for the Frobenius norm of a
matrix, we find

$\left|\widehat{G_{lj}}(\rho)\right|^{2}=\frac{|H|}{|\Gamma|}\mathsf{Tr}\left(\widehat{\gamma_{lj}}(\rho)\right),$
(2.26)

where $\gamma_{lj}$ denotes the _autocorrelation of $G_{lj}$_ which is defined
by

$\gamma_{lj}(g):=\frac{1}{|H|}\sum_{h\in
H}g_{lj}(h)\overline{g_{lj}(g^{-1}h)}=\frac{1}{|H|}G_{lj}*\widetilde{G_{lj}}=\frac{1}{|H|}\sum_{h\in
H}G_{lj}(h)\overline{G_{lj}(g^{-1}h)},$ (2.27)

where $\mathsf{supp}(\gamma_{lj})=H$. Hence, to estimate (2.22), in view of
(2.26), it is sufficient to find with high probability the approximate value
of $\gamma_{lj}$.

Since the $G_{lj}$ are random, it is natural to use Chebyshev inequality to
estimate (2.27). Observe that the random variables
$G_{lj}(h)\overline{G_{lj}(g^{-1}h)}$, with $h\in H$, are not necessarily
independent. Hence, for each $g\in H$ the goal is decompose $H$ into three
subsets $H_{g,i}$, $i=1,2,3$, of cardinalities close to $|H|/3$, for which the
random variables $G_{lj}(h)\overline{G_{lj}(g^{-1}h)}$, with $h$ running over
each of the $H_{g,i}$’s, are independent.

######  Lemma 2.11.

For each $g\in H\setminus\\{\mathsf{id}\\}$ we can partition the subgroup $H$
into three subsets $H_{g,0},H_{g,1},H_{g,2}$ of cardinalities satisfying
$||H_{g,i}|-|H|/3|\leq 2$, so that for any $i=0,1,2$ and every
$h,h^{\prime}\in H_{g,i}$, with $h\neq h^{\prime}$, there holds that
$\\{h,g^{-1}h\\}\cap\\{h^{\prime},g^{-1}h^{\prime}\\}=\emptyset$.

###### Proof.

Let us to start by listing the elements of $H$ by
$\\{\mathsf{id}=h_{1},h_{2},\ldots,h_{|H|}\\}$ and define $h_{i_{1}}:=h_{1}$.
For every $g\in H\setminus\\{\mathsf{id}\\}$, let $\mathcal{T}_{g}(h_{i_{1}})$
be the orbit of $h_{i_{1}}$ under left-translation of $g$, i.e:

$\mathcal{T}_{g}(h_{i_{1}}):=\\{g^{k}h_{i_{1}}:\ 0\leq k<\mathsf{ord}(g)\\}.$

Then, let $h_{i_{2}}$ be the next element of the list such that
$h_{i_{2}}\not\in\mathcal{T}_{g}(h_{i_{1}})$, and define the orbit

$\mathcal{T}_{g}(h_{i_{2}}):=\\{g^{k}h_{i_{2}}:\ 0\leq k<\mathsf{ord}(g)\\}.$

Inductively and as long as
$H\setminus\bigcup_{\alpha=1}^{m-1}\mathcal{T}_{g}(h_{i_{\alpha}})\neq\emptyset$,
we consider $h_{i_{m}}\in H$ being the next element of the list which does not
belong to some of the previous orbits and define:

$\mathcal{T}_{g}(h_{i_{m}}):=\\{g^{k}h_{i_{m}}:\ 0\leq k<\mathsf{ord}(g)\\}.$

Let $m_{H}$ be the largest positive integer for which
$H=\bigcup_{\alpha=1}^{m_{H}}\mathcal{T}_{g}(h_{i_{\alpha}})$. Since all the
orbits $\mathcal{T}_{g}(h_{i_{\alpha}})$, $1\leq\alpha\leq m_{H}$ have the
same number of points, the conclusions of Lemma 2.11 hold for the following
subsets of $H$:

$H_{g,i}:=\left\\{g^{3k+i}h_{i_{\alpha}}:\ 0\leq
k\leq\frac{\mathsf{ord}(g)}{3},\ 1\leq\alpha\leq
m_{H}\right\\},\qquad\text{where }i\in\\{0,1,2\\}.$

∎

######  Proposition 2.12.

Let $L>3$ and assume that $|H|\geq 6L/(L-3)$ and
$\varepsilon>\left(\frac{12C^{2}L}{|H|}\right)^{1/2}$. Under our hypotheses on
$\xi$, with probability at least $1-\frac{12C^{2}L}{\varepsilon^{2}|H|}$ there
holds

$\left|\gamma_{lj}(g)-\mathbb{E}\left[|G_{lj}(\mathsf{id})\overline{G_{lj}(g^{-1})}|^{2}\right]\delta_{\mathsf{id}}(g)\right|\leq\varepsilon.$
(2.28)

###### Proof.

For $g\neq\mathsf{id}$, let $H_{g,i}$ be as in Lemma 2.11. By independence of
the $\xi_{g}$, we have that the random variables
$\\{G_{lj}(h)\overline{G_{lj}(g^{-1}h)},h\in H_{q,i}\\}$ are i.i.d. By
Chebyshev inequality, since
$\mathsf{Var}[G_{lj}(h)\overline{G_{lj}(g^{-1}h)}]\leq 4C^{2}$, where
$C=\sup_{\pi\in\widehat{\Gamma}}\mathsf{Var}[\pi(\xi)]$, we find for
$i\in\\{0,1,2\\}$ and for $S_{g,i}:=\sum_{h\in
H_{g,i}}G_{lj}(h)\overline{G_{lj}(g^{-1}h)}$:

$\mathbb{P}\left(\left|\frac{1}{|H_{g,i}|}\sum_{h\in
H_{g,i}}G_{lj}(h)\overline{G_{lj}(g^{-1}h)}-\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}(g^{-1})}\right]\right|\geq\varepsilon\right)\leq\frac{\mathsf{Var}(S_{g,i})}{\varepsilon^{2}|H_{g,i}|^{2}}\leq\frac{4C^{2}}{\varepsilon^{2}|H_{g,i}|}\leq\frac{4C^{2}L}{\varepsilon^{2}|H|},$
(2.29)

where we used that $|H|\geq 6L/(L-3)$ and Lemma 2.11 to get that

$\frac{1}{|H_{g,i}|}\leq\frac{L}{|H|}.$

Denote by $\mathcal{A}_{\varepsilon}$ the event on the left in (2.29). On this
event, by triangle inequality, we find the following bound similar to the
strong law of large numbers for the variables
$G_{lj}(h)\overline{G_{lj}(g^{-1}h)}$:

$\mathbb{P}\left(\left|\gamma_{lj}(g)-\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}(g^{-1})}\right]\right|\geq\varepsilon\right)\leq\frac{12C^{2}L}{\varepsilon^{2}|H|}.$
(2.30)

Since the random variables $G_{lj}(h)$, $h\in H$ are i.i.d with zero-mean, for
every $g\neq\mathsf{id}$ we get that

$\mathbb{P}(|\gamma_{lj}(g)|\geq\varepsilon)\leq\frac{12C^{2}L}{\varepsilon^{2}|H|}.$
(2.31)

On the other hand, for $g=\mathsf{id}$ and since the random variables
$\\{|G_{lj}(h)|^{2},:\ h\in H\\}$ are i.i.d, the very same calculation shows
that:

$\mathbb{P}\left(\left|\frac{1}{|H|}\sum_{h\in
H}|G_{lj}(h)|^{2}-\mathbb{E}(|G_{lj}(\mathsf{id})|^{2})\right|\geq\varepsilon\right)\leq\frac{4C^{2}}{\varepsilon^{2}|H|}.$
(2.32)

Therefore, from (2.31) and (2.32) we get (2.28) as claimed. ∎

######  Corollary 2.13.

For $L,\varepsilon$ and $\xi$ as in 2.12, for each $\rho\in\widehat{\Gamma}$
there holds

$\left|\left|\widehat{G_{lj}}(\rho)\right|^{2}-\frac{|H|}{|\Gamma|^{2}}\cdot\mathbb{E}\left[|G_{lj}(\mathsf{id})|^{2}\right]\
d_{\rho}\right|\leq\varepsilon d_{\rho}\frac{|H|^{2}}{|\Gamma|^{2}}.$ (2.33)

###### Proof.

We concentrate on the term on the left-hand side in (2.26), and we find, by
triangle inequality and using the fact that $\max_{h\in
H}|\mathsf{Tr}(\rho(h))|=d_{\rho}$ and from 2.12, we get

$\begin{split}&\left|\mathsf{Tr}\left(\widehat{\gamma_{lj}}(\rho)-\mathcal{F}\left(\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}((\cdot)^{-1})}\right]\delta_{\mathsf{id}}\right)(\rho)\right)\right|\\\
&\leq\frac{1}{|\Gamma|}\sum_{g\in\Gamma}\left|\gamma_{lj}(g)-\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}(g^{-1})}|\right]\delta_{\mathsf{id}}(g)\right|\left|\mathsf{Tr}(\rho(g))\right|\leq\varepsilon
d_{\rho}\frac{|H|}{|\Gamma|},\end{split}$

where for the second inequality, we also use the fact that
$\mathsf{supp}(\gamma_{lj})=H$. Now note that

$\mathcal{F}\left(\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}((\cdot)^{-1})}\right]\delta_{\mathsf{id}}\right)(\rho)=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}(g^{-1})}\right]\delta_{\mathsf{id}}(g)\rho(g)=\mathbb{E}\left[|G_{lj}(\mathsf{id})|^{2}\right]\cdot\frac{\mathsf{Id}_{d_{\rho}}}{|\Gamma|},$

and then
$\mathsf{Tr}\left(\mathcal{F}\left(\mathbb{E}\left[G_{lj}(\mathsf{id})\overline{G_{lj}((\cdot)^{-1})}\right]\delta_{\mathsf{id}}\right)(\rho)\right)=\mathbb{E}\left[|G_{lj}(\mathsf{id})|^{2}\right]\frac{d_{\rho}}{|\Gamma|}$.
Together with (2.26) this gives

$\left|\frac{|\Gamma|}{|H|}\left|\widehat{G_{lj}}(\rho)\right|^{2}-\mathbb{E}\left[|G_{lj}(\mathsf{id})|^{2}\right]\frac{d_{\rho}}{|\Gamma|}\right|\leq\varepsilon
d_{\rho}\frac{|H|}{|\Gamma|}.$

the desired bound (2.33) follows directly. ∎

######  Corollary 2.14.

Under the hypotheses of Corollary 2.13, there holds

$\left|\left\|\widehat{G_{lj}}\right\|_{L^{2}(\widehat{\Gamma})}^{2}-\frac{|H|}{|\Gamma|^{2}}\cdot\mathbb{E}\left[|G_{lj}(\mathsf{id})|^{2}\right]\right|\leq\frac{\varepsilon|H|^{2}}{|\Gamma|^{2}}.$
(2.34)

###### Proof.

By the triangle inequality, we find

$\left|\left\|\widehat{G_{lj}}\right\|^{2}_{L^{2}(\widehat{\Gamma})}-\frac{|H|}{|\Gamma|^{2}}\cdot\mathbb{E}\left[|G_{lj}(\xi)|^{2}\right]\right|\leq\frac{1}{|\Gamma|}\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\left|\left|\widehat{G_{lj}}(\rho)\right|^{2}-\frac{|H|}{|\Gamma|^{2}}\cdot\mathbb{E}\left[|G_{lj}(\xi)|^{2}d_{\rho}\right]\right|,$

and then (2.34) follows by applying (2.33) and (2.1). ∎

###### Proof of 2.8.

From Lemma 2.9, Corollary 2.14 and (2.22) we can bound (2.21) from above by
the below (in which $\pi_{k(i,l)}$ is as in Lemma 2.9 and
$C:=\sup_{\pi\in\widehat{\Gamma}}\mathsf{Var}[\pi(\xi)]$):

$\begin{split}&|\Gamma|\sum_{\pi\in\widehat{\Gamma}}d_{\pi}\sum_{i,j=1}^{d_{\pi}}\left(\sum_{l=1}^{d_{\pi}}\frac{\mathbbm{1}_{\pi_{il}(H)\neq\\{0\\}}}{d_{\pi_{k(i,l)}}}\left\\{\frac{|H|^{2}}{|\Gamma|^{3}}\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\cdot
m(\pi_{k(i,l)},\rho|_{H})\right\\}^{1/2}\left\\{\frac{\varepsilon|H|^{2}}{|\Gamma|^{2}}+\frac{|H|}{|\Gamma|^{2}}\mathbb{E}\left[|G_{lj}(\mathsf{id})|^{2}\right]\right\\}^{1/2}\right)^{2}\\\
&\leq\frac{|H|^{2}}{|\Gamma|^{2}}\left(\frac{\varepsilon|H|^{2}}{|\Gamma|^{2}}+\frac{4C^{2}|H|}{|\Gamma|^{2}}\right)\sum_{\pi\in\widehat{\Gamma}}d_{\pi}^{2}\sum_{i=1}^{d_{\pi}}\left(\sum_{l=1}^{d_{\pi}}\frac{\mathbbm{1}_{\pi_{il}(H)\neq\\{0\\}}}{d_{\pi_{k(i,l)}}}\left\\{\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\cdot
m(\pi_{k(i,l)},\rho|_{H})\right\\}^{1/2}\right)^{2}\\\
&=\frac{|H|^{4}}{|\Gamma|^{4}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)\sum_{\pi\in\widehat{\Gamma}}\frac{d_{\pi}^{2}}{d_{\pi_{1}}^{2}}\sum_{i=1}^{d_{\pi}}\left(\sum_{l=1}^{d_{\pi}}\mathbbm{1}_{\pi_{il}(H)\neq\\{0\\}}\left(\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\cdot
m(\pi_{1},\rho|_{H})\right)^{1/2}\right)^{2},\end{split}$ (2.35)

where in the last step, we used the fact that since $H$ is a normal subgroup,
by 2.4, the dimensions $d_{\pi_{k}}$ are independent of $k$ and equal, e.g.,
to $d_{\pi_{1}}$.

Recall that $\pi_{il}$ are the matrix coefficients of $\pi$ in a basis in
which $\pi|_{H}$ has block structure with $d_{\pi_{1}}\times
d_{\pi_{1}}$-dimensional blocks, thus for each value of index $i$, at most
$d_{\pi_{1}}$ of the indices $i,l$ can give nonzero contributions.
Furthermore, $m(\pi_{k(i,l)},\rho|_{H})\leq d_{\rho}$. Therefore we have

$\sum_{l=1}^{d_{\pi}}1_{\pi_{il}(H)\neq\\{0\\}}\left(\sum_{\rho\in\widehat{\Gamma}}d_{\rho}\cdot
m(\pi_{1},\rho|_{H})\right)^{1/2}\leq\sum_{l=1}^{d_{\pi}}\mathbbm{1}_{\pi_{il}(H)\neq\\{0\\}}\left(\sum_{\rho\in\widehat{\Gamma}}d_{\rho}^{2}\right)^{1/2}\leq|\Gamma|^{1/2}d_{\pi_{1}}.$
(2.36)

Inserting (2.36) into (2.35) we get

$\left\|\widehat{\delta_{H_{\xi}}}-\widehat{\delta_{H}}\cdot\mathbb{E}(\xi(\cdot))\right\|_{L^{2}(\widehat{\Gamma})}^{2}\leq\frac{|H|^{4}}{|\Gamma|^{3}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)\sum_{\pi\in\widehat{\Gamma}}d_{\pi}^{3}\leq\frac{|H|^{4}}{|\Gamma|^{2}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)\max_{\pi\in\widehat{\Gamma}}d_{\pi}.$

Thus we obtain the desired bound, concluding the proof of 2.8. ∎

######  Remark 2.15.

For $A\subset\widehat{\Gamma}$, the very same proof of 2.8 shows that

$\begin{split}\left\|\widehat{\delta_{H_{\xi}}}-\widehat{\delta_{H}}\cdot\mathbb{E}(\xi(\cdot))\right\|_{L^{2}(A)}^{2}&\leq\frac{|H|^{4}}{|\Gamma|^{3}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)\sum_{\pi\in
A}d_{\pi}^{3}\\\
&\leq\frac{|H|^{4}}{|\Gamma|^{2}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)\max_{\pi\in
A}d_{\pi},\end{split}$

where $\|F\|_{L^{2}(A)}^{2}:=\frac{1}{|\Gamma|}\sum_{\pi\in
A}d_{\pi}\mathsf{Tr}(F(\pi)F(\pi)^{*})$ for $F\in L^{2}(\widehat{\Gamma})$. In
particular, for $A=\\{\pi\\}$, with $\pi\in\widehat{\Gamma}$ and for (any)
orthonormal basis $(e_{i}^{(\pi)})_{i=1}^{d_{\pi}}$ it follows that

$\left\|\widehat{\delta_{H_{\xi}}}-\widehat{\delta_{H}}\cdot\mathbb{E}(\xi(\cdot))\right\|_{L^{2}(\\{\pi\\})}^{2}=\frac{d_{\pi}}{|\Gamma|}\sum_{i=1}^{d_{\pi}}\left\|\left(\widehat{\delta_{H_{\xi}}}(\pi)-\widehat{\delta_{H}}(\pi)\cdot\mathbb{E}(\pi(\xi))\right)e_{i}^{(\pi)}\right\|_{V_{\pi}}^{2}\leq\frac{|H|^{4}}{|\Gamma|^{3}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)d_{\pi}^{3},$

and thus we get the following estimation

$\sum_{i=1}^{d_{\pi}}\left\|\left(\widehat{\delta_{H_{\xi}}}(\pi)-\widehat{\delta_{H}}(\pi)\cdot\mathbb{E}(\pi(\xi))\right)e_{i}^{(\pi)}\right\|_{V_{\pi}}^{2}\leq\frac{|H|^{4}}{|\Gamma|^{2}}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)d_{\pi}^{2}.$
(2.37)

##  3 Some elements on Fourier Analysis in nilpotent Lie groups

###  3.1 Uniform subgroups in nilpotent Lie groups

We start this section with some basic background on nilpotent Lie groups; for
further details, see for instance [7]. Let $\Gamma$ be a $d$-dimensional
locally compact simply connected (lcsc) Lie group, and denote by
$\mathfrak{g}$ its Lie algebra, with associated Lie bracket
$[\cdot,\cdot]:\mathfrak{g}\times\mathfrak{g}\to\mathfrak{g}$. It is well-
known that the exponential map $\mathsf{exp}:\mathfrak{g}\to\Gamma$ produces a
global diffeomorphism between $\Gamma$ and its Lie algebra
$\mathfrak{g}\cong\mathbb{R}^{d}$, and thus we can think $\Gamma$
topologically as $\mathbb{R}^{d}$. Moreover, the exponential map is a Lie
isomorphism when $\mathfrak{g}$ is endowed with the group law given by the
Baker-Campbell-Hausdorff formula.

For the Lie algebra $\mathfrak{g}$ we define its lower central series as the
sequence of Lie subalgebras
$\mathfrak{g}\trianglerighteq\mathfrak{g}_{1}\trianglerighteq\mathfrak{g}_{2}\trianglerighteq\ldots$,
where

$\mathfrak{g}_{0}:=\mathfrak{g}\qquad\text{and}\qquad\mathfrak{g}_{i}:=[\mathfrak{g},\mathfrak{g}_{i-1}].$

We say that $\Gamma$ is nilpotent if there exists a positive integer $s$ such
that $\mathfrak{g}_{s+1}=\\{0\\}$; when $\mathfrak{g}_{s}\neq\\{0\\}$ and
$\mathfrak{g}_{s+1}=\\{0\\}$, then $G$ is nilpotent of step $s$.

Now, assume that $\Gamma$ is nilpotent of step $s$. A subset
$\\{X_{1},\ldots,X_{d}\\}\subset\Gamma$ is called a strong Mal’cev basis
subordinated to
$\\{0\\}=\mathfrak{g}_{s+1}\subset\mathfrak{g}_{s}\subset\ldots\subset\mathfrak{g}_{2}\subset\mathfrak{g}_{1}\subset\mathfrak{g}_{0}=\mathfrak{g}$
if for each $0\leq i\leq s$ there holds that

$\mathfrak{g}_{i}=\mathsf{span}\\{X_{1},\ldots,X_{d_{i}}\\},\qquad\text{where}\qquad
d_{i}:=\mathsf{dim}(\mathfrak{g}_{i}).$ (3.1)

For $X_{j},X_{k}$ in the Mal’cev basis, $j\leq k$, there exists a natural
number $i$ such that $X_{k}\in\mathfrak{g}_{i}$, and in particular we get that
$[X_{j},X_{k}]\in\mathfrak{g}_{i+1}$. Since $\\{X_{1},\ldots,X_{d}\\}$ is a
strong Mal’cev basis, there are constants $c_{jk}^{l}$, $1\leq l\leq d_{i+1}$
(called structural constants), such that

$[X_{j},X_{k}]=\sum_{l=1}^{d_{i+1}}c_{jk}^{l}X_{l}.$

For a Mal’cev basis as above, we can establish a diffeomorphism
$\phi:\mathbb{R}^{d}\to\Gamma$ given by the formula

$\phi(x_{1},\ldots,x_{d}):=\mathsf{exp}(x_{1}X_{1})\cdot\mathsf{exp}(x_{2}X_{2})\cdot\ldots\cdot\mathsf{exp}(x_{d}X_{d}),$
(3.2)

which by the Baker-Campbell-Hausdorff formula (see [7, Proposition 1.2.7]), is
a polynomial diffeomorphism of the form

$\phi(x)=\mathsf{exp}\left(\sum_{j=1}^{d}P_{j}(x)X_{j}\right),$ (3.3)

where the $P_{j}$’s are polynomials without constant coefficients, and

$P_{j}(x)=x_{j}+\text{ a polynomial on }x_{j+1},\ldots,x_{d},\qquad\text{for
}j=1,\ldots,d.$

Observe that if $\Gamma$ admits a Mal’cev basis with rational structural
constants, we can choose the polynomials $P_{j}$ with integer coefficients.

If $\Gamma$ is a lcsc nilpotent Lie group, by a uniform subgroup in $\Gamma$,
we mean a discrete subgroup $H\subset\Gamma$ such that $\Gamma/H$ is compact.
The nature of the structural constants is intrinsically related to the
existence of a uniform subgroup in $\Gamma$. Indeed, the way to connect both
concepts is given by the next (see [7, Theorem 5.1.8]):

$\begin{split}\Gamma\text{ admits a uniform subgroup
}H\Longleftrightarrow\mathfrak{g}\text{ admits a Mal'cev basis with rational
structural constants.}\end{split}$

Let $H\subset\Gamma$ be uniform and let $K\subset\Gamma$ be a subgroup. In
this case, it is known that $K$ is rational (i.e., its Lie algebra admits a
Mal’cev basis with rational structural constants) if and only if $H\cap K$ is
uniform in $K$ (see [7, Theorem 5.1.11]); this fact will be exploited in
Section 4.1.

###  3.2 Induced representations

In this section, we give the basic and necessary elements of induced
representations that will be used for the problem of recovering the discrete
Fourier spectrum in nilpotent groups; for more details, see [10, Chapter 6].
Induced representations are representations of a group $\Gamma$ constructed
from a smaller subgroup $K$. Let $\Gamma$ be a locally compact group, $K$ be a
closed subgroup, and $i:\Gamma\to\Gamma/K$ be the canonical quotient map that
sends an element $x\in\Gamma$ to its equivalence class $[x]$, and where
$\Gamma/K$ denotes the space of right-cosets. Consider a unitary
representation $\sigma:K\to\mathcal{U}(\mathcal{H}_{\sigma})$, where the inner
product and the norm in the Hilbert space $\mathcal{H}_{\sigma}$ are denoted
by $\langle\cdot,\cdot\rangle_{\mathcal{H}_{\sigma}}$ and
$||\cdot||_{\mathcal{H}_{\sigma}}$, respectively.

For our purposes, assume that $\Gamma/K$ admits a left-invariant measure
$\eta$ (this is the case, for instance, when $K$ is a closed subgroup of a
nilpotent Lie group $\Gamma$). Let $\mathcal{F}_{\sigma}$ be the space of all
the Borel measurable functions $f:\Gamma\to\mathcal{H}_{\sigma}$ such that

$\int_{\Gamma/K}\|f(x)\|^{2}d\eta(xK)<\infty\qquad\text{and}\qquad f(\xi
x)=\sigma(\xi)f(x)\text{ for }x\in\Gamma,\xi\in K.$ (3.4)

Observe that for $f,g\in\mathcal{F}_{\sigma}$ and $x\in\Gamma$, the inner
product $\langle f(x),g(x)\rangle_{\sigma}$ only depends on the coset $i(x)$.
Then, we can define an inner product in $\mathcal{F}_{\sigma}$ by means of the
formula:

$\langle f,g\rangle=\langle
f,g\rangle_{\mathcal{F}_{\sigma}}:=\int_{\Gamma/K}\langle
f(x),g(x)\rangle_{\mathcal{H}_{\sigma}}d\eta(xK).$ (3.5)

Thus, the inner product (3.5) becomes $\mathcal{F}_{\sigma}$ in a complete
Hilbert space. Note that the left-translation $x\mapsto
L_{x}:\mathcal{F}_{\sigma}\to\mathcal{F}_{\sigma}$, where
$L_{x}(f)(y):=f(xy)$, is a unitary representation of $\Gamma$. Hence, we
define the induced representation by $\sigma$ as the unitary representation
$\mathsf{ind}_{K}^{\Gamma}(\sigma):\Gamma\to\mathcal{U}(\mathcal{F}_{\sigma})$
given by left-translations; more precisely

$[\mathsf{ind}_{H}^{G}(\sigma)(x)f](y):=f(xy).$ (3.6)

For explicit computations of the Fourier transform, it is more useful to
describe $\mathsf{ind}_{K}^{\Gamma}(\sigma)$ by acting over a suitable space
of square-integrable functions. To achieve this, let
$\alpha:\Gamma/K\to\Gamma$ be a Borel cross-section of $i:\Gamma\to\Gamma/K$,
i.e., for which there holds $i\circ\alpha=\mathsf{id}_{\Gamma/K}$. Due to
(3.4) we have that $f\in\mathcal{F}_{\sigma}$ is completely determined by its
values on $\alpha(\Gamma/K)$; indeed, we have that for every $x\in\Gamma$
there exist $h=h(x)\in K$ and $k=k(x)\in\alpha(\Gamma/K)$ such that
$x=h(x)k(x)$, and then

$f(x)=f(hk)=\sigma(h)f(k).$ (3.7)

In addition, we have that the map $\mathcal{F}_{\sigma}\ni f\mapsto
f\circ\alpha\in L^{2}(\Gamma/K)$ becomes in an isometry.

###  3.3 Elements of Kirillov’s orbit method

In this section, we introduce the necessary ingredients of the well-understood
theory of irreducible representations in nilpotent groups developed in the
remarkable work of Kirillov [12]. Henceforth let $\Gamma$ be an lcsc nilpotent
Lie group. For $g\in\Gamma$ denote by $\Psi_{x}:\Gamma\to\Gamma$ the
conjugation given by $\Psi_{g}(x)=gxg^{-1}$ and consider the map
$\mathsf{Ad}_{g}:=(\Psi_{g})_{*}:\mathfrak{g}\to\mathfrak{g}$, where

$((\Psi_{g})_{*}X)_{p}:=(d\Psi_{g})_{\Psi_{g}^{-1}(p)}X_{\Psi_{g}^{-1}(p)},\qquad\text{for
}X\in\mathfrak{g}.$

The adjoint representation corresponds to the map $\mathsf{Ad}:\Gamma\to
GL(\mathfrak{g})$ given by $\mathsf{Ad}(g):=\mathsf{Ad}_{g}$. The coadjoint
map $\mathsf{Ad}^{*}:\Gamma\to GL(\mathfrak{g}^{*})$ is defined by the formula

$[(\mathsf{Ad}^{*}x)l](Y):=l(\mathsf{Ad}x^{-1}Y),\qquad\text{where
}x\in\Gamma,l\in\mathfrak{g}^{*},\text{and }Y\in\mathfrak{g}.$ (3.8)

Formula (3.8) defines an action of $\Gamma$ over $\mathfrak{g}^{*}$ given by
$x\cdot l:=(\mathsf{Ad}^{*}x)l$. Each $l\in\mathfrak{g}^{*}$ determines a
symplectic form $B_{l}:\mathfrak{g}\times\mathfrak{g}\to\mathfrak{g}$ defined
as follows:

$B_{l}(X,Y):=l([X,Y]),\quad\text{where }X,Y\in\mathfrak{g}.$ (3.9)

The radical of $B_{l}$ is the set $r_{l}:=\\{Y\in\mathfrak{g}:\
B_{l}(X,Y)=0\text{ for every }X\in\mathfrak{g}\\}$. For lcsc nilpotent Lie
groups, there is a relation between the radical of $l\in\mathfrak{g}^{*}$ and
the stabilizer $\mathsf{Stab}_{l}:=\\{g\in\Gamma:g\cdot l=l\\}$ under the
coadjoint action, namely, that

$\mathsf{Stab}_{l}=\mathsf{exp}(r_{l}).$

An isotropic subspace of $\mathfrak{g}$ for $B_{l}$ is a subspace
$W\subset\mathfrak{g}$ for which $B_{l}(X,X^{\prime})=0$ for every
$X,X^{\prime}\in W$. There are maximal subalgebras
$\mathfrak{m}\subset\mathfrak{g}$ that are isotropic for $B_{l}$ and have
(maximal) isotropic dimension $d-k$, where

$k=\frac{1}{2}\mathsf{dim}(\mathfrak{g}/r_{l}).$

Such subalgebras are called polarizing subalgebras for $l$, which always exist
(see [7, Theorem 1.3.3]).

Let $\mathfrak{m}=\mathfrak{m}_{l}$ be a polarizing subalgebra for a fixed
$l\in\mathfrak{g}^{*}$, and denote $K_{l}:=\mathsf{exp}(\mathfrak{m})$. By the
isotropy, the map $\chi_{l,\mathfrak{m}}:K_{l}\to S^{1}$ given by

$\chi_{l,\mathfrak{m}}(\mathsf{exp}(Y)):=e^{2\pi il(Y)},\quad\text{where
}Y\in\mathfrak{m},$ (3.10)

is a $1$-dimensional irreducible representation of $K_{l}$. Define
$\pi_{l,\mathfrak{m}}:=\mathsf{ind}_{K}^{\Gamma}(\chi_{l,\mathfrak{m}}):\Gamma\to\mathcal{U}(\mathcal{H}_{l})$,
where $\mathcal{H}_{l}$ is the Hilbert space where $\pi_{l}$ acts, defined
like in Section 3.2. The next theorem is the cornerstone of Kirillov’s theory
and claims that the above-inducing mechanism produces all the irreducible
representations of the nilpotent group $\Gamma$.

######  Theorem 3.1.

Let $l\in\mathfrak{g}^{*}$. There exists a polarizing subalgebra
$\mathfrak{m}=\mathfrak{m}_{l}$ for $l$ such that $\pi_{l,\mathfrak{m}}$ is
irreducible. Moreover, every irreducible representation of $\Gamma$ arises in
this way. Also, the following hold:

  1. 1.

if $\mathfrak{m},\mathfrak{m}^{\prime}$ are two polarizing subalgebras for
$l$, then $\pi_{l,\mathfrak{m}}\cong\pi_{l,\mathfrak{m}^{\prime}}$. Thus, we
can write $\pi_{l}=\pi_{l,\mathfrak{m}}$.

  2. 2.

$\pi_{l}\cong\pi_{l^{\prime}}$ if and only if $l$ and $l^{\prime}$ belong to
the same $\mathsf{Ad}^{*}(\Gamma)$-orbit in $\mathfrak{g}^{*}$.

Following the discussion at the end of Section 3.2, we point out that in the
case of lcsc nilpotent Lie groups, for

$s:=\mathsf{dim}(\Gamma/K_{l})=d-\mathsf{dim}(\mathfrak{m}_{l})=\frac{1}{2}\mathsf{dim}(\mathfrak{g}/r_{l}),$
(3.11)

we have that the Hilbert space $\mathcal{H}_{l}$ is isometric to
$L^{2}(\mathbb{R}^{s})$ under the mapping $\mathcal{H}_{l}\ni f\mapsto
f\circ\alpha\in L^{2}(\Gamma/K_{l})$, and where
$\Gamma/K_{l}\cong\mathbb{R}^{s}$. In addition, we get that $s$ cannot exceed
$d/2$.

######  Lemma 3.2.

Under the previous notations, we have that $s<d/2$.

###### Proof.

Otherwise, from (3.11) we get that

$\frac{d}{2}\leq
s=\frac{d}{2}-\frac{1}{2}\mathsf{dim}(r_{l})\Longrightarrow\mathsf{dim}(r_{l})=0.$

This implies that $\mathsf{Stab}_{l}=\mathsf{exp}(r_{l})=\\{\mathsf{id}\\}$.
In particular, $\mathfrak{g}^{*}/\mathsf{Ad}^{*}\Gamma$ consists of only one
orbit, and by 3.1 we have that $|\widehat{\Gamma}|=1$. Then the trivial
representation $\Gamma\ni g\mapsto 1\in\mathbb{R}/\mathbb{Z}$ is the only
irreducible representation (under equivalence) of $\Gamma$, which is one
dimensional and hence $\Gamma$ is Abelian, and by Pontryagin duality, we have
that $\Gamma=\\{\mathsf{id}\\}$, which is impossible since
$\Gamma\cong(\mathbb{R}^{d},\cdot)$, where $d\geq 1$. ∎

###  3.4 Basics on the Fourier transform in nilpotent Lie groups

In this section, we provide the basic elements of Fourier Analysis which we
shall use to deal with the recovery problem. Although this theory can be
presented with all its abstraction in second countably, unimodular Type I
groups (see [8, 10]), as was explained above (see 1.1) we are concerned on
lcsc nilpotent Lie groups, and thus we present the theory in this last
context; we refer to [9] for further details. Like in the Euclidean case, the
basic space to define a Fourier transform in $\Gamma$ is the Schwartz space of
rapidly decreasing functions. We say that a function $f:\Gamma\to\mathbb{C}$
is in the Schwartz space $\mathcal{S}(\Gamma)$ if
$f\circ\mathsf{exp}\in\mathcal{S}(\mathfrak{g})$. For
$f\in\mathcal{S}(\Gamma)$ we define its group Fourier transform by the linear
mapping

$(\forall\pi\in\widehat{\Gamma}),\qquad\mathcal{F}(f)(\pi)=\widehat{f}(\pi):=\int_{\Gamma}f(x)\pi(x)dx:\mathcal{H}_{\pi}\to\mathcal{H}_{\pi};$
(3.12)

more precisely, for $\phi,\psi\in\mathcal{H}_{\pi}$ we have

$\langle\widehat{f}(\pi)\phi,\psi\rangle_{\mathcal{H}_{\pi}}=\int_{\Gamma}f(x)\langle\pi(x)\phi,\psi\rangle_{\mathcal{H}_{\pi}}dx.$

We say that a positive operator $T$ on a Hilbert space $\mathcal{H}$ is trace-
class if $T$ has an orthonormal basis $(e_{n})_{n\geq 1}$ with eigenvalues
$\lambda_{n}>0$ such that $\sum_{n\geq 1}\lambda_{n}<\infty$; in this case we
define $\mathsf{Tr}(T):=\sum_{n\geq 1}\lambda_{n}$. In particular, if $T$ is a
positive operator and trace-class, then for every orthonormal basis
$(x_{n})_{n\geq 1}$ for $\mathcal{H}$ we get $\mathsf{Tr}(T)=\sum_{n\geq
1}\langle Tx_{n},x_{n}\rangle_{\mathcal{H}}$. Finally, we say that an operator
$T\in\mathcal{B}(\mathcal{H})$ is trace-class if the positive operator
$|T|:=\sqrt{TT^{*}}$ is trace-class, where the root of a positive operator
$\sqrt{\cdot}$ is in the sense of spectral calculus.

In analogy to the classical Fourier transform in $\mathbb{R}^{d}$ as an
isometric isomorphism
$\mathcal{S}(\mathbb{R}^{d})\to\mathcal{S}(\mathbb{R}^{d})$ (and then extended
to an operator from $L^{2}(\mathbb{R}^{d})$ to itself), the nature of the
space $\mathcal{F}(\mathcal{S}(\Gamma))$ is well-understood as a function
space after $\widehat{\Gamma}$ is equipped with an appropriate measure, called
the Plancherel measure below.

######  Theorem 3.3 (Thm. 1.8.2 in [9]).

There exists a $\sigma$-finite measure $\mu$ in $\widehat{\Gamma}$ called the
Plancherel measure such that for every $\phi\in\mathcal{S}(\Gamma)$, the
operator
$\mathcal{F}(\phi)=\widehat{\phi}(\pi)\in\mathcal{B}(\mathcal{H}_{\pi})$ is
trace-class for any strongly continuous unitary representation $\pi$, and
$\mathsf{Tr}(\widehat{\phi}(\pi))$ depends only in the class of $\pi$.
Moreover, the function $\pi\mapsto\mathsf{Tr}(\widehat{\phi}(\pi))$ is
integrable against $\mu$ and there holds:

$\phi(0)=\int_{\widehat{\Gamma}}\mathsf{Tr}(\widehat{\phi}(\pi))d\mu(\pi).$

Henceforth we fix $\mu$ the Plancherel measure of $\widehat{\Gamma}$. Note
that by applying 3.3 to $\phi_{x}(y):=f(yx)$ and since
$\widehat{\phi}(\pi)=\pi(x)\widehat{f}(\pi)$, we obtain the Fourier inversion
formula

$f(x)=\int_{\widehat{\Gamma}}\mathsf{Tr}(\pi(x)\widehat{f}(\pi))d\mu(\pi)=\int_{\widehat{\Gamma}}\mathsf{Tr}(\widehat{f}(\pi)\pi(x))d\mu(\pi).$

An operator $T\in\mathcal{B}(\mathcal{H})$ is called Hilbert-Schmidt if
$TT^{*}$ is trace-class; we write

$\|T\|_{\mathsf{HS}(\mathcal{H})}^{2}:=\mathsf{Tr}(TT^{*}).$

The Fourier inversion formula applied to $\phi*\phi^{*}$, where
$\phi^{*}(x)=\overline{\phi(x^{-1})}$ yields the Plancherel formula below.

######  Theorem 3.4 (Thm. 1.8.5 in [9]).

Under the notation of 3.3, for $\phi\in\mathcal{S}(\Gamma)$, for every
strongly continuous $\pi\in\widehat{\Gamma}$, the operator
$\widehat{\phi}(\pi)$ is Hilbert-Schmidt, and
$\|\widehat{\phi}(\pi)\|_{\mathsf{HS}}$ is constant in the equivalence class
of $\pi$. Moreover
$\pi\mapsto\|\widehat{\phi}(\pi)\|_{\mathsf{HS}(\mathcal{H}_{\pi})}^{2}$ is
$\mu$-integrable and

$\|\phi\|_{L^{2}(\Gamma)}^{2}=\int_{\Gamma}|\phi(x)|^{2}dx=\int_{\widehat{\Gamma}}\|\widehat{\phi}(\pi)\|_{\mathsf{HS}(\mathcal{H}_{\pi})}^{2}d\mu(\pi).$

Observe that $\widehat{\phi}(\pi)$ is a bounded operator on
$\mathcal{H}_{\pi}$ for $\phi\in C_{c}(\Gamma)$. The Plancherel formula
provides a first approach to the nature of the group Fourier transform as an
operator, namely, $\mathcal{F}:C_{c}(\Gamma)\to L^{2}(\widehat{\Gamma})$ is an
isometry, where the direct integral

$L^{2}(\widehat{\Gamma}):=\int_{\widehat{\Gamma}}^{\oplus}\mathsf{HS}(\mathcal{H}_{\pi})d\mu(\pi)$

is the Hilbert space of the $\mu$-measurable fields of Hilbert-Schmidt
operators $A:\widehat{\Gamma}\ni\pi\mapsto
A_{\pi}\in\mathsf{HS}(\mathcal{H}_{\pi})$ for which

$\|A\|_{L^{2}(\widehat{\Gamma})}^{2}:=\int_{\widehat{\Gamma}}\|A_{\pi}\|_{\mathsf{HS}(\mathcal{H}_{\pi})}^{2}d\mu(\pi)<\infty.$
(3.13)

Here measurability means that

$\widehat{\Gamma}\ni\pi\mapsto\langle
A_{\pi}\varphi,\psi\rangle_{\mathcal{H}_{\pi}}\qquad\text{is measurable
}\forall\varphi,\psi\in\mathcal{H}_{\pi};$

for additional details on direct integrals and operators fields, see [9,
Appendix B] or [10, Section 7.4]. Like in the Euclidean case, the group
Fourier transform can be extended in an isometry $\mathcal{F}:L^{2}(\Gamma)\to
L^{2}(\widehat{\Gamma})$ which is surjective.

Now, in order to compute the Fourier transform of the Dirac delta
$\delta_{p},p\in\Gamma$, we need to define the group Fourier transform of a
measure. First, let $L^{\infty}(\widehat{\Gamma})$ be the space of
$\mu$-measurable fields $A:\widehat{\Gamma}\ni\pi\mapsto
A_{\pi}\in\mathcal{B}(\mathcal{H}_{\pi})$ such that

$\|A\|_{L^{\infty}(\widehat{\Gamma})}:=\sup_{\pi\in\widehat{\Gamma}}\|A_{\pi}\|_{\mathcal{B}(\mathcal{H}_{\pi})}<\infty,$

where the supremum is the essential supremum with respect to the Plancherel
measure $\mu$. The space $L^{\infty}(\widehat{\Gamma})$ together the pointwise
composition

$AB:\widehat{\Gamma}\ni\pi\mapsto
A_{\pi}B_{\pi}\in\mathcal{B}(\mathcal{H}_{\pi}),$

and the norm $\|\cdot\|_{L^{\infty}(\widehat{\Gamma})}$ is a von Neumann
algebra.

Let $\mathcal{B}_{L}(L^{2}(\Gamma))$ be the subspace of operators
$T\in\mathcal{B}(L^{2}(\Gamma))$ which are left-invariant, i.e., such that
$T\circ L_{x}=L_{x}\circ T$, for every $x\in\Gamma$, and where
$L_{x}(f)(y):=f(x^{-1}y)$ is the left-translation operator.

For each $\mu$-measurable field of uniformly bounded operators $A\in
L^{\infty}(\widehat{\Gamma})$, define the operator
$T_{A}\in\mathcal{B}_{L}(L^{2}(\Gamma))$ by

$T_{A}\phi:=\mathcal{F}^{-1}(A_{(\cdot)}\widehat{\phi}(\cdot)).$

It can be shown that the map $T:L^{\infty}(\widehat{\Gamma})\ni A\mapsto
T_{A}\in\mathcal{B}_{L}(L^{2}(\Gamma))$ is a von Neumann algebra isomorphism
and an isometry. Moreover, every operator $T\in\mathcal{B}_{L}(L^{2}(\Gamma))$
arises in this way, namely, there exists a unique (up to zero measure sets
with respect $\mu$) $\mu$-measurable field $A^{(T)}\in
L^{\infty}(\widehat{\Gamma})$ such that for every $\phi\in L^{2}(\Gamma)$:

$\widehat{T\phi}(\pi)=A^{(T)}_{\pi}\widehat{\phi}(\pi)\qquad\mu\text{-almost
everywhere}.$ (3.14)

Thus, we consider $\mathcal{K}(\Gamma)$ be the space of all the distributions
$\kappa\in(C_{c}^{\infty})^{\prime}(\Gamma)$ for which the convolution
operator $C_{c}^{\infty}(\Gamma)\ni f\mapsto f*\kappa$ extends to a bounded
operator $T_{\kappa}$ on $L^{2}(\Gamma)$. Thus, we define the Fourier
transform of the distribution $\kappa$ by

$\widehat{\kappa}(\pi):=A^{(T_{\kappa})}_{\pi},\qquad\text{where
}A^{(T_{\kappa})}\text{ is like in }\eqref{convdist}.$

Note that the convolution product between a function $f\in
C_{c}^{\infty}(\Gamma)$ and a distribution
$\kappa\in(C_{c}^{\infty}(\Gamma))^{\prime}$ is given by

$f*\kappa(x):=\langle\kappa,L_{x^{-1}}f^{*}\rangle.$

In other words, $\widehat{\kappa}$ is defined in such a way that

$\mathcal{F}(T_{\kappa}f)(\pi)=\widehat{\kappa}(\pi)\widehat{f}(\pi),\qquad
f\in L^{2}(\Gamma).$

Over $\mathcal{K}(\Gamma)$ we can define an involution
$\kappa^{*}(x):=\overline{\kappa(x^{-1})}$. For
$\kappa_{1},\kappa_{2}\in\mathcal{K}(\Gamma)$, consider the operators
$T_{\kappa_{1}},T_{\kappa_{2}}\in B_{L}(L^{2}(\Gamma))$ as above and denote by
$\kappa_{1}*\kappa_{2}$ its kernel. Also we can consider a norm in
$\mathcal{K}(\Gamma)$ via the formula:

$\|\kappa\|_{\mathcal{K}(\Gamma)}:=\|f\mapsto
f*\kappa\|_{\mathcal{B}(L^{2})(\Gamma)}.$

Hence the space $\mathcal{K}(\Gamma)$ together with the involution,
convolution product, and norm defined above is a von Neumann algebra
isomorphic to $\mathcal{B}_{L}(L^{2}(\Gamma))$. In addition, the group Fourier
transform $\mathcal{F}:\mathcal{K}(\Gamma)\to L^{\infty}(\widehat{\Gamma})$ is
an isometric isomorphism.

Denote by $\mathcal{M}(\Gamma)$ be the space of finite complex Borel measures
in $\Gamma$. Then we have the following inclusions:

$L^{1}(\Gamma)\subset\mathcal{M}(\Gamma)\subset\mathcal{K}(\Gamma);$

this allows us to define the group Fourier transform of a finite complex Borel
measure $\eta\in\mathcal{M}(\Gamma)$ by

$(\forall\pi\in\widehat{\Gamma}),\qquad\mathcal{F}(\eta)(\pi)=\widehat{\eta}(\pi):=\int_{\Gamma}\pi(x)d\eta(x),$
(3.15)

where the above integral is in the sense of Bochner.

##  4 Recovery of the discrete spectrum in nilpotent Lie groups

Let $\Gamma$ be an $d$-dimensional lcsc nilpotent Lie group, $H\subset\Gamma$
be an $r$-dimensional lattice, $r\leq d$, which means that $H$ is an
$r$-dimensional uniform subgroup of $\Gamma$, satisfying that
$\mathsf{exp}^{-1}(H)$ is an additive subgroup of
$\mathfrak{g}\cong\mathbb{R}^{d}$. Also, assume that $L\subset\Gamma$ is a
lattice containing $H$. From [7, Theorem 5.1.6], there exists a Mal’cev basis
$\\{X_{1},\ldots,X_{d}\\}$ of $\mathfrak{g}$ with rational structure constants
such that

$L=\mathsf{exp}(\mathbb{Z}X_{1})\cdot\ldots\cdot\mathsf{exp}(\mathbb{Z}X_{d})\subset\Gamma.$

For this basis, we have the natural identifications
$\Gamma\cong\phi^{-1}(\Gamma)=\mathbb{R}^{d}$ and
$L\cong\phi^{-1}(L)=\mathbb{Z}^{d}$ under the diffeomorphism
$\phi^{-1}:\Gamma\to\mathbb{R}^{d}$ defined in (3.2). Thus, without loss of
generality, we can assume that $\Gamma=(\mathbb{R}^{d},\cdot)$ and
$L=(\mathbb{Z}^{d},\cdot)$, where the law group is given by the Baker-
Campbell-Hausdorff formula. In addition, since $\mathsf{exp}^{-1}(H)$ is an
additive subgroup of $\mathfrak{g}$, after a rearrangement of the basis
elements if it is necessary, we have that there must exist
$q_{1},\ldots,q_{r}\in\mathbb{Z}\setminus\\{0\\}$ such that

$\mathsf{exp}^{-1}(H)=q_{1}^{-1}\mathbb{Z}X_{1}+\ldots+q_{r}^{-1}\mathbb{Z}X_{r}\subset\mathfrak{g}.$

Then, after applying the polynomial form of $\phi:\mathbb{R}^{d}\to\Gamma$
given by (3.3), we have that there are positive integers $N_{1},\ldots,N_{r}$
such that

$H=\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}\subset\mathbb{R}^{r},$ (4.1)

in which the identification is an group homomorphism when restricted to each
direct summand.

If $\mathsf{vol}_{r}$ denotes the Lebesgue measure in $\mathbb{R}^{r}$, and
since $\mathsf{vol}(B_{R}^{r})\sim R^{r}$ where $B_{R}^{r}:=[-R/2,R/2)^{r}$,
we have that there exists a positive constant $\lambda_{r}=\lambda_{r}(H)$
such that

$\left||H\cap
B_{R}^{r}|-\lambda_{r}\mathsf{vol}_{r}\left(B_{R}^{r}\right)\right|=o\left(\mathsf{vol}_{r}(B_{R}^{r})\right)=o(R^{r}),$
(4.2)

Write $\delta_{H}:=\sum_{p\in H}\delta_{p}$ and keep the notations of the
representation theory of lcsc nilpotent Lie groups from Section 3.3. Following
(3.15) and in view of (4.2), we define the (averaged) Fourier transform of $H$
by

$\mathcal{F}(\delta_{H})(\pi_{l}):=\lim_{R\to\infty}\frac{\mathcal{F}(\delta_{H\cap
B_{R}^{r}})(\pi_{l})}{R^{r}}=\lim_{R\to\infty}\frac{1}{R^{r}}\sum_{p\in H\cap
B_{R}^{r}}\pi_{l}(p);$ (4.3)

more precisely, for $\varphi\in\mathcal{H}_{l}\cong L^{2}(\mathbb{R}^{s})$ and
$\psi\in C_{c}(\mathbb{R}^{s})$, the following formula holds

$\langle\mathcal{F}(\delta_{H})(\pi_{l})\varphi,\psi\rangle_{L^{2}(\mathbb{R}^{s})}=\lim_{R\to\infty}\frac{1}{R^{r}}\sum_{p\in
H\cap B_{R}^{r}}\int_{\mathbb{R}^{s}}\varphi(px)\psi(x)dx.$ (4.4)

Let $\xi_{p},p\in H$ be i.i.d random vectors defined in a probability space
$(\Omega,\mathcal{T},\mathbb{P})$ with $\xi_{p}\sim\xi$ and let $H_{\xi}$ be
the realization set $\\{p\cdot\xi_{p}:\ p\in H\\}$. In this section, our goal
is to obtain the recovery of the Fourier Transform $\widehat{\delta_{H}}$ from
its random perturbations under suitable moment conditions over the
perturbations $\xi_{p}$.

######  Theorem 4.1.

Under the previous notations, assume that there is a positive number
$\varepsilon$ such that
$\mathbb{E}(|\mathsf{proj}_{r}(\xi)|^{r+\varepsilon})<\infty$, where
$\mathsf{proj}_{r}:\mathbb{R}^{d}\to\mathbb{R}^{r}$ is the orthogonal
projection onto the first $r$ coordinates. Then almost surely, for every
$l\in\mathfrak{g}^{*}$

$\mathcal{F}(\delta_{H_{\xi}})(\pi_{l})=\mathcal{F}(\delta_{H})(\pi_{l})\mathbb{E}[\pi_{l}(\xi)],$
(4.5)

where $\mathcal{F}(\delta_{H_{\xi}})$ stands for the limit
$\lim_{R\to\infty}\frac{1}{R^{r}}\mathcal{F}\left(\delta_{H_{\xi}\cap\left[-R/2,R/2\right)^{d}}\right)$.

In what follows, we are dedicated to the proof of 4.1. Let $M,N$ be positive
integers, $N_{i}|N$ for every $i=1,\ldots,r$, and consider the inclusions:

$N\mathbb{Z}\subset
N_{i}\mathbb{Z}\subset\frac{1}{M}\mathbb{Z},\qquad\text{for }1\leq i\leq r.$
(4.6)

By taking the quotient by $N\mathbb{Z}$, we find an embedding of the discrete
group

$H_{N}=\Gamma^{r}_{N}:=\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}/N\mathbb{Z}\cong\bigoplus_{i=1}^{r}\mathbb{Z}/\frac{N}{N_{i}}\mathbb{Z}$

into

$\Gamma_{M,N}^{d}:=\bigoplus_{i=1}^{d}\left(\frac{1}{M}\mathbb{Z}/N\mathbb{Z}\right),$

It should be noted that, by the rationality of $\mathbb{R}^{d}$ and
$\mathbb{R}^{r}$, the rescalings $N\mathbb{Z}^{d}$ and
$\frac{1}{M}\mathbb{Z}^{d}$ are still lattices in $\mathbb{R}^{d}$, and thus
$H_{N}\subset\Gamma_{M,N}^{d}$ are indeed finite groups.

To prove 4.1, we will ”discretize” the random perturbations
$p\cdot\xi_{p},p\in H$, restricted to $[-N/2,N/2)_{i=1}^{d}$ by approximating
them by group elements taking values in a finer and finer subgrid

$\frac{1}{M}\mathbb{Z}^{d}\cap\left[-\frac{N}{2},\frac{N}{2}\right).$

In the limit $M,N\to\infty$, after showing that the DFT converges (in a very
precise sense to be stated below) to the usual Fourier transform, we will get
the desired result as a consequence of an adequate quantitative recovery of
the DFT (see 4.7).

####  4.0.1 Discretizing $\xi$

With the inclusions $N\mathbb{Z}\subset
N_{i}\mathbb{Z}\subset\frac{1}{M}\mathbb{Z}\subset\mathfrak{g}$ in mind, for
$i=1,\ldots,r$, we restrict and discretize the maps
$\xi_{(\cdot)}:H\times\Omega\to\mathbb{R}^{d}$ defined immediately before 4.1,
to obtain $\xi^{(M,N)}_{(\cdot)}:H\times\Omega\to\Gamma^{d}_{M,N}$, as
follows. For $p\in H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}$ there
exists a unique $p^{\prime}\in H_{N}$ represented by $p$. Also, note that the
inclusion $\frac{1}{M}\mathbb{Z}^{d}\subset\mathbb{R}^{d}$ passes to the
quotient, and we get an inclusion

$\Gamma^{d}_{M,N}\subset\mathbb{R}^{d}/N\mathbb{Z}^{d}.$

Therefore for $p^{\prime}\in H_{N}$ we set
$\xi_{p^{\prime}}^{(M,N)}(\omega):=v\in\Gamma_{M,N}^{d}$ defined via the
property that the $N\mathbb{Z}^{d}$-quotient of $\xi_{p}(\omega)$, denoted by
$\xi_{p^{\prime}}^{(N)}(\omega)$, falls into the cube

$v\cdot\left[-\frac{1}{2M},\frac{1}{2M}\right)^{d}.$

With these notations, let $(H_{N})_{\xi^{(M,N)}}=\\{p\cdot\xi_{p}^{(M,N)}:\
p\in H_{N}\\}\subset\Gamma_{M,N}^{d}$.

The following claims are direct to prove and are left to the reader:

######  Claim 4.2.

$\\{\xi_{p}^{(M,N)}:\ p\in H_{N}\\}$ are independent.

######  Claim 4.3.

For each $p\in H_{N}$, $\xi_{p}^{(M,N)}(\omega)$ converges to
$\xi_{p}(\omega)$ when $M,N\to\infty$.

###  4.1 Discrete-to-continuum limits for irreducible representations in
nilpotent Lie groups

We start by considering a dual element $l\in\mathfrak{g}^{*}$, with rational
coefficients, being the representative of an orbit $\mathcal{O}_{l}$. Without
loss of generality, we write:

$l=\sum_{j=1}^{d}\frac{c_{j}}{m_{j}}X_{j}^{*}\qquad\text{with}\qquad
c_{j}\in\mathbb{Z}\text{ and }\mathsf{gcd}(c_{j},m_{j})=1\text{ for every
}j=1,\ldots,d,$ (4.7)

where some of the coefficients $c_{j}$ could be zero, and denote by
$\mathfrak{m}=\mathfrak{m}_{l}$ its polarizing subalgebra; also write
$K_{l}:=\mathsf{exp}(\mathfrak{m})$.

By 3.1, the map $\pi_{l}:\Gamma\to\mathcal{U}(\mathcal{H}_{l})$ given by

$\pi_{l}:=\mathsf{ind}_{K_{l}}^{\Gamma}(\chi_{l}),\quad\text{where}\qquad\chi_{l}(\mathsf{exp}(Y))=e^{2\pi
il(Y)},$ (4.8)

is a unitary irreducible representation of $\Gamma$ and all the elements of
$\widehat{\Gamma}$ arise in this way; also, we have that $\mathcal{H}_{l}$ is
isomorphic to $L^{2}(\mathbb{R}^{s})$, where $s=\mathsf{dim}(\Gamma/K_{l})$.
More precisely, the action of $\pi_{l}$ over $L^{2}(\mathbb{R}^{s})$ is
described as follows: since $K_{l}\subset\Gamma$ are Lie groups and $K_{l}$ is
closed and normal in $\Gamma$, we can consider
$\alpha:\Gamma/K_{l}\cong\mathbb{R}^{s}\to\Gamma$ be a continuous cross-
section for the canonical continuous quotient map $i:\Gamma\to\Gamma/K_{l}$,
like at the end of Section 3.2. Let $k:\Gamma\to K_{l}\cong\mathbb{R}^{d-s}$
and $t:\Gamma\to\alpha(\Gamma/K_{l})\cong\mathbb{R}^{s}$ be the continuous
functions given by the factorization

$x=k(x)t(x).$

Then, for $x,y\in\Gamma=(\mathbb{R}^{d},\cdot)$ and $f\in\mathcal{H}_{l}$ we
have that

$(\pi_{l}(x)f)(y)=f(xy)=f(k(xy)t(xy))=\chi_{l}(k)f(t)=e\left(\sum_{j=1}^{d-s}\frac{c_{j}k_{j}}{m_{j}}\right)f(t),$
(4.9)

with $e(x):=e^{2\pi ix}$, $t=t(xy)\in\alpha(\Gamma/K_{l})$ and where we
identify $k=k(xy)\in K_{l}\subset\mathbb{R}^{d}$ with the vector
$(k_{1},\ldots,k_{d-s})$. Thus, after identifying $\mathcal{H}_{l}\cong
L^{2}(\mathbb{R}^{s})$ through the isometry $\mathcal{H}_{l}\ni f\mapsto
f\circ\alpha\in L^{2}(\mathbb{R}^{s})$, we have that $\pi_{l}$ is an
irreducible unitary representation acting over $L^{2}(\mathbb{R}^{s})$, and
given by (4.9).

Since $K_{l}$ is rational, it is not difficult to see that the rescalings
$\frac{1}{M}\mathbb{Z}^{d-s}$ and $N\mathbb{Z}^{d-s}$, for $M,N\in\mathbb{N}$,
are still lattices in $K_{l}$. Moreover, since $K_{l}\cong\mathbb{R}^{d-s}$ is
a normal subgroup of $\mathbb{R}^{d}$ and the law group given by the
polynomial coordinates in (3.3) is assumed to have integer coefficients, we
obtain that $N\mathbb{Z}^{d-s}$ is normal in $\frac{1}{M}\mathbb{Z}^{d-s}$;
therefore, it makes sense to consider the groups $\Gamma_{M,N}^{d}$,
$\Gamma_{M,N}^{d-s}$ and $\Gamma_{M,N}^{s}$ as good approximants, in the
Gromov-Hausdorff sense, for $(\mathbb{R}^{d},\cdot)$,
$K_{l}\cong\mathbb{R}^{d-s}$ and
$\alpha(\mathbb{R}^{d}/K_{l})\cong\mathbb{R}^{s}$, respectively, for $M,N\gg
1$.

Hence, in the process of approximating $\pi_{l}$ by a suitable sequence of
irreducible unitary representations, we proceed as follows. Fix positive
integers $m|M$ and $N\in\mathbb{N}$ and consider

$c=(c_{1},\ldots,c_{d-s})\in(\mathbb{Z}/mM\mathbb{Z})^{d-s}\qquad\text{such
that}\qquad\mathsf{gcd}(c_{j},mM)=1\text{ for every }j=1,\ldots,d-s.$

Then we define the unitary representation $\pi_{M,N,m,c}$ of
$\Gamma_{M,N}^{d}$ by:

$(\pi_{M,N,m,c}(p)f)(q):=e\left(\sum_{j=1}^{d-s}\frac{c_{j}k_{j}(pq)}{m}\right)f(t(pq)),\qquad\text{where
}f\in\ell^{2}\left(\left(\frac{1}{M}\mathbb{Z}/m\mathbb{Z}\right)^{s}\right),$
(4.10)

where the vectors

$k(p)=(k_{1}(p),\ldots,k_{d-s}(p))\in\frac{1}{M}\mathbb{Z}^{d-s}\qquad\text{and}\qquad
t(p)\in\frac{1}{M}\mathbb{Z}^{s}$

in the formula (4.10), with $p\in\Gamma_{M,N}^{d}$, are taken modulo
$m\mathbb{Z}^{d-s}$ and $m\mathbb{Z}^{s}$, respectively.

From (4.10) we get that
$\pi_{M,N,m,c}:\Gamma_{M,N}^{d}\to\mathcal{U}(\ell^{2}(\Gamma_{M,m}^{s}))$ is
an irreducible unitary representation of $\Gamma_{M,N}^{d}$. Also observe
that, although the map

$\mathbb{Z}^{d-s}\times\mathbb{N}\ni(c,m)\mapsto\pi_{M,N,m,c}\in\widehat{\Gamma}_{M,N}^{d},$

where $m|M$ and the parameter $c$ in the index is taken modulo
$mM\mathbb{Z}^{d-s}$, probably is not exhaustive and there are many other
irreducible representations of $\Gamma_{M,N}^{d}$ which are not covered by the
formula (4.10), the irreducible representations of the form $\pi_{M,N,m,c}$
are sufficient to ”approximate” $\pi_{l}$; we develop this fact with more
details in Lemma 4.5 below.

Following Section 2.2, consider the Discrete Fourier Transform
$\mathcal{F}_{M,N}:\ell^{2}(\Gamma_{M,N}^{d})\to
L^{2}(\widehat{\Gamma}_{M,N}^{d})$. In particular, for
$f\in\ell^{2}(\Gamma_{M,N}^{d})$, the Fourier transform $\mathcal{F}_{M,N}(f)$
acts over an irreducible representation of the form $\pi_{M,N,m,c}$ like in
(4.10) as follows:

$\mathcal{F}_{M,N}(f)(\pi_{M,N,m,c})=\frac{1}{M^{d}N^{d}}\sum_{p\in\Gamma_{M,N}^{d}}f(p)\pi_{M,N,m,c}(p):\ell^{2}\left(\Gamma_{M,m}^{s}\right)\to\ell^{2}\left(\Gamma_{M,m}^{s}\right).$

To be able to pass information from $\mathcal{F}_{M,N}(\delta_{H_{N}})$ to
$\mathcal{F}(\delta_{X})$ we need to use an appropriate discrete-to-continuum
approximation, which we define next.

######  Remark 4.4 (periodization convention).

In order to compare functions on a discrete group $\Gamma_{M,N}^{s}$ with
functions on $\mathbb{R}^{s}$, we use the following convention: in the
following, given $M\in\mathbb{N}$ and a compactly supported function $\psi\in
C_{c}(\mathbb{R}^{s})$ with $\mathsf{supp}(\psi)\subset[-M/2,M/2)^{s}$, we
still denote its $M\mathbb{Z}^{s}$-periodization by $\psi$.

######  Definition 4.1.

We say that a sequence of linear operators $(T_{n})_{n\in\mathbb{N}}$, where
$T_{n}\in\mathcal{B}\left(\ell^{2}(\Gamma_{M_{n},m_{n}}^{s})\right)$ for
$n\geq 1$, with $M_{n},m_{n}\to\infty$, converges to a linear operator
$T\in\mathcal{B}(L^{2}(\mathbb{R}^{s}))$ if for every $\varphi,\psi\in
C_{c}(\mathbb{R}^{s})$ the following holds:

$\lim_{n\to\infty}\langle
T_{n}\varphi,\psi\rangle_{\ell^{2}\left(\Gamma_{M_{n},m_{n}}^{s}\right)}=\langle
T\varphi,\psi\rangle_{L^{2}(\mathbb{R}^{s})},$ (4.11)

where for a sufficiently large $n\geq 1$, we identify $\varphi,\psi$ with its
$m_{n}\mathbb{Z}^{s}$-periodizations like in Remark 4.4.

Now, for $H_{N}:=\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}/N\mathbb{Z}$, with
$N_{i}|N$ for all $i=1,\ldots,r$, consider the realization set
$(H_{N})_{\xi^{(M,N)}}=H_{\xi^{(M,N)}}:=\\{p\cdot\xi_{p}^{(M,N)}:p\in
H_{N}\\}$. The key claim to prove 4.1 is that the Fourier Transform of $X$ and
$X_{\xi}$ are weak limits (in the sense of 4.1) of the Discrete Fourier
Transforms $\mathcal{F}_{M,N}(\delta_{H})$ and
$\mathcal{F}_{M,N}(\delta_{H_{\xi^{(M,N)}}})$, respectively.

######  Lemma 4.5.

Let $l=\sum_{j=1}^{d}\lambda_{j}X_{j}^{*}\in\mathfrak{g}^{*}$, fix
$k\in\mathbb{N}$, and consider the irreducible unitary representation
$\pi_{l}$ acting over $\mathcal{H}_{l}\cong L^{2}(\mathbb{R}^{s})$ given by
the formula (4.9). For any pair of positive integers $m,N$, let

$\Gamma_{km,N}^{d}:=\left(\frac{1}{km}\mathbb{Z}/N\mathbb{Z}\right)^{d},\qquad
H:=\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}\subset\mathbb{R}^{d},\qquad
H_{N}:=\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}/N\mathbb{Z}\subset\Gamma_{km,N}^{d}.$

For each $m\geq 1$ let
$c_{m}:=(c_{m}^{(1)},\ldots,c_{m}^{(d-s)})\in(\mathbb{Z}/km^{2}\mathbb{Z})^{d-s}$
such that $c_{m}^{(j)}/m\to\lambda_{j}$ when $m\to\infty$, for every $1\leq
j\leq d-s$. Also consider the irreducible representations $\pi_{km,N,m,c_{m}}$
of $\Gamma_{km,N}^{d}$ like in (4.10). Then the following limit holds:

$\lim_{N\to\infty}\lim_{m\to\infty}(km)^{d-s}N^{d-r}\mathcal{F}_{km,N}(\delta_{H_{N}})(\pi_{km,N,m,c_{m}})=\mathcal{F}(\delta_{H})(\pi_{l})$
(4.12)

where the limit for $m\to\infty$ is taken in the sense of 4.1, and the weak
limit for $N\to\infty$ is in the classical sense.

###### Proof.

First we will show, in the sense of 4.1, that

$\begin{split}\lim_{m\to\infty}(km)^{d-s}N^{d-r}\mathcal{F}_{km,N}(\delta_{H})(\pi_{km,N,m,c_{m}})=\frac{1}{N^{r}}\mathcal{F}\left(\delta_{H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{r}}\right)(\pi_{l});\end{split}$
(4.13)

then, after taking $N\to\infty$ we will get the conclusion of Lemma 4.5. For
this, fix $N\in\mathbb{N}$ and consider two non-zero functions
$\varphi,\psi\in\mathcal{H}_{l}\cong L^{2}(\mathbb{R}^{s})$ supported on
$[-N/2,N/2)^{s}$; recall that by Remark 4.4, its
$N\mathbb{Z}^{s}$-periodizations are still denoted by $\varphi,\psi$. Then by
definition of the inner product
$\langle\cdot,\cdot\rangle_{\ell^{2}(\Gamma_{km,m}^{s})}$ and after the
identifications

$H_{N}\cong\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{r},\qquad\Gamma_{km,m}^{s}\cong\frac{1}{km}\mathbb{Z}^{s}\cap\left[-\frac{m}{2},\frac{m}{2}\right)^{s},$

we get that

$\begin{split}&(km)^{d-s}N^{d-r}\langle\mathcal{F}_{km,N}(\delta_{H_{N}})(\pi_{km,N,m,c_{m}})\varphi,\psi\rangle_{\ell^{2}(\Gamma_{km,m}^{s})}\\\
&=\frac{1}{(km)^{s}N^{r}}\sum_{p\in\Gamma_{km,m}^{s}}(\mathcal{F}_{km,N}(\delta_{H})(\pi_{km,m,c_{m}})\varphi)(p)\overline{\psi(p)}\\\
&=\frac{1}{(km)^{s}N^{r}}\sum_{p\in\frac{1}{km}\mathbb{Z}^{s}\cap\left[-\frac{m}{2},\frac{m}{2}\right)}\left\\{\sum_{\begin{subarray}{c}q\in\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}\\\
q\in\left[-\frac{N}{2},\frac{N}{2}\right)^{r}\end{subarray}}e\left(\sum_{j=1}^{d-s}\frac{c_{m}^{(j)}k_{j}(pq)}{m}\right)\varphi(t(pq))\overline{\psi(p)}\right\\}\\\
&=\frac{1}{N^{r}}\sum_{\begin{subarray}{c}q\in\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}\\\
q\in\left[-\frac{N}{2},\frac{N}{2}\right)^{r}\end{subarray}}\frac{1}{(km)^{s}}\left\\{\sum_{p\in\frac{1}{km}\mathbb{Z}^{s}\cap\left[-\frac{m}{2},\frac{m}{2}\right)}e\left(\sum_{j=1}^{d-s}\frac{c_{m}^{(j)}k_{j}(pq)}{m}\right)\varphi(t(pq))\overline{\psi(p)}\right\\}\\\
&\longrightarrow\frac{1}{N^{r}}\sum_{\begin{subarray}{c}q\in\bigoplus_{i=1}^{r}N_{i}\mathbb{Z}\\\
q\in\left[-\frac{N}{2},\frac{N}{2}\right)^{r}\end{subarray}}\int_{\left[-\frac{N}{2},\frac{N}{2}\right)^{s}}e\left(\sum_{j=1}^{d-s}\lambda_{j}k_{j}(xq)\right)\varphi(t(xq))\overline{\psi(x)}dx\\\
&=\frac{1}{N^{r}}\left\langle\mathcal{F}\left(\delta_{H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{r}}\right)(\pi_{l})\varphi,\psi\right\rangle_{L^{2}(\mathbb{R}^{s})},\end{split}$

where the limit taken for $m\to\infty$ in the sense of 4.1. Hence the the
conclusion of Lemma 4.5 follows by the definition of $\pi_{l}$ and
$\mathcal{F}(\delta_{H})$ after considering $\varphi,\psi\in
L^{2}(\mathbb{R}^{s})$, testing against $\varphi_{N},\psi_{N}\in
C_{c}(\mathbb{R}^{s})$ being the $N\mathbb{Z}^{s}$-periodizations of
$\varphi,\psi$ restricted to $\left[-\frac{N}{2},\frac{N}{2}\right)^{s}$,
respectively, and taking the limit when $N$ goes to $\infty$. ∎

######  Lemma 4.6.

Under the assumptions of Lemma 4.5, suppose there exists a positive number
$\varepsilon$ such that
$\mathbb{E}[|\mathsf{proj}_{r}(\xi)|^{r+\varepsilon}]<\infty$. Then the
following limit holds almost surely :

$\begin{split}\lim_{N\to\infty}\lim_{m\to\infty}(km)^{d-s}N^{d-r}\mathcal{F}_{km,N}\left(\delta_{H_{\xi^{(km,N)}}}\right)(\pi_{km,N,m,c_{m}})&=\mathcal{F}(\delta_{X_{\xi}})(\pi_{l}).\end{split}$
(4.14)

###### Proof.

Firstly consider the sets $A_{N},A_{N}^{\prime}\subset X$ given by

$\begin{split}A_{N}&=\left\\{p\in X\cap[-N/2,N/2)_{i=1}^{r}:\
p\cdot\xi_{p}\not\in[-N/2,N/2)_{i=1}^{d}\right\\}\\\
A_{N}^{\prime}&=\left\\{p\in X\setminus[-N/2,N/2)_{i=1}^{r}:\
p\cdot\xi_{p}\in[-N/2,N/2)_{i=1}^{d}\right\\}.\end{split}$

Since $\mathbb{E}[|\mathsf{proj}_{r}(\xi)|^{r+\varepsilon}]<\infty$, by the
same reasoning as Lemma 3.1 in [21] the following limits hold almost surely:

$\lim_{N\to\infty}\frac{|A_{N}|}{N^{r}}=\lim_{N\to\infty}\frac{|A_{N}^{\prime}|}{N^{r}}=0.$
(4.15)

Like in the limit in Lemma 4.5, given a positive integer $N$ and
$\varphi,\psi\in C_{c}(\mathbb{R}^{s})$ we need to estimate the value of:

$\begin{split}&\frac{1}{N^{r}}\left|\left\langle\mathcal{F}\left(\delta_{H_{\xi}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}\right)(\pi_{l})\varphi,\psi\right\rangle_{L^{2}(\mathbb{R}^{s})}-\frac{1}{(km)^{s}}\langle\mathcal{F}_{km,N}(\delta_{H_{\xi^{(km,N)}}})\varphi,\psi\rangle_{\ell^{2}\left(\Gamma_{km,m}^{s}\right)}\right|\\\
&=\frac{1}{N^{r}}\left|\int_{\mathbb{R}^{s}}\sum_{p\in
H_{\xi}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}e\left(\sum_{j=1}^{d-s}\lambda_{j}k_{j}\right)\varphi(t)\overline{\psi(x)}dx-\sum_{q\in\Gamma_{km,m}^{s}}\sum_{p\in
H_{\xi^{(km,N)}}}e\left(\sum_{j=1}^{d-s}\frac{c_{m}^{(j)}k_{j}}{m}\right)\varphi(t)\frac{\overline{\psi(q)}}{(km)^{s}}\right|,\end{split}$
(4.16)

where in the second line of (4.16), for the first term we have that
$k=k(px)=(k_{1},\ldots,k_{d-s}),t=t(px),p\in
H_{\xi}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}$, and for the second term
$k=k(pq),t=t(pq),p\in H_{\xi^{(km,N)}}$.

Now observe that

$\begin{split}&\int_{\mathbb{R}^{s}}\sum_{p\in
H_{\xi}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}e\left(\sum_{j=1}^{d-s}\lambda_{j}k_{j}(px)\right)\varphi(t(px))\overline{\psi(x)}dx\\\
&=\int_{\mathbb{R}^{s}}\sum_{p\in
H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}e\left(\sum_{j=1}^{d-s}\lambda_{j}k_{j}(p\cdot\xi_{p}\cdot
x)\right)\varphi(t(p\cdot\xi_{p}\cdot
x))\overline{\psi(x)}dx+S_{N}-S_{N}^{\prime},\end{split}$ (4.17)

where $S_{N}$ and $S_{N}^{\prime}$ are defined as the integral in the right-
hand side in (4.17), but with $p$ running over $A_{N}$ and $A_{N}^{\prime}$,
respectively.

Since the function $e(\cdot)=e^{-2\pi i(\cdot)}$ is bounded, and
$\varphi,\psi$ are compactly supported, then from (4.15) we have that almost
surely $\frac{S_{N}}{N^{r}},\frac{S_{N}^{\prime}}{N^{r}}\to 0$ when $N$ goes
to $\infty$. Then from 4.3, (4.17), (4.15), and by the triangle inequality,
given $\varepsilon>0$ there are $M_{0},N_{0}\in\mathbb{N}$ such that for every
$M\geq M_{0},N\geq N_{0}$ we get that

$\begin{split}\eqref{2ndlimitDFT}&\leq\frac{1}{N^{r}}\sum_{p\in
H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{r}}\left|\int_{\left[-\frac{N}{2},\frac{N}{2}\right)^{s}}e\left(\sum_{j=1}^{d-s}\lambda_{j}k(p\cdot\xi_{p}x)\right)\varphi(p\cdot\xi_{p}\cdot
x)\overline{\psi(x)}dx\right.\\\
&-\left.\sum_{\begin{subarray}{c}q\in\frac{1}{km}\mathbb{Z}^{s}\\\
q\in\left[-\frac{m}{2},\frac{m}{2}\right)^{s}\end{subarray}}e\left(\sum_{j=1}^{d-s}\frac{c_{m}^{(j)}k_{j}(p\cdot\xi_{p}q)}{m}\right)\varphi(p\cdot\xi_{p}^{(km,N)}\cdot
q)\frac{\overline{\psi(q)}}{(km)^{s}}\right|+\frac{|S_{N}|}{N^{r}}+\frac{|S_{N}^{\prime}|}{N^{r}}\\\
&\leq\frac{1}{N^{r}}\frac{\varepsilon
N^{r}}{3}+\frac{\varepsilon}{3}+\frac{\varepsilon}{3}=\varepsilon.\end{split}$

This concludes the proof of Lemma 4.6. ∎

The final step to prove Equation 4.5 is given by the next quantitative
recovery of the discrete Fourier spectrum, which is a direct consequence of
2.8.

######  Proposition 4.7.

Let $k\in N$ be fixed, $N,m\in\mathbb{N}$ and consider the finite groups
$\Gamma_{km,N}^{d}$ and $H_{N}$ as before. Let $\xi_{p}^{(km,N)},p\in H_{N}$
and $\varepsilon>0$ satisfying the hypotheses of 2.8. Then with probability at
least $1-\frac{C}{\varepsilon^{2}|H_{N}|}$, for some suitable positive
constant $C=C(H)$ there holds:

$\left\|\mathcal{F}_{km,N}(\delta_{H_{\xi^{(km,N)}}})-\mathcal{F}_{km,N}(\delta_{H})\mathbb{E}(\xi^{(km,N)}(\cdot))\right\|^{2}_{L^{2}(\widehat{\Gamma}_{km,N}^{d})}\leq\frac{1}{(km)^{2d}N^{2d-4r}}\left(\varepsilon+\frac{4C^{2}}{N^{r}}\right)\max_{\pi\in\widehat{\Gamma}_{km,N}^{d}}d_{\pi}.$
(4.18)

###### Proof.

This follows directly from 2.8 and from the fact that
$|H_{N}|=\frac{N^{r}}{N_{1}\ldots N_{r}}$ and
$|\Gamma_{km,N}^{d}|=(km)^{d}N^{d}$. ∎

To prove 4.1, we need a version of (4.18) in the sense of 4.1, namely

$M^{d-s}N^{d-r}\left(\mathcal{F}_{M,N}(\delta_{H_{\xi^{(M,N)}}})(\pi_{M,N,m,c})-\mathcal{F}_{M,N}(\delta_{H})\mathbb{E}\left(\pi_{M,N,m,c}\left(\xi^{(M,N)}\right)\right)\right)\longrightarrow
0,$ (4.19)

where $\pi_{M,N,m,c}$ is the finite dimensional representation having the form
of (4.10). This follows from (2.37), since for
$\varepsilon>\left(\frac{48C^{2}}{N^{r}}\right)^{1/2}$, with probability at
least $1-\frac{48C^{2}}{\varepsilon^{2}N^{r}}$ the following error bound holds
for every $\pi\in\widehat{\Gamma}_{km,N}^{d}$:

$\left\|\left(\mathcal{F}_{km,N}(\delta_{H_{\xi^{(km,N)}}})(\pi)-\mathcal{F}_{km,N}(\delta_{H})(\pi)\mathbb{E}(\pi(\xi^{(km,N)}))\right)e_{i}^{(\pi)}\right\|_{\Gamma_{km,N}^{s}}^{2}\leq\frac{N^{4r}}{(km)^{2d}N^{2d}}\left(\varepsilon+\frac{4C^{2}}{N^{r}}\right)d_{\pi}^{2},$
(4.20)

where $(e_{i}^{(\pi)})_{i=1}^{d_{\pi}}$ is an orthonormal basis for $V_{\pi}$.
Then after multiplying (4.20) by $M_{m}^{(d-s)/2}N^{(d-r)/2}$ with $M_{m}=km,\
\pi=\pi_{km,N,n,c}$ and $d_{\pi}=(km)^{s}m^{s}$ as before it follows that:

$\begin{split}&\left\|\left((km)^{d-s}N^{d-r}\mathcal{F}_{km,N}(\delta_{H_{\xi^{(km,N)}}})(\pi)-(km)^{d-s}N^{d-r}\mathcal{F}_{km,N}(\delta_{H})(\pi)\mathbb{E}(\pi(\xi^{(km,N)}))\right)e_{i}^{(\pi)}\right\|_{\Gamma_{km,N}^{s}}^{2}\\\
&\leq\frac{1}{k^{\frac{3d}{2}-s}N^{\frac{3d-9r}{2}}}\cdot\frac{1}{m^{\frac{3d}{2}-3s}}\left(\varepsilon+\frac{4C^{2}}{N^{r}}\right).\end{split}$
(4.21)

###### Proof of 4.1.

On the one hand, from Lemma 4.5 and Lemma 4.6, we have the following limit
holds in the sense of 4.1:

$\begin{split}&\lim_{m\to\infty}(km)^{d-s}N^{d-r}(\mathcal{F}_{km,N}(\delta_{H_{\xi^{(km,N)}}})(\pi_{km,N,m,c_{m}})-\mathcal{F}_{km,N}(\delta_{H})(\pi_{km,N,m,c_{m}})\mathbb{E}(\pi_{km,N,m,c}(\xi^{(km,N)})))\\\
&=\frac{1}{N^{r}}\mathcal{F}\left(\delta_{H_{\xi}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}\right)(\pi_{l})-\frac{1}{N^{r}}\mathcal{F}\left(\delta_{H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}\right)(\pi_{l})\mathbb{E}(\pi_{l}(\xi)).\end{split}$
(4.22)

On the other hand, from (4.21) and 4.2, for
$\varepsilon>\left(\frac{48C^{2}}{N^{r}}\right)^{1/2}$, with probability at
least $1-\frac{48C^{2}}{\varepsilon^{2}N^{r}}$ we have that

$\begin{split}(km)^{d-s}N^{d-r}(\mathcal{F}_{km,N}(\delta_{H_{\xi^{(km,N)}}})(\pi_{km,N,m,c})-\mathcal{F}_{km,N}(\delta_{H})(\pi_{km,N,m,c})\mathbb{E}(\pi_{km,N,m,c}(\xi^{(km,N)})))\to
0,\end{split}$ (4.23)

where again the limit for $m\to\infty$ is taken in the sense of 4.1, and we
use Lemma 3.2 in (4.21) to ensure that $3d/2-3s>0$. Therefore, by taking
$\varepsilon=\varepsilon_{N}\to 0$ such that $1/|H_{N}|\ll\varepsilon_{N}$ and
putting together (LABEL:limitproof1),(4.23), there holds that almost surely

$\lim_{N\to\infty}\frac{1}{N^{r}}\mathcal{F}\left(\delta_{H_{\xi}\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}\right)(\pi_{l})=\left(\lim_{N\to\infty}\frac{1}{N^{r}}\mathcal{F}\left(\delta_{H\cap\left[-\frac{N}{2},\frac{N}{2}\right)^{d}}\right)(\pi_{l})\right)\mathbb{E}(\pi_{l}(\xi)),$

where the limits are taken like in (4.3), and thus the conclusion of 4.1
follows. ∎

##  5 Examples

In this section, we illustrate with some examples the quantitative and almost
sure recovery given by 2.8 and 4.1. We mainly focus on the two canonical
instances of abelian and non-abelian groups, namely, the Euclidean space and
the Heisenberg group, where some explicit error bounds are provided. In
addition, in order to clarify the computations in the setting of general
finite groups, we decide to incorporate the corresponding ones for the
Euclidean case.

###  5.1 Finite abelian groups

We consider a discrete torus
$\mathbb{T}_{N}^{d}:=(\mathbb{Z}/N\mathbb{Z})^{d}$ where $N$ is not a prime
number, and its subset
$H=(M_{1}\mathbb{Z}/N\mathbb{Z})\oplus\ldots\oplus(M_{r}\mathbb{Z}/N\mathbb{Z})$
for $r\leq d$ and for some divisor $M_{i}|N$ with $1\leq i\leq r$. The general
case for the study in an ambient group
$(\mathbb{Z}/N_{1}\mathbb{Z})\oplus\ldots\oplus(\mathbb{Z}/N_{d}\mathbb{Z})$
instead $\mathbb{T}_{N}^{d}$ follows analogously; we restrict ourself to
$\mathbb{T}_{N}^{d}$ only to simplify notations and computations. We denote by
$\mathcal{F}:\ell^{2}(\mathbb{T}_{N}^{d})\to\ell^{2}(\mathbb{T}_{N}^{d})$ the
Discrete Fourier Transform (see [19, Ch. 2] for a treatment of the $d=1$ case,
and the case of general $d$ is an easy extension), given by

$\mathcal{F}(f)(k)=\widehat{f}(k):=\frac{1}{N^{d}}\sum_{p\in\mathbb{T}_{N}^{d}}e(p,k)f(p),\quad\text{where}\quad
e(p,k)=e_{N}(p,k):=e^{\frac{-2\pi}{N}i\langle p,k\rangle}.$ (5.1)

We apply (5.1) to the characteristic function

$\delta_{H}(p):=\left\\{\begin{array}[]{ll}1&\text{ if }p\in H,\\\\[5.69054pt]
0&\text{ else,}\end{array}\right.$

and then we see the characteristic function of the dual set $H^{*}$ of $H$
appears. Precisely, we have

$\begin{split}\widehat{\delta}_{H}=\frac{1}{N^{d-r}(M_{1}\ldots
M_{r})}\delta_{H^{*}},\quad\text{with }\quad
H^{*}&:=\\{k\in\mathbb{T}_{N}^{d}:\ \forall p\in H,\ k\cdot p\equiv 0\
(\text{mod }N)\\}\\\
&=\bigoplus_{i=1}^{r}\left(\frac{N}{M_{i}}\mathbb{Z}/N\mathbb{Z}\right)\oplus(\mathbb{Z}/N\mathbb{Z})^{d-r}.\end{split}$

Note that $|H|=\frac{N^{r}}{(M_{1}\ldots M_{r})}$ and $|H^{*}|=(M_{1}\ldots
M_{r})N^{d-r}$.

We then consider a random perturbation field of a configuration $H$ as above,
namely we fix a probability space $(\Omega,\mathcal{T},\mathbb{P})$ and define
a collection of $\mathbb{T}_{N}^{d}$-valued random variables
$\xi=(\xi_{p})_{p\in H}$, and the $\xi$-perturbed version of $H$ will be
denoted by $H_{\xi}=H_{\xi}(\omega):=\\{p+\xi_{p}(\omega):\ p\in H\\}$, which
is a random subset of $\mathbb{T}_{N}^{d}$, with $\omega\in\Omega$. We here
consider that $\xi_{p},p\in H$ are i.i.d. random variables.

The main quantitative recovery result in the framework of finite groups given
by 2.8 reads as follows.

######  Theorem 5.1.

Let $\xi_{p},p\in H$ be i.i.d. random variables with $\xi_{p}\sim\xi$ and
$C:=\sup_{\lambda\in\mathbb{T}_{N}^{d}}\mathsf{Var}[e(\xi,\lambda)]<\infty$,
and assume that $\varepsilon>\sqrt{\frac{72(M_{1}\ldots M_{r})}{N^{r}}}$ and
$\frac{N^{r}}{M_{1}\ldots M_{r}}>12$. Then with probability at least
$1-\frac{72(M_{1}\ldots M_{r})}{\varepsilon^{2}N^{r}}$ we have

$\max_{\lambda\in\mathbb{T}_{N}^{d}}\left|\widehat{\delta_{H_{\xi}}}(\lambda)-\mathbb{E}\left[e(\xi,\lambda)\right]\
\widehat{\delta_{H}}(\lambda)\right|\leq\frac{1}{|H^{*}|}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)^{\frac{1}{2}}.$
(5.2)

Observe that $C\leq 4$ due to the boundedness of $e(\cdot,\cdot)$. The regime
$(M_{1}\ldots M_{r})^{1/r}\ll N$ and the choice $\left(\frac{M_{1}\ldots
M_{r}}{N^{r}}\right)^{1/2}\ll\varepsilon\lesssim 1$ allow to obtain ”good
recovery with small error”, and is thus the most interesting for recovery
problems, in the following sense:

######  Corollary 5.2.

Consider a sequence of $N^{(n)},M^{(n)}_{1},\ldots M_{r}^{(n)}$ with
corresponding torii $\mathbb{T}_{N}^{d}=\mathbb{T}_{N^{(n)}}^{d}$ and subsets
$H=H^{(n)}$, and $\xi_{p}^{(n)},p\in H^{(n)}$ satisfying the hypotheses of
5.1, with $\xi_{p}^{(n)}$ independent from each other for different values of
$n$.

If we have

$(M_{1}^{(n)}\ldots M_{1}^{(n)})^{1/r}\ll N^{(n)},$

then almost surely

$\left\|\widehat{\delta_{H_{\xi^{(n)}}}}-\mathbb{E}[e(\xi^{(n)},\cdot)]\widehat{\delta_{H^{(n)}}}\right\|_{\ell_{\infty}(\mathbb{T}_{N}^{d})}\to
0.$ (5.3)

Given definition (5.1), it is natural in the pursuit of a bound (5.2) to
consider the functions $f,g:H\times\mathbb{T}_{N}^{d}\to\mathbb{C}$ defined by
as

$f(p,\lambda):=e(p,\lambda),\quad
g(p,\lambda):=\overline{e(\xi_{p},\lambda)-\mathbb{E}[e(\xi_{p},\lambda)]]}$
(5.4)

Note that $g$ is a random function, as it depends on the events $\omega$
through the $\xi_{p}$’s, whereas $f$ is deterministic. With definition (5.4)
we restate the desired bound (5.2) as

$\mathbb{P}\left\\{\frac{\left\|\langle
f_{\lambda},g_{\lambda}\rangle_{\ell^{2}(H)}\right\|_{\ell^{\infty}(\mathbb{T}_{N}^{d})}}{N^{d}}>\frac{1}{|H^{*}|}\left(\varepsilon+\frac{4C^{2}}{|H|}\right)^{1/2}\right\\}\leq\frac{72(M_{1}\ldots
M_{r})}{\varepsilon^{2}N^{r}},$ (5.5)

where we also use the notation
$f_{\lambda}:=f(\cdot,\lambda),g_{\lambda}:=g(\cdot,\lambda)$. We note that
$\langle
f_{\lambda},g_{\lambda}\rangle_{\ell^{2}(H)}=f_{\lambda}*g_{\lambda}(0)$, in
which we use the convolution of functions $\phi,\psi$ over
$\mathbb{T}_{N}^{d}$, defined by

$\phi*\psi(x):=\sum_{y\in\mathbb{T}_{N}^{d}}\phi(y)\psi(x-y).$

The function $f_{\lambda}*g_{\lambda}$ is supported on $H+H=H$ (the sum taking
place in the group $\mathbb{T}_{N}^{d}=(\mathbb{Z}/N\mathbb{Z})^{d}$) and
therefore

$\langle f_{\lambda},g_{\lambda}\rangle_{\ell^{2}(H)}=\sum_{y\in
H}f_{\lambda}*g_{\lambda}(y)\delta_{0}(y),$ (5.6)

where $\delta_{0}:=\delta_{H}$ for the special choice $H=\\{0\\}$.

We extend the functions $f_{\lambda},g_{\lambda}$ to
$F_{\lambda},G_{\lambda}:\mathbb{T}_{N}^{d}\times\mathbb{T}_{N}^{d}\to\mathbb{R}$
by zero outside $H$. Then we have

$\langle f_{\lambda},g_{\lambda}\rangle_{\ell^{2}(H)}=\langle
F_{\lambda},G_{\lambda}\rangle_{\ell^{2}(\mathbb{T}_{N}^{d})},\quad
F_{\lambda}*G_{\lambda}(y)=\delta_{H}(y)f_{\lambda}*g_{\lambda}(y).$

With our normalizations, we check that

$\displaystyle\widehat{F*G}(k)=\frac{1}{N^{d}}\sum_{q\in\mathbb{T}_{N}^{d}}(F*G)(q)e(q,k)$
$\displaystyle=$
$\displaystyle\frac{1}{N^{d}}\sum_{p,q\in\mathbb{T}_{N}^{d}}F(p)G(q-p)e(p,k)e(q-p,k)$
(5.7) $\displaystyle=$ $\displaystyle N^{d}\widehat{F}(k)\widehat{G}(k),$

and that

$\displaystyle\langle F,G\rangle_{\ell^{2}(\mathbb{T}^{d}_{N})}$
$\displaystyle=$
$\displaystyle\sum_{p\in\mathbb{T}_{N}^{d}}F(p)\overline{G(p)}$ (5.8)
$\displaystyle=$
$\displaystyle\frac{1}{N^{d}}\sum_{\begin{subarray}{c}p\in\mathbb{T}_{N}^{d}\\\
k\in\mathbb{T}_{N}^{d}\end{subarray}}F(p)e(p,k)\overline{G(p)e(p,k)}=\frac{1}{N^{d}}\sum_{\begin{subarray}{c}p,p^{\prime}\in\mathbb{T}_{N}^{d}\\\
k\in\mathbb{T}_{N}^{d}\end{subarray}}F(p)e(p,k)\overline{G(p^{\prime})e(p^{\prime},k)}$
$\displaystyle=$ $\displaystyle
N^{d}\sum_{k\in\mathbb{T}_{N}^{d}}\widehat{F}(k)\overline{\widehat{G}(k)}=N^{d}\langle\widehat{F},\widehat{G}\rangle_{\ell^{2}(\mathbb{T}^{d}_{N})}.$

Combining (5.6), (5.7) and (5.8), we get (observing that
$\widehat{\delta}_{0}\equiv N^{-d}$ by our definition)

$\langle f_{\lambda},g_{\lambda}\rangle_{\ell^{2}HX)}=\langle
F_{\lambda}*G_{\lambda},\delta_{0}\rangle_{\ell^{2}(\mathbb{T}_{N}^{d})}=N^{d}\sum_{x\in\mathbb{T}_{N}^{d}}\widehat{F_{\lambda}}(x)\overline{\widehat{G_{\lambda}}(x)}.$

Note that, for $x\in\mathbb{T}_{N}^{d}$:

$\widehat{F_{\lambda}}(x)=\frac{1}{N^{d}}\sum_{p\in
H}e(p,\lambda)e(p,x)=\widehat{\delta_{H}}(\lambda+x)=\frac{1}{N^{d-r}(M_{1}\ldots
M_{r})}\delta_{H^{*}-\lambda}(x).$ (5.9)

Therefore we get

$\langle f_{\lambda},g_{\lambda}\rangle_{\ell^{2}(H)}=\frac{N^{r}}{M_{1}\ldots
M_{r}}\sum_{y\in H^{*}-\lambda}\overline{\widehat{G}_{\lambda}(y)}.$ (5.10)

We note that the $r=d$ case of (5.10) simplifies continuum-case results such
as [17, Theorem A.4], or of [21, Appendix].

We now study the terms $\widehat{G_{\lambda}}(y)$ from (5.10). Denoting
$\widetilde{\varphi}(x):=\overline{\varphi(-x)}$, we rewrite the
autocorrelation $\gamma_{\lambda}$ of the random functions
$g(\lambda,q)=g_{\lambda}(q)$ as follows:

$\gamma_{\lambda}(q):=\frac{1}{|H|}G_{\lambda}*\widetilde{G_{\lambda}}(q)=\frac{M_{1}\ldots
M_{r}}{N^{r}}G_{\lambda}*\widetilde{G_{\lambda}}(q)=\left\\{\begin{array}[]{ll}\frac{M_{1}\ldots
M_{r}}{N^{r}}\sum_{p\in H}|g_{\lambda}(p)|^{2}&\text{ if }q=0,\\\\[8.53581pt]
\frac{M_{1}\ldots M_{r}}{N^{r}}\sum_{p\in
H}g_{\lambda}(p)\overline{g_{\lambda}(p+q)}&\text{ else.}\end{array}\right.$
(5.11)

From (5.7) we also obtain, for $x\in\mathbb{T}_{N}^{d}$,

$|\widehat{G_{\lambda}}|^{2}(x)=\frac{1}{N^{d}}\widehat{G_{\lambda}*\widetilde{G_{\lambda}}}(x)=\frac{1}{N^{d-r}(M_{1}\ldots
M_{r})}\widehat{\gamma_{\lambda}}(x).$ (5.12)

######  Proposition 5.3.

Let $\varepsilon>\left(\frac{72M_{1}\ldots M_{r}}{N^{r}}\right)^{1/2}$ and
assume that $\frac{N^{r}}{M_{1}\ldots M_{r}}>12$. Under our hypotheses on
$\xi$, with probability at least
$1-\frac{72}{\varepsilon^{2}}\frac{M_{1}\ldots M_{r}}{N^{r}}$ there holds

$\left|\gamma_{\lambda}(q)-\mathsf{Var}\left[e(\xi,\lambda)\right]\delta_{0}(q)\right|\leq\varepsilon.$
(5.13)

###### End of proof of 5.1:.

Consider the small probability event $\mathcal{A}_{\epsilon}$ for which (5.13)
holds. Conditioned on $\mathcal{A}_{\epsilon}^{c}$, we use the pointwise bound
of Proposition (5.3), triangular inequality over $H$ and (5.12), obtaining:

$\left|N^{d-r}(M_{1}\ldots
M_{r})|\widehat{G_{\lambda}}(x)|^{2}-\mathsf{Var}\left[e(\xi,\lambda)\right]\widehat{\delta_{0}}(x)\right|\leq\varepsilon\frac{|H|}{N^{d}}=\frac{\varepsilon}{N^{d-r}(M_{1}\ldots
M_{r})}.$ (5.14)

By substituting (5.14) in (5.10) we obtain the following estimation for
$\langle f_{\lambda},g_{\lambda}\rangle_{l^{2}(H)}$ valid in
$\Omega\setminus\mathcal{A}_{\epsilon}$:

$\displaystyle\frac{|\langle
f_{\lambda},g_{\lambda}\rangle_{\ell^{2}(H)}|}{N^{d}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{M_{1}\ldots M_{r}}\frac{1}{N^{d-r}}\sum_{y\in
H^{*}-\lambda}|\widehat{G_{\lambda}(y)}|$ $\displaystyle\leq$
$\displaystyle\frac{1}{N^{\frac{3}{2}(d-r)}(M_{1}\ldots
M_{r})^{\frac{3}{2}}}\sum_{y\in
H^{*}-\lambda}\left(\mathsf{Var}[e(\xi,\lambda)]\widehat{\delta_{0}}(y)+\frac{\varepsilon}{N^{d-r}(M_{1}\ldots
M_{r})}\right)^{1/2}$ $\displaystyle=$
$\displaystyle\frac{|H^{*}|}{N^{\frac{3}{2}(d-r)}(M_{1}\ldots
M_{r})^{\frac{3}{2}}}\left(\frac{\mathsf{Var}[e(\xi,\lambda)]}{N^{d}}+\frac{\varepsilon}{N^{d-r}(M_{1}\ldots
M_{r})}\right)^{1/2}$ $\displaystyle=$
$\displaystyle\frac{1}{N^{\frac{d-r}{2}}(M_{1}\dots
M_{r})^{\frac{3}{2}}}\left(\frac{\mathsf{Var}[e(\xi,\lambda)]}{N^{d}}+\frac{\varepsilon}{N^{d-r}(M_{1}\ldots
M_{r})}\right)^{1/2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{N^{d-r}(M_{1}\dots
M_{r})}\left(\varepsilon+\frac{CM_{1}\ldots M_{r}}{N^{r}}\right)^{1/2}$
$\displaystyle=$
$\displaystyle\frac{1}{|H^{*}|}\left(\varepsilon+\frac{C}{|H|}\right)^{1/2}.$

The claimed bound (5.5) follows directly, completing the proof of 5.1. ∎

###  5.2 Almost sure recovery of discrete subgroups in $\mathbb{R}^{d}$ as a
limit case

In this section, we see how the quantitative recovery given by 5.1 implies
almost sure recovery of the Fourier spectrum for discrete subgroups of
$\mathbb{R}^{d}$. By a ($r$-dimensional) discrete subgroup, we mean a subgroup
$X\leq\mathbb{R}^{d}$ of the form $H=v_{1}\mathbb{Z}\oplus\ldots\oplus
v_{r}\mathbb{Z}$, where $\\{v_{1},\ldots,v_{d}\\}$ is a basis of
$\mathbb{R}^{d}$ and $r\leq d$.

By a (complex) measure, we mean a linear functional on the set of compactly
supported $C_{c}(\mathbb{R}^{d})$ such that for every compact set
$K\subset\mathbb{R}^{d}$, there is a positive constant $M_{K}$ such that

$|\mu(f)|\leq M_{k}\|f\|_{\infty},$

for every $f\in C_{c}(\mathbb{R}^{d})$ supported on $K$, and where
$\|\cdot\|_{\infty}$ denotes the supremum norm in $C_{c}(\mathbb{R}^{d})$. By
the Riesz Representation Theorem, there is an equivalence between this
definition of measure and the classical measure-theoretic concept of regular
Radon measure.

Observe that in this case, the co-adjoint map $\mathsf{Ad}^{*}$ reduces to the
identity, and the space of coadjoint orbits $\mathfrak{g}/\mathsf{Ad}^{*}G$ is
equals to $\mathbb{R}^{d}$. Then, the elements of $\widehat{\mathbb{R}^{d}}$
correspond to the $1$-dimensional irreducible representations

$\chi_{\lambda}:=e^{-2\pi i\langle\cdot,\lambda\rangle},\qquad\text{where
}\lambda\in\mathbb{R}^{d},$

which act naturally over $L^{2}(\mathbb{R})$; thus, in our case we have that
$s:=\mathsf{dim}(G/K_{\lambda})=1$.

For a finite measure $\mu$ over $\mathbb{R}^{d}$, its Fourier transform is
defined by

$\widehat{\mu}(\lambda):=\int_{\mathbb{R}^{d}}e^{-2\pi i\langle
x,\lambda\rangle}d\mu(x),\qquad\text{for }\lambda\in\mathbb{R}^{d}.$

For $H$ being an $r$-dimensional discrete subgroup of $\mathbb{R}^{d}$, $r\leq
d$, we define its (averaged) Fourier transform $\mathcal{F}(\delta_{H})$ as
follows

$\begin{split}(\forall\lambda\in\mathbb{R}^{d}),\qquad\mathcal{F}(\delta_{H})(\lambda)&:=\lim_{R\to\infty}\frac{\mathcal{F}(\delta_{H\cap[-R/2,R/2)^{d}})(\lambda)}{R^{d}}=\lim_{R\to\infty}\frac{1}{R^{r}}\sum_{p\in
H\cap[-R/2,R/2)^{d}}e^{-2\pi i\langle p,\lambda\rangle}\end{split}$ (5.15)

For an $r$-dimensional discrete subgroup $H$, consider i.i.d random vectors
$(\xi_{p})_{p\in H}$ defined in a probability space
$(\Omega,\mathcal{T},\mathbb{P})$, and the corresponding realization set
$X_{\xi}=\\{p+\xi_{p}:\ p\in H\\}$. We define the Fourier Transform of
$H_{\xi}$ in duality with $C_{c}(\mathbb{R}^{d})$ like in (5.15) by

$\mathcal{F}\left(\delta_{H_{\xi}}\right):=\lim_{R\to\infty}\frac{1}{R^{r}}\mathcal{F}\left(\delta_{H_{\xi}\cap\left[-R/2,R/2\right)^{d}}\right).$
(5.16)

Thus, in this section our main result is the almost sure recovery of $H$ from
its random perturbations under suitable moment conditions of the perturbations
$\xi_{p}$.

######  Theorem 5.4.

Assume that $1\leq r\leq d$, that $H\subset\mathbb{R}^{d}$ is an
$r$-dimensional discrete subgroup, and $\varepsilon>0$ is such that
$\mathbb{E}[|\pi_{r}(\xi)|^{r+\varepsilon}]<\infty$, where
$\pi_{r}:\mathbb{R}^{d}\to\mathbb{R}^{r}$ is the orthogonal projection onto
the first $r$ coordinates. Then almost surely, there holds:

$\mathcal{F}\left(\delta_{H_{\xi}}\right)=\mathbb{E}\left(e^{-2\pi
i\langle\xi,\cdot\rangle}\right)\mathcal{F}\left(\delta_{H}\right).$

We will restrict ourselves to the case
$H=\mathbb{Z}^{r}\subset\mathbb{R}^{d}$, $r\leq d$; the case of more general
discrete subgroups $H=v_{1}\mathbb{Z}\oplus\ldots\oplus v_{r}\mathbb{Z}$ then
follows by a change of basis via a suitable $A\in GL(\mathbb{R}^{d})$ that
sends $\\{e_{1}\ldots,e_{r}\\}$ to $\\{v_{1},\ldots v_{r}\\}$, and is left to
the reader.

For $M,N$ being positive integers, consider the torus

$H_{N}=\mathbb{T}^{r}_{N}:=(\mathbb{Z}/N\mathbb{Z})^{r}\subset\mathbb{T}_{M,N}^{d}:=\left(\left(\frac{1}{M}\mathbb{Z}\right)/N\mathbb{Z}\right)^{d}.$

####  5.2.1 Rescaled DFT

Now we check how the above rescaling is inherited to the discrete Fourier
transforms of interest to us. Consider the torii
$\mathbb{T}_{MN}^{d}:=(\mathbb{Z}/MN\mathbb{Z})^{d}$ and
$\widetilde{H}:=(M\mathbb{Z}/NM\mathbb{Z})^{r}\simeq(M\mathbb{Z}/NM\mathbb{Z})^{r}\times\\{0\\}^{d-r}\subseteq\mathbb{T}_{MN}^{d}$
first. Then $NM,M$ plays the role of $N,M$ of the previous section. In this
case
$\widetilde{H}^{*}=(N\mathbb{Z}/NM\mathbb{Z})^{r}\oplus(\mathbb{Z}/MN\mathbb{Z})^{d-r}$,
and we have $|\widetilde{H}|=N^{r},|\widetilde{H}^{*}|=M^{d}N^{d-r}$. For the
case $r=d$, the continuum non-compact version of the problem is that in which
$\widetilde{H}$ is replaced by a lattice $\Lambda\subset\mathbb{R}^{d}$, and
$\widetilde{H^{*}}$ is replaced by its dual lattice $\Lambda^{*}$, whose
density satisfies $\mathrm{dens}(\Lambda)\mathrm{dens}(\Lambda^{*})=1$.

In the setting of Section 5.1 (with the roles of $N,M_{1},\dots,M_{r}$
replaced here by $MN,M,\dots,M$), the DFT of
$f:\mathbb{T}_{MN}^{d}\to\mathbb{C}$ is given by (5.1) as

$\mathcal{F}_{MN}(f)(k):=\frac{1}{M^{d}N^{d}}\sum_{p\in\mathbb{T}_{MN}^{d}}e^{\frac{-2\pi
i}{MN}p\cdot k}f(p)\qquad\text{for }k\in\mathbb{T}_{MN}^{d},$ (5.17)

For algebraic considerations (i.e., without including metric aspects),
definition (5.17) would suffice. However, our study is based on the fact that,
as $M\to\infty$, the metric spaces $\mathbb{T}^{d}_{M,N}$ approximate better
and better $\mathbb{R}^{d}/N\mathbb{Z}^{d}$ (since $\mathbb{T}^{d}_{M,N}$ is a
$1/M$-net of $\mathbb{R}^{d}/N\mathbb{Z}^{d}$, these spaces converge to each
other in Gromov-Hausdorff sense, for example). Thus we are led to define

$e_{M,N}(p,k):=e^{-\frac{2\pi i}{N}\langle p,k\rangle},\quad
p\in\mathbb{T}^{d}_{M,N}.$ (5.18)

At the level of Fourier-dual spaces, we observe that the compact group
$\mathbb{R}^{d}/N\mathbb{Z}^{d}$ is naturally in duality with
$\frac{1}{N}\mathbb{Z}^{d}$: functions over $\mathbb{R}^{d}/N\mathbb{Z}^{d}$
correspond to $N\mathbb{Z}^{d}$-periodic functions over $\mathbb{R}^{d}$, and
the smallest frequency that can be sampled via these functions scales like
$1/N$. In other words, the Pontryagin dual of $\mathbb{T}_{M,N}^{d}$ can be
identified with $\mathbb{T}_{N,M}^{d}$, where the family of characters is
given by $e_{M,N}(\cdot,Nk^{\prime}),\ k^{\prime}\in\mathbb{T}_{N,M}^{d}$. We
then use the definition
$\mathcal{F}_{M,N}(f)=\mathcal{F}_{MN}\left(f\circ(\mathsf{dil}_{1/M})^{-1}\right)\circ\mathsf{dil}_{1/N}$,
where for $a>0$ the map $\mathsf{dil}_{a}:\mathbb{T}^{d}_{MN}\to
a\mathbb{T}^{d}_{MN}$ is defined by $\mathsf{dil}_{a}(p)=ap$. Explicitly, we
have then

$\mathcal{F}_{M,N}:\ell^{2}(\mathbb{T}^{d}_{M,N})\to\ell^{2}(\mathbb{T}^{d}_{N,M}),\quad\mathcal{F}_{M,N}(f)(k^{\prime}):=\frac{1}{M^{d}N^{d}}\sum_{p\in\mathbb{T}^{d}_{M,N}}e_{M,N}(p,Nk^{\prime})f(p).$
(5.19)

If $r=d$, one can check that
$(\mathcal{F}_{M,N})^{-1}(g)=\mathcal{F}_{N,M}(\widetilde{g})$ where
$\widetilde{g}(k):=\overline{g(-k)}$.

As we showed before, 5.4 is a consequence of the fact that the Fourier
transforms of the Dirac measures supported on $H=\mathbb{Z}^{r}$ and
$H_{\xi}\mathbb{Z}^{r}_{\xi}$ correspond to the (normalized) limit of the DFT
of $H_{N}$ and $H_{\xi^{(M,N)}}$. Lemma 5.5 below is the adapted version of
Lemma 4.5 in the Euclidean setting, where $s=\mathsf{dim}(G/K_{l})=1$, with
the definitions of Section 3.1.

######  Lemma 5.5.

Let $(\xi_{p})_{p\in\mathbb{Z}^{r}}$ be i.i.d random vectors and let
$\varepsilon>0$ be such that
$\mathbb{E}[|\pi_{r}(\xi)|^{r+\varepsilon}]<\infty$, where
$\pi_{r}:\mathbb{R}^{d}\to\mathbb{R}^{r}$ is the orthogonal projection onto
the first $r$ coordinates. Let
$H_{N}:=(\mathbb{Z}/N\mathbb{Z})^{r}\subset\mathbb{T}^{d}_{M,N}$ and let
$\xi^{(M,N)}$ be as in Subsection 4.0.1. Then almost surely, there holds:

$\begin{split}\lim_{N\to\infty}\lim_{M\to\infty}M^{d-1}N^{d-r}\mathcal{F}_{M,N}(\delta_{H_{N}})=\mathcal{F}(\delta_{\mathbb{Z}^{r}})\
\text{ and }\
\lim_{N\to\infty}\lim_{M\to\infty}M^{d-1}N^{d-r}\mathcal{F}_{M,N}\left(\delta_{H_{\xi}}\right)=\mathcal{F}(\delta_{\mathbb{Z}^{r}_{\xi}}),\end{split}$
(5.20)

where the limit for $M\to\infty$ is taken in the sense of 4.1, and the limit
with respect to $N\to\infty$ is in the classical sense.

To prove the recovery result of 5.4, we re-express 5.1 and Corollary 5.2 for
the torii $\mathbb{T}_{M,N}^{d}$ and $X=\mathbb{T}_{N}^{r}$. To do this we
replace $(N,M_{1},\dots,M_{r})\mapsto(NM,M,\dots,M)$ obtaining the following
result:

######  Proposition 5.6.

Let $\xi_{p},p\in H_{N}=\mathbb{T}_{N}^{r}$ be i.i.d. random variables with
$\xi_{p}\sim\xi$ satisfying
$C:=\max_{\lambda\in\mathbb{T}^{d}_{N,M}}\mathsf{Var}[e(\xi,\lambda)]<\infty$,
and assume that $N^{r}>12$ and $\varepsilon>\sqrt{\frac{72}{N^{r}}}$. Then
with probability at least $1-\frac{72}{\varepsilon^{2}N^{r}}$ we have

$\max_{\lambda\in\mathbb{T}_{N,M}^{d}}\left|\mathcal{F}_{M,N}(\delta_{(H_{N})_{\xi}})(\lambda)-\mathbb{E}\left[e(\xi,\lambda)\right]\
\mathcal{F}_{M,N}(\delta_{H_{N}})(\lambda)\right|\leq\frac{1}{M^{d}N^{d-r}}\sqrt{\varepsilon+\frac{4C^{2}}{N^{r}}}.$
(5.21)

###### Proof of 5.4:.

Following Lemma 5.5, we need an estimation for the error in 5.6, after
multiplying the left-hand side of (5.5) by $M^{d-1}N^{d-r}$. Let $\xi^{(M,N)}$
be as in the Subsection 4.0.1 and $\varepsilon>\sqrt{\frac{72}{N^{r}}}$ with
$N^{r}>12$. From (5.5), with probability at least
$1-\frac{72}{\varepsilon^{2}N^{r}}$ we get:

$\max_{\lambda\in\mathbb{T}_{N,M}^{d}}\left|M^{d-1}N^{d-r}\left(\mathcal{F}_{M,N}(\delta_{H_{\xi^{(M,N)}}})(\lambda)-\mathbb{E}\left[e(\xi^{(M,N)},\lambda)\right]\
\mathcal{F}_{M,N}(\delta_{H_{N}})(\lambda)\right)\right|\leq\frac{1}{M}\sqrt{\varepsilon+\frac{4C^{2}}{N^{r}}},$
(5.22)

where we use the fact that
$\max_{\lambda\in\mathbb{T}_{N,M}^{d}}\mathsf{Var}[e(\xi^{(M,N)},\lambda)]\leq
4$. We now bound (5.22) in the regime where $\varepsilon\to 0$ and
$M,N\to\infty$. We require $N^{-r/2}\ll\varepsilon$, so that the event (5.22)
has probability tending to $1$. Hence, by letting $M\to\infty$ and
$\varepsilon\to 0$ such that $\varepsilon N^{r}\gg 1$ we get that almost
surely

$\left\|M^{d-1}N^{d-r}\left(\mathcal{F}_{M,N}(\delta_{H_{\xi^{(M,N)}}})-\mathbb{E}[e(\xi^{(M,N)},\cdot)]\mathcal{F}_{M,N}(\delta_{H_{N}})\right)\right\|_{\ell_{\infty}(\mathbb{T}_{N,M}^{d})}\to
0.$ (5.23)

5.4 follows from it and Lemma 5.5 via triangle inequality and from 4.3. ∎

###  5.3 The Heisenberg group case

In this section, for our purposes we consider the (polarized) Heisenberg group
$\Gamma$ being the set $\mathbb{R}^{3}$ with the group law

$(x,y,z)\cdot(u,v,w):=\left(x+u,y+v,z+w+xv\right).$ (5.24)

Similarly, for a number field $F$, we define $\Gamma(F):=\\{(x,y,z)\in\Gamma:\
x,y,z\in F\\}$, with group operation as in (5.24). We consider especially
$H_{N}=\Gamma(\mathbb{Z}/N\mathbb{Z})$ as the finite Heisenberg group with
coefficients in the field $\mathbb{Z}/N\mathbb{Z}$, with sum and product
operations as usual; observe that
$H_{N}\cong\Gamma(\mathbb{Z})/\Gamma(N\mathbb{Z})$. Note that the Lebesgue
measure in $\mathbb{R}^{3}$ is the Haar measure in $\Gamma$. Throughout this
section, for $R>0$ we denote

$B_{R}:=[-R/2,R/2)^{3}.$

Consider the usual Heisenberg group $\Gamma^{\prime}=(\mathbb{R}^{3},\odot)$
with the group operation given by

$(x,y,z)\odot(u,v,w):=\left(x+u,y+v,z+w+\frac{1}{2}(xv-yu)\right).$ (5.25)

The Fourier Analysis in $\Gamma^{\prime}$ is well-understood. Indeed, denote
by $\mathcal{U}(L^{2}(\mathbb{R}))$ be the group of unitary operators acting
on $L^{2}(\mathbb{R})$. By the Stone-von Neumann Theorem (see, for instance
[10, Theorem 6.49]), all the irreducible unitary representations of
$\Gamma^{\prime}$ (under equivalence) are determined by one of the following:

  1. 1.

The representations
$\pi^{\prime}_{\lambda}:\Gamma^{\prime}\to\mathcal{U}(L^{2}(\mathbb{R}))$,
$\lambda\neq 0$, where for $(x,y,z)\in\Gamma^{\prime}$, the operator
$\pi^{\prime}_{\lambda}(x,y,z)$ acts on a function $\varphi\in
L^{2}(\mathbb{R})$ via norm-preserving operations, explicitly given by the
formula

$\pi^{\prime}_{\lambda}(x,y,z)\varphi(u):=e^{2\pi i\lambda z+\pi i\lambda
xy}e^{2\pi i\lambda yu}\varphi(u+x),\qquad u\in\mathbb{R}.$

  2. 2.

The 1-dimensional irreducible unitary representations
$\pi^{\prime}_{\alpha,\beta}:\Gamma^{\prime}\to\mathbb{C}$,
$\alpha,\beta\in\mathbb{R}$, given by

$\pi^{\prime}_{\alpha,\beta}(x,y,z)=e^{2\pi i(\alpha x+\beta y)}.$

The connection between $\Gamma^{\prime}$ and $\Gamma$ is given by the
isomorphism $\phi:\Gamma^{\prime}\to\Gamma$:

$\phi(x,y,z):=\left(x,y,z+\frac{1}{2}xy\right).$