Frances Y Kuo
email: f.kuo@unsw.edu.au

Giovanni Migliorati
email: migliorati@ljll.math.upmc.fr

Fabio Nobile
email: fabio.nobile@epfl.ch

Dirk Nuyens
email: dirk.nuyens@cs.kuleuven.

Function integration, reconstruction and approximation using rank-1 lattices

Keywords: Exact integration and approximation on finite index sets, Quasi-Monte Carlo methods, Rank-1 lattice points, Fourier space, Cosine space, Chebyshev space, Componentby-component construction AMS Subject classifications: 41A10 (Approximation by polynomials), 42A10 (Trigonometric approximation), 41A63 (Multidimensional problems), 42B05 (Fourier series and coefficients), 65D30 (Numerical integration), 65D32

We consider rank-1 lattices for integration and reconstruction of functions with series expansion supported on a finite index set. We explore the connection between the periodic Fourier space and the non-periodic cosine space and Chebyshev space, via tent transform and then cosine transform, to transfer known results from the periodic setting into new insights for the non-periodic settings. Fast discrete cosine transform can be applied for the reconstruction phase. To reduce the size of the auxiliary index set in the associated component-by-component (CBC) construction for the lattice generating vectors, we work with a bi-orthonormal set of basis functions, leading to three methods for function reconstruction in the non-periodic settings. We provide new theory and efficient algorithmic strategies for the CBC construction. We also interpret our results in the context of general function approximation and discrete least-squares approximation.

Introduction

In this paper we consider function integration, reconstruction and approximation in the periodic and non-periodic settings using rank-1 lattices. We explore the connection between three function space settings to transfer known results on rank-1 lattices from the periodic setting to the non-periodic settings. We obtain necessary and sufficient conditions on rank-1 lattices to achieve the exactness properties we require in each setting, and we develop efficient algorithms to construct the generating vectors for rank-1 lattices that satisfy these conditions.

More precisely, we consider functions with absolutely convergent series expansions with respect to an orthonormal basis, written in the generic form

f = k f k α k . (1)
A large part of this paper is devoted to functions which are fully supported on a finite index set Λ, i.e., f

= k∈Λ f k α k . (2)
We develop methods based on rank-1 lattices to exactly integrate such functions [START_REF] Chkifa | Discrete least-squares polynomial approximation with random evaluations -application to parametric and stochastic elliptic PDEs[END_REF], and to exactly reconstruct all series coefficients f k in [START_REF] Chkifa | Discrete least-squares polynomial approximation with random evaluations -application to parametric and stochastic elliptic PDEs[END_REF]. We also consider the approximation problem for functions [START_REF] Byrenheid | Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness[END_REF] which are not finitely supported on Λ.

The three function space settings we consider are as follows:

• The Fourier space contains all absolutely convergent Fourier series in the unit cube [0, 1] d , with exponential basis functions e h (x) = e 2πi h•x and indices h ∈ Z d .

• The cosine space contains all absolutely convergent cosine series in [0, 1] d , with halfperiod cosine basis functions φ k (see [START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF] below) and nonnegative indices k ∈ N d 0 .

• The Chebyshev space consists of all absolutely convergent Chebyshev series in the larger domain [-1, 1] d , under the Chebyshev measure, with Chebyshev basis functions η k (see [START_REF] Potts | Sparse high-dimensional FFT based on rank-1 lattice sampling[END_REF] below) and also nonnegative indices k ∈ N d 0 .

To avoid excessive notation we keep to generic notation for the three spaces wherever possible, including the same 'hat' notation for series coefficients. However, to effectively describe the connection between spaces, we often distinguish the basis functions e h , φ k , η k , and we often use h and k to contrast indices containing integers Z or only nonnegative integers N 0 . The Fourier space contains periodic functions while the cosine and Chebyshev spaces contain nonperiodic functions. The Fourier space is often referred to as the Wiener algebra; it is the standard setting for analyzing periodic functions, see, e.g., [START_REF] Kämmerer | Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling[END_REF][START_REF] Kämmerer | Interpolation lattices for hyperbolic cross trigonometric polynomials[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF][START_REF] Potts | Sparse high-dimensional FFT based on rank-1 lattice sampling[END_REF]. The cosine space is connected to the Fourier space by the tent transform which is defined by ϕ tent (x) := 1-|2x-1| for x ∈ [0, 1] and is applied componentwise in d dimensions, see, e.g., [START_REF] Cools | Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions[END_REF][START_REF] Dick | Lattice rules for nonperiodic smooth integrands[END_REF][START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF]. We show that the composition φ k • ϕ tent is the average over all of those exponential basis functions e h for which (|h 1 |, . . . , |h d |) = k (see [START_REF] Kuo | Lattice rules for multivariate approximation in the worst case setting[END_REF] below). Consequently, the tent-transformed cosine space is a subspace of the Fourier space. Thus we can apply results from the Fourier space to the cosine space via tent transform.

The Chebyshev space is related to the cosine space by the cosine transform, given by x = cos(πx ′ ) ∈ [-1, 1] d for x ′ ∈ [0, 1] d , where the cosine function is applied componentwise, and we have η k (x) = η k (cos(πx ′ )) = φ k (x ′ ). Thus the cosine transform provides an isomorphism between the Chebyshev space and the cosine space. Trivially all results from the cosine space can be carried over to the Chebyshev space.

Rank-1 lattices have been well studied for integration, reconstruction and approximation in the Fourier space; see, e.g., [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF][START_REF] Sloan | Lattice methods for multiple integration[END_REF] for integration, [START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF][START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF] for reconstruction, and [START_REF] Byrenheid | Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling[END_REF][START_REF] Kämmerer | Interpolation lattices for hyperbolic cross trigonometric polynomials[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF][START_REF] Kuo | Lattice rules for multivariate approximation in the worst case setting[END_REF][START_REF] Kuo | Lattice rule algorithms for multivariate approximation in the average case setting[END_REF][START_REF] Kuo | Lattice algorithms for multivariate L ∞ approximation in the worst-case setting[END_REF][START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF][START_REF] Zeng | Error analysis of splines for periodic problems using lattice designs[END_REF][START_REF] Zeng | Spline methods using integration lattices and digital nets[END_REF] for approximation. Given the generating vector z ∈ Z d , the n points of a rank-1 lattice are specified by

t i = iz mod n n ∈ [0, 1] d for i = 0, . . . , n -1.
For a Fourier space function f , the average of function values at the lattice points

Q n (f ) := 1 n n-1 i=0 f (t i )
is known as a rank-1 lattice rule which is an equal-weight cubature rule for approximating the integral

I(f ) := [0,1] d f (x) dx.
Rank-1 lattices have an important property known as the "character property" (see (9) below) which states that the cubature sum of the exponential basis functions Q n (e h ) can only take the value of 1 or 0, depending on whether or not the dot product h • z is a multiple of n.

Since the integral of the basis function I(e h ) is 1 if h = 0 and is 0 otherwise, we easily deduce that a rank-1 lattice rule can exactly integrate a function f = h∈Λ f h e h whose Fourier series is supported on a finite set Λ ⊂ Z d if and only if h •z is not a multiple of n for all nonzero vectors h ∈ Λ. This condition in turn leads to an efficient algorithm to construct a generating vector z with the exactness property in a component-by-component fashion. This result is stated later in Lemma 4, see also [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF], and it can be said to be the starting point of all results in this paper. Indeed, the result extends to function reconstruction on Λ where we evaluate all the Fourier coefficients f h for h ∈ Λ by a rank-1 lattice rule, and the evaluations can be done using the fast Fourier transform. Using the character property one can deduce a necessary and sufficient condition when these Fourier coefficients can be recovered exactly, thus leading to a constructive algorithm to find suitable generating vectors by working with the "difference set" Λ ⊖ Λ which is obtained by forming all differences of indices in Λ. We state this result later in Lemma 5, which was first proved with varying generality in [START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF][START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF][START_REF] Potts | Sparse high-dimensional FFT based on rank-1 lattice sampling[END_REF]. The idea has been further extended to the construction of "multiple rank-1 lattices" in [START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF], where the benefits of multiple reconstruction lattices are combined strategically to achieve the same goal with a reduced overall number of sampling nodes; we do not go down this path.

The connection between the Fourier space and the cosine space allows us to apply the theory of rank-1 lattices to the cosine space by tent transform. We can obtain necessary and sufficient conditions for tent-transformed rank-1 lattices to achieve the integral exactness and function reconstruction properties in the cosine space, see Lemmas 10 and 11 below (see also [START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF] for part of Lemma 11). In the case of function reconstruction on a finite index set Λ ⊂ N d 0 , we end up having to work with quite a large auxiliary index set M(Λ) ⊕ M(Λ) in our component-bycomponent construction of the lattice generating vector, where M(Λ) denotes the "mirrored set" obtained from Λ by including all sign changes of indices in Λ, while the ⊕ then means that we form the sum of all indices from M(Λ); we call this plan A. To improve on the computational efficiency of plan A, we show by working with a bi-orthonormal set of basis functions that we can achieve function reconstruction on Λ with a weaker condition which means working with a smaller auxiliary index set Λ ⊕ M(Λ), see Lemma 15 below; we call this plan B. We also relax the algorithm to not necessarily recover the normalization of the basis functions to arrive at plan C, which achieves the same reconstruction property at a lower computational cost, see Lemma 16 below. All three plans for function reconstruction in the cosine space can be computed using the fast discrete cosine transform.

The isomorphism between the cosine space and the Chebyshev space allows us to take all results from the cosine space to the Chebyshev space, including plans A, B, C. We arrive at tent-transformed and then cosine-transformed rank-1 lattices, which in the case of n being even is also known as "Chebyshev lattices", see, e.g., [START_REF] Cools | Chebyshev lattices, a unifying framework for cubature with Chebyshev weight function[END_REF][START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF], although we do not adopt this terminology. Our plan C for the Chebyshev space with even n is essentially the approach in [START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF]; in this paper we do not require n to be even.

Layout of the paper and highlight of new results

In Section 2 we review results on rank-1 lattices for integration and function reconstruction on a finite index set in the Fourier space, referencing essential results from [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF][START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF][START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF][START_REF] Potts | Sparse high-dimensional FFT based on rank-1 lattice sampling[END_REF].

In Section 3 we introduce the cosine space and consider integration and function reconstruction, with three plans for achieving exact function reconstruction using rank-1 lattices with varying costs. Except for the if-part of Lemma 11 and Lemma 12 which was proved in [START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF], all remaining results in this section are new, including plan B and plan C for function reconstruction and the applicability of fast discrete cosine transform.

In Section 4 we present the corresponding results for the Chebyshev space. Lemma 21 for plan C with even n turns out to be equivalent to the approach in [START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF]. However, the precise connection to the cosine space via cosine transform and in turn the precise connection to the Fourier space via tent transform are both new interpretations here, and they lead to broader implications in the Chebyshev space. In particular, the multiplicity of the transformed points under these interpretations are known explicitly for n both even and odd, and fast discrete cosine transform can be applied for all n.

Section 5 is devoted to the theory and algorithmic aspect of the component-by-component (CBC) construction for lattice generating vectors achieving various conditions needed for the exactness properties. As the theoretical justification for the CBC construction, Theorem 23 generalises previous results proved in [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF][START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF][START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF] and provides a cheaper variant of the algorithm when building up the index set, while Theorem 26 is new and specific to plan C. The systematic way to combine two different approaches (namely, the "brute force" approach and the "elimination" approach, to be explained in Section 5) in a mixed CBC construction is new. Strategies for storage and a "smart lookup" to efficiently search through difference and/or sum involving mirrored sets are also new.

Finally in Section 6 we interpret our results in the context of approximation of general functions that are not necessarily supported on a finite index set, and compare them with discrete least-squares approximation as analysed in [START_REF] Chkifa | Discrete least-squares polynomial approximation with random evaluations -application to parametric and stochastic elliptic PDEs[END_REF][START_REF] Cohen | On the stability and accuracy of least-squares approximations[END_REF][START_REF] Migliorati | Analysis of discrete L 2 projection on polynomial spaces with random evaluations[END_REF][START_REF] Migliorati | Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets[END_REF][START_REF] Narayan | Multivariate discrete least-squares approximations with a new type of collocation grid[END_REF]. We mention other known results in function approximation based on rank-1 lattices (see, e.g., [START_REF] Kuo | Multivariate L ∞ approximation in the worst case setting over reproducing kernel Hilbert spaces[END_REF][START_REF] Kuo | On the power of standard information for multivariate approximation in the worst case setting[END_REF][START_REF] Wasilkowski | Weighted tensor product algorithms for linear multivariate problems[END_REF][START_REF] Wasilkowski | On the power of standard information for weighted approximation[END_REF] for general results and [START_REF] Byrenheid | Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness[END_REF][START_REF] Cools | Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF][START_REF] Kuo | Lattice rules for multivariate approximation in the worst case setting[END_REF][START_REF] Kuo | Lattice rule algorithms for multivariate approximation in the average case setting[END_REF][START_REF] Kuo | Lattice algorithms for multivariate L ∞ approximation in the worst-case setting[END_REF][START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF][START_REF] Zeng | Error analysis of splines for periodic problems using lattice designs[END_REF][START_REF] Zeng | Spline methods using integration lattices and digital nets[END_REF] for rank-1 lattices).

We end the introduction with setting the notation on multiindices and introducing some special index sets.

Notation on multiindices and special index sets

Throughout this paper we use # to denote the cardinality of a set. For any multiindex k ∈ Z d , we write We will consider index sets with some special properties:

|k| 0 := #{1 ≤ j ≤ d : k j = 0} for the number of nonzero indices in k. For k, k ′ ∈ Z d , k ′ ≤ k is to be interpreted componentwise, i.e., k ′ j ≤ k j for all j.
• An index set Λ ⊂ N d 0 is downward closed if k ′ ∈ Λ whenever k ′ ≤ k and k ∈ Λ.
This means that from every k ∈ Λ we can move towards 0 along the coordinate axes without finding a k ′ ∈ Λ. Analogous definition holds with

N d 0 replaced by Z d . • An index set Λ ⊂ Z d is centrally symmetric if -k ∈ Λ whenever k ∈ Λ. • An index set Λ ⊂ Z d is fully sign symmetric if σ(k) ∈ Λ whenever k ∈ Λ and σ ∈ {±1} d . • An index set Λ ⊂ N d 0 is an (anisotropic) tensor product set if there exist a, b ∈ N d 0 such that Λ = {k ∈ N d 0 : a ≤ k ≤ b}.
Λ ⊕ Λ := {k + k ′ : k, k ′ ∈ Λ} ("sum set"), Λ ⊖ Λ := {k -k ′ : k, k ′ ∈ Λ} ("difference set"), M(Λ) := σ(k) : k ∈ Λ, σ ∈ {±1} d = k∈Λ {σ(k) : σ ∈ S k } ("mirrored set"). If Λ ⊂ Z d is centrally symmetric, then Λ ⊕ Λ = Λ ⊖ Λ. If Λ ∈ Z d is fully sign symmetric, then M(Λ) = Λ. For Λ ⊂ Z d , Λ ⊖ Λ is always centrally symmetric (since both k -k ′ and k ′ -k belong to Λ ⊖ Λ when k, k ′ ∈ Λ). Trivially we have #(Λ ⊕ Λ) ≤ (#Λ) 2 , #(Λ ⊖ Λ) ≤ (#Λ) 2 , and #M(Λ) ≤ k∈Λ 2 |k| 0 ≤ 2 d #Λ.
The squaring effect in the upper bounds for the sum/difference set cannot be avoided in general, since even if all multiindices in Λ fall on the first two axes (i.e., all components of k are zero except for one of k 1 and k 2 ), the sum/difference sets will contain a large rectangle (so there is a lower bound of the same order). On the other hand, the 2 d factor in the upper bound for M(Λ) can sometimes be improved, as shown in the forthcoming Lemma 2 and Example 3 below. We also need the next Lemma 1, whose proof uses induction arguments from [START_REF] Migliorati | Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets[END_REF][START_REF] Chkifa | Discrete least-squares polynomial approximation with random evaluations -application to parametric and stochastic elliptic PDEs[END_REF].

Moreover, it holds k∈Λ

2 |k| 0 ≤ (#Λ) ln 3/ ln 2 . (4)
Proof. When η = 0 the result holds true. Consider then the case η ≥ 1. Every downward closed set Λ ⊂ Z d can be seen as a set Λ ⊂ N 2d 0 constructed in the following way. Start with Λ = ∅. For any k ∈ Λ, define the sets C k := {1 ≤ j ≤ d : k j < 0} ⊆ {1, . . . , d} and U k := {1, . . . , d} \ C k . Then define k ∈ N 2d 0 by setting k j = k j and k j+d = 0 for all j ∈ U k , and k j = 0 and k j+d = -k j for all j ∈ C k . Finally add k to Λ. Notice that this algorithm establishes a one-to-one correspondence between the elements of Λ and Λ, and therefore #Λ = # Λ. By construction Λ is also downward closed in N 2d 0 . Applying Theorem 1 from [START_REF] Migliorati | Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets[END_REF] to the set Λ ∈ N 2d 0 we obtain [START_REF] Cohen | On the stability and accuracy of least-squares approximations[END_REF]. For the proof of (4), as above, starting from Λ we construct the downward closed set Λ ⊂ N 2d 0 such that # Λ = #Λ, and then apply Lemma 3.3 from [START_REF] Chkifa | Discrete least-squares polynomial approximation with random evaluations -application to parametric and stochastic elliptic PDEs[END_REF] to the set Λ.

✷ Lemma 2. If Λ ⊂ Z d is downward closed then max k∈Λ 2 |k| 0 ≤ #Λ, k∈Λ 2 |k| 0 ≤ (#Λ) ln 3/ ln 2 , and #M(Λ) ≤ min 2 d #Λ, (#Λ) ln 3/ ln 2 .
Proof. For the first bound, since Λ is downward closed, for any k ∈ Λ, the set Λ will include the hyper-rectangle with k and the origin as corners. Thus #Λ ≥ 1≤j≤d,

k j =0 (1 + |k j |) ≥ 2 |k| 0 .
The second bound is proved in Lemma 1. The third bound is an immediate consequence of the second bound. ✷ Since #Λ most likely grows with d, in general it is not obvious which of 2 d #Λ or (#Λ) ln 3/ ln 2 is a better bound for #M(Λ). If #Λ can be bounded independently of d, then most likely so can #M(Λ).

Example 3. Consider a "weighted" index set of "degree" m ∈ N defined by (see, e.g., [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF]) Λ = {k ∈ N d 0 : r(k) ≤ m}, where r(k) is given by

max 1≤j≤d k j β j , 1≤j≤d k j β j , or d j=1 max 1, k j β j , (5)
with 1 = β 1 ≥ β 2 ≥ • • • > 0 and ∞ j=1 β j < ∞.
The first example is an anisotropic tensor product set and is the largest of the three examples. We have

#Λ = d j=1 (1 + ⌊β j m⌋) ≤ exp(m ∞ j=1 β j ) and #M(Λ) = d j=1 (1 + 2⌊β j m⌋) ≤ exp(2m ∞ j=1 β j )
, so both are bounded independently of d. Their ratio satisfies

#M(Λ) #Λ = d j=1 1 + ⌊β j m⌋ 1 + ⌊β j m⌋ ≤ min 2 J , exp m ∞ j=1 β j ,
where J is the "truncation dimension" such that β j m < 1 for all j ≥ J. If we have λ ∈ (0, 1] such that ∞ j=1 β λ j < ∞, then β J < J -1/λ ( ∞ j=1 β λ j ) 1/λ and it suffices to take J = m λ ( ∞ j=1 β λ j ). Both upper bounds on the ratio grow exponentially with m.

The third example in [START_REF] Cools | Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions[END_REF] is the smallest of the three. Its mirror set is commonly referred to as the "Zaremba cross" or "hyperbolic cross", see, e.g., [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF][START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF]. For all τ > 1 we have

m + 1 ≤ #Λ ≤ m τ d j=1 1 + ζ(τ )β τ j ≤ m τ exp ζ(τ ) ∞ j=1 β τ j , 2m + 1 ≤ #M(Λ) ≤ m τ d j=1 1 + 2ζ(τ )β τ j ≤ (#Λ) τ exp 2ζ(τ ) ∞ j=1 β τ j ,
where ζ(τ ) := ∞ k=1 k -τ is the Riemann zeta function. Since τ can be arbitrarily close to 1, #M(Λ) is essentially of the same order as #Λ, both are bounded independently of d. The upper bound on #M(Λ) is proved in [START_REF] Kuo | Lattice rules for multivariate approximation in the worst case setting[END_REF].

2 Periodic setting based on trigonometric polynomials

Fourier series

We start by considering periodic functions on [0, 1] d . Let F Four denote the space of complexvalued functions defined on [0, 1] d with absolutely converging Fourier series:

F Four := f ∈ L 2 f : [0, 1] d → C, f (x) = h∈Z d f h e 2πi h•x and h∈Z d | f h | < ∞ , where h • x := h 1 x 1 + • • • + h d x d
is the usual dot product and f h are the Fourier coefficients. We equip F Four with the usual L 2 inner product

f 1 , f 2 := [0,1] d f 1 (x)f 2 (x) dx. ( 6
)
The exponential functions form an orthonormal basis e h (x) := e 2πi h•x satisfying e h , e h ′ = δ h,h ′ , where the Kronecker delta function yields 1 if h = h ′ and 0 if h = h ′ . The Fourier coefficients are given by

f h := f, e h = [0,1] d f (x) e -2πi h•x dx, h ∈ Z d . The norm of f satisfies f 2 = [0,1] d |f (x)| 2 dx = h∈Z d | f h | 2 .

Fourier coefficients by cubature

For f ∈ F Four we define the integral operator

I(f ) := [0,1] d f (x) dx.
Later we will seek a cubature formula Q n (f ) which uses linear combinations of n evaluations of f to approximate I(f ). We define a discrete inner product

f 1 , f 2 n := Q n (f 1 f 2 )
as an approximation to [START_REF] Cools | Chebyshev lattices, a unifying framework for cubature with Chebyshev weight function[END_REF].

Given an arbitrary finite index set Λ ⊂ Z d , we consider the subspace F Four Λ of all functions whose Fourier series is supported solely on Λ, i.e.,

for f ∈ F Four Λ : f (x) = h∈Λ f h e 2πi h•x . (7)
Implicitly, this means that all other Fourier coefficients of f are zero, i.e., f h = 0 for h / ∈ Λ. In this paper we will demand one or both of the following related properties on the cubature formula:

• Integral exactness. We want our cubature formula to be exact for all functions which are supported solely on Λ, i.e., we want

Q n (f ) = I(f ) for all f ∈ F Four Λ
. This holds if and only if

Q n (e h ) = I(e h ) = δ h,0 for all h ∈ Λ, i.e., our cubature formula integrates exactly all basis functions e 2πi h•x with h ∈ Λ.

• Function reconstruction. Instead of [START_REF] Dick | Lattice rules for nonperiodic smooth integrands[END_REF] we consider

f a (x) = h∈Λ f a h e 2πi h•x ,
where each Fourier coefficient f h = f, e h = I(f e -h ) in ( 7) is replaced by the cubature formula f a h := f, e h n = Q n (f e -h ). We demand the "non-aliasing" condition that

f a h = f h for all h ∈ Λ and f ∈ F Four Λ , so that f a is a reconstruction of f . (If other coefficients f h ′ with h ′ = h contribute to f a h
then this is called "aliasing".) Using the linearity of Q n , we then have

f a h = Q n (f e -h ) = Q n h ′ ∈Λ f h ′ e h ′ e -h = h ′ ∈Λ f h ′ Q n (e h ′ -h ) = f h for all h ∈ Λ and f ∈ F Four Λ .
This holds if and only if

Q n (e h ′ -h ) = e h ′ , e h = δ h,h ′ for all h, h ′ ∈ Λ,
which is equivalent to

Q n (e h ) = I(e h ) = δ h,0 for all h ∈ Λ ⊖ Λ,
i.e., our cubature formula integrates exactly all basis functions e 2πi h•x with h ∈ Λ ⊖ Λ.

Rank-1 lattice rules

Consider now the cubature formula given by rank-1 lattices

Q n (f ) := 1 n n-1 i=0 f iz mod n n , (8)
where z ∈ Z d is an integer vector known as the generating vector. It is easy to verify the "character property" that for any h ∈ Z d ,

Q n (e h ) = 1 n n-1 i=0 e 2πi ih•z/n = 1 if h • z ≡ n 0, 0 otherwise, (9)
where the notation a ≡ n b means that (a mod n) = (b mod n). This leads to the well-known lattice cubature error formula for

f ∈ F Four Q n (f ) -I(f ) = h∈Z d \{0} h•z≡n0 f h .
The set of integer vectors {h ∈ Z d : h •z ≡ n 0} is known as the dual lattice. Clearly the cubature rule is exact for a function f solely supported on Λ if and only if the dual lattice does not contain any index from Λ \ {0}. We know how to obtain such a lattice rule generating vector using a component-by-component construction.

Lemma 4 (Integral exactness). Let Λ ⊂ Z d be an arbitrary index set. A lattice rule with n points and generating vector z integrates exactly all functions f ∈ F Four Λ solely supported on Λ if and only if

h • z ≡ n 0 for all h ∈ Λ \ {0}.
Such a generating vector z can be constructed component-by-component if n is a prime satisfying

n > max #(Λ\{0}) κ + 1, max(Λ) , with κ = 2 if Λ is centrally symmetric and κ = 1 otherwise.
Proof. The result for some standard anisotropic, downward closed and centrally symmetric sets Λ can be found in Cools, Kuo & Nuyens [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF]. A proof for general index sets is provided later in Section 5, see Theorem 23 and Remark 24. A similar proof can be found in Kämmerer [START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF]. ✷ Lemma 5 (Function reconstruction). Let Λ ⊂ Z d be an arbitrary index set. A lattice rule Q n with n points and generating vector z reconstructs exactly the Fourier coefficients of all functions f ∈ F Four Λ solely supported on Λ, by

f h = f a h := Q n (f e -h ) for all h ∈ Λ, if and only if h • z ≡ n 0 for all h ∈ (Λ ⊖ Λ)\{0}, which is equivalent to h • z ≡ n h ′ • z for all h, h ′ ∈ Λ with h = h ′ .
Such a generating vector z can be constructed component-by-component if n is a prime satisfying

n > max #(Λ ⊖ Λ) + 1 2 , 2 max(Λ) .
Proof. The result follows directly from Theorem 23, noting that the difference set Λ ⊖ Λ is centrally symmetric and contains 0, and therefore

1 2 #((Λ ⊖ Λ) \ {0}) + 1 = 1 2 (#(Λ ⊖ Λ) + 1
). Alternatively, the result for Λ a hyperbolic cross index set can be found in Kämmerer [START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF], while the result for any arbitrary index set Λ can be found in Kämmerer [START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF] and Potts & Volkmer [START_REF] Potts | Sparse high-dimensional FFT based on rank-1 lattice sampling[END_REF]Theorem 2.1]. ✷

We end this section by the very interesting property that mapping from function values to Fourier coefficients and the other way around can be done using a one-dimensional fast Fourier transform. Lemma 6. Let z be a generating vector for an n-point rank-1 lattice satisfying the reconstruction property on an arbitrary index set Λ ⊂ Z d according to Lemma 5. For a function f ∈ F Four Λ solely supported on Λ we can compute coefficients from function values: // prepare function value vector f ∈ C n for i ∈ {0, . . . , n -1}:

f i = f ((iz mod n)/n) // compute coefficient vector F ∈ C n F = FFT(f ) // f h is given by F (h•z mod n)
function values from coefficients: // prepare coefficient vector

F ∈ C n F = 0 ∈ C n for h ∈ Λ: F (h•z mod n) = f h // compute function value vector f ∈ C n f = IFFT(F ) // f i gives the value of f ((iz mod n)/n)
where f ∈ C n is a vector containing function values and F ∈ C n is a vector containing Fourier coefficients. Here FFT and IFFT are the one-dimensional fast Fourier transform and its inverse, respectively, with a normalization 1/n for FFT and 1 for IFFT; both mappings have cost O(n log(n)).

Proof. This follows from expanding the formula for f a h in Lemma 5. Each h ∈ Λ will correspond to a unique value of h • z mod n by the non-aliasing condition in Lemma 5. The other Fourier coefficients are zero by the assumption that f ∈ F Four Λ is solely supported on Λ. ✷ Remark 7. If the function f has wider support in the Fourier space than just Λ, then the vector F resulting from the evaluation F = FFT(f ) will not necessarily be zero at positions F κ when κ does not correspond to a value of h • z mod n for some h ∈ Λ. This is due to the aliasing effect from h outside of Λ and this will also contaminate all other components of F . It is possible to extend the index set to full size n while still keeping the reconstruction property on the extended index set such that all values in F can be interpreted as Fourier coefficients. This technique has been used, e.g., in [START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF][START_REF] Munthe-Kaas | Multidimensional pseudo-spectral methods on lattice grids[END_REF][START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF][START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF].

3 Nonperiodic setting based on half-period cosines

Cosine series

The cosine basis functions are a complete and orthonormal basis for L 2 ([0, 1] d ):

φ k (x) := √ 2 |k| 0 d j=1 cos(πk j x j ), k ∈ N d 0 , (10)
where |k| 0 denotes the count of the nonzero entries in the vector k, and we have

φ k , φ k ′ = δ k,k ′ .
The "cosine space" F cos consists of nonperiodic real-valued functions on [0, 1] d with absolutely converging cosine series:

F cos := f ∈ L 2 f : [0, 1] d → R, f (x) = k∈N d 0 f k φ k (x) and k∈N d 0 | f k | < ∞
where the cosine coefficients are

f k := [0,1] d f (x) φ k (x) dx.
This space was studied for integration and approximation in [START_REF] Dick | Lattice rules for nonperiodic smooth integrands[END_REF][START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF][START_REF] Cools | Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions[END_REF]. Even though the cosine basis is a complete orthonormal system for L 2 ([0, 1] d ), it does not allow the representation of arbitrary polynomials.

Cosine coefficients by cubature

As in Section 2, for a given finite index set Λ ⊂ N d 0 we consider the subspace F cos Λ of all functions whose cosine series is supported solely on Λ, i.e.,

for f ∈ F cos Λ : f (x) = k∈Λ f k φ k (x), (11)
and we are interested in two related properties on the cubature formula:

• Integral exactness. We want Q n (f ) = I(f ) for all f ∈ F cos Λ , which holds if and only if Q n (φ k ) = I(φ k ) = δ k,0 for all k ∈ Λ. (12)
• Function reconstruction. We replace each cosine coefficient

f k = f, φ k = I(f φ k ) in (11) by the cubature formula f a k := f, φ k n = Q n (f φ k )
, and demand the non-aliasing condition

f a k = Q n k ′ ∈Λ f k ′ φ k ′ φ k = k ′ ∈Λ f k ′ Q n (φ k ′ φ k ) = f k for all k ∈ Λ and f ∈ F cos Λ ,
which holds if and only if

Q n (φ k φ k ′ ) = φ k , φ k ′ = δ k,k ′ for all k, k ′ ∈ Λ. ( 13
)
Unlike the Fourier case where a product of two basis functions is another basis function, here the condition [START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF] is not straightforward to simplify, except when the index set Λ is downward closed. In the next section we will obtain necessary and sufficient conditions for function reconstruction by connecting with the Fourier space, without the restriction to downward closed index sets.

Connection with the Fourier case via tent transform

Below we will obtain sufficient conditions to achieve [START_REF] Kämmerer | Interpolation lattices for hyperbolic cross trigonometric polynomials[END_REF] and [START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF] in the cosine space by utilizing a known connection with the Fourier case via the so-called "tent transform"(see, e.g., [START_REF] Hickernell | Obtaining O(N -2+ǫ ) convergence for lattice quadrature rules[END_REF])

ϕ tent : [0, 1] → [0, 1], ϕ tent (x) := 1 -|2x -1|.
The tent transform is a Lebesgue preserving transformation and therefore a componentwise mapping of x ′ = ϕ tent (x) := (ϕ tent (x 1 ), . . . , ϕ tent (x d ))

yields

I(f • ϕ tent ) = [0,1] d f (ϕ tent (x)) dx = [0,1] d f (x ′ ) dx ′ = I(f ).
To get a sense of how this transformation works, it is informative to consider the univariate case:

1 0 f (ϕ tent (x)) dx = 1/2 0 f (2x) dx + 1 1/2 f (2 -2x) dx = 1 0 f (x ′ ) ( 1 2 dx ′ ) + 0 1 f (x ′ ) (-1 2 dx ′ ) = 1 0 f (x ′ ) dx ′ .
In the following, we recall the definition of the "mirrored" index set associated with the index set Λ, M(Λ)

:= {σ(k) : k ∈ Λ, σ ∈ {±1} d } = k∈Λ {σ(k) : σ ∈ S k }, where S k is the set of all unique sign changes of k. Lemma 8 (Integral exactness -sufficiency). Let Λ ⊂ N d 0 be an arbitrary index set. If a cubature rule Q * n (f ) = n-1 i=0 w * i f (t * i )
integrates exactly all Fourier basis functions e h with h ∈ M(Λ), then the cubature rule

Q n (f ) = n-1 i=0 w i f (t i ) with w i = w * i and t i = ϕ tent (t * i )
integrates exactly all cosine space functions f ∈ F cos Λ solely supported on Λ.

Proof. For any k ∈ N d 0 we can write

φ k (x) = √ 2 |k| 0 d j=1 cos(πk j x j ) = 1 √ 2 |k| 0 σ∈S k exp(π i σ(k) • x),
which follows from expanding the product of cos(θ j ) = (e iθ j + e -iθ j )/2 for those θ j = 0. Furthermore, since cos(πk ϕ tent (x)) = cos(2πkx) for all k ∈ N 0 , we also have

φ k (ϕ tent (x)) = 1 √ 2 |k| 0 σ∈S k e σ(k) (x). ( 14
)
Thus if we have a cubature rule Q * n which integrates exactly all Fourier basis functions e σ(k) for all sign changes of k ∈ Λ, then

Q n (φ k ) := Q * n (φ k • ϕ tent ) = 1 √ 2 |k| 0 σ∈S k Q * n (e σ(k) ) (15) = 1 √ 2 |k| 0 σ∈S k δ σ(k),0 = δ k,0 ,
as required for integral exactness in [START_REF] Kämmerer | Interpolation lattices for hyperbolic cross trigonometric polynomials[END_REF]. The cubature rule Q n is obtained from Q * n by applying the tent-transform to the points.

✷ Lemma 9 (Function reconstruction -sufficiency). Let Λ ⊂ N d 0 be an arbitrary index set. If a cubature rule Q * n (f ) = n-1 i=0 w * i f (t * i )
integrates exactly all Fourier basis functions e h with h ∈ M(Λ) ⊕ M(Λ), then the cubature rule Q n (f ) = n-1 i=0 w i f (t i ) with w i = w * i and t i = ϕ tent (t * i ) reconstructs exactly the cosine coefficients of all cosine space functions f ∈ F cos Λ solely supported on Λ.

Proof. For any k, k ′ ∈ N d 0 we have from ( 14) that

φ k (ϕ tent (x)) φ k ′ (ϕ tent (x)) = 1 √ 2 |k| 0 +|k ′ | 0 σ∈S k σ ′ ∈S k ′ e σ(k)+σ ′ (k ′ ) (x).
Thus if we have a cubature rule Q * n which integrates exactly all Fourier basis functions e σ(k)+σ ′ (k ′ ) for all sign changes of k, k ′ ∈ Λ, then

Q n (φ k φ k ′ ) := Q * n ((φ k φ k ′ ) • ϕ tent ) = 1 √ 2 |k| 0 +|k ′ | 0 σ∈S k σ ′ ∈S k ′ Q * n (e σ(k)+σ ′ (k ′ ) ) (16) = 1 √ 2 |k| 0 +|k ′ | 0 σ∈S k σ ′ ∈S k ′ δ σ(k)+σ ′ (k ′ ),0 = 1 √ 2 |k| 0 +|k ′ | 0 σ∈S k σ ′ ∈S k ′ σ ′ j =-σ j when k j =0 δ k,k ′ = δ k,k ′ ,
which is the reconstruction property [START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF]. In the penultimate step we used the property that

σ(k) + σ ′ (k ′ ) = 0 if and only if k = k ′ and σ ′ j = -σ j whenever k j = 0. ✷
Now we consider the situation where the cubature rule Q * n in Lemma 8 and Lemma 9 is a rank-1 lattice rule [START_REF] Hickernell | Obtaining O(N -2+ǫ ) convergence for lattice quadrature rules[END_REF]. In this case, the corresponding cubature rule

Q n (f ) = Q * n (f • ϕ tent ) is often called a tent-transformed lattice rule, given explicitly by Q n (f ) := 1 n n-1 i=0 f ϕ tent iz mod n n .
The character property (9) of lattice rules enables us to conclude that the implications in Lemma 8 and Lemma 9 also hold in the opposite direction, and we obtain necessary and sufficient conditions for tent-transformed lattice rules to achieve our desired properties. Lemma 10 and the "only if" part of Lemma 11 have not been explicitly stated in the literature.

Lemma 10 (Integral exactness). Let Λ ⊂ N d 0 be an arbitrary index set. A tent-transformed lattice rule Q n of a lattice rule Q * n with n points and generating vector z integrates exactly all cosine space functions f ∈ F cos Λ solely supported on Λ if and only if

h • z ≡ n 0 for all h ∈ M(Λ)\{0}.
Such a generating vector z can be constructed component-by-component if n is a prime satisfying

n > max #(M(Λ)\{0}) 2 + 1, max(Λ) .
Proof. The "if" direction follows by combining Lemma 4 with Lemma 8. To prove the "only if" direction, we observe from the character property (9) that the terms Q * n (e σ(k) ) on the right-hand side of (15) can only take the values of 1 or 0 so there can be no cancelation. In particular, when k = 0, if Q n (φ k ) is 0 on the left-hand side of ( 15) then necessarily all terms Q * n (e σ(k) ) are 0 on the right-hand side of [START_REF] Kuo | Lattice rule algorithms for multivariate approximation in the average case setting[END_REF], which implies σ(k) • z ≡ n 0. When k = 0 both sides of (15) are equal to 1, and trivially

Q n (φ 0 ) = 1 implies Q * n (e 0 ) = 1.
The CBC result follows from Theorem 23, noting that M(Λ) is centrally symmetric. ✷ Lemma 11 (Function reconstruction -plan A). Let Λ ⊂ N d 0 be an arbitrary index set. A tenttransformed lattice rule Q n of a lattice rule Q * n with n points and generating vector z reconstructs exactly the cosine coefficients of all cosine space functions f ∈ F cos Λ solely supported on Λ, by

f k = f a k := Q n (f φ k ) = Q * n ((f φ k ) • ϕ tent ) for all k ∈ Λ, if and only if h • z ≡ n 0 for all h ∈ M(Λ) ⊕ M(Λ)\{0}.
Such a generating vector z can be constructed component-by-component if n is a prime satisfying

n > max #(M(Λ) ⊕ M(Λ)) + 1 2 , 2 max(Λ) .
Proof. As in the previous proof, the "if" direction follows by combining Lemma 5 with Lemma 9.

When k = k ′ , if Q n (φ k φ k ′ ) = 0 on the left-hand side of ( 16), then necessarily all terms Q * n (e σ(k)+σ ′ (k ′ ) ) are 0 on the right-hand side of ( 16), since the only permissible values are 0 or 1 due to the character property [START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF]. When k = k ′ , if Q n (φ k φ k ) = 1 on the left-hand side of ( 16), then we have

1 = Q n (φ k φ k ) = 1 2 |k| 0 σ,σ ′ ∈S k σ(k)+σ ′ (k)=0 Q * n (1) + 1 2 |k| 0 σ,σ ′ ∈S k σ(k)+σ ′ (k) =0 Q * n (e σ(k)+σ ′ (k) ) = 1 + 1 2 |k| 0 σ,σ ′ ∈S k σ(k)+σ ′ (k) =0 Q * n (e σ(k)+σ ′ (k) ).
Necessarily, all terms

Q * n (e σ(k)+σ ′ (k) ) must be zero for σ(k) + σ ′ (k) = 0. Hence we conclude that (σ(k) + σ ′ (k)) • z ≡ n 0 for all k, k ′ , σ, σ ′ satisfying σ(k) + σ ′ (k ′ ) = 0. The CBC result follows from Theorem 23.
✷

The tent transformation "stretches and folds the domain" so that essentially one half of the lattice points will land on top of the other half. This is given precisely by the property that

ϕ tent (t i ) = ϕ tent (t n-i ) for 1 ≤ i < n/2.
There is one point at the origin t 0 which will not be duplicated. When n is even, there is one other point ϕ tent (t n/2 ) which will not be duplicated. All other points have a multiplicity of two provided that the generating vector includes at least one component z j such that gcd(n, z j ) = 1.

Typically in a CBC construction we set z 1 = 1. This is sufficient to ensure uniqueness.

Lemma 12. A rank-1 lattice rule with n points and generating vector z ∈ Z d n , where gcd(n, z j ) = 1 for some j, has ⌊n/2 + 1⌋ unique points after tent transform.

Proof. See Suryanarayana, Nuyens & Cools [START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF]. ✷

Alternative approach for function reconstruction

In this subsection we use an alternative approach for function reconstruction. There are two essential ingredients, which we will separate into plan B and plan C below. Firstly, we make use of the tent transform and bi-orthonormality to switch to a simpler set of functions. Secondly, we allow "self-aliasing" of the cubature rule to relax bi-normality and correct for this normalization afterward. We shall see in the next section that this alternative approach has a connection with the method in Potts & Volkmer [START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF].

Remark 13 (Orthonormal and bi-orthonormal families). For function reconstruction we demand that the inner product of all basis functions in our support set are exactly represented by replacing the integral by a cubature rule. An alternative is to be able to exactly represent the inner product of all basis functions with another set of orthogonal functions which have the bi-orthonormal property. In general, if {u k } is an orthonormal basis with u k , u k ′ = δ k,k ′ , and {v k } is an orthogonal set with the bi-orthonormal property

u k , v k ′ = δ k,k ′ , while v k , v k ′ = d k δ k,k ′ with d k not necessarily equal to 1,
then the coefficients of a function f ∈ span{u k } can be calculated by the inner product against either {u k } or {v k } since f, u k = f, v k . A cubature rule which can exactly calculate the inner products u k , v k ′ = δ k,k ′ for all k, k ′ in our support set then also has the reconstruction property. We will make use of such a bi-orthonormal property below.

Lemma 14. For any f ∈ F cos and k ∈ N d 0 , we can write the cosine coefficients in multiple ways

f k = f, φ k = f • ϕ tent , φ k • ϕ tent = f • ϕ tent , √ 2 |k| 0 e k = f • ϕ tent , √ 2 |k| 0 cos(2πk • • ) = f • ϕ tent , √ 2 |k| 0 e σ(k) = f • ϕ tent , √ 2 |k| 0 cos(2πσ(k) • • ) for all σ ∈ S k .
Proof. Using the Lebesgue preserving property of the tent transform and ( 14), we can write

f k = [0,1] d f (ϕ tent (x)) φ k (ϕ tent (x)) dx = 1 √ 2 |k| 0 σ∈S k [0,1] d f (ϕ tent (x)) e σ(k) (x) dx.
For each integral, we apply the change of variables x ′ j = x j if σ j = 1 and x ′ j = 1x j if σ j = -1, and use the properties exp(2πi σ(k)

• x) = exp(2πi k • σ(x)) = exp(2πi k • x ′ ) and ϕ tent (x) = ϕ tent (x ′ ) to deduce that [0,1] d f (ϕ tent (x)) e σ(k) (x) dx = [0,1] d f (ϕ tent (x ′ )) e k (x ′ ) dx ′ for all σ ∈ S k .
Thus all integrals are equal regardless of the sign changes on k. Furthermore, since f is a realvalued function, all its cosine coefficients will be real. Hence we may replace the exponential function e σ(k) by its real part cos(2πσ(k) • • ). ✷

By considering the special case of f = φ k ′ in Lemma 14 we obtain

δ k,k ′ = φ k ′ , φ k = φ k ′ • ϕ tent , √ 2 |k| 0 cos(2πk • • ) for all k, k ′ ∈ N d 0 , (17)
i.e., the functions

{u k = φ k • ϕ tent } and {v k = √ 2 |k| 0 cos(2πk • • )} are bi-orthonormal in L 2 .
Instead of demanding a cubature rule with exactness for the first inner product in (17) (as we did in ( 13)), below we seek a cubature rule with exactness for the second inner product in [START_REF] Kuo | On the power of standard information for multivariate approximation in the worst case setting[END_REF] (see [START_REF] Migliorati | Analysis of discrete L 2 projection on polynomial spaces with random evaluations[END_REF] below), thus preserving bi-orthonormality.

Lemma 15 (Function reconstruction -plan B). Let Λ ⊂ N d 0 be an arbitrary index set. A lattice rule Q * n with n points and generating vector z reconstructs exactly the cosine coefficients of all cosine space functions f ∈ F cos Λ solely supported on Λ, by

f k = f b k := Q * n ((f • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) for all k ∈ Λ, (18)
if and only if

σ(k ′ ) • z ≡ n k • z for all k, k ′ ∈ Λ, σ ∈ S k ′ , σ(k ′ ) = k, (19)
which is equivalent to

h • z ≡ n 0 for all h ∈ (Λ ⊕ M(Λ))\{0}. ( 20
)
Such a generating vector z can be constructed component-by-component if n is a prime satisfying

n > max {#(Λ ⊕ M(Λ)), 2 max(Λ)} .
Proof. Substituting the cosine series of f into [START_REF] Kuo | Lattice algorithms for multivariate L ∞ approximation in the worst-case setting[END_REF], it follows that we have exact reconstruction of the cosine coefficients, i.e.,

f b k = k ′ ∈Λ f k ′ Q * n ((φ k ′ • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) = f k for all f ∈ F cos Λ and k ∈ Λ,
if and only if

Q * n ((φ k ′ • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) = δ k ′ ,k for all k, k ′ ∈ Λ. ( 21
)
It remains to prove that (21) holds if and only if [START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF] holds. Using [START_REF] Kuo | Lattice rules for multivariate approximation in the worst case setting[END_REF] and cos(2πk • • ) = (e k + e -k )/2, we can write

Q * n ((φ k ′ • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) = √ 2 |k| 0 2 • √ 2 |k ′ | 0 σ∈S k ′ Q * n (e σ(k ′ )+k ) + Q * n (e σ(k ′ )-k ) = √ 2 |k| 0 2 • √ 2 |k ′ | 0 σ∈S k ′ Q * n (e -σ(k ′ )+k ) + Q * n (e σ(k ′ )-k ) , ( 22
)
where it is valid to replace one σ(k ′ ) by -σ(k ′ ) since we sum over all unique sign changes. Consider first the case k = k ′ . Then σ(k ′ ) = k. By the character property [START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF] we know that Q * n (e ±(σ(k ′ )-k) ) can only take the values of 1 or 0. Thus ( 22) is equal to 0 if and only if all terms Q * n (e ±(σ(k ′ )-k) ) are 0, which holds following the character property if and only if

σ(k ′ ) • z ≡ n k • z.
Consider now the case k = k ′ . Then we can rewrite [START_REF] Migliorati | Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets[END_REF] as

Q * n ((φ k • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) = 1 + 1 2 σ∈S k σ(k) =k Q * n (e -σ(k)+k ) + Q * n (e σ(k)-k ) . (23)
Using the character property as before, we conclude that ( 23) is equal to 1 if and only if all terms Q * n (e ±(σ(k)-k) ) are 0 whenever σ(k) = k, and in turn this means that σ(k) • z ≡ n k • z except for when σ(k) = k. Combining all conditions, we conclude that (21) holds if and only if [START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF] holds.

Finally [START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF] is clearly equivalent to [START_REF] Martucci | Symmetric convolution and the discrete sine and cosine transforms[END_REF]. The condition on n then follows from Theorem 23, noting that the set Λ ⊕ M(Λ) includes 0 but is not centrally symmetric. ✷

In the next lemma we propose another modification which allows "self-aliasing" in the lattice rule with respect to sign changes (see σ(k) • z ≡ n k • z in (24) below). Consequently, the righthand side of (21) for the case k = k ′ can be an integer c k , not necessarily 1 (see [START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF]

below).

In other words, the cubature rule no longer preserves bi-normality, with normalization to be corrected by this factor c k .

Lemma 16 (Function reconstruction -plan C). Let Λ ⊂ N d 0 be an arbitrary index set. A lattice rule Q * n with n points and generating vector z reconstructs exactly the cosine coefficients of all cosine space functions f ∈ F cos Λ solely supported on Λ, by

f k = f c k := Q * n ((f • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) c k , with c k := # σ ∈ S k : σ(k) • z ≡ n k • z for all k ∈ Λ, (24)
if and only if

σ(k ′ ) • z ≡ n k • z for all k, k ′ ∈ Λ, σ ∈ S k ′ , k = k ′ . ( 25
)
Such a generating vector z can be constructed component-by-component if n is a prime satisfying

n > max {#Λ #M(Λ), 2 max(Λ)} .
Proof. Following the argument in the proof of Lemma 15, we now have exact reconstruction of the cosine coefficients if and only if (instead of ( 21))

Q * n ((φ k ′ • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) = c k δ k ′ ,k for all k, k ′ ∈ Λ. ( 26
)
The case k = k ′ is the same as in Lemma 15. It suffices to reconsider the case k = k ′ . Instead of separating out the term σ(k) = k as in [START_REF] Migliorati | Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets[END_REF], we apply the character property (9) for Q * n (e ±(σ(k ′ )-k) ) in [START_REF] Migliorati | Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets[END_REF] with k = k ′ to arrive at

Q * n ((φ k • ϕ tent ) √ 2 |k| 0 cos(2πk • • )) = 1 2 σ∈S k σ(k)•z≡nk•z 2,
which is equal to c k as required. The CBC result is proved in Theorem 26 later. ✷

Fast calculation of cosine coefficients and function values

Here we can also make use of a one-dimensional fast Fourier transform to map cosine coefficients to function values on the tent-transformed lattice points and vice versa.

f i = f (ϕ tent ((iz mod n)/n)) f n-i = f i // compute coefficient vector F ∈ R n F = FFT(f ) // f k is given by √ 2 |k| 0 F (k•z mod n) /c k function values from coefficients: // prepare coefficient vector F ∈ R n F = 0 ∈ R n for k ∈ Λ: for σ ∈ S k : F (σ(k)•z mod n) = F (σ(k)•z mod n) + f k / √ 2 |k| 0 // compute function value vector f ∈ R n f = IFFT(F ) // f i gives the value of f (ϕ tent ((iz mod n)/n))
where f ∈ R n is a vector containing function values with the symmetry f i = f n-i and F ∈ R n is a vector containing cosine coefficients with the symmetry F κ = F n-κ . Here FFT and IFFT are the one-dimensional fast Fourier transform and its inverse, respectively, with a normalization 1/n for FFT and 1 for IFFT; both mappings have cost O(n log(n)). For plan A and B we set

c k = 1 for all k.
Alternatively, for even n = 2m a length m + 1 DCT-I can be used, while for odd n = 2m -1 a length m DCT-V can be used. In this case the memory requirement and computational effort is halved (w.r.t. a real-to-real FFT).

Proof. We show the result by using the calculation of Lemma 16 (plan C). Plan A and plan B are essentially the same with c k = 1. For all plans we have the option to use the inner product with respect to cos(2π i k • z/n) as given in Lemma 14 since the reconstruction property is guaranteed by the conditions of plan C which is a subset of the conditions of plan B which in turn is a subset of the conditions of plan A.

Let f i := f (ϕ tent ((iz mod n)/n)) for i = 0, . . . , n -1. In all three plans we have for k ∈ Λ,

f k = √ 2 |k| 0 c k 1 n n-1 i=0 f i cos 2π i k • z n = √ 2 |k| 0 c k 1 n n-1 i=0 f i cos 2π i k • z n + i sin 2π i k • z n = √ 2 |k| 0 c k 1 n n-1 i=0 f i exp -2πi i k • z n =: F (k•z mod n)
, which follows because of the symmetry of f i = f n-i due to the tent transform and the odd and even properties of the sine and cosine functions respectively. The last expression is a scaled discrete Fourier transform of length n in terms of i and κ = k • z mod n. This shows the calculation of coefficients from function values by one-dimensional FFT.

Next we consider the evaluation of function values from coefficients. For each i = 0, . . . , n-1, we have from ( 14) that

f i = k∈Λ f k 1 √ 2 |k| 0 σ∈S k exp 2πi i σ(k) • z n = n-1 κ=0 k∈Λ σ∈S k σ(k)•z≡nκ f k 1 √ 2 |k| 0 =: Fκ exp 2πi i κ n ,
where it is unfortunately not possible to avoid considering all sign changes of k. For plan A and plan B there is only one κ associated with each σ(k). For plan C it might occur that different sign changes on the same k map to the same value of κ, hence the summation in the algorithm to prepare the coefficient vector F . Now we explain how to make use of DCT using symmetry. We have f i = f n-i due to the symmetry of ϕ tent . In the formula below, we will write f n/2 which is to be interpreted in the way we just defined for even n, and to be considered equal to zero for odd n. Then, by making use of the symmetry, we have for general n (odd or even)

f k = √ 2 |k| 0 c k 1 n f 0 + 2 ⌊(n-1)/2⌋ i=1 f i cos 2π i κ n + f n/2 cos(π κ) ,
where f n/2 cos(π κ) is only present for even n. Now for n = 2m we have ⌊(n -1)/2⌋ = n/2 -1 = m -1 and we find

f k = √ 2 |k| 0 c k F κ , with F κ := 1 m 1 2 f 0 + m-1 i=1 f i cos π i κ m + 1 2 f m cos(π κ) ,
which is the formula for the one-dimensional DCT-I of length m + 1 to turn the sequence f 0 , f 1 , . . . , f m into the sequence F 0 , F 1 , . . . , F m . For odd n = 2m -1 we have ⌊(n -1)/2⌋ = m -1 and we find

f k = √ 2 |k| 0 c k F κ , with F κ := 1 2m -1 f 0 + 2 m-1 i=1 f i cos 2π i κ 2m -1 ,
which is the formula for the one-dimensional DCT-V of length m to turn the sequence f 0 , f 1 , . . . , f m-1 into the sequence F 0 , F 1 , . . . , F m-1 . For DCT-I and DCT-V see Martucci [START_REF] Martucci | Symmetric convolution and the discrete sine and cosine transforms[END_REF] (definitions (A.1) and (A.5) therein). Similarly, we have F κ = F n-κ so we can write

f i = F 0 + 2 ⌊(n-1)/2⌋ κ=1 F κ cos 2π i κ n + F n/2 cos(π i),
where F n/2 := 0 if n is odd. Therefore DCT-I and DCT-V work in an analogous way. ✷

We note that all coefficients calculated by the FFT are real because of the symmetry in the input, but in a typical implementation one would take the real part in case of a complex FFT routine to remove possible numerical noise. Alternatively one can make use of a special real to real FFT implementation or use a specific implementation for the corresponding DCT.

Similarly to Remark 7, one can also extend the set Λ such that σ(k) • z mod n covers as many values as possible in Z n for functions which are not solely supported on Λ.

4 Nonperiodic setting based on Chebyshev polynomials

Chebyshev series

In the univariate case, the Chebyshev polynomials of the first kind for |x| ≤ 1 can be written

T k (x) = cos(k arccos(x)), k = 0, 1, 2, . . . , for x ∈ [-1, 1].
We have orthogonality with respect to the Chebyshev weight (

√ 1 -x 2 ) -1 : 1 -1 T k (x) T k ′ (x) dx √ 1 -x 2 =      0, if k = k ′ , π, if k = k ′ = 0, π/2, if k = k ′ = 0.
To obtain an orthonormal basis on [-1, 1], we first normalize the measure to 1 by adjusting the Chebyshev weight to (π √ 1x 2 ) -1 . Then we define

η k (x) := T 0 (x) = 1, if k = 0, √ 2 T k (x), if k = 1, 2, . . . ,
and for the multivariate case we define the tensor product basis functions

η k (x) := d j=1 η k j (x j ) = √ 2 |k| 0 d j=1 T k j (x j ), (27)
where, as for cosine basis, |k| 0 denotes the count of the nonzero entries in the vector k.

Let F Cheb denote the space of real valued functions defined on [-1, 1] d with absolutely converging Chebyshev series:

F Cheb := f ∈ L 2 f : [-1, 1] d → R, f (x) = k∈N d 0 f k η k (x) and k∈N d 0 | f k | < ∞ ,
where f k are the Chebyshev coefficients of f . We equip F Cheb with the weighted L 2 inner product

f 1 , f 2 µ := [-1,1] d f 1 (x) f 2 (x) µ(dx), µ(dx) := dx d j=1 π 1 -x 2 j .
The orthonormal Chebyshev basis functions satisfy η k , η k ′ µ = δ k,k ′ . The Chebyshev coefficients are

f k := f, η k µ = [-1,1] d f (x) η k (x) µ(dx).
Given an arbitrary finite index set Λ ⊂ N d 0 , we consider the subspace F Cheb Λ of all functions whose Chebyshev series is supported solely on Λ, i.e.,

for f ∈ F Cheb Λ : f (x) = k∈Λ f k η k (x).

Isomorphism with the cosine space via cosine transform

The Chebyshev basis functions and the cosine basis functions are related by the mapping

η k (x) = φ k (x ′ ) ⇐⇒ arccos(x) = π x ′ ⇐⇒ x = cos(π x ′ ),
where the cosine function and its inverse are applied componentwise. This provides an isomorphism between the Chebyshev setting and the cosine space, with

f ∈ F Cheb ⇐⇒ f cos := f (cos(π • )) ∈ F cos .
To get a sense of how this transformation works, it is informative to consider the univariate case:

1 -1 f (x) dx π √ 1 -x 2 = 0 1 f (cos(πx ′ )) -π sin(πx ′ ) dx ′ π 1 -cos 2 (πx ′ ) = 1 0 f (cos(πx ′ )) dx ′ .
For the multivariate case we have the integral operator

I µ (f ) := [-1,1] d f (x) µ(dx) = [0,1] d f (cos(π x ′ )) dx ′ = I(f (cos(π • ))) = I(f cos ), so that I µ (η k ) = I(φ k ), I µ (η k η k ′ ) = I(φ k φ k ′ ), and
f, η k µ = f (cos(π • )), φ k = f cos , φ k ,
i.e., the Chebyshev coefficients of f are precisely the cosine coefficients of f cos .

Chebyshev coefficients by transformed rank-1 lattice rules

The isomorphism between the spaces means that we can bring all results from the cosine space over to the Chebyshev space. Noting the useful property cos(π ϕ tent (t)) = cos(2π t),

we then arrive at the results for a tent-transformed and then cosine-transformed lattice rule, which is given explicitly by

Q n (f ) := 1 n n-1 i=0 f cos 2π iz mod n n = 1 n n-1 i=0 f cos 2π iz n .
Since cos(2π iz/n) = cos(2π (ni)z/n), the cubature points double up and we can write

Q n (f ) =              f (1) n + f (-1) n + 2 n n/2-1 i=1 f cos 2π iz n if n is even, f (1) n + 2 n (n-1)/2 i=1 f cos 2π iz n if n is odd.
Thus the cubature rule can be computed with ⌊n/2+1⌋ function evaluations, where the cubature weight for i = 0 and i = n/2 (if n is even) are 1/n and the others are 2/n. In general there can be further duplication of points. However, if gcd(z j , n) = 1 for at least one j = 1, . . . , d, then all the ⌊n/2 + 1⌋ points are distinct, see Lemma 12.

For even n = 2m this point set has previously been called a "Chebyshev lattice", see, e.g., [START_REF] Cools | Chebyshev lattices, a unifying framework for cubature with Chebyshev weight function[END_REF][START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF], defined by cos(πiz/m) : i = 0, . . . , m . However, we prefer the interpretation as a tent-transformed and then cosine-transformed lattice, since then we can also use odd n, and the cubature weights are automatically correct according to the multiplicity of the points.

We now state the analogous results to Lemmas 10, 11, 15, 16, 17 from the cosine space. Lemma 21 with even n = 2m in combination with the DCT-I in Lemma 22 is essentially the approach in Potts & Volkmer [START_REF] Potts | Fast and exact reconstruction of arbitratry multivariate algebraic polynomials in Chebyshev form[END_REF]. [START_REF] Cools | Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions[END_REF] The CBC construction

Induction proof for the component-by-component construction

Let Z * n := {1, . . . , n -1} for n prime. The necessary and sufficient conditions on the lattice rule generating vector z ∈ (Z * n ) d for integral exactness and function reconstruction in most cases boil down to the same generic form of verifying for a given index set

A ⊂ Z d that h • z ≡ n 0 for all h ∈ A\{0}. (29)
The following theorem justifies a generic component-by-component (CBC) algorithm to find a z satisfying this condition. The inductive argument needs to work with projections of the index set A down to the lower coordinates. We consider two definitions for the projections since each has its advantages:

either A s := {h ∈ Z s : (h, 0) ∈ A} for s = 1, . . . , d, (30)
or

A s := {h ∈ Z s : (h, h ⊥ ) ∈ A for some h ⊥ ∈ Z d-s } for s = 1, . . . , d. (31)
Both definitions yield A d = A. The definition (30) includes only the indices whose higher components are zero; we shall refer to this as the 'zero' projection. The definition (31) includes all indices obtained by truncating the original indices; we shall refer to this as the 'full' projection.

If the index set A is downward closed then they are the same; otherwise (30) is a subset of [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF].

The full projection [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF] was used in [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF][START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF][START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF]; the zero projection ( 30) is new in this paper. The condition n > max(A) in the theorem guarantees that the components of h ∈ A all satisfy |h j | < n, and thus h j ≡ n 0 if and only if h j = 0. This condition can be replaced by the direct assumption that there is no h ∈ A with a nonzero component h j that is a multiple of n. Theorem 23. Let A ⊂ Z d be an arbitrary index set, and let n be a prime number satisfying

n > max #(A\{0}) κ + 1 , max(A) , (32)
with κ = 2 if A is centrally symmetric and κ = 1 otherwise. Define the projections A s by [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF] or [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF]. Then a generating vector z * = (z 1 , . . . , z d ) ∈ (Z * n ) d can be constructed component-bycomponent such that for all s = 1, . . . , d and z = (z 1 , . . . , z s ) we have

h • z ≡ n 0 for all h ∈ A s \{0}. (33)
Proof. The result for centrally symmetric and downward closed index sets (e.g. hyperbolic cross) or more general index sets with the full projection (31) has been proved in [START_REF] Cools | Constructing lattice rules based on weighted degree of exactness and worst case error[END_REF][START_REF] Kämmerer | Reconstructing hyperbolic cross trigonometric polynomials from sampling along rank-1 lattices[END_REF][START_REF] Kämmerer | Reconstructing multivariate trigonometric polynomials from samples along rank-1 lattices[END_REF]. So we focus on proving the general result with the zero projection [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF].

The proof is by induction on s. We will attempt to derive the condition (32) rather than assuming it from the beginning.

For s = 1, the condition h 1 z 1 ≡ n 0 holds for all z 1 ∈ Z * n if h 1 ≡ n 0, and fails for all z 1 if h 1 ≡ n 0. To avoid the latter scenario we assume that n > |h 1 | always holds. Suppose we already obtained the generating vector z ∈ (Z * n ) s-1 satisfying (33) for A s-1 . For each (h, h s ) ∈ A s \{0}, we will eliminate any 'bad'

z s ∈ Z * n that satisfies (h, h s ) • (z, z s ) ≡ n h • z + h s z s ≡ n 0 ⇔ h s z s ≡ n -h • z. (34)
We stress that (h, h s ) ∈ A s does not imply h ∈ A s-1 under the zero projection [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF]. Depending on the value of h s we have the following scenarios:

1. If h s = 0 then h ∈ A s-1 \{0}; in turn the induction hypotheses (33) for A s-1 guarantees that h • z ≡ n 0 and so [START_REF] Wasilkowski | On the power of standard information for weighted approximation[END_REF] has no solution for z s . There are #(A s-1 \{0}) such cases.

2. If h s = 0 but h s ≡ n 0, then [START_REF] Wasilkowski | On the power of standard information for weighted approximation[END_REF] has no solution for z s if h • z ≡ n 0, or it holds for all z s if h • z ≡ n 0. To avoid the latter scenario we assume that n > |h s | always holds.

3. If h s ≡ n 0 then, since n is prime, (34) has a unique solution for

z s ∈ Z * n if h • z ≡ n 0, or has no solution for z s ∈ Z * n if h • z ≡ n 0.
The latter scenario includes h = 0 so there are at least #A † s such cases, where A † s := {h s ∈ Z : h s ≡ n 0 and (0, h s ) ∈ A s }.

Thus, provided that n > |h s |, there is at most one bad z s to be eliminated for each (h, h s ) ∈ A s \{0}, and the total number of bad z s we eliminate is at most

#(A s \{0})-#(A s-1 \{0})-#A † s . Hence, provided additionally that #Z * n = n -1 > #A s -#A s-1 -#A † s ,
there is always a 'good' z s remaining such that (z, z s ) will satisfy [START_REF] Wasilkowski | Weighted tensor product algorithms for linear multivariate problems[END_REF] for A s . Moreover if A is centrally symmetric, then all A s are centrally symmetric, and both (h ′ , h s ) and (-h, -h s ) will eliminate the same z s if a solution for (34) exists. It then suffices to demand that n -

1 > (#A s -#A s-1 - #A † s )/2. By induction, to ensure that a good z * ∈ (Z * n ) d exists, it suffices to assume that n > max max s=2,...,d #A s -#A s-1 -#A † s κ + 1 , max s=1,...,d max h∈As |h s | ,
with κ = 2 if A is centrally symmetric and κ = 1 otherwise. This leads to the simplified condition on n in the theorem. Now for completeness we discuss briefly the case for the full projection [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF]. The proof is almost identical to the case for the zero projection but is slightly simpler. The subtle difference is that for each (h, h s ) ∈ A s we now have h ∈ A s-1 regardless of the value of h s , and the induction hypothesis [START_REF] Wasilkowski | Weighted tensor product algorithms for linear multivariate problems[END_REF] for A s-1 guarantees that h • z ≡ n 0 if h s = 0, thus simplifying the second and third scenarios above. ✷

Algorithmic aspects of the CBC construction

Remark 24. For the projections A s defined by either (30) or (31), Theorem 23 and its proof justify two different approaches to carry out the component-by-component construction:

• Brute force approach: At step s, we search through z s ∈ Z * n until we find one that satisfies (33) for all h ∈ A s \{0}. The cost is O(n fail #A s ), where n fail is the number of different z s that was checked. So the cost is at worst O(n #A s ), leading to a total cost of O(d n #A).

• Elimination approach: At step s, we loop through every h ∈ A s \ {0} and eliminate the corresponding z s ∈ Z * n that fails [START_REF] Wasilkowski | Weighted tensor product algorithms for linear multivariate problems[END_REF], if any. Then we take any remaining z s . The cost is only O(#A s ), leading to a total cost of O(d #A).

In both approaches we have left out the O(s) factor in step s that arises from the evaluation of dot products; this is valid if we store and update the values of h • z for all h in each step. In the elimination approach we mark the bad choices of z s in an array of length n -1 with pointers linking the previous and next good choices of z s , so that it is O(1) cost to obtain a good z s at the end.

The two approaches may be used for different steps in the algorithm if it is advantageous to mix them. Both approaches are guaranteed to succeed provided n is sufficiently large, see [START_REF] Volkmer | sparseFFTr1l software library[END_REF]. We can run the algorithm with smaller values of n (or even composite values of n in the brute force approach), and be prepared to increase n when the algorithm fails. Once a z is found, we can systematically test and reduce the value of n by verifying whether (33) still holds for A.

In general the zero projections [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF] are subsets of the full projections [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF], and consequently the condition [START_REF] Wasilkowski | Weighted tensor product algorithms for linear multivariate problems[END_REF] is weaker and faster to check for (30) than for [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF]. There are also algorithmic advantages in the data structure for iterating the sets based on [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF], namely, that the indices can be ordered according to the number of zeros at the end.

We now apply Theorem 23 to the situation where the input set A is a difference set, i.e., A = Λ ⊖ Λ. Then the condition ( 33) is now explicitly given by

h • z ≡ n 0 for all h ∈ (Λ ⊖ Λ) s \ {0}, (35)
where (Λ ⊖ Λ) s denote the projection of the difference set Λ ⊖ Λ defined according to [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF] or [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF]. Since #(Λ ⊖ Λ) ≤ (#Λ) 2 , Remark 24 indicates that the cost of CBC construction for

A = Λ ⊖ Λ is O(d n (#Λ) 2 ) or O(d (#Λ) 2
) for the two approaches, respectively.

Similarly, for all sign changes on an index set Λ we have #M(Λ) ≤ 2 d #Λ and therefore the cost of CBC construction for

A = M(Λ) ⊕ M(Λ) is O(d n 2 2d (#Λ) 2 ) or O(d 2 2d (#Λ) 2 ); the cost for A = Λ ⊕ M(Λ) is O(d n 2 d (#Λ) 2 ) or O(d 2 d (#Λ) 2 ).
Hence, we can apply Theorem 23 and Remark 24 to the Fourier space in Lemmas 4 and 5, noting that the difference set Λ ⊖ Λ is always centrally symmetric and contains the zero vector. Analogously, we can apply Theorem 23 and Remark 24 to the cosine space in Lemmas 10 and 11, as well as Lemma 15 -plan B, and correspondingly, to the Chebyshev space in Lemmas 18,[START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF][START_REF] Martucci | Symmetric convolution and the discrete sine and cosine transforms[END_REF] However, plan C for the cosine space and Chebyshev space, see Lemmas 16 and 21, respectively, cannot be formulated in the same generic form [START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF]. So we will need to develop a separate justification for it. We will return to this later in Subsection 5.5.

Smart lookup for the brute force approach with full projection

When A s are full projections [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF], we have the important property that the projection of the difference set equals the difference set of the projections, i.e., (Λ ⊖ Λ) s = Λ s ⊖ Λ s for the full projection [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF]. [START_REF] Zeng | Spline methods using integration lattices and digital nets[END_REF] Thus the condition [START_REF] Zeng | Error analysis of splines for periodic problems using lattice designs[END_REF] becomes

h • z ≡ n 0 for all h ∈ (Λ s ⊖ Λ s )\{0},
which is equivalent to

h • z ≡ n h ′ • z for all h, h ′ ∈ Λ s with h = h ′ . ( 37
)
In other words, every dot product needs to have a unique value.

The following code snippet shows that it is possible to verify condition (37) for a given z with cost O(#Λ s ) rather than O((#Λ s ) 2 ), by marking a bit string of length n for the values of dot product modulo n that have occurred.

// Fourier space // INPUT: z, n and Λ s // VERIFY: h

• z ≡ n h ′ • z for all h, h ′ ∈ Λ s , h = h ′ // COST: O(#Λ s ) // VERIFY: σ(k ′ ) • z ≡ n k • z for all k, k ′ ∈ Λ s , σ ∈ S k ′ , σ(k ′ ) = k // COST: O(#M(Λ s )) S 1 = 0 S 2 = 0 for k ∈ Λ s : α = k • z mod n if S 2 [α] = 1: return FALSE // note: the value of S 1 [α] is also checked since S 1 ⊆ S 2 S 2 [α] = 1 S 1 [α] = 1 for h ∈ {σ(k) : σ ∈ S k } with h = k: α ′ = h • z mod n if S 1 [α ′ ] = 1: return FALSE S 2 [α ′ ] = 1 // note: it does not matter if S 2 [α ′ ] is already set return TRUE
The previous algorithm can now be modified to allow self-aliasing and to keep track of the constant c k , see Lemma 16 for cosine space and Lemma 21 for Chebyshev space.

// Cosine space and Chebyshev space --plan C // INPUT: z, n and Λ s // VERIFY:

σ(k ′ ) • z ≡ n k • z for all k, k ′ ∈ Λ s , σ ∈ S k ′ , k ′ = k // COST: O(#M(Λ s )) S 1 = 0 S 2 = 0 for k ∈ Λ s : α = k • z mod n if S 2 [α] = 1: return FALSE S 2 [α] = 1 c k = 1 for h ∈ {σ(k) : σ ∈ S k } with h = k: α ′ = h • z mod n if α ′ = α: c k += 1 if S 1 [α ′ ] = 1: return FALSE S 2 [α ′ ] = 1 S 1 [α] = 1 return TRUE with {c k : k ∈ Λ s }
The crucial difference between the last two code snippets is that in plan B the bit S 1 [α] is marked before the dot products α ′ from the sign changes are checked against S 1 , thus not allowing α ′ = α (no aliasing), while in plan C the bit S 1 [α] is marked only after all α ′ have been checked against S 1 , thus allowing α ′ = α and indeed counts the number of times this occurs in c k (self-aliasing).

We summarize this subsection in the following remark.

Remark 25. The cost for brute force CBC in step s with full projection (31) and smart lookup is

O(n fail #Λ s ), O(n fail #M(Λ s )), O(n fail #M(Λ s )),
for the index sets A = Λ ⊖ Λ, A = M(Λ) ⊕ M(Λ) and A = Λ ⊕ M(Λ), respectively.

Similar strategies have been implemented in the sparseFFTr1l software library of Toni Volkmer [START_REF] Volkmer | sparseFFTr1l software library[END_REF].

Mixed CBC construction

Combining Remark 25 with Remark 24, we see that there is advantage in mixing the two different approaches. As long as n fail remains small it is advantageous to follow the brute force approach with full projection [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF] and smart lookup. We anticipate this to be the case for the initial dimensions.

Starting from z 1 = 1, at step s we begin our brute force search with the value z s = z s-1 + 1. If this z s fails then we increment again by 1 and do this repeatedly (if n -1 is reached then we continue from 1) until a valid z s is found, while keeping a count on n fail . Then gradually as the dimension increases and as we run out of choices, we expect the value of n fail to increase until at some point the balance tips over the other way and it becomes cheaper to follow the elimination approach. From then on we switch over to the elimination approach in the generic formulation [START_REF] Suryanarayana | Reconstruction and collocation of a class of nonperiodic functions by sampling along tent-transformed rank-1 lattices[END_REF] with the zero projection [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF] so that the sets are smaller (except for the case of plan C which we discuss in the next subsection).

We summarize our results for the different spaces in Table 1. Recall that the condition ( 25) is weaker than the condition [START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF], which is in turn equivalent to [START_REF] Martucci | Symmetric convolution and the discrete sine and cosine transforms[END_REF]. Thus when we have the full projection [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF], the condition on n in Theorem 23 guarantees the existence of z s with the required property in step s. However, to prove that the CBC construction can find this vector, we need a new CBC proof.

(a) h • z ≡ n 0 for all h • z ≡ n 0 for all h • z ≡ n 0 for all NA h ∈ (Λ ⊖ Λ) s \{0} h ∈ (M(Λ)⊕M(Λ)) s \{0} h ∈ (Λ ⊕M(Λ)) s \{0} (b) h • z ≡ n h ′ • z σ ′ (k ′ ) • z ≡ n σ(k) • z σ(k ′ ) • z ≡ n k • z σ(k ′ ) • z ≡ n k • z for all h, h ′ ∈ Λ s , for all k, k ′ ∈ Λ s , for all k, k ′ ∈ Λ s , for all k, k ′ ∈ Λ s , h = h ′ σ ∈ S k , σ ′ ∈ S k ′ , σ ∈ S k ′ , σ ∈ S k ′ , σ ′ (k ′ ) = σ(k) σ(k ′ ) = k k = k ′ (c) n ∼ #(Λ ⊖ Λ) s n ∼ #(M(Λ)⊕M(Λ)) s n ∼ #(Λ⊕M(Λ)) s n ∼ #Λ s #M(Λ s ) (d) #(Λ ⊖ Λ) s #(M(Λ)⊕M(Λ)) s #(Λ⊕M(Λ)) s NA (e) n fail #(Λ ⊖ Λ) s n fail #(M(Λ)⊕M(Λ)) s n fail #(Λ⊕M(Λ)) s NA (f) (#Λ s ) 2 (#M(Λ s )) 2 #Λ s #M(Λ s ) #Λ s #M(Λ s ) (g) n fail (#Λ s ) 2 n fail (#M(Λ s )) 2 n fail #Λ s #M(Λ s ) (h) n fail #Λ s n fail #M(Λ s ) n fail #M(Λ s ) (i) n fail ∼ #Λ s n fail ∼ #M(Λ s ) n fail ∼ #M(Λ s ) (j) d (#Λ) 2 d (#M(Λ)) 2 d #Λ #M(Λ) (
where the sum is over Z d (for Fourier space) or N d 0 (for cosine and Chebyshev spaces). Now consider a subset Λ of the indices and represent the exact L 2 µ projection of f , i.e., the best L 2 µ approximation on Λ, by

f Λ = k∈Λ f k α k .
We cannot calculate these coefficients f k exactly and will have to approximate them, leading to for Chebyshev space plan A, B, C, We demand from our lattice rule that

f Λ = k∈Λ f k α k , with ∈
α k • ϕ = u k = exp(2πi h • x) for Fourier space, √ 2 |k| 0 d j=1 cos(2π k j x j ) for cosine/Chebyshev space plan A, B, C, v k = u k for Fourier space, cosine/Chebyshev space plan A, √ 2 |k| 0 cos(2π k • x) for cosine/Chebyshev space plan B, C. Then we have u k , u k ′ = δ k,k ′ , u k , v k ′ = δ k,k ′ , and v k , v k ′ = d k δ k,k ′ , with d k = 2 |k| 0 -1 for k = 0 in
Q n (u k v k ′ ) = c k δ k,k ′ ∀k, k ′ ∈ Λ, (41)
Q n (v k v k ′ ) = d k δ k,k ′ ∀k, k ′ ∈ Λ, (42)
where c k in the case of cosine or Chebyshev space plan C (see [START_REF] Munthe-Kaas | Multidimensional pseudo-spectral methods on lattice grids[END_REF] or ( 28)) can be a positive integer up to the number of unique sign changes of k, i.e., 1 ≤ c k ≤ 2 |k| 0 , and c k = 1 otherwise. Note that we do not necessarily have

Q n (u k u k ′ ) = δ k,k ′ (except for when v k = u k ).
With the above unifying notation, and with w i = 1/n and t i our lattice points, we can write our approximate coefficient as

f k = Q n (f • ϕ v k ) c -1 k = n-1 i=0 w i f (ϕ(t i )) v k (t i ) c -1 k , k ∈ Λ . (43)
In comparison, the exact coefficient is given by

f k = f, α k µ = f • ϕ, u k = f • ϕ, v k .

Connection to discrete least squares

With a prescribed ordering of the elements in Λ, the approximate coefficients (43) for k ∈ Λ can be written in matrix-vector notation as

f = C -1 V * W f ϕ , with column vectors f ϕ = [f (ϕ(t i ))] i , f = [ f k ] k , and matrices V = [v k (t i )] i,k , C = diag(c k ),
and W = diag(w i ). The conditions (41) and (42) can be expressed as

V * W U = C and V * W V = D, with matrices U = [u k (t i )] i,k and D = diag(d k ).
For plan A (or for the Fourier case) we have U = V and C = D = I, so

f a = U * W f ϕ ,
which is precisely the solution to the normal equations

(W 1/2 U ) * W 1/2 U f a = (W 1/2 U ) * W 1/2 f ϕ ⇔ (U * W U ) f a = U * W f ϕ ⇔ f a = U * W f ϕ ,
which in turn solves the discrete least-squares problem

min f a W 1/2 U f a -W 1/2 f ϕ 2 2 .
Plan B and plan C do not have the least-squares interpretation.

Stability to perturbation

Suppose that there is perturbation error in the function evaluations in (43) so that instead of f (ϕ(t i )) we have

f pert (ϕ(t i )) = f (ϕ(t i )) + ε i , i = 0, . . . , n -1.
We denote the corresponding perturbed approximate coefficients by f k,pert and the corresponding approximate function over Λ by f Λ,pert for ∈ {a, b, c}. Using (43), we can write

f Λ,pert -f Λ 2 L 2 µ = k∈Λ | f k,pert -f k | 2 = k∈Λ n-1 i=0 w i (f pert -f )(ϕ(t i )) v k (t i ) c -1 k 2 = C -1 V * W ε 2 2 , with column vector ε = [ε i ] i . We have C -1 V * W ε 2 2 = C -1 D 1/2 (D -1/2 V * W 1/2 ) W 1/2 ε 2 2
, where (D -1/2 V * W 1/2 ) (W 1/2 V D -1/2 ) = D -1/2 V * W V D -1/2 = I, so that D -1/2 V * W 1/2 2 = 1. Thus

f Λ,pert -f Λ 2 L 2 µ = C -1 V * W ε 2 2 ≤ C -1 D 1/2 2 2 W 1/2 ε 2 2 = max k∈Λ d k c 2 k =: ρ Λ 1 n n-1 i=0 |ε i | 2 .
Here ρ Λ is the stability constant, and we have

ρ a Λ = 1, ρ b Λ = max 1 0∈Λ , max k∈Λ\{0}
2 |k| 0 -1 , ρ c Λ = max 1 0∈Λ , max k∈Λ\{0}
2 |k| 0 -1 c 2 k , (44)
where 1 0∈Λ is 1 if 0 ∈ Λ and is 0 otherwise. For plan A the approximation is perfectly stable.

For plan B and plan C we have the general upper bound ρ c Λ ≤ ρ b Λ ≤ 2 d-1 which might be too pessimistic. If we have a weighted index set with decaying weights (see Example 3) ρ b Λ could be much smaller. Alternatively, if Λ is downward closed then by Lemma 2 we have ρ c Λ ≤ ρ b Λ ≤ #Λ. In any case, the stability constant for plan B is likely to be much bigger than 1 even if it is independent of d.

For plan C the values of c k depend on the lattice rule and can potentially be as large as 2 |k| 0 , giving hope that one may attempt to minimize the stability constant ρ c Λ as part of the CBC construction of the lattice generating vector. Unfortunately, numerical experiments show that not much improvement can be obtained because "self-aliasing" does not happen often enough.

Comparison with previous results from the literature and conclusions

Approximation by discrete least-squares has been analysed for different measures µ and bases {α k } in several works. We mention for instance [START_REF] Chkifa | Discrete least-squares polynomial approximation with random evaluations -application to parametric and stochastic elliptic PDEs[END_REF][START_REF] Cohen | On the stability and accuracy of least-squares approximations[END_REF][START_REF] Migliorati | Analysis of discrete L 2 projection on polynomial spaces with random evaluations[END_REF] when using evaluations at random points, and in [START_REF] Migliorati | Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets[END_REF][START_REF] Narayan | Multivariate discrete least-squares approximations with a new type of collocation grid[END_REF] when random points are replaced by deterministic point sets. A common denominator in all the aforementioned analyses is the equivalence of the norm • L 2 µ and a suitably defined discrete seminorm • n , on the finite-dimensional space F Λ . More precisely, there exists δ ∈ [0, 1) such that, under appropriate conditions on n, #Λ and δ, it holds that

(1 -δ) f 2 L 2 µ ≤ f 2 n ≤ (1 + δ) f 2 L 2 µ , for all f ∈ F Λ . (49)
Under the same conditions between n, #Λ and δ that ensure (49), the discrete least-squares approximation Π n f of any f ∈ F satisfies

f -Π n f L 2 µ ≤ 1 + 1 1 -δ inf v∈F Λ f -v L ∞ , (50)
see [21, Proposition 1] for a proof.

Our results for the Fourier space and for plan A of the cosine and Chebyshev spaces achieve exactly δ = 0; see also (48) with ρ a Λ = 1. For the Fourier case we obtain essentially a scaling of n ≥ (#Λ) 2 . For the cosine and Chebyshev spaces we obtain essentially n ≥ 4 d (#Λ) 2 in general, and n ≥ min(4 d (#Λ) 2 , (#Λ) 2 ln 3/ ln 2 ) for downward closed index sets. However, if the mirrored index set is a weighted hyperbolic cross with sufficiently fast decaying weights (see Example 3), then we obtain essentially n ≥ c τ (#Λ) 2τ for τ > 1 arbitrarily close to 1.

With the Chebyshev space and for any downward closed set Λ, these results improve on [START_REF] Narayan | Multivariate discrete least-squares approximations with a new type of collocation grid[END_REF] where it is proven that (49) holds true if n ≥ 2 2d+1 d 2 (#Λ) 2 .

Moreover, we mention that in the case of uniform measure µ and expansion on the Legendre basis, the results in [START_REF] Migliorati | Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets[END_REF] show a scaling of n/(ln n) d as (#Λ) 4 for general downward closed sets, and a scaling of n/(ln n) d as (#Λ) 2 when F Λ is an anisotropic tensor product space.

Our results for plans B and C in the cosine and Chebyshev spaces do not have the discrete least-squares interpretation. All three plans give exact function reconstruction in F Λ , but for a general f ∈ F not finitely supported on Λ, there is a trade-off between the approximation error and the requirement on n (e.g., plan A requires n to be larger but also has the smallest constant ρ a Λ ). Therefore it is not easy to directly compare them without further analysis. To proceed further from the very general result in Theorem 27, one would need to make further assumptions on, for example, the smoothness properties of the function space, and the knowledge of a corresponding index set that has been chosen to take advantage of such properties. Starting from the loose upper bound (48), if we know that the best L ∞ approximation error satisfies ff Λ L ∞ ≤ c q (#Λ) -q for some q > 0, see, e.g., [START_REF] Kuo | Multivariate L ∞ approximation in the worst case setting over reproducing kernel Hilbert spaces[END_REF], then we arrive at ff Λ L 2 µ ≤ 1 + ρ Λ c q (#Λ) -q . For the Fourier space we have ρ a Λ = 1 and n needs to be proportional to #(Λ⊖Λ) ≤ (#Λ) 2 , leading to f -f a Λ L 2 µ = O(n -q/2 ), where the implied constant is independent of d if c q is independent of d. For the cosine or Chebyshev space, the result is more complicated because it depends on the size of the mirrored index set. If we have a weighted hyperbolic cross with sufficiently decaying weights (see Example 3) then the mirrored set itself is not of concern. However, for plan B or C we need to further take into account the value of ρ b Λ or ρ c Λ . In general ρ b Λ and ρ c Λ can be much worse than ρ a Λ = 1, but depending on the actual index set they might also be manageable.

Finally we stress that the L 2 approximation result based on the estimate (48) is not sharp, and neither is (50), because the best L 2 approximation error ff Λ L 2 µ , i.e., the first term on the right-hand side of (47), has been estimated by the best L ∞ approximation error ff Λ L ∞ , which is generally half an order worse in the convergence rate (e.g., rate p for L 2 versus rate p -1/2 = q for L ∞ ), see, e.g., [START_REF] Kuo | On the power of standard information for multivariate approximation in the worst case setting[END_REF]. Moreover, a direct analysis on the discrete norm ff Λ n , i.e., the second term on the right-hand side of (47), based on properties of the lattice points, has a chance to improve upon the best L ∞ approximation error too. Indeed, function approximation based on rank-1 lattices has been analyzed in [START_REF] Cools | Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions[END_REF][START_REF] Kuo | Lattice rules for multivariate approximation in the worst case setting[END_REF][START_REF] Kuo | Lattice rule algorithms for multivariate approximation in the average case setting[END_REF][START_REF] Kuo | Lattice algorithms for multivariate L ∞ approximation in the worst-case setting[END_REF] where the lattice generating vectors were constructed to minimize the approximation error directly, without the reconstruction property. It is known that if p is the rate of convergence for the best L 2 approximation error (rather than L ∞ ) then lattice generating vectors can be constructed to achieve ff a Λ L 2 µ = O(n -p/2 ). There are also other approximation results using rank-1 or multiple rank-1 lattices, see, e.g., [START_REF] Byrenheid | Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling[END_REF][START_REF] Kämmerer | Interpolation lattices for hyperbolic cross trigonometric polynomials[END_REF][START_REF] Kämmerer | Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices[END_REF][START_REF] Li | Trigonometric spectral collocation methods on lattices[END_REF][START_REF] Zeng | Error analysis of splines for periodic problems using lattice designs[END_REF][START_REF] Zeng | Spline methods using integration lattices and digital nets[END_REF].

Rank-1 lattices are very attractive due to their simplicity and stability, and the availability of fast computation methods compared to other approximation algorithms.

  For σ ∈ {±1} d and k ∈ Z d , we write σ(k) := (σ 1 k 1 , . . . , σ d k d ) to mean that we apply the sign changes in σ componentwise to k. For any k ∈ Z d we use S k := σ ∈ {±1} d : σ j = +1 for each j for which k j = 0 to denote a set of unique sign changes for k. Then clearly we have #S k = 2 |k| 0 .

Lemma 1 .

 1 In any dimension d, given any Λ ⊂ Z d downward closed and any polynomial p(n) = η k=0 b k n k of degree η ≥ 0 with nonnegative coefficients b 0 ≤ 1 and all b k ≤ η+1 k , it holds k∈Λ d j=1 p(|k j |) ≤ (#Λ) η+1 .

Lemma 17 .

 17 Let z be a generating vector for an n-point rank-1 lattice satisfying the reconstruction property on an arbitrary index set Λ ⊂ N d 0 according to Lemma 11 (plan A), Lemma 15 (plan B ) or Lemma 16 (plan C ). For a function f ∈ F cos Λ solely supported on Λ we can compute coefficients from function values: // prepare function value vector f ∈ R n f 0 = f (0) for i ∈ {1, . . . , ⌊n/2⌋}:

Lemma 22 .

 22 We can use FFTs or DCTs to map Chebyshev coefficients to function values on tent-transformed and then cosine-transformed lattice points, and the other way round, for an n-point rank-1 lattice rule with generating vector z satisfying the non-aliasing conditions of Lemma 19 (plan A), Lemma 20 (plan B ) or Lemma 21 (plan C ) on an arbitrary index set Λ ⊂ N d 0 by replacing ϕ tent ( • ) by cos(π ϕ tent ( • )) in the statement of Lemma 17.

  a) Standard formulation of the reconstruction condition at step s with full/zero projection (b) Equivalent formulation of the reconstruction condition at step s with full projection (c) Required size of n to guarantee success at step s (also need n to cover spread of index set) (d) Cost of elimination approach at step s based on (a) with full/zero projection (e) Cost of brute force approach at step s based on (a) with full/zero projection (f) Cost of elimination approach at step s based on (b) with full projection (g) Cost of brute force approach at step s based on (b) with full projection (h) Cost of brute force approach at step s based on (b) with full projection and smart lookup (i) Switching point on n fail from brute force (h) to elimination (d)/(f) (j) Total cost of mixed CBC: brute force until n fail reaches switching point then elimination 5.5 A new CBC proof for plan C

  {a, b, c} denoting the approximation by plan A (including the Fourier case), plan B, ϕ tent for cosine space plan A, B, C, cos(π ϕ tent ( • ))

  the case of cosine or Chebyshev space plan B or C and d k = 1 otherwise.

  Analogous definition holds with N d 0 replaced by Z d .

	For any index set Λ ⊂ N d 0 or Λ ⊂ Z d , we denote its largest component in magnitude by
	max(Λ) := max k∈Λ	max 1≤j≤d	|k j |,
	and we define

Table 1 :

 1 Summary of CBC algorithms for function reconstruction

	Fourier space	Cosine space and Chebyshev space
	Plan A	Plan B	Plan C

Lemma 18 (Integral exactness). Let Λ ⊂ N d 0 be an arbitrary index set. A tent-transformed and then cosine transformed lattice rule with n points and generating vector z integrates exactly (against the Chebyshev density) all Chebyshev space functions f ∈ F Cheb Λ solely supported on Λ if and only if h • z ≡ n 0 for all h ∈ M(Λ)\{0}.

Such a generating vector z can be constructed component-by-component if n is a prime satisfying n > max #(M(Λ)\{0}) 2 + 1, max(Λ) .

Lemma 19 (Function reconstruction -plan A). Let Λ ⊂ N d 0 be an arbitrary index set. A lattice rule Q * n with n points and generating vector z reconstructs exactly the Chebyshev coefficients of all Chebyshev space functions f ∈ F Cheb Λ solely supported on Λ, by

Such a generating vector z can be constructed component-by-component if n is a prime satisfying

Lemma 20 (Function reconstruction -plan B). Let Λ ⊂ N d 0 be an arbitrary index set. A lattice rule Q * n with n points and generating vector z reconstructs exactly the Chebyshev coefficients of all Chebyshev space functions f ∈ F Cheb Λ solely supported on Λ, by

Such a generating vector z can be constructed component-by-component if n is a prime satisfying

Lemma 21 (Function reconstruction -plan C). Let Λ ⊂ N d 0 be an arbitrary index set. A lattice rule Q * n with n points and generating vector z reconstructs exactly the Chebyshev coefficients of all Chebyshev space functions f ∈ F Cheb Λ solely supported on Λ, by

if and only if

Such a generating vector z can be constructed component-by-component if n is a prime satisfying

Consequently, we can reduce the cost of the brute force CBC construction for

We shall refer to this as the "smart lookup" trick.

We stress once again that [START_REF] Zeng | Spline methods using integration lattices and digital nets[END_REF] only holds when we have the full projection [START_REF] Suzuki | Rank-1 lattices and higher-order exponential splitting for the timedependent Schrödinger equation[END_REF]. Under the zero projection [START_REF] Suzuki | Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation[END_REF] we would have in general (Λ ⊖ Λ) s ⊇ Λ s ⊖ Λ s ; in this case the alternative formulation (37) would miss out on some indices.

Similar reduction in cost can be achieved for A = M(Λ) ⊕ M(Λ) as we show in the code snippet below.

// Cosine space and Chebyshev space --plan A // INPUT: z, n and Λ s // VERIFY:

We can save on half of the calculations, since if k = 0 we can fix one of the signs for a non-zero element of k to get half of the sign changes and multiply by -1 to get the other half as shown below.

// Cosine space and Chebyshev space --plan A --halved // INPUT: z, n and Λ s // VERIFY:

We can achieve a similar reduction in cost for A = Λ ⊕ M(Λ), but this is more complicated because we need to distinguish between the dot products coming from the original indices and the dot products coming from sign changes of the indices. We do this by keeping two bit strings of length n as shown in the code snippet below: S 1 marks the original dot products, while S 2 marks the dot products from all sign changes thus including S 1 . (We can also half the cost as above but we do not include that here.) // Cosine space and Chebyshev space --plan B // INPUT: z, n and Λ s Thus, provided that n > 2 max (k,ks)∈Λs |k s |, there is at most one bad z s to be eliminated for each distinct pair (k, k s ), (k ′ , k ′ s ) ∈ Λ s and each (σ, σ s ) ∈ S (k ′ ,k ′ s ) , so the total number of bad z s we eliminate is at most #Λ s (#M(Λ s ) -1).

Hence, provided additionally that #Z * n = n -1 > #Λ s (#M(Λ s ) -1), there is always a 'good' z s remaining such that (z, z s ) will satisfy (39) for Λ s . By induction, to ensure that a good z * ∈ (Z * n ) d exists, it suffices to assume that n satisfies (38). This completes the proof. ✷

Approximation

We now discuss function approximation for all three settings under a unified framework. A major difference of this section compared to the previous sections is that the function f under consideration is no longer supported only on a finite index set. We cannot achieve exact function reconstruction and therefore an error analysis is needed.

Function approximation under a unified framework

We have an orthonormal basis {α k } for L 2 µ (Ω), where µ(Ω) = 1, and consider functions with absolutely converging series expansions

Error analysis

We have for our three plans A (including the Fourier space), B, and C, annotated by ∈ {a, b, c},

The first part is the truncation error for the finite index set Λ, and thus represents the best L 2 µ approximation error for the choice of Λ. In the Information Based Complexity (IBC) error analysis, this would be a complexity result using arbitrary linear information: if we know more about the smoothness class of our functions, then this bound is known in terms of a set Λ which is constructed according to the decay of the singular values of the approximation operator and this error is exactly the next singular value, see, e.g., [START_REF] Wasilkowski | Weighted tensor product algorithms for linear multivariate problems[END_REF]. The second part is how well we approximate this best possible approximation by our numerical algorithm which only uses function values; in IBC this is known as standard information, see, e.g., [START_REF] Wasilkowski | On the power of standard information for weighted approximation[END_REF].

We proceed to analyze the second error

. Since f Λ is supported only on Λ, our reconstruction lattice can exactly compute its coefficients on Λ. Thus for k ∈ Λ we have

Using ( 45) and ( 43) and following the same argument as for the stability analysis, we obtain

with column vector g = [(f Λf )(ϕ(t i ))] i , and we arrive at

We summarize our combined result for function approximation in the following theorem.

Theorem 27. Consider the problem of approximating a function f ∈ F from the Fourier, cosine, or Chebyshev space by f Λ , ∈ {a, b, c}, using a finite index set Λ and an n-point rank-1 lattice under plans A, B, or C as described in this paper. For sufficiently large n we have

with stability constant ρ Λ given in (44) and discrete seminorm • n defined in (46). We have ρ a Λ = 1, and if Λ is downward closed then ρ c Λ ≤ ρ b Λ ≤ min(2 d-1 , #Λ). A loose upper bound is

The requirement on n to achieve (47) is proportional to #(Λ ⊖ Λ) for the Fourier case, while for the cosine/Chebyshev case it is #(M(Λ) ⊕ M(Λ)) with plan A, #(Λ ⊕ M(Λ)) with plan B, and #Λ #M(Λ) with plan C.