# Function Reconstruction Using Rank-1 Lattices and Lower Sets

Moulay Abdellah Chkifa  and  Abdelqoddous Moussa

###### Abstract.

Our study focuses on constructing optimal rank-1 lattices that enable exact
integration and reconstruction of functions in the Chebyshev space, based on
finite index sets. We introduce novel theoretical lower bounds on the minimum
number of integrands needed for reconstruction, show equivalence between
different plans for reconstruction under certain conditions and propose an
innovative algorithm for generating the optimal generator vector of rank-1
lattices. By leveraging the inherent structure of the set of interpolators,
our approach ensures admissibility conditions through exhaustive search and
verification, outperforming existing methods in terms of computation time and
memory usage. Numerical experiments validate the efficiency and practical
applicability of our algorithm.

###### Key words and phrases:

Rank-1 lattices, Function reconstruction, Chebyshev space, Cubature rules,
Component-by-component (CBC) strategies, Deterministic algorithms,
Approximation theory

###### 2020 Mathematics Subject Classification:

41A10 , 41A63, 65D32, 42A15, 65D15

<EMAIL_ADDRESS>
College of Computing, University Mohammed VI Polytechnic, Morocco.
<EMAIL_ADDRESS>
##  1\. Introduction

In the field of function integration and reconstruction, rank-1 lattices
framework plays a crucial role. Typically, we consider the approximation of
the $d$-dimensional integral over the unit cube $[0,1]^{d}$

(1.1)
$I_{d}(f)=\int_{[0,1]^{d}}f({\boldsymbol{x}})\mathrm{d}{\boldsymbol{x}},$

or the approximation of the $d$-variates function ${\boldsymbol{x}}\mapsto
f({\boldsymbol{x}})$, by a equal weight rank-1 lattice rules

$Q_{n,{\boldsymbol{z}}}(f)=\frac{1}{n}\sum_{i=0}^{n-1}f({\boldsymbol{t}}_{i}),\quad\quad\quad\quad{\boldsymbol{x}}\mapsto\sum_{{\boldsymbol{k}}\in\Lambda}Q_{n,{\boldsymbol{z}}}(f\alpha_{\boldsymbol{k}})\alpha_{\boldsymbol{k}}({\boldsymbol{x}})$

where
$\mathcal{L}=\left\\{{\boldsymbol{t}}_{i}:=\left\\{\frac{i{\boldsymbol{z}}}{n}\right\\},i=0,\dots,n-1\right\\}\subset[0,1]^{d}$
is the rank-1 lattice generated by ${\boldsymbol{z}}/n$ with
${\boldsymbol{z}}\in\mathbb{Z}^{d}$ and
$\\{\alpha_{\boldsymbol{k}}\\}_{{\boldsymbol{k}}\in\Lambda}$ a basis of
multivariate algebraic or trigonometric polynomials. In this article, we are
particularly interested in specific spaces of multivariate algebraic or
trigonometric polynomials $f$, indexed in the so-called lower sets which are
inherent in approximation theory. Our primary focus in this paper is the fast
construction of optimal rank-1 lattices, providing through the adequate
cubature rules, the exact integration or reconstruction of functions belonging
to these spaces. This involves determining the optimal number $n$ of nodes
${\boldsymbol{t}}_{i}$ for the cubature rule and their optimal distribution.

In [cools2010constructing], the authors introduced weighted degrees of
exactness and considered anisotropic integrands. To address the exponential
growth of required integration points with increasing dimension, they present
two algorithms for constructing lattice rules. The first one ensures a
prescribed weighted degree of exactness, while the second maximizes the degree
at each step. The authors provide theoretical foundations and numerical
illustrations to demonstrate the effectiveness of these methods in achieving
optimal convergence rates in weighted Korobov spaces [sloan2001].

A key challenge in the domain of rank-1 lattices is constructing the optimal
generator vector and determining the appropriate number of integrands (sample
size) that satisfy the admissibility conditions for exact integration or
reconstruction of functions on a space. The construction of the optimal rank-1
lattice typically employs component-by-component (CBC) strategies. These CBC
strategies significantly reduce the search space, providing efficient
reconstruction with minimal impact on approximation errors
[Kmmerer2014ReconstructingMT]. Rank-1 lattice sampling, coupled with CBC
constructions, has gained attention due to its advantageous approximation
properties. The efficient use of one-dimensional Fast Fourier Transforms for
function reconstruction from sampled points further enhances its appeal
[Kuo2008LatticeRA].

Recent non-probabilistic algorithms exhibit polynomial runtime concerning both
spatial dimension and lattice size [rank1]. Furthermore, [Kammerer2020AFP]
presents a linearly complex algorithm for constructing rank-1 lattices that
ensures exact integration, demonstrating high efficiency for all functions
within a specified truncated Fourier space. Additionally, the authors
introduce a probabilistic version of a CBC construction algorithm for rank-1
lattices, improving the computational efficiency of an established
deterministic approach. This probabilistic algorithm effectively determines
reconstructing rank-1 lattices with high probability, showing efficiency in
various scenarios, including the construction of exactly integrating rank-1
lattices.

In [gross2021deterministic], a deterministic algorithm is presented for
generating multiple rank-1 lattices, specifically designed for approximating
periodic functions with multiple variables. This algorithm decomposes a single
rank-1 lattice into smaller ones, streamlining the accurate and effective
reconstruction of trigonometric polynomials. The resulting multiple rank-1
lattices are characterized by theoretical limits on sampling points and
demonstrate notable computational efficiency.

##  2\. Main Results

This paper addresses the challenge of constructing the optimal generator
vector and determining the appropriate number of integrands for the rank-1
lattice both theoretically and numerically.

The primary contribution lies in introducing new theoretical sharp lower
bounds on the minimal number of integrands needed for reconstruction,
theoretical optimal choice of the rank-1 lattice for some geometry,
equivalence between different reconstruction plans and developing a novel
algorithm for constructing the corresponding optimal generator vector of the
rank-1 lattice facilitating the reconstruction of a given set of interpolants.
We leverage the inherent lower structure of the set of interpolants to
optimize our approach, breaking down the problem into more manageable
components. By employing exhaustive search techniques and meticulous
verification steps, we ensure the fulfillment of admissibility conditions.
Notably, our algorithm surpasses existing methods in computation time and
memory usage, making it exceptionally suitable for handling lower sets at
larger scales.

Our paper is organized as follows, in the preliminary section 3, we provide an
overview, primarily drawing from [rank1], of the latest advancements in
constructing rank-1 lattices and cubature rules for integration and function
reconstruction. We focus on a broad finite index set and examine results
pertaining to Fourier, cosine, and Chebyshev functional spaces. These findings
encompass necessary and sufficient conditions regarding the number and
distribution of integrands for exact integration and function reconstruction,
alongside theoretical upper bounds on their size. Leveraging the
interconnections among the three spaces, known results for integration and
reconstruction in Fourier spaces are adapted.

In Section 4, we establish lower bounds on the number of integrands for
various approximation plans to achieve exact reconstruction, accompanied by
examples illustrating the sharpness of these bounds for each plan.
Additionally, we provide theoretical optimal choices of the rank-1 lattice for
some useful sets of interpolants.

In Section 5, we introduce the lower set structure and its inherent
properties, proving an inequality characterizing lower sets. We also introduce
a new parameter of lower sets, namely, extremal elements, which proves useful
in providing sufficient conditions to establish links between reconstructions
under different plans for useful sets. We demonstrate when these
reconstructions are equivalent, which is particularly practical for running
algorithms with fewer constraints, as illustrated in Section 6.

Section 7 presents an efficient numerical algorithm for finding near-optimal
values of the number of integrands. We offer an in-depth exploration of our
algorithm, outlining the steps involved in searching for the optimal choice of
the rank-1 lattice parameters. We intricately detail the verification process,
emphasizing the pivotal role played by the lower set structure. Furthermore,
we validate the efficiency of our algorithm through a complexity analysis of
our algorithms in Section 8.1 and experimental results in Section 8.2.2.
Finally, our paper concludes in Section 9, summarizing our findings and
discussing potential avenues for future research.

##  3\. Preliminaries

We consider the following classical spaces

(3.1) ${\mathcal{F}}^{\rm Four}:=\Big{\\{}f\in
L^{2}\;|\;f:[0,1]^{d}\mapsto\mathbb{C},f(x)=\sum_{{\boldsymbol{k}}\in\mathbb{Z}^{d}}{\widehat{f}}_{\boldsymbol{k}}e_{\boldsymbol{k}}({\boldsymbol{x}}),\leavevmode\nobreak\
\sum_{{\boldsymbol{k}}\in\mathbb{Z}^{d}}|{\widehat{f}}_{\boldsymbol{k}}|<\infty\Big{\\}},$
(3.2) ${\mathcal{F}}^{\rm cos}:=\Big{\\{}f\in
L^{2}\;|\;f:[0,1]^{d}\mapsto\mathbb{R},f(x)=\sum_{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}}{\widehat{f}}_{\boldsymbol{k}}\phi_{\boldsymbol{k}}({\boldsymbol{x}}),\leavevmode\nobreak\
\sum_{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}}|{\widehat{f}}_{\boldsymbol{k}}|<\infty\Big{\\}},$
(3.3) ${\mathcal{F}}^{\rm Cheb}:=\Big{\\{}f\in
L^{2}\;|\;f:[-1,1]^{d}\mapsto\mathbb{R},f(x)=\sum_{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}}{\widehat{f}}_{\boldsymbol{k}}\eta_{\boldsymbol{k}}({\boldsymbol{x}}),\leavevmode\nobreak\
\sum_{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}}|{\widehat{f}}_{\boldsymbol{k}}|<\infty\Big{\\}}.$

The underlying measure is the Lebesgue measure $d{\boldsymbol{x}}$ for the
first two spaces and the tensor product arcsine measure
$\prod_{j=1}^{d}\frac{dx_{j}}{\pi\sqrt{1-x_{j}^{2}}}$ for the third space. For
each space, the basis used in the expansion is a complete orthonormal system.
They all have a tensor product structure
$e_{\boldsymbol{k}}=\otimes_{j=1}^{d}e_{k_{j}}$,
$\phi_{\boldsymbol{k}}=\otimes_{j=1}^{d}\phi_{k_{j}}$,
$\eta_{\boldsymbol{k}}=\otimes_{j=1}^{d}\eta_{k_{j}}$, where $e_{0}\equiv 1$,
$\phi_{0}\equiv 1$, $\eta_{0}\equiv 1$ otherwise $e_{k}(x)=e^{2i\pi kx}$,
$\phi_{k}(x)=\sqrt{2}\cos(\pi kx)$ and $\eta_{k}(x)=\sqrt{2}T_{k}(x)$, where
$T_{k}$ is the $k$-th Chebyshev polynomial defined by the identity:

$T_{k}(x)=\cos(k\arccos(x)),\quad k=0,1,2,...,\quad\text{for }x\in[-1,1].$

We recall the following

  * •

$(e_{k})_{k\in\mathbb{Z}}$ is a complete orthonormal system for
$L^{2}([0,1],dx)$,

  * •

$(\phi_{k})_{k\in\mathbb{N}_{0}}$ is a complete orthonormal system for
$L^{2}([0,1],dx)$

  * •

$(\eta_{k})_{k\in\mathbb{N}_{0}}$ is a complete orthonormal system for
$L^{2}([-1,1],dx/{\pi\sqrt{1-x^{2}}})$.

In our paper, we designate the first space ${\mathcal{F}}^{\mathrm{Four}}$ as
the Fourier space, representing periodic functions over the unit cube
$[0,1]^{d}$ characterized by absolutely converging Fourier series. The second
space, denoted ${\mathcal{F}}^{\mathrm{cos}}$, is termed the cosine space, of
periodic functions over $[0,1]^{d}$ with absolutely converging cosine series.
The third space, ${\mathcal{F}}^{\mathrm{Cheb}}$, denotes the space of
functions possessing absolutely converging Chebyshev series.

Given an arbitrary finite set $\Lambda$ of indices in $\mathbb{Z}^{d}$
(respectively in $\mathbb{N}_{0}^{d}$), the subspace
${\mathcal{F}}_{\Lambda}^{\rm Four}$ (respectively
${\mathcal{F}}_{\Lambda}^{\rm cos}$, ${\mathcal{F}}_{\Lambda}^{\rm Cheb}$) is
the space of all functions whose Fourier (respectively cosine, Chebyshev)
series is supported solely on $\Lambda$, i.e.,
$\widehat{f}_{\boldsymbol{k}}=0$ for ${\boldsymbol{k}}\notin\Lambda$. For
instance

(3.4) $f\in{\mathcal{F}}_{\Lambda}^{\rm Four}:\quad
f(x)=\sum_{{\boldsymbol{k}}\in\Lambda}\widehat{f}_{\boldsymbol{k}}e^{2\pi\mathrm{i}{\boldsymbol{k}}\cdot{\boldsymbol{x}}}.$

###  3.1. Approximation requirements

For the sake of clarity, in this section we will employ a unified notation for
the spaces and bases we have introduced. We use notation
$(\alpha_{{\boldsymbol{k}}})_{{\boldsymbol{k}}}$ for the multi-variate
complete orthonormal systems and use conjugate notation
$\overline{\alpha_{\boldsymbol{k}}}$. The integral $I(f)$ and inner product
$\langle f,g\rangle=I(f\overline{g})$ are understood from the context. We will
also use ${\mathcal{F}}_{\Lambda}$ for truncated spaces, without specifying
Fourier, cosine or Chebyshev.

Placing ourselves in one of the three spaces, a cubature (or quadrature) is
simply defined by $Q_{n}(f)=\sum_{j=1}^{n}w_{j}f({\boldsymbol{t}}_{i})$ for
given weights $w_{j}>0$ and given nodes ${\boldsymbol{t}}_{i}$ belonging to
the underlying domain. One can be interested in the following properties

  * •

Integral exactness. To demand that the cubature is exact for all functions
which are supported solely on $\Lambda$, i.e., $Q_{n}(f)=I(f)$ for all
$f\in{\mathcal{F}}_{\Lambda}$. This holds if and only if

(3.5)
$Q_{n}(\alpha_{\boldsymbol{k}})=I(\alpha_{\boldsymbol{k}})=\delta_{{\boldsymbol{k}},{\boldsymbol{0}}},\quad\quad\quad{\boldsymbol{k}}\in\Lambda,$

where $\delta$ is the Kronecker symbol, i.e. the cubature formula integrates
exactly all basis functions $\alpha_{\boldsymbol{k}}$ for
${\boldsymbol{k}}\in\Lambda$.

  * •

Function reconstruction. To demand that an approximation operator using
$Q_{n}$ reconstruct all functions which are supported solely on $\Lambda$. We
consider

(3.6)
$f^{a}({\boldsymbol{x}})=\sum_{{\boldsymbol{k}}\in\Lambda}\widehat{f}_{\boldsymbol{k}}^{a}\leavevmode\nobreak\
\alpha_{\boldsymbol{k}}({\boldsymbol{x}}),\quad\quad\quad{\widehat{f}}_{\boldsymbol{k}}^{a}=Q_{n}(f\overline{\alpha_{{\boldsymbol{k}}}}),$

where each coefficient ${\widehat{f}}_{\boldsymbol{k}}=\langle
f,\alpha_{\boldsymbol{k}}\rangle=I(f\overline{\alpha_{\boldsymbol{k}}})$ is
replaced by ${\widehat{f}}_{\boldsymbol{k}}^{a}$ obtained by the cubature
formula applied to $f\overline{\alpha_{\boldsymbol{k}}}$. We assume the “non-
aliasing” condition

${\widehat{f}}_{\boldsymbol{k}}^{a}={\widehat{f}}_{\boldsymbol{k}}\quad\quad\quad\forall{\boldsymbol{k}}\in\Lambda\text{
and }f\in\mathcal{F}_{\Lambda},$

then the operator defined by $f\in{\mathcal{F}}\mapsto
f^{a}\in{\mathcal{F}}_{\Lambda}$ is a reconstruction operator (if other
coefficients $\widehat{f}_{{\boldsymbol{k}}^{\prime}}$ with
${\boldsymbol{k}}^{\prime}\neq{\boldsymbol{k}}$ contribute to
$\widehat{f}_{\boldsymbol{k}}^{a}$ then this is called “aliasing”). It is
easily verified that non-aliasing holds if and only if

(3.7)
$Q_{n}(\alpha_{\boldsymbol{k}}\overline{\alpha_{{\boldsymbol{k}}^{\prime}}})=\delta_{{\boldsymbol{k}},{\boldsymbol{k}}^{\prime}}=\langle\alpha_{\boldsymbol{k}},\alpha_{{\boldsymbol{k}}^{\prime}}\rangle,\quad\quad\quad{\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\Lambda.$

  * •

Function reconstruction and bi-orthonormality. As far as the reconstruction
using cubatures is concerned, a different approach based on bi-orthonormality
is viable. More precisely, we assume given
$(\beta_{\boldsymbol{k}})_{{\boldsymbol{k}}\in\Lambda}$ an arbitrary set of
functions in ${\mathcal{F}}$, which we assume is bi-orthonormal to
$(\alpha_{\boldsymbol{k}})_{{\boldsymbol{k}}\in\Lambda}$, i.e.
$\langle\alpha_{\boldsymbol{k}},\beta_{{\boldsymbol{k}}^{\prime}}\rangle=\delta_{{\boldsymbol{k}},{\boldsymbol{k}}^{\prime}}$.
We consider the approximation $f^{b}$ by

(3.8)
$f^{b}({\boldsymbol{x}})=\sum_{{\boldsymbol{k}}\in\Lambda}{\widehat{f}}_{\boldsymbol{k}}^{b}\leavevmode\nobreak\
\alpha_{\boldsymbol{k}}({\boldsymbol{x}}),\quad{\widehat{f}}_{\boldsymbol{k}}^{b}=\frac{Q_{n}(f\overline{\beta_{{\boldsymbol{k}}}})}{c_{\boldsymbol{k}}},$

for some coefficients $c_{\boldsymbol{k}}\neq 0$. In contrast to approximation
$f^{a}$, the coefficient ${\widehat{f}}_{\boldsymbol{k}}^{b}$ are not defined
using the functions $\alpha_{\boldsymbol{k}}$. Demanding that this scheme
reproduce ${\mathcal{F}}_{\Lambda}$, which is also equivalent to reproducing
all the $\alpha_{\boldsymbol{k}}$ for ${\boldsymbol{k}}\in\Lambda$, holds if
and only if

(3.9)
$Q_{n}(\alpha_{\boldsymbol{k}}\overline{\beta_{{\boldsymbol{k}}^{\prime}}})=c_{\boldsymbol{k}}\delta_{{\boldsymbol{k}},{\boldsymbol{k}}^{\prime}}=c_{\boldsymbol{k}}\langle\alpha_{\boldsymbol{k}},\beta_{{\boldsymbol{k}}^{\prime}}\rangle,\quad\quad\quad{\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\Lambda.$

We can cast the above requirement in a duality framework. For integral
exactness, one is interested in finding a linear form
$\alpha_{\boldsymbol{0}}^{*}:f\mapsto\alpha_{\boldsymbol{0}}^{*}(f)$ over
${\mathcal{F}}$ satisfying
$\alpha_{\boldsymbol{0}}^{*}(\alpha_{\boldsymbol{k}})=\delta_{{\boldsymbol{0}},{\boldsymbol{k}}}$
for any ${\boldsymbol{k}}\in\Lambda$, since such form yields
$\alpha_{\boldsymbol{0}}(f)=\widehat{f}_{\boldsymbol{0}}=I(f)$ for any
$f\in{\mathcal{F}}_{\Lambda}$. As for reconstruction, one is interested in
finding a family of linear forms
$\alpha_{\boldsymbol{h}}^{*}:f\mapsto\alpha_{\boldsymbol{h}}^{*}(f)$ indexed
in $\Lambda$ satisfying
$\alpha_{\boldsymbol{h}}^{*}(\alpha_{\boldsymbol{k}})=\delta_{{\boldsymbol{h}},{\boldsymbol{k}}}$
for any ${\boldsymbol{h}},{\boldsymbol{k}}\in\Lambda$, in which case the
operator
$\sum_{{\boldsymbol{h}}\in\Lambda}\alpha_{\boldsymbol{h}}^{*}(f)\leavevmode\nobreak\
\alpha_{\boldsymbol{h}}$ reconstructs all functions in
${\mathcal{F}}_{\Lambda}$. The forms may or may not depend on $\Lambda$. The
linear forms $f\mapsto{\widehat{f}_{\boldsymbol{h}}}^{\square}$ where
$\square\in\\{a,b,c\\}$ introduced later do not have dependence $\Lambda$.
They were proposed and investigated on [rank1].

###  3.2. Rank-1 lattices rules

Rank-1 lattices are studied for integration, reconstruction and approximation
in the Fourier space. Given the generating vector
${\boldsymbol{z}}\in\mathbb{Z}^{d}$, the $n$ points of a rank-1 lattice are
specified by

(3.10) ${\boldsymbol{t}}_{i}=\frac{i{\boldsymbol{z}}\bmod
n}{n}\in[0,1[^{d}\quad\text{ for }\quad i=0,\ldots,n-1.$

For a function $f$ in the Fourier (respectively Cosine or Chebyshev) space,
the average of the function values at the lattice points (respectively the
tent-transformed [Cools2016TenttransformedLR] or tent-transformed cosine-
transformed lattice points) are given by

(3.11)
$\frac{1}{n}\sum_{i=0}^{n-1}f\left({\boldsymbol{t}}_{i}\right),\quad\frac{1}{n}\sum_{i=0}^{n-1}f\left(\varphi_{\rm
tent}({\boldsymbol{t}}_{i})\right),\quad\frac{1}{n}\sum_{i=0}^{n-1}f\left(\cos\left(2\pi{\boldsymbol{t}}_{i}\right)\right).$

These cubature can be used for approximation objectives discussed earlier. The
first is called a rank-1 lattice rule and is used for approximating the
integral $I(f)=\int_{[0,1]^{d}}fd{\boldsymbol{x}}$ for $f\in{\mathcal{F}}^{\rm
Four}$. Rank-1 lattices have an important property known as the “character
property” which states that the cubature sum of the exponential basis
functions can only take the value of 1 or 0. More precisely

(3.12) $\frac{1}{n}\sum_{i=0}^{n-1}e^{{\mathrm{i}}2\pi
i{{\boldsymbol{h}}\cdot{\boldsymbol{z}}}/n}=\begin{cases}1&\text{ if
}{\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}0,\\\ 0&\text{ otherwise
}.\end{cases}$

The character property, and also the property
$e_{\boldsymbol{k}}\overline{e_{\boldsymbol{k}}^{\prime}}=e_{{\boldsymbol{k}}-{\boldsymbol{k}}^{\prime}}$,
allows to reformulate integral exactness and reconstruction requirements
discussed earlier.

Henceforth, we use # to denote the cardinality of a set. For any multiindex
${\boldsymbol{k}}\in\mathbb{Z}^{d}$, we write
$|{\boldsymbol{k}}|_{0}:=\\#\\{1\leq j\leq d:k_{j}\neq 0\\}$ to represent the
number of nonzero coordinates of ${\boldsymbol{k}}$. For $\sigma\in\\{\pm
1\\}^{d}$ and ${\boldsymbol{k}}\in\mathbb{Z}^{d}$, we define
$\sigma({\boldsymbol{k}}):=(\sigma_{1}k_{1},\ldots,\sigma_{d}k_{d})$,
indicating that the sign changes in $\sigma$ are applied component-wise to
${\boldsymbol{k}}$. For any ${\boldsymbol{k}}\in\mathbb{Z}^{d}$, we define

$S_{{\boldsymbol{k}}}:=\left\\{\sigma\in\\{\pm 1\\}^{d}:\sigma_{j}=+1\text{
for each }j\text{ where }k_{j}=0\right\\}$

to denote a set of unique sign changes for ${\boldsymbol{k}}$. Clearly, we
have $\\#S_{{\boldsymbol{k}}}=2^{|{\boldsymbol{k}}|_{0}}$.

######  Lemma 3.1 (See [Kmmerer2014ReconstructingMT, Potts2016SparseHF]).

Let $\Lambda\subset\mathbb{Z}^{d}$ be an arbitrary index set. A lattice rank-1
rule $Q_{n}^{*}$ with $n$ points and generating vector ${\boldsymbol{z}}$

  * •

integrates exactly all functions $f\in{\mathcal{F}}^{\rm Four}_{\Lambda}$ iff

(3.13) ${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}0\quad\mbox{for
all}\quad{\boldsymbol{h}}\in\Lambda\setminus\\{{\boldsymbol{0}}\\},$

  * •

reconstructs exactly the Fourier coefficients of all $f\in{\mathcal{F}}^{\rm
Four}_{\Lambda}$ by ${\widehat{f}^{a}}=Q_{n}^{*}(fe_{{\boldsymbol{k}}})$ iff

(3.14)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{for
all}\quad{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in\Lambda.$

Requirements for integral exactness and reconstruction along the same lines of
Lemma 3.1 hold with spaces ${\mathcal{F}}_{\Lambda}^{\rm cos}$,
${\mathcal{F}}_{\Lambda}^{\rm Cheb}$. The lemma combined with identities

(3.15)
$\phi_{\boldsymbol{k}}=\frac{1}{2^{|{\boldsymbol{k}}|_{0}}}\sum_{{\boldsymbol{\sigma}}\in{\mathcal{S}}_{\boldsymbol{k}}}e_{{\boldsymbol{\sigma}}({\boldsymbol{k}})},\quad\quad\quad\phi_{\boldsymbol{k}}\phi_{{\boldsymbol{k}}^{\prime}}=\frac{1}{2^{|{\boldsymbol{k}}|_{0}+|{\boldsymbol{k}}^{\prime}|_{0}}}\sum_{\begin{subarray}{c}{\boldsymbol{\sigma}}\in{\mathcal{S}}_{\boldsymbol{k}}\\\
{\boldsymbol{\sigma}}^{\prime}\in{\mathcal{S}}_{{\boldsymbol{k}}^{\prime}}\end{subarray}}e_{{\boldsymbol{\sigma}}({\boldsymbol{k}})+{\boldsymbol{\sigma}}^{\prime}({\boldsymbol{k}}^{\prime})},$

which are valid for any
${\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\mathbb{N}_{0}^{d}$ yields the
results below. The “if” directions in Lemma 3.2 and Lemma 3.3 (plan A)
follows. The “only if” directions also hold and were established in [rank1].

######  Lemma 3.2 (See [rank1]).

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be an arbitrary index set. A tent-
transformed lattice rule of a rank-1 lattice rule $Q_{n}^{*}$ with $n$ points
and generating vector ${\boldsymbol{z}}$ integrates exactly all functions
$f\in{\mathcal{F}}^{\rm cos}_{\Lambda}$ iff

(3.16) ${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}0\quad\mbox{for
all}\quad{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)\setminus\\{{\boldsymbol{0}}\\},$

where

${\mathcal{M}}(\Lambda):=\left\\{\sigma({\boldsymbol{k}}):{\boldsymbol{k}}\in\Lambda,\quad\sigma\in\\{\pm
1\\}^{d}\right\\}=\bigcup_{{\boldsymbol{k}}\in\Lambda}\\{\sigma({\boldsymbol{k}}):\sigma\in
S_{{\boldsymbol{k}}}\\}.$

In order to present rigorously the reconstruction results established in
[rank1], we need to give an account on the cubature introduced their-in. Given
a rank-1 lattice rule $Q_{n}^{*}$ with $n$ points and generating vector
${\boldsymbol{z}}$, we associate to ${\boldsymbol{k}}\in\mathbb{N}_{0}^{d}$

(3.17) $\displaystyle{\widehat{f}}_{\boldsymbol{k}}^{a}$
$\displaystyle:=Q_{n}^{*}\big{(}(f\circ\varphi_{\text{tent
}})(\phi_{\boldsymbol{k}}\circ\varphi_{\text{tent }})\big{)},$ (3.18)
$\displaystyle{\widehat{f}}_{\boldsymbol{k}}^{b}$
$\displaystyle:=Q_{n}^{*}\big{(}(f\circ\varphi_{\text{tent
}})\sqrt{2}^{|{\boldsymbol{k}}|_{0}}\cos(2\pi{\boldsymbol{k}}\cdot{\boldsymbol{x}})\big{)},$
(3.19) $\displaystyle{\widehat{f}}_{\boldsymbol{k}}^{c}$
$\displaystyle:=Q_{n}^{*}\big{(}(f\circ\varphi_{\text{tent
}})\sqrt{2}^{|{\boldsymbol{k}}|_{0}}\cos(2\pi{\boldsymbol{k}}\cdot{\boldsymbol{x}})\big{)}/{c_{{\boldsymbol{k}}}},$

where
$c_{{\boldsymbol{k}}}:=\\#\\{{{\boldsymbol{\sigma}}}\in{\mathcal{S}}_{\boldsymbol{k}}:{\boldsymbol{\sigma}}({\boldsymbol{k}})\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{k}}\cdot{\boldsymbol{z}}\\}$.

The reconstruction requirement (plan A) in based on
${\widehat{f}}_{\boldsymbol{k}}^{a}$ and is relatively straightforward. The
requirements can be weakened employing the bi-orthonormality trick. By
observing that

(3.20)
$\displaystyle\int_{[0,1]^{d}}\phi_{{\boldsymbol{k}}^{\prime}}(\varphi_{\text{tent
}}({\boldsymbol{x}}))\sqrt{2}^{|{\boldsymbol{k}}|_{0}}\cos(2\pi{\boldsymbol{k}}\cdot{\boldsymbol{x}})d{\boldsymbol{x}}=\delta_{{\boldsymbol{k}}^{\prime},{\boldsymbol{k}}},\quad{\boldsymbol{k}}^{\prime},{\boldsymbol{k}}\in\mathbb{N}_{0}^{d},$

one can use functions
$\beta_{\boldsymbol{k}}=\sqrt{2}^{|{\boldsymbol{k}}|_{0}}\cos(2\pi{\boldsymbol{k}}\cdot{\boldsymbol{x}})$
in order to carry the bi-orthonormality trick, which we have briefly
discussed. This observation along the requirements (plan B/C) below where also
derived and thoroughly discussed in [rank1].

######  Lemma 3.3 ([rank1]).

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be an arbitrary index set. A tent-
transformed lattice rule $Q_{n}$ of a rank-1 lattice rule $Q_{n}^{*}$ with $n$
points and generating vector ${\boldsymbol{z}}$ reconstructs exactly the
cosine coefficients of all $f\in{\mathcal{F}}^{\rm cos}_{\Lambda}$

  * •

(plan A) by ${\widehat{f}}={\widehat{f}^{a}}$ iff

(3.21)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{for
all}\quad{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda),$

  * •

(plan B) by ${\widehat{f}}={\widehat{f}^{b}}$ iff

(3.22)
$\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{for
all}\quad{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\leavevmode\nobreak\
\sigma({\boldsymbol{h}})\neq{\boldsymbol{h}}^{\prime},$

  * •

(plan C) by ${\widehat{f}}={\widehat{f}^{c}}$ iff

(3.23)
$\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{for
all}\quad{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime},$

Let us discuss the difference between requirements (3.21), (3.22) and (3.23).
First, it is obvious that (3.21) is stronger than (3.22). Since
$\Lambda\subset\mathbb{N}_{0}^{d}$, then for any
${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in\Lambda$ and
$\sigma\in{\mathcal{S}}_{h}$ one clearly has
$\sigma({\boldsymbol{h}})\neq{\boldsymbol{h}}^{\prime}$ except if
${\boldsymbol{h}}={\boldsymbol{h}}^{\prime}$ and $\sigma=\rm id$. Requiring
(3.22) is therefore equivalent to requiring (3.23) and in addition that
$\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}$
for all ${\boldsymbol{h}}\in\Lambda$ and
$\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}-\\{\rm id\\}$. In other words, in
(3.23) it is allowed that ${\boldsymbol{h}}\cdot{\boldsymbol{z}}$ occur in the
set
$\\{\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}\\}_{\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}-\\{\rm
id\\}}$.

For latter use, we introduce the proper notation for admissibility with plan
A, B and C. Given $\Lambda\subset\mathbb{N}_{0}^{d}$ an arbitrary set of
indices, we let ${\mathcal{P}}_{0}(\Lambda)$ be the set of couples
$(n,{\boldsymbol{z}})\in\mathbb{N}\times\mathbb{Z}^{d}$ satisfying (3.16).
Similarly, we introduce ${\mathcal{P}}_{A}(\Lambda)$,
${\mathcal{P}}_{B}(\Lambda)$ and ${\mathcal{P}}_{C}(\Lambda)$ to be the sets
of couples $(n,{\boldsymbol{z}})\in\mathbb{N}\times\mathbb{Z}^{d}$ satisfying
(3.21), (3.22), and (3.23) respectively. We say that $(n,{\boldsymbol{z}})$ is
admissible for plan $\square$ if
$(n,{\boldsymbol{z}})\in{\mathcal{P}}_{\square}(\Lambda)$.

The discussion above shows that
${\mathcal{P}}_{A}(\Lambda)\subset{\mathcal{P}}_{B}(\Lambda)\subset{\mathcal{P}}_{C}(\Lambda)$.
For the sake of completeness, we summarize in the following proposition.

######  Proposition 3.4.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ finite, the following implications hold

$(n,{\boldsymbol{z}})$ is admissible for plan A $\implies$
$(n,{\boldsymbol{z}})$ is admissible for plan B $\implies$
$(n,{\boldsymbol{z}})$ is admissible for plan C.

######  Remark 3.5.

We denote
${\mathcal{S}}_{{\boldsymbol{h}}}^{*}={\mathcal{S}}_{{\boldsymbol{h}}}-\\{\rm
id\\}$. We remark that ${\mathcal{S}}_{{\boldsymbol{0}}}=\\{\rm id\\}$ and
therefore ${\mathcal{S}}_{{\boldsymbol{0}}}^{*}=\emptyset$. Since
$\Lambda\subset\mathbb{N}_{0}^{d}$, one can easily verify that the extra
requirement on admissibility condition of every plan with respect to others is
as outlined below. By O-O, we simply mean
${\boldsymbol{h}}\in\Lambda\mapsto{\boldsymbol{h}}\cdot{\boldsymbol{z}}$ is
one-to-one.

$\begin{array}[]{|l
l|c|c|c|c|}\hline\cr\text{Requirement}&&\text{O-O}&\text{C}&\text{
B}&\text{A}\\\
\hline\cr{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}&{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda&\checkmark&\checkmark&\checkmark&\checkmark\\\
{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}&{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}^{*}&&\checkmark&\checkmark&\checkmark\\\
{\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\
\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}&{\boldsymbol{h}}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}^{*}&&&\checkmark&\checkmark\\\
\sigma^{\prime}({\boldsymbol{h}}^{\prime})\cdot{\boldsymbol{z}}\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}&{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}^{*},\leavevmode\nobreak\
\sigma^{\prime}\in{\mathcal{S}}_{{\boldsymbol{h}}^{\prime}}^{*}.&&&&\checkmark\\\
\hline\cr\end{array}$

For any given ${\boldsymbol{z}}\in\mathbb{Z}^{d}$, we let
$n^{*}_{0}(\Lambda,{\boldsymbol{z}})$ be the smallest possible integer $n$
s.t. $(n,{\boldsymbol{z}})\in{\mathcal{P}}_{0}(\Lambda)$. By convention
$n^{*}_{0}(\Lambda,{\boldsymbol{z}})=+\infty$ if no such $n$ exists, e.g. the
case ${\boldsymbol{z}}={\boldsymbol{0}}$. We define similarly the integers
$n^{*}_{A}(\Lambda,{\boldsymbol{z}})$, $n^{*}_{B}(\Lambda,{\boldsymbol{z}})$
and $n^{*}_{C}(\Lambda,{\boldsymbol{z}})$.

We introduce a dedicated notation $n^{*}_{0}(\Lambda)$ for the smallest
possible integer $n$ such that
$(n,{\boldsymbol{z}})\in{\mathcal{P}}_{0}(\Lambda)$ for some
${\boldsymbol{z}}$. We define similarly the notation $n^{*}_{A}(\Lambda)$,
$n^{*}_{B}(\Lambda)$ and $n^{*}_{C}(\Lambda)$. Obviously
$n^{*}_{\square}(\Lambda)\geq 2$ where $\square$ is $0$ or A/B/C. Upper bounds
$n_{\square}^{*}(\Lambda)\leq p_{\square}^{*}(\Lambda)$ are provided in
[rank1]. Namely

(3.24) $\begin{array}[]{cl}p_{0}^{*}(\Lambda)&\text{smallest prime
}\geq\max\left\\{{\\#({\mathcal{M}}(\Lambda)\backslash\\{0\\}}+2,2q\right\\}/2,\\\
p_{A}^{*}(\Lambda)&\text{smallest prime
}\geq\max\left\\{{\\#({\mathcal{M}}(\Lambda)\oplus{\mathcal{M}}(\Lambda))}+2,2q\right\\}/2,\\\
p_{B}^{*}(\Lambda)&\text{smallest prime
}\geq\max\left\\{{\\#(\Lambda\oplus{\mathcal{M}}(\Lambda))},2q\right\\},\\\
p_{C}^{*}(\Lambda)&\text{smallest prime
}\geq\max\left\\{{\\#(\Lambda)\\#({\mathcal{M}}(\Lambda))},2q\right\\},\end{array}$

where $q=\max\\{\|{\boldsymbol{k}}\|_{\infty}:{\boldsymbol{k}}\in\Lambda\\}$.

In the next section, we derive new lower bounds on $n$, the number of rank-$1$
lattice points needed for exact integration and the exact reconstruction using
plan A, plan B, or plan C.

##  4\. Necessary condition for the exact reconstruction

###  4.1. Necessary condition for plans A/B/C

In this section, we derive lower bounds on the numbers $n^{*}_{A}(\Lambda)$,
$n^{*}_{B}(\Lambda)$ and $n^{*}_{C}(\Lambda)$ of minimal rank-$1$ lattice
points needed for exact reconstruction over ${\mathcal{F}}^{\rm
cos}_{\Lambda}$ using plan A, plan B, and plan C respectively.

######  Proposition 4.1.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be an arbitrary index set of finite
cardinality.

  * •

for any value $n<\\#({\mathcal{M}}({\Lambda}))$, there exists no
${\boldsymbol{z}}\in\mathbb{Z}^{d}$ s.t.

(4.1)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{
for all
}\quad{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda).$

If ${\boldsymbol{0}}\not\in\Lambda$, the conclusion also holds for
$n=\\#({\mathcal{M}}({\Lambda}))$.

  * •

for any value
$n<\\#(\\{{\boldsymbol{h}},-{\boldsymbol{h}}\\}_{{\boldsymbol{h}}\in\Lambda})$,
there exists no ${\boldsymbol{z}}\in\mathbb{Z}^{d}$ s.t.

(4.2)
$\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{for
all}\quad{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\leavevmode\nobreak\
\sigma({\boldsymbol{h}})\neq{\boldsymbol{h}}^{\prime},$

and if ${\boldsymbol{0}}\not\in\Lambda$, the conclusion also holds for
$n=\\#(\\{{\boldsymbol{h}},-{\boldsymbol{h}}\\}_{{\boldsymbol{h}}\in\Lambda})$,

  * •

for any value $n<\\#(\Lambda)$, there exists no
${\boldsymbol{z}}\in\mathbb{Z}^{d}$ s.t.

(4.3)
$\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{for
all}\quad{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}.$

###### Proof.

We consider ${\boldsymbol{z}}\in\mathbb{Z}^{d}$ arbitrary and the associated
map

${\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)\mapsto{\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\
{\rm mod}\leavevmode\nobreak\ n\in\\{0,\dots,n-1\\}.$

If $n<\\#({\mathcal{M}}({\Lambda}))$, then by the pigeonhole principle the map
can not be injective, which proves the first claim. We assume now
$n=\\#({\mathcal{M}}({\Lambda}))$ but ${\boldsymbol{0}}\not\in\Lambda$. Two
situations are to be considered. If the image of ${\mathcal{M}}({\Lambda})$ is
strictly included in $\\{0,\dots,n-1\\}$, then again by the pigeonhole
principle the map can not be injective. Otherwise, all the remainders
$0,1,\cdots,n-1$ are obtained by the mapping. In particular, there exists
${\boldsymbol{h}}\in{\mathcal{M}}({\Lambda})$ satisfying
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}0$. This implies that
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}$
which again make the map not injective since
$-{\boldsymbol{h}}\in{\mathcal{M}}({\Lambda})$ and
${\boldsymbol{h}}\neq-{\boldsymbol{h}}$. The requirement (4.2) implies that
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all ${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in\Lambda$ (by letting
$\sigma=id$) and that
$-{\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all ${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in\Lambda$ (by letting
$\sigma=-id$ and checking that
$-{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}$ holds except if
${\boldsymbol{h}}={\boldsymbol{h}}^{\prime}={\boldsymbol{0}}$). Also, since
$x\equiv_{n}y$ if and only if $-x\equiv_{n}-y$, the requirement implies
$-{\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}-{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all ${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in\Lambda$. We
introduce the set
$\Lambda^{\pm}=\\{{\boldsymbol{h}},-{\boldsymbol{h}}\\}_{{\boldsymbol{h}}\in\Lambda}$.
The requirement thus implies that the map
${\boldsymbol{h}}\in\Lambda^{\pm}\mapsto({\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\
{\rm mod}\leavevmode\nobreak\ n)$ is injective. But, this can not hold if
$n<\\#(\Lambda^{\pm})$. If ${\boldsymbol{0}}\not\in\Lambda$, the same argument
used above applies since as for ${\mathcal{M}}(\Lambda)$, the set
$\Lambda^{\pm}$ satisfies
${\boldsymbol{h}}\in\Lambda^{\pm}\Longrightarrow-{\boldsymbol{h}}\in\Lambda^{\pm}$.
Requirement (4.3) implies clearly that the map
${\boldsymbol{h}}\in\Lambda\mapsto({\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\
{\rm mod}\leavevmode\nobreak\ n)$ is injective (by letting $\sigma=id$). We
can not have this if $n<\\#(\Lambda)$. ∎

We note that $\\#(\Lambda^{\pm})$ is equal to $2\\#(\Lambda)$ if
${\boldsymbol{0}}\not\in\Lambda$ and to $2\\#(\Lambda)-1$ otherwise. The lemma
provides lower bounds on the number of points that are necessary to perform
exact reconstruction over ${\mathcal{F}}^{\rm cos}_{\Lambda}$ using plan A,
plan B, and plan C. In particular, we have proved that for any finite set
$\Lambda\subset\mathbb{N}_{0}^{d}$

(4.4) $\begin{array}[]{l}n^{*}_{A}(\Lambda)\geq
l^{*}_{A}(\Lambda):=\\#({\mathcal{M}}({\Lambda}))+1_{{\boldsymbol{0}}\not\in\Lambda},\\\
n^{*}_{B}(\Lambda)\geq
l^{*}_{B}(\Lambda):=2\\#(\Lambda)+\delta_{\Lambda,{\boldsymbol{0}}},\\\
n^{*}_{C}(\Lambda)\geq l^{*}_{C}(\Lambda):=\\#(\Lambda),\end{array}$

where

$\delta_{\Lambda,{\boldsymbol{0}}}=1$ if ${\boldsymbol{0}}\not\in\Lambda$ and
$\delta_{\Lambda,{\boldsymbol{0}}}=-1$ if ${\boldsymbol{0}}\in\Lambda$.

Next, we demonstrate that $n^{*}_{A}(\Lambda)=\\#({\mathcal{M}}({\Lambda}))$
is optimal in some cases, in particular in any dimension for $\Lambda$ of
“block” type. It is worth noting that while the other lower bounds are not
optimal, they provide a favorable initial guess to initiate algorithms.

(a) block

(b) cross

(c) simplex

Figure 1.  Sets ${\mathcal{B}}_{{\boldsymbol{k}}}$,
${\mathcal{C}}_{{\boldsymbol{k}}}$ and ${\mathcal{S}}_{{\boldsymbol{1}},k}$
and associated mirrored sets in dimension 2.

###  4.2. Sharpness of the necessary condition

For ${\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\mathbb{Z}^{d}$,
${\boldsymbol{k}}^{\prime}\leq{\boldsymbol{k}}$ is to be interpreted
component-wise, i.e., $k^{\prime}_{j}\leq k_{j}$ for all $j$. We introduce the
notation ${\mathcal{B}}_{{\boldsymbol{k}}}$,
${\mathcal{C}}_{{\boldsymbol{k}}}$ and ${\mathcal{S}}_{{\boldsymbol{1}},k}$
for
${\mathcal{B}}_{{\boldsymbol{k}}}:=\\{{\boldsymbol{h}}\in\mathbb{N}_{0}^{2}:{\boldsymbol{h}}\leq{\boldsymbol{k}}\\}$,
${\mathcal{C}}_{{\boldsymbol{k}}}:=\\{{\boldsymbol{h}}\in{\mathcal{B}}_{{\boldsymbol{k}}}:h_{1}h_{2}=0\\}$
where ${\boldsymbol{k}}\in\mathbb{N}_{0}^{2}$ and
${\mathcal{S}}_{{\boldsymbol{1}},k}=\\{{\boldsymbol{h}}\in\mathbb{N}_{0}^{2}:h_{1}+h_{2}\leq
k\\}$ where $k\in\mathbb{N}_{0}$. Mirrored sets are
${\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}})=\\{{\boldsymbol{h}}\in\mathbb{Z}^{2}:-{\boldsymbol{k}}\leq{\boldsymbol{h}}\leq{\boldsymbol{k}}\\}$,
${\mathcal{M}}({\mathcal{C}}_{{\boldsymbol{k}}})=\\{{\boldsymbol{h}}\in{\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}):h_{1}h_{2}=0\\}$,
and
${\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k})=\\{{\boldsymbol{h}}\in\mathbb{Z}^{2}:|h_{1}|+|h_{2}|\leq
k\\}$. Cardinalities of all these sets are easily verified

(4.5)
$\begin{array}[]{ll}\\#({\mathcal{B}}_{{\boldsymbol{k}}})=(k_{1}+1)(k_{2}+1),&\quad\\#({\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}))=(2k_{1}+1)(2k_{2}+1),\\\
\\#({\mathcal{C}}_{{\boldsymbol{k}}})=k_{1}+k_{2}+1,&\quad\\#({\mathcal{M}}({\mathcal{C}}_{{\boldsymbol{k}}}))=2(k_{1}+k_{2})+1,\\\
\\#({\mathcal{S}}_{{\boldsymbol{1}},k})={(k+1)(k+2)}/2,&\quad\\#({\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k}))=2k^{2}+2k+1.\end{array}$

######  Proposition 4.2.

Let ${\boldsymbol{k}}\in\mathbb{N}_{0}^{2}$,
$n=\\#({\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}))$ and
${\boldsymbol{z}}=(1,2k_{1}+1)$. Then

(4.6)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{
for all
}\quad{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}).$

###### Proof.

We let ${\boldsymbol{h}}$, ${\boldsymbol{h}}^{\prime}$ be in
${\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}})$ satisfying
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$.
We have that $(h_{1}^{\prime}-h_{1})+(h_{2}^{\prime}-h_{2})(2k_{1}+1)=nq$ for
some integer $q$. Since $n|q|\leq 2k_{1}+2k_{2}\times(2k_{1}+1)=n-1$,
necessarily $q=0$. This in turn implies
$(2k_{1}+1)(h_{2}-h_{2}^{\prime})=h_{1}^{\prime}-h_{1}\in\\{-k_{1},\dots,k_{1}\\}$
which holds if and only if $h_{2}^{\prime}-h_{2}=0$ and
$h_{1}^{\prime}-h_{1}=0$, hence ${\boldsymbol{h}}={\boldsymbol{h}}^{\prime}$.
The proof is complete. ∎

######  Proposition 4.3.

Let $k\in\mathbb{N}$,
$n=\\#({\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k}))$ and
${\boldsymbol{z}}=(1,2k+1)$. Then

(4.7)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{
for all
}\quad{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k}).$

###### Proof.

We let ${\boldsymbol{h}}$, ${\boldsymbol{h}}^{\prime}$ be in
${\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k})$ satisfying
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$.
We have that $(h_{1}^{\prime}-h_{1})+(h_{2}^{\prime}-h_{2})(2k+1)=nq$ for some
integer $q$, which we can assume $\geq 0$ up to permute the roles of
${\boldsymbol{h}}$ and ${\boldsymbol{h}}^{\prime}$. We have
$(h_{1}^{\prime}+h_{2}^{\prime})-(h_{1}+h_{2})+2k(h_{2}^{\prime}-h_{2})=nq$,
thus $0\leq nq\leq k+k+2k\times 2k=4k^{2}+2k$. In view of $n=2k^{2}+2k+1$, we
deduce that $q\in\\{0,1\\}$. If $q=1$, we reformulate as
$(h_{1}^{\prime}-h_{1}+k)+(h_{2}^{\prime}-h_{2})(2k+1)=(k+1)(2k+1)$, hence
$(h_{1}^{\prime}-h_{1}+k)$ is a multiple of $(2k+1)$. Since
$|h_{1}|,|h_{1}^{\prime}|\leq k$, then necessarily $h_{1}^{\prime}-h_{1}+k=0$
or $h_{1}^{\prime}-h_{1}+k=2k+1$, to which correspond
$h_{2}^{\prime}-h_{2}=k+1$ and $h_{2}^{\prime}-h_{2}=-k$ respectively. In the
first case, necessarily $h_{1}\geq 0$ and $h_{2}\leq-1$, implying

$k\geq\|{\boldsymbol{h}}\|_{\ell_{1}}=h_{1}-h_{2}=h_{1}^{\prime}+k+k+1-h_{2}^{\prime}\geq
2k+1-\|{\boldsymbol{h}}^{\prime}\|_{\ell_{1}}>k.$

The second case is similar, simply the roles of $h_{1},h_{1}^{\prime}$ and
$h_{2},h_{2}^{\prime}$ as swapped. We deduce that necessarily $q=0$. This in
turn implies
$(2k+1)(h_{2}^{\prime}-h_{2})=(h_{1}-h_{1}^{\prime})\in\\{-k,\dots,k\\}$ which
holds if and only if $h_{2}^{\prime}-h_{2}=0$ and $h_{1}^{\prime}-h_{1}=0$,
hence ${\boldsymbol{h}}={\boldsymbol{h}}^{\prime}$. The proof is complete. ∎

######  Remark 4.4.

With ${\boldsymbol{z}}=(k,k+1)$, the same result as above holds. In addition,
the proof is much simpler as we quickly derive that $q=0$ and conclude. This
is the lattice rule for the Padua points (see [Padua]).

######  Proposition 4.5.

Let ${\boldsymbol{k}}\in\mathbb{N}^{2}$,
$n=\\#({\mathcal{B}}_{\boldsymbol{k}})+1$ and ${\boldsymbol{z}}=(1,k_{1}+1)$.
Then

(4.8)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\quad\mbox{
for all
}\quad{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{C}}_{{\boldsymbol{k}}}).$

Moreover, for any $n\leq\\#({\mathcal{B}}_{\boldsymbol{k}})$ and any
${\boldsymbol{z}}$, the above can not hold.

###### Proof.

We let ${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}$ be in
${\mathcal{M}}({\mathcal{C}}_{{\boldsymbol{k}}})$ satisfying
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$.
Then $(h_{1}-h_{1}^{\prime})+(h_{2}-h_{2}^{\prime})(k_{1}+1)=nq$ for some
integer $q$, which we assume $\geq 0$. We then use $0\leq
nq\leq|h_{1}-h_{1}^{\prime}|+|h_{2}-h_{2}^{\prime}|(\leavevmode\nobreak\
k_{1}+1)$, $n=(k_{1}+1)(k_{2}+1)+1$, and distinguish between the different
cases:

  * •

if $h_{1}=h_{1}^{\prime}=0$: then $nq\leq 2k_{2}(k_{1}+1)<2n$ implying $q=0$
or $q=1$,

  * •

if $h_{2}=h_{2}^{\prime}=0$: then $nq\leq 2k_{1}<n$ implying $q=0$,

  * •

if $h_{1}=h_{2}^{\prime}=0$: then $nq\leq k_{1}+k_{2}(k_{1}+1)<n$ implying
$q=0$,

  * •

if $h_{1}^{\prime}=h_{2}=0$: then $nq\leq k_{1}+k_{2}(k_{1}+1)<n$ implying
$q=0$.

In the first case, $q=1$ implies $(h_{2}-h_{2}^{\prime}-(k_{2}+1))(k_{1}+1)=1$
but this can not holds. Therefore, $q=0$ in all cases. In the first and second
case, this clearly yields
${\boldsymbol{h}}={\boldsymbol{h}}^{\prime}={\boldsymbol{0}}$. In the third
case, it implies $-h_{1}^{\prime}+h_{2}(k_{1}+1)=0$ hence in view of
$|h_{1}^{\prime}|\leq k_{1}$ necessarily $h_{1}^{\prime}=h_{2}^{\prime}=0$, so
that ${\boldsymbol{h}}={\boldsymbol{h}}^{\prime}={\boldsymbol{0}}$. The same
holds for the forth case. The first part of the proof is complete. Now we
prove that for $n\leq\\#({\mathcal{B}}_{\boldsymbol{k}})$ and any
${\boldsymbol{z}}\in\mathbb{Z}^{2}$, it is impossible to have (4.8). For
${\boldsymbol{z}}=(z_{1},z_{2})$ arbitrary, we consider the set

${\mathcal{S}}=\\{{\boldsymbol{h}}\cdot{\boldsymbol{z}}{\leavevmode\nobreak\
\text{mod}\leavevmode\nobreak\
}n\\}_{{\boldsymbol{h}}\in{\mathcal{B}}_{{\boldsymbol{k}}}}.$

If $n<\\#({\mathcal{B}}_{{\boldsymbol{k}}})$, by the pigeonhole principle
there must exist
${\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in{\mathcal{B}}_{{\boldsymbol{k}}}$
s.t.
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}$.
This in turn implies
${\boldsymbol{l}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{l}}\cdot{\boldsymbol{z}}$
where ${\boldsymbol{l}}^{\prime}=(h_{1}^{\prime}-h_{1},0)$ and
${\boldsymbol{l}}=(0,h_{2}-h_{2}^{\prime})$, which are distinct and both
belong to ${\mathcal{M}}({\mathcal{C}}_{{\boldsymbol{k}}})$. If
$n=\\#({\mathcal{B}}_{{\boldsymbol{k}}})$, then either we have a similar
situation otherwise all the remainder $0,\dots,n-1$ are taken by
$({\boldsymbol{h}}\cdot{\boldsymbol{z}}{\leavevmode\nobreak\
\text{mod}\leavevmode\nobreak\ }n)$ for ${\boldsymbol{h}}$ varying in
${\mathcal{B}}_{{\boldsymbol{k}}}$. In this case, there exists
$(a,b)\in{\mathcal{B}}_{{\boldsymbol{k}}}$ s.t. $az_{1}+bz_{2}\equiv_{n}1$.
Also, there exist
${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in{\mathcal{B}}_{{\boldsymbol{k}}}$
s.t. $h_{1}z_{1}+h_{2}z_{2}\equiv_{n}(k_{1}+1)z_{1}$ and
$h_{1}^{\prime}z_{1}+h_{2}^{\prime}z_{2}\equiv_{n}(k_{2}+1)z_{2}$, which we
reformulate as $h_{2}z_{2}\equiv_{n}(k_{1}+1-h_{1})z_{1}$ and
$h_{1}^{\prime}z_{1}\equiv_{n}(k_{2}+1-h_{2}^{\prime})z_{2}$. In particular,
if $1\leq h_{1}\leq k_{1}$ we obtain
${\boldsymbol{l}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{l}}^{\prime}\cdot{\boldsymbol{z}}$
where ${\boldsymbol{l}}=(k_{1}+1-h_{1},0)$ and
${\boldsymbol{l}}^{\prime}=(0,h_{2})$, and if $1\leq h_{2}^{\prime}\leq
k_{2}$, we obtain
${\boldsymbol{l}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{l}}^{\prime}\cdot{\boldsymbol{z}}$
where ${\boldsymbol{l}}=(h_{1}^{\prime},0)$ and
${\boldsymbol{l}}^{\prime}=(0,k_{2}+1-h_{2}^{\prime})$, with
${\boldsymbol{l}}\neq{\boldsymbol{l}}^{\prime}\in\mathcal{M}({\mathcal{C}}_{{\boldsymbol{k}}})$
in both cases, which yields to the violation of equation (4.8). It only
remains the case $h_{1}=h_{2}^{\prime}=0$, which implies

$\left\\{\begin{array}[]{rl}h_{2}z_{2}\equiv_{n}(k_{1}+1)z_{1},\\\
h_{1}^{\prime}z_{1}\equiv_{n}(k_{2}+1)z_{2}.\end{array}\right.$

Multiplying these equations by $(k_{2}+1)$ and $(k_{1}+1)$ respectively yields

$\left\\{\begin{array}[]{rl}h_{2}h_{1}^{\prime}z_{2}\equiv_{n}nz_{1}\equiv_{n}0,\\\
h_{2}h_{1}^{\prime}z_{1}\equiv_{n}nz_{2}\equiv_{n}0.\end{array}\right.$

Combining with the equality $az_{1}+bz_{2}\equiv_{n}1$, we obtain
$h_{2}h_{1}^{\prime}\equiv_{n}h_{2}h_{1}^{\prime}(az_{1}+bz_{2})\equiv_{n}0$,
which implies $n$ divides $h_{2}h_{1}^{\prime}$. In view of
$n=(k_{1}+1)(k_{2}+1)$ and $|h_{2}h_{1}^{\prime}|\leq k_{2}k_{1}$ this is only
possible if $h_{2}=0$ or $h_{1}^{\prime}=0$. We again obtain
${\boldsymbol{l}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{l}}\cdot{\boldsymbol{z}}$
with ${\boldsymbol{l}}=(-1,0)$ and ${\boldsymbol{l}}^{\prime}=(k_{1},0)$ or
${\boldsymbol{l}}=(0,-1)$ and ${\boldsymbol{l}}^{\prime}=(0,k_{2})$
respectively, which in both cases satisfy
${\boldsymbol{l}}\neq{\boldsymbol{l}}^{\prime}\in\mathcal{M}({\mathcal{C}}_{{\boldsymbol{k}}})$.
We conclude that (4.8) can not hold. The proof is complete. ∎

In each of the three previous propositions, $n$ is the smallest possible
number for which the conditions hold. In particular, in dimension $d=2$ one
has

(4.9)
$\begin{array}[]{rll}n_{A}^{*}({\mathcal{B}}_{\boldsymbol{k}})&=&(2k_{1}+1)(2k_{2}+1),\\\
n_{A}^{*}({\mathcal{C}}_{\boldsymbol{k}})&=&(k_{1}+1)(k_{2}+1)+1,\\\
n_{A}^{*}({\mathcal{S}}_{{\boldsymbol{1}},k})&=&2k^{2}+2k+1.\end{array}$

The first result also holds in higher dimensions. We now use notation
${\mathcal{B}}_{{\boldsymbol{k}}}:=\\{{\boldsymbol{h}}\in\mathbb{N}_{0}^{d}:{\boldsymbol{h}}\leq{\boldsymbol{k}}\\}$
where ${\boldsymbol{h}}\in\mathbb{N}_{0}^{d}$ to denote a block in dimension
$d$.

######  Lemma 4.6.

Consider ${\mathcal{B}}_{{\boldsymbol{k}}}$ and let
$n_{\boldsymbol{k}}=\\#({\mathcal{B}}_{{\boldsymbol{k}}})$. The vector
${\boldsymbol{z}}=(z_{1},\cdots,z_{d})$ defined by $z_{1}=1$ and
$z_{i}=\prod_{j=1}^{i-1}(k_{j}+1)$ for $i=2,\dots,d$, yields

(4.10) ${\boldsymbol{h}}\to{\boldsymbol{h}}\cdot{\boldsymbol{z}},\quad\mbox{is
injective over ${\mathcal{B}}_{{\boldsymbol{k}}}$}.$

Moreover,
$|{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}|<n_{{\boldsymbol{k}}}$
for any
${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in{\mathcal{B}}_{{\boldsymbol{k}}}$.

###### Proof.

For the sake of clarity, we distinguish the cases $d=1$, $d=2$ and $d\geq 3$.
This also allows us to build up the intuition that led to the particular
choice of ${\boldsymbol{z}}$.

$\bullet$ Case $d=1$: ${\mathcal{B}}_{k}=\\{0,\dots,k\\}$ and $n_{k}=k+1$.
Every integer $z_{1}\neq 0$ ensures the map is injective but only $z_{1}=\pm
1$ ensure the second conclusion.

$\bullet$ Case $d=2$:
${\mathcal{B}}_{{\boldsymbol{k}}}=\\{0,\dots,k_{1}\\}\times\\{0,\dots,k_{2}\\}$
and $n_{\boldsymbol{k}}=(k_{1}+1)(k_{2}+1)$. We have
${\boldsymbol{h}}\cdot{\boldsymbol{z}}=h_{1}z_{1}+h_{2}z_{2}$. For $h_{2}$
varying in $\\{0,\dots,k_{2}\\}$, the values $h_{2}z_{2}$ make jumps of length
$|z_{2}|$. By setting $z_{1}=1$, so that $h_{1}z_{1}=h_{1}$ takes the
contiguous values $0,\dots,k_{1}$, it is sufficient to set $z_{2}=(k_{1}+1)$
in order to ensure ${\boldsymbol{h}}\to{\boldsymbol{h}}\cdot{\boldsymbol{z}}$
is injective over ${\mathcal{B}}_{{\boldsymbol{k}}}$. Moreover
$|{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}|\leq|h^{\prime}_{1}-h_{1}|+(k_{1}+1)|h_{2}^{\prime}-h_{2}|\leq
k_{1}+(k_{1}+1)k_{2}=n_{\boldsymbol{k}}-1$ for any
${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in{\mathcal{B}}_{{\boldsymbol{k}}}$.

$\bullet$ Case $d\geq 3$: we have
${\mathcal{B}}_{{\boldsymbol{k}}}=\\{0,\dots,k_{1}\\}\times{\mathcal{B}}_{\widehat{\boldsymbol{k}}}$,
and $n_{{\boldsymbol{k}}}=(k_{1}+1)n_{\widehat{\boldsymbol{k}}}$, where
$\widehat{\boldsymbol{k}}=(k_{2},\dots,k_{d})$. In particular,
$n_{{\boldsymbol{k}}}-1=k_{1}+(k_{1}+1)(n_{\widehat{\boldsymbol{k}}}-1)$. The
idea is to exploit the above properties and set ${\boldsymbol{z}}$ to a choice
that allow us to unroll an induction and derive the desired conclusions. We
set ${\boldsymbol{z}}=(1,(k_{1}+1)\widehat{\boldsymbol{z}})$, then

${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}=(h_{1}^{\prime}-h_{1})+(k_{1}+1)(\widehat{\boldsymbol{h}}^{\prime}\cdot\widehat{\boldsymbol{z}}-\widehat{\boldsymbol{h}}\cdot\widehat{\boldsymbol{z}}).$

For
${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in{\mathcal{B}}_{{\boldsymbol{k}}}$,
$|h_{1}^{\prime}-h_{1}|\leq k_{1}$. If in addition we assume
$|\widehat{\boldsymbol{h}}^{\prime}\cdot\widehat{\boldsymbol{z}}-\widehat{\boldsymbol{h}}\cdot\widehat{\boldsymbol{z}}|<n_{\widehat{\boldsymbol{k}}}$,
we obtain
$|{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}|\leq
k_{1}+(k_{1}+1)(n_{\widehat{\boldsymbol{k}}}-1)=n_{{\boldsymbol{k}}}-1$.
Moreover if
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}={\boldsymbol{h}}\cdot{\boldsymbol{z}}$
then

$(h_{1}^{\prime}-h_{1})+(2k_{1}+1)(\widehat{\boldsymbol{h}}^{\prime}\cdot\widehat{\boldsymbol{z}}-\widehat{\boldsymbol{h}}\cdot\widehat{\boldsymbol{z}})=0,$

which in view of $|h_{1}^{\prime}-h_{1}|\leq k_{1}$ implies
$h_{1}^{\prime}=h_{1}$ and
$\widehat{\boldsymbol{h}}^{\prime}\cdot\widehat{\boldsymbol{z}}=\widehat{\boldsymbol{h}}\cdot\widehat{\boldsymbol{z}}$.
Defining $\widehat{\boldsymbol{z}}$ from $\widehat{\boldsymbol{k}}$ in a
similar fashion to ${\boldsymbol{z}}$ from ${\boldsymbol{k}}$ allows us to re-
iterate the argument and yield
$h_{2}^{\prime}=h_{2},\dots,\leavevmode\nobreak\ h_{d}^{\prime}=h_{d}$. The
choice ${\boldsymbol{z}}$ suggested in the lemma satisfy the desired
properties. The proof is complete. ∎

The lemma is not exclusive to blocks anchored to ${\boldsymbol{0}}$. Over all
translated block ${\boldsymbol{a}}+{\mathcal{B}}_{\boldsymbol{k}}$ for
${\boldsymbol{a}}\in\mathbb{N}_{0}^{d}$, the same dependence of
${\boldsymbol{z}}$ in ${\boldsymbol{k}}$ yields the exact same conclusions. In
particular, since
${\mathcal{M}}({\mathcal{B}}_{\boldsymbol{k}})=-{\boldsymbol{k}}+{\mathcal{B}}_{2{\boldsymbol{k}}}$,
we have the following.

######  Lemma 4.7.

Consider ${\mathcal{B}}_{{\boldsymbol{k}}}$ and let
$m_{\boldsymbol{k}}=\\#({\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}))$. The
vector ${\boldsymbol{z}}=(z_{1},\cdots,z_{d})$ defined by $z_{1}=1$ and
$z_{i}=\prod_{j=1}^{i-1}(2k_{j}+1)$ for $i=2,\dots,d$, yields

(4.11) ${\boldsymbol{h}}\to{\boldsymbol{h}}\cdot{\boldsymbol{z}},\quad\mbox{is
injective over ${\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}})$}.$

Moreover,
$|{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}|<m_{{\boldsymbol{k}}}$
for any
${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}})$.

In the previous lemmas, many others choices of ${\boldsymbol{z}}$ yield the
same conclusions. By building ${\boldsymbol{z}}$ as suggested but in some
order $z_{\pi(1)},\dots,z_{\pi(d)}$ from $(k_{\pi(1)},\dots,k_{\pi(d)})$ where
$\pi$ a permutation of $\\{1,\dots,d\\}$, we obtain a different
${\boldsymbol{z}}$. Therefore, at least $d!$ suitable choices for
${\boldsymbol{z}}$.

The above lemma implies that
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}})$,
is realized with the prescribed ${\boldsymbol{z}}$ and
$n=\\#({\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}))$ which is the smallest
possible value according to Proposition 4.1. Therefore, in any dimension
$d\geq 1$

(4.12)
$n_{A}^{*}({\mathcal{B}}_{\boldsymbol{k}})=\\#({\mathcal{M}}({\mathcal{B}}_{{\boldsymbol{k}}}))=(2k_{1}+1)\dots(2k_{d}+1).$

##  5\. Lower sets

###  5.1. Definition and examples

######  Definition 5.1.

An index set $\Lambda\subset\mathbb{N}_{0}^{d}$ is called lower111also called
downward closed if it does satisfy the following property

(5.1) ${\boldsymbol{k}}\in\Lambda\quad\mbox{ and
}\quad{\boldsymbol{h}}\leq{\boldsymbol{k}}\quad\implies\quad{\boldsymbol{h}}\in\Lambda.$

The comparison ${\boldsymbol{h}}\leq{\boldsymbol{k}}$ is meant component-wise,
$h_{i}\leq k_{i}$ for all $1\leq i\leq d$.

A lower set $\Lambda$ can be equivalently defined by the property

(5.2) ${\boldsymbol{k}}\in\Lambda\quad\text{and}\quad k_{i}\geq
1\quad\implies\quad{\boldsymbol{k}}-e_{i}\in\Lambda.$

These particular sets are useful in various applications, as discussed e.g. in
[ChkifaLower, Chkifa2016PolynomialAV]. Any lower set contains the null multi-
index ${\boldsymbol{0}}$. For a lower set $\Lambda$, we have
$\Lambda=\bigcup_{{\boldsymbol{k}}\in\Lambda}{\mathcal{B}}_{\boldsymbol{k}}$.
Typical examples of lower sets are the isotropic sets
$\left\\{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}:k_{j}\leq r\leavevmode\nobreak\
\forall j\right\\}$,
$\\{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}:\sum_{j=1}^{d}k_{j}\leq r\\}$, and
$\\{{\boldsymbol{k}}\in\mathbb{N}_{0}^{d}:\sum_{j=1}^{d}k_{j}^{2}\leq
r^{2}\\}$, parameterized by $r\geq 1$. These are the intersections of
$\mathbb{N}_{0}^{d}$ with balls in $\mathbb{R}^{d}$ of radius $r$, for the
$\ell_{\infty}$, $\ell_{1}$ and $\ell_{2}$ norms respectively. Another typical
set is the hyperbolic cross $\\{{\boldsymbol{k}}:\prod_{j=1}^{d}(1+k_{j})\leq
N\\}$, which is the union of all lower sets of cardinality less or equal than
$N$.

The lower sets we will refer to as of block-type, cross-type or simplex-type,
are

(5.3)
$\begin{array}[]{c}\displaystyle{\mathcal{B}}_{\boldsymbol{k}}:=\big{\\{}{\boldsymbol{h}}\in\mathbb{N}_{0}^{d}:{\boldsymbol{h}}\leq{\boldsymbol{k}}\big{\\}},\quad{\mathcal{C}}_{\boldsymbol{k}}:=\big{\\{}h_{j}e_{j}:0\leq
h_{j}\leq
k_{j}\big{\\}},\quad{\mathcal{S}}_{{\boldsymbol{w}},u}:=\left\\{{\boldsymbol{h}}\in\mathbb{N}_{0}^{d}:\sum_{j=1}^{d}w_{j}h_{j}\leq
u\right\\}.\end{array}$

The first two sets are parameterized by
${\boldsymbol{k}}\in\mathbb{N}_{0}^{d}$ while the latest one by weights
$w_{1},\dots,w_{d}>0$ and upper bound $u>0$. These sets are isotropic if
${\boldsymbol{k}}$ (resp. ${\boldsymbol{w}}$) is a multiple of
${\boldsymbol{1}}$. These sets in dimension 2 are illustrated in figure 1.

###  5.2. Maximal and extremal elements

We say that ${\boldsymbol{k}}$ is a maximal element of $\Lambda$ lower if it
is maximal w.r.t. the partial order $\leq$, i.e. ${\boldsymbol{h}}\in\Lambda$
and ${\boldsymbol{k}}\leq{\boldsymbol{h}}$ $\Longrightarrow$
${\boldsymbol{h}}={\boldsymbol{k}}$. This is also equivalent to
${\boldsymbol{k}}+e_{i}\not\in\Lambda$ for all $i=1,\dots,d$. We say that
${\boldsymbol{k}}$ is an extremal element of $\Lambda$ if ${\boldsymbol{k}}$
can not be the midpoint of two distinct multi-indices from $\Lambda$, i.e.

(5.4) $2{\boldsymbol{k}}={\boldsymbol{h}}+{\boldsymbol{h}}^{\prime}\quad\text{
and
}\quad{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in\Lambda\quad\quad\Longrightarrow\quad\quad{\boldsymbol{h}}={\boldsymbol{h}}^{\prime}={\boldsymbol{k}}.$

The element ${\boldsymbol{0}}$ is clearly extremal. It is also obvious that if
${\boldsymbol{k}}+e_{j}\in\Lambda$ for some
$j\in\operatorname{supp}({\boldsymbol{k}})$, then ${\boldsymbol{k}}$ is not
extremal in $\Lambda$. We denote by ${\mathcal{E}}(\Lambda)$ (resp.
${\mathcal{E}}_{\leq}(\Lambda)$) the set of extremal (resp. maximal) elements
of $\Lambda$.

We also introduce notation ${\mathcal{K}}(\Lambda)$ for the elements that are
maximal along canonical directions, i.e.
${\boldsymbol{k}}\in{\mathcal{K}}(\Lambda)$ if and only if
${\boldsymbol{k}}=ke_{j}\in\Lambda$ for some $k\geq 1$ but
${\boldsymbol{k}}+e_{j}\not\in\Lambda$. We note that ${\mathcal{K}}(\Lambda)$
is not necessarily contained in ${\mathcal{E}}_{\leq}(\Lambda)$. Also, a
maximal element is not necessarily extremal, however maximal element along
canonical directions are.

Any finite lower set has at least one maximal element, and is completely
determined by them, i.e.

(5.5) $\Lambda=\bigcup_{{\boldsymbol{k}}\leavevmode\nobreak\
maximal\leavevmode\nobreak\ in\leavevmode\nobreak\
\Lambda}{\mathcal{B}}_{\boldsymbol{k}}\;.$

The maximal elements in block/cross/simplex type sets are explicit, i.e.

(5.6)
$\begin{array}[]{c}{\mathcal{E}}_{\leq}({\mathcal{B}}_{\boldsymbol{k}})=\big{\\{}{\boldsymbol{k}}\big{\\}},\quad{\mathcal{E}}_{\leq}({\mathcal{C}}_{\boldsymbol{k}})=\big{\\{}k_{j}e_{j}:j\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ k_{j}\geq 1\big{\\}},\\\
{\mathcal{E}}_{\leq}({\mathcal{S}}_{{\boldsymbol{w}},u})=\left\\{{\boldsymbol{h}}:u-\min_{i}(w_{i})<\sum_{j=1}^{d}w_{j}h_{j}\leq
u\right\\},\end{array}$

as well as maximal along canonical directions, i.e.

(5.7)
$\begin{array}[]{ccc}{\mathcal{K}}({\mathcal{B}}_{\boldsymbol{k}})={\mathcal{K}}({\mathcal{C}}_{\boldsymbol{k}})={\mathcal{E}}_{\leq}({\mathcal{C}}_{\boldsymbol{k}})&\text{
and }&{\mathcal{K}}({\mathcal{S}}_{{\boldsymbol{w}},u})=\big{\\{}\lfloor
u/w_{j}\rfloor e_{j}:j\leavevmode\nobreak\ s.t.\leavevmode\nobreak\ w_{j}\leq
u\big{\\}}.\end{array}$

In particular
${\mathcal{E}}_{\leq}({\mathcal{S}}_{{\boldsymbol{1}},k})=\\{{\boldsymbol{h}}\in\mathbb{N}_{0}^{d}:\sum_{j=1}^{d}h_{j}=k\\}$
and
${\mathcal{K}}({\mathcal{S}}_{{\boldsymbol{1}},k})=\\{ke_{j}:j=1,\dots,d\\}$.

The extremal elements are straightforward for ${\mathcal{B}}_{\boldsymbol{k}}$
and ${\mathcal{C}}_{\boldsymbol{k}}$, i.e.

(5.8)
$\begin{array}[]{c}{\mathcal{E}}({\mathcal{B}}_{\boldsymbol{k}})=\big{\\{}{\boldsymbol{h}}:h_{j}=0\leavevmode\nobreak\
or\leavevmode\nobreak\
h_{j}=k_{j}\big{\\}},\quad{\mathcal{E}}({\mathcal{C}}_{\boldsymbol{k}})=\big{\\{}{\boldsymbol{0}}\big{\\}}\cup{\mathcal{E}}_{\leq}({\mathcal{C}}_{\boldsymbol{k}}).\end{array}$

For simplex-type sets ${\mathcal{S}}_{{\boldsymbol{w}},u}$, we have
${\mathcal{E}}({\mathcal{S}}_{{\boldsymbol{w}},u})=\\{{\boldsymbol{0}}\\}\cup{\mathcal{K}}({\mathcal{S}}_{{\boldsymbol{w}},u})\cup{\mathcal{E}}^{(2)}({\mathcal{S}}_{{\boldsymbol{w}},u})$,
where ${\mathcal{E}}^{(2)}({\mathcal{S}}_{{\boldsymbol{w}},u})$ consists on
extremal elements with at least 2 non-zero components. The characterization of
this set is somewhat technical, we simply note the following plain inclusion,
if
${\boldsymbol{h}}\in{\mathcal{E}}^{(2)}({\mathcal{S}}_{{\boldsymbol{w}},u})$
then

(5.9) $u-\delta<\sum_{j=1}^{d}w_{j}h_{j}\leq
u,\quad\quad\quad\delta=\max_{i}(w_{i})-\min_{i}(w_{i}).$

Indeed, if ${\boldsymbol{h}}\in\mathbb{N}^{d}$ has two non-zero components,
say $h_{i},h_{j}\geq 1$, we can write
${\boldsymbol{h}}={\boldsymbol{k}}+{\boldsymbol{k}}^{\prime}$ where
${\boldsymbol{k}}={\boldsymbol{h}}+(e_{i}-e_{j})$ and
${\boldsymbol{k}}^{\prime}={\boldsymbol{h}}+(e_{j}-e_{i})$. We have that
${\boldsymbol{k}}\neq{\boldsymbol{k}}^{\prime}\in\mathbb{N}^{d}$ and
$\langle{\boldsymbol{w}},{\boldsymbol{k}}\rangle=\langle{\boldsymbol{w}},{\boldsymbol{h}}\rangle+(w_{i}-w_{j})$,
$\langle{\boldsymbol{w}},{\boldsymbol{k}}^{\prime}\rangle=\langle{\boldsymbol{w}},{\boldsymbol{h}}\rangle+(w_{j}-w_{i})$.
In particular, if $\langle{\boldsymbol{w}},{\boldsymbol{h}}\rangle\leq
u-\delta$, then
$\langle{\boldsymbol{w}},{\boldsymbol{k}}\rangle,\langle{\boldsymbol{w}},{\boldsymbol{k}}^{\prime}\rangle\leq
u$, implying that ${\boldsymbol{h}}$ is not extremal in
${\mathcal{S}}_{{\boldsymbol{w}},u}$. We note that $\delta$ in (5.9) can be
replaced by $\delta_{{\boldsymbol{h}}}=\min_{i\neq j}(|w_{i}-w_{j}|)$ with
minimization carried over $i,j\in\operatorname{supp}({\boldsymbol{h}})$.

The same above discussion applied to isotropic simplex, for which $\delta=0$,
implies

(5.10)
${\mathcal{E}}({\mathcal{S}}_{{\boldsymbol{1}},k})=\\{{\boldsymbol{0}}\\}\cup{\mathcal{K}}({\mathcal{S}}_{{\boldsymbol{1}},k}).$

###  5.3. Sum of lower sets

It is clear that lower structure is preserved by union and intersection.
Furthermore, we have the following.

######  Proposition 5.2.

Let $\Lambda,\Lambda^{\prime}\subset\mathbb{N}_{0}^{d}$ be two lower sets.
Then
$\Lambda\oplus\Lambda^{\prime}=\\{{\boldsymbol{h}}+{\boldsymbol{k}}:{\boldsymbol{h}}\in\Lambda,{\boldsymbol{k}}\in\Lambda^{\prime}\\}$
is also lower. Moreover

(5.11)
${\mathcal{M}}(\Lambda\oplus\Lambda^{\prime})={\mathcal{M}}(\Lambda)\oplus{\mathcal{M}}(\Lambda^{\prime}).$

###### Proof.

First, it is easy to verify that
${\mathcal{B}}_{\boldsymbol{h}}\oplus{\mathcal{B}}_{\boldsymbol{k}}={\mathcal{B}}_{{\boldsymbol{h}}+{\boldsymbol{k}}}$.
It is easily verified that $\oplus$ distributes $\cup$, hence
$\Lambda\oplus\Lambda^{\prime}=(\cup_{{\boldsymbol{h}}\in\Lambda}{\mathcal{B}}_{\boldsymbol{h}})\oplus(\cup_{{\boldsymbol{k}}\in\Lambda^{\prime}}{\mathcal{B}}_{\boldsymbol{k}})=\cup_{{\boldsymbol{h}}\in\Lambda,{\boldsymbol{k}}\in\Lambda^{\prime}}{\mathcal{B}}_{{\boldsymbol{h}}+{\boldsymbol{k}}}$
is indeed lower. The proof shows incidentally that
${\mathcal{E}}_{\leq}(\Lambda\oplus\Lambda^{\prime})\subset{\mathcal{E}}_{\leq}(\Lambda)\oplus{\mathcal{E}}_{\leq}(\Lambda^{\prime})$.
Now, given
${\boldsymbol{h}}+{\boldsymbol{h}}^{\prime}\in\Lambda\oplus\Lambda^{\prime}$
and $s\in\\{-1,1\\}^{d}$, the multi-index
${\boldsymbol{k}}=s\otimes({\boldsymbol{h}}+{\boldsymbol{h}}^{\prime})=(s_{1}(h_{1}+h_{1}^{\prime}),\dots,s_{d}(h_{d}+h_{d}^{\prime}))$
satisfies
${\boldsymbol{k}}=s\otimes{\boldsymbol{h}}+s\otimes{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda)\oplus{\mathcal{M}}(\Lambda^{\prime})$.
As a result
${\mathcal{M}}(\Lambda\oplus\Lambda^{\prime})\subset{\mathcal{M}}(\Lambda)\oplus{\mathcal{M}}(\Lambda^{\prime})$.
Inversely, we consider ${\boldsymbol{k}}\in{\mathcal{M}}(\Lambda)$, and
${\boldsymbol{k}}^{\prime}\in{\mathcal{M}}(\Lambda^{\prime})$. We define
${\boldsymbol{h}}$ and ${\boldsymbol{h}}^{\prime}$ in $\mathbb{N}^{d}$ by the
following

$\bullet$ $h_{j}=|k_{j}|$ and $h_{j}^{\prime}=|k_{j}^{\prime}|$ if $k_{j}$ and
$k_{j}^{\prime}$ have the same signs, otherwise

$\bullet$ $h_{j}=|k_{j}+k_{j}^{\prime}|$ and $h_{j}^{\prime}=0$ if
$|k_{j}|\geq|k_{j}^{\prime}|$, or $h_{j}=0$ and
$h_{j}^{\prime}=|k_{j}+k_{j}^{\prime}|$ if $|k_{j}|<|k_{j}^{\prime}|$.
By construction, we have
$|{\boldsymbol{k}}+{\boldsymbol{k}}^{\prime}|={\boldsymbol{h}}+{\boldsymbol{h}}^{\prime}$
with ${\boldsymbol{h}}\leq|{\boldsymbol{k}}|$ and
${\boldsymbol{h}}^{\prime}\leq|{\boldsymbol{k}}^{\prime}|$. Since $\Lambda$
and $\Lambda^{\prime}$ are lower, then ${\boldsymbol{h}}$ belongs to $\Lambda$
and ${\boldsymbol{h}}^{\prime}$ belongs to $\in\Lambda^{\prime}$, implying
that $|{\boldsymbol{k}}+{\boldsymbol{k}}^{\prime}|$ belongs to
$\Lambda\oplus\Lambda$. Therefore ${\boldsymbol{k}}+{\boldsymbol{k}}^{\prime}$
belongs to ${\mathcal{M}}(\Lambda\oplus\Lambda)$. The proof is complete. ∎

As mentioned above, the sum $\oplus$ of block-type sets is plain, i.e.
${\mathcal{B}}_{\boldsymbol{h}}\oplus{\mathcal{B}}_{\boldsymbol{k}}={\mathcal{B}}_{{\boldsymbol{h}}+{\boldsymbol{k}}}$.
For cross-type sets, we have
${\mathcal{C}}_{\boldsymbol{h}}\oplus{\mathcal{C}}_{\boldsymbol{k}}=\cup_{1\leq
i,j\leq d}\leavevmode\nobreak\ {\mathcal{B}}_{h_{i}e_{i}+k_{j}e_{j}}$. As for
simplex-type sets,

(5.12)
${\mathcal{S}}_{{\boldsymbol{w}},u_{1}+u_{2}-\max_{i}(w_{i})}\subset{\mathcal{S}}_{{\boldsymbol{w}},u_{1}}\oplus{\mathcal{S}}_{{\boldsymbol{w}},u_{2}}\subset{\mathcal{S}}_{{\boldsymbol{w}},u_{1}+u_{2}}.$

The inclusion in ${\mathcal{S}}_{{\boldsymbol{w}},u_{1}+u_{2}}$ is obvious,
and given
${\boldsymbol{h}}\in{\mathcal{S}}_{{\boldsymbol{w}},u_{1}+u_{2}-\max_{i}(w_{i})}$,
then either ${\boldsymbol{h}}\in{\mathcal{S}}_{{\boldsymbol{w}},u_{2}}$ or
${\boldsymbol{h}}\in{\mathcal{S}}_{{\boldsymbol{w}},u_{1}}$ or
$\sum_{i}h_{i}w_{i}>\max(u_{1},u_{2})$. In the latter case, we write
${\boldsymbol{h}}={\boldsymbol{k}}+({\boldsymbol{h}}-{\boldsymbol{k}})$ where
${\boldsymbol{k}}$ defined by ${\boldsymbol{k}}\leq{\boldsymbol{h}}$ and
having the closest value $\langle{\boldsymbol{k}},{\boldsymbol{w}}\rangle$ to
$u_{1}$ from below, then use
$\langle{\boldsymbol{k}},{\boldsymbol{w}}\rangle>u_{1}-\max_{i}(w_{i})$ in
order to imply
$\langle{\boldsymbol{h}}-{\boldsymbol{k}},{\boldsymbol{w}}\rangle\leq u_{2}$.
The same reasoning yields to
${\mathcal{S}}_{{\boldsymbol{1}},k_{1}}\oplus{\mathcal{S}}_{{\boldsymbol{1}},k_{2}}={\mathcal{S}}_{{\boldsymbol{1}},k_{1}+k_{2}}$
for any $k_{1},k_{2}\in\mathbb{N}$.

Next, we establish an inequality for lower sets in terms of the size of their
mirrored and sum sets.

######  Proposition 5.3.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ a finite lower set. There holds

(5.13)
$\\#({\mathcal{M}}(\Lambda))=\sum_{{\boldsymbol{k}}\in\Lambda}2^{|{\boldsymbol{k}}|_{0}}\leq\\#(\Lambda\oplus\Lambda).$

Equality holds if and only if $\Lambda={\mathcal{B}}_{{\boldsymbol{k}}}$ for
some ${\boldsymbol{k}}\in\mathbb{N}_{0}^{d}$.

###### Proof.

For a multi-index ${\boldsymbol{k}}\in\mathbb{N}_{0}^{d}$, we let ${\rm
supp}({\boldsymbol{k}})$ be the support of ${\boldsymbol{k}}$, which is the
subset of $\\{1,\dots,d\\}$ consisting of $j$ s.t. $k_{j}\neq 0$. We define
${\mathcal{D}}_{{\boldsymbol{k}}}$ to be the set of
$\varepsilon\in\\{0,1\\}^{d}$ satisfying ${\rm supp}(\varepsilon)\subset{\rm
supp}({\boldsymbol{k}})$. We then consider a set-valued map over
$\mathbb{N}_{0}^{d}$ by

$F:{\boldsymbol{k}}\longmapsto\\{2{\boldsymbol{k}}-\varepsilon\\}_{\varepsilon\in{\mathcal{D}}_{{\boldsymbol{k}}}}.$

This map satisfies $F({\boldsymbol{k}})\cap
F({\boldsymbol{k}}^{\prime})=\emptyset$ if
${\boldsymbol{k}}\neq{\boldsymbol{k}}^{\prime}$. First, it is easily verified
$F({\boldsymbol{0}})=\\{{\boldsymbol{0}}\\}$ and ${\boldsymbol{0}}$ does not
belong to any other $F({\boldsymbol{k}})$. If we are given
${\boldsymbol{k}},{\boldsymbol{k}}^{\prime}\in\mathbb{N}_{0}^{d}-\\{{\boldsymbol{0}}\\}$
s.t. $F({\boldsymbol{k}})\cap F({\boldsymbol{k}}^{\prime})\neq\emptyset$, then
for some $\varepsilon\in{\mathcal{D}}_{{\boldsymbol{k}}}$ and
$\varepsilon^{\prime}\in{\mathcal{D}}_{{\boldsymbol{k}}^{\prime}}$ we must
have
$2{\boldsymbol{k}}-\varepsilon=2{\boldsymbol{k}}^{\prime}-\varepsilon^{\prime}$.
But this implies
$2({\boldsymbol{k}}-{\boldsymbol{k}}^{\prime})=\varepsilon-\varepsilon^{\prime}$
belongs to $\\{-1,0,1\\}^{d}$, which is possible only if
${\boldsymbol{k}}-{\boldsymbol{k}}^{\prime}={\boldsymbol{0}}$. Now, given
$\Lambda$ lower, we have for any ${\boldsymbol{k}}\in\Lambda$ and any
$\varepsilon\in{\mathcal{D}}_{{\boldsymbol{k}}}$ that
$2{\boldsymbol{k}}-\varepsilon={\boldsymbol{k}}+({\boldsymbol{k}}-\varepsilon)$
belongs to $\Lambda\oplus\Lambda$. Therefore
$\cup_{{\boldsymbol{k}}\in\Lambda}F({\boldsymbol{k}})\subset\Lambda\oplus\Lambda$.
This combined with empty intersection property implies

$\\#(\Lambda\oplus\Lambda)\geq\sum_{{\boldsymbol{k}}\in\Lambda}\\#(\\{2{\boldsymbol{k}}-\varepsilon\\}_{\varepsilon\in{\mathcal{D}}_{{\boldsymbol{k}}}})=\sum_{{\boldsymbol{k}}\in\Lambda}\\#({\mathcal{D}}_{{\boldsymbol{k}}})=\sum_{{\boldsymbol{k}}\in\Lambda}2^{|{\boldsymbol{k}}|_{0}}=\\#({\mathcal{M}}(\Lambda)).$

The first part of the proposition is complete. We note that
$F(\Lambda):=\cup_{{\boldsymbol{k}}\in\Lambda}F({\boldsymbol{k}})$ has an
explicit formula for $\Lambda$ a lower set, i.e.
$F(\Lambda)=\cup_{{\boldsymbol{k}}\in\Lambda}{\mathcal{B}}_{2{\boldsymbol{k}}}=\cup_{{\boldsymbol{k}}\in\Lambda\text{
maximal }}{\mathcal{B}}_{2{\boldsymbol{k}}}$. On the other hand, we have
$\Lambda\oplus\Lambda=\cup_{{\boldsymbol{h}},{\boldsymbol{k}}\in\Lambda}{\mathcal{B}}_{{\boldsymbol{h}}+{\boldsymbol{k}}}=\cup_{{\boldsymbol{h}},{\boldsymbol{k}}\in\Lambda\text{
maximal }}{\mathcal{B}}_{{\boldsymbol{h}}+{\boldsymbol{k}}}$. Clearly,
equality holds for block-type sets, with
$F({\mathcal{B}}_{\boldsymbol{h}})={\mathcal{B}}_{2{\boldsymbol{h}}}={\mathcal{B}}_{{\boldsymbol{h}}}\oplus{\mathcal{B}}_{{\boldsymbol{h}}}$.
In general, it seems unlikely that for all pairs
$({\boldsymbol{i}},{\boldsymbol{j}})$ of maximal elements of $\Lambda$, one
has ${\boldsymbol{i}}+{\boldsymbol{j}}\subset F(\Lambda)$. We give a proof to
this observation.

We let $\Lambda$ be lower not of block-type and assume
$\Lambda\oplus\Lambda=F(\Lambda)$. Let
${\boldsymbol{i}}^{(1)},\dots,{\boldsymbol{i}}^{(m)}$ be its maximal elements
ordered in lexicographical order, ${\boldsymbol{h}}\leq_{L}{\boldsymbol{k}}$
if and only if $h_{1}<k_{1}$ or ($h_{1}=k_{1}$ and
$\widehat{\boldsymbol{h}}\leq_{L}\widehat{\boldsymbol{k}}$) where
$\widehat{\boldsymbol{x}}=(x_{2},\dots,x_{d})$. By the assumption
$\Lambda\oplus\Lambda=F(\Lambda)$, we must have
${\boldsymbol{i}}^{(m-1)}+{\boldsymbol{i}}^{(m)}\leq 2{\boldsymbol{i}}^{(n)}$
for some $n\in\\{1,\dots,m\\}$. We can not have $n=m-1$ or $n=m$ since maximal
elements are not comparable. If $m=2$, we reach already a contradiction. We
assume that $m\geq 3$ and use notation $\nu={\boldsymbol{i}}^{(m-1)}$,
$\mu={\boldsymbol{i}}^{(m)}$, $\lambda={\boldsymbol{i}}^{(n)}$, hence
$\nu+\mu\leq 2\lambda$. Using the lexicographical order assumption, at
position $1$ we must have $\lambda_{1}\leq\nu_{1}$ and
$\lambda_{1}\leq\mu_{1}$, hence $2\lambda_{1}\leq\nu_{1}+\mu_{1}$. If one of
the first inequalities is strict, we get $2\lambda_{1}<\nu_{1}+\mu_{1}$
contradicting $\nu+\mu\leq 2\lambda$. Re-iterating this argument shows that we
must have $\lambda_{j}=\nu_{j}$ and $\lambda_{j}=\mu_{j}$ for all $j$. We
again reach a contradiction. The proof is complete. ∎

With little extra effort, we identify a map that allows to embed
${\mathcal{M}}(\Lambda)$ into $\Lambda\oplus\Lambda$ for any lower set
$\Lambda$. In view of the application $F$ defined in the proof, the following
map is suited

(5.14) ${\boldsymbol{k}}\in\mathbb{Z}\mapsto 2|{\boldsymbol{k}}|-{\bf
1}_{{\boldsymbol{k}}<{\boldsymbol{0}}}\in\mathbb{N}_{0}^{d},$

where $|{\boldsymbol{k}}|$ is component-wise absolute value of
${\boldsymbol{k}}$ and ${\bf
1}_{{\boldsymbol{k}}<{\boldsymbol{0}}}\in\\{0,1\\}^{d}$ having ones in
positions $j$ s.t. $k_{j}<0$.

##  6\. Equivalence between reconstruction plans for lower sets

In this section, we establish some equivalence properties between
admissibility requirements (3.16), (3.21) (3.22) and (3.23) when $\Lambda$ is
lower and more particularly when $\Lambda$ is of simplex-type.

###  6.1. Equivalences for general lower sets

We start with the following result.

######  Proposition 6.1.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be a lower set, $n\in\mathbb{N}$, and
${\boldsymbol{z}}\in\mathbb{Z}^{d}$. The following assertions are equivalent:

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan 0 for $\Lambda\oplus\Lambda$,

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan A for $\Lambda$.

Indeed, we have by proposition 5.2 that
${\mathcal{M}}(\Lambda\oplus\Lambda)={\mathcal{M}}(\Lambda)\oplus{\mathcal{M}}(\Lambda)={\mathcal{M}}(\Lambda)\ominus{\mathcal{M}}(\Lambda)$.
In particular, ${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}0$ for all
${\boldsymbol{h}}\in{\mathcal{M}}(\Lambda\oplus\Lambda)\setminus\\{{\boldsymbol{0}}\\}$
is equivalent to
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all ${\boldsymbol{h}},{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda)$
s.t. ${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}$.

This next result is also straightforward.

######  Proposition 6.2.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be a lower set, $n\in\mathbb{N}$ and
${\boldsymbol{z}}\in\mathbb{Z}^{d}$. Then,

(6.1)
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in\Lambda\quad\quad\implies\quad\quad{\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}0\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)\setminus\\{0\\}.$

An equivalence holds if $\Lambda={\mathcal{B}}_{\boldsymbol{k}}$ for some
${\boldsymbol{k}}\in\mathbb{N}_{0}^{d}$.

###### Proof.

Given any ${\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)\setminus\\{0\\}$, we can
decompose it as ${\boldsymbol{h}}={\boldsymbol{h}}^{+}-{\boldsymbol{h}}^{-}$
where ${\boldsymbol{h}}^{+}=\max({\boldsymbol{h}},{\boldsymbol{0}})$ and
${\boldsymbol{h}}^{-}=\max(-{\boldsymbol{h}},{\boldsymbol{0}})$ both in
$\mathbb{N}^{d}$. Since
${\boldsymbol{h}}^{+},{\boldsymbol{h}}^{-}\leq|{\boldsymbol{h}}|$,
$|{\boldsymbol{h}}|\in\Lambda$, and $\Lambda$ is lower, then
${\boldsymbol{h}}^{+},{\boldsymbol{h}}^{-}\in\Lambda$. Also by construction
${\boldsymbol{h}}^{+}\neq{\boldsymbol{h}}^{-}$, and
${\boldsymbol{h}}^{-}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{+}\cdot{\boldsymbol{z}}$
implies ${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}0$. If
$\Lambda={\mathcal{B}}_{k}$, we use that
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in\Lambda$ is equivalent to
${\boldsymbol{0}}\neq({\boldsymbol{h}}-{\boldsymbol{h}}^{\prime})\in{\mathcal{M}}(\Lambda)$.
∎

The following results are more involved, however rely on the same techniques
as above. First, we address the equivalence between plans B and C, i.e.
requirements (3.22) and (3.23).

######  Proposition 6.3.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be a lower set, $n\in\mathbb{N}$, and
${\boldsymbol{z}}\in\mathbb{Z}^{d}$. The following assertions are equivalent:

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan B,

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan C and
$2{\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\ \not\equiv_{n}0$
for all ${\boldsymbol{h}}\in{\mathcal{E}}(\Lambda)\setminus\\{0\\}$.

Moreover, if $n$ is odd, the last assumption is not needed.

###### Proof.

It is immediate that plan B admissibility does imply plan C admissibility and
does imply that ${\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\
\not\equiv_{n}-{\boldsymbol{h}}\cdot{\boldsymbol{z}}$ for all
${\boldsymbol{h}}\in\Lambda\setminus\\{{\boldsymbol{0}}\\}$, see Remark 3.5.
As for the other implication, we use proof by contradiction. We assume that
$(n,{\boldsymbol{z}})$ is admissible for plan C and satisfies the identity but
$(n,{\boldsymbol{z}})$ is not admissible for plan B. In view of Remark 3.5,
there must exist ${\boldsymbol{h}}\in\Lambda\setminus\\{{\boldsymbol{0}}\\}$
and $\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}^{*}$ such that
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}$.
We have that
$\sigma({\boldsymbol{h}})={\boldsymbol{h}}^{+}-{\boldsymbol{h}}^{-}$ and
${\boldsymbol{h}}={\boldsymbol{h}}^{+}+{\boldsymbol{h}}^{-}$ where
${\boldsymbol{h}}^{+}=\max(\sigma({\boldsymbol{h}}),{\boldsymbol{0}})$ and
${\boldsymbol{h}}^{-}=\max(-\sigma({\boldsymbol{h}}),{\boldsymbol{0}})$ both
in $\mathbb{N}^{d}_{0}$. Let us note that
${\boldsymbol{h}}^{-}\neq{\boldsymbol{0}}$, since
${\boldsymbol{h}}^{-}={\boldsymbol{0}}$ is only possible if $\sigma=id$ which
is excluded. The equality
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}$
is reformulated

$2{\boldsymbol{h}}^{-}\cdot{\boldsymbol{z}}\equiv_{n}0\equiv_{n}{\boldsymbol{0}}\cdot{\boldsymbol{z}}.$

In particular, if $2{\boldsymbol{h}}^{-}\in\Lambda$ we reach a contradiction.
In general, since $\Lambda$ is lower then ${\boldsymbol{h}}^{-}\in\Lambda$. If
${\boldsymbol{h}}^{-}\not\in{\mathcal{E}}(\Lambda)$, then
$2{\boldsymbol{h}}^{-}={\boldsymbol{k}}+{\boldsymbol{k}}^{\prime}$ for some
${\boldsymbol{k}}\neq{\boldsymbol{k}}^{\prime}\in\Lambda$. Then
$2{\boldsymbol{h}}^{-}\cdot{\boldsymbol{z}}\equiv_{n}0$ implies
${\boldsymbol{k}}\cdot{\boldsymbol{z}}=-{\boldsymbol{k}}^{\prime}\cdot{\boldsymbol{z}}$,
which contradicts plan C admissibility. The proof of the equivalence is
complete. If $n$ is odd, then
$2{\boldsymbol{h}}^{-}\cdot{\boldsymbol{z}}\not\equiv_{n}0$ is equivalent to
${\boldsymbol{h}}^{-}\cdot{\boldsymbol{z}}\not\equiv_{n}0$, but this is
already incorporated in plan C admissibility since
${\boldsymbol{0}}\neq{\boldsymbol{h}}^{-}\in\Lambda$. The proof is complete.

∎

In general, the requirement
$2{\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\ \not\equiv_{n}0$
for all ${\boldsymbol{h}}\in{\mathcal{E}}(\Lambda)\setminus\\{0\\}$ seems
quite involved since its entails identifying the set of extremal elements
${\mathcal{E}}(\Lambda)$. One can therefore always favor searching for $n$
odd. Since $n^{*}_{C}(\Lambda)\leq n^{*}_{B}(\Lambda)$ and
$n^{*}_{C}(\Lambda,{\boldsymbol{z}})\leq n^{*}_{B}(\Lambda,{\boldsymbol{z}})$
for any set $\Lambda\subset\mathbb{N}_{0}^{d}$ and for any ${\boldsymbol{z}}$,
the following holds when we choose $\Lambda$ to be a lower set,

  * •

$n^{*}_{C}(\Lambda,{\boldsymbol{z}})$ is odd $\implies$
$n^{*}_{B}(\Lambda,{\boldsymbol{z}})=n^{*}_{C}(\Lambda,{\boldsymbol{z}})$,

  * •

$n^{*}_{C}(\Lambda)$ is odd $\implies$
$n^{*}_{B}(\Lambda)=n^{*}_{C}(\Lambda)$.

######  Remark 6.4.

In the general case, we cannot ensure $n^{*}_{C}(\Lambda)=n^{*}_{B}(\Lambda)$,
as per the case $\Lambda=\\{0,1\\}$, which is a lower set in dimension $1$.
For plan C, we need $z\not\equiv_{n}0$, hence $(n=2,{\boldsymbol{z}}=1)$ is
admissible and $n^{*}_{C}(\Lambda)=2$. For plan B, we need $z\not\equiv_{n}0$
and $z\not\equiv_{n}-z$ which implies that $(n=3,{\boldsymbol{z}}=1)$ is
admissible and $n^{*}_{B}(\Lambda)=3$.

######  Remark 6.5.

Given any $\Lambda\subset\mathbb{N}_{0}^{d}$ lower and $n\in\mathbb{N}$ odd,
having
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}$
for some
${\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)$ both
belonging to the same ${\mathcal{S}}_{\boldsymbol{k}}$ is equivalent to
$\widetilde{\boldsymbol{h}}\cdot{\boldsymbol{z}}\equiv_{n}0$ where
$\widetilde{\boldsymbol{h}}\neq{\boldsymbol{0}}$ is defined by
$\widetilde{h}_{j}=k_{j}$ if $h_{j}^{\prime}=-h_{j}$ and $\widetilde{h}_{j}=0$
otherwise. Since $\widetilde{\boldsymbol{h}}\in\Lambda$, this is ruled out if
plan C admissibility is assumed. In light of this observation, the table of
Remark 3.5 can be simplified for $\Lambda$ lower and $n\in\mathbb{N}$ odd to

$\begin{array}[]{|l l|c|c|c|}\hline\cr\text{Requirement}&&\text{C}&\text{
B}&\text{A}\\\
\hline\cr{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}&\quad{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda,\leavevmode\nobreak\
\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}&\checkmark&\checkmark&\checkmark\\\
{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}&\quad{\boldsymbol{h}}^{\prime},{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda),|{\boldsymbol{h}}^{\prime}|\neq|{\boldsymbol{h}}|&&&\checkmark\\\
\hline\cr\end{array}$

###  6.2. Equivalence for the isotropic simplex-type sets

We now specialize to simplex-type sets. For these sets, minimal conditions are
required in order to have equivalence between plans. First, for
${\mathcal{S}}_{{\boldsymbol{1}},k}$ by simply combining Proposition 6.3 with
the fact that
${\mathcal{E}}({\mathcal{S}}_{{\boldsymbol{1}},k})\setminus\\{{\boldsymbol{0}}\\}={\mathcal{K}}({\mathcal{S}}_{{\boldsymbol{1}},k})=\\{ke_{j}:j=1,\dots,d\\}$,
see (5.10), we have the equivalence between these two assertions:

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan B,

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan C and $2kz_{j}\not\equiv_{n}0$
for all $j=1,\dots,d$,

with the last assumption not needed if $n$ is odd. A stronger result actually
holds.

######  Proposition 6.6.

Let $k,n\in\mathbb{N}$, and ${\boldsymbol{z}}\in\mathbb{Z}^{d}$. For
$\Lambda={\mathcal{S}}_{{\boldsymbol{1}},k}$, the following assertions are
equivalent:

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan A

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan B

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan C and $2kz_{j}\not\equiv_{n}0$
for all $j=1,\dots,d$.

Moreover, if $n$ is odd, the last assumption is not needed.

###### Proof.

The forward implications are immediate. We only need to prove the reciprocate
ones. We assume $(n,{\boldsymbol{z}})$ is admissible for plan C and satisfies
the identity, but not admissible for plan A. Let
${\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in{\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k})$
be s.t.
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}$.
We decompose ${\boldsymbol{h}}={\boldsymbol{h}}^{+}-{\boldsymbol{h}}^{-}$ and
${\boldsymbol{h}}^{\prime}={\boldsymbol{h}}^{\prime+}-{\boldsymbol{h}}^{\prime-}$,
leading to
${\boldsymbol{k}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{k}}^{\prime}\cdot{\boldsymbol{z}}$
where ${\boldsymbol{k}}={\boldsymbol{h}}^{+}+{\boldsymbol{h}}^{\prime-}$ and
${\boldsymbol{k}}^{\prime}={\boldsymbol{h}}^{\prime+}+{\boldsymbol{h}}^{-}$,
which both belong to $\mathbb{N}_{0}^{d}$ and satisfy
${\boldsymbol{k}}\neq{\boldsymbol{k}}^{\prime}$. Also, up to subtract
$\min({\boldsymbol{k}},{\boldsymbol{k}}^{\prime})$ from ${\boldsymbol{k}}$ and
${\boldsymbol{k}}^{\prime}$, and swap them if necessary, we may assume that
$\operatorname{supp}({\boldsymbol{k}})\cap\operatorname{supp}({\boldsymbol{k}}^{\prime})=\emptyset$
and
$\|{\boldsymbol{k}}\|_{\ell_{1}}\leq\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}}$.
We have

$2\|{\boldsymbol{k}}\|_{\ell_{1}}\leq\|{\boldsymbol{k}}\|_{\ell_{1}}+\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}}=\|{\boldsymbol{h}}\|_{\ell_{1}}+\|{\boldsymbol{h}}^{\prime}\|_{\ell_{1}}\leq
2k,$

hence ${\boldsymbol{k}}\in{\mathcal{S}}_{{\boldsymbol{1}},k}$. If
${\boldsymbol{k}}^{\prime}\in{\mathcal{S}}_{{\boldsymbol{1}},k}$, we reach a
contradiction with plan C admissibility. We consider the case
${\boldsymbol{k}}^{\prime}\not\in{\mathcal{S}}_{{\boldsymbol{1}},k}$, namely
$\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}}>k$. Without loss of generality, we
assume that $\operatorname{supp}({\boldsymbol{k}}^{\prime})=\\{1,\dots,J\\}$.
We then let ${\boldsymbol{y}}={\boldsymbol{k}}$ and
${\boldsymbol{y}}^{\prime}={\boldsymbol{k}}^{\prime}$, loop over $j=1,\dots,J$
and within every loop, while $\|{\boldsymbol{y}}^{\prime}\|_{\ell_{1}}>k$ do
${\boldsymbol{y}}\leftarrow{\boldsymbol{y}}-e_{j}$ and
${\boldsymbol{y}}^{\prime}\leftarrow{\boldsymbol{y}}^{\prime}-e_{j}$. This
procedure produces ${\boldsymbol{y}}\in\mathbb{Z}^{d}$ and
${\boldsymbol{y}}^{\prime}\in\mathbb{N}_{0}^{d}$ satisfying
$\|{\boldsymbol{y}}\|_{\ell_{1}}+\|{\boldsymbol{y}}^{\prime}\|_{\ell_{1}}=\|{\boldsymbol{k}}\|_{\ell_{1}}+\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}}$
and $\|{\boldsymbol{y}}^{\prime}\|_{\ell_{1}}=k$. In particular
${\boldsymbol{y}}\in{\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{1}},k})$ and
${\boldsymbol{y}}^{\prime}\in{\mathcal{S}}_{{\boldsymbol{1}},k}$. Since
${\boldsymbol{y}}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{y}}^{\prime}\cdot{\boldsymbol{z}}$,
then if $|{\boldsymbol{y}}|\neq{\boldsymbol{y}}^{\prime}$ we reach a
contradiction with plan C admissibility. We observe that
$|{\boldsymbol{y}}|\neq{\boldsymbol{y}}^{\prime}$ will always hold unless
$J=1$, ${\boldsymbol{k}}={\boldsymbol{0}}$ and
${\boldsymbol{k}}^{\prime}=2ke_{1}$.

In this case
${\boldsymbol{k}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{k}}\cdot{\boldsymbol{z}}$
is reformulated as $2kz_{1}\equiv_{n}0$,

hence a contradiction with the assumption on $k$ and ${\boldsymbol{z}}$.

When $n$ is odd, the assumption
$2kz_{1}\not\equiv_{n}0,\dots,2kz_{d}\not\equiv_{n}0$ reduces to
$kz_{1}\not\equiv_{n}$,…, $kz_{d}\not\equiv_{n}0$ which is incorporated in
plan C admissibility. The proof is complete. ∎

The arguments used in the proof can be used in order to simplify the
requirements. In the first case of the proof, i.e.
$\|{\boldsymbol{k}}\|_{\ell_{1}}\leq\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}}\leq
k$, we can define ${\boldsymbol{y}}={\boldsymbol{k}}+\delta e_{1}$ and
${\boldsymbol{y}}^{\prime}={\boldsymbol{k}}^{\prime}+\delta e_{1}$ with
$\delta=(k-\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}})$, so that
$\|{\boldsymbol{y}}^{\prime}\|_{\ell_{1}}=k$. This identity is also satisfied
with ${\boldsymbol{y}}^{\prime}$ produced by the procedure in the second case.
In view of this, we can verify that for
$\Lambda={\mathcal{S}}_{{\boldsymbol{1}},k}$, $(n,{\boldsymbol{z}})$ is
admissible for plan C if and only if

(6.2)
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}},\quad\mbox{for}\quad\begin{array}[]{c}{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda,\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\quad\quad\|{\boldsymbol{h}}^{\prime}\|_{\ell^{1}}=k.\end{array}$

Likewise, we can carry on the procedure updating ${\boldsymbol{y}}$ and
${\boldsymbol{y}}^{\prime}$, while
$\|{\boldsymbol{y}}^{\prime}\|_{\ell_{1}}>\|{\boldsymbol{y}}\|_{\ell_{1}}+1$,
instead of stopping when $\|{\boldsymbol{y}}^{\prime}\|_{\ell_{1}}=k$, and use
this as well if
$\|{\boldsymbol{k}}\|_{\ell_{1}}\leq\|{\boldsymbol{k}}^{\prime}\|_{\ell_{1}}\leq
k$. We establish that for $\Lambda={\mathcal{S}}_{{\boldsymbol{1}},k}$,
$(n,{\boldsymbol{z}})$ is admissible for plan C if and only if

(6.3)
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}},\quad\mbox{for}\quad\begin{array}[]{c}{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda,\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\quad\quad\|{\boldsymbol{h}}^{\prime}\|_{\ell^{1}}-\|{\boldsymbol{h}}\|_{\ell^{1}}\in\\{0,1\\}.\end{array}$

###  6.3. Equivalence for the anisotropic simplex-type sets

The techniques we have used in the proof of Proposition 6.6 can be re-examined
with general simplex-type sets. For $w_{1},\dots,w_{d}>0$, one has that
$\|{\boldsymbol{x}}\|_{{\boldsymbol{w}},\ell_{1}}:=\sum_{j=1}^{d}w_{j}|x_{j}|$
defines a norm over $\mathbb{R}^{d}$, and that
${\mathcal{S}}_{{\boldsymbol{w}},u}=\\{{\boldsymbol{k}}\in\mathbb{N}^{d}:\|{\boldsymbol{k}}\|_{{\boldsymbol{w}},\ell_{1}}\leq
u\\}$,
${\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{w}},u})=\\{{\boldsymbol{h}}\in\mathbb{Z}^{d}:\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell_{1}}\leq
u\\}$. The proof is unchanged if $\|\cdot\|_{\ell_{1}}$ is replaced by
$\|\cdot\|_{{\boldsymbol{w}},\ell_{1}}$ and $k$ is replaced by $u$, up until
we consider
${\boldsymbol{k}}^{\prime}\not\in{\mathcal{S}}_{{\boldsymbol{w}},u}$. Then we
distinguish two cases

  * •

$\|{\boldsymbol{k}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{k}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq
2u-\alpha$, and

  * •

$\|{\boldsymbol{k}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{k}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}>2u-\alpha$,

where
$\alpha=\max_{i\in\operatorname{supp}({\boldsymbol{k}}^{\prime})}(w_{i})$. In
the first case, the same procedure as the proof yields ${\boldsymbol{y}}$ and
${\boldsymbol{0}}\leq{\boldsymbol{y}}^{\prime}\leq{\boldsymbol{k}}^{\prime}$
satisfying
$u-\alpha<\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq u$,
and
$\|{\boldsymbol{y}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}=\|{\boldsymbol{k}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{k}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq
2u-\alpha$, hence $\|{\boldsymbol{y}}\|_{{\boldsymbol{w}},\ell_{1}}\leq u$.
Also $|{\boldsymbol{y}}|\neq{\boldsymbol{y}}^{\prime}$ unless $J=1$,
${\boldsymbol{k}}={\boldsymbol{0}}$ and ${\boldsymbol{k}}^{\prime}=2\lfloor
u/w_{1}\rfloor e_{1}$ assuming $w_{1}\leq u$. The second case originates in
the proof from ${\boldsymbol{h}}$ and ${\boldsymbol{h}}^{\prime}$ s.t.
$\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{h}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}>2u-\alpha$.

We introduce notation
$\alpha_{{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}}:=\max(w_{i})$ with
minimization carried over
$i\in\operatorname{supp}({\boldsymbol{h}})\cup\operatorname{supp}({\boldsymbol{h}}^{\prime})$.
In view of the above discussion, we identify the equivalence presented in the
following proposition.

######  Proposition 6.7.

Let $w_{1},\dots,w_{d},u>0$, and $n\in\mathbb{N}$,
${\boldsymbol{z}}\in\mathbb{Z}^{d}$. For
$\Lambda={\mathcal{S}}_{{\boldsymbol{w}},u}$, the following are equivalent:

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan A

  * •

$(n,{\boldsymbol{z}})$ is admissible for plan C, $2\lfloor u/w_{j}\rfloor
z_{j}\not\equiv_{n}0$ for $j$ s.t. $u\geq w_{j}$, and

(6.4)
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}\quad\mbox{for}\quad\begin{array}[]{c}{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)\quad\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{h}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}>2u-\alpha_{{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}}.\end{array}$

If $n$ is odd, the second assumption is not needed.

Characterizations such as (6.2) and (6.3) can be derived for general simplex-
type sets. We observe that if
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}}$
for some
${\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in{\mathcal{M}}({\mathcal{S}}_{{\boldsymbol{w}},u})$,
we may assume that
${\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{E}}_{\leq}({\mathcal{S}}_{{\boldsymbol{w}},u}))$.
Indeed, up to multiply by $-1$ and swap if necessary, we may assume
$\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell_{1}}\leq\|{\boldsymbol{h}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}$
and $h_{i}^{\prime}\geq 0$ where $i$ is s.t. $w_{i}$ is minimal among the
$w_{j}$. Then by considering ${\boldsymbol{y}}={\boldsymbol{h}}+\delta e_{i}$
and ${\boldsymbol{y}}^{\prime}={\boldsymbol{h}}^{\prime}+\delta e_{i}$ where
$\delta$ is the largest integer s.t.
$|{\boldsymbol{y}}^{\prime}|\in{\mathcal{S}}_{{\boldsymbol{w}},u}$, we obtain
$|{\boldsymbol{y}}^{\prime}|$ is maximal and
$\|{\boldsymbol{y}}\|_{{\boldsymbol{w}},\ell_{1}}\leq\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq
u$. We therefore have for $\Lambda={\mathcal{S}}_{{\boldsymbol{w}},u}$ that
$(n,{\boldsymbol{z}})$ is admissible for plan A if and only if

(6.5)
$\displaystyle{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}\cdot{\boldsymbol{z}},\quad\mbox{
for
}\quad{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda),\;\;{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}({\mathcal{E}}_{\leq}(\Lambda)),\;\;{\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}.$

In procedure we discussed above, if we carry on updating ${\boldsymbol{y}}$
and ${\boldsymbol{y}}^{\prime}$ while
$\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}-\|{\boldsymbol{y}}\|_{{\boldsymbol{w}},\ell_{1}}>\alpha$,
instead of stopping when
$\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq u$, we obtain
that
$|\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}-\|{\boldsymbol{y}}\|_{{\boldsymbol{w}},\ell_{1}}|\leq\alpha$,
also implying $\|{\boldsymbol{y}}\|_{{\boldsymbol{w}},\ell_{1}}\leq u$ and
$\|{\boldsymbol{y}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq u$. The other
case
$\|{\boldsymbol{k}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{k}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}>2u-\alpha$,
which results of
$\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell_{1}}+\|{\boldsymbol{h}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}>2u-\alpha$,
implies that ${\boldsymbol{h}}$ and ${\boldsymbol{h}}^{\prime}$ are
necessarily s.t.
$u-\alpha<\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell_{1}},\|{\boldsymbol{h}}^{\prime}\|_{{\boldsymbol{w}},\ell_{1}}\leq
u$. In particular, we identify that for sets
$\Lambda={\mathcal{S}}_{{\boldsymbol{w}},u}$, $(n,{\boldsymbol{z}})$ is
admissible for plan C if and only if

(6.6)
${\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\not\equiv_{n}\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}},\quad\mbox{
for
}\quad{\boldsymbol{h}}^{\prime}\neq{\boldsymbol{h}}\in\Lambda,\;\;\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}},\;\;\left|\|{\boldsymbol{h}}^{\prime}\|_{{\boldsymbol{w}},\ell^{1}}-\|{\boldsymbol{h}}\|_{{\boldsymbol{w}},\ell^{1}}\right|<\alpha_{{\boldsymbol{h}},{\boldsymbol{h}}^{\prime}}.$

##  7\. Specialized CBC construction

In this section, we introduce efficient numerical algorithms for determining
moderate values of $n$ and the generator vector ${\boldsymbol{z}}$ for any
given lower set $\Lambda$. Our algorithm offers substantial improvements over
current methods in both computation time and memory efficiency, making it
particularly effective for high-dimensional cases.

###  7.1. Exhaustive search

We let $\Lambda\subset\mathbb{N}_{0}^{d}$ be an arbitrary set of finite
cardinality and $(n,{\boldsymbol{z}})\in\mathbb{N}\times\mathbb{Z}^{d}$. We
recall that $(n,{\boldsymbol{z}})\in{\mathcal{P}}_{0}(\Lambda)$ iff (3.16)
holds. On the other hand, $(n,{\boldsymbol{z}})\in{\mathcal{P}}_{A}(\Lambda)$
(resp. $(n,{\boldsymbol{z}})\in{\mathcal{P}}_{B}(\Lambda)$,
$(n,{\boldsymbol{z}})\in{\mathcal{P}}_{C}(\Lambda)$) iff (3.21) holds (resp.
(3.22) holds, (3.23) holds).

The goal is to find a couple $(n,{\boldsymbol{z}})$ consisting in a small
integer $n$ and ${\boldsymbol{z}}\in\mathbb{Z}^{d}$ s.t.
$({\boldsymbol{z}},n)\in{\mathcal{P}}_{\square}(\Lambda)$ with $\square$ is a
placeholder for 0, A, B or C. Exhaustive search entails incrementally testing
all possible combinations of $n$ and ${\boldsymbol{z}}$
($\in\\{0,\dots,n-1\\}^{d}$) until the admissibility condition is met. A
unified implementation of the search is Algorithm 1.

Inputs: $\Lambda\subset\mathbb{N}^{d}$, and $n_{\rm lower}$, $n_{\rm upper}$
theoretical lower and upper bound on $n$

$n=n_{\rm lower}$

while $n\leq n_{\rm upper}$ do

for ${\boldsymbol{z}}\in\\{0,\dots,n-1\\}^{d}$ do

if $(n,{\boldsymbol{z}})\in{\mathcal{P}}_{\square}(\Lambda)$ then

return $n,{\boldsymbol{z}}$

end if

end for

Increment $n$ by 1

end while

Algorithm 1 Exhaustive search for optimal $n$ and an associated generator
${\boldsymbol{z}}$

Let us comment on the algorithm. In light of equations (3.24) and (4.4),
whatever the geometry of $\Lambda$, one has closed formulas for $n_{\rm
lower}$ and $n_{\rm upper}$. Checking whether
$(n,{\boldsymbol{z}})\in{\mathcal{P}}_{\square}(\Lambda)$ for $\Lambda$
entails iterating through elements ${\boldsymbol{h}}$ in
${\mathcal{M}}(\Lambda)$ and making sure that the inner products
${\boldsymbol{h}}\cdot{\boldsymbol{z}}$ satisfy a prescribed condition, as
summarized in Remark 3.5. More precisely

  * •

integral exactness: verify that
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}0$ if
${\boldsymbol{h}}\neq{\boldsymbol{0}}$,

  * •

reconstruction with plan A: verify that
$({\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\ {\rm
mod}\leavevmode\nobreak\ n)$ are pairwise distinct,

  * •

reconstruction with plans B/C: first list all
$({\boldsymbol{h}}\cdot{\boldsymbol{z}}\leavevmode\nobreak\ {\rm
mod}\leavevmode\nobreak\ n)$ for ${\boldsymbol{h}}$ in
${\mathcal{M}}(\Lambda)$, then

    * –

for plan B: iterate through ${\boldsymbol{h}}^{\prime}$ in $\Lambda$ and
verify that
$({\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\leavevmode\nobreak\ {\rm
mod}\leavevmode\nobreak\ n)$ has only been listed once.

    * –

for plan C: iterate through ${\boldsymbol{h}}^{\prime}$ in $\Lambda$ and
verify that
$({\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}\leavevmode\nobreak\ {\rm
mod}\leavevmode\nobreak\ n)$ has only been listed once, or else it was listed
from $\sigma({\boldsymbol{h}}^{\prime})$ for some
${\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}^{\prime}}^{*}}$.

###  7.2. Iterative procedure for lower sets

For lower sets $\Lambda$, the cost of the above verification step can be
optimized. We outline in this section how this is performed, but first
introduce some necessary notation in this regard.

Given $\Lambda\subset\mathbb{N}_{0}^{d}$ lower of finite cardinality, we
introduce the sets $\Lambda_{[1]},\dots,\Lambda_{[d]}$ by
$\Lambda_{[j]}:=\\{{\boldsymbol{h}}_{[j]}:{\boldsymbol{h}}\in\Lambda\\}$. The
lower property of $\Lambda$ implies that $\Lambda_{[j]}$ are also lower with
$\Lambda_{[j]}\times\\{0\\}\subset\Lambda_{[j+1]}$ for any $j=1,\dots,d-1$. It
does also imply the explicit characterization

(7.1)
$\Lambda_{[j]}=\\{{\boldsymbol{h}}\in\mathbb{N}_{0}^{j}:({\boldsymbol{h}},{\boldsymbol{0}})\in\Lambda\\},$

where $({\boldsymbol{h}},{\boldsymbol{0}})$ means extending ${\boldsymbol{h}}$
with $d-j$ zeros. Associated mirrored sets ${\mathcal{M}}(\Lambda_{[j]})$
satisfy the same properties, i.e.
${\mathcal{M}}(\Lambda_{[j]})\times\\{0\\}\subset{\mathcal{M}}(\Lambda_{[j+1]})$,
and
${\mathcal{M}}(\Lambda_{[j]})=\\{{\boldsymbol{k}}\in\mathbb{Z}^{j}:({\boldsymbol{k}},{\boldsymbol{0}})\in{\mathcal{M}}(\Lambda)\\}$.
We note that

(7.2)
$\Lambda_{[1]}=\\{0,\dots,q\\},\quad{\mathcal{M}}(\Lambda_{[1]})=\\{-q,\dots,q\\},\quad\quad\mbox{where}\quad\quad
q=\max_{{\boldsymbol{h}}\in\Lambda}(h_{1}),$

and $\Lambda_{[d]}=\Lambda$. For the sake of convenience, we introduce the
convention $\Lambda_{[0]}=\emptyset$.

For ${\boldsymbol{z}}\in\mathbb{Z}^{d}$ arbitrary and
${\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)$, there holds
${\boldsymbol{h}}\cdot{\boldsymbol{z}}={\boldsymbol{h}}_{[d-1]}\cdot{\boldsymbol{z}}_{[d-1]}$
if $h_{d}=0$ and this is equal to
${\boldsymbol{h}}_{[d-2]}\cdot{\boldsymbol{z}}_{[d-2]}$ if in addition
$h_{d-1}=0$, etc. In light of this observation, we derive the lemma 7.1 below.
Here again $\square$ is a placeholder for 0 (integral exactness), or A, B, or
C (reconstruction using plan A, plan B or plan C).

######  Lemma 7.1.

Let $\Lambda\subset\mathbb{N}_{0}^{d}$ be lower and
$(n,{\boldsymbol{z}})\in\mathbb{N}\times\mathbb{Z}^{d}$. Then

  * $(n,{\boldsymbol{z}})\in{\mathcal{P}}_{\square}(\Lambda)$ $\Longrightarrow\;(n,{\boldsymbol{z}}_{[d-1]})\in{\mathcal{P}}_{\square}(\Lambda_{[d-1]})$

$\Longrightarrow\dots$
$\Longrightarrow\;(n,z_{1})\in{\mathcal{P}}_{\square}(\Lambda_{[1]})$.

The lemma has an immediate consequence. Namely, verifying whether
$(n,{\boldsymbol{z}})$ is in ${\mathcal{P}}_{\square}(\Lambda)$ can be
implemented as an iterative scheme consisting on $d$ iterations,

  * -

$1^{st}$ iteration: check whether $(n,z_{1})$ is in
${\mathcal{P}}_{\square}(\Lambda_{[1]})$;

  * -

$2^{nd}$ iteration: check whether $(n,{\boldsymbol{z}}_{[2]})$ is in
${\mathcal{P}}_{\square}(\Lambda_{[2]})$;

  * -

…;

  * -

$d^{th}$ iteration: check whether $(n,{\boldsymbol{z}})$ is in
${\mathcal{P}}_{\square}(\Lambda_{[d]})$.

The condition to be checked in each iteration can be explicitly described.

The first iteration consists in checking if
$(n,z_{1})\in{\mathcal{P}}_{\square}(\\{0,\dots,q\\})$. For instance,

  * •

for $\square=0$, it consists on checking if $az_{1}\not\equiv_{n}0$ for all
$a\in\\{-q,\dots,q\\}-\\{0\\}$, which is equivalent to $az_{1}\not\equiv_{n}0$
for all $a\in\\{1,\dots,q\\}$,

  * •

for $\square\in\\{A,B,C\\}$, it consists on checking if
$(az_{1}\leavevmode\nobreak\ {\rm mod}\leavevmode\nobreak\ n)$ are pairwise
distinct for $a\in\\{-q,\dots,q\\}$ (equivalent to $az_{1}\not\equiv_{n}0$ for
$a\in\\{1,\dots,2q+1\\}$), but with $az_{1}\equiv_{n}-az_{1}$ allowed for
$\square=C$.

It is enough to let $z_{1}=1$ and choose $n\geq q+1$, resp. $n\geq 2q+1$. In
order to complete the scheme, we only need to outline how to efficiently check
if $(n,{\boldsymbol{z}}_{[j]})\in{\mathcal{P}}_{\square}(\Lambda_{[j]})$ once
we have established that $(n,{\boldsymbol{z}}_{[j-1]})$ is in
${\mathcal{P}}_{\square}(\Lambda_{[j-1]})$. When considering
${\boldsymbol{h}}$ in ${\mathcal{M}}(\Lambda_{[j]})$, we necessarily have
${\boldsymbol{h}}=(\widehat{\boldsymbol{h}},h_{j})$ with
$\widehat{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda_{[j-1]})$ and $h_{j}=\pm p$,
hence
${\boldsymbol{h}}\cdot{\boldsymbol{z}}_{[j]}=\widehat{\boldsymbol{h}}\cdot{\boldsymbol{z}}_{[j-1]}\pm
pz_{j}$. For example if $\square=A$, assuming we have already computed all
$\widehat{\boldsymbol{h}}\cdot{\boldsymbol{z}}_{[j-1]}$ for
$\widehat{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda_{[j-1]})$ and verified they
are pairwise distinct (modulo $n$), we simply iterate through
${\boldsymbol{h}}$ in ${\mathcal{M}}(\Lambda_{[j]})$ s.t. $h_{j}\neq 0$,
calculate ${\boldsymbol{h}}\cdot{\boldsymbol{z}}_{[j]}$ as prescribed, and
check whether the result modulo $n$ has not already been listed.

In the course of the iterative scheme, it is crucial to keep record of values
${\boldsymbol{h}}\cdot{\boldsymbol{z}}$ for
${\boldsymbol{h}}\in{\mathcal{M}}(\Lambda_{[j]})$ . Accordingly, we introduce
notation

(7.3) ${\mathcal{D}}_{j}(\Lambda):=\\{V_{\boldsymbol{h}}\mbox{ for
}{\boldsymbol{h}}\in\Lambda_{[j]}\\},\mbox{ where
}V_{\boldsymbol{h}}:=\\{\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}:\sigma\in{\mathcal{S}}_{{\boldsymbol{h}}}\\}$

Our discussion so far shows that
${\mathcal{D}}_{1}(\Lambda)\subset{\mathcal{D}}_{2}(\Lambda)\subset\dots\subset{\mathcal{D}}_{d}(\Lambda)$,
and that computing ${\mathcal{D}}_{j}(\Lambda)$ is fast, with computational
complexity ${\mathcal{O}}(\\#(\Lambda_{[j]}\setminus\Lambda_{[j-1]}))$. We
will refer to ${\mathcal{D}}_{j}(\Lambda)$ as the dictionary associated with
$\Lambda_{[j]}$. For all such dictionaries, we use notation
${\mathcal{D}}=\\{{\boldsymbol{k}}\mapsto(v_{{\boldsymbol{k}}},v_{\boldsymbol{k}}^{*})\\}$
refer to ${\boldsymbol{k}}$ as the key, and have
$v_{{\boldsymbol{k}}}={\boldsymbol{k}}\cdot{\boldsymbol{z}}$ and
$v_{\boldsymbol{k}}^{*}=V_{\boldsymbol{k}}-\\{v_{\boldsymbol{k}}\\}$. The set
$\Lambda_{[j]}$ is implicit in the notation, it consists simply on all the
keys. The use of dictionaries allows us to efficiently store and optimize data
during the search, ensuring minimal redundant computations.

###  7.3. Search Algorithm

Algorithm 2 proposes an iterative procedure for obtaining
$(n,{\boldsymbol{z}})$ admissible, for any given $\Lambda$ and admissibility
criterion $\square\in\\{0,A,B,C\\}$. The algorithm initializes $n$ to a lower
bound, ${\boldsymbol{z}}$ to an ‘empty vector’ and consists on $d$ iterations.
Within iteration $j$, an integer $\zeta$ is incremented in $\\{0,\dots,n-1\\}$
until $(n,[{\boldsymbol{z}},\zeta])$ becomes admissible for $\Lambda_{[j]}$.
If no suitable $\zeta$ is found, $n$ is incremented and the search is
repeated. Once a $\zeta$ is found, ${\boldsymbol{z}}$ is extended with $\zeta$
and we advance to iteration $j+1$.

Algorithm 2 Search for admissible $(n,{\boldsymbol{z}})$

0: $d$, $\Lambda$, $n_{\text{lower}}$, plan-$\square$.

1: Initialize $n=n_{\text{lower}}$, ${\boldsymbol{z}}=[\leavevmode\nobreak\
]$, ${\mathcal{D}}=\\{\\}$,

2: Let $\zeta=0$, $F_{nz}=\text{True}$,

3: for $j=1,\dots,d$ do

4: $n\leftarrow n-1$, $\zeta\leftarrow 0$, $F_{nz}\leftarrow\text{False}$,

5: while $\text{not }F_{nz}$ do

6: $n\leftarrow n+1$,

7: while $\text{ not }F_{nz}$ and $\zeta<n$ do

8:
$F_{j},{\mathcal{D}}_{j}=\text{Admissibility}(\Lambda_{[j]},\leavevmode\nobreak\
{\mathcal{D}},\leavevmode\nobreak\ n,\leavevmode\nobreak\
{\boldsymbol{z}},\leavevmode\nobreak\ \zeta,\leavevmode\nobreak\
\text{plan-}\square)$

9: if $F_{j}$ then

10: $F_{nz}\leftarrow\text{True}$, ${\mathcal{D}}\leftarrow{\mathcal{D}}_{j}$,

11: else

12: $\zeta\leftarrow\zeta+1$

13: end if

14: end while

15: end while

16: ${\boldsymbol{z}}\leftarrow[{\boldsymbol{z}},\zeta]$

17: end for

18: return $n$, ${\boldsymbol{z}}$, ${\mathcal{D}}$

The main procedure in every iteration is Admissibility (line 8) which
evaluates the admissibility of a given pair $(n,[{\boldsymbol{z}},\zeta])$ for
$\Lambda_{[j]}$, and outputs the dictionary associated with $\Lambda_{[j]}$
and $[{\boldsymbol{z}},\zeta]$ in case of admissibility. The procedure is
presented in Algorithm 3.

Algorithm 3 Admissibility of $(n,[{\boldsymbol{z}},\zeta])$

0: $\Lambda_{[j]}$, ${\mathcal{D}}$, $n$, ${\boldsymbol{z}}$, $\zeta$,
$\text{plan-}\square$.

1: Initialize sets $V=\\{\\}$ and $V^{*}=\\{\\}$ and dictionary
${\mathcal{D}}_{out}=\\{\\}$,

2: for each ${\boldsymbol{h}}=(\widehat{\boldsymbol{h}},h)$ in $\Lambda_{[j]}$
do

3: Extract $(v_{\text{id}},v_{\text{other}})$ associated with key
$\widehat{\boldsymbol{h}}$ in ${\mathcal{D}}$,

4: if $h\neq 0$ then

5: update $v_{\text{id}}\leftarrow v_{\text{id}}+h\zeta$ and
$v_{\text{other}}\leftarrow\\{v-h\zeta\\}\cup\\{w\pm h\zeta\mbox{ for }w\in
v_{\text{other}}\\}$,

6: end if

7: if condition-$\square$ then

8: return False, $\\{\\}$

9: else

10: Update $V\leftarrow V\cup\\{v_{\text{id}}\\}$ and $V^{*}\leftarrow
V^{*}\cup v_{\text{other}}$

11: Create and associate in ${\mathcal{D}}_{out}$ the key ${\boldsymbol{h}}$
with value $(v_{\text{id}},v_{\text{other}})$.

12: end if

13: end for

14: return True, ${\mathcal{D}}_{out}$

The admissibility algorithm 3 processes the input lower set $\Lambda_{[j]}$,
the dictionary ${\mathcal{D}}$ associated with $\Lambda_{[j-1]}$, the integer
$n$, the vector ${\boldsymbol{z}}\in\mathbb{Z}^{j-1}$,
$\zeta\in\\{0,\dots,n-1\\}$ and a specified admissibility for plan-$\square$
criterion. The purpose is to determine the admissibility of the couple
$(n,[{\boldsymbol{z}},\zeta])$ for $\Lambda_{[j]}$ for the specified
criterion. If admissibility is satisfied, the dictionary associated with
$\Lambda_{[j]}$ is returned.

Admissibility for all criteria is implemented similarly. The algorithm
structure is the same, except for the if condition in line 7, which varies as
summarized below:

plan-$\square$ |  Condition | Time Complexity ${\mathcal{O}}(\square)$
---|---|---
$\square=0$ |  $0\in v_{\text{id}}\cup v_{\text{other}}$ | ${\mathcal{O}}(\\#v_{\text{other}})$
$\square=C$ |  $v_{\text{id}}\in V\cup V^{*}$ or $v_{\text{other}}\cap V\neq\emptyset$ | ${\mathcal{O}}(\\#V^{*})$
$\square=B$ |  $v_{\text{id}}\in v_{\text{other}}$ or $v_{\text{id}}\in V\cup V^{*}$ or $v_{\text{other}}\cap V\neq\emptyset$ | ${\mathcal{O}}(\\#V^{*})$
$\square=A$ |  repetition in $v_{\text{other}}$ or $v_{\text{id}}\in v_{\text{other}}$ or $v_{\text{id}}\in V\cup V^{*}$ or $v_{\text{other}}\cap(V\cup V^{*})\neq\emptyset$ | ${\mathcal{O}}(\\#V^{*})$
Table 1. Conditions for each plan with corresponding time complexity

######  Remark 7.2.

To do the time complexity analysis we make the following remarks:

  * •

A simple lookup has complexity of the size of the set.

  * •

To determine if the intersection of two lists $A$ and $B$ is non-empty, we
consider the hash-set approach which has complexity
${\mathcal{O}}(\\#A+\\#B)$.

  * •

The size of $V$ is negligible compared to $V^{*}$. In fact, $V$ has the same
cardinality as $\widetilde{\Lambda}$, while $V^{*}$ has same as
${\mathcal{M}}(\widetilde{\Lambda})\setminus\widetilde{\Lambda}$, where
$\widetilde{\Lambda}$ consists on indices ${\boldsymbol{h}}$ that have been
iterated of $\Lambda_{[j]}$.

  * •

$V^{*}$ are made to include all new $v_{\text{other}}$ vectors, which means
$\\#v_{\text{other}}\ll\\#V^{*}$

The conditions are meant modulo $n$. More precisely, checking if $v\in S$
means checking if $v\equiv_{n}s$ for some $s\in S$, and checking if $S\cap
S^{\prime}\neq\emptyset$ means checking if $s\equiv_{n}s^{\prime}$ for some
$s\in S$ and $s^{\prime}\in S^{\prime}$. Let us note that for $\square=0$,
instructions in lines 1 and 10 are not needed. Also for $\square=A$, we do not
need to define $V$ and $V^{*}$ separately but rather use directly $V\cup
V^{*}$. When the inputs are $\Lambda_{1}=\\{0,\dots,q\\}$,
${\mathcal{D}}=\\{\\}$ and ${\boldsymbol{z}}=[\leavevmode\nobreak\ ]$, we have
$\widehat{\boldsymbol{h}}=()$ is the “empty multi-index” in line 2. The
convention of extracting $(v,v^{*})=(0,\emptyset)$ in line 3 and of evaluating
$v\in\emptyset$ to true makes the procedure consistent with the theory.

Algorithm 2 is well posed, and finishes in finite time. For illustration, we
consider plan A. We assume we are at iteration $j$, so that
$(n,{\boldsymbol{z}})$ is admissible for $\Lambda_{[j-1]}$, i.e.
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda_{[j-1]})$.
Then necessarily
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\neq{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda_{[j-1]})$.
It is easily checked that for $\zeta$ very large, we have
${\boldsymbol{h}}\cdot[{\boldsymbol{z}},\zeta]\neq{\boldsymbol{h}}^{\prime}\cdot[{\boldsymbol{z}},\zeta]$
for all
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda_{[j]})$,
and this will also holds if $\neq$ is replaced by $\not\equiv_{m}$ for $m$
also too large. As a result, with certainty we end up exiting iteration $j$
and going to iteration $j+1$.

###  7.4. Faster algorithm

Algorithm 2 can be very slow, in particular in high dimension. Every time $n$
is incremented and $\zeta$ is varied in $\\{0,\dots,n-1\\}$, new computations
modulo $n$ have to be performed. We propose a new approach where finding $n$
is postponed to the end of the algorithm.

The omission of the modulo $n$ operation in the previous algorithms,
particularly in the admissibility algorithm 3, results in a faster
alternative. More precisely, for $\Lambda$ lower we first construct a vector
${\boldsymbol{z}}$ verifying an admissibility criterion where $\not\equiv_{n}$
is replaced by $\neq$, then after that compute an integer $n$ such that
$(n,{\boldsymbol{z}})\in{\mathcal{P}}_{\square}(\Lambda)$. For example, for
plan A, we first compute ${\boldsymbol{z}}$ for which holds
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\neq{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda)$, then
find $n$ small such that
${\boldsymbol{h}}\cdot{\boldsymbol{z}}\not\equiv_{n}{\boldsymbol{h}}^{\prime}\cdot{\boldsymbol{z}}$
for all
${\boldsymbol{h}}\neq{\boldsymbol{h}}^{\prime}\in{\mathcal{M}}(\Lambda)$ which
we can search for in
$\\{\\#({\mathcal{M}}(\Lambda)),\dots,2\max_{{\boldsymbol{h}}\in{\mathcal{M}}(\Lambda)}(|{\boldsymbol{h}}\cdot{\boldsymbol{z}}|)+1\\}$.
While this alternative may produce a larger $n$, it significantly accelerates
computations, providing a viable heuristic when prioritizing speed over
optimality.

The algorithms structure is the same. We modify algorithm 2 by removing the
dependence on $n$. Algorithm 4 is an iterative procedure for obtaining
${\boldsymbol{z}}$ admissible, for any given $\Lambda$ and admissibility
criterion $\square\in\\{0,A,B,C\\}$. The algorithm initializes
${\boldsymbol{z}}$ to an ‘empty vector’ and consists on $d$ iterations. Within
iteration $j$, an integer $\zeta$ is incremented in $\\{0,\dots\\}$ until
$([{\boldsymbol{z}},\zeta])$ becomes admissible for $\Lambda_{[j]}$. Once a
$\zeta$ is found, ${\boldsymbol{z}}$ is extended with $\zeta$ and we advance
to iteration $j+1$. The main procedure in every iteration is Admissibility
(line 6) which evaluates the admissibility of $[{\boldsymbol{z}},\zeta]$ for
$\Lambda_{[j]}$, and outputs the dictionary associated with $\Lambda_{[j]}$
and $[{\boldsymbol{z}},\zeta]$ in case of admissibility. The procedure uses
Algorithm 3 with the parameter $n$ being “nil” meaning that
condition-$\square$ in line 7 is performed with $\neq$ instead of
$\not\equiv_{n}$.

Algorithm 4 outputs ${\boldsymbol{z}}$ and associated dictionary
${\mathcal{D}}$ of the all values
$\sigma({\boldsymbol{h}})\cdot{\boldsymbol{z}}$ for
${\boldsymbol{h}}\in\Lambda$. Subsequently, we can execute an algorithm that
straightforwardly determines $n$ based on these outcomes as shown in Algorithm
6.

For lower sets of simplex-type, such as ${\mathcal{S}}_{{\boldsymbol{1}},k}$
or in general ${\mathcal{S}}_{{\boldsymbol{w}},u}$ the above algorithms can be
simplified further. For instance, for plan-A admissibility, it is
computationally more advantageous to rely (6.5) instead of (3.21) while for
for plan-C admissibility, it is computationally more advantageous to rely
(6.6) instead of (3.23). We have implemented these optimizations in the
numerical experiments.

Algorithm 4 Search for admissible ${\boldsymbol{z}}$

0: $d$, $\Lambda$, plan-$\square$.

1: Initialize ${\boldsymbol{z}}=[\leavevmode\nobreak\ ]$,
${\mathcal{D}}=\\{\\}$,

2: Let $\zeta=0$, $F=\text{True}$

3: for $j=1,\dots,d$ do

4: $\zeta\leftarrow 0$, $F\leftarrow\text{False}$,

5: while $\text{not }F$ do

6:
$F_{j},{\mathcal{D}}_{j}=\text{Admissibility}(\Lambda_{j},\leavevmode\nobreak\
{\mathcal{D}},\leavevmode\nobreak\ nil,\leavevmode\nobreak\
{\boldsymbol{z}},\leavevmode\nobreak\ \zeta,\leavevmode\nobreak\
\text{plan-}\square)$

7: if $F_{j}$ then

8: $F\leftarrow True$, ${\mathcal{D}}\leftarrow{\mathcal{D}}_{j}$,

9: else

10: $\zeta\leftarrow\zeta+1$

11: end if

12: end while

13: ${\boldsymbol{z}}\leftarrow[{\boldsymbol{z}},\zeta]$

14: end for

15: return ${\boldsymbol{z}}$, ${\mathcal{D}}$

Algorithm 5 admit_n

0: $\Lambda$, ${\mathcal{D}}$, $n$, plan-$\square$

1: Let $V=\\{\\}$ and $V^{*}=\\{\\}$,

2: for each ${\boldsymbol{h}}$ in $\Lambda$ do

3: Extract $(v_{\text{id}},v_{\text{other}})$ from ${\mathcal{D}}$, associated
with key ${\boldsymbol{h}}$,

4: if condition-$\square$ modulo $n$ then

5: return False,

6: else

7: Update $V\leftarrow V\cup\\{v_{\text{id}}\\}$ and $V^{*}\leftarrow
V^{*}\cup\\{v_{\text{other}}\\}$

8: end if

9: end for

10: return True

Algorithm 6 Search for admissible $n$ given ${\boldsymbol{z}}$

0: $\Lambda$, ${\mathcal{D}}$, $n_{\text{lower}}$, plan-$\square$.

1: Initialize $n=n_{\text{lower}}-1$, $F=\text{False}$,

2: while $\text{not }F$ do

3: $n\leftarrow n+1$,

4: $F=\text{admit\\_n}(\Lambda,\leavevmode\nobreak\
{\mathcal{D}},\leavevmode\nobreak\ n,\leavevmode\nobreak\
\text{plan-}\square)$ {admit_n is defined in Algorithm 5}

5: end while

6: return $n$

##  8\. Performance Analysis

###  8.1. Complexity Analysis

  * •

Algorithm 3: The outer loop iterates over each element in $\Lambda_{[j]}$.
Updating $v_{\text{other}}$ is done in
$\mathcal{O}(2^{|{{\boldsymbol{h}}}|_{0}})$ time. The check of
condition-$\square$ has complexity
$\mathcal{O}(\\#V^{*})\ll{\mathcal{O}}(\\#\mathcal{M}(\Lambda_{[j]}))$ as per
Table 1. Thus, the overall complexity of Algorithm 3 can be expressed at worst
as

$\mathcal{O}(\\#\Lambda_{[j]}\times\\#\mathcal{M}(\Lambda_{[j]}))$

.

  * •

Algorithm 2: The outer loop runs $d$ times, corresponding to each dimension.
The inner WHILE loop continues until a valid $\zeta$ is found, with a maximum
of $n_{j}$ iterations. For each iteration, the ”Admissibility” function is
called with complexity
$\mathcal{O}(\\#\Lambda_{[j]}\times\\#\mathcal{M}(\Lambda_{[j]}))$. Therefore,
the overall worst-case complexity is

$\mathcal{O}(p_{\square}^{*}(\Lambda)^{2}\times\\#\Lambda\times\\#\mathcal{M}(\Lambda)).$

  * •

Algorithm 4: Since this algorithm does not depend on $n$, its complexity is
reduced to

$\mathcal{O}(\\#\Lambda\times\\#\mathcal{M}(\Lambda)).$

  * •

Algorithm 5: The outer FOR loop runs once for each element ${\boldsymbol{h}}$
in $\Lambda$, making the loop run $\\#\Lambda$ times. Checking
condition-$\square$ modulo $n$ has complexity $\mathcal{O}(\square)$. Thus,
following the same logic as per Algorithm 3, the total time complexity is

$\mathcal{O}(\\#\Lambda\times\\#\mathcal{M}(\Lambda)).$

  * •

Algorithm 6: The algorithm iterates over $n$ using Algorithm 5, achieving a
worst-case time complexity of:

$\mathcal{O}(p_{\square}^{*}(\Lambda)\times\\#\Lambda\times\\#\mathcal{M}(\Lambda)).$

###  8.2. Experimental Results

####  8.2.1. Comparison to minimal values

For our numerical investigation, we utilize anisotropic simplex-type sets in
three dimensions, characterized by ${\boldsymbol{w}}=(0.9,0.8,0.7)$. Instead
of specifying a radius $u$, we parametrized the sets
${\mathcal{S}}_{{\boldsymbol{w}},u}$ by their cardinalities. More precisely,
given an integer $N\geq 1$, we generate $\Lambda\subset\mathbb{N}^{d}$
consisting in the $N$ multi-indices ${\boldsymbol{h}}$ with the smallest
values of $\langle{\boldsymbol{h}},{\boldsymbol{w}}\rangle$ with ties broken
arbitrarily. For give sizes of $\Lambda$, we employ an exhaustive algorithm to
compute the optimal $n_{\square}^{*}(\Lambda)$ for each plan-$\square$, and
compare to the resulting values obtained using our approach (Algorithm 4 \-
5). Table 2 illustrates the diverse values obtained. Our algorithm yields
identical results across all three plans.

$\\#(\Lambda)$ | $\\#({\mathcal{M}}(\Lambda))$ | $n_{A}^{*}(\Lambda)$ | $n_{B}^{*}(\Lambda)$ | $n_{C}^{*}(\Lambda)$ | $n_{A}(\Lambda)=n_{B}(\Lambda)=n_{C}(\Lambda)$
---|---|---|---|---|---
40 | 149 | 160 | 151 | 151 | 180
50 | 195 | 217 | 200 | 200 | 253
80 | 341 | 379 | 363 | 362 | 418
100 | 445 | 481 | 471 | 471 | 591
150 | 713 | 803 | 759 | 759 | 962
Table 2. Comparison of optimal $n_{\square}^{*}(\Lambda)$ and values obtained
using our approach for different sizes of $\Lambda$.

We compute the Mean Absolute Percentage Error (MAPE) given by the formula:

$\text{MAPE}_{\square}=\frac{100\%}{N}\sum_{i=1}^{N}\left|\frac{n_{\square}^{*}(\Lambda_{i})-n_{\square}(\Lambda_{i})}{n_{\square}^{*}(\Lambda_{i})}\right|.$

This metric expresses the error as a percentage of the actual values, which
can be more intuitive for understanding relative accuracy.

$\text{MAPE}_{A}$ | $\text{MAPE}_{B}$ | $\text{MAPE}_{C}$
---|---|---
16.42% | 17.78% | 18.3%
Table 3. MAPE for the different plans

In Table 3, we observe an overall deviation of around $17\%$, suggesting that
our algorithm produces reasonably accurate estimates swiftly. While this
margin of error may appear substantial, it serves as a useful starting point
for search algorithms or offers quick insights into the necessary number of
points.

We only consider dimension $d=3$ due to the increased complexity and time
requirements associated with reporting the greedy search in higher dimensions
${\mathcal{O}}(n^{*}_{\square}(\Lambda)^{d+1})$.

####  8.2.2. Execution Time

For the second setup, we consider ${\boldsymbol{w}}_{3}=(0.9,0.8,0.7)$,
${\boldsymbol{w}}_{4}=(0.9,0.8,0.7,0.6)$,
${\boldsymbol{w}}_{5}=(0.9,0.8,0.7,0.6,0.5)$, and
${\boldsymbol{w}}_{8}=(0.9,0.8,0.7,0.6,0.5,0.4,0.3,0.2)$ for the cases
$d=3,4,5$ and $d=8$ respectively. We consider for each dimension sets
$\Lambda$ of different cardinalities. The scatter plot in Figure 2 illustrates
the execution time for the different plans (Plan A, Plan B, and Plan C) across
the dimensions for different choices of $\\#(\Lambda)$.

Observations from Figure 2 reveal that Plan C consistently outperforms Plans A
and B in terms of execution time, while Plan A consistently exhibits the
longest duration. Moreover, as the dataset size increases, a corresponding
escalation in execution time is observed. The $\log-\log$ plot indicates a
linear trend, suggesting that execution time is a power of the product of
$\\#(\Lambda)$ and $\\#({\mathcal{M}}(\Lambda))$ across different plans,
expressed as ${\mathcal{O}}(\text{Execution
time})=\mathcal{O}([\\#(\Lambda)\\#({\mathcal{M}}(\Lambda))]^{p})$.

A linear regression analysis yields $p\lesssim 1$ for different dimensions,
supporting our complexity analysis.

Finally, we make the following observations:

  * •

Dimension has minimal impact on our algorithm, as the effect of dimension is
encapsulated within ${\mathcal{M}}(\Lambda)$. For the same $\\#(\Lambda)$,
$\\#({\mathcal{M}}(\Lambda))$ increases with dimension.

  * •

The overall complexity can be bounded using the inequality
$\\#{\mathcal{M}}(\Lambda)\leq\min\\{2^{d}\\#\Lambda,\\#\Lambda^{\ln 3/\ln
2}\\}$ from [ChkifaLower]*Lemma 3.3. Thus, our algorithm’s complexity is
bounded by

${\mathcal{O}}(p_{\square}^{*}(\Lambda)\times\min\\{2^{d}\\#\Lambda^{2},\\#\Lambda^{\ln
3/\ln 2+1}\\}).$

  * •

The execution time values provided are indicative, obtained from computations
on a machine with an Intel i7 CPU, 31.2 GB of RAM, and a 233.18 GB disk. All
our algorithms are single-core implementations..

##  9\. Conclusion

In this paper, we have addressed the challenge of constructing optimal rank-1
lattices for function integration and reconstruction, specifically focusing on
finite index sets that are lower sets namely blocks and simplexes. We
introduced new theoretical sharp lower bounds on the minimal number of
integrands needed for reconstruction and developed a novel algorithm for
constructing the corresponding optimal generator vector of the rank-1 lattice.
Our approach, which leverages the inherent lower structure of the set of
interpolants, optimizes the construction process through exhaustive search and
meticulous verification, resulting in significant improvements in computation
time and memory usage. The efficiency and practicality of our algorithm were
demonstrated through numerical experiments, confirming its suitability for
handling large-scale problems. Future research may explore further refinements
of the algorithm and its application to other functional spaces and
integration tasks.

Figure 2. Execution time patterns across the three plans for different
dimensions as function of $\\#\Lambda$ (left) and $\\#{\mathcal{M}}(\Lambda)$
(middle) and $\\#\Lambda\\#{\mathcal{M}}(\Lambda)$ (right).

## References