J Galkowski
email: j.galkowski@ucl.ac.uk

D Lafontaine
email: david.lafontaine@math.univ-toulouse.fr

E A Spence
email: spence@bath.ac.uk

J Wunsch
email: jwunsch@math.northwestern.edu

The hp-FEM applied to the Helmholtz equation with PML truncation does not suffer from the pollution effect

Keywords: Helmholtz equation, high frequency, perfectly-matched layer, pollution effect, finite element method, error estimate, semiclassical analysis AMS subject classifications: 35J05, 65N12, 65N15, 65N30

.

We show that the hp-FEM applied to this problem does not suffer from the pollution effect, in that there exist C1, C2 > 0 such that if hk/p ≤ C1 and p ≥ C2 log k then the Galerkin solutions are quasioptimal (with constant independent of k), under the following two conditions (i) the solution operator of the original Helmholtz problem is polynomially bounded in k (which occurs for "most" k by [41]), and (ii) either there is no obstacle and the coefficients are smooth or the obstacle is analytic and the coefficients are analytic in a neighbourhood of the obstacle and smooth elsewhere.

. The decomposition is obtained using tools from semiclassical analysis (i.e., the PDE techniques specifically designed for studying Helmholtz problems with large k).

1 Introduction and statement of the main results

Recap of the Helmholtz exterior Dirichlet problem and kdependence of its solution operator

This paper is primarily concerned with computing solutions of the Helmholtz exterior Dirichlet problem when the wavenumber k is large.

R d and k > 0, u ∈ H 1 loc (Ω + ) satisfies the exterior Dirichlet problem if

c 2 scat ∇ • (A scat ∇u) + k 2 u = -g in Ω + , u = 0 on Γ D , (1.1)
and u is outgoing in the sense that ∂u ∂r (x) -iku(x) = o 1 r (d-1)/2

(1.2)

as r := |x| → ∞, uniformly in x := x/r (i.e., u satisfies the Sommerfeld radiation condition).

Although the exterior Dirichlet problem makes sense for non smooth domains and coefficients, our results below require the smoothness in Definition 1.1 (and more), and so we assume this smoothness from the start for simplicity. Let • H 1 k be the standard weighted

H 1 norm w 2 H 1 k := ∇w 2 L 2 + k 2 w 2 L 2 .
(1.3) Definition 1.2 (Polynomial boundedness of the solution operator) Given k 0 > 0, K ⊂ [k 0 , ∞), the solution operator of the Helmholtz exterior Dirichlet problem is polynomially bounded for k ∈ K if there exists M ≥ 0 such that given R > 0 there exists C > 0 such that given g ∈ L 2 (Ω + ) with supp g ⊂ B R , the solution u of the Helmholtz exterior Dirichlet problem satisfies

u H 1 k (B R ∩Ω+) ≤ Ck M g L 2 (B R ∩Ω+) for all k ∈ K.
(

1.4)

There exist C ∞ coefficients A scat and c scat and obstacles Ω -such that the solution operator is not polynomially bounded for all k. E.g., [START_REF] Ralston | Trapped rays in spherically symmetric media and poles of the scattering matrix[END_REF] gives an example of a c scat ∈ C ∞ such that the solution operator with this c scat and A scat ≡ I grows exponentially through a sequence 0 < k 1 < k 2 < . . . with k j → ∞ as j → ∞. Note that this exponential growth is the worst-possible growth of the solution operator by [START_REF] Burq | Décroissance des ondes absence de de l'énergie locale de l'équation pour le problème extérieur et absence de resonance au voisinage du réel[END_REF]Theorem 2]. (i) If Ω -, A scat , and c scat are additionally nontrapping (i.e. all the trajectories of the generalised bicharacteristic flow defined by the semiclassical principal symbol of (1.1) starting in B R leave B R after a uniform time), then given k 0 > 0, (1.4) holds with M = 0 and K = [k 0 , ∞).

(ii) Given k 0 , δ, ε > 0 there exists a set J ⊂ [k 0 , ∞) with |J| ≤ δ such that (1.4) holds with M = 5d/2 + ε and K = [k 0 , ∞) \ J.

References for the proof.

(i) follows from either the results of [START_REF] Melrose | Singularities of boundary value problems[END_REF] combined with either [66, Theorem 3]/ [67, Chapter 10, Theorem 2] or [START_REF] Lax | Scattering Theory[END_REF], or [9, Theorem 1.3 and §3]. (ii) is proved for c = 1 in [41, Theorem 1.1 and Corollary 3.6] and the proof for more-general c follows from combining the results of [START_REF] Lafontaine | For most frequencies, strong trapping has a weak effect in frequency-domain scattering[END_REF] with [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]Lemma 2.3]; we highlight that, under an additional assumption about the location of resonances, a similar result with a larger M can also be extracted from [START_REF] Stefanov | Resonance expansions and Rayleigh waves[END_REF]Proposition 3] by using the Markov inequality.

Truncation of the exterior domain Ω + using the exact Dirichlet-to-Neumann map and solution via the hp-FEM

A popular way of solving boundary value problems involving variable-coefficient PDEs, such as the Helmholtz exterior Dirichlet problem of Definition 1.1, is the finite-element method (FEM).

When the FEM is used with standard piecewise-polynomial subspaces (i.e., piecewise polynomials of degree p on a mesh with meshwidth h), the exterior domain Ω + must be truncated before the FEM can be used. One truncation option is to introduce R > R scat such that supp g ⊂ B R , and then replace Ω + by Ω + ∩ B R , using as a boundary condition on ∂B R the exact Dirichlet-to-Neumann (DtN) map for the Helmholtz equation ∆u + k 2 u = 0 in the exterior of B R with the radiation condition (1.2) (with this map given explicitly, by separation of variables, in terms of Fourier series and Hankel functions). The solution of this truncated problem is then the restriction of the solution of the exterior Dirichlet problem to B R .

For the exterior Dirichlet problem with exact-DtN-map truncation, there has been a relatively large amount of analysis of the associated FEMs since the initial work of [START_REF] Masmoudi | Numerical solution for exterior problems[END_REF][START_REF] Keller | Exact non-reflecting boundary conditions[END_REF]. In particular, for the hp-version of the FEM, where accuracy is increased by both decreasing h and increasing p, the results of [START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF]Theorem 5.8] (when Γ D is analytic, A = I, and c = 1) and [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]Theorem B1] (when Γ D is analytic and A, c are analytic near Γ D -see Assumption 1.11 below) show that if the solution operator is polynomially bounded in k as k → ∞ (in the sense of Definition 1.2) then there exist C 1 , C 2 , and C qo (independent of k, h, and p) such that if hk p ≤ C 1 and p ≥ C 2 log k then the Galerkin solution u N exists, is unique, and satisfies

u -u N H 1 k (B R ∩Ω+) ≤ C qo min v N ∈V N u -v N H 1 k (B R ∩Ω+) ,
where V N is the hp approximation space.

Since the total number of degrees of freedom of the approximation space is proportional to (p/h) d , these results show there is a choice of h and p such that the Galerkin solution is quasioptimal, with quasioptimality constant (i.e. C qo ) independent of k, and with the total number of degrees of freedom proportional to k d . The significance of this result is that it is well-known that the h-FEM (where accuracy is increased by decreasing h with p fixed) is not quasioptimal with C qo independent of k when the total number of degrees of freedom ∼ k d (i.e., when h ∼ k -1 ); see [START_REF] Babuška | Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?[END_REF]. This feature is known as "the pollution effect" (with the term coined in [START_REF] Ihlenburg | Finite element solution of the Helmholtz equation with high wave number Part I: The h-version of the FEM[END_REF]), and the results of [START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] quoted above therefore show that the hp-FEM applied to the exterior Dirichlet problem with exact-DtN-map truncation does not suffer from it.

Truncation of Ω + using a PML

Although the solution of the problem truncated with the exact DtN map is the restriction of the solution of the true problem to Ω + ∩ B R , the exact DtN map is a non-local operator, and hence expensive to compute.

A popular way of truncating in a less-computationally-expensive way is to use a perfectlymatched layer (PML), introduced by [START_REF] Berenger | A perfectly matched layer for the absorption of electromagnetic waves[END_REF] (in cartesian coordinates) and [START_REF] Collino | The perfectly matched layer in curvilinear coordinates[END_REF] (in spherical coordinates). In this paper we consider the following radial PMLs.

Radial PML definition. Let R tr > R 1 > R scat and let Ω tr ⊂ R d be a bounded Lipschitz open set with B Rtr ⊂ Ω tr . Let Ω := Ω tr ∩ Ω + , Γ tr := ∂Ω tr , and 0 ≤ θ < π/2. Let

P := -c 2 scat ∇ • (A scat ∇).
so that the Helmholtz equation in (1.1) is (P -k 2 )u = g. The PML method replaces (1.1)-(1.2) by

(P θ -k 2 )v = g in Ω, v = 0 on Γ D , and v = 0 on Γ tr , (1.5)
where

P θ := P, r ≤ R 1 , -∆ θ , r > R 1 , (1.6)
where -∆ θ is a second order differential operator that is given in spherical coordinates (r, ω) ∈ [0, ∞) × S d-1 by

∆ θ = 1 1 + if θ (r) ∂ ∂r 2 + d -1 (r + if θ (r))(1 + if θ (r)) ∂ ∂r + 1 (r + if θ (r)) 2 ∆ ω , (1.7)
= 1 (1 + if θ (r))(r + if θ (r)) d-1 ∂ ∂r (r + if θ (r)) d-1 1 + if θ (r) ∂ ∂r + 1 (r + if θ (r)) 2 ∆ ω ,
with ∆ ω the surface Laplacian on S d-1 and f θ (r) ∈ C ∞ ([0, ∞); R) given by f θ (r) := f (r) tan θ for some f satisfying {f (r) = 0} = {f (r) = 0} = {r ≤ R 1 }, f (r) ≥ 0, f (r) ≡ r on r ≥ R 2 ;

(1.8)

i.e., the scaling "turns on" at r = R 1 , and is linear when r ≥ R 2 . We emphasize that R tr can be < R 2 , i.e., we allow truncation before linear scaling is reached. Indeed, R 2 > R 1 can be arbitrarily large and therefore, given any bounded interval [0, R] and any function f ) the PML problem is written using notation from the method of complex scaling (see, e.g., [21, §4.5]). In the numerical-analysis literature on PML, the scaled variable is often written as r(1 + i σ(r)) with σ(r) = σ 0 for r sufficiently large, see, e.g., [36, §4], [7, §2]. To convert from our notation, set σ(r) = f θ (r)/r and σ 0 = tan θ.

∈ C ∞ ([0, R]) satisfying { f (r) = 0} = { f (r) = 0} = {r ≤ R 1 }, f (
Remark 1.5 (Smoothness of the PML scaling function f θ ) We assume that f θ ∈ C ∞ because we need the differential operator -∆ θ to be a semiclassical pseudodifferential operator (with the definition of these recapped in §A). More precisely, we need the operator Q ,θ , defined by (3.10) in terms of -∆ θ , to be a semiclassical pseudodifferential operator. While we could work with pseudodifferential operators with non-smooth symbols, and thus cover f θ with lower regularity, this would be more technical.

Accuracy of PML truncation. It is well-known that, for fixed k, the error

u -v H 1 k (B R 1 \Ω)
decays exponentially in R tr -R 1 and tan θ -see [START_REF] Lassas | On the existence and convergence of the solution of PML equations[END_REF]Theorem 2.1], [45, Theorem A], [START_REF] Hohage | Solving time-harmonic scattering problems based on the pole condition II: convergence of the PML method[END_REF]Theorem 5.8] (with analogous results for cartesian PMLs in [START_REF] Bramble | Analysis of a finite PML approximation for the three dimensional time-harmonic Maxwell and acoustic scattering problems[END_REF]Theorem 3.4]).

It was recently proved in [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF] that the error u -v H 1 k (B R 1 \Ω) also decreases exponentially in k; indeed, the following theorem is a simplified version of [28, Theorems 1.2 and 1.5].

Theorem 1.6 (Radial PMLs are exponentially accurate for k large) Suppose that f θ ∈ C 3 (0, ∞) and the solution operator of exterior Dirichlet problem is polynomially bounded in k (in the sense of Definition 1.2). Given > 0, there exist C 1 , C 2 , k 0 > 0 such that for all θ ≥ , R tr ≥ R 1 (1 + ), and k ≥ k 0 the following is true.

Given g ∈ L 2 (Ω + ) with supp g ⊂ B R1 , the solution v to (1.5) exists, is unique, and satisfies

u -v H 1 k (B R 1 \Ω-) ≤ C 1 exp -C 2 k R tr -R 1 (1 + ) tan θ g L 2 (Ω+) , (1.9)
where u is the solution to the exterior Dirichlet problem of Definition 1.1.

We make three remarks regarding Theorem 1.6.

• The order of the quantifiers in Theorem 1.6 (and also later results in the paper) dictates what the constants depend on; e.g., in Theorem 1.6, C 1 , C 2 , and k 0 depend on , but are independent of R tr , R 1 , and θ.

• A similar bound on the error holds even when the solution operator is not polynomially bounded and grows exponentially in k; see [28, Theorems 1.2 and 1.5].

• Results showing exponential decay in k (similar to in (1.9)) for the model problem of A scat ≡ I, c scat ≡ 1, and Ω -= ∅ (i.e., no scatterer) were given in [START_REF] Chen | A source transfer domain decomposition method for Helmholtz equations in unbounded domain[END_REF]Lemma 3.4] for d = 2 and [47, Theorem 3.7] for d = 2, 3, using the fact that the solution of this problem can be written explicitly via the fundamental solution or separation of variables.

• The exponential decay of the error (1.9) in k is in contrast to truncation with local absorbing boundary conditions (introduced in [START_REF] Lindman | Free-space" boundary conditions for the time dependent wave equation[END_REF][START_REF] Engquist | Absorbing boundary conditions for numerical simulation of waves[END_REF][START_REF] Engquist | Absorbing boundary conditions for the numerical simulation of waves[END_REF][START_REF] Engquist | Radiation boundary conditions for acoustic and elastic wave calculations[END_REF][START_REF] Bayliss | Radiation boundary conditions for wave-like equations[END_REF][START_REF] Bayliss | Boundary conditions for the numerical solution of elliptic equations in exterior regions[END_REF]) which give O(1) relative errors as k → ∞ when approximating the solutions of scattering problems; see [START_REF] Galkowski | Local absorbing boundary conditions on fixed domains give order-one errors for high-frequency waves[END_REF].

The variational formulation of the PML problem. Given f θ (r), let α(r) := 1 + if θ (r) and β(r

) := 1 + if θ (r)/r. (1.10) Let A := A scat for r < R 1 HDH T for r ≥ R 1 , and 1 c 2 := c -2 scat for r < R 1 α(r)β(r) d-1 for r ≥ R 1 , (1.11)
where, in polar coordinates,

D = β(r)α(r) -1 0 0 α(r)β(r) -1 and H = cos θ -sin θ sin θ cos θ for d = 2,
and

D =   β(r) 2 α(r) -1 0 0 0 α(r) 0 0 0 α(r)   and H =   sin θ cos φ cos θ cos φ -sin φ sin θ sin φ cos θ sin φ cos φ cos θ -sin θ 0   for d = 3.
(observe that then A = I and c -2 = 1 when r = R 1 and thus A and c -2 are continuous at r = R 1 ).

Lemma 1.7 (Variational formulation of the PML problem (1.5)) Given g ∈ L 2 (Ω + ) with supp g ⊂ B R1 , the variational formulation of the PML problem (1.5) is find v ∈ H 1 0 (Ω) such that a(v, w) = G(w) for all w ∈ H 1 0 (Ω), (1.12)
where

a(v, w) := Ω A∇v • ∇w - k 2 c 2 vw and G(w) := B R 1 g c 2 w.
Proof. With α and β defined by (1.10) (with this notation used by [START_REF] Lassas | On the existence and convergence of the solution of PML equations[END_REF][START_REF] Li | FEM and CIP-FEM for Helmholtz Equation with High Wave Number and Perfectly Matched Layer Truncation[END_REF]), ∆ θ defined by (1.7) becomes

∆ θ = 1 α(rβ) d-1 ∂ ∂r (βr) d-1 α ∂ ∂r + 1 (rβ) 2 ∆ ω .
Multiplying the PDE in (1.5) by c -2 scat αβ d-1 , using that c scat ≡ 1 for r ≥ R 1 , α ≡ β ≡ 1 for r ≤ R 1 , and supp g ⊂ B R1 , and then changing variables to cartesian coordinates, we find that

∇ • (A∇u) + k 2 c 2 u = - g c 2 ;
the variational formulation (1.12) follows.

Remark 1.8 (Plane-wave scattering) The exterior Dirichlet problem of Definition 1.1 considers the Helmholtz equation with right-hand side g. Another important Helmholtz problem is that of plane-wave scattering; that is, with Ω -, A scat , and c scat as above, given

a ∈ R d with |a| = 1, let u I (x) := exp(ikx • a) and find u ∈ H 1 loc (Ω + ) such that c 2 scat ∇ • (A scat ∇u) + k 2 u = 0 in Ω + , u = 0 on Γ D ,
and u S := u-u I is outgoing (i.e., satisfies (1.2)). Since u itself is not outgoing, it cannot be directly approximated by the solution of a problem with PML truncation. However, let χ ∈ C ∞ comp (R d ; [0, 1]) be such that χ ≡ 1 for r ≤ R scat and χ ≡ 0 for r ≥ R 1 , and let

u := χu I + u S = u -(1 -χ)u I .
Observe that u satisfies the PDE in (1.1) with

g := 2∇χ • ∇u I + u I ∆χ, which is supported in R scat ≤ r ≤ R 1 .
Therefore PML truncation can be used to approximate u. Observe further that u ≡ u for r ≤ R scat , with this usually the region where one is interested in finding the solution u. Assumption 1.9 When d = 3, f θ (r)/r is nondecreasing. Assumption 1.9 is standard in the literature (in the notation described in Remark 1.4 it is that σ is non-decreasing; see, e.g., [7, §2]) and ensures that the matrix A (1.11) satisfies A > 0 (in the sense of quadratic forms) for all θ; see Lemma 2.3 and Remark 2.5 below.

The main result: accuracy of the hp-FEM applied to the Helmholtz exterior Dirichlet problem with PML truncation

Existing results on the accuracy of the FEM applied to Helmholtz problems with PML truncation. Although the FEM with PML truncation is widely used to compute solutions of the Helmholtz exterior Dirichlet problem (and other boundary value problems involving the Helmholtz or Maxwell equations), until now there have been no rigorous k-explicit results guaranteeing the accuracy of the computed solutions of the Helmholtz exterior Dirichlet problem with PML truncation as described in §1.3. Indeed, the only existing k-explicit results on the accuracy of the FEM applied to Helmholtz problems with PML truncation are the following.

• The result [START_REF] Li | FEM and CIP-FEM for Helmholtz Equation with High Wave Number and Perfectly Matched Layer Truncation[END_REF]Theorem 4.4] concerns the model problem of A scat ≡ I, c scat ≡ 1, and Ω -= ∅ (i.e., no scatterer), and shows that v -v N H 1 k (Ω) is bounded (independently of k) in terms of the data if hk 3/2 is sufficiently small; this threshold is observed empirically to be sharp and is the same threshold that appears for the problem with DtN truncation [START_REF] Lafontaine | A sharp relative-error bound for the Helmholtz h-FEM at high frequency[END_REF] or a first-order absorbing boundary condition [START_REF] Wu | Pre-asymptotic error analysis of CIP-FEM and FEM for the Helmholtz equation with high wave number. Part I: linear version[END_REF].

• The result [START_REF] Chaumont-Frelet | Wavenumber explicit convergence analysis for finite element discretizations of time-harmonic wave propagation problems with perfectly matched layers[END_REF] considers Ω -starshaped, A scat ≡ I, and c scat ≡ 1, and obtains the same thresholds for quasioptimality as for both the problem with DtN truncation or a first-order absorbing boundary condition [START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF]. However, [START_REF] Chaumont-Frelet | Wavenumber explicit convergence analysis for finite element discretizations of time-harmonic wave propagation problems with perfectly matched layers[END_REF] considers scaling functions of the form f θ (r) = r σ/k (with σ independent of k), and with such scaling the PML error is not exponentially small in k.

• The result [6, Theorem 6.6.7] in principle covers the exterior Dirichlet problem, but makes an assumption established by [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF]Theorem 1.6] (quoted as Theorem 5.3 below); we discuss the results of [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF] further in §1.8 below.

Statement of the main result. We consider the exterior Dirichlet problem with domain and coefficients satisfying one of the following two assumptions. (ii) Ω -is analytic, and both A scat and c scat are analytic in B R * for some

R 0 < R * < R 1 . (iii) Either Γ tr is C 1,1 or Ω tr is convex.
The reasons we consider these classes of domain and coefficients is explained in §1.8/ §4.2 below. We note here that the assumptions on Ω tr imply that the PML solution is in H 2 (Ω tr ).

Theorem 1.12 (Quasioptimality of hp-FEM for the exterior Dirichlet problem with PML truncation) Suppose that Ω -, A scat , c scat , and Ω tr satisfy either Assumption 1.10 or Assumption 1.11. Suppose further that Ω -, A scat , c scat , and K ⊂ [k 0 , ∞) are such that the solution operator of the exterior Dirichlet problem is polynomially bounded (in the sense of Definition 1.2). Suppose that the PML scaling function f θ ∈ C ∞ and satisfies Assumption 1.9. Let (V N ) ∞ N =0 be the piecewise-polynomial approximation spaces described in [53, §5], [54, §5.1.1] (where, in particular, the triangulations are quasi-uniform and allow curved elements).

Given > 0, there exist

k 1 , C 1 , C 2 , C qo > 0 such that the following is true. Given G ∈ (H 1 k (Ω)) * , for all k ∈ K ∩ [k 1 , ∞), ≤ θ ≤ π/2 -, and R tr ≥ R 1 (1 +
), the solution v to the PML problem (1.5)/ (1.12) exists and is unique. Furthermore, if

hk p ≤ C 1 and p ≥ C 2 log k, (1.13)
then the Galerkin solution v N of the PML problem (1.12), satisfying

a(v N , w N ) = G(w N ) for all w N ∈ V N , (1.14)
exists, is unique, and satisfies the quasioptimal error bound

v -v N H 1 k (Ω) ≤ C qo min w N ∈V N v -w N H 1 k (Ω) .
(1.15)

The error on B R ∩ Ω + between the true solution u and the Galerkin approximation to the PML solution v N is then controlled by combining (1.15) with (1.9). Remark 1.13 (Non-conforming error) Theorem 1.12 assumes that the domain Ω is triangulated exactly. In practical applications, however, exact triangulations are seldom used, and some analysis of the geometric error is therefore necessary. We ignore this issue here (just as in the previous work on the hp-FEM in [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF][START_REF] Melenk | General DG-methods for highly indefinite Helmholtz problems[END_REF][START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF][START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]), but note that, at least for the h-FEM, the analysis in [13] shows that the geometric error caused by using simplicial elements can be controlled when hk is sufficiently small (with [13] also containing results for isoparametric elements).

1.5 The idea behind the hp-FEM result of Theorem 1.12: decompositions of high-frequency Helmholtz solutions

Decomposition of constant-coefficient Helmholtz solutions in [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF]. The celebrated papers [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF][START_REF] Melenk | General DG-methods for highly indefinite Helmholtz problems[END_REF] established a k-explicit convergence theory for the hp-FEM applied to the constant-coefficient Helmholtz equation

∆u + k 2 u = -f. (1.16)
This theory is based on decomposing solutions of (1.16) as

u = u A + u H 2 , (1.17)
where (i) u A is analytic, and satisfies bounds with the same k-dependence as those satisfied by the full Helmholtz solution, but with explicit k-dependence built into the Cauchy estimates, and

(ii) u H 2 has finite regularity (normally H 2 ), and satisfies bounds with improved k-dependence compared to those satisfied by the full Helmholtz solution.

The papers [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF] obtained such a decomposition for a variety of constant-coefficient Helmholtz problems, with the idea of the decomposition that u A corresponds to the low-frequency components of the solution u (i.e., components with frequencies k) u H 2 corresponds to the high-frequency components of solution (i.e., components with frequencies k) -we discuss this "decomposingvia-frequencies" idea further in §1.8.

How the decomposition shows that the hp-FEM does not suffer from the pollution effect under the conditions (1.13). The classic duality argument (originating from ideas introduced in [START_REF] Schatz | An observation concerning Ritz-Galerkin methods with indefinite bilinear forms[END_REF] and then refined by [START_REF] Sauter | A refined finite element convergence theory for highly indefinite Helmholtz problems[END_REF]) gives a condition for the Galerkin solutions to be quasioptimal in terms of how well solutions of the adjoint problem are approximated by the finite-element space (see §2.1 below and the discussion/references therein). Note that solutions of the adjoint problem for the Helmholtz equation are just complex-conjugates of Helmholtz solutions (see Lemma 2.7 below), so in this argument one only needs to consider approximation of Helmholtz solutions.

When applying the classic duality argument to the Helmholtz equation, approximating the Helmholtz solution directly (without any decomposing) and using the sharp bound (in terms of kdependence) on its H 2 norm results in the condition "hk 2 /p sufficiently small" for quasioptimality; this is the sharp condition when p = 1 -see, e.g., [START_REF] Ihlenburg | Finite element solution of the Helmholtz equation with high wave number Part I: The h-version of the FEM[END_REF]Figure 8].

The fact that u H 2 satisfies a bound one power of k better than that satisfied by u means that the analogue of the condition "hk 2 /p sufficiently small" with u replaced by u H 2 is the improved "hk/p sufficiently small"; i.e., the first condition in (1.13). Provided that the solution operator is polynomially bounded, the analogue of the condition "hk 2 /p sufficiently small" with u replaced by u A (and using the first p + 1 derivatives of u A ) is essentially

k 1+M hk σp p (1.18)
sufficiently small (with σ constant); see (2.6) below. With hk/p sufficiently small, (1.18) can be made arbitrarily small if p/ log k is sufficiently large, leading to the second condition in (1.13); note that the analyticity of u A is crucial here, since it allows us to take p arbitrarily large.

The recent paper [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]: analogous decompositions for very general Helmholtz scattering problems. The recent paper [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] (following [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF]) showed that similar decompositions can be obtained for very general Helmholtz scattering problems, namely, those fitting into the so-called "black-box" framework of Sjöstrand-Zworski [START_REF] Sjöstrand | Complex scaling and the distribution of scattering poles[END_REF], with this framework including problems where the scattering is caused by variable coefficients, penetrable obstacles, or impenetrable obstacles. For these general Helmholtz solutions, u A is not necessarily analytic, but the regularity is determined by properties of the scatterer. The paper [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] then showed that, if the domain and coefficients satisfy either Assumptions 1.10 or 1.11, then u A is analytic (possibly modulo a remainder that is super-algebraically small in k), and then the arguments of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF] can be used to show that the hp-FEM applied to these Helmholtz problems does not suffer from the pollution effect.

The main contribution of the present paper. The main contribution of the present paper is showing that the decompositions of outgoing Helmholtz solutions obtained in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] also hold for the corresponding Helmholtz solutions with PML truncation. Indeed, our main decomposition result for PML solutions, stated informally in the next subsection as Theorem 1.15, and then rigorously in Theorem 4.1, is the exact analogue of the corresponding decomposition result in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] for Helmholtz solutions satisfying the Sommerfeld radiation condition (1.2). The results in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] that show that u A is analytic if the domain and coefficients satisfy either Assumption 1.10 or 1.11, then show the corresponding result for the low-frequency components of the PML solution. Thus, exactly as in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF], the arguments of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF] can be used to show that the hp-FEM applied to these PML problems does not suffer from the pollution effect, i.e., Theorem 1.12.

Recap of k-explicit analyticity. Before stating informally the main decomposition result for PML solutions (Theorem 1.15), we record the following lemma about how the bound an analytic function depending on k satisfies dictates the k-dependence of the region of analyticity; we use this lemma below to understand the properties of the v A s in Theorems 1.15, 1.16, and 1.17. (i) If there exist C, C u > 0 such that, for all multiindices α,

∂ α u L 2 (D) ≤ C u (Ck) |α| .
then u is real analytic in D with infinite radius of convergence, i.e., u is entire.

(ii) If there exist C, C u > 0 such that, for all multiindices α,

∂ α u L 2 (D) ≤ C u (Ck) |α| |α|!,
then u is real analytic in D with radius of convergence proportional to (Ck) -1 . (iii) If there exist C, C u > 0 such that, for all multiindices α,

∂ α u L 2 (D) ≤ C u C |α| max |α|, k |α| ,
then u is real analytic in D with radius of convergence independent of k.

Proof. In each case, we use the Sobolev embedding theorem to obtain a bound on ∂ α u L ∞ (D) , and then sum the remainder in the truncated Taylor series. For this procedure carried out in Case (iii), see, e.g., [53, Proof of Lemma C.2]; the proofs for the other cases are similar.

Informal statement of the main decomposition result for Helmholtz problems with PML truncation

Theorem 1.15 (Informal statement of the main decomposition result) Let P be a formally self-adjoint operator with P = -∆ outside a sufficiently-large ball ("the black-box"). Suppose that P -k 2 is well defined and that (H1) the solution operator associated with P -k 2 is polynomially bounded: there exists M ≥ 0 so that for any χ ∈ C ∞ comp and any compactly-supported g ∈ L 2 , the outgoing solution of

(P -k 2 )u = g satisfies χu L 2 k M g L 2 ,
(H2) one has an estimate quantifying the regularity of P inside the black-box.

Let P θ be defined by (1.6), and let Ω tr and Ω be as in §1.1. Then any solution of

(P θ -k 2 )v = g in Ω can be written as v = v H 2 + v A + v residual
where (i) v H 2 satisfies the same boundary conditions as v and the bound

v H 2 L 2 (Ω) + k -2 P θ v H 2 L 2 (Ω) g L 2 (Ω) ,
(ii) v A is regular, with an estimate depending on both the regularity of the underlying problem (as measured by (H2)) and M . In addition, the part of v A away from the black-box is entire (in the sense of Lemma 1.14(i)).

(iii) v residual is negligible, in the sense that all of its norms are smaller than any algebraic power of k.

Finally, given > 0, the constants in the bounds on v H 2 , v A , and v residual are uniform in θ for ≤ θ ≤ π/2 -.

We make the following immediate remarks:

• The assumptions in Theorem 1.15 (involving the unscaled operator P ) are exactly the same as in the analogue of Theorem • The paper [START_REF] Lafontaine | For most frequencies, strong trapping has a weak effect in frequency-domain scattering[END_REF] shows that the assumption (H1) holds in the black-box framework for "most" frequencies (see Part (i) of Theorem 1.3 for a more precise statement of this). Therefore, to apply this result to specific situations, the key point is to check that an estimate of the type (H2) holds; we discuss this further in §4.2.

Transferring the results in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] for particular Helmholtz solutions to the corresponding Helmholtz solutions with PML truncation. Since (i) the assumptions of Theorem 1.15 (and its precise version Theorem 4.1) are exactly the same (by design) as the assumptions of [29, Theorem A /Theorem A], and (ii) these assumptions are checked in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] for the particular Helmholtz problems we are interested in here, analogous decompositions to those in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] for outgoing Helmholtz solutions then immediately hold for the analogous PML problems. Indeed, [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] proves the decomposition u = u A + u H 2 (1.17) with u A analytic under Assumptions 1.10 and 1.11, with (H2) corresponding to, respectively, an explicit estimate on the eigenfunctions of the Laplace operator on the torus and an analytic estimate for solutions of the heat equation. The PML analogues of these results then follow immediately and are stated in Theorems 1.16 and 1.17 in the next section. We highlight that [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] also decomposes the solution of the Helmholtz transmission problem, and thus an analogous result holds for the corresponding PML problem. This result shows only finiteregularity of v A (as opposed to analyticity), and so gives a (sharp) result about quasioptimality of the h-FEM, but not the hp-FEM. Since we focus on the hp-FEM in the present paper, we do not state this decomposition for the transmission problem with PML truncation (but highlight here that it exists).

The main decomposition result applied to the Helmholtz exterior

Dirichlet problem with PML truncation under Assumptions 1.10 or 1.11

Theorem 1.16 (Decomposition of the PML solution under Assumption 1.10) Suppose that Ω -, A scat , c scat , and Ω tr satisfy Assumption 1.10. Suppose further that A scat , c scat , and K ⊂ [k 0 , ∞) are such that the solution operator is polynomially bounded (in the sense of Definition 1.2). Given > 0, there exist C j , j = 1, 2, 3, and k 1 > 0 such that the following is true. For all

R tr > R 1 + , B Rtr ⊂ Ω tr R d with Lipschitz boundary, < θ < π/2 -, given g ∈ L 2 (Ω)
, the solution v of the PML problem (1.5) exists, is unique, and is such that

v = v H 2 + v A + v residual , where v A , v H 2 , and v residual satisfy the following. v H 2 ∈ H 2 (Ω) ∩ H 1 0 (Ω) with ∂ α v H 2 L 2 (Ω) ≤ C 1 k |α|-2 g L 2 (Ω) for all k ∈ K ∩ [k 1 , ∞) and for all |α| ≤ 2. (1.19) v A satisfies ∂ α v A L 2 (Ω) ≤ C 2 (C 3 ) |α| k |α|-1+M g L 2 (Ω) for all k ∈ K ∩ [k 1 , ∞) and for all α (1.20)
and is negligible in the scaling region in the sense that for any N, m > 0 there exists C N,m > 0

(independent of θ) such v A H m ((B R 1 (1+ ) ) c ) ≤ C N,m N g H(Ωtr) for all k ∈ K ∩ [k 1 , ∞).
Finally v residual is negligible in the sense that for any N, m > 0 there exists

C N,m > 0 (independent of θ) so that v residual H m (Ω) ≤ C N,m k -N g L 2 (Ω) for all k ∈ K ∩ [k 1 , ∞). (1.21)
By Part (i) of Lemma 1.14, v A in Theorem 1.16 is entire.

Theorem 1.17 (Decomposition of the PML solution under Assumption 1.11) Suppose that Ω -, A scat , c scat , and Ω tr satisfy Assumption 1.11. Suppose further that Ω -, A scat , c scat , and K ⊂ [k 0 , ∞) are such that the solution operator is polynomially bounded (in the sense of Definition 1.2). Given > 0, there exist C j > 0, j = 1, . . . , 5, and

R 0 < R I < R II < R III < R IV < R 1 such that the following is true. For all R tr > R 1 + , B Rtr ⊂ Ω tr R d with Lipschitz boundary, < θ < π/2 -, given g ∈ L 2 (Ω), the solution v of the PML problem (1.5) exists, is unique, and is such that v = v H 2 + v A + v residual where v A , v H 2 , and v residual satisfy the following. v H 2 ∈ H 2 (Ω) ∩ H 1 0 (Ω) with ∂ α u H 2 L 2 (Ω) ≤ C 1 k |α|-2 g L 2 (Ω) for all k ∈ K ∩ [k 1 , ∞) and for all |α| ≤ 2. (1.22) R 0 R I R II R III R IV R v A,near analytic v A,near = O(k -∞ ) v A,far = O(k -∞ ) v A,far entire Figure 1.1:
The regions where v A,near and v A,far appearing in Theorem 1.17 are analytic, entire, or O(k -∞ ).

v A = v A,near + v A,
k ∈ K ∩ [k 1 , ∞) and all α, ∂ α v A,near L 2 (B R IV ∩Ω) ≤ C 2 (C 3 ) |α| max |α| |α| , k |α| k -1+M g L 2 (Ω) , (1.23)
∂ α v A,far L 2 ((B R I ) c ∩Ω) ≤ C 4 (C 5 ) |α| k |α|-1+M g L 2 (Ω) ,
and, for any N, m > 0 there exists C N,m > 0 (independent of θ) so that

v A,far H m (B R II ∩Ω) + v A,near H m ((B R III ) c ∩Ω) ≤ C N,m k -N g L 2 (Ω) for all k ∈ K ∩ [k 1 , ∞).
Finally v residual is negligible in the sense that for any N, m > 0 there exists C N,m > 0 (independent of θ) so that (1.21) holds.

By Parts (iv) and (i) of Lemma 1.14, v A,near is analytic in B R IV with k-independent radius of convergence, and v A,far is entire in (B R I ) c ; see Figure 1.1.

1.8

The ideas behind the decomposition result of Theorems 1.15, 1.16, and 1.17 and previous decomposition results for Helmholtz problems Table 1.1 summarises the problems considered and approaches to the decompositions in the papers [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF][START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF][START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF], and the present paper. We now discuss the six main ideas/ingredients used in the proof of Theorem 1.15 (and its precise statement in Theorem 4.1).

Ingredient 1: semiclassical ellipticity of the Helmholtz operator on high frequencies.

The reason the high-frequency component v H 2 satisfies a bound with better k-dependence than the solution v is because the Helmholtz operator is semiclassically elliptic on frequencies with modulus > k. While this feature was observed in [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF] in the variable-coefficient setting, its essence is most easily illustrated in the constant-coefficient setting. With the Fourier transform defined by

F k φ(ξ) := R d exp -ikx • ξ φ(x) dx (1.24)
(i.e., the standard Fourier transform with the Fourier variable scaled by k), the constant-coefficient Helmholtz operator is Fourier multiplier with Fourier symbol |ξ| 2 -1; i.e., [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF][START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF][START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] and the present paper. "SRC" stands for "Sommerfeld radiation condition", "EDP" stands for "exterior Dirichlet problem", "IIP" stands for "interior impedance problem", "HF" stands for "high-frequency", and "LF" stands for "low-frequency". To keep the notation concise, we abbreviate A scat and c scat by A and c, respectively.

(-k -2 ∆ -1)v (x) = F -1 k (|ξ| 2 -1)F k v(ξ) (x). (1.25) If λ > 1 then there exists C > 0 such that |ξ| 2 -1 ≥ C ξ
i.e., the Fourier symbol of the constant-coefficient Helmholtz operator is elliptic on |ξ| > 1, with this range of ξ corresponding to the standard Fourier variable (i.e., with no scaling by k in (1.24)) having modulus > k. The "high-frequency" components of the solution are then defined as those with frequency > k, and the "low-frequency" ones defined as those with frequencies k.

Ingredient 2: semiclassical pseudodifferential operators. The variable-coefficient Helmholtz operator ∇ • (A scat ∇) + k 2 c scat is no longer a Fourier multiplier (i.e., it cannot be written in the form (1.25)). It is, however, a pseudodifferential operator; indeed, recall that part of the motivation for the development of pseudodifferential operators was to extend Fourier analysis to study variable-coefficient (as opposed to constant-coefficient) PDEs. Semiclassical pseudodifferential operators are those defined with Fourier transform defined by (1.24), i.e., with the large parameter k (or small parameter k -1 ) built in; thus semiclassical pseudodifferential operators are precisely the pseudodifferential operators tailor-made to study problems with a large/small parameter.

The paper [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF] uses the "nice" behaviour of elliptic semiclassical pseudodifferential operators (namely, they are invertible up to a small error) to prove the required bound on the high-frequency components of the decomposition for the (non-truncated) Helmholtz equation in R d (i.e., Ω -= ∅) with smooth A scat and c scat . Note that (i) the polynomial boundedness condition of Definition 1.2 is needed to show that the O(k -∞ ) error terms in the pseudodifferential calculus acting on the solution are indeed small (which is not guaranteed if the solution operator grows exponentially in k), and (ii) the theory of pseudodifferential operators is the least technical when the symbols are smooth, thus [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF] used smooth frequency cut-offs (as opposed to those defined by an indicator function in [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF]). 1 Ingredient 3: frequency cut-offs defined as functions of the operator (i.e., eigenfunction expansion). For problems posed in domains other than R d , it is difficult to use the Fourier transform to define frequency cut-offs. The papers [START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF] tackle this issue by using the composition of the frequency cut-offs on R d and a suitable extension operator from the domain to R d . Here, following [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF], we instead define frequency cut-offs using the eigenfunctions of the Helmholtz operator considered on a large torus including Ω tr (and the black-box inside it); this approach has the advantage that the frequency cut-offs then commute with the Helmholtz operator used to define them.

More precisely, recall that the functional calculus defines functions of a self-adjoint elliptic operator in terms of eigenfunction expansions. Here we choose the operator to be the socalled reference operator in the framework of black-box scattering; this is just the operator P := -k -2 c 2 scat ∇ • (A scat ∇) considered on the torus T d R with R sufficiently large so that the torus contains Ω tr (see §3.1 below). Then, with λ j and φ j the eigenvalues and eigenfunctions of P and f a real-valued Borel function,

f (P )v = j a j f (λ j )φ j for v = j a j φ j (see §3.4 below). Given ψ ∈ C ∞ comp (R; [0, 1]) with supp ψ ⊂ [-2, 2] and ψ ≡ 1 on [-1, 1],
we define ψ µ := ψ(•/µ) and let Π Low := ψ µ (P ) and Π High := (1 -ψ µ )(P ) = I -Π Low ; see (5.7) and (5.8) below. As mentioned above, a crucial fact about these frequency cut-offs is that they commute with P .

Ingredient 4: introduce a spatial cut-off and use ellipticity of the PML operator in the scaling region. We choose ϕ tr ∈ C ∞ comp (R d ; [0, 1]) such that ϕ tr ≡ 1 on B R1(1+δ) and supp ϕ tr ⊂ B R1(1+2δ) for a suitably chosen δ > 0. We then decompose v as v = Π High (ϕ tr v)

=:v High + Π Low (ϕ tr v) =:vLow + (1 -ϕ tr )v =:vPML .
We then use results from the recent paper [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF] to bound v PML in terms of the data with one power better k-dependence than the bound on the solution v; thus v PML can be included in the component v H 2 (note that the conditions on Γ tr in Assumptions 1.10 and 1.11 ensure that the PML solution is H 2 up to the boundary Γ tr ).

The ingredients used to bound v PML are (i) the fact that, at highest order, the imaginary part of -k -2 ∆ θ -1 has a sign in the scaling region (see, e.g., [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF]Equation 4.22], with this behind Lemma 5.4 below) and (ii) a Carleman estimate describing how v propagates in the scaling region (see Lemma 5.5 below).

In bounding v PML , it is crucial that (1 -ϕ tr ) (and hence also (1 -ϕ tr )v) is supported only in the PML scaling region (B R1 ) c . However, the fact that supp ϕ tr enters the scaling region causes the following issue. When bounding v High , we consider

(P -I)Π High (ϕ tr v) = Π High (P -I)(ϕ tr v) = Π High [P , ϕ tr ]v + ϕ tr (P -I)v .
(1.26)

We would now like to say that (P -I)v equals the data (P ,θ -I)v, but this is not the case since P = P ,θ on supp ϕ tr (which enters the scaling region).

The solution is twofold: we first split

v High = Π High (ϕ 0 v)+Π High (1-ϕ 0 )ϕ tr v (see (5.29) below), where ϕ 0 ∈ C ∞ comp (R d ; [0, 1]
) such that ϕ 0 ≡ 1 on B R0 and supp ϕ 0 ⊂ B R1 , and thus P = P ,θ on supp ϕ 0 . We argue as above for Π High (ϕ 0 v) and then deal with the component Π High (1 -ϕ 0 )ϕ tr v, as well as the commutator term in (1.26), using the next ingredient.

Ingredient 5: away from the black box, functions of P are semiclassical pseudodifferential operators. When bounding v High and v Low , we use repeatedly the result that, when f is sufficiently well-behaved and χ ∈ C ∞ (R d ; [0, 1]) is zero in a neighbourhood of the black box, χf (P )χ is a pseudodifferential operator (up to a negligible error term); see Lemma 3.6 below. In particular, this result allows us to treat Π High and Π Low as pseudodifferential operators away from the black box.

The context of this result, due to Sjöstrand [START_REF] Sjöstrand | A trace formula and review of some estimates for resonances[END_REF], is the following: in the setting of the homogeneous pseudodifferential calculus, Strichartz [START_REF] Strichartz | A functional calculus for elliptic pseudo-differential operators[END_REF] proved that a well-behaved function of a selfadjoint elliptic differential operator is a pseudodifferential operator. Helffer-Robert [START_REF] Helffer | Calcul fonctionnel par la transformation de Mellin et opérateurs admissibles[END_REF] proved the corresponding result in the semiclassical setting (see, e.g., the account [18, Chapter 8]), with this result using the Helffer-Sjöstrand approach to the functional calculus [START_REF] Helffer | Équation de Schrödinger avec champ magnétique et équation de Harper[END_REF]. In the setting of black-box scattering, we cannot expect such a result to hold everywhere, because we don't know what's inside the black box. However, thanks to Sjöstrand [START_REF] Sjöstrand | A trace formula and review of some estimates for resonances[END_REF] this pseudodifferential property holds when localised away from the black box.

Ingredient 6: regularity estimates inside the black box. While the analysis of v High is insensitive to the contents of the black-box (see Ingredient 3) understanding the properties of the low-frequency piece v Low necessarily involves "opening" the black-box. Intuitively, the fact that the spectral parameter in Π Low (ϕ tr v) is compactly supported indicates that strong elliptic estimates should hold, but knowing that v Low is analytic is dependent on the coefficients and domain inside the black box.

The abstract result Theorem 4.1 contains the abstract regularity hypothesis (4.4). The choices of this hypothesis to prove Theorems 1.16 and 1.17 are discussed in §4.2 (after the statement of Theorem 4.1), but we highlight here that bound (1.20) on v Low in Theorem 1.16 is proved using explicit calculation involving the eigenvalues of -∆ on the torus, and the bound (1.23) on v Low in Theorem 1.17 is proved using heat equation bounds from [START_REF] Escauriaza | Analyticity of solutions to parabolic evolutions and applications[END_REF]. Indeed, for the latter, because of the compact support of the spectral parameter in Π Low , we can run the backward heat equation on Π Low (ϕ tr v) for as long as we like and obtain L 2 estimates on the result. If the boundary and coefficients are analytic then known heat kernel estimates yield the necessary Cauchy-type estimates on ∂ α Π Low (ϕ tr v); see Corollary 6.1 and Theorem 6.2 below.

Discussion of the recent thesis [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF] that extends the approach of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF] to variablecoefficient problems. The recent thesis [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF] is an extension of the approach of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF] to variable-coefficient Helmholtz problems. We make the following three remarks comparing and contrasting the approach of [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF] (following [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF]) and the approach of [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF]/ [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]/the present paper.

1. (Boundary conditions.) The approach of [6, Lemma 6.5.8] in principle covers a variety of boundary conditions. For example, [6, Theorem 6.6.7] proves an analogous result to Theorem 1.12 under (i) assumptions about the coefficients and domain discussed in Point 2 below, and (ii) the assumption that the solution operator of the PML problem is polynomially bounded in k [6, Assumption 6.6.6]. Theorem 5.3 below (from [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF]) verifies the latter assumption (under the assumptions on the scaling function in §1.3), and thus completes the proof in [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF] for PML truncation.

We note that truncation via the exact DtN map, which is the easiest boundary condition to deal with in the approach of [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF]/ [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]/the present paper, is the most difficult boundary condition to deal with in the approach of [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF]. Indeed, the decomposition for the DtN map required in the latter approach is proved using results about boundary integral operators from [START_REF] Melenk | Mapping properties of combined field Helmholtz boundary integral operators[END_REF] (see [6, Lemma 6.5.12 and its proof in §6.9]).

(Assumptions on the coefficients/domain.)

As in [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF], the frequency cut-offs in [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF] are applied to the data; v A is then the solution of a Helmholtz problem with (piecewise) analytic data, and one needs (piecewise) analytic coefficients (where the pieces are separated by analytic surfaces) and an analytic domain to get that v A is analytic [6, Lemma 6.5.8].

In contrast, the approach in [START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF]/ [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]/the present paper can deal with smooth coefficients (everywhere when Ω -= ∅, and away from the obstacle in the general case) as a result of applying the cut-offs to the solution itself.

3. (Bound on the high-frequency part.) In [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF], the semiclassical ellipticity of the Helmholtz operator on high frequencies -although not explicitly mentioned -is again behind the improved bound on v H 2 compared to v. Indeed, with S - k the solution operator to the Helmholtz equation (∆ + k 2 )v = -f and S + k the solution operator to (∆ -k 2 v) = f , [6, Page 98] writes "we will later see that S - k and S + k act very similar on high-frequency data" (with "later" referring to [START_REF] Bernkopf | Finite element analysis of the heterogeneous Helmholtz equation and least squares methods[END_REF]Remark 6.3.7]).

Outline of the rest of the paper

Section 2 proves the hp-FEM convergence result of Theorem 1.12 using Theorems 1.16 and 1.17, as discussed in §1.5, this follows closely the arguments in [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF][START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] and so, for brevity, quotes several results from these papers without proof.

Section 3 recalls the framework of black-box scattering, and sets up the associated functional calculus; this section is similar to [29, §2] (and refers to that for some of the proofs) except that it now has to deal with both the (unscaled) operator P and the scaled operator P θ , whereas [29, §2] only deals with P .

Section 4 states the main decomposition result for Helmholtz solutions in the black-box framework with PML truncation (Theorem 4.1), with this result then proved in Section 5.

Section 6 shows how Theorems 1.16 and 1.17 follow from Theorem 4.1 -by design, these proofs are essentially identical to the proofs in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] of the analogous results for outgoing Helmholtz solutions; we therefore give a sketch of the main steps.

Appendix A recalls results about semiclassical pseudodifferential operators on the torus.

2 Proof of Theorem 1.12 using Theorems 1.16 and 1.17

.1 Overview

The two ingredients for the proof of Theorem 1.12 are

• Lemma 2.9, which is the classic duality argument giving a condition for quasioptimality to hold in terms of how well the solution of the adjoint problem is approximated by the finite-element space (measured by the quantity η(V N ) defined by (2.5)), and

• Lemma 2.10 that bounds η(V N ) using the decomposition from Theorem 1.17.

Regarding Lemma 2.9: this argument came out of ideas introduced in [START_REF] Schatz | An observation concerning Ritz-Galerkin methods with indefinite bilinear forms[END_REF], was formalised in its present form in [START_REF] Sauter | A refined finite element convergence theory for highly indefinite Helmholtz problems[END_REF], and has been used extensively in the analysis of the Helmholtz FEM; see, e.g., [START_REF] Aziz | A two point boundary value problem with a rapidly oscillating solution[END_REF][START_REF] Douglas | Frequency domain treatment of one-dimensional scalar waves[END_REF][START_REF] Melenk | On generalized finite element methods[END_REF][START_REF] Ihlenburg | Finite element analysis of acoustic scattering[END_REF][START_REF] Sauter | A refined finite element convergence theory for highly indefinite Helmholtz problems[END_REF][START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Zhu | Preasymptotic error analysis of CIP-FEM and FEM for Helmholtz equation with high wave number. Part II: hp version[END_REF][START_REF] Wu | Pre-asymptotic error analysis of CIP-FEM and FEM for the Helmholtz equation with high wave number. Part I: linear version[END_REF][START_REF] Du | Preasymptotic error analysis of higher order FEM and CIP-FEM for Helmholtz equation with high wave number[END_REF][START_REF] Chaumont-Frelet | High-frequency behaviour of corner singularities in Helmholtz problems[END_REF][START_REF] Li | FEM and CIP-FEM for Helmholtz Equation with High Wave Number and Perfectly Matched Layer Truncation[END_REF][START_REF] Chaumont-Frelet | Wavenumber explicit convergence analysis for finite element discretizations of general wave propagation problem[END_REF][START_REF] Gallistl | Wavenumber explicit convergence analysis for finite element discretizations of time-harmonic wave propagation problems with perfectly matched layers[END_REF][START_REF] Graham | Stability and finite element error analysis for the Helmholtz equation with variable coefficients[END_REF][START_REF] Galkowski | Optimal constants in nontrapping resolvent estimates[END_REF][START_REF] Lafontaine | Wavenumber-explicit convergence of the hp-FEM for the full-space heterogeneous Helmholtz equation with smooth coefficients[END_REF]. Regarding Lemma 2.10: given the decomposition in Theorem 1.17, the bound on η(V N ) when Assumption 1.11 is satisfied is identical to the corresponding proof of [29, Lemma 5.5] (which is also very similar to the proof of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF]Theorem 5.5]).

The main work in this section is therefore recalling that the PML variational formulation (1.12) satisfies a Gårding inequality and therefore fits in the framework of Lemma 2.9.

The sesquilinear form a(•, •) is continuous and satisfies a Gårding inequality

In the following lemma (•, •) 2 and • 2 denote, respectively, the Euclidean inner product and associated norm on C d .

Lemma 2.1 Given A scat and c scat as in Definition 1.1, a scaling function f (r) satisfying (1.8), and > 0 there exist A + and c -such that, for all ≤ θ ≤ π/2 -,

|(A(x)ξ, ζ) 2 | ≤ A + ξ 2 ζ 2 for all ξ, ζ ∈ C d and x ∈ Ω, and
1 |c(x)| 2 ≥ 1 c 2 - for all x ∈ Ω.
Proof. This follows from the definitions of A and c in (1.11), the definitions of α and β in (1.10), and the fact that f θ (r) := f (r) tan θ.

Corollary 2.2 (Continuity of a(•, •)) If C cont := max{A + , c -2 -}, then |a(v, w)| ≤ C cont v H 1 k (Ω) w H 1 k (Ω)
for all v, w ∈ H 1 0 (Ω).

Proof. This follows by the Cauchy-Schwarz inequality and the definition of

• H 1 k (Ω) (1.
3). Lemma 2.3 Suppose that Assumption 1.9 holds when d = 3. With A defined by (1.11), given > 0 there exists A -> 0 such that, for all ≤ θ ≤ π/2 -,

A(x)ξ, ξ 2 ≥ A -ξ 2 2 for all ξ ∈ C d and x ∈ Ω + . Corollary 2.4 (a(•, •) satisfies a Gårding inequality) a(w, w) ≥ A -w 2 H 1 k (Ω) -A -+ c -2 min k 2 w 2 L 2 (Ω)
for all w ∈ H 1 0 (Ω).

(2.1)

Proof of Lemma 2.3. By assumption, A scat (x) is symmetric positive definite for all x ∈ Ω with r ≤ R 1 . We therefore only need to consider the region r ≥ R 1 Let η := H T ξ; since H is orthogonal, η 2 = ξ 2 . Then (Aξ, ξ) 2 = (Dη, η) 2 . Explicit calculation from the definition of D shows that

D =   1+r -1 f θ f θ 1+(f θ ) 2 0 0 1+r -1 f θ f θ 1+r -2 f 2 θ   , d = 2, and D =    1-r -2 f 2 θ +2r -1 f θ f θ 1+f 2 θ 0 0 0 1 0 0 0 1    , d = 3.
(2.2)

We now claim that there exists C > 0 (depending on tan θ) such that

(D(x)η, η) 2 = ( D(x)η, η) 2 ≥ C η 2 2
for all η ∈ C d and r ≥ R 1 ;

(2.3) the result then follows since tan θ depends continuously on θ and is bounded above and below (with bounds depending on ) for ≤ θ ≤ π/2 -. When d = 2, (2.3) follows immediately from (2.2) and the fact that both r -1 f θ and f θ are non-negative. When d = 3, (2.3) follows if we can show that

r -1 f θ (r) ≤ f θ (r) for all r ≥ R 1 ,
which in turn follows from Assumption 1.9 since f θ (r) = f θ (r)/r + r(f θ (r)/r) .

Remark 2.5 (Assumption 1.9 and Lemma 2.3) Without assumptions on f θ (r) additional to (1.8) (such as Assumption 1.9) the eigenvalues of the matrix D will not all lie in a half plane. Indeed, α (defined in (1.10)) lies in the first quadrant of the complex plane for all θ ∈ [0, π/2]. Explicit calculation shows that

β 2 α = 1 + (f θ ) 2 -1 1 - f θ r 2 + 2f θ f θ r + i 2f θ r + f θ f θ r 2 -1 .
If f θ (r)/r is small compared to both 1 and f θ (r) (which can occur when the scaling "turns on" sufficiently quickly at a large R 1 )

β 2 α ≈ 1 + (f θ ) 2 -1 1 + 2f θ f θ r -if θ
and so is in the fourth quadrant of the complex plane. If, in addition, f θ (r) is large compared to 1, then 3π/2 ≤ arg(β 2 /α) ≤ 7π/8. If there exists r * ∈ (R 1 , R 2 ) such that f θ (r * ) is small then

β 2 α ≈ 1 - f θ r 2 + i 2f θ r .
Suppose, furthermore, that f θ (r * ) > r * tan θ. Then if tan θ > 1 (i.e., θ > π/4), then when r = r * , β 2 /α lies in the second quadrant of the complex plane. Furthermore, as θ → π/2, the argument of β 2 /α tends to π. Therefore, for an f θ (r) combining the two types of behaviour above, β 2 /α and α are not contained in the same half plane for all R 1 ≤ r ≤ R 2 and ≤ θ ≤ π/2 -.

The standard duality argument

* f ∈ H 1 0 (Ω) such that a(v, S * f ) = Ω v f for all v ∈ H 1 0 (Ω). (2.4)
The conditions for quasioptimality below are formulated in terms of S * . However, we record immediately in the following lemma that S * f is just the complex-conjugate of a solution of the PML variational problem (1.12).

Lemma 2.7 (The adjoint solution is the complex conjugate of a Helmholtz solution) With S * is defined by (2.4),

a(S * k f , w) = Ω f w for all w ∈ H 1 0 (Ω).
Proof. By the definitions of a(•, •) and the coefficients A and c -2 (1.11), and the facts that H is real and D is diagonal (and hence symmetric), a(v, w) = a(w, v) for all v, w ∈ H 1 0 (Ω); the result then follows from the definition of S * k (2.4).

Definition 2.8 (η(V N )) Given a sequence (V N ) ∞ N =0 of finite-dimensional subspaces of H 1 0 (Ω), let η(V N ) := sup 0 =f ∈L 2 (Ω) min w N ∈V N S * f -w N H 1 k (Ω) f L 2 (Ω) . (2.5)
Lemma 2.9 (Conditions for quasioptimality) If

k η(V N ) ≤ 1 C cont A + 2 A -+ c -2 - ,
then the Galerkin equations (1.14) have a unique solution which satisfies

v -v N H 1 k (Ω) ≤ 2C cont A - min w N ∈V N v -w N H 1 k (Ω) .
References for the proof. This is based on the Gårding inequality (2.1); see, e.g., [53, Theorem 4.3] (when A ≡ I and c ≡ 1) or [43, Lemma 6.4] (for general A and c).

2.4

The bound on η(V N ) obtained using Theorems 1.16 and 1.17 Given N > 0 there exist

• k 1 , C 1 , C 2
, σ > 0, all independent of k, h, p, and N , and

• C N > 0, independent of k, h, p, such that, for k ∈ K ∩ [k 1 , ∞), k η(V N ) ≤ C 1 hk p 1 + hk p + C 2 k M h h + σ p + k hk σp p + C N k 1-N . (2.6)
Proof. The proof of the bound (2.6) using Theorems 1.16/1.17 is identical to the proof of [

have v = v H 2 + v A + v residual , whereas [29, Lemma 5.5] only has v = v H 2 + v A .
The term v residual , however, can be approximated by zero giving a term of the form C N k 1-N (other terms of this form arise, exactly as in the proof of [29, Lemma 5.5], from approximating in the regions where they are negligible either v A,far and v A,near in Theorem 1.17 or v A in Theorem 1.16).

2.5 Proof of Theorem 1.12 from the bound on η(V N )

The existence of the solution v to the variational problem (1.12) follows from [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF]Theorem 1.6]. Indeed, this result proves existence and uniqueness of the PML solution for k is sufficiently large when G(w) = Ω g w for g ∈ L 2 (Ω). Existence and uniqueness of the PML solution for G ∈ (H 1 k (Ω)) * follows from existence and uniqueness for L 2 right-hand sides since the problem is Fredholm (via the Gårding inequality (2.1)).

To prove existence of the Galerkin solution v N to (1.14) under the conditions (1.13), we combine Lemmas 2.9 and 2.10 Indeed, the bound on k η(V N ) (2.6) holds by Lemma 2.10. We choose N > 1, and then increase k 1 > 0 (if necessary) so that

C N k 1-N ≤ 1 2C cont A - 2 A -+ c -2 - for all k ≥ k 1 .
After using this bound in (2.6), we see that the conditions (1.13) with C 1 sufficiently small and C 2 sufficiently large then ensure that k η(V N ) is sufficiently small (independent of k), and the result follows from Lemma 2.9.

The black-box framework and functional calculus 3.1 Recap of the black-box framework

Let := k -1 be the semiclassical parameter; in the literature, the semiclassical parameter is often denoted by h, but we use to avoid a notational clash with the meshwidth of the FEM appearing in §1 and §2.

In this subsection, we briefly recap the abstract framework of black-box scattering introduced in [START_REF] Sjöstrand | Complex scaling and the distribution of scattering poles[END_REF]; for more details, see the comprehensive presentation in [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Chapter 4]. In fact, we use the approach of [61, §2], where the black-box operator is a variable-coefficient Laplacian (with smooth coefficients) outside the black-box, and not the Laplacian -2 ∆ itself as in [21, Chapter 4] (although the operator still agrees with -2 ∆ outside a sufficiently large ball).

The operator P . Let H be a Hilbert space with an orthogonal decomposition

H = H R0 ⊕ L 2 (R d \B R0 , ω(x)dx), (BB1)
where the weight-function ω : R d → R is measurable and supp(1 -ω) is compact in R d . Let 1 B R 0 and 1 R d \B R 0 denote the corresponding orthogonal projections. Let P be a family in of self adjoint operators H → H with domain D ⊂ H independent of (so that, in particular, D is dense in H). Outside the black-box H R0 , we assume that P equals Q defined as follows. We assume that, for any multi-index |α| ≤ 2, there exist functions a ,α ∈ C ∞ (R d ), uniformly bounded with respect to , independent of for |α| = 2, and such that (i) for some

C 1 > 0 |α|=2 a ,α (x)ξ α ≥ C 1 |ξ| 2 for all x ∈ R d , (3.1)
(ii) for some

R scat > R 0 |α|≤2 a ,α (x)ξ α = |ξ| 2 for |x| ≥ R scat ,
and (iii) the operator Q defined by

Q := |α|≤2 a ,α (x)( D x ) α (3.2)
(where

D := -i∂) is formally self-adjoint on L 2 (R d , ω(x)dx).
We require the operator P to be equal to Q outside the black-box H R0 in the sense that

1 R d \B R 0 (P u) = Q (u| R d \B R 0 ) for u ∈ D, and 1 R d \B R 0 D ⊂ H 2 (R d \B R0 ). (BB2)
We further assume that if, for some ε > 0,

v ∈ H 2 (R d ) and v| B R 0 +ε = 0, then v ∈ D, (BB3)
(with the restriction to B R0+ defined in terms of the projections in (BB2); see also (3.7) below) and that

1 B R 0 (P + i) -1 is compact from H → H. (BB4)
Under these assumptions, the semiclassical resolvent R(z, ) := (P -z) -1 : H → D is meromorphic for Im z > 0 and extends to a meromorphic family of operators of H comp → D loc in the whole complex plane when d is odd and in the logarithmic plane when d is even [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Theorem 4.4]; where H comp and D loc are defined by

H comp := u ∈ H : 1 R d \B R 0 u ∈ L 2 comp (R d \B R0 ) ,
(where L2 comp denotes compactly-supported L 2 functions) and

D loc := u ∈ H R0 ⊕ L 2 loc (R d \B R0 ) : if χ ∈ C ∞ comp (R d ), χ| B R 0 ≡ 1 then (1 B R 0 u, χ1 R d \B R 0 u) ∈ D .
The reference operator P . We now define the so-called reference operator using the torus

T d R := R d / (2R Z) d for some R > 0 such that supp(1 -ω) ⊂ B R .
We work with [-R , R ] d as a fundamental domain for this torus. The black-box framework by itself requires that R > R scat ; for simplicity we take R > diam(Ω tr ), so that Ω tr ⊂ [-R , R ] d (where we assume, without loss of generality, the origin is inside Ω tr ). 2 Let H := H R0 ⊕ L 2 (T d R \B R0 , ω(x)dx), and let 1 B R 0 and 1 T d R \B R 0 denote the corresponding orthogonal projections. We define

D := u ∈ H : if χ ∈ C ∞ comp (B R ), χ = 1 near B R0 , then (1 B R 0 u, χ1 T d R \B R 0 u) ∈ D, and (1 -χ)1 T d R \B R 0 u ∈ H 2 (T d R ) , (3.3)
and, for any χ as in (3.3) and u ∈ D ,

P u := P (1 B R 0 u, χ1 T d R \B R 0 u) + Q (1 -χ)1 T d R \B R 0 u , (3.4)
where we have identified functions supported in B(0, R )\B(0, R 0 ) ⊂ T d R \B(0, R 0 ) with the corresponding functions on R d \B(0, R 0 ) -see the paragraph on notation below.

Let q ∈ S 2 (T d R ) denote the principal symbol of Q as a semiclassical pseudodifferential operator acting on the torus T d R (see Appendix A for a review of semiclassical pseudodifferential operators on T d R ). We record for later the fact that (3.1), (3.2), and the uniform boundedness of a ,α (x) with respect to imply that there exist C 1 , C 2 > 0 such that C 1 |ξ| 2 ≤ q (x, ξ) ≤ C 2 |ξ| 2 for sufficiently large ξ and all x.

(3.5)

The idea behind these definitions is that we have glued our black box into a torus instead of R d , and then defined on the torus an operator P that can be thought of as P in H R0 and Q in (R/2R Z) d \B R0 ; see Figure 3.1. The resolvent (P + i) -1 is compact (see [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Lemma 4.11]), and hence the spectrum of P , denoted by Sp P , is discrete (i.e., countable and with no accumulation point).

We assume that the eigenvalues of P satisfy the polynomial growth of eigenvalues condition

N P , [-C, λ] = O( -d λ d /2 ), (BB5)
for some d ≥ d, where N (P , I) is the number of eigenvalues of P in the interval I, counted with their multiplicity. When d = d, the asymptotics (BB5) correspond to a Weyl-type upper bound, and thus (BB5) can be thought of as a weak Weyl law.

We summarise with the following definition.

Definition 3.1 (Semiclassical black-box operator)

We say that a family of self-adjoint operators P on a Hilbert space H, with dense domain D, independent of , is a semiclassical black-box operator if (P , H) satisfies (BB1), (BB2), (BB3), (BB4), (BB5).

P h P h ?

P h P h Q h P h P h -h 2 ∆ R R 0 R scat P h -h 2 ∆ Figure 3.1:
The black-box setting. The symbol is used to denote equality in the sense of (BB2) and (3.4).

Notation. We identify in the natural way:

• the elements of {0} ⊕ L 2 (T d R \B R0 ) ⊂ H , • the elements of L 2 (T d R \B R0 ),
• the elements of L 2 (T d R ) supported outside B R0 ,

• the elements of L 2 (R d ) supported in [-R , R ] d \B R0 ,
• and the elements of

{0} ⊕ L 2 (R d \B R0 ) ⊂ H whose orthogonal projection onto L 2 (R d \B R0 ) is supported in [-R , R ] d \B R0 . If v ∈ H and χ ∈ C ∞ comp (R d
) is equal to some constant α on a neighbourhood of B R0 , we define

χv := (α1 B R 0 v, χ1 R d \B R 0 v) ∈ H. (3.6)
(for example, using this notation, the requirements on u in the definition of

D (3.3) are χu ∈ D and (1 -χ)u ∈ H 2 (T d R ) for χ equal to 1 near B R0 ). If v ∈ H and R > R 0 , we define v| B R := 1 B R 0 v, (1 R d \B R 0 v | B R ) ∈ H R0 ⊕ L 2 (B R \B R0 ), (3.7) and, if v ∈ H , v| B R := 1 B R 0 v, (1 T d R \B R 0 v | B R ) ∈ H R0 ⊕ L 2 (B R \B R0 ). Finally, if R 0 ≤ r ≤ R , we define the partial norms u H (Br) = u H(Br) := u H R 0 ⊕L 2 (Br\B R 0 ) , u H (B c r ) := 1 T d R \B R 0 u L 2 (T d R \Br) and u H(B c r ) := 1 R d \B R 0 u L 2 (R d \Br) .

Scattering problems fitting in the black-box framework

P v := -2 c 2 scat ∇ • A scat ∇v)
with the domain

D := H 2 (Ω + ) ∩ H 1 0 (Ω + ) is a semiclassical black-box operator (in the sense of Definition 3.1) with ω = c -2 scat , Q = -2 c 2 scat ∇ • (A scat ∇), and
H R0 = L 2 B R0 ∩ Ω + ; c -2 scat (x)dx so that H = L 2 Ω + ; c -2 scat (x)dx .
Furthermore the corresponding reference operator P satisfies (BB5) with d = d.

Proof. In [29, Lemma 2.3] the result is proved for Lipschitz Ω -and A scat and c ∈ L ∞ with domain

v ∈ H 1 (Ω + ), ∇ • A scat ∇v ∈ L 2 (Ω + ), v = 0 on ∂Ω + ;
by elliptic regularity, this domain equals H 2 (Ω + ) ∩ H 1 0 (Ω + ) when Ω -and A scat are smooth.

The scaled operator P ,θ and its truncation

The scaled operator P ,θ . With χ ∈ C ∞ comp (B R1 ) equal to 1 on B R0 , we define the scaled operator P ,θ u := P (χu) + (-

2 ∆ θ )((1 -χ)u), (3.8)
where ∆ θ is defined by (1.7) Although the domain and range of P ,θ strictly involve the scaled manifold (see [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Definition 4.31], [27, Equation A.3]), they can be naturally identified with D and H, respectively.

Truncation of the scaled operator (i.e., PML truncation). For the PML truncation, just as in §1.3, we let Ω tr ⊂ R d be a bounded Lipschitz open set with B Rtr ⊂ Ω tr . Just as for P ,θ on the whole exterior domain, the domain and range of P ,θ on the truncated domain strictly involve the scaled manifold (see [28, §A.3]). However, we can naturally identify them with the following:

H(Ω tr ) := H R0 ⊕ L 2 (Ω tr \ B R0 ), D(Ω tr ) := u ∈ H(Ω tr ) : if χ ∈ C ∞ comp (B R1 ) with χ ≡ 1 near B R0 then χu ∈ D, (1 -χ)u ∈ H 1 0 (Ω tr ), -∆ θ ((1 -χ)u) ∈ L 2 (Ω tr ) .
Remark 3.3 (A different choice of reference operator) Instead of defining the reference operator P using the torus T d R , we could instead define P using a large ball or hypercube with zero Dirichlet boundary conditions; see [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Remark on Page 236]. We could therefore define the reference operator P on the domain Ω tr used for the PML truncation, which would have the advantage that the domain of P could be naturally identified with the domain of P ,θ . We choose not to do this, however, since our arguments extensively use pseudodifferential operators defined on the torus T d R , and part of our proof of the decomposition of Theorem 1.15/4.1 involve explicit computation with the eigenvalues of the Laplacian on T d R ; see §5.4.6.

Definition of a suitable scaled operator on the torus. Fix δ > 0 so that R 1 + 4δ < R tr .

In the course of the proof of the main result, we need a operator defined on T d R and equal to P ,θ on B R1(1+3δ) \ B R0 . We therefore let -∆ θ be defined by (1.7) with f θ replaced by a non-negative function

f θ ∈ C ∞ ([0, ∞); R) such that f θ (r) = f θ (r) for r ≤ R 1 + 3δ and f (r) = 0 for r ≥ R 1 + 4δ; (3.9)
i.e., -∆ θ = -∆ θ for r ≤ R 1 + 3δ and -∆ θ = -∆ for r ≥ R 1 + 4δ (so that the coefficients of -∆ θ are periodic on the torus T d R ). Define the operator Q ,θ on H 2 (T d R ) by

Q ,θ u = Q ψu + (-2 ∆ θ ) (1 -ψ)u , (3.10)
where ψ ∈ C ∞ comp (B R1 ) with ψ ≡ 1 on B Rscat (we use a tilde in the notation to denote that Q ,θ is not just the natural scaling of Q ). Let q ,θ ∈ S 2 (T d R ) denote the principal symbol of Q ,θ as a semiclassical pseudodifferential operator acting on the torus T d R (see §A).

A black-box functional calculus for P

The Borel functional calculus. The operator P on the torus with domain D is self-adjoint with compact resolvent [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Lemma 4.11], hence we can describe the Borel functional calculus [START_REF] Reed | Methods of Modern Mathematical Physics Volume 1: Functional analysis[END_REF]Theorem VIII.6] for this operator explicitly in terms of the orthonormal basis of eigenfunctions φ j ∈ H (with eigenvalues λ j , appearing with multiplicity and depending on ): for f a real-valued Borel function on R, f (P ) is self-adjoint with domain

D f := a j φ j ∈ H : f (λ j )a j 2 < ∞ , and if v = a j φ j ∈ D f then f (P )(v) := a j f (λ j )φ j .
For f a bounded Borel function, f (P ) is a bounded operator, hence in this case we can dispense with the definition of the domain and allow f to be complex-valued. For m ≥ 1, we then define D ,m as the domain of (P ) m , i.e.,

D ,m := v ∈ H : (P ) v ∈ D , = 0, . . . , m -1 , equipped with the norm v D ,m := v H + (P ) m v H , (3.11)
and D ,-m as its dual (note that, in the exterior of the black box, the regularity imposed in the definition of D ,m is that of periodic functions on the torus with 2m derivatives in L 2 ). We also define the partial norms, for m > 0,

v D ,m (B) := v H (B) + (P ) m v H (B) ,
where B equals one of B r or (B r ) c (with R 0 ≤ r ≤ R ) or Ω tr . In addition, we let

D ,∞ := m≥0 D ,m , (3.12) so that v ∈ D ,∞ iff (P ) m v ∈ D for all m ∈ Z + .
The following theorem is proved in [START_REF] Davies | Spectral theory and differential operators[END_REF]Pages 23 and 24]; see also [START_REF] Reed | Methods of Modern Mathematical Physics Volume 1: Functional analysis[END_REF]Theorem VIII.5].

Theorem 3.4

The Borel functional calculus enjoys the following properties.

1. f → f (P ) is a -algebra homomorphism.

2. for z / ∈ R, if r z (w) := (w -z) -1 then r z (P ) = (P -z) -1 .

3. If f is bounded, f (P ) is a bounded operator for all , with f (P ) L(H ) ≤ sup λ∈R |f (λ)|.

4. If f has disjoint support from Sp P , then f (P ) = 0.

The Helffer-Sjöstrand construction. In describing the structure of the operators produced by the functional calculus, at least for well-behaved functions f, it is useful to recall the Helffer-Sjöstrand construction of the functional calculus [START_REF] Helffer | Équation de Schrödinger avec champ magnétique et équation de Harper[END_REF], [17, §2.2] (which can also be used to prove the spectral theorem to begin with; see [START_REF] Davies | The functional calculus[END_REF]). We say that f ∈ A if f ∈ C ∞ (R) and there exists β < 0, such that, for all r > 0, there exists

C r > 0 such that |f (r) (x)| ≤ C r (1 + |x| 2 ) (β-r)/2 .
Let τ ∈ C ∞ (R) be such that τ (s) = 1 for |s| ≤ 1 and τ (s) = 0 for |s| ≥ 2. Finally, let n ≥ 1. We define an n-almost-analytic extension of f , denoted by f , by Pseudodifferential properties of the functional calculus. We say that Furthermore, we can show from [61, §4] that, modulo a negligible term, away from the blackbox the functional calculus is given by the semiclassical pseudodifferential calculus in the sense of our next lemma. The following lemma uses the notion of semiclassical pseudodifferential operators on T d R (including the concept of the operator wavefront set WF ), recapped in Appendix A.

f (z) := n m=0 1 m! ∂ m f (Re z) (i Im z) m τ Im z Re z (observe that f (z) = f (z) if z is real). For f ∈ A, we define f (P ) := - 1 π C ∂ f ∂ z (P -z) -1 dxdy, ( 3
E ∞ ∈ L(H ) is O( ∞ ) D ,-∞ →D ,∞ if,

Lemma 3.6 (Pseudodifferential properties away from the black box)

If f ∈ C ∞ comp (R) is independent of and χ ∈ C ∞ (T d R ) is equal to zero near B R0 , then f (Q ) ∈ Ψ -∞ (T d R ) with χf (P )χ = χf (Q )χ + O( ∞ ) D ,-∞ →D ,∞ . (3.15)
References for the proof. The relation (3.15) follows from [61, Lemma 4.2 and the subsequent two paragraphs] (similar to in the proof of Lemma 3.6). The result [34, Théorème 4.1] (see also [START_REF] Robert | Autour de l'approximation semi-classique[END_REF], [START_REF] Dimassi | Spectral asymptotics in the semi-classical limit[END_REF]Theorem 8.7]) imply that f (Q ) is a pseudodifferential operator on T d R .

Black-box differentiation operator

Finally, we define the (non-standard) notion of a family of black-box differentiation operators as a family of operators agreeing with differentiation outside the black-box (note that there is no a priori notion of derivative inside the black-box itself).

v ∈ C ∞ comp (T d R \B R0 ), D(α)v = ∂ α v.
4

The main decomposition result in the black-box setting 4.1 The precise statement of Theorem 1.15

In addition to the black-box notation introduced in §3, we use the notation that

C 0 (R) := f ∈ C(R) : lim λ→±∞ f (λ) = 0 . (4.1)
Theorem 4.1 (The decomposition in the black-box setting) Let P be a semiclassical blackbox operator on H (in the sense of Definition 3.1). There exists Λ > 0 such that the following holds. Suppose that, for some 0 > 0, there exists H ⊂ (0, 0 ] such that the following two assumptions hold.

1. There exists M ≥ 0 such that for any χ ∈ C ∞ comp (R d ) equal to one near B R0 , there exists C > 0 such that if u ∈ D is an outgoing solution to (P -I)u = χg, then

χu H ≤ C -M -1 χg H for all ∈ H. ( 4

.2)

2. There exists E ∈ C 0 (R) that is nowhere zero on [-Λ, Λ] such that

E(P ) = E + O( ∞ ) D ,-∞ →D ,∞ , (4.3
)

where E has the following property: there exists ρ ∈ C ∞ (T d R ) equal to one near B R0 , such that, for some α-family of black-box differentiation operators (D(α)) α∈A and for some

C E (α, ) > 0, ρD(α)Ew H ≤ C E (α, ) w H for all w ∈ D ,∞ and ∈ H, (4.4)
Given > 0, there exist 1 > 0, C j > 0, j = 1, 2, 3, and λ > 1 such that for all R tr > (1 + )R 1 , B Rtr ⊂ Ω tr R d with Lipschitz boundary, < θ < π/2 -, all g ∈ H(Ω tr ), and all ∈ H ∩ (0, 1 ], the following holds. The solution v ∈ D(Ω tr ) to

(P ,θ -I)v = g on Ω tr and v = 0 on Γ tr (4.5)
exists and is unique and there exists v

H 2 ∈ D(Ω tr ), v A ∈ D ,∞ , and v residual ∈ D ,∞ such that v = v H 2 + v A + v residual (4.6)
and v H 2 , v A , and v residual satisfy the following properties. The component v

H 2 ∈ D(Ω tr ) satisfies v H 2 H(Ωtr) + P ,θ v H 2 H(Ωtr) ≤ C 1 g H(Ωtr) for all ∈ H ∩ (0, 1 ]. (4.7) There exist R I , R II , R III , R IV with R 0 < R I < R II < R III < R IV < R 1 such that v A ∈ D ,∞ decomposes as v A = v A,near + v A,far , (4.8)
where v A,near ∈ D is regular near the black-box and negligible away from it, in the sense that

D(α)v A,near H (B R IV ) ≤ C 2 C E (α, ) sup λ∈[-Λ,Λ] E(λ) -1 -M -1 g H(Ωtr) (4.9)
for all ∈ H ∩ (0, 1 ], α ∈ A, and, for any N, m > 0 there exists

C N,m > 0 (independent of θ) such that v A,near D ,m ((B R III ) c ) ≤ C N,m N g H(Ωtr) for all ∈ H ∩ (0, 1 ] (4.10)
and v A,far ∈ D(Ω tr ) is entire away from the black-box and negligible near it, in the sense that

∂ α v A,far H ((B R I ) c ) ≤ C 3 λ |α| -|α|-M -1 g H(Ωtr) for all ∈ H ∩ (0, 1 ] and α ∈ A, (4.11)
and, for any N, m > 0 there exists C N,m > 0 (independent of θ) such that

v A,far D ,m (B R II ) ≤ C N,m N g H(Ωtr) for all ∈ H ∩ (0, 1 ]. (4.12)
Finally, v residual ∈ D ,∞ is negligible in the sense that for any N, m > 0 there exists C N,m > 0 (independent of θ) such that

v residual D ,m (Ωtr) ≤ C N,m N g H(Ωtr) for all ∈ H ∩ (0, 1 ]. (4.13)
In addition, if ρ = 1 in (4.4), then the decomposition (4.6) can be constructed in such a way that instead of (4.8)-(4.12), v A ∈ D ,∞ satisfies the global regularity estimate

D(α)v A H C E (α, ) sup λ∈[-Λ,Λ] E(λ) -1 -M -1 g H(Ωtr) for all ∈ H and α ∈ A (4.14)
and is negligible in the scaling region in the sense that for any N, m > 0 there exists C N,m > 0

(independent of θ) such v A D ,m ((B R 1 (1+ ) ) c ) ≤ C N,m N g H(Ωtr) for all ∈ H ∩ (0, 1 ]. (4.15)
Finally, If E(P ) = E (i.e., with no O( ∞ ) D ,-∞ →D ,∞ remainder in (4.3)), then the functions v H 2 , v A , v A,near , and v A,far are all independent of E, and all the constants in the bounds above are independent of E as well.

Discussion of Theorem 4.1

The first assumption (involving (4.2)). This assumption is that the solution operator is polynomially bounded in . In the black-box setting, [START_REF] Lafontaine | For most frequencies, strong trapping has a weak effect in frequency-domain scattering[END_REF] proved that this assumption always holds with M > 5d/2 and { -1 : ∈ H} c having arbitrarily small measure in R + (see Part (ii) of Theorem 1.3). The solution operator is then polynomially bounded because H excludes (inverse) frequencies close to resonances. (Under an additional assumption about the location of resonances, a similar result with a larger M can also be extracted from [64, Proposition 3] by using the Markov inequality.) For nontrapping problems, one expects (4.2) to hold with M = 0 and H = (0, h 0 ] (see Theorem 1.3 and the references therein).

The second assumption (involving (4.3) and (4.4)). This assumption is a regularity assumption that depends on the contents of the black box. We later refer to (4.4) as the "low-frequency estimate", since the fact that E is nowhere zero on [-Λ, Λ] means that it bounds low-frequency components. The cut-off ρ in (4.4) is needed when the black box contains, e.g., an analytic obstacle and the operator inside has analytic coefficients and we want to show that Ew is analytic inside the black box.

To prove Theorem 1.16, we choose E ∈ C ∞ comp (R d ) with E ≡ 1 on [-Λ, Λ], and ρ ≡ 1; the low-frequency estimate (4.4) then corresponds to a bound on the eigenfunctions of P . By using the flexibility to write E(P ) as E + O( ∞ ) D ,-∞ →D ,∞ , we can actually obtain the low-frequency estimate (4.4) from a bound on the eigenfunctions of -∆ on the torus, instead of those of the variable-coefficient operator; see §6.2.

To prove Theorem 1.17, we choose E(λ) = e -t|λ| , corresponding to a heat-flow estimate; see §6. [START_REF] Bayliss | Boundary conditions for the numerical solution of elliptic equations in exterior regions[END_REF]. Since E ∞ = 0, the decomposition is independent of E, and this allows us to use a family of Es, depending on t, and hence a family of estimates as (4.4). This feature allows us to tune the choice of the parameter t, depending on and α, to get the best possible estimate on v A,near in (4.9).

The component v H 2 . Comparing (4.2) and (4.7), and recalling that in the nontrapping case (4.2) holds with M = 0, we see that v H 2 satisfies a bound that is better, by at least one power of , than the bound satisfied by u; this is the analogue of the property (ii) in §1.5 of the results of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF][START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF][START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF][START_REF] Melenk | General DG-methods for highly indefinite Helmholtz problems[END_REF], and is a consequence of the semiclassical ellipticity of P -1 on high-frequencies (as discussed in §1.8). The regularity of v H 2 depends on the domain of the operator but not on any other features of the black box (in particular, not on the regularity estimate (4.4)).

The component v A . v A is in the domain of arbitrary powers of the operator (v A ∈ D ,∞ ) and so is smooth in an abstract sense. v A is split further into two parts: v A,near and v A,far , with v A,near regular near the black-box and negligible away from it, and v A,far entire away from the blackbox and negligible near it; Figure 1.1 illustrates this set up (with "v A,near analytic" replaced by "v A,near regular"). Comparing (4.2) and (4.9)/(4.11), we see that, in the regions where they are not negligible, v A,near and v A,far satisfy bounds with the same -dependence as u, but with improved regularity. These properties are the analogue of the property (i) in §1.5 of the results of [START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF], [START_REF] Melenk | Wavenumber explicit convergence analysis for Galerkin discretizations of the Helmholtz equation[END_REF], [START_REF] Esterhazy | On stability of discretizations of the Helmholtz equation[END_REF], [START_REF] Melenk | General DG-methods for highly indefinite Helmholtz problems[END_REF]. In particular, the regularity of u A depends on the regularity inside the black-box (from (4.4)), and, for the exterior Dirichlet problem with analytic obstacle and coefficients analytic in a neighbourhood of the obstacle, u A is analytic.

The boundary conditions satisfied by each component. On both Γ tr and on any boundaries in the interior of the black box, each of the main components v H 2 , v A,far , and v A,near either satisfies the same boundary condition as the PML solution v or is negligible in a neighbourhood of that boundary. Indeed, both v H 2 and v A,far ∈ D(Ω tr ), and thus satisfy the same boundary conditions as v in both the black box and on Γ tr . The component v A,near ∈ D ,∞ , and thus satisfies the same boundary condition(s) (if any) as the PML solution v in the black box; furthermore, by (4.10), v A,near is negligible near Γ tr . This discussion was all for the case ρ = 1 in (4.4) (where v A is split into v A,far and v A,near ). When ρ = 1 in (4.4), v A ∈ D ,∞ , and thus satisfies the same boundary condition(s) (if any) as the PML solution v in the black box, and is negligible itself in a neighbourhood of Γ tr by (4.15) and the fact that R tr > R 1 (1 + ).

These facts about the boundary conditions are important when using the decomposition of Theorem 1.17 (obtained from the general decomposition in Theorem 4.1) in proving Theorem 1.12 about the hp-FEM. Indeed, Lemma 2.9 reduces proving quasioptimality of the Galerkin solution to determining how well v is approximated by the sequence of finite-element spaces (V N ) ∞ N =0 , with each V N ⊂ D(Ω tr ) (i.e., the spaces have the boundary conditions for v "built in"). Via the decomposition v = v H 2 + v A , we then seek to determine how well v H 2 and v A are approximated in these spaces -hence why we care about the boundary conditions.

The error term v residual . The reason the negligible error term v residual appears in the decomposition (4.6) is so that v H 2 satisfies the zero Dirichlet boundary condition on Γ tr , the importance of which is highlighted above. Note that if we did not care about v H 2 satisfying this boundary condition, we could include v residual in v H 2 .

Comparison with the analogous result for the (non-truncated) Helmholtz solution in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]Theorem A]. By design, the assumptions of Theorem 4.1 are exactly the same as the assumptions in the analogue of Theorem 4.1 for the non-truncated Helmholtz problem, i.e., [29, Theorem A]. The conclusions of Theorem 4.1 are essentially the same as those of [29, Theorem A], except for the fact that the decomposition has the residual term v residual ; as discussed in the previous paragraph, the reason for this is that we want v H 2 to satisfy the zero Dirichlet boundary condition on Γ tr (which is not present for the non-truncated Helmholtz problem).

Proof of Theorem 4.1

The decomposition (4.6) is defined in §5.1 (and illustrated schematically in Notation. In this proof, we shorten the notation

O( ∞ ) D ,-∞ →D ,∞ to O( ∞ ) D ,∞ to keep ex- pressions compact.
with v A ∈ D ,∞ satisfying (4.14) and (4.15). Otherwise, we show that

v Low = v A,near + v A,far + O( ∞ ) D ,∞ ϕ tr v, (5.16)
where v A,near and v A,far satisfy (4.9)-(4.12), v A,near ∈ D ,∞ , and v A,far ∈ D(Ω tr ).

The idea now is to let v H 2 equal v High + v PML , and then the decomposition (4.6) would hold by (5.12) and (5.15)/(5.16). However, we want v H 2 to be in D(Ω tr ), which is not guaranteed since, although v PML ∈ D(Ω tr ) (as noted above), v High need not be in D(Ω tr ). We therefore let ϕ tr ∈ C ∞ comp (R d ; [0, 1]) be such that ϕ tr ≡ 1 on a neighbourhood of supp ϕ tr and such that supp ϕ tr ⊂ B R1+3δ . Then, by the definitions of v High (5.11) and Π High (5.8) and Lemma 3.5,

v High = ϕ tr v High + O( ∞ ) D ,∞ ϕ tr v.
(5.17)

We then set v H 2 := ϕ tr v High + v PML , so that, by (5.12), (5.16), and (5.17),

v = v H 2 + v A + v residual where v residual = O( ∞ ) D ,∞ ϕ tr v.
(5.18)

The bound (4.13) on v residual (which completes the proof) follows from the result of [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF] (recapped in Theorem 5.3 below) that v inherits the polynomial bound on the resolvent enjoyed by u (4.2).

This decomposition strategy is summed-up in Figure 5.1; with an overview of the decomposition of the low-frequency component v Low in Figure 5.4.

Organisation of the rest of the proof. In §5.2 we prove the bound (5.14) on v PML . In §5.3 we prove the bound (5.13) on v High . In §5.4 we prove that the decomposition (5.16) holds, with v A,near and v A,far satisfying (4.9)-(4.12).

In the rest of the proof we assume that ∈ H and we omit the quantifiers and the explicit statement that the bounds hold uniformly for R tr > R 1 (1 + ) and < θ < π/2 -. We use the notation in bounds to indicate that the omitted constant is independent of .

The component near the PML boundary

In this subsection we prove that the bound (5.14) on v PML holds. We first recap results from [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF] about PML truncation.

Recap of three results from [28]

The first result is a special case of the result from [START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF]Theorem 1.6] that the solution operator of the PML problem "inherits" the -dependence of the solution operator of the original (nontruncated) Helmholtz problem. The next result is an elliptic estimate on the PML solution near the boundary (proved using the structure of -∆ θ in the scaling region). (5.20)

O( ∞ ) D ,∞ ϕ tr v small part O( ∞ ) D ,∞ ϕ tr v small part v A v residual ϕ tr ∈ C ∞ comp (B R1(1+2δ) ) 1 -ϕ tr Π Low Π High 1 -ϕ tr ϕ tr
The final result is a Carleman estimate describing how solutions of (-2 ∆ θ -1)v = f propagate in the scaling region. 4.6]) Given ε > 0 there exist C j > 0, j = 1, 2, 3, and 0 > 0 such that, for all ε ≤ θ ≤ π/2 -ε and 0 < < 0 , so that

v H 1 (Ωtr\B R 1 +ε ) ≤ C 1 (-2 ∆ θ -1)v L 2 (Ωtr\B R 1 ) + C 2 exp(-C 3 -1 ) v H 1 (B R 1 +ε \B R 1 ) . ( 5
]v L 2 (Ωtr) v H 1 (B R 1 +2δ \B R 1 +δ ) , (5.23)
R 0 R 1 (1 -δ) R 1 (1 + δ) R 1 ϕ 1 ϕ 0 ϕ 1 ϕ 0 R 1 (1 + 2δ) R 1 (1 + 3δ)
v PML H 1 (Ωtr\B R 1 +δ ) g H(Ωtr) + v H 1 (B R 1 +2δ \B R 1 +δ ) . ( 5
v H 1 (B R 1 +δ \B R 1 ) -M -1 g H(Ωtr) ; (5.26)
indeed, this follows by the combination of (i) the fact that P ,θ = -2 ∆ θ for R ≥ R 1 , (ii) the fact that -∆ θ is elliptic (by, e.g., [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Theorem 4.32]), (iii) elliptic regularity (to obtain control of the H 2 norm of v), and then (iv) interpolation (to obtain control of the H 1 norm of v). Then, the combination of (5.21) (with ε = min{ , δ}) and (5.26) implies that

v H 1 (B R 1 +2δ \B R 1 +δ ) 1 + exp(-C 3 -1 ) -M -1 g H(Ωtr) .
Combining this last inequality with (5.25) and reducing 0 if necessary, the result (5.14) follows.

5.3 Proof of the bound (5.13) on v High (the high-frequency component)

Decomposing into parts that are "near to" or "far from" the black box. Let ϕ 0 , ϕ 0 ∈ C ∞ comp (R d ; [0, 1]) be such that ϕ 0 ≡ 1 near B R0 and ϕ 0 ≡ 1 in a neighbourhood of supp ϕ 0 , with supp ϕ 0 ⊂ supp ϕ 0 ⊂ B R1(1-δ) , so that, in particular, P = P = P ,θ on the supports of ϕ 0 and ϕ 0 .

(5.27)

In addition, let ϕ 1 := 1 -ϕ 0 and let ϕ 1 ∈ C ∞ (R d ; [0, 1]) be supported away from the black-box B R0 and such that ϕ 1 ≡ 1 in a neighbourhood of supp ϕ 1 . Finally, let ϕ tr ∈ C ∞ comp (R d ; [0, 1]) be as in §5.1; i.e., equal to one on the support of ϕ tr and so that supp ϕ tr ⊂ B R1(1+3δ) ; see Figure 5 Starting from the definition v High := Π High ϕ tr v (5.11), using that ϕ 0 + ϕ 1 = 1, the first and third support properties in (5.28), Lemma 3.5, and that ϕ 0 ϕ tr = ϕ 0 , we obtain that

v High = Π High ϕ 0 ϕ tr v + Π High ϕ 1 ϕ tr v = Π High ϕ 0 ϕ tr v + ϕ 1 Π High ϕ 1 ϕ tr v + O( ∞ ) D ,∞ ϕ tr v = Π High ϕ 0 ϕ tr v + ϕ tr ϕ 1 Π High ϕ 1 ϕ tr v + O( ∞ ) D ,∞ ϕ tr v = Π High ϕ 0 v + ϕ tr ϕ 1 Π High ϕ 1 ϕ tr v + O( ∞ ) D ,∞ ϕ tr v =: v High,near + v High,far + O( ∞ ) D ,∞ ϕ tr v.
(5.29)

Remark 5.6 (The decomposition of v High ) This decomposition of v High into "near" and "far" components is different from the non-truncated case in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]. The reason we do it is we want the function to which Π High is applied in v High,near to be supported away from the scaling region (i.e., supported where P = P ,θ ) -see (5.32)

on v High,far using ideas from Steps 2 and 3 (in a simplified setting).

Step 1: An abstract argument in H to bound v High,near . Since Π High commutes with P (by Part 1 of Theorem 3.4) and P = P ,θ on supp ϕ 0 ⊂ B R0 ,

(P -I)Π High (ϕ 0 v) = Π High (P -I)(ϕ 0 v) = Π High (P ,θ -I)(ϕ 0 v) = Π High ϕ 0 g + Π High [P ,θ , ϕ 0 ]v = Π High ϕ 0 g + Π High [P , ϕ 0 ]v. (5.32)
(Note that, strictly speaking, we should be writing the commutator [P ,θ , ϕ 0 ] as [P ,θ , M ϕ0 ], where multiplication is defined in the black-box setting by (3.6); however, we abuse this notation slightly for simplicity.) For λ ∈ R, let

f (λ) := (λ -1) -1 (1 -ψ µ )(λ),
and observe that f ∈ C 0 (R) (defined by (4.1)) by the second property in (5.2). Using (5.9), the fact that the Borel calculus is an algebra homomorphism (Part 1 of Theorem 3.4), and finally (5.32), we get Π High (ϕ 0 v) = Π High Π High (ϕ 0 v) = f (P )(P -I)Π High (ϕ 0 v) = f (P ) Π High ϕ 0 g + Π High [P , ϕ 0 ]u .

(5.33) Since f ∈ C 0 (R), f (P ) is uniformly bounded from H → H by Part 3 of Theorem 3.4. Combining this fact with (5.33), we obtain

Π High (ϕ 0 v) H Π High (ϕ 0 g) H + Π High [P , ϕ 0 ]v H .
Writing P Π High = Π High + (P -I)Π High and using (5.32) again, we obtain

Π High (ϕ 0 v) H + P Π High (ϕ 0 v) H Π High (ϕ 0 g) H + Π High [P , ϕ 0 ]v H .
Hence, by (5. We now seek to convert the P v High,near H on the left-hand side of this last bound into P ,θ v High,near H using that P = P ,θ on supp ϕ 0 and pseudolocality of the functional calculus. With ϕ 0 ∈ C ∞ comp (R d ; [0, 1]) defined as above, the definition of v High,near (5.29), the second support property in (5.28), and Lemma 3.5 then imply that

v High,near = ϕ 0 Π High,θ (ϕ 0 v) + O( ∞ ) D ,∞ ϕ 0 v. and thus S[ Q ,θ , χ] = O( ∞ ) Ψ -∞ .
Using this in (5.50) and then taking the H 2 (T d R ) norm, using the definitions of O( ∞ ) Ψ -∞ and O( ∞ ) D ,∞ , we obtain that, given N > 0 there exists C N > 0 such that

ϕ 1 ϕ tr Π Ψ High ϕ 1 ϕ tr v H 2 (T d R ) S χg H 2 (T d R ) + C N N χ alt v L 2 (T d R )
where χ alt is compactly supported in B R \ B R0 and equal to one on a neighbourhood of supp χ. By Part (iii) of Theorem A.1, and the fact that S ∈ Ψ -2 (T d R ),

ϕ 1 ϕ tr Π Ψ High ϕ 1 ϕ tr v H 2 (T d R ) g H + C N N v H(Ωtr) .
The

∞ = O( ∞ ) D ,∞ with
E(P ) = E + E ∞ , (5.51)
and the low-frequency estimate (4.4) holds. By (5.6) (a consequence of the definition of the constant Λ (5.5)), E is nowhere zero on the support of ψ µ ; therefore the function ψ µ /E is well-defined and in C 0 (R) (defined by (4.1)). The definition of Π Low (5.7) and Part 1 of Theorem 3.4 imply that We first assume that ρ = 1 and establish the decomposition (5.15), together with the bounds (4.14) and (4.15) on u A . In this case, we let

Π Low = ψ µ (P ) = E(P ) 1 E ψ µ (P ) = E • 1 E ψ µ (P ) + E ∞ • 1 E ψ µ (P ) . ( 5
E ∞ = O( ∞ ) D ,∞ , E ∞ • 1 E ψ µ (P ) = O( ∞ ) D ,∞ . (5
v A := E • 1 E ψ µ (P ) ϕ tr v, (5.54)
so that (5.15) holds by (5.52) and (5.53). Moreover, since v A involves a compactly-supported function of P , by the reasoning below (5.10), v A ∈ D ,∞ . Then, using (in this order) the lowfrequency estimate (4.4), Part 3 of Theorem 3.4, and finally the resolvent estimate (5.19), we get

D(α)v A H = D(α)E • 1 E ψ µ (P ) ϕ tr v H ≤ C E (α, ) 1 E ψ µ (P )ϕ tr v H ≤ C E (α, ) sup λ∈R 1 E(λ) ψ µ (λ) ϕ tr v H = C E (α, ) sup λ∈R 1 E(λ) ψ µ (λ) ϕ tr v H(Ωtr) C E (α, ) sup λ∈R 1 E(λ) ψ µ (λ) -M -1 g H(Ωtr) ; R 0 R I R II R III R 1 γ 1 ρ 1 γ 2 ρ 2 R 1 (1 + 2δ) R 1 (1 + 3δ)
v D ,m ((B R 1 (1+ ) ) c ) ≤ (1 -ϕ tr )v D ,m , (5.55
-ϕ tr )E • 1 E ψ µ (P ) ϕ tr = (1 -ϕ tr )E(P ) 1 E ψ µ (P )ϕ tr + O( ∞ ) D ,∞ = (1 -ϕ tr )ψ µ (P )ϕ tr + O( ∞ ) D ,∞ = O( ∞ ) D ,∞ . 1
The bound (4.15) then follows by combining this with (5.55) and the resolvent estimate (5.19).

Remark 5.11 (The decomposition is independent of E if E ∞ = 0) The last part of Theorem 4.1 is the claim that when E ∞ = 0, the decomposition is independent of E. To establish this in the case ρ = 1, observe that (5.54) and (5.52) imply that if E ∞ = 0, then v A = v Low = ψ µ (P )ϕ tr v (which is independent of E).

Cut-off functions for the case ρ = 1

We first define the cut-off functions used to bound v Low , displayed in Figure 5.3. Whereas the cut-off functions used in the bound on v High (in §5.3) were denoted ϕ, φ, and χ (sometimes with tildes), in this section we use the notation ρ j and γ j , j = 1, 2. Recall that ρ is the cut-off function in the assumption (4.4). Given R 0 , R 1 , and ρ, let

R I , R II , R III , R IV , be such that R 0 < R I < R II < R III < R IV < R 1 and ρ = 1 on a neighbourhood of B R IV . Let ρ 1 ∈ C ∞ comp (T d R ; [0, 1]) be such that supp(1 -ρ 1 ) ⊂ (B R II ) c and supp ρ 1 B R III Let ρ 2 ∈ C ∞ comp (T d R ; [0, 1]) be supported in B R III and such that ρ 2 ≡ 1 on supp ρ 1 , i.e., supp(1 -ρ 2 ) ∩ supp ρ 1 = ∅. (5.56) Let γ 1 ∈ C ∞ (T d R ; [0, 1]) be such that γ 1 ≡ 0 on a neighbourhood of B R0 , such that γ 1 ≡ 1 on a neighbourhood of B R1(1+2δ) \ B R I , and γ 1 ≡ 0 on (B R1(1+3δ) ) c . A key feature of this definition is that supp (1 -γ 1 ) ∩ supp (1 -ρ 1 )ϕ tr = ∅. (5.57) Finally, let γ 2 ∈ C ∞ (T d R ; [0, 1
]) be equal to zero on B R II and such that γ 2 ≡ 1 on supp(1 -ρ 1 ); i.e., supp (1 -γ 2 ) ∩ supp 1 -ρ 1 ) = ∅.

(5.58) 5.4.4 Decomposing into parts that are "near to" or "far from" the black box when ρ = 1

We split v Low in the following way, using the pseudo-locality of the functional calculus (i.e., Lemma 3.5) and the support properties (5.56) and (5.57),

v Low := ψ µ (P )ϕ tr v = ψ µ (P )ρ 1 ϕ tr v + ψ µ (P )(1 -ρ 1 )ϕ tr v v Low := Π Low ϕ tr v v Low,near := Π Low ρ 1 ϕ tr v v Low,far := γ 1 Π Low (1 -ρ 1 )ϕ tr v O( ∞ ) D ,∞ ϕ tr v O( ∞ ) D ,∞ ϕ tr v v A,near := E • 1 E ψ µ (P ) ρ 1 v
v + γ 1 ψ µ (P )(1 -ρ 1 )ϕ tr v + O( ∞ ) D ,∞ ϕ tr v =: v Low,near + v Low,far + O( ∞ ) D ,∞ ϕ tr v.
We now split v Low,near and v Low,far further, with this decomposition summarised in Figure 5.4. We highlight that the arguments from here on are identical to the corresponding arguments in [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF] (in [29, §3.3.3- §3.3.4]).

The part near the black-box v Low,near

By (5.52), and (5.53), along with the fact that ρ

1 ϕ tr = ρ 1 , v Low,near = ψ µ (P )ρ 1 v = E • 1 E ψ µ (P ) ρ 1 v + O( ∞ ) D ,∞ ϕ tr v =: v A,near + O( ∞ ) D ,∞ ϕ tr v.
(5.59)

Since v A,near involves a compactly-supported function of P by the reasoning below (5.10) v A,near is in D ,∞ .

Remark 5.12 (The decomposition is independent of E if E ∞ = 0) The last part of Theorem 4.1 is the claim that the decomposition is independent of E if E ∞ = 0. To establish this when ρ = 1, observe that the only part of the definition of the decomposition where E enters is in the decomposition v Low,near = v A,near +O( ∞ ) D ,∞ v. Furthermore, if E ∞ = 0, then, by (5.52) and (5.59), we can define v A,near := ψ µ (P )ρ 1 v (which is independent of E) and have v Low,near = v A,near .

Proof of (4.9) and (4.10) for v A,near . Using (in this order) the definition of v A,near (5.59), the fact that ρ = 1 on B R IV , the low-frequency estimate (4.4), Part 3 of Theorem 3.4, and finally the resolvent estimate (5.19) we obtain

D(α)v A,near H (B R IV ) ≤ ρD(α)E • 1 E ψ µ (P ) ρ 1 v H ≤ C E (α, ) 1 E ψ µ (P ) ρ 1 v H We let v A,far := γ 1 Op T d R ( ϕ(|ξ| 2 ))Π Ψ Low γ 1 (1 -ρ 1 )ϕ tr v, (5.67)
so that the combination of (5.61), (5.66), and (5.67) implies that

v Low,far = v A,far + O( ∞ ) D ,∞ ϕ tr v.
Observe that v A,far ∈ D(Ω tr ) because of the presence of γ 1 at the start of the expression (which causes v A,far to be zero on Γ tr ).

Step 2: proving that v A,far is regular in (B R I ) c (i.e., the bound (4.11)). By the definition of v A,far (5.67) and the fact that

γ 1 = 1 on (B R I ) c , ∂ α v A,far H((B R I ) c ) = ∂ α Op T d R ( ϕ(|ξ| 2 ))Π Ψ Low γ 1 (1 -ρ 1 )ϕ tr v H((B R I ) c ) ≤ ∂ α Op T d R ( ϕ(|ξ| 2 ))Π Ψ Low γ 1 (1 -ρ 1 )ϕ tr v L 2 (T d R )
.

(5.68)

We now bound the right-hand side of (5.68). By Lemma A.3, Op

T d R ( ϕ(|ξ| 2
)) is given as a Fourier multiplier on the torus (defined by (A.11)), i.e., Op

T d R ( ϕ(|ξ| 2 )) = ϕ(-2 ∆).
(5.69)

Let w ∈ L 2 (T d R ) be arbitrary, and let w(j) be the Fourier coefficients of w. By (A.11),

ϕ(-2 ∆)w = j∈Z d w(j) ϕ( 2 |j| 2 π 2 /R 2 )e j ,
where the normalised eigenvectors e j are defined by (A.1). Hence, for any multi-index α,

∂ α ϕ(-2 ∆)w = j∈Z d w(j) ϕ( 2 |j| 2 π 2 /R 2 ) iπj R α e j = j∈Z d , |j|≤ λR π w(j) ϕ( 2 |j| 2 π 2 /R 2 ) iπj R α e j ,
since ϕ is supported in B(0, λ 2 ). Therefore

∂ α ϕ(-2 ∆)w 2 L 2 (T d R ) = j∈Z d , |j|≤ λR π w(j) ϕ( 2 |j| 2 π 2 /R 2 ) iπj R α 2 ≤ λ 2|α| -2|α| j∈Z d | w(j)| 2 = λ 2|α| -2|α| w 2 L 2 (T d R ) .
(5.70)

We now use (5.70) with w := Π Ψ Low γ 1 (1 -ρ 1 )ϕ tr v, and combine the resulting estimate with (5.68) and (5.69). Using the fact that Π Ψ Low ∈ Ψ ∞ (T d R ), γ 1 = 0 on a neighbourhood of B R0 , and the resolvent estimate (5.19), we get

∂ α v A,far H((B R I ) c ) ≤ λ |α| -|α| Π Ψ Low γ 1 (1 -ρ 1 )ϕ tr v L 2 (T d R )
λ The bound (1.20) on v A follows immediately from (4.14). The bound (1.19) on v H 2 follows from (4.7) after using (i) Green's identity and Lemma 2.3 to obtain a bound on the H 1 semi-norm, and then (ii) Lemma 2.3 and H 2 regularity (when Γ tr is C 1,1 by, e.g., [START_REF] Grisvard | Elliptic problems in nonsmooth domains[END_REF]Theorem 2.4.2.5] and when Ω tr is convex by, e.g., [START_REF] Grisvard | Elliptic problems in nonsmooth domains[END_REF]Theorem 3.1.3.1]).

Sketch proof of Theorem 1.17

Theorem 1.17 is based on the following result, which is Theorem 4.1 specialised to the case when the regularity estimate inside the black box comes from a heat flow estimate. Given > 0, there exist 1 > 0, C j > 0, j = 1, 2, 3, and λ > 1 such that for all R tr > (1 + )R 1 , B Rtr ⊂ Ω tr R d with Lipschitz boundary, < θ < π/2 -, all g ∈ H(Ω tr ), and all ∈ H ∩ (0, 1 ], the following holds. The solution v ∈ D(Ω tr ) to (P ,θ -I)v = g on Ω tr and v = 0 on Γ tr exists and is unique and there exists v H 2 ∈ D(Ω tr ), v A ∈ D ,∞ and v residual ∈ D ,∞ such that C(α, , t)e Λt -M -1 g H(Ωtr) for all ∈ H∩(0, 1 ], α ∈ A, (6.4) and, for any N, m > 0 there exists C N,m > 0 (independent of θ) such that (4.10) holds and v A,far ∈ D(Ω tr ) is entire away from the black-box and negligible near it, in the sense that (4.11) holds and, for any N, m > 0 there exists C N,m > 0 (independent of θ) such that (4.12) holds. Finally, v residual ∈ D ,∞ is negligible in the sense that for any N, m > 0 there exists C N,m > 0 (independent of θ) such that (4.13) holds.

v = v H 2 + v A + v residual
The proof of Corollary 6.1 is identical to the proof of [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]Corollary 4.1]; since the proof is so short, however, we include it for completeness.

Proof of Corollary 6.1. For α ∈ A and ∈ H, let t ∈ I( , α), and E t (λ) := e -t|λ| . Since P ≥ a( ) > 0, Sp P ⊂ [a( ), ∞). Therefore, by Parts 4 and 3 of Theorem 3.4, e -tP = E t (P ). Such an E t is in C 0 (R), never vanishes, and satisfies (4.4) with E t := E t (P ) and C Et (α, ) := C(α, , t) by (6.3). From Theorem 4.1, we therefore obtain the above decomposition v A , v A,near , v A,far , v H 2 . Since E t (P ) = E t (i.e., E ∞ = 0), by the final part of Theorem 4.1, the decomposition is constructed independently of E t , and hence independently of t. The result then follows, with the infimum in t in (6.4) coming from (4.9) and the fact that this estimate in valid for any t ∈ I( , α).

Theorem 1.17 is proved using Corollary 6.1 with the following heat-flow estimate as (6.3). Theorem 6.2 (Heat equation estimate from [START_REF] Escauriaza | Analyticity of solutions to parabolic evolutions and applications[END_REF]) Suppose that Assumption 1.11 holds with A scat and c scat analytic in B R * for some R 0 < R * < R scat . Let P denote the associated black-box reference operator on the torus (as described in §3.1).

Given ρ ∈ C ∞ comp (R d ; [0, 1]) with supp ρ ⊂ B R * , there exists C > 0 such that for all t ∈ (0, 1] and for all τ ∈ [0, 1] ρ∂ α e t -2 P L 2 →L 2 ≤ exp(t -τ )|α|! C |α| t (τ -1)|α|/2 . (6.5)

References for the proof of Theorem 6.2. Since the operator e t -2 P is just the variable coefficient heat operator for time t, the estimate (6.5) can be extracted from the heat equation bounds in [START_REF] Escauriaza | Analyticity of solutions to parabolic evolutions and applications[END_REF] We therefore apply Corollary 6.1 to the specific set up in §6.1, noting that the heat-flow estimate (6.3) is then satisfied with D(α) := ∂ α , C(α, , t) := exp ( 2 t) -τ |α|! C |α| 2 t) (τ -1)|α|/2 , and I( , α) := (0, -2 ] (the heat-flow given by the functional calculus, appearing in (6.3), is indeed the solution of the heat equation; see, e.g., [START_REF] Reed | Methods of Modern Mathematical Physics Volume 1: Functional analysis[END_REF]Theorem VIII.7]).

To obtain Theorem 1.17 from Corollary 6.1, we then only need to show that (i) v H 2 satisfies (1.22), and (ii) v A,near satisfies (1.23). The proof of (i) is identical to the proof that v H 2 in Theorem 1.16 satisfies (1.19). For (ii), we carefully choose t and τ as functions of |α| and to obtain (1.23); for the details, see [29, §4.1]. To deal uniformly near fiber-infinity with the behavior of functions on phase space, we also consider the radial compactification in the fibers of this space,

A Semiclassical pseudodifferential operators on the torus

Theorem 1 . 3 (

 13 Conditions under which the solution operator is polynomially bounded) Suppose Ω -, A scat , and c scat are as in Definition 1.1.

Remark 1 . 4 (

 14 r) ≥ 0, our results hold for an f with f | [0,R] = f . Link with other notation used in the literature) In (1.5)-(1.8

Assumption 1 .

 1 10 (i) Ω -= ∅. (ii) A scat and c scat are as in Definition 1.1. (iii) Either Γ tr is C 1,1 or Ω tr is convex. Assumption 1.11 (i) Ω -, A scat , and c scat are as in Definition 1.1.

Lemma 1 .

 1 14 (k-explicit analyticity) With D a bounded open set, let u ∈ C ∞ (D) be a family of functions depending on k.

2

 2

Definition 2 . 6 (

 26 Adjoint solution operator S * ) Given f ∈ L 2 (Ω), let S * f be defined as the solution of the variational problem find S

Lemma 2 . 10 (

 210 Bound on η(V N ) under Assumption 1.10 or 1.11) Suppose that Ω -, A scat , and c scat satisfy either Assumption 1.10 or 1.11. Suppose further that Ω -, A scat , c scat , and K ⊂ [k 0 , ∞) are such that the solution operator of the exterior Dirichlet problem is polynomially bounded (in the sense of Definition 1.2).

29 ,

 29 Lemma 5.5], which uses the results [53, Theorem 5.5] and [54, Proposition 5.3]. The only difference between the present set up and [29, Lemma 5.5] is that here we

Lemma 3 . 5 (

 35 for any N > 0 and any m > 0, there exists C N,m > 0 such thatE ∞ D ,-m →D ,m ≤ C N,m N(compare to (A.4) below). Operators in the functional calculus are pseudo-local in the following sense. Pseudolocality) Suppose f ∈ A is independent of , and ψ 1 , ψ 2 ∈ C ∞ (T d R ) are constant near B R0 . If ψ 1 and ψ 2 have disjoint supports, thenψ 1 f (P )ψ 2 = O( ∞ ) D ,-∞ →D ,∞ .(3.14)Proof. On a smooth manifold with boundary, this result follows from the fact that f (P ) is a pseudodifferential operator, and hence pseudo-local. Here, it follows from combining the corresponding result about the resolvent [61, Lemma 4.1] (i.e.,(3.14) with f (w) := (w -z) -1 )) with (3.13) and then integrating (as discussing in a slightly different context in [61, Paragraph after proof of Lemma 4.2]).

Definition 3 . 7 (

 37 Black-box differentiation operator) (D(α)) α∈A is a family of black-box differentiation operators on D ,∞ (defined by (3.12)) if A is a family of d-multi-indices, and for any α and any

  Figures 5.1 and 5.4). The estimates (4.7) and (4.9)-(4.14) are proved in §5.3 and 5.4 respectively.

Theorem 5 . 3 (

 53 Simplified version of[START_REF] Galkowski | Perfectly-matched-layer truncation is exponentially accurate at high frequency[END_REF] Theorem 1.6]) Suppose Point 1 in Theorem 4.1 holds; i.e., the solution operator of the black-box problem is polynomially bounded for ∈ H. Given > 0, there exist C, 0 > 0 such that the following holds. For all R tr > R 1 (1 + ), B Rtr ⊂ Ω tr R d with Lipschitz boundary, < θ < π/2 -, all g ∈ H with supp g ⊂ Ω tr , and all ∈ H ∩ [0, 0 ], the solution v to (P ,θ -I)v = g in Ω tr and v = 0 on Γ tr (i.e., (4.5)) exists, is unique, and satisfies v H(Ωtr) + P ,θ v H(Ωtr) ≤ C -M -1 g H(Ωtr) .(5.[START_REF] Douglas | Frequency domain treatment of one-dimensional scalar waves[END_REF]

2 v

 2 torus v PML := (1 -ϕ tr )v v Low low-frequency part v High high-frequency part ϕ tr v High v H A,far negligible near BR 0 entire away from BR 0 v A,near regular near BR 0 negligible away from BR 0

Figure 5 . 1 :Lemma 5 . 4 (

 5154 Figure 5.1: Decomposition of the PML solution described in §5.1 (when ρ = 1 in (4.4))

Lemma 5 . 5 (

 55 Simplified version of [28, Lemma 4.2, Equation

Figure 5 . 2 :

 52 Figure 5.2: The cut-off functions ϕ 0 , ϕ 0 , ϕ 1 , ϕ 1 , ϕ tr , and ϕ tr described at the start of §5.3.

  .2. (Observe then that a tilde denotes a function with larger support than the corresponding function without the tilde.) These definitions imply the following support properties supp(1-ϕ tr )∩supp ϕ tr = ∅, supp(1-ϕ 0 )∩supp ϕ 0 = ∅, and supp(1-ϕ 1 )∩supp ϕ 1 = ∅. (5.28)

. 52 )

 52 Then, by Part 3 of Theorem 3.4 and the fact that

.53) 5 . 4 . 2

 542 The decomposition (5.15) of v Low when ρ = 1 in (4.4)

Figure 5 . 3 :

 53 Figure 5.3: The cut-off functions ρ 1 , ρ 2 , γ 1 , γ 2 defined at the start of §5.4.

  ) since ϕ tr ≡ 0 on (B R1(1+ ) ) c . Then by (5.51), (5.53), Part 1 of Theorem 3.4, pseudo-locality of the functional calculus (Lemma 3.5), and the first support property in (5.28), (

0 Figure 5 . 4 : 6 =

 0546 Figure 5.4: The decomposition of v Low when ρ = 1, described in §5.4.4- §5.4.6

  |α| -|α| γ 1 (1 -ρ 1 )ϕ tr v L 2 (T d R ) = λ |α| -|α| γ 1 (1 -ρ 1 )ϕ tr v H ≤ λ |α| -|α| -M -1 g H(Ωtr) ; hence (4.11) holds. so that if E := ϕ(-2 ∆)E(P ) then E(P ) = E + O( ∞ ) D ,-∞ →D ,∞ .(6.2)We now need to show that an estimate of the form (4.4) is satisfied. Since ϕ is compactly supported in B(0, Λ 2 0 ), the definition of E (6.2) and the same argument used to show the bound (5.70) imply that∂ α Ev L 2 (T d R ) ≤ Λ |α| 0 -|α| E(P v) L 2 (T d R )for all v ∈ L 2 (T d R ) and multi-indices α. Then, since E(P ) ∈ Ψ -∞ (T d R ), Part (iii) of Theorem A.1 implies that there exists C > 0 such that∂ α Ev L 2 (T d R ) ≤ CΛ |α| 0 -|α| v L 2 (T d R ) for all v ∈ L 2 (T d R )and multi-indices α. Therefore, the assumption in Point 2 of Theorem 4.1 is satisfied with D(α) := ∂ α , C E (α, ) := CΛ |α| 0 -|α| and ρ = 1.

Corollary 6 . 1

 61 Let P be a semiclassical black-box operator on H satisfying the polynomial resolvent estimate (4.2) in H ⊂ (0, 0 ]. Assume further that (i) P ≥ a( ) > 0 for some a( ) > 0, and (ii) for some α-family of black-box differentiation operators (D(α)) α∈A (Definition 3.7), there exists ρ ∈ C ∞ (T d R ) equal to one near B R0 such that, for some family of subsets I( , α) ⊂ [0, +∞), the following localised heat-flow estimate holds, ρD(α)e -tP H →H ≤ C(α, t, ) for all α ∈ A, t ∈ I( , α), ∈ H.(6.3)

and v H 2

 2 , v A , and v residual satisfy the following properties. The component vH 2 ∈ D(Ω tr ) satisfies (4.7). There exist R I , R II , R III , R IV with R 0 < R I < R II < R III < R IV < R 1 such that v A ∈ D ,∞ decomposes as v A = v A,near + v A,far ,where v A,near ∈ D is regular near the black-box and negligible away from it, in the sense thatD(α)v A,near H (B R IV ) ≤ C 2 inf t∈I( ,α)

2 H

 2 Recall that for R > 0, T d R := R d /(2R Z) d . This appendix reviews the material about semiclassical pseudodifferential operators on T d R used in §5.3- §5.[START_REF] Bayliss | Radiation boundary conditions for wave-like equations[END_REF], and appearing in Lemma 3.6, with our default references being[START_REF] Zworski | Semiclassical analysis[END_REF] and[START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF] Appendix E].Semiclassical Sobolev spaces. We consider functions or distributions on the torus as periodic functions or distributions on R d . To eliminate confusion between Fourier series and integrals, for f ∈ L 2 (T d R ) we define the Fourier coefficientsf (j) := T d R f (x)e j (x) dx,where j ∈ Z d and the integral is over the cube of side 2R , and where the Fourier basis given by the L 2 -normalized functionse j (x) = (2R ) -d/2 exp iπj • x/R (A.1)for j ∈ Z d . The Fourier inversion formula is thenf = j∈Z d f (j)e j ,and the action of the operator ( D) α on the torus is therefore( D) α f = j∈Z d ( j) α f (j)e j .We work on the spaces defined by the boundedness of these operators, namelyH m (T d R ) := u ∈ L 2 (T d R ), j m f (j) ∈ 2 (Z d ) ,with the normu m (T d R ) := | f (j)|2 j 2m ; (A.2) see [70, §8.3], [21, §E.1.8]. In this appendix, we abbreviate H m (T d R ) to H m and L 2 (T d R ) to L 2. Since these spaces are defined for positive integer m by boundedness of (hD) α with |α| = m (and can be extended to m ∈ R by interpolation and duality), they agree with localized versions of the corresponding spaces on R d defined by semiclassical Fourier transformF u(ξ) := R d exp -ix • ξ/ u(x) dx, and u 2 H m (R d ) := (2π ) -d R d ξ m |F u(ξ)| 2 dξ.Phase space. The set of all possible positions x and momenta (i.e. Fourier variables) ξ is denoted by T * T d R ; this is known informally as "phase space". Strictly, T * T d R := T d R × (R d ) * , but for our purposes, we can consider T * T d R as {(x, ξ) : x ∈ T d R , ξ ∈ R d }. We also use the analogous notation for T * R d where appropriate.

  R d × B d , where B d denotes the closed unit ball, considered as the closure of the image of R d under the radial compactification map RC : ξ → ξ/(1 + ξ ); see [21, §E.1.3]. Near the boundary of the ball, |ξ| -1 • RC -1 is a smooth function, vanishing to first order at the boundary, with (|ξ| -1 • RC -1 , ξ • RC -1 ) thus furnishing local coordinates on the ball near its boundary. The boundary of the ball should be considered as a sphere at infinity consisting of all possible directions of the momentum variable. Where appropriate (e.g., in dealing with finite values of ξ only), we abuse notation by dropping the composition with RC from our notation and simply identifying R d with the interior of B d . Symbols, quantisation, and semiclassical pseudodifferential operators. A symbol on R d is a function on T * R d that is also allowed to depend on , and thus can be considered as an -dependent family of functions. Such a family a = (a ) 0< ≤ 0 , with a ∈ C ∞ (R d ), is a symbol of order m on the R d , written as a ∈ S m (R d ), if for any multi-indices α, β |∂ α x ∂ β ξ a(x, ξ)| ≤ C α,β ξ m-|β| for all (x, ξ) ∈ T * R d and for all 0 < ≤ 0 , where C α,β does not depend on ; see [70, p. 207], [21, §E.1.2].

  If P is the Dirichlet Laplacian with Γ D ∈ C 1,1 and either Γ tr ∈ C 1,1 or Ω tr is convex, then P θ v H 2 L 2 controls v H 2 H 2 up to v H 2 L 2 byelliptic regularity, and thus the bound in (i) is a bound on v H 2 H 2 -hence the notation v H 2 . (Assumptions 1.10 and 1.11 contain these assumptions on Γ D and Γ tr precisely to ensure this H 2 regularity of v H 2 .)

	1.15 for outgoing Helmholtz solutions; see [29, Theorem A ].
	The conclusions of Theorem 1.15 are essentially the same as those [29, Theorem A ], except
	with u replaced by v, P replaced by P θ , and the addition of the "residual" term v residual (the
	reason why this residual term appears here, but not in [29, Theorem A ], is to make v H 2
	satisfy the zero Dirichlet boundary condition on Γ tr -see the discussion after Theorem 4.1).
	•

Table 1 . 1 :

 11 Summary of the decomposition results in the papers

	Paper	Helmholtz equation	Problem	Freq. cut-offs	Freq. cut-offs	Proof of bound	Proof of bound
				defined by	applied to	on HF part	on LF part
	[53]	∆u + k 2 u = -f	in R d with SRC	Fourier transform on R d	data	asymptotics of	asymptotics of
				with sharp cut-off		Bessel/Hankel	Bessel/Hankel
						functions	functions
	[54]	∆u + k 2 u = -f	EDP obstacle analytic	as in [53] plus	data	bounds on	analytic estimate
			IIP convex polygon	extension operators		cut-offs from [53]	on Helm. solutions
			or smooth				with analytic data
	[26]	∆u + k 2 u = -f	IIP convex polygon	as in [53] plus	data	bounds on	analytic estimate
				extension operators		cut-offs from [53]	on Helm. solutions
							with analytic data
	[43]
							from FT
	[29]	equations that are	any problem	functional calculus	solution	semiclassical ellip.	abstract regularity
	(general	∆u + k 2 u = 0	fitting in framework	(i.e., eigenfunction	× spatial cut-off	pseudo. prop.	estimate in
	result)	outside large ball	of black-box scattering	expansion),		of func. calc.	black box
				smooth cut-off
	[29]	∇ • (A∇u) + k 2 cu = -f	EDP obstacle analytic	functional calculus,	solution	semiclassical ellip.	heat-flow
	(specific		A, c analytic near obstacle	smooth cut-off	× spatial cut-off	pseudo. prop.	estimate
	result)					of func. calc.
				functional calculus,	solution	semiclassical ellip.	heat-flow
	paper	+ PML truncation	or EDP obstacle analytic	smooth cut-off	× spatial cut-off	pseudo. prop.	estimate
			A, c analytic near obstacle		supported	of func. calc.
					into PML region

2 for |ξ| ≥ λ; ∇ • (A∇u) + k 2 cu = -f in R d with SRC Fourier transform on R d solution semiclassical ellip. immediate A, c smooth smooth cut-off × spatial cut-off of Helmholtz on HF this ∇ • (A∇u) + k 2 cu = -f either A, c smooth, no obs.

  A wide variety of scattering problems fit in the black-box framework; see [21, §4.1], [29, §2.2]. The present paper only uses that the exterior Dirichlet problem of Definition 1.1 fits in this framework. Lemma 3.2 (Scattering by a Dirichlet obstacle in the black-box framework) Let Ω -, A scat , c scat , R 0 , and R scat be as in Definition 1.1. Then the family of operators

  .21) 5.2.2 Proof of the bound(5.14) on v PML Since v PML := (1 -ϕ tr )v, (P ,θ -I)v PML = (P ,θ -I)(1 -ϕ tr )v = (1 -ϕ tr )g + [P ,θ , ϕ tr ]v,(5.22)and the fact that ϕ tr ≡ 1 on B R1+δ implies that supp v PML ⊂ Ω tr \ B R1+δ . Thus, applying Lemma 5.4 with ε = min{ , δ}, we see that the bound (5.20) implies thatv PML H 1 (Ωtr\B R 1 +δ ) (P ,θ -I)v PML L 2 (Ωtr) g H(Ωtr) + [P ,θ , ϕ tr ]v L 2 (Ωtr) . Now, by direct computation and the fact that supp∇ϕ tr ⊂ B R1+2δ \ B R1+δ , [P ,θ , ϕ tr

  + [P ,θ , ϕ tr ]v L 2 (Ωtr) + v PML L 2 (Ωtr) , and combining this with (5.23) and (5.24) (and recalling that supp v PML ⊂ Ω tr \ B R1+δ ) we find that v PML H(Ωtr) + P ,θ v PML H(Ωtr) g H(Ωtr) + v H 1 (B R 1 +2δ \B R 1 +δ ) . (5.25) Our plan is to use the Carleman estimate (5.21) to bound this last term in terms of g H(Ωtr) . We first claim that (5.19) implies that

		.24)
	Using (5.22) again, we have
	P ,θ v PML H(Ωtr)	g H(Ωtr)

  below. The component v High,far can then be dealt with via Lemma 3.6 (since it involves cut-offs supported away from the black box) and semiclassical ellipticity; see Step 4 below. High,near and are the analogues of Steps 1-3 in [29, §3.2] that deal with u High (although Step 1 is more involved because of the presence of the two operators P and P ,θ as opposed to just P ). Step 4 obtains the bound v High,far H + P ,θ v High,far H g H(Ωtr) ,

	Overview of the rest of the proof of (5.13). We proceed in four steps; Steps 1-3 obtain the
	bound
	v High,near H + P ,θ v High,near H	g H(Ωtr) ,	(5.30)
	on v

  bound (5.31) on v High,far := ϕ tr ϕ 1 Π High ϕ 1 ϕ tr v then follows by combining this last inequality with the resolvent estimate (5.19). 5.4 Proof of the decomposition (5.16) of v Low (the low-frequency component) and associated bounds on v A,near and v A,far 5.4.1 Decomposing Π Low using Assumption 2 in Theorem 4.1 By Assumption 2 in Theorem 4.1, there exists E

  , Theorem 1.1 and Lemma 2.7]; see [29, Proof of Theorem 4.3] for more detail.

The expository paper[START_REF] Spence | A simple proof that the hp-FEM does not suffer from the pollution effect for the constantcoefficient full-space Helmholtz equation[END_REF] shows that a frequency cut-off defined by an indicator function can nevertheless be used in the constant-coefficient case; this is because Fourier multipliers can be formulated without any differentiability requirements on the symbols. The paper[START_REF] Spence | A simple proof that the hp-FEM does not suffer from the pollution effect for the constantcoefficient full-space Helmholtz equation[END_REF] gives an alternative proof of the decomposition result in[START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF] using just elementary properties of the Fourier transform and integration by parts (in particular, without any of the Bessel/Hankel-function asymptotics used in[START_REF] Melenk | Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions[END_REF]).

In fact, we could modify the arguments below to work for R > R 1 only, since we just need supp ϕtr contained inside B R .

We highlight that working in a compact manifold allows us to dispense with the proper-support assumption appearing in[43, §4],[START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF] Proposition E.32, Theorem E.33].

Acknowledgements

JG acknowledges support from EPSRC grants EP/V001760/1 and EP/V051636/1. EAS acknowledges support from EPSRC grant EP/1025995/1. JW was partially supported by Simons Foundation grant 631302, NSF grant DMS-2054424, and a Simons Fellowship.

The decomposition

Definition of the frequency cut-offs. Let ψ ∈ C ∞ comp (R; [0, 1]) be such that supp ψ ⊂ [-2, 2] and ψ ≡ 1 on [-1, 1]. For µ, µ > 0, let

We now assume that µ > 2 and choose µ as a function of µ so that (1 -ψ µ )(1 -ψ µ ) = (1 -ψ µ ) and 1 / ∈ supp(1 -ψ µ ); (5.2) these two conditions are ensured if 1 ≤ µ ≤ µ/2 (hence the assumption that µ > 2).

Choice of the parameter µ. We now impose additional conditions on µ. By (3.5), there exists µ 0 such that if µ ≥ µ 0 , then (x, ξ) : |q (x, ξ)| ≥ µ = (x, ξ) : q (x, ξ) ≥ µ .

(

We then choose µ ≥ max{µ 0 , µ 1 }, where µ 1 is given by the following lemma.

Lemma 5.1 (Semiclassical ellipticity of Q and Q ,θ for µ large enough) Given > 0, there exists µ 1 > 2 and c ell > 0 such that if µ ≥ µ 1 then the following hold.

(i) If q (x, ξ) ≥ µ, then ξ -2 (q (x, ξ) -1) ≥ c ell > 0 (5.4) (i.e., Q -1 is semiclassically elliptic in this region of phase space).

(ii) If ≤ θ ≤ π/2 -, x ∈ B R1(1+3δ) \ B R0 , and q (x, ξ) ≥ µ, then ξ -2 q ,θ (x, ξ) -1 ≥ c ell > 0.

(i.e., Q ,θ -1 defined by (3.10) is semiclassically elliptic in this region of phase space).

Proof. In each part we show that there exists a µ 1 such that the conclusion holds, and set the final constant µ to be the maximum of the two. (i) By the lower bound in (3.5), there exists µ > 1 and c ell > 0 such that |ξ| ≥ µ implies that ξ -2 (q (x, ξ) -1) ≥ c ell > 0.

The lower bound (3.5) also ensures that there exists µ > 1 such that q (x, ξ) ≥ µ implies that |ξ| ≥ µ, and thus (5.4) holds.

(ii) Recall from §3.3 that Q ,θ = Q on B Rscat and Q ,θ = -2 ∆ θ on B R1(1+3δ) \ B Rscat . Therefore, by [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Theorem 4.32], given > 0, there exist C 1 , C 2 > 0 such that

for all x ∈ B R1(1+3δ) \ B Rscat , for all ξ, and for ≤ θ ≤ π/2 -. The result then follows in a similar way to the proof of Part (i). Note that both µ and Λ only depend on q and { q ,θ } ≤θ≤π/2-.

The frequency cut-offs. We define, using the Borel functional calculus for P (Theorem 3.4), Definition of the decomposition. Let v be the solution of (4.5). Given > 0, fix δ > 0 so that R

) be such that ϕ tr ≡ 1 on B R1(1+δ) and supp ϕ tr ⊂ B R1(1+2δ) . After writing

we then treat ϕ tr v as an element of D and let

When ρ = 1 in the assumption (4.4), we show that

By (5.27) and a further use of Lemma 3.5, Step 2: Viewing Π High [P , ϕ 0 ] as a semiclassical pseudodifferential operator on T d R . To prove (5.30) from (5.35), it therefore remains to bound the commutator term Π High [P , ϕ 0 ]u. Since [P , ϕ 0 ] is supported away from B R0 , we can write the high-frequency cut-off in terms of a semiclassical pseudodifferential operator thanks to Lemma 3.6.

Recall that ϕ 0 is compactly supported in B R1 and equal to one near

) be supported in B R1 , equal to zero near B R0 , and such that φ ≡ 1 near supp∇ϕ 0 .

(5.36)

, equal to zero near B R0 , and equal to one near suppφ. Using (5.37) and Lemma 3.5 with ψ 1 = 1 -χ and ψ 2 = χφ = φ, we obtain that

(5.38)

i.e., modulo negligible terms, χΠ High χ is a high-frequency cut-off defined from the semiclassical pseudodifferential calculus. We here emphasise that, since χ is supported in B R1 and vanishes near B R0 , χΠ Ψ High χ can be seen as an element of both L(H ) and

(5.41)

Reference for the proof. See [START_REF] Galkowski | Decompositions of high-frequency Helmholtz solutions via functional calculus, and application to the finite element method[END_REF]Lemma 3.1], where this is proved using Lemma 3.6. Now, by (5.38) and (5.39), for any N and any m,

with φ compactly supported in B R1 \B R0 and equal to one on supp φ. Taking m = 1, then N = M + 1 and using the resolvent estimate (5.19) we get

(5.42)

Step 3: A semiclassical elliptic estimate in T d R . Combining (5.35) and (5.42), we see that to prove (5.30) we only need to bound χΠ

To do this, we use the semiclassical elliptic parametrix construction given by Theorem A.2.

Lemma 5.8 The operator

Proof. By (A.8), (A.10), (5.41), and (5.3),

But, on {q ≥ µ}, by definition of µ (5.4),

and the proof is complete.

) by Theorem A.1, we can therefore apply the elliptic parametrix construction given by Theorem A.

and such that χΠ Ψ High χ[Q , ϕ 0 ] = S(Q -1) + R. We apply both sides of this identity to φv and then use that φ is equal to zero near B R0 and supported in B R1 , and thus Q = P = P ,θ on supp φ ; the result is that

The following lemma combined with (A.9) shows that

Proof. By (5.43) and the definition of

Now, by (5.36), supp∇ϕ 0 and supp∇φ are disjoint, and the result follows.

Therefore, by (5.44), (5.45) and the definition of O( ∞ ) Ψ -∞ (A.4), for any N , there exists

where φ is compactly supported in B R1 \B R0 and equal to one on supp φ. Taking N := M + 1, using the resolvent estimate (5.19), and then using that

Combining this last estimate with (5.35) and (5.42) we obtain the desired bound (5.30) on v High,near .

Step 4: Obtaining the bound (5.31) on v High,far using the ideas from Steps 2 and 3. We now show that v High,far :=

satisfies the bound (5.31). Since ϕ 1 is supported away from B R0 , exactly as in Step 2, Π Ψ Low :=

Now, by (5.46), (5.47), and the facts that ϕ tr ϕ tr = ϕ tr and ϕ

Lemma 5.10 The operator Q ,θ -1 is semiclassically elliptic on WF ( ϕ 1 ϕ tr Π Ψ High ϕ 1 ϕ tr ).

Proof. First recall that supp(ϕ 1 ϕ tr ) ⊂ supp( ϕ 1 ϕ tr ) ⊂ B R1(1+3δ) \ B R0 . Using this property, along with (A.8), (A.10), (5.41), and (5.3), we find that

By Lemma 5.1, Q ,θ -1 is semiclassically elliptic on the set on the right-hand side of the last displayed inclusion, and the proof is complete.

We now apply Theorem A.2 with A = ϕ 1 ϕ tr Π Ψ High ϕ 1 ϕ tr , B = Q ,θ -1, = 0, and m = 2; observe that the assumptions of Theorem A.2 are then satisfied by Lemma 5.10. Hence, there exists

We now apply (5.49) to χv where

By construction Q ,θ = P ,θ on B R1(1+3δ) \ B R0 (see (3.10) and (3.9)); thus χ( Q ,θ -1)v = χg and

Arguing exactly as in Lemma 5.9, using (5.48) and the fact that supp ∇ χ ∩ supp(ϕ

ψ µ (λ) -M -1 g H(Ωtr) ; thus (4.9) holds, where the sup λ∈R becomes sup λ∈[-Λ,Λ] because of the support property (5.6) of ψ µ . The proof of (4.10) is very similar to the proof of (4.15) above. Since

By (5.51), Part 1 of Theorem 3.4, pseudo-locality of the functional calculus (Lemma 3.5), and the support property (5.56),

Combining this with (5.60) and then using the resolvent estimate (5.19), we obtain (4.10).

5.4.6

The term away from the black-box v Low,far .

We now study v Low,far :=

which is in D ,∞ by the fact that Π Low : D → D ,∞ (see §5.1) and the smoothness and support properties of γ 1 (see §5.4.3).

Step 1: expressing v Low,far in terms of v A,far Since supp(1-γ 1 ) and supp(1-ρ 1 ) are disjoint (see Figure 5.3), the pseudo-locality of the functional calculus given by Lemma 3.5 implies that

Therefore, by Lemma 3.6 (and exactly as in §5.3),

and, by (5.40), WF Π Ψ Low ⊂ {|q | ≤ 2µ}. Therefore, by (3.5), there exists λ > 1 such that

] and equal to one on [-λ 2 /4, λ 2 /4]. By (A.10) and (5.63), WF 1 -Op

Therefore, by (A.9), as operators on the torus,

(5.64)

Since γ 1 = 0 on a neighbourhood of B R0 , by the definitions of P (3.4), • D ,m (3.11), and

and thus

. Therefore, combining this with (5.64) and (5.62), we obtain that

(5.66)

Step 3: proving that v A,far is negligible in B R II (i.e., the bound (4.12)). It therefore remains to show (4.12). By (A.8), (A.10), and the support property (5.58),

Then, by (A.9),

(1 -γ 2 ) Op

as a pseudo-differential operator on the torus. Multiplying by γ 1 on the right and on the left, and then using the fact that γ 1 = 0 on B R0 and the norm equivalence (5.65), we find

as an element of L(H ). On the other hand, since

Then (4.12) follows from combining this last equation with the definition of u ∞ A (5.67), (5.71), and the resolvent estimate (5.19).

The proof of Theorem 4.1 is now complete.

6 Proofs of Theorems 1.16 and 1.17 For completeness, we sketch here the ideas behind these proofs.

Set-up common to both proofs

Let := k -1 and define H and P as in Lemma 3.2 with Ω -= ∅. By Lemma 3.2, P is a semiclassical black-box operator on H. The reference operator is given by P

The assumption that the solution operator is polynomially bounded (in the sense of Definition 1.2) means that the bound (4.2) holds with H given by (6.1); i.e., the assumption in Point 1 of Theorem 4.1 is satisfied. Define P ,θ by (3.8). In this notation, the PML problem (1.5) becomes (P ,θ -I)v = 2 g.

Sketch proof of Theorem 1.16

We now construct E and E satisfying the assumptions in Point 2 of Theorem 4.1 under Assumption 1.10. Let Λ > 0 be as in Theorem 4.1, and let E ∈ C ∞ comp (R) be such that E = 1 in [-Λ, Λ], and E = 0 outside [-2Λ, 2Λ]. The results of Helffer-Robert [START_REF] Helffer | Calcul fonctionnel par la transformation de Mellin et opérateurs admissibles[END_REF] imply that

R (see the discussion in §1.8 under the paragraph "Ingredient 5"). Then, arguing as in Step 1 in §5.4.6, we obtain that there exists Λ 0 > 0 such that

) and equal to one on B(0, Λ 2 0 /4). By Lemma A.3, If A can be written in the form above, i. e. A = Op T d R (a) with a ∈ S m , we say that A is a semiclassical pseudodifferential operator of order m on the torus and we write A ∈ Ψ m (T d R ); furthermore that we often abbreviate Ψ m (T d R ) to Ψ m in this Appendix. We use the notation Residual class. We say that A = O( ∞ ) Ψ -∞ if, for any s > 0 and N ≥ 1, there exists C s,N > 0 such that

i.e. A ∈ Ψ -∞ and furthermore all of its operator norms are bounded by any algebraic power of .

Principal symbol σ . Let the quotient space S m / S m-1 be defined by identifying elements of S m that differ only by an element of S m-1 . For any m, there is a linear, surjective map When applying the map σ m to elements of Ψ m , we denote it by σ (i.e. we omit the m dependence) and we use σ (A) to denote one of the representatives in S m (with the results we use then independent of the choice of representative).

Operator wavefront set WF . We say that (

denoted by WF A, if there exists a neighbourhood U of (x 0 , ζ 0 ) such that for all multi-indices α, β and all N ≥ 1 there exists C α,β,U,N > 0 (independent of ) such that, for all 0 < ≤ 0 ,

For ζ 0 = RC(ξ 0 ) in the interior of B d , the factor ξ -N is moot, and the definition merely says that outside its semiclassical operator wavefront set an operator is the quantization of a symbol that vanishes faster than any algebraic power of ; see [START_REF] Zworski | Semiclassical analysis[END_REF]Page 194], [START_REF] Dyatlov | Mathematical theory of scattering resonances[END_REF]Definition E.27]. For ζ 0 ∈ ∂B d = S d-1 , by contrast, the definition says that the symbol decays rapidly in a conic neighborhood of the direction ζ 0 , in addition to decaying in .

Properties of the semiclassical operator wavefront set that we use in §5. Ellipticity. We say that B ∈ Ψ m is elliptic at (x 0 , ζ 0 ) ∈ T * T d R if there exists a neighborhood U of (x 0 , ζ 0 ) and c > 0, independent of , such that ξ -m σ (B)(x, ξ) ≥ c for all (x, RC(ξ)) ∈ U and for all 0 < ≤ 0 .

A key feature of elliptic operators is that they are microlocally invertible; this is reflected in the following result. Functional Calculus. The main properties of the functional calculus in the black-box context are recalled in §3.4; here we record a simple result that we need about functions of the flat Laplacian. For f a Borel function, the operator f (-2 ∆) is defined on smooth functions on the torus (and indeed on distributions if f has polynomial growth) by the functional calculus for the flat Laplacian, i.e., by the Fourier multiplier

(A.11)

The following lemma shows that f (-2 ∆) is precisely the quantization of f (|ξ| 2 ); since our quantization procedure was defined in terms of Fourier transform rather than Fourier series, this is not obvious a priori.