Roberta Di Gennaro

Giovanna Ilardi

Jean Vall Ès

SINGULAR HYPERSURFACES CHARACTERIZING THE LEFSCHETZ PROPERTIES

 and to give new examples of ideals failing the SLP. Finally, line arrangements are related to artinian ideals and the unstability of the associated derivation bundle is linked to the failure of the SLP. Moreover we reformulate the so-called Terao's conjecture for free line arrangements in terms of artinian ideals failing the SLP.

Introduction

The tangent space to an integral projective variety X ⊂ P N of dimension n in a smooth point P , named T P X, is always of dimension n. It is no longer true for the osculating spaces. For instance, as it was pointed out by Togliatti in [START_REF] Togliatti | Alcune osservazioni sulle superficie razionali che rappresentano equazioni di Laplace[END_REF], the osculating space T 2 P X, in a general point P , of the rational surface X defined by P 2 φ -→ P 5 , (x, y, z) → (xz 2 , yz 2 , x 2 z, y 2 z, xy 2 , x 2 y), is of projective dimension 4 instead of 5. Indeed there is a non trivial linear relation between the partial derivatives of order 2 of φ at P that define T 2 P X. This relation is usually called a Laplace equation of order 2. More generally, we will say that X satisfies a Laplace equation of order s when its s-th osculating space T s P X in a general point P ∈ X is of dimension less than the expected one, that is inf{N, n+s n -1}. The study of the surfaces satisfying a Laplace equation was developed in the last century by Togliatti [START_REF] Togliatti | Alcune osservazioni sulle superficie razionali che rappresentano equazioni di Laplace[END_REF] and Terracini [START_REF] Terracini | Sulle V k che rappresentano più di 1 2 k(k -1) equazioni di Laplace linearmente indipendenti[END_REF]. Togliatti [START_REF] Togliatti | Alcune osservazioni sulle superficie razionali che rappresentano equazioni di Laplace[END_REF] gave a complete classification of the rational surfaces embedded by linear systems of plane cubics and satisfying a Laplace equation of order two.

In the paper [START_REF] Perkinson | Inflections of toric varieties[END_REF], Perkinson gives a complete classification of smooth toric surfaces (Theorem 3.2) and threefolds (Theorem 3.5) embedded by a monomial linear system and satisfying a Laplace equation of any order.

Very recently Miro-Roig, Mezzetti and Ottaviani [START_REF] Mezzetti | Laplace Equations and the Weak Lefschetz Property[END_REF] have established a nice link between rational varieties (i.e. projections of Veronese varieties) satisfying a Laplace equation and artinian graded rings A = ⊕ 0≤i≤s A i such that the multiplication by a general linear form has not maximal rank in a degree i. On the contrary, when the rank of the multiplication map is maximal in any degree, the ring is said to have the Weak Lefschetz Property (briefly WLP). The same type of problems arises when we consider the multiplication by powers L k (k ≥ 1) of a general linear form L. Indeed, if the rank of the multiplication map by L k is maximal for any k and any degree, the ring is said to have the Strong Lefschetz Property (briefly SLP).

Third author partially supported by ANR-09-JCJC-0097-0 INTERLOW, ANR GEOLMI, the project "F.A.R.O. 2010: Algebre di Hopf, differenziali e di vertice in geometria, topologia e teorie di campo classiche e quantistiche" and by the program "Scambi internazionali tra l'Università degli Studi di Napoli Federico II ed Istituti di ricerca stranieri per la mobilità di breve durata di docenti, studiosi e ricercatori".

These properties are so called after Stanley's seminal work: the Hard Lefschetz theorem is used to prove that the ring C[x0,...,xn] (x d 0 0 ,...,x dn n )

has the SLP [START_REF] Bibliographyrichard | Weyl groups, the hard Lefschetz theorem, and the Sperner property[END_REF]Theorem 2.4]. From this example one can ask if the artinian complete intersection rings have the WLP. Actually C[x,y,z] (F0,F1,F2) has the WLP (first proved in [START_REF] Harima | The weak and Strong Lefschetz Properties for artinian K-Algebras[END_REF] and then also in [START_REF] Brenner | Syzygy bundles on P 2 and the Weak Lefschetz Property[END_REF]) but it is still not known for more than three variables. Many other questions derive from this first example. For more details about known results and some open problems we refer to [START_REF] Bibliographyjuan | A tour of the weak and strong Lefschetz properties[END_REF].

Let I = (F 1 , . . . , F r ) be an artinian ideal generated by the r forms F 1 , . . . , F r , all of the same degree d, and Syz(I) be the syzygy bundle associated to I and defined in the following way: 0 ----→ Syz(I)(d) ----→ O r P n (F1,...,Fr) ------→ O P n (d) ----→ 0.

For shortness we will denote K = Syz(I)(d) and, forgetting the twist by d, in all the rest of this text we call it the syzygy bundle. As in [START_REF] Harima | The weak and Strong Lefschetz Properties for artinian K-Algebras[END_REF], many papers about the Lefschetz properties involve the syzygy bundle. Indeed, in [3, Proposition 2.1], Brenner and Kaid prove that the graded piece of degree d + i of the artinian ring A = C[x0,...,xn] (F0,...,Fr) is H 1 (K(i)). In [ [START_REF] Mezzetti | Laplace Equations and the Weak Lefschetz Property[END_REF], thm. 3.2] the authors characterize the failure of the WLP (in degree d -1, i.e. for the map

A d-1 → A d ) when r ≤ h 0 (O L (d))
by the non injectivity of the restricted map

H 0 (O L ) r (F1,...,Fr) ------→ H 0 (O L (d)),
on a general hyperplane L.

Let us say, in few words, what we are doing in this paper and how it is organized. First of all we recall some definitions, basic facts and we propose a conjecture (Section 3). In Section 4 we extend to the SLP the characterization of failure of the WLP given in [START_REF] Mezzetti | Laplace Equations and the Weak Lefschetz Property[END_REF]. Then we translate the failure of the WLP and SLP in terms of existence of special singular hypersurfaces (Section 5). It allows us to give an answer to three unsolved questions in [START_REF] Bibliographyjuan | A tour of the weak and strong Lefschetz properties[END_REF]. In Section 6 we construct examples of artinian rings failing the WLP and the SLP by producing the appropriate singular hypersurfaces. In the last section we relate the problem of SLP at the range 2 to the topic of line arrangements (Section 7).

Let us now give more details about the different sections of this paper. In Section 4, more precisely in Theorem 4.1, we characterize the failure of the SLP by the non maximality of the induced map on sections

H 0 (O L k (i)) r (F1,...,Fr) ------→ H 0 (O L k (i + d)).
The geometric consequences of this link are explained in Section 5 (see Theorem 5.1). The non injectivity is translated in terms of the number of Laplace equations and the non surjectivity is related, via apolarity, to the existence of special singular hypersurfaces. Then we give Propositions 5.3, 5.4 and 5.5 that solve three problems posed in [START_REF] Bibliographyjuan | A tour of the weak and strong Lefschetz properties[END_REF]Problem 5.4 and Conjecture 5.13].

In Section 6 we produce many examples of ideals (monomial and non monomial) that fail the WLP and the SLP. The failure of the WLP is studied for monomial ideals generated in degree 4 on P 2 (Theorem 6.1), in degree 5 on P 2 (Proposition 6.2), in degree 4 on P 3 (Proposition 6.5); the failure of the SLP is studied for monomial ideals generated in degree 4 (Proposition 6.6); finally, we propose a method to produce non monomial ideals that fail the SLP at any range (Proposition 6.7).

In the last section Lefschetz properties and line arrangements are linked. The theory of line arrangements, more generally of hyperplane arrangements, is an old and deep subject that concerns combinatorics, topology and algebraic geometry. One can say that it began with Jakob Steiner (in the first volume of Crelles's journal, 1826) who determined in how many regions a real plane is divided by a finite number of lines. It is relevant also with Sylvester-Gallai's amazing problem. Hyperplane arrangements come back in a modern presentation in Arnold's fundamental work [START_REF] Bibliographyvaldimir | The cohomology ring of colored braid group[END_REF] on the cohomology ring of P n \ D (where D is the union of the hyperplanes of the arrangement).

For a large part of mathematicians working on arrangements, it culminates today with the Terao conjecture (see the last section of this paper or directly [START_REF] Orlik | of Grundlerhen der Mathematischen Wissenschaften[END_REF]). This conjecture concerns particularly the derivation sheaf (also called logarithmic sheaf) associated to the arrangement. In this paper we recall the conjecture. In Proposition 7.2 we prove that the failure of the SLP at the range 2 of some ideals is equivalent to the unstability of the associated derivation sheaves. Thanks to the important literature on arrangements, we find artinian ideals that fail the SLP. For instance the Coxeter arrangement, called B3, gives an original ideal that fails the SLP at the range 2 in a non trivial way (see Proposition 7.3).

We finish by a reformulation of Terao's conjecture in terms of SLP.

Notations

The ground field is C.

The dual Hom C (V, C) of a vector space V is denoted by V * . The dimension of the vector space H 0 (O P n (t)) is denoted by r t where n is clearly known in the context.

The vector space generated by the set

E ⊂ C t is < E >.
The join variety of s projective varieties X i ⊂ P n is denoted by Join(X 1 , • • • , X s ) (see [START_REF] Harris | Algebraic geometry[END_REF] for the definition of join variety).

The fundamental points (1, 0, . . . , 0), (0, 1, . . . , 0), . . . , (0, 0, . . . , 0, 1) in P n are denoted by P 0 , P 1 , . . . , P n . We often write in the same way a projective hyperplane and the linear form defining it; we use in general the notation L i on P n and the notation l i on P 2 for hyperplanes.

The ideal sheaf of a point P is I P .

Lefschetz properties

Let R = C[x 0 , . . . , x n ] = R t be the graded polynomial ring in n + 1 variables over C. The dimension of the vector space R t is r t . Let

A = R/I = m i=0
A i be a graded artinian algebra, defined by the ideal I. Note that A is finite dimensional over C. Definition 3.1. The artinian algebra A (or the artinian ideal I) has the Weak Lefschetz Property (WLP) if there exists a linear form L such that the homomorphism induced by the multiplication by L, ×L : A i → A i+1 , has maximal rank (i.e. is injective or surjective) for all i. The artinian algebra A (or the artinian ideal I) has the Strong Lefschetz Property (SLP) if there exists a linear form L such that

×L k : A i → A i+k ,
has maximal rank (i.e. is injective or surjective) for all i and k.

Remarks 1.

• It is clear that the SLP for k = 1 corresponds to the WLP. • Actually, it can be proved that if a Lefschetz element exists, then there is an open set of such elements, so that one can call "general linear form" such an element. • We will often be interested in artinian rings A that fail the SLP (or WLP), i.e. when for any linear form L there exist i and k such that the multiplication map

×L k : A i → A i+k ,
has not maximal rank. In that case we will say that A (or I) fails the SLP at range k and degree i. When k = 1 we will say simply that A fails the WLP in degree i.

One of the main examples comes from Togliatti's result (see for instance [START_REF] Brenner | Syzygy bundles on P 2 and the Weak Lefschetz Property[END_REF], Example 3.1): the ideal I = (x 3 , y 3 , z 3 , xyz) fails the WLP in degree 2. There are many ways to prove it. One of them comes from the polarity on the rational normal cubic curve. It leads to a generalization that gives one of the few known non toric examples. Proposition 3.2. ( [27, Theorem 3.1]) Let n ≥ 1 be an integer and l 1 , . . . , l 2n+1 be non concurrent linear forms on P 2 . Then the ideal

(l 2n+1 1 , . . . , l 2n+1 2n+1 , 2n+1 i=1 l i )
fails the WLP in degree 2n.

Indeed on the general line l the 2n + 2 forms of degree 2n + 1 become dependent thanks to the polarity on the rational normal curve of degree 2n + 1. We propose the following conjecture. For n = 1 it is again Togliatti's result.

Conjecture 1. Let l 1 , . . . , l 2n+1 be non concurrent linear forms on P 2 and f be a form of degree 2n + 1 on P 2 . Then the ideal (l 2n+1 1 , . . . , l 2n+1 2n+1 , f ) fails the WLP in degree 2n if and only if f ∈ (l 2n+1 1 , . . . , l 2n+1 2n+1 , 2n+1 i=1 l i ).

Lefschetz properties and the syzygy bundle

In [17, Proposition 2.3], the failure of the WLP in degree d -1 is related to the restriction of the syzygy bundle to a general hyperplane. Here we extend this relationship to the SLP situation at any range and in many degrees, by using the syzygy bundle method originated in [START_REF] Harima | The weak and Strong Lefschetz Properties for artinian K-Algebras[END_REF]. Theorem 4.1. Let I = (F 1 , . . . , F r ) ⊂ R be an artinian ideal generated by homogeneous forms of degree d and K the syzygy bundle defined by the exact sequence

0 ----→ K ----→ O r P n Φ I ----→ O P n (d) ----→ 0,
where Φ I (a 1 , . . . , a r ) = a 1 F 1 + . . . + a r F r . Let i be a non-negative integer such that h 0 (K(i)) = 0 and k be an integer such that k ≥ 1. Then I fails the SLP at the range k in degree d + i -k if and only if the induced homomorphism on sections (denoted by H 0 (Φ I,L k ))

H 0 (O L k (i)) r H 0 (Φ I,L k ) -------→ H 0 (O L k (i + d))
has not maximal rank for a general linear form L.

Remark 1. The theorem is not true if h 0 (K(i)) = 0 i.e. if there exists a syzygy of degree i among F 1 , . . . , F r . In [START_REF] Mezzetti | Laplace Equations and the Weak Lefschetz Property[END_REF] the authors consider the injectivity of the map H 0 (Φ I,L k ) for i = 0 and for r ≤ h 0 (O L (d)). In that case, since the forms F j are the generators of I, we have of course h 0 (K) = 0.

Proof. In [3, Proposition 2.1] the authors proved that

A d+i = H 1 (K(i)) for any i ∈ Z. Let us consider the canonical exact sequence 0 ----→ K(i -k) ×L k ----→ K(i) ----→ K ⊗ O L k (i) ----→ 0.
We obtain a long exact sequence of cohomology

0 → H 0 (K ⊗ O L k (i)) → A d+i-k ×L k -→ A d+i → H 1 (K ⊗ O L k (i)) → H 2 (K(i -k)) → 0.
Let us assume first that n > 2. Then we have always h 2 (K(i -k)) = 0 and it gives a shorter exact sequence:

0 -→ H 0 (K ⊗ O L k (i)) -→ A d+i-k ×L k -→ A d+i -→ H 1 (K ⊗ O L k (i)) -→ 0.
Moreover, since n > 2, we have also h 1 (O L k (i)) = 0. Then by tensoring the exact sequence defining the bundle K by O L k (i) and taking the long cohomology exact sequence, we find:

0 -→ H 0 (K ⊗ O L k (i)) -→ H 0 (O L k (i)) r H 0 (Φ I,L k ) -→ H 0 (O L k (i + d)) -→ H 1 (K ⊗ O L k (i)) → 0.
Since the kernel and cokernel of both maps, H 0 (Φ I,L k ) and ×L k are the same, the theorem is proved for n > 2.

If n = 2, let us introduce the number t = h 2 (K(i -k)). This number is equal to t = rr k-i-3r k-i-d-3 and we have a long exact sequence:

0 → H 0 (K ⊗ O L k (i)) -→ A d+i-k ×L k -→ A d+i -→ H 1 (K ⊗ O L k (i)) -→ C t → 0.
Let us consider now the long exact sequence:

0 ----→ H 0 (K ⊗ O L k (i)) ----→ H 0 (O L k (i)) r H 0 (Φ I,L k ) -------→ H 0 (O L k (i + d)) ----→ ----→ H 1 (K ⊗ O L k (i)) ----→ H 1 (O L k (i)) r ----→ H 1 (O L k (i + d)) ----→ 0. Since h 1 (O L k (i)) = h 2 (O P 2 (i -k)) = r k-i-3 (and h 1 (O L k (i + d)) = h 2 (O P 2 (i + d -k)) = r k-i-d-3 ), it remains a shorter exact sequence 0 ----→ H 0 (K ⊗ O L k (i)) ----→ H 0 (O L k (i)) r H 0 (Φ I,L k ) -------→ H 0 (O L k (i + d)) ----→ H 1 (K ⊗ O L k (i)) ----→ C t ----→ 0.
As before, since the kernel and cokernel of both maps are the same, the theorem is proved.

Let us introduce the numbers

N (r, i, k, d) := r(r i -r i-k ) -(r d+i -r d+i-k ), N + = sup(0, N (r, i, k, d)) and N -= sup(0, -N (r, i, k, d)).
The following corollary is a didactic reformulation of the theorem above.

Corollary 4.2. Assume that there is no syzygy of degree i among the F j 's. Then I fails the SLP at the range k in degree d+i-k if and only if one of the two following equivalent conditions occurs:

• h 0 (K ⊗ O L k (i)) = dim C (ker(H 0 (Φ I,L k ))) > N + , • dim C (coker(H 0 (Φ I,L k ))) > N -.
In the next section we translate this corollary in geometric terms.

Syzygy bundle and Veronese variety

We recall that the s-th osculating space T s P (X) to a n-dimensional complex projective variety X ⊂ P N at P is the subspace of P N spanned by P and by all the derivative points of degree less than or equal to s of a local parametrization of X, evaluated at P . Of course, for s = 1 we get the tangent space T P (X). A n-dimensional variety X ⊂ P N whose s-th osculating space at a general point has dimension inf( n+s n -1, N ) -δ is said to satisfy δ independent Laplace equations of order s. We will say, for shortness, that the number of Laplace equations is δ.

Remark 2. If N < n+s n -1, then there are always n+s n -1 -N linear relations between the partial derivatives. These relations are "trivial" Laplace equations of order s. We will not consider them in the following, so when we write "there is a Laplace equation of order s" we understand "a non-trivial Laplace equation of order s".

Let us briefly explain now the link with projections of v t (P n ). Let R 1 be a complex vector space of linear forms of dimension n + 1 such that H 0 O P n (1) = R 1 . We consider the Veronese embedding:

v t : P(R * 1 ) → P(R * t ) [L] → [L t ].
The image v t (P n ) is called the Veronese n-fold of order t. At the point [L t ] ∈ v t (P n ), the s-th osculating space, 1 ≤ s ≤ t -1, is the space of degree d forms possessing a factorization L t-s G where G is a form of degree s [14, Theorem 1.3]. It is identified with P(R * s ). Let us think about the projective duality in terms of derivations (it is in fact the so-called apolarity, see [START_REF] Dolgachev | Classical Algebraic Geometry: a modern view[END_REF]). A canonical basis of R * d is given by the r d derivations:

∂ d ∂x i0 0 . . . ∂x in n with i 0 + . . . + i n = d.
Let I = (F 1 , . . . , F r ) ⊂ R an ideal generated by r forms of degree d. Note that F 1 , . . . , F r are points in P(R * d ). We denote by I d the vector subspace of R d generated by the F 1 , . . . , F r and by

I d+i = R i F 1 + • • • + R i F r ,
for any i ≥ 0. Let us introduce the orthogonal vector space to I d+i i ] ∈ P(R 1 ). It is well known that the tangent spaces to the Veronese varieties can be interpreted as singular hypersurfaces. More precisely a hyperplane containing the tangent space T [L t ] v t (P n ) corresponds in the dual space P n∨ to a hypersurface of degree t that is singular at the point [L ∨ ]. More generally a hyperplane containing the s-th (s ≤ 1) osculating space T s [L t ] v t (P n ) corresponds to a hypersurface of degree t and multiplicity (s + 1) at the point [L ∨ ] (see for instance [START_REF] Bernardi | Osculating varieties of Veronese varieties and their higher secant varieties[END_REF]).

I ⊥ d+i = {δ ∈ R * d+i | δ(F ) = 0, ∀F ∈ I d+i }. It gives an exact sequence of vector spaces 0 ----→ I ⊥ d+i ----→ R * d+i ----→ I * d+i ----→
Thus the dual variety of v t (P n ) is the discriminant variety that parametrizes the singular hypersurfaces of degree t when the s-th osculating variety of v t (P n ) parametrizes the hypersurfaces of degree t with a point of multiplicity s + 1.

We propose now an extended version of the "main" theorem of [START_REF] Mezzetti | Laplace Equations and the Weak Lefschetz Property[END_REF] (to be precise Theorem 3.2).

Theorem 5.1. Let I = (F 1 , . . . , F r ) ⊂ R be an artinian ideal generated by r homogeneous polynomials of degree d. Let i, k, δ be integers such that i ≥ 0, k ≥ 1. Assume that there is no syzygy of degree i among the F j 's. The following conditions are equivalent:

(1) The ideal I fails the SLP at the range k in degree d + i -k.

(2) There exist

N + + δ, with δ ≥ 1, independent vectors (G 1j , . . . , G rj ) j=1,...,N + +δ ∈ R ⊕r i and N + + δ forms G j ∈ R d+i-k such that G 1j F 1 + . . . + G rj F r = L k G j for a general linear form L of P n . (3) The n-dimensional variety π I d+i (v d+i (P n )) satisfies δ ≥ 1 Laplace equations of order d + i -k. (4) For any L ∈ R 1 , dim C ((I ⊥ d+i ) * ∩ H 0 (I d+i-k+1 L ∨ (d + i)) ≥ N -+ δ, with δ ≥ 1.
Proof. The equivalence (1) ⇔ (2) is proved in Theorem 4.1.

Since I is generated in degree d, the map R i × I d → I d+i is surjective and the relation

G 1 F 1 + . . . + G r F r = L k G is equivalent to P(I * d+i ) ∩ T d+i-k [L d+i ] v d+i (P n ) = ∅.
More generally the number of independent relations G 1j F 1 + . . . + G rj F r = L k G j is the dimension of the kernel of the map H 0 (Φ I,L k ) i.e. the dimension of H 0 (K ⊗ O L k (i)); this number of independent relations, written in a geometric way, is

N + + δ = dim[P(I * d+i ) ∩ T d+i-k [L d+i ] v d+i (P n )] + 1, (δ ≥ 0)
where the projective dimension is -1 if the intersection is empty. The number δ is the number of (non trivial) Laplace equations. Indeed, the dimension of the (d + i -k)-th osculating space to π I d+i (v d+i (P n )) is r d+i-k -N + -δ since the (d + i -k)-th osculating space to v d+i (P n ) meets the center of projection along a P N + +δ-1 . In other words, the n-dimensional variety π I d+i (v d+i (P n )) satisfies δ Laplace equations and ( 3) is equivalent to [START_REF] Bernardi | Osculating varieties of Veronese varieties and their higher secant varieties[END_REF].

The image by π I d+i of the (d + i -k)-th osculating space to the Veronese v d+i (P n ) in a general point has codimension h 0 (K⊗O L k (i))-N + in P(I ⊥ d+i ). The codimension corresponds to the number of hyperplanes in P(I ⊥ d+i ) containing the osculating space to π I d+i (v d+i (P n )). These hyperplanes are images by π I d+i of hyperplanes in P(R * d+i ) containing P(I * d+i ) and the (d + i -k)-th osculating plane to v d+i (P n ) at the point [L d+i ]. In the dual setting it means that these hyperplanes are forms of degree d + i in (I ⊥ d+i ) * with multiplicity (d

+ i -k + 1) at [L ∨ ]. It proves that (3) is equivalent to (4).
To summarize, the number of Laplace equations is h Geometrically it can be described as

0 (K ⊗ O L k ) -N + and coker(H 0 (Φ I,L k )) (I ⊥ d+i ) * ∩ H 0 (I d+i-k+1 L ∨ (d + i)).
P(I * d+i ) = Join(T i [L d+i 1 ] v d+i (P n ), • • • , T i [L d+i r
] v d+i (P n )). 3. By the theorem above, when N (r, i, k, d) ≥ 0, the ideal I = (L d 1 , . . . , L d r ) fails the SLP at the range k in degree d -k + i if and only if the following intersection is not empty:

Join(T i [L d+i 1 ] v d+i (P n ), • • • , T i [L d+i r ] v d+i (P n )) ∩ T d+i-k [L d+i ] v d+i (P n ). 4.
Here we focus the attention also on the number δ of Laplace equations satisfied by π I d+i (v d+i (P n )).

The geometric meaning of this number was highlighted by Terracini [START_REF] Terracini | Sulle V k che rappresentano più di 1 2 k(k -1) equazioni di Laplace linearmente indipendenti[END_REF] for Laplace equations of order 2 and recently for any order by [START_REF] De Poi | On varieties with higher osculating defect[END_REF], where a classification of varieties satisfying "many" Laplace equations is given.

The characterization of the failure of the SLP by the existence of ad-hoc singular hypersurfaces allows us to answer, in the three following propositions, some questions posed by Migliore and Nagel. Let us recall their questions:

Problem 1. [18, Problem 5.4] Let I = (x N 1 , x N 2 , x N 3 , x N 4 , L N
) for a general linear form L. R/I fails the WLP, for N = 3, ..., 12. There are some natural questions arising from this example:

(1) Prove the failure of the WLP in previous example for all N ≥ 3.

(2) What happens for mixed powers? Since all these results concern powers of linear forms, let us first verify that the hypothesis on the global syzygy in Theorem 5.1 is not restrictive. Lemma 5.2. Let I be the ideal (L d 1 , . . . , L d r ) where the L j are linear forms and r < r d . Let K be its syzygy bundle. Then h 0 (K(i)) = 0 ⇔ rr i ≤ r d+i .

Proof. One direction is obvious. Let us assume that rr i ≤ r d+i and that there exists a relation

G 1 L d 1 + . . . + G r L d r = 0, with G 1 , . . . , G r forms of R i .
Both hypotheses imply that the projective space Join(T i

[L d+i 1 ] v d+i (P n ), • • • , T i [L d+i r ] v d+i (P n ))
has dimension strictly less than the expected one. Since the linear forms are general, it implies that the algebraic closure of ∪ L∈R d+i

1 T i [L d+i ] v d+i (P n ) has not the expected dimension. It contradicts the lemma 3.3 in [2].
Proposition 5.4 is already proved in [START_REF] Harbourne | Inverse systems, Gelfand-Tsetlin patterns and the weak Lefschetz property[END_REF]Lemma 4.8] and also in [START_REF] Bibliographyjuan | On the weak lefschetz property for powers of linear forms[END_REF]Theorem 4.2 (ii)]. We propose here a new proof based on the existence of a singular hypersurface characterizing the failure of the SLP. Let us mention that, on P 2 a hypersurface of degree d + i with a point of multiplicity d + i is simply an union of lines (as, for instance, in Theorem 6.1 and Proposition 6.2), but on P n , with n > 2, a hypersurface of degree d + i with a point of multiplicity d + i is more generally a cone over a hypersurface in the hyperplane at infinity. This is the key argument in the proofs of the three following propositions. Proposition 5.3. Let N be an integer such that N ≥ 3. Then the ideal (x N 0 , x N 1 , x N 2 , x N 3 , (x 0 + x 1 + x 2 + x 3 ) N ) fails the WLP in degree 2N -3.

Remark 4.

Of course it is equivalent to say that (L N 1 , . . . , L N 5 ) fails the WLP in degree 2N -3 for L 1 , . . . , L 5 general linear forms.

Proof. Let us consider the syzygy bundle associated to the linear system 0 ----→ K ----→ O 5

P 3 (x N 0 ,x N 1 ,x N 2 ,x N 3 ,(x0+x1+x2+x3) N ) ----------------------→ O P 3 (N ) ----→ 0. Since 5r N -2 < r 2N -2 Lemma 5.2 implies h 0 (K(N -2)) = 0. Let L be a linear form. When N ≥ 3 we have 5h 0 (O L (N -2)) ≥ h 0 (O L (2N -2)
). According to Theorem 5.1 the failure of the WLP in degree 2N -3 is equivalent to the existence of a surface with multiplicity N -1 in the points P 0 , P 1 , P 2 , P 3 and P (1, 1, 1, 1) and multiplicity 2N -2 at a moving point M . The five concurrent lines in M passing through P 0 , P 1 , P 2 , P 3 , P belong to a quadric cone with equation {F = 0} (the cone over the conic at infinity through the five points). Since

F N -1 ∈ H 0 (I 2N -2 M (2N -2)
) the hypersurface {F N -1 = 0} has the desired properties.

In P n there is always a quadric through n(n+3) 2 points in general position. Then given any general point M ∈ P n+1 , there is a quadratic cone with a vertex at M and passing through n(n+3) 2 fixed points in general position. Then we prove, Proposition 5.4. In the following cases the ideal (L N 1 , . . . , L N n(n+3) 2

) fails the WLP in degree 2N -3:

• N = 3 and n ≥ 2,

• N = 4 and 2 ≤ n ≤ 4,

• N > 4 and 2 ≤ n ≤ 3.

Proof. Let us consider the syzygy bundle associated to the linear system

0 ----→ K ----→ O n(n+3) 2 P n+1 ----→ O P n+1 (N ) ----→ 0.
Let L a linear form. Then the inequality n(n+3)

2 h 0 (O L (N -2)) ≥ h 0 (O L (2N -2)
) is true if and only if N and n are one of the possibilities stated in the theorem. In all these cases we have Proof. Since 8r 1 < r 4 Lemma 5.2 implies h 0 (K(1)) = 0. We have to prove that, on a general hyperplane L, the cokernel of H 0 (O L (1)) 8 ----→ H 0 (O L (4)) has dimension strictly greater than h 0 (O L (4)) -h 0 (O L (1)) 8 = 78. The dimension of this cokernel is the dimension of the quartics with a quadruple point [L ∨ ] and 8 double points. We consider on the hyperplane at infinity the vector space V of quadrics through the images of the 8 points

[L ∨ 1 ], . . . , [L ∨ 8 ]
. It has dimension 13. Let Q 1 , . . . , Q 13 be a basis of this space of quadrics. Then the vector space Sym 2 (V ) of quartics generated by the products Q i Q j has dimension 91 and all these quartics are singular in the 8 points. In P 6 the independent quartic cones over these quartics belong to the cokernel.

In the next section, we propose many examples of ideals failing the WLP or the SLP by producing ad-hoc singular hypersurfaces.

6. Classes of ideals failing the WLP and the SLP 6.1. Monomial ideals coming from singular hypersurfaces. In their nice paper about osculating spaces of Veronese surfaces, Lanteri and Mallavibarena remark that the equation of the curve given by three concurrent lines depends only on six monomials instead of seven. More precisely let us consider a cubic with a triple point at (a, b, c) passing through P 0 , P 1 and P 2 . Its equation is (bz -cy)(az -cx)(ay -bx) = 0 and it depends only on the monomials x 2 y, xy 2 , x 2 z, xz 2 , y 2 z, yz 2 . So there is a non zero form in

(I ⊥ 3 ) * =< x 2 y, xy 2 , x 2 z, xz 2 , y 2 z, yz 2 > R 3 < x 3 , y 3 , z 3 , xyz >
that is triple at a general point. In this way they explain the Togliatti surprising phenomena ( [15, Theorem 4.1], [START_REF] Ilardi | Togliatti systems[END_REF] and [START_REF] Franco | On a theorem of Togliatti[END_REF]).

We apply this idea in our context. Recall that in the monomial case being artinian to the ideal I means that it contains the forms x d 0 , . . . , x d n . Let us consider the (n + 1) fundamental points P 0 , P 1 , . . . , P n and let us assume that the number r of monomials generating I is chosen such that N (r, i, k, d) = 0 for i ≥ 0, k ≥ 1 fixed integers. Then, as it is noted in item 1 of Remarks after Theorem 5.1, the ideal I fails the SLP at the range k in degree d + i -k if and only if there exists at any point M a hypersurface of degree d + i with multiplicity d + i -k + 1 at M given by a form in (I ⊥ d+i ) * R d+i /I d+i . We have to write this equation with a number of monomials as small as possible. Then the orthogonal space becomes bigger and we will cover all the possible choices.

First of all we describe exhaustively the monomial ideals (x 4 , y 4 , z 4 , f, g) ⊂ C[x, y, z] of degree 4 that do not verify the WLP. Theorem 6.1. Up to permutation of variables the monomial ideals generated by five quartic forms in C[x, y, z] that fail the WLP in degree 3 are the following

• I 1 = (x 4 , y 4 , z 4 , x 3 z, x 3 y),

• I 2 = (x 4 , y 4 , z 4 , x 2 y 2 , xyz 2 ).

Remark 5. Geometrically it is evident that the first ideal (x 4 , y 4 , z 4 , x 3 z, x 3 y) fails the WLP. Indeed under the Veronese map, a linear form L becomes a rational normal curve of degree four that defines a projective space P 4 and, modulo L, the restricted monomials xi ȳj can be interpreted as points of this P 4 . Then the tangent line to the rational quartic curve at the point [x 4 ] contains the two points [x 3 ȳ] and [x 3 z]. This line meets the plane P(< x4 , ȳ4 , z4 >) in one point; it implies that dim C < x4 , ȳ4 , z4 , x3 ȳ, x3 z >≤ 4. For the second ideal, it is not evident to see that the line P(< x2 ȳ2 , xȳz 2 >) always (for any restriction) meets the plane P(< x4 , ȳ4 , z4 >).

Proof. Let us consider the points P 0 , P 1 and P 2 and the degree 4 curves with a quadruple point in (a, b, c) passing through these three points. These curves are product of four lines:

f (x, y, z) = (ay -bx)(cx -az)(cy -bz)(α(ay -bx) + β(cx -az)) = 0.
Expanding f explicitly in the coordinates (x, y, z), we see that the forms x 4 , y 4 , z 4 are missing (a, b, c)

P 2 P 1 P 0 Figure 1.
Quartic with a quadruple point and that twelve monomials appear to write its equation. Since we want only ten monomials, we have to remove two. The following possibilities occur:

• α = 0 (or equivalently by permutation of variables [β = 0] or [α = 0, β = 0 and bα = cβ]) then the remaining linear system is (x 4 , y 4 , z 4 , y 3 z, xy 3 ). It corresponds to the first case i.e. to the ideal I 1 . • α = 0 and β = 0 but cβ+bα = 0 (or equivalentely by permutation of variables [2bα-cβ = 0] or [bα-2cβ = 0]) then the remaining linear system is (x 4 , y 4 , z 4 , x 2 yz, y 2 z 2 ). It corresponds to the second case i.e. to the ideal I 2 .

Remark 6. The quartic curve with multiplicity four in (a, b, c) consists, in the first case, of two lines and a double line that are concurrent; in the second case of four concurrent lines in harmonic division.

We do not apply the same technique to describe exhaustively the monomial ideals (x 5 , y 5 , z 5 , f, g, h) ⊂ C[x, y, z] of degree 5 that do not verify the WLP because the computations become too tricky. But we can give some cases by geometric arguments. Proposition 6.2. The following monomial ideals

• (x 5 , y 5 , z 5 , x 3 y 2 , x 3 z 2 , x 3 yz),

• (x 5 , y 5 , z 5 , x 4 z, x 4 y, m), where m is any monomial,

• (x 5 , y 5 , z 5 , x 3 y 2 , x 2 y 3 , x 2 y 2 z), fail the WLP in degree 4.

Proof. Under the Veronese map, a linear form L becomes a rational normal curve of degree five that defines a projective space P 5 and, modulo L, the restricted monomials xi ȳj can be interpreted as points of this P 5 . Then the tangent line the rational quintic curve at the point [x 5 ] contains the two points [x 4 ȳ] and [x 4 z]. This line meets the plane P(< x5 , ȳ5 , z5 >) in one point; it implies that dim C < x5 , ȳ5 , z5 , x4 ȳ, x4 z, m >≤ 5. In the same way the osculating plane at [x 5 ] i.e. P(< x3 ȳ2 , x3 z2 , x3 ȳz >) meets the plane P(< x5 , ȳ5 , z5 >) in one point. In the last case, the geometric argument is not so evident. Let us set X = bz -cy and Y = cx -az. Then the equation of the product of the five concurrent lines is f (X(x, y, z), Y (x, y, z)

) = XY (aX + bY )(αX + βY )(γX + δY ) = aαγX 4 Y + (aαγ + bαγ + aαδ)X 3 Y 2 + (bβγ + bαδ + aβδ)X 2 Y 3 + bβδXY 4 = 0.
For any point M (a, b, c, d) we choose (α, β, γ, δ) such that aαγ + bαγ + aαδ = 0 and bβγ + bαδ + aβδ = 0. Then the equation depends only on 15 monomials and the remaining monomials are (x 5 , y 5 , z 5 , x 3 y 2 , x 2 y 3 , x 2 y 2 z).

We describe now some monomial ideals in C[x, y, z, t], generated in degree 3, that do not verify the WLP. Proposition 6.3. The monomial ideals I = (x 3 , y 3 , z 3 , t 3 , f 1 , f 2 , f 3 , f 4 , f 5 , f 6 ) where the forms f i are chosen among one of the following sets of monomials:

• {x 2 y, xy 2 , x 2 z, x 2 t, y 2 z, y 2 t, z 2 t, zt Remark 7. We do not know if under permutation of variables the description above is exhaustive or not. The singular cubic that we are considering here are union of concurrent planes and not all the cubic cones.

Proof. We look for a surface of degree 3 with multiplicity 3 at a general point M (a, b, c, d) that passes through the points P 0 , P 1 , P 2 , P 3 such that its equation depends only on the remaining monomials in R 3 /I 3 . Such a cubic surface is a cone over a cubic curve. Here, instead of a general cubic cone we consider only three concurrent planes. Since these 3 planes have to pass through P 0 , P 1 , P 2 and P 3 it remains only, after a simple verification, the following cases:

• (e) Case (B1)

• (B1) The equation of the cubic is (cy -bz)(dz -ct)(dy -bt) = 0.

If we want I 3 to be of dimension r < 10 (for instance r = 8) we need 10 -r + 1 independent cubics with a triple point. So, to get the failure of the WLP, we need 10 -r + 1 independent cubics with a triple point. Let us recover with our method two linear systems of eight cubic forms (the complete classification is already done in [START_REF] Mezzetti | Laplace Equations and the Weak Lefschetz Property[END_REF]Theorem 4.10]) that fail the WLP in degree 2.

Proposition 6.4. The following monomial ideals

• I = (x 3 , y 3 , z 3 , t 3 , x 2 y, xy 2 , zt 2 , z 2 t),

• J = (x 3 , y 3 , z 3 , t 3 , xyz, xyt, xzt, yzt) fail the WLP in degree 2. (ct -dz)(at -dx)(ay -bx) = 0, (ct -dz) 2 (ay -bx) = 0, (ct -dz)(ay -bx) 2 = 0.

They are particular cases of type (A) in the proof of Proposition 6.3. They are linearly independent and can be written with twelve monomials. Then it remains only 8 forms for I 3 : I = (x 3 , y 3 , z 3 , t 3 , x 2 y, xy 2 , zt 2 , z 2 t).

Let us consider the following three forms defining singular cubics passing through the basis points and the general point (a, b, c, d):

(bz -cy)(az -cx)(ay -bx) = 0, (bx -ay)(at -dx)(dy -bt) = 0, (az -cx)(dx -at)(dz -ct) = 0.

They are cases of type (B1) in the proof of Proposition 6.3. They are linearly independent and can be written with twelve monomials: (x 2 y, x 2 z, xy 2 , xz 2 , y 2 z, yz 2 , t 2 y, t 2 z, ty 2 , tz 2 , t 2 x, x 2 t).

It remains only J = (x 3 , y 3 , z 3 , t 3 , xyz, xyt, xzt, yzt).

Of course the same argument (concurrent planes or hyperplanes) can be used in degree or dimension bigger than 3. For instance let us give a set of monomial ideals in C[x, y, z, t], generated in degree 4 that fail the WLP. Proposition 6.5. Let f 1 , . . . , f 11 be eleven monomials chosen among x 3 y, x 3 z, x 3 t, xy 3 , xz 3 , xt 3 , y 3 z, y 3 t, yz 3 , yt 3 , z 3 t, zt 3 , x 2 y 2 , z 2 t 2 , y 2 z 2 , x 2 t 2 .

Then the ideal I = (x 4 , y 4 , z 4 , t 4 , f 1 , . . . , f 11 ) fails the WLP in degree 3.

Proof. At any point M = (a, b, c, d) an equation of a surface of degree 4 with multiplicity 4 at M that passes through the points P 0 , P 1 , P 2 , P 3 is given by f (x, y, z, t) = (ct -dz)(at -dx)(ay -bx)(bz -cy) = 0.

We conclude this section with an example that fails the SLP at the range 2. Proposition 6.6. The ideal I = (x 4 , y 4 , z 4 , xy 3 , xz 3 , x 2 yz, y 2 z 2 , y 3 z, yz 3 ) ⊂ C[x, y, z] fails the SLP at the range 2 in degree 2.

Proof. Let P 0 , P 1 , P 2 and M (a, b, c) be four points. We consider the quartic curve consisting of the union of the four lines (M P 0 ), (M P 1 ), (M P 2 ) and (P 0 P 1 ). It is a quartic passing through P 0 , P 1 , P 2 and triple at M (a, b, c). It depends on the six monomials x 3 y, x 3 z, x 2 y 2 , xy 2 z, x 2 z 2 , xyz 2 . Then it remains 9 = 15 -6 monomials I 4 =< x 4 , y 4 , z 4 , xy 3 , xz 3 , x 2 yz, y 2 z 2 , y 3 z, yz 3 > .

The associated syzygy bundle K verifies h 0 (K ⊗ O L 2 ) = 0 for a general linear form L. It proves that I = (x 4 , y 4 , z 4 , xy 3 , xz 3 , x 2 yz, y 2 z 2 , y 3 z, yz 3 ) fails the SLP at the range 2 in degree 2. With this method it is always possible to find systems of any degree that fail the SLP by exhibiting a curve of degree d with multiplicity d -k + 1 at a general point P . But one can find some set of points for which these special curves do not split as product of lines (see Proposition 7.3 in the next section).

SLP at the range 2 and line arrangements on P 2

A line arrangement is a collection of distinct lines in the projective plane. Arrangement of lines or more generally arrangement of hyperplanes is a famous and classical topic that has been studied by many authors for a very long time (see [START_REF] Cartier | Les arrangements d'hyperplans: un chapitre de géométrie combinatoire[END_REF] or [START_REF] Orlik | of Grundlerhen der Mathematischen Wissenschaften[END_REF] for a good introduction).

Let us denote by f = 0 the equation of the union of lines of the considered arrangement. Another classical object associated to the arrangement is the vector bundle D 0 defined as the kernel of the jacobian map:

0 ----→ D 0 ----→ O 3 P 2 (∂f ) ----→ O P 2 (d -1).
The bundle D 0 is called derivation bundle (sometimes logarithmic bundle ) of the line arrangement (see [START_REF] Saito | Theory of logarithmic differential forms and logarithmic vector fields[END_REF] and [START_REF] Bibliographyhenry | Elementary modifications and line configurations in P 2[END_REF] for an introduction to derivation bundles).

One can think about the lines of the arrangement in P 2 as a set of distinct points Z in P 2∨ . Then we will denote by D 0 (Z) the associated derivation bundle.

The arrangement of lines is said free with exponents (a, b) when its derivation bundle splits on P 2 as a sum of two line bundles, more precisely when

D 0 (Z) = O P 2 (-a) ⊕ O P 2 (-b).
The splitting of D 0 (Z) over a line l ⊂ P 2 is related to the existence of curves (with a given degree a + 1) passing through Z that are multiple (with multiplicity a) at l ∨ ∈ P 2∨ . More precisely, Lemma 7.1. ( [28, Proposition 2.1]) Let Z ⊂ P 2∨ be a set of a+b+1 distinct points with 1 ≤ a ≤ b and l be a general line in P 2 . Then the following conditions are equivalent:

(

) D 0 (Z) ⊗ O l = O l (-a) ⊕ O l (-b). 1
(2) h 0 ((J Z ⊗ J a l ∨ )(a + 1)) = 0 and h 0 ((J Z ⊗ J a-1 l ∨ )(a)) = 0. In our context it implies the following characterization of unstability. We recall that a rank two vector bundle E on P n , n ≥ 2 is unstable if and only if its splitting

E l = O l (a) ⊕ O l (b) on a general line l verifies | a -b |≥ 2.
This characterization is a consequence of the Grauert-Mülich theorem, see [START_REF] Okonek | Vector bundles on complex projective spaces[END_REF]. Let us give now an ideal generated by non monomials quartic forms that fails the SLP at the range 2. It comes from a line arrangement, called B3 arrangement (see [START_REF] Orlik | of Grundlerhen der Mathematischen Wissenschaften[END_REF]Pages 13,[START_REF] Terracini | Sulle V k che rappresentano più di 1 2 k(k -1) equazioni di Laplace linearmente indipendenti[END_REF] and 287]), such that the associated derivation bundle is unstable (in fact even decomposed). The existence of a quartic curve with a general triple point is the key argument. But contrary to the previous examples, this quartic is irreducible and consequently not obtainable by Proposition 6.7. Proof. Consider the set Z of the nine dual points of the linear forms x, y, z, x+y, x-y, x+z, x-z, y+ z, y -z. Let I be the artinian ideal (x 4 , y 4 , z 4 , (x + y) 4 , (x -y) 4 , (x + z) 4 , (x -z) 4 , (y + z) 4 , (y -z) 4 ) and K its syzygy bundle. The derivation bundle of the arrangement is D 0 (Z) = O P 2 (-3)⊕O P 2 (-5) (it is free with exponents [START_REF] Brenner | Syzygy bundles on P 2 and the Weak Lefschetz Property[END_REF][START_REF] De Poi | On varieties with higher osculating defect[END_REF]; see [START_REF] Orlik | of Grundlerhen der Mathematischen Wissenschaften[END_REF] for a proof). Then, according to the Lemma 7.1 there is at any point P a degree 4 curve with multiplicity 3 at P passing through Z. In other words, by Theorem 5.1, I fails the SLP at the range 2 and degree 2. ) fails the SLP at the range 2 and degree a+b 2 . Proof. Let us denote by Z = {l ∨ 1 , . . . , l ∨ a+b+1 } the dual set of points of A. Since there exists at any general point l ∨ a curve of degree a + 1 passing through Z, the Lemma 7.1 implies that D 0 (Z) is unstable and Proposition 7.2 implies that I fails the SLP at the range 2 and degree a+b 2 -1.

7.1. SLP at the range 2 and Terao's conjecture. One of the main conjecture about hyperplane arrangements (still open also for line arrangements) is Terao's conjecture. It concerns the free arrangements. The conjecture says that freeness depends only on the combinatorics of the arrangement. Let us recall that the combinatorics of the arrangement A = {l 1 , . . . , l n } is determined by an incidence graph. Its vertices are the lines l k and the points P i,j = l i ∩ l j . Its edges are joining l k to P i,j when P i,j ∈ l k . We refer again to [START_REF] Orlik | of Grundlerhen der Mathematischen Wissenschaften[END_REF] for a good introduction to the subject. Terao's conjecture is valid not only for line arrangement but more generally for hyperplane arrangements.

Conjecture 3 (Terao). The freeness of a hyperplane arrangement depends only on its combinatorics.

  0 and the corresponding projection map π I d+i : P(R * d+i )/P(I * d+i ) → P(I ⊥ d+i ) Of course one can identify R d+i /I d+i (I ⊥ d+i ) * and write the decomposition R d+i = I d+i ⊕(I ⊥ d+i ) * . Remark 3. In the following two situations, the vector space (I ⊥ d ) * is easy to describe: (1) When I d is generated by r monomials of degree d, (I ⊥ d ) * is generated by the remaining r d -r monomials. (2) When I d = (L d 1 , . . . , L d r ) where [L i ] ∈ P(R * 1 ), (I ⊥ d ) * is generated by degree d polynomials that vanish at the points [L ∨

Remarks 2 . 1 .

 21 Let us explain the geometric meaning of Theorem 5.1 4 in a simple case: if N -= 0, then 4 means that I fails the SLP at the range k in degree d + i -k if and only if there exists at any point M ∈ P n a hypersurface of degree d + i with multiplicity d + i -k + 1 at M given by a form in (I ⊥ d+i ) * R d+i /I d+i . 2. Let I = (L d 1 , . . . , L d r ) where L 1 , . . . , L r are general linear forms. The vector space (I ⊥ d+i ) * , whereI d+i = L d 1 R i + . . . + L d r R i ,is the vector space of the forms of degree d + i vanishing in r points [L ∨ j ] with multiplicity (i + 1). In other words f ∈ ∩ r j=1 H 0 (I i+1 L ∨ j (d + i)) (see [8, Corollary 3]).

( 3 ) 4 ?

 34 What happens for almost complete intersections, that is, for r + 1 powers of general linear forms in r variables when r ≥ Conjecture 2. [18, Conjecture 5.13] Let L 1 , . . . , L 2n+2 be general linear forms and I = (L d 1 , . . . , L d 2n+2 ) (1) If n = 3 andd = 3 then R/I fails the WLP. (2) If n ≥ 4 then R/I fails the WLP if and only if d > 1. We prove 1 of [18, Problem 5.4] in Proposition 5.3, 3 of [18, Problem 5.4], for r = 4 and N = 4, in Proposition 5.4 and 1 of [18, Conjecture 5.13] in Proposition 5.5.

n(n+3) 2 r 2 M(

 22 N -2 ≤ r 2N -2 , and by Lemma 5.2, h 0 (K(N -2)) = 0. According to Theorem 5.1 the failure of the WLP is equivalent to the existence of a hypersurface with multiplicity N -1 in the points [L ∨ i ] and multiplicity 2N -2 at the moving point M . The lines through M and [L ∨ i ] belong to a quadratic cone with equation {F = 0} (the cone over the quadric at infinity through the points). Since F N -1 ∈ H 0 (I 2N -2N -2)) the hypersurface {F N -1 = 0} has the desired properties.Proposition 5.5. The ideal I = (L 3 1 , . . . , L 3 8 ) fails the WLP in degree 3 where L 1 , . . . , L 8 be general linear forms on P 6 .

  A1) The equation of the cubic is (bx -ay)(dz -ct) 2 = 0. • (A2) The equation of the cubic is (bx -ay)(dz -ct)(cx -az) = 0. • (A3) The equation of the cubic is (bx -ay)(dz -ct)(bx + ay + udz + uct) = 0 where at any point (a, b, c, d) the function u(a, b, c, d) verifies ab + u(a, b, c, d)cd = 0. • (A4) The equation of the cubic is (bx -ay)(dz -ct)(bdx + ady -2abt) = 0.

  (a) Case (A1).(b) Case (A2).

( c )

 c Case (A3). (d) Case (A4).

Remark 8 .

 8 The ideals I and J correspond respectively to the cases (3) and (1) in [17, Theorem 4.10]. Proof. Let us consider the following three forms defining singular cubics passing through the fundamental points and a general point (a, b, c, d):

6. 2 .Proposition 6 . 7 .

 267 Non monomial examples coming from singular hypersurfaces. Let us study now the interesting caseI ⊥ d = H 0 (I Z (d)) *where Z is a finite set of distinct points in P 2∨ of length |Z| and I Z its ideal sheaf. The set Z corresponds by projective duality to a set of |Z| distinct lines in P 2 defined by linear forms l 1 , . . . , l |Z| . We will now consider the idealI ⊂ R generated by (l d 1 , . . . , l d |Z| ). We have |Z| = dim C I d . Let k ≥ 1, r = r d -r d-k and Z = {l ∨ 1 , .. . , l ∨ r } a finite set of r distinct points in P 2∨ where l i are linear forms on P 2 . Assume that there exists a subsetZ 1 ⊂ Z, of length r -d + k -1, contained in a curve Γ 1 of degree k -1. Then the ideal I = (l d 1 , . . . , l d r ) fails the SLP at the range k in degree d -k.Proof. The union of Γ 1 and (d -k + 1) concurrent lines at a point P passing through the remaining points Z \ Z 1 , is a non zero section of H 0 (I Z ⊗ I d-k+1 P (d)). By Theorem 5.1 it proves that I fails the SLP at the range k in degree d -k.

Proposition 7 . 2 .

 72 Let I ⊂ R = C[x, y, z] be an artinian ideal generated by 2d + 1 polynomials l d 1 , . . . , l d 2d+1 where l i are distinct linear forms in P 2 . Let Z = {l ∨ 1 , . . . , l ∨ 2d+1 } be the corresponding set of points in P 2∨ . Then the following conditions are equivalent:(1) The ideal I fails the SLP at the range 2 in degree d -2.(2) The derivation bundle D 0 (Z) is unstable.Proof. The failure of the SLP at the range 2 in degree d -2 is equivalent to the existence at a general point l ∨ of a curve of degree d with multiplicity d -1 at l ∨ belonging to I ⊥ d = H 0 (I Z (d)). By the lemma 7.1 it is equivalent to the following splittingD 0 (Z) ⊗ O l = O l (d -s) ⊕ O l (d + s) with s > 0,on a general line l. In other words the failure of the SLP is equivalent to have a non balanced decomposition and according to Grauert-Mülich theorem it is equivalent to unstability.

Proposition 7 . 3 .

 73 The idealI = (x 4 , y 4 , z 4 , (x + y) 4 , (x -y) 4 , (x + z) 4 , (x -z) 4 , (y + z) 4 , (y -z) 4 ) ⊂ C[x, y, z]fails the SLP at the range 2 and degree 2.

Figure 2 . 1 , . . . , l a+b 2 a+b+1) 1 . 9 . 2 1,

 212192 Figure 2. Dual set of points of the B3 arrangement

  2 , xyz, xyt}, (Case (A1)) • {x 2 y, xy 2 , xz 2 , y 2 z, yz 2 , y 2 t, zt 2 , z 2 t}, (Case (A2)) • {x 2 y, xy 2 , z 2 t, zt 2 , xyz, xyt, xzt, yzt}, (Case (A3)) • {xz 2 , yz 2 , xyz, xyt, x 2 y, xy 2 , z 2 t, zt 2 }, (Case (A4)) • {x 2 y, xy 2 , x 2 z, xz 2 , x 2 t, xt 2 , xyz, xzt, xyt, yzt}, (Case (B1)) fail the WLP in degree 2.

In other words an arrangement with the same combinatorics of a free arrangement is free, too. Let us consider a free arrangement A 0 = {h 1 , . . . , h n } with exponents (a, b) (a ≤ b) and let us denote by Z 0 its dual set of points. We assume that Terao's conjecture is not true i.e, that there exists a non free arrangement A = {l 1 , . . . , l n } with the same combinatorics of A 0 . Let us add b -a points {M 1 , . . . , M b-a } in general position to Z 0 in order to form Γ 0 and to th dual set Z ofA to form Γ. Then the length of both sets of points is 2b + 1. On the general line l we have

when, since Z is not free, we have a less balanced decomposition for D 0 (Z) (this affirmation is proved in [START_REF] Elencwajg | Bounding cohomology groups of vector bundles on Pn[END_REF]):

It implies that h 0 (I Z ⊗ I a-1 l ∨ (a)) = 0, h 0 (I Z0 ⊗ I a-1 l ∨ (a)) = 0 and h 0 (I Z0 ⊗ I a l ∨ (a + 1)) = 0. Then adding b-a lines passing through l ∨ and the b-a added points we obtain h

Then D 0 (Γ 0 ) is semistable and D 0 (Γ) is unstable. In other words the ideal


Mugurel Ionut ¸andreica
email: mugurel.andreica@cs.pub.ro

Nicolae T ¸ȃpuş
email: nicolae.tapus@cs.pub.ro

Answering nearest neighbor queries is an important problem in many areas, ranging from geographic systems to similarity searching in object data-bases (e.g. image and video databases). In order to answer such queries efficiently, an index data structure is usually constructed over the searched objects. In this paper we present novel top-down and bottomup sequential algorithms for constructing a multidimensional quad-tree index. In all the algorithms the objects may be indexed in association with both quad-tree nodes which they intersect and those which they do not intersect. The common aspect of all the algorithms is that, in order to answer a query, only a single node of the index will need to be searched.

Sequential Algorithms for Constructing an "Out-of-Place" Multidimensional Quad-Tree Index for Answering Exact and Approximate Fixed-Radius Nearest Neighbor Queries

Introduction

The fixed-radius nearest neighbor problem is defined as follows. Given a set of objects in a D-dimensional space, a query point P and a distance R, find the closest object to the point P located at a distance at most equal to R. Usually, the set of objects is fixed and it requires pre-processing in order to answer multiple queries in an efficient manner. This problem has applications in many areas. The most obvious one is in the domain of geographic information systems (GIS). A user may send his coordinates to a GIS and receive back information about the closest object of interest (e.g. address, business, etc.) located at a distance at most R from him/her. Another application is given by similarity search queries. There are many services storing data objects (e.g. images, video clips) which can be described by the values of their features. The set of features forms the feature space. A query point in this space specifies a value for each feature and asks for the object whose features are most similar to those of the query point, but which is not too "far away" from the point.

In this paper we consider a mixed nearest neighbor problem with two distance thresholds: Rmin and Rmax. We are interested in obtaining exact answers up to distance Rmin and approximate answers up to distance Rmax. The rest of 1 this paper is structured as follows. In Section 2 we define the problem statement clearly. In Section 3 we discuss the choice of the index data structure. In Section 4 we introduce the main assumptions, prerequisites and we define the main notations used in the rest of the paper. In Sections 5 and 6 we present sequential versions of the "out-of-place" indexing, "in-place" searching algorithm (the definitions of "in-place" and "out-of-place" are given in Section 4), both using a top-down (Section 5) and a bottom-up (Section 6) approach. In Section 7 we discuss a few object filtering methods. In Section 8 we discuss distributed query processing based on the multidimensional quad-tree index constructed by the presented algorithms. In Section 9 we present the proof for the constant factor approximation of our algorithm in the case of the approximate requirement. In Section 10 we discuss related work and in Section 11 we conclude and discuss future work.

Problem Statement

The problem addressed in this paper is the following. We consider N objects in a D-dimensional space. The objects can be of any type (e.g. points, segments, polyhedra, unions of simpler objects, etc.), where both N and the total amount of data representing the objects are very large. We also consider a distance function over the D-dimensional space (e.g. one of the L p norms (1 ≤ p ≤ +∞)) and two distance thresholds: Rmin and Rmax. We are interested in efficiently answering the following types of queries: Given a point P in the D-dimensional space, return an object O satisfying the following requirements:

1. if the distance between the point P and the nearest object is at most equal to Rmin, then O must be the closest object among all the objects O located at distance at most Rmin from the point P (the exact requirement).

2. if the distance between the point P and the nearest object exceeds Rmin but is at most equal to Rmax, then O should be an approximate nearest object to P (the approximate requirement).

3. if the distance between P and its nearest object exceeds Rmax, then O can be any object, or even no object (the don't care requirement).

The distance between a point P and an object O is defined in the usual way, as the distance between P and the closest point Q to P , such that Q ∈ O. We will assume that a function which computes the distance between a point P and an object O is given. We assume a normal distance function, without additive or multiplicative weights. We also assume that a distance function computing the distance between two geometric objects exists (if the objects intersect, then the distance is 0; otherwise, the distance between them is equal to the minimum distance between a point of the first object and a point of the second object).

Obviously, satisfying the third requirement is trivial (e.g. just select a default object which is returned whenever we do not fit in the first two cases), so we will focus on the first two requirements next.

Choice of the Index Data Structure

The same reasons considered in [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF] for choosing the index data structure are valid in this case, too. We decided that a (multidimensional) quad-tree is the most appropriate solution, because:

1. the set of potential regions (covered by the nodes of the tree) is decoupled from the set of objects.

2. the regions can be chosen at different "resolutions", thus adapting to the space distribution of the objects.

Our choice of the data structure affects the indexing algorithm to a large degree. However, other data structures can be used instead of the (multidimensional) region quad-tree, as long as they have similar properties.

We considered two possibilities for using the (multidimensional) quad-tree:

1. every object is indexed only in nodes which it intersects; then, at query time, we will have to search multiple tree nodes in order to find the answer (we call this the "in-place" indexing, "out-of-place" searching method) (this possibility was investigated in [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]).

2. every object is indexed both in nodes which it intersects, as well as in other (neighboring) nodes; then, at query time, we will only need to search one node containing the query point (we call this the "out-of-place" indexing, "in-place" searching method) (this possibility is described in this paper).

Main Prerequisites, Assumptions and Terms

The same prerequisites, assumptions and notations from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF] are used in this paper, too. For completeness, we include most of them in this section. First, we will describe in more detail what a multidimensional quad-tree is. Each node of the tree has a unique identifier and corresponds to a finite hyper-rectangular region of the D-dimensional space, having a pre-specified aspect ratio. To be more precise, let (c 1 , . . . , c D-1 ) be a set of constant positive values and let (L 1 , . . . , L D ) be the side lengths of a hyper-rectangle corresponding to any tree node. Then we must have L i /L D = c i (for 1 ≤ i ≤ D -1). (c 1 , . . . , c D-1 ) are constant parameters of the tree. The same holds for another constant K ≥ 2, which describes how the regions corresponding to a node's sons are computed. Let's consider the hyper-rectangular region Cell(Q) corresponding to a node Q (with Q being the node's identifier). The node has K D children and their regions are computed as follows: For each dimension i (1 ≤ i ≤ D), divide the side length of Cell(Q) in dimension i into K equal parts, by drawing K -1 equally-spaced hyper-planes. (K -1) • D hyper-planes drawn this way divide the interior of Cell(Q) into K D equal hyper-rectangles, each of them having the same aspect ratio as Cell(Q) (the usual region quad-tree in 2D uses K = 2 and the region of each node is a square). Each of these hyper-rectangles corresponds to a child of Q. Note that we consider Cell(Q) to contain all the points in its interior.

Each node Q of the tree has an associated level Level(Q) (Level(root) = 1, where root is the root node of the tree) and every node Q except the root has a parent, P arent(Q). In theory, the tree can have an infinite number of nodes. Because of this, we will set a threshold M axLevel and we will consider that the nodes at the level M axLevel have no children.

Given the identifier Q of a node, the following functions must be computed efficiently, preferably based only on Q and the constant parameters of the tree (i.e. (c 1 , . . . , c D-1 ) and K):

• Level(Q): returns the level of the node.

• P arent(Q): returns the identifier of the node's parent.

• Cell(Q): returns the geometric representation of the hyper-rectangle (cell) corresponding to the node Q.

• Children(Q): returns a set consisting of the identifiers of the node's children (if any); nodes at level M axLevel have no children and the result is not defined for Level(Q) > M axLevel.

• N eighbors(Q): returns a set consisting of the identifiers of the nodes Q such that Level(Q ) = Level(Q) and Cell(Q ) touches Cell(Q) in at least one point.

Based on these functions, we can define the following extra functions:

• Siblings(Q): returns the set of identifiers of all the nodes Q such that P arent( Q ) = P arent(Q)

• ExtN eighbors(Q): returns the set consisting of node Q's neighbors and siblings (together called extended neighbors)

• Descendants(Q, dlevel): returns the identifiers of all the descendants of Q located at the level dlevel

• Ancestor(Q, alevel): returns the ancestor of the node Q located at the level alevel

• Ancestors(Q, alevel): returns the set of ancestor of the node Q located at or below the level alevel

The function Ancestors(Q, alevel) can be extended to Ancestors(S, alevel), where S is a set of nodes. In this case, Ancestors(S, alevel) returns the union of the sets Ancestors(Q, alevel) for Q ∈ S.

Using the Z-order (or Morton curve) [START_REF] Kumar | A Study of Spatial Clustering Techniques[END_REF] in order to assign identifiers to the nodes of a multidimensional quad-tree helps us to easily implement all the functions mentioned above. However, other encoding schemes with similar properties are also possible [START_REF] Kumar | A Study of Spatial Clustering Techniques[END_REF].

Another function which we require is:

• Cover(F, clevel): returns the set of all the node identifiers Q such that Level(Q) = clevel and the geometric figure

F intersects Cell(Q).
The Cover(F, clevel) function can be implemented easily for connected figures F . One possible implementation is the following. First, we find a point P ∈ F and compute the identifier Q such that Level(Q) = clevel and P ∈ Cell(Q) (i.e. we find the node at level clevel containing the point P ). This can be easily achieved, by computing the position of this node in the level clevel grid of nodes. Then, we will perform a breadth-first search traversal starting from that node. We will visit all the level clevel nodes starting from Q which are intersected by the figure F (once a node is visited, we add it to a queue; when we extract a node from the queue, we visit all of its non-visited neighbors intersected by the figure F ). If F is disconnected, we can still use the same algorithm, as long as we know the coordinates of a point P from each connected component.

Note that, since the Distance function does not include additive distance weights, we have the equivalence between:

• object O intersects Cell(Q) and • Distance(O, Cell(Q)) = 0
However, in the algorithms presented in the rest of this paper, we will not necessarily assume the previous equivalence and we will consider that the intersection between an object and a node is computed geometrically.

We will also make use of two other functions, which can be implemented easily:

• Diameter(F ) which returns the diameter of the figure F , i.e. the largest distance between any pair of points belonging to F .

• Border(Q): returns a geometric representation of the hyper-rectangle Cell(Q), but without the points in its interior (i.e. containing only the border of Cell(Q)).

Using the functions defined above, we can define a new function: Inf late(F, ilevel, radius) which returns a set of identifiers of all the nodes at level ilevel whose nodes are at distance at most radius from the geometric figure F . We will refer to the set of nodes of the identifiers from this set as a "covering". Actually, we will use a more general function, ExtInf late(F, ilevel, radius, f raction) (Algorithm 1 from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]). Then, we can define Inf late(F, ilevel, radius) = ExtInf late(F, ilevel, radius, 0). The f raction parameter can be used in order to also include in the covering a node Q if it is adjacent to a same-level node Q intersecting the figure F and the distance between the figure F and Cell(Q) does not exceed f raction • Diameter(Cell(Q )) (note that since all the nodes at the same level are identical, we have Diameter(Cell(Q)) = Diameter(Cell(Q )). We will use a constant F rac for the value of the f raction parameter.

The final assumption is that each of the N objects O has a unique identifier id(O). This way, we will differentiate between the whole object O (which contains the object's geometry and, possibly, other information) and its identifier.

All the functions defined in this section will be used in the following sections, both at indexing and at query time.

The index consists of a sub-tree T of the complete multidimensional quadtree. During the indexing process, each leaf Q of T will have assigned a list Lobj(Q) of objects which are indexed in association with Q. At the end of the indexing process, we will compute a list Lid(Q) for each leaf Q, where

Lid(Q) = {id(O)|O ∈ Lobj(Q)}.
During our indexing process, we will also use a parameter M inLevel, meaning that we don't want to have leaves at a smaller level than M inLevel. Because of this, we will define the operation SplitAtLevel(Q, slevel), which replaces a leaf Q ∈ T such that Level(Q) < slevel by its descendants at the level slevel (see Algoritm 2 from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]).

We will denote by Children T (Q) the set of identifiers of the nodes of T which are also children of

Q. Children T (Q) is a subset of Children(Q).
We will associate to each object O a non-negative weight W (O). We provide guidelines as to how this weight should be chosen. The weight should be proportional to:

• the size of the object (i.e. the storage space it takes) and/or

• the duration of computing the distance from a query point to the object For each leaf Q of the tree, we will maintain a value W L(Q) representing the aggregate weight of the objects associated to Q. We will use an aggregation function aggf (e.g. aggf = addition). We will use an indexing weight threshold IW T in order to decide when we need to split a leaf. If the aggregate weight of the objects associated to a leaf Q exceeds IW T and Level(Q) < M axLevel, then we will need to split the leaf.

The time complexities of the algorithms presented in this paper depend both on the maximum depth of the (multidimensional) quad-tree (M axLevel) and on the sizes of the indexed objects (or on the number of cells of the covers and inflated covers of the objects).

5 The Top-Down Method

Constructing the Index -Addressing the Exact Search Requirement

We insert the objects O one at a time, in an arbitrary order. We use the algorithm InsertT opDown (Algorithm 3 from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]); the initial call is InsertT opDown( root, O, Rmin, F rac), where root is the root node of the tree. At the end of the insertion process, the list Lobj(Q) of each leaf Q contains all the objects located at a distance at most equal to Rmin from Cell(Q). However, not necessarily all these objects can be nearest object candidates for the points of Cell(Q). Thus, we propose a filtering process, in order to reduce the sizes of the lists Lobj( * ).

Let's consider that we have a function F ilter(Q, L) which takes as input a node id of a leaf in T and a list of objects L and returns a list L obtained by removing from L (all or some of) the objects which are not nearest neighbors to any part of Cell(Q). We discuss the implementation of the F ilter function in a separate section.

During the filtering phase we will use a second threshold F W T for the aggregate weight of the objects associated to any leaf Q and a second value for the maximum allowed level of a leaf: F M axLevel (with F M axLevel ≥ M axLevel). Unlike the insertion procedure, this part of the indexing process does not need to be implemented sequentially. Thus, we will describe the algorithm using the Replicated Workers paradigm. We will use a pool of tasks T askP ool; a task is specified by the identifier Q of a leaf on which we need to perform the filtering process. Initially, we insert all the leaf identifiers into T askP ool. We will also maintain a counter N umW aiting, describing the number of workers waiting for extracting a task from T askP ool. Let N umW orkers be the total number of workers. Algorithm 1 describes the steps taken by each worker. The read/write accesses to T askP ool and N umW aiting are synchronized by a condition variable Cond.

if Q = F IN ISH T ASK then return end if Lobj(Q) = F ilter(Q, Lobj(Q)) W L(Q) = 0 for O ∈ Lobj(Q) do W L(Q) ← aggf (W L(Q), W (O)) end for if (W L(Q) > F W T ) and (Level(Q) < F M axLevel) then Cond.lock() for Q ∈ Children(Q) do Lobj(Q ) = Lobj(Q) T askP

Constructing the Index -Addressing the Approximate Search Requirement

The set of leaf nodes of T obtained so far corresponds to dense nodes, i.e. parts of the space which intersect some object or are close to an object. However, they do not cover the whole space (in particular, there are zones whose distance to the closest object is at most Rmax which may not be covered by any dense node). In order to address the approximate search requirement, we will fill in the gaps by adding a set of non-dense nodes as leaves of T . First, we will construct the set N DN of non-dense nodes, by usng Algorithm 2. We need to run the algorithm (ComputeN onDenseN odesT opDown(root)), considering that, initially, N DN = {} and is a global variable.

Algorithm 2 ComputeN onDenseN odesT opDown(Q) if Q is a leaf in T then return else for Q ∈ (Children(Q) \ Children T (Q)) do N DN ← N DN ∪ {Q} end for for Q ∈ Children T (Q) do ComputeN onDenseN odesT opDown(Q ) end for end if
The set N DN contains non-dense nodes which, together with the dense nodes, disjointly cover the whole space (the non-dense nodes "filled the gaps" left by the dense nodes). All that is left to do is associate some objects to the non-dense nodes. Unfortunately, we were unable to achieve a constant factor approximation in a top-down manner. Because of this, we will provide a bottom-up algorithm. Initially, Lobj(QN DN ) = {} and Lid(QN DN ) = {} for every non-dense node QN DN . The algorithm 3 is called once for every node Q corresponding to a dense node (i.e. for every leaf Q of T ; note that the nondense nodes were not added as leaves in T , yet). The second input parameter of the algorithm must be Rmax. The algorithm is based on the following property: each non-dense node is the neighbor of an ancestor of a dense node. Note that we compute the lists Lid directly for the non-dense nodes. Also note that the total number of object ids in the lists Lid( * ) of the non-dense nodes is bounded by O(|Leaves T | • F M axLevel). In Algorithm 3 we had to go all the way up to level 1, because non-dense nodes can be located at any level lev ≤ F M axLevel (not just at levels lev for which M inLevel ≤ lev ≤ F M axLevel). In order to use only nodes between the levels M inLevel and F M axLevel, at the end of the indexing process, we will call the function SplitAtLevel(Q, M inLevel) for each non-dense node Q with Level(Q) < M inLevel (see Algoritm 2 from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]).

In Section 9 we present a full proof regarding why the simple algorithm described above provides a constant factor approximation when the query point is located in one of the non-dense nodes.

Here we will continue by improving the algorithms presented so far for nondense nodes. The problem with the algorithm above is that although we have an upper bound on the total number of object ids in the lists Lid( * ) of the nondense nodes, there is no upper bound on the cardinality of every individual list. The improvement described next will provide a somewhat better theoretical upper bound, but a much better practical upper bound. Let's consider the nodes Q and AN in Algorithm 3. Let QAN (Q, AN ) be the lowest ancestor of Q which has some extended neighbor EN such that AN is an ancestor of EN . A less formal explanation is that QAN (Q, AN ) is the lowest ancestor of Q which is an extended neighbor of some part of AN . The reason for computing this is that given a fixed node AN , all the objects O from dense nodes Q with the same value of QAN (Q, AN ) are "close" to each other and any such object can be selected as a representative (discarding the others). Moreover, if we have two nodes Q 1 and Q 2 such that QAN (Q 1 , AN ) is an ancestor of QAN (Q 2 , AN ), then Q 1 can be ignored, as any object whose id belongs to Lid(Q 2 ) is at most a constant number of times further away from any point of AN than any object with an id from Lid(Q 1 ). The Algorithm 4 presents the first step of this optimization, in which for every non-dense node AN we compute a list Ltuple(AN ) of tuples (node, ancestor node, id(O)). In the algorithm we will maintain a set U sedQAN (QN D) for every non-dense node QN D (initially, each of these sets is empty). We need to run the algorithm for every dense node Q.

The second part of this optimization is presented in Algorithm 5. We need to run the algorithm for each non-dense node AN ∈ N DN .

The proof that this optimization still preserves the constant factor approximation is given in Section 9. Note that in the algorithms above, a non-dense node "received" objects only from dense nodes located at the same level or larger levels (i.e. lower in the tree). If required, we may also add objects from dense nodes at smaller levels (although this is not strictly needed for achieving a constant factor approximation). Algorithm 6 shows how this can be implemented (it must be called for each non-dense node Q).

As an observation, we could have computed the list of objects Lobj(Q) for every non-dense node Q (and then, based, on Lobj(Q), we would be able to compute Lid(Q)). This would have allowed us to filter useless objects from the list in the end (before computing Lid(Q)) and keep only some of the objects from the list. However, it is more time-efficient to compute Lid( * ) directly (and, thus, we will not perform any extra filtering, as in the case of the dense nodes).

Answering a Query

For the query part we use the algorithm 7. We will call T opDownQuery(root, P ) in order to obtain the list of candidate object ids. The closest object to the query point P whose identifier belongs to the set of candidate object ids is returned. ComputeObjectsF orN onDenseN odes F romLargerDenseN odes(Q, Rmax) SA = Ancestors({Q}, 1)

for A ∈ SA do for AN ∈ (ExtN eighbors(A) ∩ Leaves T ) do if Distance(Cell(Q), Cell(AN )) ≤ Rmax then Let O be the closest object to Cell(Q) from Lobj(AN ) Lid(Q) ← Lid(Q) ∪ {id(O)} end if end for end for Algorithm 7 T opDownQuery(Q, P ) if Q is a leaf then return Lid(Q) else result = {} for Q ∈ Children T (Q) do if P is located inside Cell(Q ) then result ← result ∪ T opDownQuery(Q , P ) end if end for return result end if
6 The Bottom-Up Method

Constructing the Index -Addressing the Exact Search Requirement

Let's consider a fraction F rac. For each object O we first compute the set SC = ExtInf late(O, M axLevel, Rmin, F rac). Then, for each node Q ∈ Ancestors(SC, M inLevel) which is also a leaf in T , we call AddObjectT oLeaf (Q, O, Rmin, F rac) (Algorithm 4 from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]). At the end, we use Algorithm 1 in order to filter the objects associated to every tree leaf and, possibly, split the leaves up to the level F M axLevel (where F M axLevel ≥ M axLevel).

Constructing the Index -Addressing the Approximate Search Requirement

The top-down method described previously actually makes use of many bottomup functions, which will not be described here anymore. The only function which still needs to be defined in a bottom-up manner is the computation of the set of non-dense nodes. We will assume that the set N DN of non-dense nodes is initially empty. Then, we call ComputeN onDenseN odesBottomU p for every dense node Q (see Algorithm 8). After this step, we need to remove from N DN all the nodes whose parent also belongs to N DN . The simplest way of achieving this is to construct the

Answering a Query

We will compute the set SC = Ancestors(Cover(P, F M axLevel), M inLevel), consisting of the node Q containing the point P such that Level(Q) = F M axLevel, plus all of its ancestors up to the level M inLevel. Only at most one of the nodes from this set is a leaf in T : let this node be QL. Then, we consider all the objects O for which id(O) ∈ Lid(QL) as candidate answers for the query. The closest candidate object to the query point P is returned.

Object Filtering Methods

The function F ilter(Q, Lobjects) returns a subset of objects O from Lobjects, such that those objects are nearest neighbors to at least one point of Cell(Q). We propose two types of filtering:

• a coarse-grained filtering, based on subdividing (the borders of) Cell(Q) and computing distances from the objects to the subdivisions.

• a fine-grained filtering, based on computing a (restricted) Voronoi diagram of the objects.

Filtering based on Distances to Nodes' Cells and their Borders

We can subdivide Cell(Q) by using a D-dimensional grid (e.g. by dividing its side in dimension i in s i equal parts by drawing s i -1 equally spaced hyperplanes perpendicular on the dimension i). Then, for each part P of the s 1 •. . .•s D grid, we compute the following values:

• Dmin(P ) = min{Distance(O, P )|O ∈ Lobjects}

• Dmax(P ) = Dmin(P ) + Diameter(P )

Since each part P is a hyper-rectangle, the same function which computes the diameter of a node can be used for computing the diameter of P . The result list will contain only those objects O ∈ Lobjects for which Distance(O, P ) ≤ Dmax(P ) for at least one subdivided part P .

If the distance function returns 0 if an object intersects Cell(Q), then we can reduce the dimensionality by 1. Cell(Q) has 2•D "faces", each corresponding to an extreme (lowest or highest) coordinate in each dimension. We will subdivide each "face" F using a (D -1)-dimensional grid. We can choose the numbers s 1 , . . . , s D-1 . Then, we renumber the dimensions dim(1), . . . , dim(D -1) in such a way that the dimension i where the length of F is 0 is excluded. Then, we subdivide the side of F in dimension dim(i) into s i equal parts, by drawing s i -1 equally spaced hyper-planes perpendicular on the dimension dim(i). Thus, each face F is subdivided into s 1 • . . . • s D-1 parts. Then, for each part P (of some face F ), we compute the same values as before (however, the parts are now restricted to the faces of the node only, and are not located in the node's interior).

The result list will contain only those objects O ∈ Lobjects for which:

• Distance(O, P ) ≤ Dmax(P ) for at least one subdivided part P or

• Distance(O, Cell(Q)) = 0 (e.g. if O intersects Cell(Q))
We denote this filtering function F ilterBasedOnDistancesT oSubdivisions(Q, Lobjects).

Filtering based on Voronoi Diagrams

In order to maintain strictly only those objects O ∈ Lobjects which can be nearest neighbors to some parts of Cell(Q), we could compute the Voronoi diagram of the objects (using the distance function Distance) restricted to the interior and the borders of Cell(Q). Then, only those objects O whose Voronoi cell intersects Cell(Q) (or, equivalently, their Voronoi cells are non-empty when the diagram is restricted to Cell(Q) only) would be added to the result list.

However, computing the Voronoi diagram of (not necessarily simple) geometric objects in multiple dimensions is a complex task (both time consuming and cumbersome to implement). If the distance function returns 0 for any object intersecting Cell(Q), then we can reduce the dimensionality by 1. We will compute a Voronoi diagram restricted to each face F of Cell(Q). Then, an object O is added to the result list if:

• it intersects Cell(Q) or

• its Voronoi cell restricted to at least some face F of Cell(Q) is non-empty.

In the common case of D = 2, the "faces" of each node are actually line segments. If the objects are points or line segments (or can be decomposed into a finite number of points and line segments) then the Voronoi diagram restricted to a segment of the border of a node consists of the lower envelope of the distance function from the objects to the segment. Algorithms for computing lower envelopes in the case we mentioned were discussed in [START_REF] Andreica | Line-Constrained Geometric Server Placement[END_REF][START_REF] Agrawal | Davenport-Schinzel Sequences and Their Geometric Applications[END_REF].

We will denote the function performing Voronoi diagram-based filtering as F ilter-U singV oronoiDiagram(Q, Lobjects). An efficient way of combining the two types of filtering is to define a general filter function F ilter(Q, Lobjects) = F ilterU singV oronoiDiagram(Q, F ilterBasedOnDistancesT oSubdivisions(Q, Lobjects)).

Distributed Query Processing

The possibility of processing queries in a distributed manner was discussed in [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF]. For completeness, we include here the most important ideas. When multiple machines are available for answering a query, we can distribute the index over these machines. From the point of view of a leaf node Q, we may choose to store its list Lid(Q) on a single machine, or have it distributed over the whole range of available machines. When a query is performed, we first compute the set of nodes SC (from the bottom-up solution) which may have the answer to the query. Then, this set is sent to each machine, which, in turn, returns a set of candidate object ids for the query (if it stores part of Lid(Q) for some Q ∈ SC) or doesn't return anything. After computing the union of the sets of object ids, each object is retrieved independently and we compute the distance from the query point to it (we may consider the candidate objects sequentially or in parallel, using multiple threads and/or multiple machines).

Proof of Constant Factor Approximation for the Approximate Search Requirement

First, it should be obvious that, whenever the query point is at most a distance Rmin away from the closest object, it will fall inside a dense node (because all the space up to distance Rmin and possibly more is covered by dense nodes). Moreover, the list of object identifiers associated to a dense node will always contain the identifier of the closest object O to any point P inside the node, if Distance(P, O) ≤ Rmin. That is to say, whenever a query point P lies inside a dense node of a node Q, the identifier of the closest object O will definitely be found within Lid(Q), as long as the distance from the closest object to P does not exceed Rmin (that's because Q ∈ Ancestors(ExtInf late(O, M axLevel, Rmin, F rac), M inLevel). Thus, the exact search requirement is fulfilled by our algorithms. We will prove next that, when we fall within the approximate search requirement case, the returned object is at most a constant number of times further away from the query point than the real nearest neighbor. Our proof will need to handle two major cases:

1. Case 1: The query point P lies within a dense node, but its closest object is at a distance larger than Rmin 2. Case 2: The query point P lies within a non-dense node.

In each case, the proof will consist of computing a lower bound Dmin of the minimum possible distance of an object to P and an upper bound Dmax of the maximum possible distance of the returned object to P and showing that Dmax Dmin is upper bounded by a constant value. The proof will also use Dmin(zone) as a lower bound of the minimum possible distance from any part of an object intersecting the zone zone to the point P . F rac . Thus, the upper bound in this case is 1+ 1 F rac .

The query point lies within a non-dense node

First, it should be obvious that the non-dense nodes cover all the space not occupied by the dense nodes, at least up to distance Rmax from the objects. Thus, if the query point lies neither in a dense node, nor in a non-dense node, then its distance from the closest object certainly exceeds Rmax.

We will start by proving that our initial, unoptimized algorithm for assigning object identifiers to non-dense nodes provides a constant factor approximation. Then, we will show how the optimized algorithm maintains the constant factor approximation.

The unoptimized version of the algorithm

The key to the proof is the following. Let's consider a query point P contained inside a non-dense node N DC. Then, we will show that, for every dense node DC, L(N DC) contains the identifier of an object which is at most a constant number of times further away from P than any part of the intersection between an object and Cell(DC). Like in the previous subcase, some (random) object identifier id(O) ∈ Lid(DC) also belongs to Lid(N DC). We have the same lower and upper distance bounds as in the previous subcase.

Subcase 1.3: Let ADC be the ancestor of DC located at the same level as N DC.

Note that ADC and N DC are not extended neighbors (otherwise, we would get subcase 1.2). In this case, no object identifier from Lid(DC) will be "thrown" into Lid(N DC). However, this is not necessary. We have Dmin(Cell(DC)) = Distance(Cell(DC), Cell(N DC)). However, Dmin(Cell(DC)) ≥ max{Rmin, F rac • Diameter(DC), min{L i |1 ≤ i ≤ D}} (where L i is the length in dimension i of Cell(N DC)). In this case, there is some extended neighbor DC of N DC which is an ancestor of a dense node (otherwise not N DC, but one of a distributed algorithm for constructing octrees (3D quad-trees) was presented. In [START_REF] Panda | PLANET: Massively Parallel Learning of Tree Ensembles with MapReduce[END_REF], a MapReduce-based framework which can be used for constructing classification and regression trees in parallel has been proposed. Other attempts for processing spatial data using the MapReduce model for constructing an R-tree index have been made in [START_REF] Cary | Experiences on Processing Spatial Data with MapReduce[END_REF]. A generic MapReduce framework for tree data structures has been proposed in [START_REF] Sarje | A MapReduce Style Framework for Computations on Trees[END_REF].

The work presented in this paper is a natural continuation of the work we presented in [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF].

Conclusions and Future Work

In this paper we presented novel methods for constructing an index over a set of (arbitrary) geometric objects, which can speed up the exact and approximate computation of answers for fixed-radius nearest neighbors queries. We presented novel, sequential, top-down and bottom-up, algorithms for "out-ofplace" indexing and "in-place" searching. The model presented in this paper complements our previous work from [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF], where "in-place" indexing and "outof-place" searching algorithms were discussed. Unlike in [START_REF] Andreica | Sequential and MapReduce-based Algorithms for Constructing an In-Place Multidimensional Quad-Tree Index for Answering Fixed-Radius Nearest Neighbor Queries[END_REF], we did not provide a parallel or distributed "out-of-place" indexing method (e.g. based on the MapReduce computation model [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF]) in this paper. Note, also, that there may also be other intermediate levels between "in-place" indexing plus "out-of-place" searching and "out-of-place" indexing plus "in-place" searching, which might be interesting to explore in order to better understand the trade-offs which they may provide.

Algorithm 1

 1 ReplicatedW orkersF ilter(N umW orkers, T askP ool, N umW aiting, Cond) Cond.lock() while (N umW aiting < N umW orkers -1) or (T askP ool.size() > 0) do N umW aiting ← N umW aiting + 1 while T askP ool.size() = 0 do Cond.wait() end while Q ← T askP ool.ExtractT ask() N umW aiting ← N umW aiting -1 Cond.unlock()

Algorithm 3

 3 ComputeObjsN onDenseN odesBottomU p(Q, Rmax) SA = Ancestors({Q}, 1) for A ∈ SA do for AN ∈ (ExtN eighbors(A) ∩ N DN ) do if Distance(Cell(Q), Cell(AN )) ≤ Rmax then Let O be any object from Lobj(Q) {Or, alternatively, let id(O) be any object id from Lid(O)} Lid(AN ) ← Lid(AN ) ∪ {id(O)} end if end for end for

Algorithm 8

 8 ComputeN onDenseN odesBottomU p(Q) SA = Ancestors({Q}, 1) for A ∈ SA do for AN ∈ (ExtN eighbors(A) \ Leaves T ) do N DN ← N DN ∪ {AN } end for end for set N DN P arents = {Q |Q = P arent(Q) and Q ∈ N DN } and then to set N DN = N DN \ N DN P arents.

9. 1

 1 The query point lies within a dense node max{ Rmin, F rac • Diameter(Cell(Q))} = Diameter(Cell(Q)) + Dmin. Thus, we have Dmax Dmin = 1+ Diameter(Cell(Q)) Dmin . Since Dmin ≥ F rac•Diameter(Cell(Q)), we have Diameter(Cell(Q)) Dmin ≤ 1

Case 1 :

 1 Level(N DC) ≥ Level(DC) (i.e. Cell(N DC) is larger than Cell(DC)) Subcase 1.1: Level(N DC) = Level(DC) (this means that N DC is an extended neighbor of DC) Some (random) object identifier id(O) ∈ Lid(DC) also belongs to Lid(N DC). Since no parts of N DC were indexed as dense nodes (otherwise N DC would not have been indexed as a non-dense node), then Dmin(Cell(DC)) = max{Rmin, F rac•Diameter(Cell(DC)), Distance(Cell(DC), Cell(N DC))}. Let's consider the identifier id(O) which was "thrown" from Lid(DC) to Lid(N DC). If O intersects Cell(DC), then Distance(O, Cell(N DC)) ≤ Distance(Cell(DC), Cell( N DC))+Diameter(Cell(DC)); otherwise the upper bound is equal to Distance( Cell(DC), Cell(N DC))+ Diameter(Cell(DC))+max{Rmin, F rac•Diameter( Cell(DC))}. In this case, the ratio between the upper bound and the lower bound is again O1F rac. Subcase 1.2: Let ADC be the lowest ancestor of DC which is an extended neighbor of N DC (thus, we have Level(ADC) = Level(N DC)).

Acknowledgements

The work presented in this paper was partially funded by the Romanian National Council for Scientific Research (CNCS)-UEFISCDI under research grant PD 240/2010 (AATOMMS -contract no. 33/28.07.2010), from the PN II -RU program, and by the Sectoral Operational Programme Human Resources Development 2007-2013 of the Romanian Ministry of Labour, Family and Social Protection through the financial agreement POSDRU/89/1.5/S/62557.

. Note that Diameter(Cell(N DC)) is a function only of the sizes of Cell(N DC) in every dimension and Dmin(Cell(DC)) is larger than the minimunm value of such a size. Since all the nodes have the same aspect ratio, it is easy to prove that all the nodes have the same ratio between their diameter and their smallest size in a dimension (which we will denote by a constant DS). Thus, we obtain again a constant upper bound.

Case 2: Level(N DC) > Level(DC) (i.e. Cell(N DC) is smaller than Cell( DC))

In this case, no identifier from Lid(DC) is added to Lid(N DC). However, none is actually required (as shown below).

We have Dmin(Cell(DC)) = max{Rmin, F rac • Diameter(DC), Distance( Cell(DC), Cell(N DC))}. There exists an extended neighbor DC of N DC which is an ancestor of a dense node and, thus, an object identifier id(O) ∈ Lid(DC ) which also belongs to Lid(N DC). In this case, we have Dmax = K • D • Diameter(N DC) + max{Rmin, F rac • Diameter(N DC)}. Thus, the ratio between the upper and lower bounds is bounded by 1 + K•D F rac .

The optimized version of the algorithm

When considering the optimized version of computing the lists Lid( * ) of the nondense nodes, we need to recompute the upper distance bounds in each of the subcases defined above (the new bounds will be higher than in the unoptimized case, but they will still provide a constant factor approximation). Subcase 1.1:

We still have a constant factor approximation. Subcase 1.2: We obtain the same lower and upper bounds as in subcase 1.1. Subcase 1.3: We have the same lower and upper bounds as in the same subcase of the unoptimized version.

Case 2: We have the same lower and upper bounds as in the same subcase of the unoptimized version.

Related Work

The fixed-radius nearest neighbor problem has been addressed before in several research papers (e.g. [START_REF] Bentley | The Complexity of Finding Fixed-Radius Near Neighbors[END_REF][START_REF] Aref | Efficient Processing of Proximity Queries for Large Databases[END_REF][START_REF] Castelli | Multidimensional Indexing Structures for Content-based Retrieval[END_REF][START_REF] Kirkpatrick | Optimal Search in Planar Subdivisions[END_REF]) and many data structures for solving this problem or related problems have been proposed: R-trees [START_REF] Guttman | R-Trees -A Dynamic Index Structure for Spatial Searching[END_REF][START_REF] Sharifzadeh | VoR-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries[END_REF], kd-trees [START_REF] Bentley | Multidimensional Binary Search Trees Used for Associative Searching[END_REF], quad-trees [START_REF] Hunter | Operations on Images using Quad Trees[END_REF], fixed-size node subdivisions [START_REF] Lai | A node Subdivision Strategy for R-Nearest Neighbors Computation[END_REF][START_REF] Akman | Geometric Computing and Uniform Grid Technique[END_REF] and many others [START_REF] Chavez | A Compact Space Decomposition for Effective Metric Indexing[END_REF]. Most of the proposed solutions assume that the index can be constructed in main memory or, at least, can be stored on the disk of a single machine. Thus, the proposed algorithms are sequential in nature (see, for instance, [START_REF] Dinis | A Sweep Line Algorithm for Nearest Neighbot Queries[END_REF]).

More recently, parallel and distributed algorithms for constructing indices over geometrical data have been proposed. In [START_REF] Liu | Clustering Billions of Images with Large Scale Nearest Neighbor Search[END_REF], some parts of the construction of a hierarchical index are parallelized using the MapReduce computation model, but other parts were still implemented in a sequential manner. In [START_REF] Sundar | Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel[END_REF],