Isabelle Sivignon
email: isabelle.sivignon@gipsa-lab.grenoble-inp.fr

A near-linear time guaranteed algorithm for digital curve simplification under the Fréchet distance

Given a digital curve and a maximum error, we propose an algorithm that computes a simplification of the curve such that the Fréchet distance between the original and the simplified curve is less than the error. The algorithm uses an approximation of the Fréchet distance, but a guarantee over the quality of the simplification is proved. Moreover, even if the theoretical complexity of the algorithm is in O(n log(n)), experiments show a linear behaviour in practice.

Introduction

Given a polygonal curve, the curve simplification problem consists in computing another polygonal curve that (i) approximates the original curve, (ii) satisfies a given error criterion, (iii) with as few vertices as possible. This problem arises in a wide range of applications, such as geographic information systems (GIS), computer graphics or computer vision, where the management of the level of details is of crucial importance to save memory space or to speed-up analysis algorithms.

This problem has been studied for many years for various metrics : classical L 1 , L 2 , L ∞ metrics (see [START_REF] Buzer | Optimal simplification of polygonal chains for subpixel-accurate rendering[END_REF] for a survey on simplification algorithms using these metrics), Hausdorff distance or Fréchet distance. While the L norms and Hausdorff distance are relevant measures for many applications, they do not always reflect the similarity or dissimilarity of two polygonal curves (see for instance the example given in [START_REF] Pelletier | Computing the Fréchet distance between two polygonal curves[END_REF] for the Hausdorff distance). The main reason of this discrepancy is that these metrics consider the curves as sets of points, and do not reflect the course of the curves. However, the course of the curve may be important in some applications, like handwritting recognition for instance [START_REF] Sriraghavendra | Fréchet distance based approach for searching online handwritten documents[END_REF]. The Fréchet distance is often used to overcome this problem as it nicely measures the similarity between two curves. The Fréchet distance can be intuitively defined considering a man walking his dog. Each protagonist walks along a path, and controls its speed independently, but cannot go backwards. The Fréchet distance between the two pathes is the minimal length of the leash required.

Fréchet distance

Given two curves f and g specified by functions f : [0, 1] → R 2 and g : [0, 1] → R 2 , and two non-decreasing continuous functions α : [0, 1] → [0, 1] and β : [0, 1] → [0, 1] with α(0) = 0, α(1) = 1, β(0) = 0, β(1) = 1, the Fréchet distance δ F (f, g) between two curves f and g is defined as

δ F (f, g) = inf α,β max 0≤t≤1 d(f (α(t)), g(β(t)))
where d denotes the Euclidean distance. The polygonal curve simplification problem was first studied for the Fréchet distance by Godau [START_REF] Godau | A natural metric for curves-computing the distance for polygonal chains and approximation algorithms[END_REF]. Alt and Godau proposed in [START_REF] Alt | Computing the Fréchet distance between two polygonal curves[END_REF] an O(mn)-time algorithm to determine whether δ F (P, Q) ≤ ε for two polygonal curves P and Q of size n and m, and a given error ε > 0. The complexity turns out to be O((m 2 n + n 2 m) log(mn)) for the actual computation of the Fréchet distance between two curves. A recent work [START_REF] Driemel | Approximating the fréchet distance for realistic curves in near linear time[END_REF] proposes a nearlinear time algorithm to compute an approximation of this distance.

Curve simplification problem

In the rest of the paper, we follow the notations used in [START_REF] Agarwal | Near-linear time approximation algorithms for curve simplification[END_REF] or [START_REF] Abam | Streaming algorithms for line simplification[END_REF]. Given a polygonal curve P = p 1 , . . . p n , a curve P ′ = p i1 , . . . p i k with 1 = i 1 < . . . < i k = n is said to simplify the curve P . P (i, j) denotes the subpath from p i to p j .

Given a pair of indices 1 ≤ i ≤ j ≤ n, δ F (p i p j , P ) denotes the error of the segment p i p j with respect to P (i, j). Then,

δ F (P ′ , P ) = max 1≤j≤k δ F (p ij p ij+1 , P )
For the sake of clarity, the simplified notation error(i, j) = δ F (p i p j , P ) will sometimes be used. We also say that p i p j is a shortcut.

P ′ is an ε-simplification of P if δ F (P ′ , P ) ≤ ε. The optimization problem is the following : given a polygonal curve P , find a ε-simplification P ′ of P with the minimum number of vertices. The approach of Imai and Iri [START_REF] Imai | Polygonal approximations of a curve: formulations and algorithms[END_REF] leads to an optimal solution under the Fréchet distance in O(n 3 ).

In [START_REF] Agarwal | Near-linear time approximation algorithms for curve simplification[END_REF], the authors propose an O(n log(n)) algorithm. The base of their algorithm is greedy and very simple: points are added one by one while the error of the shortcut is lower than ε, otherwise the process starts over from the last point processed. The strength of their approach lies in the following property :

Lemma 1. [2, Lemma 3.3] Let P = {p 1 , p 2 , . . . , p n } be a polygonal curve in R 2 . For 1 ≤ i ≤ l ≤ r ≤ j ≤ n, error(l, r) ≤ 2error(i, j)
This means that for any shortcut p l p r such that error(l, r) > ε, there does not exist a shortcut p i p j such that error(i, j) ≤ ε 2 . They derive the following theorem: Theorem 1. [2, Theorem 3.4] Given a polygonal curve P in R d and a parameter ε > 0, we can compute in O(n log(n)) an ε-simplification P ′ of P under the Fréchet metric error with at most the number of vertices of an optimal ε 2simplification.

The O(nlog(n)) complexity is achieved with a dichotomic processs in the greedy algorithm. The question we arouse in this paper is the following : does there exist a linear-time guaranteed algorithm to compute an ε-simplification ? We propose a guaranteed algorithm for digital curves whose complexity is Ω(n log(n)) in theory but behaves in O(n) in practice. The main features of this algorithm are the following: (i) approximation of the Fréchet distance as in [START_REF] Abam | Streaming algorithms for line simplification[END_REF], (ii) restriction to digital curves. In section 2, we present the approximated distance, and give the algorithm outline as a novel way of using the results of [START_REF] Abam | Streaming algorithms for line simplification[END_REF]. Section 3 is the core of the paper and details the approximated distance efficient and online update, with a restriction to digital curves to achieve a near-linear complexity. Section 4 begins with a theoretical study of the complexity and the guarantee of the proposed algorithm, and ends with some experimental results.

2 Guaranteed algorithm using an approximated distance

Approximating the Fréchet distance

In [START_REF] Abam | Streaming algorithms for line simplification[END_REF], Ali Abam et al. study the following problem: given a possibly infinite sequence of points defining a polygonal path, maintain in a streaming setting, a simplification of this set of points with 2k points and a bounded error. The error is measured using the Hausdorff distance or the Fréchet distance. The Fréchet distance being computationally too costly for this framework, they show that error(i, j) can be upper and lower bounded by functions of two values, namely ω(i, j) and b(i, j). ω(i, j) is the width of the points of P (i, j) in the direction p i p j . b(i, j) is the length of the longest backpath in the direction --→ p i p j . Its precise definition requires the following other definitions: Definition 1. Let l be a straight line of directional vector -→ d . α is the angle between l and the abscissa axis. proj α (p) denotes the orthogonal projection of p onto the line of angle α.

If --→ p l p m . - → d < 0, then proj α (p l ) is "after" proj α (p m ) in direction α, and we denote proj α (p l ) >> proj α (p m ) (see Figure 1(a)). Definition 2. --→ p l p m is a positive shift if and only if --→ p l p m . - → d > 0, negative oth- erwise. Definition 3. A backpath in direction α is a negative shift --→ p l p m such that l < m (see Figure 1(b)). p l is the origin of the backpath. The length of the backpath is equal to d(proj α (p l ), proj α (p m )).
Lemma 2 relates ω(i, j) and b(i, j) to error(i, j): --→ prpq is a backpath since it is a negative shift and pr is before pq on the curve P (i, j). However, it is not the longest backpath: --→ p l pm is also a backpath, of maximal length b(i, j).

Lemma 2. [1, Lemma 4.2] The Fréchet error of a shortcut p i p j satisfies max( w(i,j) 2 , b(i,j) 2 ) ≤ error(i, j) ≤ 2 √ 2 max( w(i,j) 2 , b(i,j) 2 ). p l p m proj α (p l ) proj α (p m ) - → d α (a) b(i, j) p l p m p q p r p i p j (b)

Algorithm 1: Greedy Fréchet simplification algorithm

i = 1, j = 2 while i < n do while j < n and max(w(i, j), b(i, j)) ≤ ε √ 2 do j=j+1 create a new shortcut pipj-1 i = j -1,j = i + 1

Algorithm outline

Algorithm 1 presents the general outline of the ε-simplification. Lemma 3. Algorithm 1 computes an ε-simplification P ′ of a polygonal curve P such that |P ′ | is lower than the number of vertices of an optimal ε Proof. When a shortcut p i p j is created in P ′ , the following two properties are true:

(i) max(w(i, j), b(i, j)) ≤ ε √ 2 and (ii) max(w(i, j + 1), b(i, j + 1)) > ε √ 2 .
From Lemma 2, (i) implies that error(i, j) ≤ ε which proves that P ′ is a εsimplification of P . From lemma 2 again, (ii) implies that error(i, j + 1)

> ε 2 √ 2 .
The hypothesis are then similar to the ones of the proof of [2, Theorem 3.4], and a similar reasoning proves the guarantee.

Note that the complexity of Algorithm 1 has not been adressed yet. Indeed, the difficulty lies in the updates of ω(i, j) and b(i, j) when a new point p j is considered. These two variables depend directly on the direction --→ p i p j . However, when a new point is added, this direction may change drastically: Figure 2 shows an example where the maximal width and maximal backpath are achieved for different vertices of the polyline for --→ p i p j and ----→ p i p j+1 . In the next section, we show how to update efficiently the decisions on ω(i, j) and b(i, j), with a specification for digital curve to reach a near-linear time complexity.

p i p j b(i, j) ω(i, j) (a) ω(i, j) b(i, j) p j+1 p i (b)
Fig. 2. Updating ω(i, j) and b(i, j) can be costly in the general case: for instance, the longest backpath is much smaller in (b) for the direction ----→ pipj+1 than in (a) for the direction --→ pipj.

3 Updating the approximated distance efficiently

In [START_REF] Abam | Streaming algorithms for line simplification[END_REF], where the approximated distance is defined, an actual computation of the variables ω(i, j) and b(i, j) is necessary since the problem is to minimize the error. However, as computing the exact values is too expensive, guaranteed approximations are updated when a new point is added. Contrary to [START_REF] Abam | Streaming algorithms for line simplification[END_REF], in our framework an update of these variables is not necessary, but the decisions "is ω(i, j) ≤ ε √ 2 ?" and "is b(i, j) ≤ ε √ 2 ?" must be exact to ensure the computation of an ε-simplification. This section is devoted to the design of new algorithmic approaches to solve these two problems.

Decision on ω(i, j)

Instead of deciding wether ω(i, j) is under a given threshold or not, we show that it is enough to check the distance between any point of P (i, j) and the vector --→ p i p j . Property 1. Let d max (i, j) = max p∈P (i,j) d(p, --→ p i p j ). We have ω(i,j)

2 ≤ d max (i, j) ≤ ω(i, j).
This property is actually implicitely used in the proof of Lemma 2 in [1, Lemma 4.2]. The authors use the following inequalities to define the approximated distance (the parameters (i, j) are ommited for the sake of lisibility):

max( ω 2 , b 2 ) ≤ max(d max , b 2 ) ≤ error ≤ √ 2 max(d max , b) ≤ √ 2 max(ω, b)
In our framework, it is much easier to use d max instead of ω thanks to the algorithm of Chan and Chin [5, Lemmas 1 and 2]. Given an origin point p i and a set of points P (i, j) we construct the set S ij of straight lines l going through p i such that max p∈P (i,j) (p, l) ≤ r. To do so, we use the following simple fact: d(p, l) ≤ r ⇔ the straight line l crosses the disk of center p and radius r (see Figure 3(a)). S ij is a cone computed incrementally in O(1) time considering for a point p k two new rays defined by p i and the disk of center p k and radius r (see Figure 3(b)). As a result, deciding wether d max (i, j) is lower than r or not is equivalent to checking wether the straight line (p i , p j ) belongs to S ij or not.

Decision on b(i, j)

We first show that some particular points, named occulters, play a special role in the decision on b(i, j). Then, we restrict the framework to digital curves to get a better complexity thanks to the following two facts: the computation of the occulters can be mutualized, and the number of occulters is bounded by the error.

General considerations

Definition 4. A occulter for the direction -→ d is a point p k such that for all l < k, proj α (p k ) >> proj α (p l ). Moreover, an occulter is said to be active if there is no occulter p ′ k with k ′ > k.

Property 2. There is one and only one active occulter for a given direction -→ d .

In other words, the active occulter of a curve P (i, j) in the direction -→ d is the point equal to arg max(proj α (p)). Figure 4 (a) illustrates this definition. Property 3. The origin of the longest backpath of P (i, j) is an occulter for the direction --→ p i p j .

Proof. Let ---→ p k p m be the longest backpath of P (i, j) in the direction --→ p i p j . Suppose that p k is not an occulter. Then there exist a point p l of P (i, j) such that l < k and proj α (p l ) >> proj α (p k ). Thus --→ p l p m is a backpath too, and

||proj α ( --→ p l p m )|| > ||proj α ( ---→ p k p m )||
, which is a contradiction with the fact that ---→ p k p m is the longest backpath.

Property 4. Consider the set of occulters {occ j , j = 1 . . . n} of P (i, k). Let occ max be the active occulter. Consider all the backpathes ----→ occ j p k ending at p k , if any.

Then ||proj α ( ------→ occ max p k )|| > ||proj α ( ----→ occ j p k )|| for all j.
Proof. By definition, proj α (occ max ) >> proj α (occ j ) for all j, and the result follows straighforwardly.

Putting together the previous properties, we see that updating the active occulter is the key point of the computation of the longest backpath. Suppose that we are computing the backpathes in direction -→ d for the curve P (i, j). Suppose that all the points of P (i, k) have been processed, and that the point p k+1 is added. If p k p k+1 is a positive shift then nothing needs to be done:

p k+1 cannot be the origin of a backpath since it's the last point processed.

p k+1 is not the end of the longest backpath since proj α (p k+1 ) >> proj α (p k ).

The case when p k p k+1 is a negative shift is detailed in Algorithm 2. Figure 4(b) illustrates the difference cases of Algorithm 2. Only the double-squared backpathes are considered in the algorithm. Indeed, the backpathes number 2 and 5 are not taken into account because of Property 4. The backpath number 4 is not considered either because the end of the backpath follows a positive shift: we know for sure that the backpath number 3 is longer. However, note that the backpath number 0 is considered: the length of this backpath may be greater than the threshold.

According to Algorithm 1 we see that Algorithm 2 must be applied for any direction --→ p l p m where p l and p m are any two points of the curve, with l < m. In the general case, for a polygonal curve of n points, there are O(n 2 ) such directions, that can be computed as a preprocessing of the curve. In the case of a digital curve embedded in an image of size n × n, the possible directions are known a priori but O(n 2 ) directions must still be considered. However, we see in the following that the computation of the backpathes can be mutualized in the case of digital curves.

Digital curves specificities

In the following, we consider 8-connected digital curves, but the algorithm also works for 4-connected curves.

Algorithm 2: Active occulter update and backpath computation for a direction -→ d

Let occmax be the active occulter for

P (i, k) in direction -→ d . 1 if ----→ p k p k+1 is negative then 2 if ----→ p k-1 p k is positive then 3 if projα(p k ) >> projα(occmax) then 4 occmax = p k 5
The vector --------→ occmaxp k+1 may be a backpath.

6

An elementary shift is a vector ----→ p k p k+1 . For a digital curve, there are only 8 elementary shifts, given by the chain codes, and denoted -→ e i , i = 0 . . . 7 in the following. We also classify the directions -→ d = (d x , d y ) into 8 octants as illustrated in Figure 5. Proof. An octant clusters all the directions with a fixed sign for d x and d y , and such that the order on d x and d y is the same. For instance, in the octant 0, we find all the directions such that 0 ≤ d y < d x . Since the components e i,x and e i,y of -→ e i lie in {-1, 0, 1}, the sign of -→ d .

-→ e i only depends on the signs and order of d x and d y , which ends the proof.

As a consequence, for all the directions of a given octant the elementary positive and negative shifts are the same. In Figure 5(b), all the elementary positive shifts are depicted for each octant. Thus, the tests of Algorithm 2 lines 2-3 are the same for all the directions of a given octant. Nevertheless, on line 4, the projections of two points on a direction -→ d are compared, and this test is not so easy when an octant of directions is considered. In the following the octant 0 is considered, but a similar reasoning can be done for the other cases. Consider the Figure 6(a), where the plane is divided into four areas according to the position of a point p:

for any point q in the gray area, we have proj α (q) >> proj α (p) for any direction of the octant 0; -for any point q in the dashed area, we have proj α (p) >> proj α (q) for any direction of the octant 0; -in the white area, the order of the projections changes, as illustrated in Figure 6(b-d).

Thus, we do not have only one active occulter to update anymore, but a set of occulters for each octant. Any active occulter is associated to an interval of angles for which it is actually the active occulter. From Property 2, we derive that these intervals are disjoint and that there union is the interval [0, π 4 ]. Algorithm 3 describes how to update the active occulters for the directions of octant 0. The complexity of Algorithm 3 depends on the number of active occulters. The following lemma is used in the complexity analysis in Section 4 to prove that the number of occulters per octant is bounded by the approximation error in the case of digital curves.

Lemma 5. For a digital curve and for a given octant, there is at most one active occulter per line and per column of Z 2 . Idea of the proof. When two points p and q are on the same row or the same column, then for all the directions of a given octant, either p is an occulter for q or q is an occulter for p.

List of forbidden directions

From Algorithm 1, we see that the length of the longest backpath is tested for each point, which defines a new direction. Moreover, we see from Algorithm 2 line 6 that for each negative shift, we can have as many backpathes as active occulters. All in all, testing individually all the possible backpathes when a new point is added is too costly. To solve this problem, we propose to maintain a "set" of the directions for which there exist a backpath of length greater than the error ε.

This set actually consists of a list of intervals defined as follows. Consider a backpath ---→ p k p m of length l. Then the length of the projection of this backpath on the direction -→ d is a function of l and the angle between ---→ p k p m and -→ d . This

Fig. 1 .

 1 Fig. 1. (a) Illustration of Definitions 1 and 2. (b) Illustration of backpathes in direction --→ pipj: --→prpq is a backpath since it is a negative shift and pr is before pq on the curve P (i, j). However, it is not the longest backpath: --→ p l pm is also a backpath, of maximal length b(i, j).

Fig. 3 .

 3 Fig. 3. (a) A line which is at a distance lower than r from a point p crosses the disk of center p and radius r. (b) The cone Sij (dark gray) is computed incrementally as the intersection of the light gray cones.

Fig. 4 .

 4 Fig. 4. (a) Occulters for the direction -→ d . The only active occulter is circled. (b) Backpathes in the direction -→ d : the origin of all the backpathes is an occulter, but only the double-squared backpathes need to be considered in the algorithm.

Fig. 5 .

 5 Fig. 5. (a) Clustering of the directions into octants: for instance, the direction -→ d belongs to the octant 0. (b) Illustration of the elementary positive shifts for each octant.

Lemma 4 .

 4 Consider any elementary shift -→ e i . Then, the sign of -→ d . -→ e i is the same for all the directions -→ d of a given octant.

Fig. 6 .

 6 Fig. 6. When the point q in the the white area (a), the order of the projections of p and q on the line of angle α changes according to the angle β (b-d).

√ 2 -simplification of P.

Algorithm 3: Update of the list of active occulters for the octant 0 Let p be the last point added, we want to check if p is an active occulter. is illustrated in the Figure 7: for a given backpath of length l and angle α, and a given error ε, the interval of directions for which the projection of the backpath has a length greater than ε is computed easily. Eventually, such an interval is computed for each backpath of length greater than ε, and the list of all these intervals is called the list of forbidden directions. At the end, we have the following equivalence: b(i, j) is greater than ε if and only if the direction --→ p i p j belongs to the list of forbidden directions. This equivalence enables to test efficiently b(i, j) in O(log(n i )) for n i intervals (see Algorithm 1).

Theoretical and experimental results

Complexity and guarantee analysis

Theorem 2. Algorithm 1, combined with Algorithm 2 and Algorithm 3, compute in O(n log(n i )) an ε-simplification of a digital curve P under the Fréchet distance with at most the number of vertices of an optimal ε 4 √ 2 -simplification.

Proof. The proof of the guarantee is given by Lemma 3. The complexity of the algorithm lies in: (i) the number of active occulters n o and (ii) the size of the list of intervals of forbidden directions n i . Indeed, the general complexity is O(n(n o + log(n i ))). Nevertheless, putting together Lemma 5 and the fact that the width is bounded by the error, we get that n o is also upper bounded by the error, which ends the proof.

n i is more difficult to bound since one interval may be added after each negative shift, but we see in the following section that experimentally, the algorithm runs in linear time.

Experimental behaviour

Figure 8 illustrates the results of our algorithm for a noisy flower with 5 extremities, for three different values of the ε parameter. The images were generated with the Imagene toolkit [START_REF] Lachaud | ImaGene[END_REF].

In Figure 9(a), runtime results are depicted for noisy synthetic data of increasing size: a circle, a flower with 5 extremities, and a phase accelerating flower with 5 extremities. We see that the general behaviour is clearly linear in time. In Figure 9(b), we study the runtime for different values of ε for noisy synthetic flowers of increasing size. Once again, we see a linear behaviour for any value of ε. A more detailed study of the evolution of the slope would give some hints to refine the theoretical complexity analysis.

Lastly, in Figure 10 we compare the result of the approximated Frechet simplification algorithm (where the width and the backpathes length are taken into account) with the result of a simplification algorithm with a width criterion only (points are added while w(i, j) is lower than the error). We see that for the same error, even if the polygons returned by the two algorithms roughly have the same number of vertices (56 in (a), 60 in (b)), the sharp features of the shape are better preserved with the approximated Frechet distance.

Future works

The first perspective is to refine the theoretical complexity from O(n log(n)) to O(n) since the experimental results show a linear behaviour. Another perspective is to extend this algorithm (and its complexity) to general polygonal curves. Indeed the main idea of the algorithm is to cluster the directions used for the projection according to the directions of elementary shifts. This clustering is possible if the minimal angle between two elementary shifts directions is known, which is trivial in the case of digital curves, but could be computed as a preprocessing for polygonal curves.


Lyonell Boulton

Nabile Boussa Ïd

Mathieu Lewin

GENERALISED WEYL THEOREMS AND SPECTRAL POLLUTION IN THE GALERKIN METHOD

Keywords: November 21, 2011 Weyl's Theorem, generalised essential spectrum, spectral pollution, Galerkin method. 1

We consider a general framework for investigating spectral pollution in the Galerkin method. We show how this phenomenon is characterised via the existence of particular Weyl sequences which are singular in a suitable sense. For a semi-bounded selfadjoint operator A we identify relative compactness conditions on a selfadjoint perturbation B ensuring that the limiting set of spectral pollution of A and B coincide. Our results show that, under perturbation, this limiting set behaves in a similar fashion as the essential spectrum.

Introduction

Let A be a self-adjoint operator acting on a separable infinite dimensional Hilbert space H and let λ be an isolated eigenvalue of A. For I ⊂ R an interval let 1 I (A) be the spectral projector of A associated to I. The numerical estimation of λ whenever inf σ ess (A) < λ < sup σ ess (A) and, more generally, when Tr 1 (-∞,λ) (A) = Tr 1 (λ,∞) (A) = ∞, constitutes a serious challenge in applied spectral theory. Indeed, it is well established that classical approaches, such as the Galerkin method, suffer from variational collapse under no further restrictions on the approximating space. This often leads to numerical artefacts which do not belong to the spectrum of A, giving rise to what is generically called spectral pollution.

The spectral pollution phenomenon occurs in different practical contexts such as Sturm-Liouville operators [START_REF] Aceto | Numerical computation of eigenvalues in spectral gaps of Sturm-Liouville operators[END_REF][START_REF] Stolz | Approximation of isolated eigenvalues of general singular ordinary differential operators[END_REF][START_REF] Stolz | Approximation of isolated eigenvalues of ordinary differential operators[END_REF], perturbations of periodic Schrödinger operators [START_REF] Boulton | On approximation of the eigenvalues of perturbed periodic Schrödinger operators[END_REF][START_REF] Marletta | Neumann-Dirichlet maps and analysis of spectral pollution for non-self-adjoint elliptic PDEs with real essential spectrum[END_REF] and systems underlying elliptic partial differential equations [START_REF] Arnold | Finite element exterior calculus: from Hodge theory to numerical stability[END_REF][START_REF] Boffi | Mixed finite elements for Maxwell's eigenproblem: the question of spurious modes[END_REF][START_REF] Boffi | On the problem of spurious eigenvalues in the approximation of linear elliptic problems in mixed form[END_REF].

It is a well-documented difficulty in quantum chemistry and physics, in particular regarding relativistic computations [START_REF] Kutzelnigg | Basis set expansion of the Dirac operator without variational collapse[END_REF][START_REF] Stanton | Kinetic balance: A partial solution to the problem of variational safety in Dirac calculations[END_REF][START_REF] Grant | Conditions for convergence of variational solutions of Dirac's equation in a finite basis[END_REF][START_REF] Drake | Application of discrete-basis-set methods to the Dirac equation[END_REF]. It also plays a fundamental role in elasticity and magnetohydrodynamics [START_REF] Kraus | Variational principles and eigenvalue estimates for unbounded block operator matrices and applications[END_REF][START_REF] Dauge | Numerical approximation of the spectra of non-compact operators arising in buckling problems[END_REF][START_REF] Rappaz | On spectral pollution in the finite element approximation of thin elastic "membrane" shells[END_REF][START_REF] Atkinson | The essential spectrum of some matrix operators[END_REF]. In recent years this phenomenon has raised a large interest in the mathematical community [START_REF] Marletta | Neumann-Dirichlet maps and analysis of spectral pollution for non-self-adjoint elliptic PDEs with real essential spectrum[END_REF][START_REF] Hansen | On the approximation of spectra of linear operators on Hilbert spaces[END_REF][START_REF] Levitin | Spectral pollution and second-order relative spectra for self-adjoint operators[END_REF][START_REF] Davies | Spectral pollution[END_REF][START_REF] Descloux | Essential numerical range of an operator with respect to a coercive form and the approximation of its spectrum by the galerkin method[END_REF][START_REF] Pokrzywa | Method of orthogonal projections and approximation of the spectrum of a bounded operator[END_REF][START_REF] Pokrzywa | Method of orthogonal projections and approximation of the spectrum of a bounded operator[END_REF]. There are known pollution-free computational procedures alternative to the basic Galerkin method. These include specialised variational formulations such as those studied at length in [START_REF] Esteban | Variational methods in relativistic quantum mechanics[END_REF][START_REF] Kraus | Variational principles and eigenvalue estimates for unbounded block operator matrices and applications[END_REF][START_REF] Dolbeault | On the eigenvalues of operators with gaps. Application to Dirac operators[END_REF][START_REF] Mertins | On the convergence of the Goerisch method for self-adjoint eigenvalue problems with arbitrary spectrum[END_REF] as well as general methods such as those proposed in [START_REF] Boulton | On the convergence of second order spectra and multiplicity[END_REF][START_REF] Boulton | Non-variational computation of the eigenstates of Dirac operators with radially symmetric potentials[END_REF][START_REF] Boulton | On approximation of the eigenvalues of perturbed periodic Schrödinger operators[END_REF][START_REF] Levitin | Spectral pollution and second-order relative spectra for self-adjoint operators[END_REF][START_REF] Davies | Spectral pollution[END_REF].

A natural approach to deal with spectral pollution, is to derive conditions on the approximating subspaces guaranteeing a "safe" Galerkin method in a given interval of the real line. These conditions were found in [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF] on an abstract setting for operators with particular block-type structures with respect to decompositions of the ambient Hilbert space. They turn out to be motivated from techniques in numerical analysis [START_REF] Arnold | Finite element exterior calculus: from Hodge theory to numerical stability[END_REF][START_REF] Boffi | On the problem of spurious eigenvalues in the approximation of linear elliptic problems in mixed form[END_REF][START_REF] Rappaz | On spectral pollution in the finite element approximation of thin elastic "membrane" shells[END_REF] and computational physics and chemistry (see references in [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF]).

In the present paper we adopt a more general viewpoint than that of [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF]. We establish an abstract framework for spectral pollution in the Galerkin method and then examine its invariance under relatively compact perturbations. Our main concern is primarily theoretical and general in nature. Nonetheless, however, we include various simple examples which illustrate the many subtleties faced when dealing with spectral pollution on a practical setting.

The technical context of our results can be summarised as follows. Let D(A) be the domain of A. Let L = (L n ) n∈N be a sequence of finite dimensional subspaces of D(A), dense in the graph norm as n → ∞ (Definition 1) 1 . Denote by A n the compression of A to L n . Denote by σ(A, L) the large n limiting set in Hausdorff distance of the Galerkin method spectra σ(A n ), (Definition 2). Then σ(A) ⊂ σ(A, L) (Proposition 2), however in general equality fails to occur in this identity. An abstract notion of limiting spectral pollution set can be formulated naturally as, σ poll (A, L) = σ(A, L) \ σ(A).

As it turns, points in the limiting spectral pollution set behave in a similar fashion as points in the essential spectrum (Proposition 3). Therefore a question arises: what sort of conditions on a perturbation B ensure σ poll (A, L) = σ poll (B, L)? Below we establish a theoretical framework in order to address this question.

Section 2 and 3 are devoted to a characterisation of σ(A, L) in terms of special Weyl-type sequences (L-Weyl sequences) and its structural properties. In Definition 3 we consider a decomposition of σ(A, L) as the union of a limiting essential spectrum associated with L, σ ess (A, L), and its limiting discrete spectrum counterpart, σ disc (A, L). The former contains both the true essential spectrum σ ess (A) and σ poll (A, L) (Proposition 5).

The purpose of sections 4 and 5 is to find conditions on B ensuring (1) σ ess (B, L) = σ ess (A, L).

1 Below we will often consider a slightly more general framework which covers important applications such as those involving the finite element method. In this framework we will only require that the subspaces Ln lie in the domain of the quadratic form associated to A and that the sequence L is dense in the form sense. However, in this more general setting we restrict our attention to A being semi-bounded.

According to our main result (Theorem 11), when A and B are bounded from below and

(2)

(A -a) 1/2 (B -a) -1/2 -1
is a compact operator for some a negative enough, (1) holds true. Therefore, an approximating sequence L will not asymptotically pollute for A in a given interval if and only if it does not pollute for B in the same interval. This generalises [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF]Corollary 2.5].

Our present approach consists in adapting to the context of limiting spectra, several classical results for the spectrum and essential spectrum. In turns, this leads to many unexpected difficulties which we will illustrate on a variety of simple examples. In particular, we establish (Theorem 7) a limiting spectra version of the spectral mapping theorem allowing to replace the unbounded operator A by its (bounded) resolvent (A -a) -1 . Remarkably, this theorem fails in general (Remark 4) for operators which are not semi-bounded.

Limiting spectra

We will often restrict our attention to A being bounded from below, however we do not require this for the moment. Unless otherwise specified, we always assume that the subspaces L n are dense in the following precise sense. Definition 1 (A-regular Galerkin sequences). We say that L = (L n ), L n ⊂ D(A), is an A-regular Galerkin sequence, or simply an A-regular sequence, if for all f ∈ D(A) there exists a sequence of vectors (f n ) with

f n ∈ L n such that f n → f in the graph norm of A, that is: (3) f n -f + Af n -Af → n→∞ 0.
The orthogonal projection in the scalar product of H onto L n will be denoted by π n : H -→ L n and the compression of A to L n by A n = π n A↾ Ln : L n -→ L n . These compressions will sometimes be identified with any of their matrix representations. On sequences (x n ) n∈N ⊂ H of vectors and (L n ) n∈N of subspaces L n ⊂ D(A) we will often suppress the index and write (x n ) and (L n ) instead. we will denote by x n ⇀ x the fact that x n is weakly convergent to x ∈ H. When the norm is not specified, x n → x will denote the fact that x n -x → 0.

When A is semi-bounded, we may also consider sequences L = (L n ) only in the form domain of A. They may approximate the latter but not necessarily the operator domain. If A ≥ 0, for instance, this simply means that L n ⊂ D(A 1/2 ) and L is A 1/2 -regular but not necessarily A-regular. In our notation, for

x n ∈ L n , Ax n ∈ D(A 1/2 ) # , the dual of D(A 1/2 ) as subspace of H. Since π n A 1/2 y ∈ H # = H and π n A 1/2
y ⊥ g for any y ∈ H and g ∈ H ⊖ L n , the compression π n A ↾ Ln : L n -→ L n is well defined also in this framework. Moreover, a matrix representation of A n can be obtained in the usual manner, via

[ A 1/2 b j , A 1/2 b k ] dim Ln jk=1
for a given orthonormal basis {b j } of L n . We will denote the duality product associated to w ∈ D(A 1/2 ) # by z -→ z|w .

When A is not semi-bounded but its essential spectrum has a gap containing a number a, we could as well consider sequences (L n ) which are only |A -a| 1/2regular. We have chosen to avoid mentioning quadratic forms for operators which are not semi-bounded, because in practical applications (such as those involving the Dirac operator) the domain of |A -a| 1/2 does not necessarily coincide with the natural domain upon which the quadratic form is defined.

The limiting spectrum of A relative to the Galerkin sequence L, is the set of all limit points, up to subsequences, of the spectra of A n in the large n limit. Definition 2 (Limiting spectrum). The limiting spectrum of A relative to L, σ(A, L), is the set of all λ ∈ R for which there exists

λ k ∈ σ(A n k ) such that n k → ∞ and λ k → λ as k → ∞.
Since all A n are Hermitian endomorphisms, σ(A, L) ⊂ R. The following lemma provides an alternative characterisation of σ(A, L).

Lemma 1 (L-Weyl sequences). The real number λ ∈ σ(A, L) if and only if there exists a sequence

x k ∈ L n k such that x k = 1 and π n k (A -λ) x k → 0 as k → ∞.
Proof. According to the definition, λ ∈ σ(A, L) if and only if there exists λ k ∈ R and

x k ∈ L n k with x k = 1 such that λ k → λ and π n k (A -λ k ) x k = 0. As π n k (A -λ) x k = (λ k -λ)x k → 0, one implication follows immediately.
On the other hand, let (x k ) be as stated. Since the A n are Hermitian, there necessarily exists

λ k ∈ σ(A n k ) such that |λ k -λ| ≤ ||(A n k -λ)x k || → 0. Thus λ ∈ σ(A, L) ensuring the complementary implication.
We call (x k ) an L-Weyl sequence for λ ∈ σ(A, L), by analogy to the classical notion of Weyl sequence [START_REF] Davies | Spectral theory and differential operators[END_REF].

Remark 1. Selfadjointness of A n is crucial in Lemma 1. We illustrate this by means of a simple example. Let H = ℓ 2 (N) and (e j ) ⊂ H be the canonical orthonormal basis of this space. Let A be the left shift operator defined by the condition A : e j -→ e j-1 with the convention e 0 = 0. Let L k = Span {e i , i ≤ k}. For this data an analogous of Lemma 1 is no longer valid. Indeed, if |λ| < 1 and

x k := 1 -|λ| 2 1 -|λ| 2k k i=1 λ i-1 e i , then x k ∈ L k , ||x k || = 1 and ||Ax k -λx k || = 1 -|λ| 2 1 -|λ| 2k |λ| k → 0.
Therefore any point of the open unit disk is associated with an L-Weyl sequence.

On the other hand, however, A n is a Jordan block, so σ(A n ) = {0} for all n ∈ N and hence necessarily σ(A, L) = {0}. ⋄

The above characterisation of points in the limiting spectrum combined with the minimax principle yields the following fundamental statement.

Proposition 2 (The limiting spectrum and the spectrum). Let L be an A-regular Galerkin sequence or, if A ≥ 0, an A 1/2 -regular Galerkin sequence. Then,

(4) σ(A) ⊂ σ(A, L)

and

(5)

σ poll (A, L) := σ(A, L) \ σ(A) ⊂ ℓ -, ℓ +
where

ℓ -:= -∞ for inf σ(A) = -∞ inf σ ess (A) otherwise ℓ + := +∞ for sup σ(A) = +∞ sup σ ess (A) otherwise.
Proof. We start with the general case of an A-regular sequence. The classical characterisation of the spectrum of selfadjoint operators ensures that λ ∈ σ(A) if and only if there is a normalised sequence (y k ) ⊂ D(A) such that (A -λ)y k → 0 (that is (y k ) is a Weyl sequence for λ). We will now construct an L-Weyl sequence from (y k ). According to (3), we can find (

x k m ) (k,m)∈N 2 such that x k m ∈ L m , (y k - x k m ) → 0 and (A -λ)(y k -x k m ) → 0 as m → ∞. By virtue of a diagonal process, we can extract a subsequence such that π m k (A -λ)x k m k → 0. Dividing by x k m k
(which does not vanish in the k → ∞ limit), gives (4) as consequence of Lemma 1.

When A ≥ 0 and L is only A 1/2 -regular, a similar proof applies. We explicitly take x k m := π ′ m y k where π ′ m is the orthogonal projection onto L m , for the scalar product furnished by the quadratic form associated to A.

For all z ∈ L m with ||z| | = 1 z|(A -λ)x k m | = z|(A -λ)y k + (λ + 1) z|y k -x k m ≤ ||(A -λ)y k || + (λ + 1) y k -x k m , where we have used that z|(A + 1)y k = z|(A + 1)π ′ m y k by definition of the projection π ′ m . Thus π m (A -λ)x k m ≤ ||(A -λ)y k || + (λ + 1) y k -x k m . Our assumption that L is A 1/2 -regular implies that x k m → y k in D(A 1/2
) when m → ∞. Hence, the desired conclusion is achieved, once again, by a diagonal argument.

The proof of ( 5) is a classical consequence of the minimax principle. It may be found, for instance, in [21, Theorem 2.1] or [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF]Theorem 1.4].

In [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF]Theorem 1.4] the existence of an A-regular Galerkin sequence L such that σ(A, L) = [ℓ -, ℓ + ] is shown. Therefore the inclusion complementary to (4) does not hold in general. This is a source of difficulties in applications as there is no known systematic procedure able to identify A-regular Galerkin sequences such that σ(A) = σ(A, L). By virtue of (5), limiting spectral pollution σ poll (A, L) can only occur in "gaps" of the essential spectrum.

Let us now see how σ poll (A, L) can be characterised in a more precise manner in terms of particular L-Weyl sequences.

Definition 3 (Limiting essential spectrum). We denote by σ ess (A, L) the set of all λ ∈ σ(A, L) for which there exists an L-Weyl sequence (x k ) as in Lemma 1 with the additional property that x k ⇀ 0.

By analogy to the classical notions, we will call σ ess (A, L) the limiting essential spectrum of A associated to L and the corresponding sequence (x k ) a singular L-Weyl sequence.

Remark 2. From the definition it follows that σ ess (A + K, L) = σ ess (A, L) for any selfadjoint operator K ∈ K(H). ⋄ Definition 4 (Limiting discrete spectrum). The residual set σ disc (A, L) = σ(A, L)\ σ ess (A, L), will be called the limiting discrete spectrum of A associated to L.

We illustrate these definitions by means of various simple examples.

Example 1 (A a bounded operator). Let H = Span{e ± n } n∈N where e ± n is an orthonormal set of vectors in a given scalar product. Let

L n = Span{e ± 1 , . . . , e ± n-1 , f n } where f n = (cos θ)e + n + (sin θ)e - n for θ ∈ (0, π/2). Let 2 A = n≥1 |e + n e + n |, that is, A is the orthogonal projector onto Span(e + n ) and σ(A) = σ ess (A) = {0, 1}. Then σ(A n ) = {0, 1, cos 2 θ} for all n and σ(A, L) = σ ess (A, L) = {0, 1, cos 2 θ}. Here x n = e - n is a singular L-Weyl sequence associated to λ = 0, x n = e + n is a singular L-Weyl sequence associated to λ = 1 and x n = f n is a singular L-Weyl sequence associated to λ = cos 2 θ. ⋄
Example 2 (A a semi-bounded operator). Let H be as in Example 1 and define

L n = Span{e ± 1 , . . . , e ± n-1 , e - n }. For f ± n = sin( 1 n ) e ∓ n ± cos( 1 n ) e ± n , let A = n 2 |f + n f + n | - |f - n f - n | which has a 2 × 2 block diagonal representation in the basis (e ± n ). Then σ ess (A) = {-1} and σ disc (A) = {n 2 : n ∈ N}. On the other hand σ(A n ) = -1, n 2 sin 2 1 n -cos 2 1 n , 1, . . . , (n -1) 2 ,
where -1 is an eigenvalue of multiplicity n -1. Therefore

σ ess (A, L) = {-1, 0} and σ disc (A, L) = {n 2 : n ∈ N}.
The former is a consequence of Proposition 3-(ii) while the latter follows from Proposition 5-(iii) below. We can verify directly the validity of the latter as follows. Assume that conversely (x k ) was a singular L-Weyl sequence associated with

ν 2 ∈ σ disc (A). Then π n k (A - ν 2 )x k → 0 and x k ⇀ 0. For m < n k p m π n k (A -ν 2 )x k = (A -ν 2 )p m x k where p m = i≤m |f ± i f ± i |.
Then, on the one hand,

p n k -1 x k -f + ν , x k f + ν 2 ≤ (A -ν 2 )p n k -1 x k 2 → 0 so that ||p n k -1 x k || 2 + (A -ν 2 )p n k -1 x k 2 → 0 as k → ∞. On the other hand, (A -ν 2 )(x k -e - n k , x k e - n k ) = (A -ν 2 )p n k -1 x k . Since (A -ν 2 )e - n , e - n = n 2 sin 2 1 n + cos 2 1 n -ν 2 → 2 -ν 2 > 0, projecting each term onto L n k yields e - n k , x k → 0 also. But then 1 = ||x k || → 0,
which is a contradiction, so there are no singular L-Weyl sequences for ν 2 . ⋄

2 Here and elsewhere we use the bra-ket notation |f g| to denote the linear operator ψ → g, ψ f .

Example 3 (A a strongly indefinite operator). Let H and L n be as in Example 2.

Let

f ± n = 1 √ 2 e + n ± 1 √ 2 e - n . Let A = n|f + n f + n | - n|f - n f - n |. Then σ(A) = {±n : n ∈ N} = σ disc (A). On the other hand σ(A, L) = Z, σ ess (A, L) = {0} and σ disc (A, L) = {±n : n ∈ N}.
The proof of the latter is similar to that of the analogous property in Example 2. ⋄

Limiting spectra and the behaviour of singular L-Weyl sequences

We now examine more closely various basic properties of the limiting spectra σ(A, L), σ ess (A, L) and σ disc (A, L). These properties can be deduced via an analysis of the behaviour of different types of L-Weyl sequences.

Proposition 3 (Limiting essential and discrete spectra and the spectrum). Let L be an A-regular Galerkin sequence, or, if A ≥ 0, an A 1/2 -regular Galerkin sequence. Then (i) the limiting spectrum σ(A, L) and the limiting essential spectrum σ ess (A, L) are closed subsets of R;

(ii) moreover σ ess (A) ⊂ σ ess (A, L) and σ disc (A, L) ⊂ σ disc (A).
Proof. The proof of (i) involves a standard diagonal argument and it is left to the reader. For the second statement we need the following auxiliary result which will be used repeatedly below.

Lemma 4. A sequence x k ∈ L n k is such that x k = 1, x k ⇀ x and π n k (A - λ)x k → 0, only when x ∈ Ker(A -λ).
Proof of Lemma 4. Suppose that (x k ) satisfies the hypothesis with L an A-regular Galerkin sequence. Let f ∈ D(A) and

f n ∈ L n such that f n → f in the norm of D(A). Then π n k (A -λ)x k , f n k → 0. On the other hand, since f k → f in D(A), π n k (A -λ)x k , f n k = x k , (A -λ)f n k → x, (A -λ)f .
Thus x, (A-λ)f = 0 for all f ∈ D(A), so that x ∈ D(A * ) = D(A) and (A-λ)x = 0 as required. Suppose now that A ≥ 0 and L is only A 1/2 -regular. The hypothesis implies that (x k ) is a bounded sequence in D(A 1/2 ). Then the proof reduces to the same argument, but taking this time f n k in D(A 1/2 ).

We now turn to the proof of (ii) in Proposition 3. The fact that σ ess (A) ⊂ σ ess (A, L) is proved similarly to [START_REF] Boffi | Mixed finite elements for Maxwell's eigenproblem: the question of spurious modes[END_REF]. It should only be noted that the L-Weyl sequence found for λ ∈ σ ess (A) additionally satisfies x k m k ⇀ 0. For the inclusion

σ disc (A, L) ⊂ σ disc (A) note that, if λ ∈ σ disc (A, L), there exists x k ∈ L n k such that x k = 1, x k ⇀ x = 0 and π n k (A -λ)x k → 0.
As λ ∈ σ ess (A) (by the previous part), then either λ ∈ σ disc (A) or λ ∈ σ(A). By Lemma 4, the latter is impossible.

Remark 3. If σ ess (A) = σ ess (A, L) then automatically σ disc (A) = σ disc (A, L) and σ(A) = σ(A, L). ⋄
We will now examine more closely singular L-Weyl sequences associated to points λ ∈ σ ess (A, L).

Proposition 5 (Singular L-Weyl sequences). Let L be an A-regular Galerkin sequence, or, if A > 0, an A 1/2 -regular Galerkin sequence. The real number λ ∈ σ ess (A, L) if and only if (i) either λ ∈ σ(A) and there exists λ k → λ and y k ∈ L n k such that y k ⇀ 0 and π n k (A -λ k )y k = 0; (ii) or λ ∈ σ ess (A) and there exists λ k → λ and y k ∈ L n k such that y k ⇀ 0 and

π n k (A -λ k )y k = 0; (iii) or λ ∈ σ disc (A) and for any ε > 0 Rank 1 (λ-ε,λ+ε) (A n ) ≥ Rank 1 {λ} (A) + 1
for all n large enough.

In cases (i) and (iii), λ can in some sense be regarded as a point of spectral pollution for A relative to L. In case (iii), λ ∈ σ(A), but the multiplicity of the approximating spectrum σ(A n ) is too large for n large, leading to the wrong spectral representation of A in the limit n → ∞. In our definition of the polluted spectrum σ poll (A, L) in ( 5), we have chosen to require that λ / ∈ σ(A), following [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF]. Any λ ∈ σ(A) satisfying (iii) could also be considered as a spurious spectral point. However, in case (ii), the singular L-Weyl sequence (y k ) behaves like a classical singular Weyl sequence.

Only in cases (i) and (ii) the existence of a singular L-Weyl sequence (y k ) consisting of exact eigenvectors of A n k such that π n k (A -λ k )y k = 0 and λ k → λ is guaranteed. In case (iii) it may occur that all the eigenvectors of A n k whose corresponding eigenvalue converges to λ, converge weakly to a non-zero element of Ker(A -λ), and that only a linear combination of these eigenvectors converges weakly to zero. This can be illustrated by means of a simple example.

Example 4 (Spectral point satisfying Proposition 5-(iii)). Let H = Span{e 0 , e ± n } where e 0 , e ± n form an orthonormal basis. Let

A = ∞ n=1 |e + n e + n | - ∞ n=1 |e - n e - n |.
Then σ(A) = {-1, 0, 1} and σ ess (A) = {-1, 1}. The eigenvalue 0 has multiplicity one and associated eigenvector e 0 . Let

L n = Span{e ± 1 , . . . , e ± n-1 , f ± n } where f ± n = e 0 + α ± n e + n -α ∓ n e - n 1 + (α ± n ) 2 + (α ∓ n ) 2 for α ± n = ± 1 ± 1 n 2 2(1 ∓ 1 n 2 )
.

Then σ(A, L) = {0, ±1} = σ ess (A, L). In this case A n has two eigenvalues approaching zero in the large n limit, with corresponding eigenvectors f + n and f - n . It is readily seen that f ± n ⇀ e 0 / √ 2 and so only the difference f + n -f - n tends weakly to zero. ⋄ Proof of Proposition 5. Let λ ∈ σ ess (A, L) ⊂ σ(A, L). By definition of σ(A, L) there exists a normalised sequence (y k ) such that π n k (A -λ k )y k = 0 and λ k → λ.

The main question is whether one can ensure that y k ⇀ 0 weakly. Up to extraction of a subsequence, we may assume that y k ⇀ y ∈ Ker(A -λ) (by Lemma 4). If λ / ∈ σ(A), then Ker(A -λ) = {0} and necessarily y = 0, thus (i) follows.

For the proof of (ii) we require the following auxiliary result.

Lemma 6. Let V ⊂ D(A) be a subspace of dimension d > 0, with associated orthogonal projector π V . Let ε > 0 be such that

π V (A -λ)x ≤ ε x ∀x ∈ V.
There exists N > 0 and a sequence of spaces

W n ⊂ L n of dimension d, such that for all n ≥ N π Wn (A -λ)y ≤ 2ε √ d y ∀y ∈ W n .
Proof of Lemma 6. We firstly assume that L is A-regular. Let (e j ) be a fixed orthonormal basis of V. Then there exists e n j ∈ L n such that e n j -e j D(A) → 0 when n → ∞. The Gram matrix G n := ( e n i , e n j ) 1≤i,j≤d converges to the d × d identity matrix as n → ∞, and therefore, for sufficiently large n, W n := span{e n j , j = 1, ..., d} has dimension d. Now we define an orthonormal basis for W n by

f n j := d k=1 (G -1/2 n ) kj e n k .
Since (G

-1/2 n
) kj → δ kj and e n j → e j in the graph norm, it is then clear that

e j -f n j D(A) → 0 n → ∞.
This shows in particular that (π Wn -π V )A → 0, π Wn -π V → 0 and hence that π Wn (A -λ)f n j -π V (A -λ)e j → 0. Let N > 0 be such that π Wn (A -λ)f n j ≤ 2ε ∀n ≥ N, j = 1, . . . , d.

For y = d j=1 ŷj f n j ∈ W n , we get π Wn (A -λ)y ≤ 2ε d j=1 |ŷ j | ≤ 2ε √ d y ,
which ensures the desired property. When A ≥ 0 and L is only A 1/2 -regular, the proof is the same, using convergence in D(A 1/2 ) and the fact that (π Wn -π V )A 1/2 → 0 The proof of (ii) in Proposition 5 is achieved as follows. Assume that λ ∈ σ ess (A). For all d ∈ N there exists a subspace

V d ⊂ D(A), such that dim V d = d 2 and (A -λ)y ≤ 1 d 2 y ∀y ∈ V d ,
y 1 = f n1 1 y 2 = f n2 δ2 with 1 ≤ δ 2 ≤ 2 2 such that | y 2 , y 1 | ≤ 1/ √ 2 y 3 = f n3 δ3 with 1 ≤ δ 3 ≤ 3 2 such that | y 3 , y j | ≤ 1/ √ 3 for j = 1, 2 . . . y d = f n d δ d with 1 ≤ δ d ≤ d 2 such that | y d , y j | ≤ 1/ √ d for j = 1, . . . , d -1.
The existence of δ d is guaranteed by the fact that

∀k = 1, ..., d -1, 1 = y k 2 ≥ d 2 j=1 | y k , f n d j | 2 .
Indeed, there are at most d indices j in the above summation, such that Note that, conversely, if (i) or (ii) holds true, then λ ∈ σ ess (A, L) by Definition 3.

| y k , f n d j | 2 ≥ 1/d.
Let us now prove that if λ ∈ σ ess (A, L) ∩ σ disc (A), then (iii) holds true. Let

x k ∈ L n k be a singular L-Weyl sequence: π n k (A -λ)x k → 0, ||x k || = 1 and x k ⇀ 0. Let V = Ker(A -λ) = {0} and d = dim(V).
For n sufficiently large there is a space W n ⊂ L n of dimension d such that for all ε > 0, there exists N > 0 such that

π n (A -λ)y ≤ ε y ∀y ∈ W n whenever n ≥ N . Let S k = Span{W n k , x k }.
Since x k ⇀ 0 and W n k does not increase in dimension in the large k limit, necessarily dim(S k ) = d + 1 for all k large enough. For all ε > 0 there exists M > 0 such that

π n k (A -λ)y ≤ ε y ∀y ∈ S k whenever k ≥ M . This ensures that σ(A n k ) ∩ (λ -ε, λ + ε) contains at least d + 1
points counting multiplicity and hence the claimed conclusion is achieved. It only remains to prove that (iii) implies λ ∈ σ ess (A, L). Each individual eigenvector of A n k might not converge weakly to 0, however there is a linear combination of them that does it. We prove this as follows. Let (f k j ) d+1 j=1 be an orthonormal set of d + 1 eigenvectors

A n k f k j = λ k j f k j j = 1, . . . , d + 1.
Up to extraction of subsequences we may assume that f k j ⇀ f j ∈ Ker(A -λ) for all j = 1, . . . , d + 1. If f j = 0 for some j, then the desired conclusion follows. Otherwise, since dim Ker(A -λ) = d, there exist coefficients (a j ) ∈ C d+1 \ {0} such that d+1 j=1 a j f j = 0. Therefore, we may take

y k := d+1 j=1 a j f k j d+1 j=1 |a j | 2
as singular L-Weyl sequence for λ. This completes the proof of Proposition 5.

Mapping of the limiting spectra

In this section we establish mapping theorems for the different limiting spectra. They are a natural generalisation of the analogous well-known result for σ(A) and σ ess (A) (see for example [START_REF] Reed | Methods of modern mathematical physics. IV. Analysis of operators[END_REF]Section XIII.4]). From now on we assume that A is bounded from below and we take L to be an (A -a) 1/2 -regular Galerkin sequence with a < inf σ(A).

Theorem 7 (Mapping of the limiting spectra). Let A be semi-bounded from below and let a < inf σ(A). Assume that L is an (A -a) 1/2 -regular Galerkin sequence. Then

(6) λ ∈ σ(A, L) ⇐⇒ (λ -a) -1 ∈ σ (A -a) -1 , G and
(7) λ ∈ σ ess (A, L) ⇐⇒ (λ -a) -1 ∈ σ ess (A -a) -1 , G where G = (A -a) 1/2 L n n∈N .
Remark 4. Recall that a selfadjoint operator A is unbounded (D(A) H) if and only if 0 ∈ σ((A -a) -1 ) for one (hence for all) a ∈ σ(A). As it turns out, A is unbounded if and only if 0 ∈ σ ess ((A-a) -1 , G) for one (and hence all) a < min σ(A) and (A -a) 1/2 -regular sequence L. Formally in Theorem 7 this corresponds to the case +∞ ∈ σ(A) and (+∞ -a) -1 = 0. ⋄ Evidently a result analogous to Theorem 7 can be established when A is semibounded from above. However, here A is required to be semi-bounded, in order to be able to use a square root (A -a) 1/2 in the definition of G, and also for a more fundamental reason. When a is in a gap of the essential spectrum, it would be natural to expect an extension of the above result by considering, for example, G = |A -a| 1/2 L n n∈N . The following shows that this extension is not possible in general.

Example 5 (Impossibility of extending Theorem 7 for A strongly indefinite). Let H be as in Example 2. Define L n = Span{e ± 1 , . . . , e ± n-1 , cos(θ n ) e + n + sin(θ n ) e - n } with θ n := π/4 -λ/(2n) for a fixed λ ∈ (0, 1). Let

A = n|e + n e + n | - n|e - n e - n |. Then σ(A) = {±n : n ∈ N} = σ disc (A). On the other hand σ(A, L) = σ(A) ∪ {λ}, σ ess (A, L) = {λ} and σ disc (A, L) = σ(A). Now A -1 = n -1 |e + n e + n | -n -1 |e - n e - n | and G = |A|L = L. Since A -1 is compact we have σ(A -1 , G) = σ(A -1 ) and σ ess (A -1 , G) = σ ess (A -1 ) = {0}. Thus λ ∈ σ ess (A, L) whereas 1/λ ∈ σ(A -1 , G). ⋄
In fact the following example shows that no general extension of this theorem is possible whenever a lies in the convex hull of the essential spectrum, even for A ∈ B(H).

Example 6 (Impossibility of extending Theorem 7 for a ∈ Conv{σ ess (A)}). Let

H = L 2 (-π, π) and Af (x) = sgn(x)f (x) for all f ∈ H. Then σ(A) = σ ess (A) = {±1}. If L is any A-regular sequence, then σ(A, L) ⊂ [-1, 1]. Fixing a = 0 yields (A -a) -1 = A. Thus also σ(A -1 ) = {±1} and σ((A -a) -1 , G) ⊂ [-1, 1]
, for any A-regular sequence G. If we construct a sequence L = (L n ) leading to a spurious eigenvalue λ ∈ σ ess (A, L) ∩ (-1, 1), we will always have λ -1 / ∈ σ ess (A -1 , G), no matter what G is. We thus see that Theorem 7 cannot be extended to include a in the convex hull of the essential spectrum. ⋄

Proof of Theorem 7. Statement (6) will follow immediately from the next result.

Lemma 8 (Mapping for the spectrum of compressions). Let A be semi-bounded from below, let a < inf σ(A) and

L n ⊂ D((A -a) 1/2 ). Then λ ∈ σ(π n A ↾ Ln ) ⇐⇒ (λ -a) -1 ∈ σ(p n (A -a) -1 ↾ Gn )
where G n = (A -a) 1/2 L n and p n is the associated orthogonal projector.

Proof. Note that λ ∈ σ(A n ) if and only if there exists x ∈ L n \ {0} such that

π n (A -a) 1/2 (λ -a) -1 -(A -a) -1 (A -a) 1/2 x = 1 λ -a π n (A -λ)x = 0. By fixing y = (A -a) 1/2 x ∈ G n \ {0}, it is readily seen that λ ∈ σ(A n ) if and only if there exist y ∈ G n \ {0} such that (A -a) 1/2 u, (λ -a) -1 -(A -a) -1 y = 0 for all u ∈ L n . Therefore, the statement λ ∈ σ(A n ) is equivalent to the existence of y ∈ G n \{0} such that (λ -a) -1 -(A -a) -1 y ⊥ G n which, in turns, is equivalent to p n (λ -a) -1 -(A -a) -1 y = 0.
We now turn to the proof of [START_REF] Boulton | On approximation of the eigenvalues of perturbed periodic Schrödinger operators[END_REF]. We begin by establishing an alternative characterisation of the limiting essential spectrum and then we formulate a stability result for the limiting spectra with respect to compact perturbations of the regular Galerkin sequence.

Lemma 9 (Alternative characterisation of σ ess (A, L)). Let

F (A) := f (A) : f ∈ C c R \ σ ess (A), R F ± (A) := f (A) : f ∈ C c R \ σ ess (A), R ± . Then σ ess (A, L) = B∈F (A) σ(A + B, L) = B∈F + (A) σ(A + B, L) = B∈F -(A) σ(A + B, L). (8)
Here C c (Ω, R) denotes the set of all real-valued continuous functions of compact support in the open set Ω. Note that F (A) is a real vector space and F ± (A) are cones, all spanned by projectors onto the eigenspaces of A associated with isolated eigenvalues of finite multiplicity. At the end of this section it will become clear the reason why we highlight the right hand side characterisation in [START_REF] Boulton | On the convergence of second order spectra and multiplicity[END_REF].

Proof of Lemma 9. We only prove the first equality of (8) as the proof of the other ones follows exactly the same pattern. It is well-known that [START_REF] Cancès | Non-perturbative embedding of local defects in crystalline materials[END_REF] σ ess (A) =

B∈F (A) σ(A + B).
Since all the operators in F (A) are of finite rank, then σ ess (A + B) = σ ess (A) for all B ∈ F (A). Hence ( 9) is equivalent to ( 10)

B∈F (A) σ disc (A + B) = ∅.
From Remark 2, it follows that σ ess

(A + B, L) = σ ess (A, L) for all B ∈ F (A). Therefore σ(A + B, L) = σ disc (A + B, L) ∪ σ ess (A, L). Moreover σ disc (A + B, L) ⊆ σ disc (A + B)
, by Proposition 3. Hence, by [START_REF] Dauge | Numerical approximation of the spectra of non-compact operators arising in buckling problems[END_REF],

B∈F (A) σ disc (A + B, L) ⊂ B∈F (A) σ disc (A + B) = ∅
and the result is proved.

Lemma 10. Let T = T * be such that T < ∞ and let L be a T -regular sequence. Let K ∈ K(H). If -1 ∈ σ(K), then σ ess (T, L) = σ ess (T, (1 + K)L) and σ disc (T, L) = σ disc (T, (1 + K)L).
Proof of Lemma 10. We firstly prove that [START_REF] Davies | Spectral theory and differential operators[END_REF] σ ess (T,

L) \ σ disc (T ) = σ ess (T, (1 + K)L) \ σ disc (T ). Since (12) L = (1 + K) -1 (1 + K)L = (1 -K(1 + K) -1 )(1 + K)L,
it suffices to show that the left hand side of ( 11) is contained in the right hand side. Let λ ∈ σ ess (T, L) \ σ disc (T ). If λ ∈ σ ess (T ), a direct application of Proposition 3-(ii) ensures that λ lies also in the right hand side of [START_REF] Davies | Spectral theory and differential operators[END_REF], so we can assume that λ ∈ σ(A). According to Proposition 5-(i), there exists λ k → λ and x k ∈ L n k such that x k = 1, x k ⇀ 0 and π n k (T -λ k )x k = 0. For all v k ∈ L n k , and hence for all

w k = (1 + K)v k ∈ (1 + K)L n k , we have 0 = (T -λ k )x k , v k = (1 + K * ) -1 (T -λ k )x k , (1 + K)v k = (1 + K * ) -1 (T -λ k )x k , w k .
Let q k be the orthogonal projection onto (1 + K)L n k . Then

q k (1 + K * ) -1 (T -λ k )x k = 0. Now (1 + K * ) -1 = 1 -K where K = K * (1 + K * ) -1 ∈ K(H). Hence q k (1 -K)(T -λ)x k → 0.
But, since T < ∞ and x k ⇀ 0, K(T -λ)x k → 0, so that also q k (T -λ)x k → 0. Thus q k (T -λ)y k → 0 for y k = (1 + K)x k ⇀ 0. By re-normalising y k in the obvious manner, we obtain a singular L-Weyl sequence for λ ∈ σ(T, (1 + K)L), ensuring [START_REF] Davies | Spectral theory and differential operators[END_REF].

To complete the proof of the first identity in the conclusion of the lemma, suppose that λ ∈ σ ess (T, L) ∩ σ disc (T ). For any µ = λ let T = T + (µ -λ)1 (λ-ε,λ+ε) (T ) where ε > 0 is sufficiently small. Then λ ∈ σ ess ( T , L) \ σ disc ( T ). By virtue of [START_REF] Davies | Spectral theory and differential operators[END_REF] and Remark 2, λ ∈ σ ess ( T , (1 + K)L) = σ ess (T, (1 + K)L) as needed.

We now show the second identity in the conclusion of the lemma. By virtue of [START_REF] Davies | Spectral pollution[END_REF] and the first identity which we just proved, it is enough to verify

σ disc (T, L) ⊂ σ(T, (1 + K)L).
This, in turns, follows from Proposition 3-(ii) and ( 4), since σ disc (T, L) ⊂ σ disc (T ) and σ(T ) ⊂ σ(T, (1 + K)L) taking into account that (1 + K)L is a T -regular sequence.

We now complete the proof of Theorem 7 by showing [START_REF] Boulton | On approximation of the eigenvalues of perturbed periodic Schrödinger operators[END_REF]. Let λ ∈ σ ess (A, L). By virtue of Lemma 9, this is equivalent to the statement

∀B ∈ F + (A), λ ∈ σ(A + B, L).
Since B ≥ 0 and a < min[σ(A + B)], according to (6) the latter is equivalent to

∀B ∈ F + (A), (λ -a) -1 ∈ σ((A + B -a) -1 , G B )
where G B = (A + B -a) -1/2 L. Since B has finite rank and is therefore compact, Lemma 10 ensures that the above in turns is equivalent to This completes the proof of Theorem 7.

∀B ∈ F + (A), (λ -a) -1 ∈ σ((A + B -a) -1 , G 0 ). Note that 0 ∈ σ((A + B -a) 1/2 (A -a) -1/2 )
Remark 5. The above proof mimics the proof of the classical Mapping Theorem for the essential spectrum which can be deduced from the characterisation

σ ess (A) = B∈K(H) σ(A + B),
see, e.g., [START_REF] Reed | Methods of Modern Mathematical Physics. I. Functionnal Analysis[END_REF]. ⋄

Stability properties of the limiting essential spectrum

In this final section we present the main contribution of this paper. It strongly depends on the validity of Theorem 7.

Theorem 11 (Weyl-type stability theorem for the limiting spectra). Let A and B be two selfadjoint operators which are bounded below. Assume that for some a < inf{σ(A), σ(B)},

(13) D((B -a) 1/2 ) = D((A -a) 1/2 ) and (14) (A -a) 1/2 ((B -a) -1/2 -(A -a) -1/2 ) ∈ K(H). Then σ ess (A, L) = σ ess (B, L)
for all sequences L = (L n ) which are simultaneously (A -a) 1/2 -regular and (Ba) 1/2 -regular.

Under Assumption ( 13), ( 14) is equivalent to the same condition with the roles of A and B reversed:

(15) (B -a) 1/2 ((A -a) -1/2 -(B -a) -1/2 ) ∈ K(H).
Note however that ( 13) and ( 14) do not imply necessarily that an A-regular sequence is also B-regular. For this it is enough to consider an example where D(A) = D(B).

Let A = ∂ 4 x with domain D(A) = H 4 (0, 1) ∩ {u(0) = u(1) = 0, u ′′ (0) = u ′′ (1) = 0} ⊂ L 2 (0, 1) = H. Let B = ∂ 4 x + |1 1|(1 -∂ 2 x ) with domain D(B) = H 4 (0, 1) ∩ u(0) = u(1) = 0, u ′′ (0) = u ′′ (1) = 1 0 u(x)dx = D(A). Then A 1/2 -∂ 2 x and B 1/2 = -∂ 2 x + |1 1| both with domain D(A 1/2 ) = D(B 1/2 ) = H 2 (0, 1) ∩ {u(0) = u(1) = 0}. Since A 1/2 (B -1/2 -A -1/2 ) = |1 1|B -1/2
is a rank-one operator, A and B satisfy the hypotheses of Theorem 11, but clearly A-regular sequences L n ⊂ D(A) \ D(B) are not B-regular. Remark 6. The KLMN theorem [START_REF] Reed | Methods of modern mathematical physics. IV. Analysis of operators[END_REF] ensures that if B -A is a densely defined symmetric A-form-bounded operator with bound less than 1, then (13) holds for a sufficiently negative. ⋄

The following example from [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF] shows that Theorem 11 cannot be easily generalised to operators which are not semi-bounded.

Example 7 (Relatively compact perturbations of the Dirac operator). Let A = D 0 and B = D 0 + V where D 0 denotes the free Dirac operator with unit mass [START_REF] Thaller | The Dirac equation[END_REF] and V ∈ C ∞ c (R 3 ) is a smooth non-negative function of compact support. The ambient Hilbert space here is H = L 2 (R 3 , C 4 ). Under the additional assumption that sup

V = ||V || L ∞ (R 3 ) < 1, it is guaranteed that 0 / ∈ σ(B). Furthermore it can be verified that D |A| 1/2 = D |B| 1/2 = H 1/2 (R 3 , C 4 ) and that |A| 1/2 |B| -1/2 -|A| -1/2 ∈ K(H).
As a consequence of [22, Theorem 2.7], it is known that there exists a B-regular

Galerkin sequence L = (L n ) such that (16) σ ess (B, L) ⊃ 0 ; sup V .
These Galerkin spaces comprise upper and lower spinors, meaning that

L n = Span f n 1 0 , ..., f n dn 0 , 0 g n 1 , ..., 0 g n d ′ n for suitable (f n j ), (g n j ) ⊂ L 2 (R 3 , C 2
). This basis is known to be free of pollution if the external field V = 0, that is

σ(A, L) = σ(D 0 ) = (-∞, -1] ∪ [1, ∞) = σ ess (A, L).
Hence σ ess (A, L) = σ ess (B, L) so Theorem 11 fails for operators which are strongly indefinite. ⋄ Proof of Theorem 11. Denote by K the operator on the left side of [START_REF] Dolbeault | On the eigenvalues of operators with gaps. Application to Dirac operators[END_REF]. Then

(17) (B -a) -1 -(A -a) -1 = (A -a) -1/2 K(B -a) -1/2 + (A -a) -1 K ∈ K(H).
Let G := (A -a) 1/2 L. According to [START_REF] Boulton | On approximation of the eigenvalues of perturbed periodic Schrödinger operators[END_REF],

λ ∈ σ ess (A, L) ⇐⇒ (λ -a) -1 ∈ σ ess (A -a) -1 , G . By Remark 2, σ ess (B -a) -1 , G = σ ess (A -a) -1 , G . Let G ′ = (B -a) 1/2 L. Then G = (A -a) 1/2 L = (A -a) 1/2 (B -a) -1/2 G ′ = (1 + K)G ′ .
Note that K = (A -a) 1/2 (B -a) -1/2 -1 and -1 ∈ σ(K) as a consequence of the fact that 0 ∈ σ((A -a) 1/2 (B -a) -1/2 ) by [START_REF] Descloux | Essential numerical range of an operator with respect to a coercive form and the approximation of its spectrum by the galerkin method[END_REF]. According to Lemma 10,

σ ess (B -a) -1 , G = σ ess (B -a) -1 , G ′ (18)
The conclusion follows by applying Theorem 7 again, this time to operator B.

Corollary 12. Let A and B be two bounded-below selfadjoint operators such that (13) holds true for some a < inf{σ(A), σ(B)}. Assume that C := B -A is a densely defined symmetric operator such that In this respect, Theorem 11 can be seen as a generalisation of these results. Although condition [START_REF] Kutzelnigg | Basis set expansion of the Dirac operator without variational collapse[END_REF] is stronger than [START_REF] Levitin | Spectral pollution and second-order relative spectra for self-adjoint operators[END_REF], the statement guarantees that the whole polluted spectrum will not move irrespectively of the (A -a) 1/2 -regular Galerkin family L and not only for those satisfying [Π, π n ] = 0 for all n. ⋄ Therefore L is compact, given the following (23) ℓ = 2, 0 < β, α < 1, 0 < r < 2, -βr -2α + 2 < 0, α > 1/2, β > 1 -1 r .

On the other hand, for ℓ = 2, σ ess (A, L) = {1, 2} and σ ess (B, L) = {1}.

This example suggests that condition [START_REF] Kutzelnigg | Basis set expansion of the Dirac operator without variational collapse[END_REF] in Corollary 12 is quasi-optimal for the stated range of β and α as illustrated by Figure 1. Note however that in this example ( 13) is only satisfied when r = ℓ. ⋄

  Hence, in total, there are at mostd(d-1) indices j such that | y k , f n d j | 2 ≥ 1/d for at least one k = 1, ..., d -1. Since d(d -1) < d 2 for d ≥ 1, we deduce that there is at least one index j =: δ d such that | y k , f n d j | 2 ≤ 1/d for all k = 1, ..., d -1.By construction y d = 1 and | y i , y j | ≤ 1/ max(i, j). Thus y k ⇀ 0 as k → ∞, ensuring (ii).

  as the corresponding operator is an invertible function of A. Now (A + B -a) -1 = (A -a) -1 + B, where B = -(A-a) -1 B(A+B-a) -1 runs over all of F -(A -a) -1 as B runs over all F + (A) and conversely. For the latter note that f ∈ F + (A) if and only if-f ((• -a) -1 ) ∈ F -((A -a) -1). Thus, once again by Lemma 9, λ ∈ σ ess (A, L) is equivalent to (λ -a) -1 ∈ σ ess ((A -a) -1 , G).

( 19 )

 19 C ∈ B(D((B -a) β ), H) and (20) (A -a) -α C(B -a) -β ∈ K(H) for some 0 ≤ α, β < 1 with α + β < 1. Then σ ess (A, L) = σ ess (B, L) for all sequences L = (L n ) which are simultaneously (A -a) 1/2 -regular and (Ba) 1/2 -regular.Remark 7. Let A be a given bounded-below selfadjoint operator and assume that A has a gap (a, b) in its essential spectrum in the following precise sense,σ ess (A) ∩ (a, b) = ∅, tr 1 (-∞,a) (A) = tr 1 (b,∞) (A) = +∞.Let Π := 1 (c,∞) (A) where a < c < b. Results shown in[START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF] ensure that, when the Galerkin spaces L n are compatible with the decomposition H = ΠH⊕(1-Π)H (i.e. when Π and π n commute for all n), there is no pollution in the gap:σ ess (A, L) ∩ (a, b) = ∅. According to [22, Corollary 2.5], when(21)(B -a) -1 C(A -a) -1/2 ∈ K(H), then σ ess (B, L) = ∅ as well.

Figure 1 .- 1 π ∞ 0 (

 10 Figure 1. The region in green colour for the parameters β and α is covered by the conditions of Corollary 12. If A and B satisfy[START_REF] Kutzelnigg | Basis set expansion of the Dirac operator without variational collapse[END_REF] for (β, α) in this region, then the limiting essential spectrum is preserved. The region in red shows the parameters β and α in condition[START_REF] Marletta | Neumann-Dirichlet maps and analysis of spectral pollution for non-self-adjoint elliptic PDEs with real essential spectrum[END_REF] of Example 9. The region in blue is generated by exchanging the roles of β and α. It is not enough for A and B to satisfy[START_REF] Kutzelnigg | Basis set expansion of the Dirac operator without variational collapse[END_REF] for (β, α) in these two regions, to guarantee preservation of the limiting essential spectrum.

  This ensures that A n d has at least d 2 eigenvalues in the interval λ -2/d, λ + 2/d . Let (f n d j ) d 2 j=1 ⊂ L n d be an orthonormal set of d 2 eigenvectors of A n d , with associated eigenvalues (λ n d j ) d 2 j=1 satisfying |λ n d j -λ| ≤ 2/d. We inductively define the following singular L-Weyl sequence for λ:

	see for instance [11, Lemma 4.1.4]. According to Lemma 6 and an inductive argu-
	ment, there is a sequence (n d ) ⊂ N and d 2 -dimensional subspaces W d ⊂ L n d , such that π n d (A -λ)y ≤ 2 d y ∀y ∈ W d .

Department of Mathematics and Maxwell Institute for Mathematical Sciences, Heriot-Watt University, Edinburgh EH14 4AS, United Kingdom E-mail address: L.Boulton@hw.ac.uk

Département de Mathématiques (CNRS-UMR 6623), UFR Sciences et techniques, 16 route de Gray, 25 030 Besanc ¸on cedex, France E-mail address: nabile.boussaid@univ-fcomte.fr

CNRS & Département de Mathématiques (CNRS-UMR 8088), Université de Cergy-Pontoise, 95 000 Cergy-Pontoise, France E-mail address: Mathieu.Lewin@math.cnrs.fr

Acknowledgement. The authors would like to acknowledge financial support from the British-French project PHC Alliance no. 22817YA. Partial support from the French Ministry of Research (ANR-10-BLAN-0101) is also acknowledged. They would also like to thank Éric Ricard for useful discussions.

Example 8 (Periodic Schrödinger operators). Let A = -∆ + V per where V per is a periodic potential with respect to some fixed lattice R ⊂ R d (for instance R = Z 3 ). Let C = W (x) be a perturbation. Assume that [START_REF] Kutzelnigg | Basis set expansion of the Dirac operator without variational collapse[END_REF] holds true for suitable α, β and a, and therefore [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF] σ ess (-

A Galerkin sequence L which does lead to any pollution in a given gap, can be found by localised Wannier functions, [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF][START_REF] Cancès | Non-perturbative embedding of local defects in crystalline materials[END_REF]. In practice, these functions can only be calculated numerically, so it is natural to ask what would be the polluted spectrum when they are known only approximately. According to [START_REF] Lewin | Spectral pollution and how to avoid it (with applications to Dirac and periodic Schrödinger operators[END_REF], the polluted spectrum will not increase in size more than that of the unperturbed operator -∆ + V per . ⋄

Example 9 (Optimality of the constants in Corollary 12). Let H, L, e ± n and f ± n be as in Example 2. Let

The matrix representation of A and B in the basis e ± n is made out of 2 × 2 blocks placed along the diagonal. More precisely

where

Fix a = 0 and let L = A -α CB -β . The matrix representation of L in the basis e ± k is L = diag[L n ] where we can calculate explicitly the entries as

n -βr-αℓ+ℓ -n -βr-αℓ+r -n -βr + n -r(β-1) (L n ) 22 = sin 2 1 n n -ℓ(α-1) -n -αℓ .