Alexander D Rahm

ON THE EQUIVARIANT K-HOMOLOGY OF PSL 2 OF THE IMAGINARY QUADRATIC INTEGERS

We establish formulae for the part due to torsion of the equivariant K-homology of all the Bianchi groups (PSL2 of the imaginary quadratic integers), in terms of elementary number-theoretic quantities. To achieve this, we introduce a novel technique in the computation of Bredon homology: representation ring splitting, which allows us to adapt the recent technique of torsion subcomplex reduction from group homology to Bredon homology.

Organisation of the paper. In Section 2, we describe the cell complex on which we study the Bianchi groups through their action. In Section 3, we make recalls about the Bredon chain complex; in Section 4, we recall torsion subcomplexes and their reduction. In Section 5, we give the proof of Theorem 1. In Section 6, we give the proof of Theorems 2 and 3. Section 7 is a study on how the methods of this paper can be generalised, and establishes a statement for arbitrary classifying spaces for proper actions with zero-dimensional singular part. We summarize information on the assembly map for the Bianchi groups in Section 8. Section 9 appends results from machine computations on the Bredon homology of the Bianchi groups.

Introduction

Let O -m be the ring of algebraic integers in the imaginary quadratic number field Q( -m) ); the Bianchi groups are the projective special linear groups PSL 2 (O -m ). In this paper, we establish formulae for the part due to torsion of the Bredon homology of the Bianchi groups, with respect to the family Fin of finite subgroups and coefficients in the complex representation ring R C , from which we deduce their equivariant K-homology. Then we use the fact that the Baum-Connes assembly map from the equivariant K-homology to the K-theory of the reduced C * -algebras of the Bianchi groups is an isomorphism. This has been inspired by works of Sanchez-Garcia [START_REF] Rubén | Bredon homology and equivariant K-homology of SL(3, Z)[END_REF][START_REF] Rubén | Equivariant K-homology for some Coxeter groups[END_REF], and allows us to obtain the isomorphism type of the latter operator Ktheory, which would be extremely hard to compute from the reduced C * -algebras. Case-by-case computations on the machine have already been carried out for the equivariant K-homology of the Bianchi groups [START_REF] Rahm | Homology and K-theory of the Bianchi groups[END_REF] (see [START_REF] Fuchs | Equivariant K-homology of Bianchi groups in the case of non-trivial class group[END_REF] for a way to extend them to non-trivial class group cases, alternative to the current implementation by the author), but by their nature, they can of course only cover a small finite collection of Bianchi groups. In order to obtain the desired formulae for all Bianchi groups, we set up an adaptation to Bredon homology of torsion subcomplex reduction, a technique which has recently been formulated for group homology [START_REF] Rahm | Accessing the cohomology of discrete groups above their virtual cohomological dimension[END_REF], and some elements of which had already been used earlier on as ad hoc tricks by Soulé [START_REF] Soulé | The cohomology of SL3(Z)[END_REF]. A priori, it is possible with our methods to treat any discrete group with a nice action on a cell complex; and another class of examples for this is work in advanced progress jointly with Lafont, Ortiz and Sanchez-Garcia [START_REF] Lafont | Bredon homology and equivariant K-homology of hyperbolic Coxeter groups[END_REF], namely hyperbolic Coxeter groups, many of which are not arithmetic. Please note that definitions of Bredon homology and equivariant K-homology are given in [START_REF] Mislin | Proper group actions and the Baum-Connes conjecture[END_REF], [START_REF] Rubén | Bredon homology and equivariant K-homology of SL(3, Z)[END_REF] and [START_REF] Rubén | Equivariant K-homology for some Coxeter groups[END_REF], so we will not recall them in this paper.

Statement of the results

Denote by EΓ the classifying space for proper actions of Γ, and denote by BΓ := Γ\EΓ the orbit space.

Theorem 1. Let Γ be a Bianchi group or one of their subgroups. Then the Bredon homology H Fin n (Γ; R C ) is concentrated in degrees n ∈ {0, 1, 2} and splits as a direct sum over (1) the orbit space homology H n (BΓ; Z), (2) a submodule H n (Ψ

• ) determined by a reduced 2-torsion subcomplex for (EΓ, Γ) (3) and a submodule H n (Ψ

• ) determined by a reduced 3-torsion subcomplex for (EΓ, Γ).

Date: January 21, 2016. 2010 Mathematics Subject Classification. 55N91, Equivariant homology and cohomology. 19L47, Equivariant K-theory.

These submodules are given as follows, except for PSL 2 over the Gaussian and Eisensteinian integers. The additional units in these two rings induce some particularities which we would like to avoid. This does not cause any harm, because the Bredon homology and equivariant K-homology of these two Bianchi groups have already been computed [START_REF] Rahm | Homology and K-theory of the Bianchi groups[END_REF]. So for the remainder of this article, the term "Bianchi group" will stand for PSL 2 over a ring of imaginary quadratic integers excluding these two.

Theorem 2. The part due to 2-torsion of the Bredon complex of a Bianchi group Γ has homology

H n (Ψ (2) • ) ∼ =      Z z 2 ⊕ (Z/2) d 2 2 , n = 0, Z o 2 , n = 1, 0, otherwise,
where z 2 counts the number of conjugacy classes of subgroups of type Z/2 in Γ, o 2 counts the conjugacy classes of those of them which are not contained in any 2-dihedral subgroup, and d 2 counts the number of 2-dihedral subgroups, whether or not they are contained in a tetrahedral subgroup of Γ.

Theorem 3. The part due to 3-torsion of the Bredon complex of a Bianchi group Γ has homology

H n (Ψ (3)
• ) ∼ = Z 2o 3 +ι 3 , n = 0 or 1, 0, otherwise,
where amongst the subgroups of type Z/3 in Γ, o 3 counts the number of conjugacy classes of those of them which are not contained in any 3-dihedral subgroup, and ι 3 counts the conjugacy classes of those of them which are contained in some 3-dihedral subgroup in Γ.

Note that there are formulae for the numbers o 2 , z 2 , d 2 , o 3 and ι 3 in terms of elementary number-theoretic quantities [START_REF]Die Konjugationsklassenanzahlen der endlichen Untergruppen in der Norm-Eins-Gruppe von Maximalordnungen in Quaternionenalgebren[END_REF], which are very easy to evaluate on the machine [20, appendix].

Together with Theorem 5 below, we obtain the following formulae for the equivariant Khomology of the Bianchi groups. Note for this purpose that for a Bianchi group Γ, there is a model for EΓ of dimension 2, so H 2 (BΓ; Z) ∼ = Z β 2 is torsion-free. It has been shown in [START_REF] Serre | Le problème des groupes de congruence pour SL2[END_REF] that the naive Euler characteristic of the Bianchi groups vanishes (again excluding the two special cases of Gaussian and Eisensteinian integers), for

β i = dim H i (BΓ; Q) we have β 0 -β 1 + β 2 = 0 and β 0 = 1.
Corollary 4. For any Bianchi group Γ, the short exact sequence of Theorem 5 splits into

K Γ 0 (EΓ) ∼ = Z⊕Z β 2 ⊕Z z 2 ⊕(Z/2) d 2 2 ⊕Z 2o 3 +ι 3 . Furthermore, K Γ 1 (EΓ) ∼ = H 1 (BΓ; Z)⊕Z o 2 ⊕Z 2o 3 +ι 3 .
A table evaluating these formulas for a range of Bianchi groups is given in Appendix 9. That table agrees with the machine calculations which were carried out by the author for all cases of class number 1 and 2 with [START_REF] Bianchi | Open source program (GNU general public license)[END_REF] in the way described in the author's PhD thesis [START_REF]Co)homologies and K-theory of Bianchi groups using computational geometric models[END_REF] (only the cases of class number 1 were covered at that time), following the method of [START_REF] Rubén | Bredon homology and equivariant K-homology of SL(3, Z)[END_REF][START_REF] Rubén | Equivariant K-homology for some Coxeter groups[END_REF].

The remainder of the equivariant K-homology of Γ is given by 2-periodicity. As the Baum-Connes conjecture is verified by the Bianchi groups, these equivariant K-homology groups are isomorphic to the K-theory of the reduced group C * -algebras.

Acknowledgements. The author would like to thank Conchita Martínez Pérez, Alain Valette and especially Rubén Sánchez-García for helpful discussions, and an anonymous referee for helpful suggestions.

A suitable model for the classifying space for proper actions

In order to construct a suitable model for EΓ when Γ is a Bianchi group, we start with the natural action of Γ < SL 2 (C) on its associated symmetric space SL 2 (C)/ SU 2 . The latter space is isomorphic to hyperbolic 3-space H 3 , and under this isomorphism, the action can be expressed by the Möbius transformation formula when embedding H 3 into the quaternions for carrying out the occurring division. This action makes H 3 into a model for EΓ, but not a cocompact one; a fact which is annoying for Bredon homology computations. In order to reach the desired cocompactness, one could for instance apply the Borel-Serre compactification; but for explicit homological computations, it is more convenient to construct a 2-dimensional Γ-equivariant retract of H 3 . A very conceptual way for such a construction is to use the reduction theory of Borel and Harish-Chandra. This has been done by Harder [START_REF] Harder | A Gauss-Bonnet formula for discrete arithmetically defined groups[END_REF], put into practice for the Bianchi groups by his student Mendoza [START_REF] Mendoza | Cohomology of PGL2 over imaginary quadratic integers[END_REF] and implemented on the machine by Vogtmann [START_REF] Vogtmann | Rational homology of Bianchi groups[END_REF]. For a reader desiring to extend the present investigations to other arithmetic groups, this construction should be the method of choice. However, the above mentioned computer implementation has not been preserved over time, and the author has implemented a different model for EΓ in order to produce the machine results presented in the appendix (Section 9). That model, due to Flöge [START_REF] Flöge | Zur Struktur der PSL2 über einigen imaginär-quadratischen Zahlringen[END_REF], comes with some peculiarities as one does first adjoin the singular cusps of the Γ-action to H 3 before retracting Γ-equivariantly (see details in [START_REF] Rahm | The integral homology of PSL2 of imaginary quadratic integers with nontrivial class group[END_REF]). In order to keep the cell stabilisers finite, one has therefore to start, instead of with H 3 , with its Borel-Serre bordification. Then at the cusps, one gets 2-tori instead of points stabilised by fundamental groups of 2-tori. A variation of this has been pursued in detail by Fuchs [START_REF] Fuchs | Equivariant K-homology of Bianchi groups in the case of non-trivial class group[END_REF].

On the other hand, as Flöge's model is obtained from the boundary of Bianchi's fundamental polyhedron, it allows to study the geometry of the Bianchi groups using the insights of old masters like Luigi Bianchi [START_REF] Bianchi | Sui gruppi di sostituzioni lineari con coefficienti appartenenti a corpi quadratici immaginarî[END_REF], Felix Klein [START_REF] Klein | Ueber binäre Formen mit linearen Transformationen in sich selbst[END_REF] and Henri Poincaré [START_REF] Poincaré | [END_REF]. We note that the Harder-Mendoza model and the Flöge model coincide when the ring of integers is a principal ideal domain, because then there are no singular cusps. The reader may choose to think of the Γ-equivariant retract X of H 3 in this paper either as the Harder-Mendoza model or as the Flöge model, according to her or his research interests. What is important in any case, is to provide X with a Γ-invariant cell structure in which Γ does not perform any "inversions" of cells (mapping a cell to itself without restricting to the identity map on that cell). For theoretical purposes, this can always be achieved using the barycentric subdivision of a given cell structure; but for explicit computations, one should instead make a subdivision along the symmetries of the cells. Such a subdivision of X has been achieved on the machine [START_REF] Rahm | Higher torsion in the Abelianization of the full Bianchi groups[END_REF], and has been used for the appendix (Section 9). As a consequence of any subdivision which eliminates the "inversions" of cells,

• the 2-cells of X are trivially stabilised;

• any 1-cell stabiliser is of isomorphism type Z/ nZ , n ∈ {1, 2, 3}, and performs a rotation of order n on H 3 such that its 1-cell is on the rotation axis. On the 0-cells, obviously any stabilising map restricts to the identity map, so the cell stabiliser can be any of the finite subgroups of Γ.

Recalls about the Bredon chain complex

As described in [START_REF] Mislin | Proper group actions and the Baum-Connes conjecture[END_REF], the equivariant K-homology of the classifying space for proper actions K G * (EG) can be computed by means of the Bredon homology with coefficients in the complex representation ring, H Fin * (G; R C ). More precisely, when we have a classifying space for proper actions of dimension at most 2, then the Atiyah-Hirzebruch spectral sequence from its Bredon homology to its equivariant K-homology degenerates on the E 2 -page and directly yields the following.

Theorem 5 ([18]). Let G be an arbitrary group such that dim EG 2. Then there is a natural short exact sequence

0 → H Fin 0 (G; R C ) → K G 0 (EG) → H Fin 2 (G; R C ) → 0 and a natural isomorphism H Fin 1 (G; R C ) ∼ = K G 1 (
EG). We will follow Sánchez-García's treatment [START_REF] Rubén | Bredon homology and equivariant K-homology of SL(3, Z)[END_REF][START_REF] Rubén | Equivariant K-homology for some Coxeter groups[END_REF]. Consider the Bianchi group Γ := PSL 2 (O -m ). We use the 2-dimensional model X for EΓ described in Section 2.

Denote by Γ σ the stabiliser of a cell σ, and by R C (G) the complex representation ring of a group G. We will study the Bredon chain complex 0

/ / σ∈ Γ \X (2) R C (Γ σ ) Ψ 2 / / σ∈ Γ \X (1) R C (Γ σ ) Ψ 1 / / σ∈ Γ \X (0) R C (Γ σ ) / / 0, of our Γ-cell complex X.
As X is a model for the classifying space for proper Γ-actions, the homology of this Bredon chain complex is the Bredon homology H Fin p (Γ; R C ) of Γ [START_REF] Rubén | Bredon homology and equivariant K-homology of SL(3, Z)[END_REF].

Recalls about torsion subcomplexes

In this section we recall the ℓ-torsion subcomplexes theory of [START_REF] Rahm | Accessing the cohomology of discrete groups above their virtual cohomological dimension[END_REF] for the calculation of group homology, which we are going to adapt to the calculation of Bredon homology in this paper. We require any discrete group Γ under our study to be provided with a Γ -cell complex, that is a finite-dimensional cell complex X with cellular Γ-action such that each cell stabilizer fixes its cell point-wise. Let ℓ be a prime number. Definition 6. The ℓ-torsion subcomplex of a Γ-cell complex X consists of all the cells of X whose stabilizers in Γ contain elements of order ℓ.

We further require that the fixed point set X G be acyclic for every nontrivial finite ℓ-subgroup G of Γ. Then Brown's proposition X.(7.2) [START_REF] Brown | Cohomology of groups[END_REF] specializes as follows.

Proposition 7. There is an isomorphism between the ℓ-primary parts of the Farrell cohomology of Γ and the Γ-equivariant Farrell cohomology of the ℓ-torsion subcomplex.

With the splitting of Theorem 1, we obtain a Bredon homology analogue of the above proposition, finding for each occurring prime ℓ a component of the Bredon homology carried by the ℓ-torsion subcomplex.

For a given Bianchi group, the ℓ-torsion subcomplex can be quite large. It turns out to be useful to reduce this subcomplex, and we identify two conditions under which we can do this in a way that Proposition 7 still holds.

Condition A. In the ℓ-torsion subcomplex, let σ be a cell of dimension n -1 which lies in the boundary of precisely two n-cells representing different orbits, τ 1 and τ 2 . Assume further that no higher-dimensional cells of the ℓ-torsion subcomplex touch σ; and that the n-cell stabilizers admit an isomorphism Γ τ

1 ∼ = Γ τ 2 .
Condition B. The inclusion of the cell stabilizer Γ σ into Γ τ 1 and Γ τ 2 induces isomorphisms on mod ℓ cohomology.

When both conditions are satisfied in the ℓ-torsion subcomplex, we merge the cells τ 1 and τ 2 along σ and do so for their entire orbits. The effect of this merging is to decrease the size of the ℓ-torsion subcomplex without changing its Γ-equivariant Farrell cohomology. This process

Z/2 o 2 Z/3 o 3 A 4 A 4 ι 2 D 3 D 3 ι 3 D 2 D 2 θ D 2 A 4 ρ
can often be repeated: by a "terminal vertex," we will denote a vertex with no adjacent higherdimensional cells and precisely one adjacent edge in the quotient space, and by "cutting off" the latter edge, we will mean that we remove the edge together with the terminal vertex from our cell complex.

Definition 8. The reduced ℓ-torsion subcomplex associated to a Γ-cell complex X is the cell complex obtained by recursively merging orbit-wise all the pairs of cells satisfying conditions A and B, and cutting off edges that admit a terminal vertex when condition B is satisfied.

The following theorem, stating that Proposition 7 still holds after reducing, is proved in [START_REF] Rahm | Accessing the cohomology of discrete groups above their virtual cohomological dimension[END_REF]: There is an isomorphism between the ℓ-primary parts of the Farrell cohomology of Γ and the Γ-equivariant Farrell cohomology of the reduced ℓ-torsion subcomplex. In the case of a trivial kernel of the action on the Γ-cell complex, this allows one to establish general formulae for the Farrell cohomology of Γ [START_REF] Rahm | Accessing the cohomology of discrete groups above their virtual cohomological dimension[END_REF]. Analogously, we will use our adaptation of torsion subcomplex reduction to Bredon homology in order to prove the formulae in Theorems 2 and 3.

Table 1 displays the types of connected components of reduced torsion subcomplex quotients for the action of the Bianchi groups on hyperbolic space: Norbert Krämer [13, Satz 8.3 and Satz 8.4] has shown that the types , , and are all possible homeomorphism types which connected components of the 2-torsion subcomplex of the action of a Bianchi group on hyperbolic space can have. For 3-torsion, the existence of only the two specified types was already proven in [START_REF]The homological torsion of PSL2 of the imaginary quadratic integers[END_REF].

Representation ring splitting

Recall the following classification of Felix Klein [START_REF] Klein | Ueber binäre Formen mit linearen Transformationen in sich selbst[END_REF]. Lemma 9 (Klein). The finite subgroups in PSL 2 (O) are exclusively of isomorphism types the cyclic groups of orders one, two and three, the 2-dihedral group D 2 ∼ = Z/2 × Z/2, the 3-dihedral group D 3 or the tetrahedral group isomorphic to the alternating group A 4 .

We further use the existence of geometric models for the Bianchi groups in which all edge stabilisers are finite cyclic and all cells of dimension 2 and higher are trivially stabilised. Therefore, the system of finite subgroups of the Bianchi groups admits inclusions only emanating from cyclic groups. This makes the Bianchi groups and their subgroups subjects to the splitting of Bredon homology stated in Theorem 1.

The proof of Theorem 1 is based on the above particularities of the Bianchi groups, and applies the following splitting lemma for the involved representation rings to a Bredon complex for (EΓ, Γ).

Lemma 10. Consider a group Γ such that every one of its finite subgroups is either cyclic of order at most 3, or of one of the types D 2 , D 3 or A 4 . Then there exist bases of the complex representation rings of the finite subgroups of Γ, such that simultaneously every morphism of representation rings induced by inclusion of cyclic groups into finite subgroups of Γ, splits as a matrix into the following diagonal blocks.

(1) A block of rank 1 induced by the trivial and regular representations, (2) a block induced by the 2-torsion subgroups (3) and a block induced by the 3-torsion subgroups.

As this splitting holds simultaneously for every morphism of representation rings, we have such a splitting for every morphism of formal sums of representation rings, and hence for the differential maps of the Bredon complex for any Bianchi group and any of their subgroups.

Proof. We consider the complex representation ring of these finite groups as the free Z-module the basis of which are the irreducible characters of the group (here and in the following, we identify representations with their associated characters, basing ourselves on [START_REF]Linear representations of finite groups[END_REF]). The trivial group admits only the representations by the identity matrix, so its only irreducible character is given by the trace 1. For the other finite subgroups of the Bianchi groups, we make the below choices of conjugacy representatives of their elements, and specify below the irreducible characters by the values they take on these elements. For Z/2 = g | g 2 = 1 , we transform the tables of irreducible characters into the following basis for the representation ring.

  Z/2 1 g ρ 1 1 1 ρ 2 1 -1   →   Z/2 1 g ρ 1 + ρ 2 2 0 ρ 2 1 -1   . Let j = e 2πi 3 . Then for Z/3 = h | h 3 = 1 , we transform     Z/3 1 h h 2 σ 1 1 1 1 σ 2 1 j j 2 σ 3 1 j 2 j     →     Z/3 1 h h 2 i σ i 3 0 0 σ 2 1 j j 2 σ 3 1 j 2 j     ,
and for the the Klein four-group

D 2 = a, b | a 2 = b 2 = (ab) 2 = 1 ,       D 2 1 a b ab ξ 1 1 1 1 1 ξ 2 1 -1 -1 1 ξ 3 1 -1 1 -1 ξ 4 1 1 -1 -1       →       D 2 1 a b ab ξ 1 1 1 1 1 ξ 2 -ξ 1 0 -2 -2 0 ξ 3 -ξ 1 0 -2 0 -2 ξ 4 -ξ 1 0 0 -2 -2       .
In all these three cases, we encounter either only 2-torsion or only 3-torsion. In the cases of D 3 and A 4 , where we have both types of torsion, we split the representation ring into a direct sum of submodules associated to respectively the trivial subgroup, 2-torsion and 3-torsion. We achieve this in the following way.

• We write the symmetric group D 3 = ( 12), (123) | cycle relations in cycle type notation.

Then we apply the following base transformation to its character table.

    D 3 1 (12) (123) π 1 1 1 1 π 2 1 -1 1 π 3 2 0 -1     →     D 3 1 (12) (123) π 1 1 1 1 π 2 := π 2 -π 1 0 -2 0 π 3 := π 3 -π 2 -π 1 0 0 -3    
• We also write the alternating group A 4 in cycle type notation, and let again j = e 2πi 3 . Then we transform 

     A 4 1 (12)(34) (123) (132) χ 1 1 1 1 1 χ 2 3 -1 0 0 χ 3 1 1 j j 2 χ 4 1 1 j 2 j       →       A 4 1 (12)(34) (123) (132) χ 1 1 1 1 1 χ 2 -χ 1 -χ 3 -χ 4 0 -4 0 0 χ 3 -χ 1 0 0 j -1 j 2 -1 χ 4 -χ 1 0 0 j 2 -1 j -1       .
The above transformed tables consist no more only of irreducible characters, but clearly, they still are bases for the complex representation rings of the concerned groups.

For an injective morphism H ֒→ G of finite groups, we compute as follows the map induced on the complex representation rings. We restrict the characters φ i of G to the image of H, and write φ i ↓ for the restricted character. Then we consider the scalar products

(φ i ↓ |τ j ) := 1 |H| h∈H φ i ↓ (h) • τ j (h)
with the characters τ j of H. By Frobenius reciprocity, the induced map of representation rings is given by the matrix (φ i ↓ |τ j ) i,j . When H is the trivial group, this matrix is the one-columnmatrix of values of the characters of G on the neutral element. For the non-trivial inclusions amongst finite subgroups of the Bianchi groups, let us compute this matrix case by case.

• Any inclusion Z/ℓ ֒→ D 3 maps the generator of Z/ℓ to the only conjugacy class of elements of order ℓ in D 3 . So it induces the map obtained by restricting to two cycles, -for ℓ = 2, the cycles ( 1) and ( 12):

Z/2 ֒→ D 3 (1) (12) (π i ↓ |ρ 1 + ρ 2 ) (π i ↓ |ρ 2 ) π 1 ↓ 1 1 1 0 π 2 ↓ 0 -2 0 1 π 3 ↓ 0 0 0 0
for ℓ = 3, the cycles (1) and (123):

Z/3 ֒→ D 3 (1) (123) (π i ↓ | i σ i ) (π i ↓ |σ 2 ) (π i ↓ |σ 3 ) π 1 ↓ 1 1 1 0 0 π 2 ↓ 0 0 0 0 0 π 3 ↓ 0 -3 0 1 1
• There are three possible inclusions Z/2 ֒→ D 2 , namely g → a, g → b and g → ab. For each of these inclusions, we restrict to the image of Z/2:

g → a 1 a (ξ i ↓ |ρ 1 + ρ 2 ) (ξ i ↓ |ρ 2 ) ξ 1 ↓ 1 1 1 0 (ξ 2 -ξ 1 ) ↓ 0 -2 0 1 (ξ 3 -ξ 1 ) ↓ 0 -2 0 1 (ξ 4 -ξ 1 ) ↓ 0 0 0 0 , g → b 1 b (ξ i ↓ |ρ 1 + ρ 2 ) (ξ i ↓ |ρ 2 ) ξ 1 ↓ 1 1 1 0 (ξ 2 -ξ 1 ) ↓ 0 -2 0 1 (ξ 3 -ξ 1 ) ↓ 0 0 0 0 (ξ 4 -ξ 1 ) ↓ 0 -2 0 1 , g → ab 1 ab (ξ i ↓ |ρ 1 + ρ 2 ) (ξ i ↓ |ρ 2 ) ξ 1 ↓ 1 1 1 0 (ξ 2 -ξ 1 ) ↓ 0 0 0 0 (ξ 3 -ξ 1 ) ↓ 0 -2 0 1 (ξ 4 -ξ 1 ) ↓ 0 -2 0 1
.

• Any inclusion Z/2 ֒→ A 4 maps the generator of Z/2 to the only conjugacy class of elements of order 2 in A 4 . So it induces the map obtained by restricting to the two cycles ( 1) and ( 12) [START_REF] Valette | Introduction to the Baum-Connes conjecture[END_REF].

Z/2 ֒→ A 4 1 (12)(34) (χ i ↓ |ρ 1 + ρ 2 ) (χ i ↓ |ρ 2 ) χ 1 ↓ 1 1 1 0 (χ 2 -χ 1 -χ 3 -χ 4 ) ↓ 0 -4 0 2 (χ 3 -χ 1 ) ↓ 0 0 0 0 (χ 4 -χ 1 ) ↓ 0 0 0 0 An inclusion Z/3 ֒→ A 4 can
either map the generator h of Z/3 to the conjugacy class of (123), or to the conjugacy class of its square (132). So we have the two possibilities

h → (123) 1 (123) (132) ( χ i ↓ | i σ i ) ( χ i ↓ |σ 2 ) ( χ i ↓ |σ 3 ) χ 1 ↓ 1 1 1 1 0 0 (χ 2 -χ 1 -χ 3 -χ 4 ) ↓ 0 0 0 0 0 0 (χ 3 -χ 1 ) ↓ 0 j -1 j 2 -1 0 1 0 (χ 4 -χ 1 ) ↓ 0 j 2 -1 j -1 0 0 1 and h → (132) 1 (132) (123) ( χ i ↓ | i σ i ) ( χ i ↓ |σ 2 ) ( χ i ↓ |σ 3 ) χ 1 ↓ 1 1 1 1 0 0 (χ 2 -χ 1 -χ 3 -χ 4 ) ↓ 0 0 0 0 0 0 (χ 3 -χ 1 ) ↓ 0 j 2 -1 j -1 0 0 1 (χ 4 -χ 1 ) ↓ 0 j -1 j 2 -1 0
1 0 So we observe the claimed simultaneous diagonal block splitting.

Remark 11. It has been pointed out in [21, observation 50] that there are only two homeomorphism types of connected components which can occur in the orbit space of the 3-torsion subcomplex. An observation which facilitates our Bredon homology computations can be made on the connected components which are homeomorphic to a closed interval. Let us make a consideration on the preimage of such a component. Concerning our refined cell complex, by [21, lemma 16] at each vertex v of stabiliser type A 4 , we have two adjacent edges of stabiliser type Z/3 modulo the action of the vertex stabiliser. We attribute the cycle (123) ∈ A 4 to the image of the generator of one of the two stabilisers of type Z/3 of representative edges adjacent to v. Then we choose the preimage of (123) under the inclusion of the other copy of Z/3 to be the generator h. Since we have assumed that v maps to a point on a connected component homeomorphic to a closed interval in the quotient the 3-torsion subcomplex, v is the only point at which h can be related to our first copy of Z/3. So, we have obtained bases in which all the inclusions Z/3 ֒→ A 4 induce the first of the two possibilities in the last item of the proof of Lemma 10.

Proof of Theorem 1. By the properties of the cell complex X described in Section 2, all edge stabilisers are finite cyclic, all 2-cell stabilisers are trivial and there are no higher-dimensional cells. So the Bredon chain complex is concentrated in dimensions 0, 1 and 2, and has differentials 0

/ / σ∈ Γ \X (2) R C ({1}) Ψ 2 / / σ∈ Γ \X (1) R C (Z/ nZ ) Ψ 1 / / σ∈ Γ \X (0) R C (Γ σ ) / / 0,
where Ψ 1 , Ψ 2 are concentrated in blocks given by the cell stabiliser inclusions. Those blocks split by Lemma 10, and therefore we can reorder the rows and columns of Ψ 1 such that Ψ 1 becomes concentrated in three blocks on the diagonal,

(1) Ψ

(1)

1 , induced by the trivial and regular representations, (2) Ψ C (G) the subring generated by the regular representation of G when G is a cyclic group, respectively by the trivial representation when G is a finite group of different type. The trivial representation and the regular representation do obviously coincide when G is the trivial group. As the blocks of Ψ 2 are induced exclusively by maps {1} → Z/ nZ , the differential Ψ 2 is concentrated exclusively in blocks induced by regular representations. Therefore, from the Bredon chain complex we can split off a sequence 0

/ / σ∈ Γ \X (2) R C ({1}) Ψ 2 / / σ∈ Γ \X (1) R (1) C (Z/ nZ ) Ψ (1) 1 / / σ∈ Γ \X (0) R (1) C (Γ σ )
/ / 0, isomorphic to the cellular chain complex

0 / / C 2 ( Γ \X) ∂ 2 / / C 1 ( Γ \X) ∂ 1 / / C 0 ( Γ \X) / / 0,
computing the orbit space homology H • (BΓ; Z). The remainder of the Bredon chain complex is then concentrated in dimensions 0 and 1, and splits into a direct summand for ℓ = 2 and another one for ℓ = 3, both of the shape 0

/ / σ∈ Γ \X (1) R (ℓ) C (Z/ nZ ) Ψ (ℓ) 1 / / σ∈ Γ \X (0) R (ℓ) C (Γ σ ) / / 0, where R (ℓ)
C is defined by the source, respectively the target of Ψ (ℓ) 1 .

Reduction of the torsion subcomplexes

Proof of Theorem 2. The part of the Bredon complex that is due to 2-torsion is carried by the 2-torsion subcomplex of the action of Γ on hyperbolic space, and has the shape

0 → 1-cell orbits R (2)
C (Z/2) Ψ (2) 1 -→ orbits 0-cell R (2)
C (Z/2) orbits 0-cell R (2)
C (D 2 ) orbits 0-cell R (2)
C (D 3 ) orbits 0-cell R (2)
C (A 4 ) → 0,
where the direct sums run over cells with the respective stabiliser. At any vertex which is stabilised by a copy of Z/2, we have two adjacent edges with the same stabiliser type, and the cell stabiliser inclusions Z/2 ֒→ Z/2 induce isomorphisms on representation rings. So before splitting the representation rings, in the orbit space we can merge the two edges into one, getting rid of the vertex, without changing the homology of the Bredon complex. The part of the latter that is due to 2-torsion then has the partially reduced shape 0

→ (less) 1-cell orbits R (2)
C (Z/2) Ψ (2) 1 -→ o 2 j=1 R (2)
C (Z/2) orbits 0-cell R (2)
C (D 2 ) orbits 0-cell R (2)
C (D 3 ) orbits 0-cell R (2)
C (A 4 ) → 0,
where any of the vertices counted by j is the only vertex in a connected component of homeomorphism type in the quotient of the 2-torsion subcomplex. The splitting of Section 5 implies that the matrix for Ψ

(2)

1 has blocks •   1 1 0   ,   0 1 1   or   1 0 1   at inclusions Z/2 ֒→ D 2
, depending on which of the three cyclic subgroups of D 2 is hit,

• (1) at inclusions Z/2 ֒→ D 3 , • (2) at inclusions Z/2 ֒→ A 4 .
At any vertex which is stabilised by a copy of D 3 , we have two adjacent edges with stabiliser type Z/2, and the cell stabiliser inclusions Z/2 ֒→ D 3 induce isomorphisms on the 2-torsion parts of the splitted representation rings. So we can merge the two edges into one, getting rid of the vertex, without changing the homology of the Bredon complex. The latter then has the completely reduced shape As the matrix blocks between distinct connected components are zero, we now only need to compute the homology on a component of type , and take it to the multiplicity o 2 , and on components of types , , , and figure out the multiplicities for the latter.

0 → z 2 j=1 R (2) C (Z/2) Ψ (2) 1 -→ o 2 j=1 R (2) C (Z/2) orbits 0-cell R (2) C (D 2 ) orbits 0-cell R (2) C (A 4 ) → 0,
• On a connected component of type , the map R

C (Z/2) Ψ (2) 1 | -----→ R (2)
C (Z/2) must be the zero map, because of the opposing signs at edge origin and edge end. Therefore,

H n Ψ (2)
• | ∼ = Z, n = 0 or 1, 0, otherwise.

• On a connected component of type however, the map

R (2) C (Z/2) Ψ (2) 1 | -----→ R (2)
C (A 4 ) ⊕ R (2)
C (A 4 ) must be the diagonal map concatenated with multiplication by 2 and alternating sign, Z → Z ⊕ Z, x → (-2x, 2x), because of the matrix block (2) at inclusions Z/2 ֒→ A 4 .

This yields H n Ψ

(2)

• | ∼ = Z ⊕ Z/2, n = 0, 0, otherwise. • On a connected component of type
, the three maps coming from the three cyclic subgroups in D 2 do together constitute a matrix block

Z 3 ∼ = R (2) C (Z/2) 3 Ψ (2) 1 | -----→ R (2) C (D 2 ) 2 ∼ = Z 6 , Ψ (2)
1 | =         -1 -1 0 -1 0 -1 0 -1 -1 1 1 0 1 0 1 0 1 1        
This matrix has elementary divisors 2 of multiplicity one, and 1 of multiplicity two. This yields H n Ψ

• | ∼ = Z 3 ⊕ Z/2, n = 0, 0, otherwise. • On a connected component of type , the two maps coming from the edge stabilisers do together constitute a matrix block

Z 2 ∼ = R (2) C (Z/2) 2 Ψ (2) 1 | -----→ R (2) C (D 2 ) ⊕ R (2) C (A 4 ) ∼ = Z 4 , Ψ (2)
1 | =     1 -0 1 1 -1 0 0 -1 1 0 -2    
This matrix has elementary divisors 2 and 1, of multiplicity one each. This yields

H n Ψ (2)
• | ∼ = Z 2 ⊕ Z/2, n = 0, 0, otherwise.

Finally, we observe that precisely for each connected component except for those of type , we obtain one summand Z/2 for H 0 Ψ

(2) •

; and that each such connected component admits two orbits of D 2 , whether contained in A 4 or not (these orbits are counted by d 2 ). And precisely for each orbit of reduced edges (i.e., conjugacy classes of Z/2 in Γ, counted by z 2 ), we have obtained a summand Z for H 0 Ψ

(2) • .

Proof of Theorem 3. The part of the Bredon complex that is due to 3-torsion is carried by the 3-torsion subcomplex of the action of Γ on hyperbolic space, and has the shape

0 → 1-cell orbits R (3) C (Z/3) Ψ (3) 1 -→ 0-cell orbits R (3)
C (Z/3)

0-cell orbits R (3)
C (D 3 ) 0-cell orbits R (3)
C (A 4 ) → 0,
where the direct sums run over cells with the respective stabiliser. At any vertex which is stabilised by a copy of Z/3, we have two adjacent edges with the same stabiliser type, and the cell stabiliser inclusions Z/3 ֒→ Z/3 induce isomorphisms on representation rings. So before splitting the representation rings, in the orbit space we can merge the two edges into one, getting rid of the vertex, without changing the homology of the Bredon complex. The part of the latter that is due to 3-torsion then has the partially reduced shape 0 → (less)

1-cell orbits R

C (Z/3) Ψ (3) 1 -→ o 3 j=1 R (3)
C (Z/3)

0-cell orbits R (3)
C (D 3 ) 0-cell orbits R (3)
C (A 4 ) → 0, where any of the vertices counted by j is the only vertex in a connected component of homeomorphism type in the quotient of the 3-torsion subcomplex. The splitting of Section 5 implies that the matrix for Ψ

C (Z/3) Ψ (3) 1 -→ o 3 j=1 R (3)
C (Z/3)

2ι 3 j=1 R (3)
C (D 3 ) → 0,
where the vertices of type D 3 are the exclusive vertices of connected components of type . As the matrix blocks between distinct connected components are zero, we now only need to compute the homology on a component of type , and take it to the multiplicity o 3 , and on a component of type , and take it to the multiplicity ι 3 .

submodules generated by the bases {ξ 2 -ξ 2 (1)ξ 1 , . . . , ξ n -ξ n (1)ξ 1 } at each vertex of BΓ sing , and the image of the trivial characters of the edges. The latter image is isomorphic to the image of the boundary map from 1-cells to 0-cells in BΓ, so we obtain

• a monomorphism H 1 (BΓ; Z) ֒→ H Fin 1 (EΓ; R C )
• and an isomorphism H Fin 0 (EΓ; R C ) ∼ = H 0 (BΓ; Z) ⊕ Z[FC(Γ) \ {1}]. Using Mislin's map (1), we obtain the claimed result.

For Γ a Hilbert modular group or orientable Fuchsian group, dim EΓ sing = 0, so we can apply the above proposition.

Recalls on the assembly map

We will only outline the meaning of this assembly map. For any discrete group G, we define its reduced C * -algebra, C * r (G), and the K-theory of the latter as in [START_REF] Valette | Introduction to the Baum-Connes conjecture[END_REF]. According to Georges Skandalis, the algebras C * r (G) are amongst the most important and natural examples of C * -algebras. It is difficult to compute their K-theory directly, so we use a homomorphism constructed by Paul Baum and Alain Connes [START_REF] Baum | Classifying space for proper actions and K-theory of group C * -algebras, C * -algebras: 1943-1993[END_REF],

µ i : K G i (EG) -→ K i (C * r (G)), i ∈ N ∪ {0},
called the (analytical) assembly map. A model for the classifying space for proper actions, written EG, is in the case of the Bianchi groups given by hyperbolic three-space (being isomorphic to their associated symmetric space), the stabilisers of their action on it being finite. The Baum-Connes conjecture now states that the assembly map is an isomorphism. The conjecture can be stated more generally, see [START_REF] Baum | Classifying space for proper actions and K-theory of group C * -algebras, C * -algebras: 1943-1993[END_REF]. The Baum-Connes conjecture implies several important conjectures in topology, geometry, algebra and functional analysis. Groups for which the assembly map is surjective verify the Kaplansky-Kadison conjecture on the idempotents. Groups for which it is injective satisfy the strong Novikov conjecture and one sense of the Gromov-Lawson-Rosenberg conjecture, namely the sense predicting the vanishing of the higher Â-genera (see the book of Mislin and Valette [START_REF] Mislin | Proper group actions and the Baum-Connes conjecture[END_REF] for details).

The assembly map for the Bianchi groups. Julg and Kasparov [START_REF] Julg | Operator K-theory for the group SU(n, 1)[END_REF] have shown that the Baum-Connes conjecture is verified for all the discrete subgroups of SO(n, 1) and SU(n, 1). The Lobachevski model of hyperbolic three-space gives a natural identification of its orientation preserving isometries, with matrices in PSO [START_REF] Bianchi | Sui gruppi di sostituzioni lineari con coefficienti appartenenti a corpi quadratici immaginarî[END_REF][START_REF] Baum | Classifying space for proper actions and K-theory of group C * -algebras, C * -algebras: 1943-1993[END_REF]. So especially, the assembly map is an isomorphism for the Bianchi groups; and we have obtained the isomorphism type of K i (C * r (Γ)). An alternative way to check that the Baum-Connes conjecture is verified for the Bianchi groups, is using "a-T-menability" in the sense of Gromov, also called the Haagerup property [START_REF] Cherix | Groups with the Haagerup property[END_REF]. Cherix, Martin and Valette prove in [START_REF] Cherix | Spaces with measured walls, the Haagerup property and property (T)[END_REF] that among other groups, the Bianchi groups admit a proper action on a space "with measured walls". In [START_REF] Cherix | Groups with the Haagerup property[END_REF], Haglund, Paulin and Valette show that groups with such an action have the Haagerup property. Finally Higson and Kasparov [START_REF] Higson | E-theory and KK-theory for groups which act properly and isometrically on Hilbert space[END_REF] prove that the latter property implies the bijectivity of several assembly maps, and in particular the Baum-Connes conjecture.

The assembly map for the Bianchi groups is more deeply studied in [START_REF] Fuchs | Equivariant K-homology of Bianchi groups in the case of non-trivial class group[END_REF].

Appendix

On the machine [START_REF] Bianchi | Open source program (GNU general public license)[END_REF], we obtain the following results: m class no. β 1 2-torsion subcomplex, reduced 3-torsion subcomplex, reduced H Fin 0

H Fin 1 7 1 1 Z 3 Z 2 ⊕ Z β 1 2 1 1 Z 5 ⊕ Z/2 Z 2 ⊕ Z β 1 11 1 1 Z 4 ⊕ Z/2 Z 2 ⊕ Z β 1 19 1 1 Z 3 ⊕ Z/2 Z ⊕ Z β 1 15 2 2 Z 4 Z 3 ⊕ Z β 1 5 2 2 Z 6 ⊕ Z/2 Z 2 ⊕ Z β 1 6 2 2 Z 5 ⊕ Z/2 Z 3 ⊕ Z β 1 43 1 2 Z 3 ⊕ Z/2 Z ⊕ Z β 1 35 2 3 Z 4 Z 3 ⊕ Z β 1 10 2 3 Z 6 ⊕ Z/2 Z 2 ⊕ Z β 1 51 2 3 Z 5 ⊕ Z/2 ⊕ Z/2 Z 2 ⊕ Z β 1 13 2 3 Z 6 ⊕ Z/2 Z 2 ⊕ Z β 1 67 1 3 Z 3 ⊕ Z/2 Z ⊕ Z β 1 22 2 5 Z 5 ⊕ Z/2 Z 3 ⊕ Z β 1 91 2 5 Z 4 Z 3 ⊕ Z β 1 115 2 7 Z 4 Z 3 ⊕ Z β 1 123 2 7 Z 5 ⊕ Z/2 ⊕ Z/2 Z 2 ⊕ Z β 1 163 1 7 Z 3 ⊕ Z/2 Z ⊕

1 ,

 1 induced by the 3-torsion subgroups. Let us denote by R (1)

  • (1, 1) at inclusions Z/3 ֒→ D 3 , inclusions Z/3 ֒→ A 4 (by Remark 11, we can choose bases such that we exclusively get the first of these two blocks, if we desire), At any vertex which is stabilised by a copy of A 4 , we have two adjacent edges with stabiliser type Z/3, and the cell stabiliser inclusions Z/3 ֒→ A 4 induce isomorphisms on the 3-torsion parts of the splitted representation rings. So we can merge the two edges into one, getting rid of the vertex, without changing the homology of the Bredon complex. The latter then has the completely

Table 1 .

 1 Connected components of reduced torsion subcomplex quotients for the Bianchi groups

	2-torsion subcomplex components	counted by	3-torsion subcomplex components	counted by

  where the vertices of type D 2 are the bifurcation points in the connected components of types and , and the vertices of type A 4 are the endpoints in the connected components of types and . Norbert Krämer [13, Satz 8.3 and Satz 8.4] has shown that the types , , and are all possible homeomorphism types which connected components of the 2-torsion subcomplex of the action of a Bianchi group on hyperbolic space can have.

• On a connected component of type , the map R

C (Z/3) must be the zero map, because of the opposing signs at edge origin and edge end. Therefore,

, n = 0 or 1, 0, otherwise.

• On a connected component of type however, the map

must be the the map Z 2 → Z ⊕ Z, (x, y) → (-x -y, x + y), because of the matrix block

(1, 1) at inclusions Z/3 ֒→ D 3 . This yields H n Ψ

(3)

Counting the connected components yields the claimed multiplicities.

Representation ring splitting in a more general setting

Representation ring splitting, as introduced in this paper, relies on the groups under study admitting a nice system of subgroups. Without this prerequisite, we can still make the statements in the present section, but this does not essentially improve on what has already been obtained by Lück and Oliver [START_REF] Lück | Chern characters for the equivariant K-theory of proper G-CW-complexes[END_REF] based on the split coefficient systems of S lominska [START_REF] Jolanta | On the equivariant Chern homomorphism[END_REF].

First, we want to sharpen the following lemma of [START_REF] Mislin | Proper group actions and the Baum-Connes conjecture[END_REF]. This will allow us to apply representation ring splitting to determine the free part of the equivariant K-homology of any group with vanishing geometric torsion dimension, for instance the Hilbert modular groups and the Fuchsian groups.

Lemma 12 ([18]

). Let G be an arbitrary group and write FC(G) for the set of conjugacy classes of elements of finite order in G. Then there is an isomorphism

Let EG sing denote the singular part of the classifying space EG for proper actions of a group G, namely the subcomplex consisiting of all points in EG with non-trivial stabiliser. Mislin [START_REF] Mislin | Proper group actions and the Baum-Connes conjecture[END_REF] indicates that up to G-homotopy, EG sing is uniquely determined by G. Hence, dim EG sing can be defined as the minimal dimension of EG sing within its G-homotopy type.

Mislin [START_REF] Mislin | Proper group actions and the Baum-Connes conjecture[END_REF] shows that for any group G, there is a natural map (1) H Fin q (EG; R C ) → H q (BG; Z), which is an isomorphism in dimensions q > dim EG sing + 1, and injective in dimension q = dim EG sing + 1. In the special case of vanishing geometric torsion dimension, we can sharpen this statement together with Lemma 12 as follows.

Proposition 13. For any group Γ with dim EΓ sing = 0, we have H Fin q (EΓ; R C ) ∼ = H q (BΓ; Z) in degrees q > 0, and H Fin 0 (EΓ; R C ) ∼ = Z[FC(Γ)]. Proof. Consider a classifying space EΓ with zero-dimensional EΓ sing . Here, the Bredon complex of EΓ is reduced in positive degrees to the cellular chain complex of BΓ. For any stabiliser group of a vertex in EΓ sing , with character table {ξ 1 , . . . , ξ n }, where ξ 1 is the trivial character, we choose the basis {ξ 1 , ξ 2 -ξ 2 (1)ξ 1 , . . . , ξ n -ξ n (1)ξ 1 } for its complex representation ring. Then clearly any morphism induced by inclusions of the trivial edge stabilisers, induces a map with image contained in the submodule generated by ξ 1 in the representation ring. So the Bredon complex splits in degree 0 into a direct sum of the


C Herzet

A Malti

SAFE SCREENING TESTS FOR LASSO BASED ON FIRMLY NON-EXPANSIVENESS

Keywords: 1 -norm minimization, LASSO, screening techniques

This technical report focusses on safe screening techniques for the LASSO problem. We derive a new sphere test, coined RFNE, exploiting the firmly non-expansiveness of projection operators. Our test generalizes some methods of the literature but, unlike the latter, exploits approximated primal-dual solutions of the LASSO problem while remaining safe and effective. Our simulation results show that the proposed RFNE test outperforms the best methodology of the state of the art, namely the GAP test derived by Fercoq et al.

INTRODUCTION

In this document, we focus on the (nonnegative) LASSO problem 1 :

x λ ∈ arg min x≥0 P λ (y, x), (1)
where P λ (y, x) = 1 2 y -Ax 2 2 + λ x 1 , and y ∈ R m , x ∈ R n , A = [a 1 , . . . , a n ] ∈ R m×n with a i 2 = 1 for all i. During the last decade, 1 -norm penalization has revealed to be a proper regularization scheme for many inverse problems (see [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF]). Therefore, the study of computationally-efficient procedures solving [START_REF] Mario | Teaching a new trick to an old dog: Revisiting the quadratic programming formulation of sparse recovery using admm[END_REF] has become an active field of research [START_REF] Osborne | A new approach to variable selection in least squares problems[END_REF][START_REF] Efron | Least angle regression[END_REF][START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF][START_REF] Afonso | Fast image recovery using variable splitting and constrained optimization[END_REF].

Recently, an important step in that direction has been carried out in [START_REF] Ghaoui | Safe feature elimination in sparse supervised learning[END_REF] by El Ghaoui et al.: the authors introduced a "screening" technique, allowing for a safe 2 identification of some of the zeros in x λ ; the latter components can thus be ignored in the LASSO computations leading to (potentially) huge memory and computational savings. Since the cornerstone paper by El Ghaoui et al., many contributions addressing the screening problem have appeared in the literature, see [START_REF] Wang | Lasso screening with a small regularization parameter[END_REF][START_REF] Zhen | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF][START_REF] Zhen | Fast lasso screening tests based on correlations[END_REF][START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF][START_REF] Zhen | Screening tests for lasso problems[END_REF][START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF][START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF].

In this paper, we propose a new screening method belonging to the family of "safe sphere tests". Our approach relies on properties of projection onto convex sets and generalizes some methods of the state of the art [START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]. In particular, unlike previous works, the proposed screening technique is ensured being safe even when the primal-dual solution exploited in the test is corrupted by some error 3 . We show that our methodology leads to superior performance than the best sphere test of the current state of the art (namely GAP [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]), at both a theoretical (in some specific setups, see Lemma 1) and an empirical level.

SOME CONVEX CONSIDERATIONS

In this section, we remind some elements of convex analysis which will serve as building blocks in the next sections.

Problem [START_REF] Mario | Teaching a new trick to an old dog: Revisiting the quadratic programming formulation of sparse recovery using admm[END_REF] is convex and has always (at least) one solution x λ [START_REF] Tibshirani | The lasso problem and uniqueness[END_REF]. The dual problem associated to (1) can be written as (see for example [START_REF] Zhen | Screening tests for lasso problems[END_REF]):

θ λ = arg min θ∈D D λ (y, θ), (2)
where

D λ (y, θ) = 1 2 y 2 2 - 1 2 y -λθ 2 2 , D = θ ∈ R m : a T i θ ≤ 1, 1 ≤ i ≤ n .
Since D λ (y, θ) is a strictly convex function and D a closed set, there exists one unique θ λ satisfying [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF]. We can also notice that (2) can be recast as a projection problem, θ λ being the projection of y/λ onto D. We will exploit this property in section 4 to state Theorem 1.

From the KKT conditions, it can be shown that any primal-dual optimal couple (x λ , θ λ ) must satisfy the following optimality conditions [START_REF] Bertsekas | Nonlinear Programming[END_REF]Prop. 5.1.5]:

x λ ≥ 0, a T i θ λ ≤ 1 for all i, (3)
a T i θ λ -1 x λ (i) = 0 for all i, (4)
y = λθ λ + Ax λ , (5)
where x λ (i) denotes the ith component of x λ . From these conditions, it can be seen that if λ ≥ λ max A T y ∞ , then the only possible solution is x λ = 0. In the sequel we will therefore restrict our attention to the case λ < λ max .

SCREENING TESTS

It is well-known that the solutions of (1) are typically sparse. Optimality conditions (3)-( 5) provide some information about the position of zeros in x λ . Indeed, if a i , θ λ < 1 then necessarily x λ (i) = 0 from (4). Defining the support of x ≥ 0 and the active set associated to θ ∈ D as

supp(x) = {i ∈ {1, . . . , n} : x(i) > 0}, acts(θ) = i ∈ {1, . . . , n} : a T i θ = 1 ,
this can also be rewritten as

supp(x λ ) ⊆ acts(θ λ ). (6)
Knowing θ λ thus gives a valuable information about the support of x λ . Of course, in practice θ λ is unknown and solving (2) is unfortunately as difficult as solving [START_REF] Mario | Teaching a new trick to an old dog: Revisiting the quadratic programming formulation of sparse recovery using admm[END_REF]. Nevertheless, as first noted in [START_REF] Ghaoui | Safe feature elimination in sparse supervised learning[END_REF], (4) can be of interest to identify the position of some of the zeros in x λ : assume one can identify a region R ⊂ R m such that θ λ ∈ R; then the following inequality trivially holds

a T i θ λ ≤ max θ∈R a T i θ,
and from (4), we thus have

max θ∈R a T i θ < 1 ⇒ x λ (i) = 0. (7)
This observation was the cornerstone of the "safe" screening test proposed in [START_REF] Ghaoui | Safe feature elimination in sparse supervised learning[END_REF]. Since this seminal paper, many different tests, corresponding to different choices of R (sphere, dome, etc), have been proposed in the literature, see [START_REF] Zhen | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF][START_REF] Zhen | Fast lasso screening tests based on correlations[END_REF][START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF][START_REF] Zhen | Screening tests for lasso problems[END_REF][START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF][START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF].

In this paper, we focus on the family of sphere tests because: i) they are conceptually very simple; ii) they have been shown to achieve state-of-the-art performance [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF]. In such a case, R = S(q, r) {θ ∈ R m : θq 2 ≤ r}) and the screening test [START_REF] Ghaoui | Safe feature elimination in sparse supervised learning[END_REF] takes a very simple form:

a T i q + r < 1 ⇒ x λ (i) = 0. (8)
The sphere tests proposed in the literature differ in the definition of the center q and the radius r, see [START_REF] Ghaoui | Safe feature elimination in sparse supervised learning[END_REF][START_REF] Zhen | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF][START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF][START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF]. We review the most competitive sphere tests of the literature in sections 4 and 5. We present some methodologies deriving from the properties of projection onto convex sets [START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF] in section 4. In section 5, we recall the main equations of the GAP test [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF], which is a safe screening method currently achieving the best performance of the state of the art.

TESTS BASED ON PROJECTION PROPERTIES

A recent line of research has concentrated on the design of screening methods exploiting the knowledge of a dual optimal point θ λ with λ = λ. Among the most effective screening methods relying on this approach, let us mention the sphere test based on "variational inequalities" presented in [START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF] and the methods exploiting the non-expansiveness property of projection operators onto convex sets in [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]. The inequalities exploited in these papers are summarized and extended in the following result:

Theorem 1. Let θ ∈ D. Then, θ λ -θ + 1 2 y λ - y λ 2 ≤ 1 2 y λ - y λ 2 , (9)
for any y ∈ Y(θ), where

Y(θ) =    y : y = λ θ + i∈acts(θ) a i x(i), x ≥ 0    . ( 10
)
This result is a direct consequence of the firmly nonexpansiveness (FNE) property of projection operators (see [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]) and of the optimality conditions (3)- [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. A proof can be found in section 9. In the sequel we will refer to the screening methods deriving from Theorem 1 as FNE sphere tests.

As a consequence of Theorem 1, safe screening tests can be derived from any sphere S(q fne , r fne ) satisfying

q fne = θ + 1 2 y λ -y λ , r fne = 1 2 y λ -y λ 2 , ( 11
)
where θ ∈ D and y ∈ Y(θ). In particular, the spheres proposed in [START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF][START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF] are obtained as particular cases of (11): if θ = θ λ and y = λ θ λ for some λ = λ, (11) corresponds to the "variational" sphere proposed in [13, Section 2]; similarly, if θ = θ λ and x = βx λ , for some β > 0, one recovers the EDDP sphere proposed in [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]Th. 15]. It can be seen from Theorem 1 that the choice of y constitutes a degree of freedom in the construction of an FNE sphere test. In practice, a good rule of thumb consists in choosing y close to y: as seen from ( 11), the radius of the FNE sphere can be decreased by a proper choice of y . Since y ∈ Y(θ) and y ∈ Y(θ λ ), one should therefore choose θ such that Y(θ) is close to Y(θ λ ). In particular, if some θ λ with λ λ is available (as it occurs in sequential implementations of LASSO), setting θ = θ λ is certainly a sensible choice.

However, in practice, this approach faces an important bottleneck: only finite-precision approximations of θ λ , say 4θλ ∈ D, are available in numerical solvers. Unfortunately, simply using θ = θλ in Theorem 1 (as implicitly done in [START_REF] Liu | Safe screening with variational inequalities and its application to lasso[END_REF]) typically leads to poor results for the following reason: in most cases the cardinality of acts( θλ ) is equal to 1 and Y( θλ ) thus corresponds to a half-line in R m ; on the other hand, the cardinality of acts(θ λ ) is often much larger 5 than 1 and Y(θ λ ) is a high-dimensional cone in R m ; hence, we are likely to fail finding y ∈ Y( θλ ) close to y ∈ Y(θ λ ).

To deal with this issue, an approach (implicitly) considered in [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF] consists in approximating acts( θλ ) by supp(x λ ) in the definition of Y( θλ ) (see [START_REF] Zhen | Fast lasso screening tests based on correlations[END_REF]), where xλ is a finite-precision approximation of x λ . Unfortunately, such approximation may lead to a violation of the hypotheses of Theorem 1 and this approach is then no longer ensured to lead to a safe screening test.

We propose a solution to this issue in section 6 by deriving a new safe sphere test relaxing the constraint of a perfect knowledge of θ λ while allowing for a fine tuning of y . In the next section, we recall the expressions of the GAP sphere test which constitutes one of the building blocks of the result presented in Theorem 2.

THE GAP SPHERE TEST

In [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF], the authors used another route to derive a safe sphere test: they exploited the dual gap between the primal and the dual functions of the LASSO problem. More specifically, they showed that the following inequality holds for any primal-dual feasible points (x, θ): θ λ (y) -2 ≤ 2λ -2 (P λ (y, x) -D λ (y, θ)). [START_REF] Zhen | Screening tests for lasso problems[END_REF] It immediately follows that the sphere S(q gap , r gap ) with

q gap = θ, r gap = 2λ -2 (P λ (y, x) -D λ (y, θ)), (13)
and x ≥ 0, θ ∈ D, defines a safe sphere test. The GAP sphere test has been shown to lead to very impressive results.

In particular, the radius of the sphere r gap tends to zero as (x, θ) converges to (x λ , θ λ ).

Because the GAP sphere ( 13) is safe for any primal-dual feasible point, it might be interesting to compare it with the FNE sphere test defined in [START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF] for (x, θ) = (x λ , θ λ ), λ = λ. The next lemma, whose proof is available in section 9, provides an answer to this question: Lemma 1. Assume one wants to solve (1) for a given λ > 0 and a primal-dual solution (x λ , θ λ ), λ = λ < λ max , is available. Then, there exists y ∈ Y(θ λ ) such that the FNE sphere defined in [START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF] and the GAP sphere defined in (13) with (x, θ) = (x λ , θ λ ) verify S(q fne , r fne ) ⊂ S(q gap , r gap ),

that is the FNE sphere is strictly included in the GAP sphere.

In particular, (14) holds when y is a minimizer of r fne over Y(θ λ ).

5 From (6), we have that card acts θ λ ≥ card supp x λ .

The inclusion [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF] implies that any zero identified by the GAP test will also be identified by some FNE test. Hence, as far as a primal-dual optimal point (x λ , θ λ ) is available, Lemma 1 suggests that using FNE rather than GAP screening tests may be rewarding. We discuss the implementation of FNE tests based on the approximate knowledge of (x λ , θ λ ) in the next section.

RELAXED FNE SPHERE TESTS

Motivated by Lemma 1, it may be tempting to derive FNE sphere tests by setting θ = θ λ with λ λ . Unfortunately, as discussed at the end of section 4, one has to face to the problem of the finite precision of θ λ in practical numerical solvers.

In the next theorem, we provide a solution to this issue by deriving a relaxed version of the FNE sphere test: Theorem 2. Let x and θ be primal and dual feasible points and let

y = λ θ + Ax. (15)
Then,

θ λ -q fne 2 ≤ r fne + r slack , (16)
where q fne and r fne are defined in [START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF] and

r slack = (λ ) -1/2 i x(i) 1 -a T i θ
A proof of this result can be found in section 9. It essentially relies on the arguments developed in Theorem 1 and the use of the GAP inequality [START_REF] Zhen | Screening tests for lasso problems[END_REF].

There are two main differences between Theorems 1 and 2. First, the definition of y in Theorem 2 is a relaxed version of the one in Theorem 1. More specifically, unlike in Theorem 1, Theorem 2 does not require that the positions of the nonzero elements in x correspond to indices in acts(θ). Second, the radius of the sphere defined in [START_REF] Tibshirani | The lasso problem and uniqueness[END_REF] is larger than the one defined in [START_REF] Zhen | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF]: the extra term in ( 16), r slack , penalizes the violation of the complementary slackness condition (4). This term disappear as soon as supp(x) ⊆ acts(θ). In particular, if (x, θ) = (x λ , θ λ ), we have r slack = 0 and ( 16) corresponds to the standard FNE test defined in Theorem 1. In this sequel, we will refer to the screening methods deriving from Theorem 2 as "robust FNE" (RFNE) tests.

We next consider the RFNE sphere test obtained by particularizing Theorem 2 to y defined as follows:

y = arg min ỹ∈ Ŷ( θλ ) r fne , (17)
with

Ŷ( θλ ) =    ỹ ∈ R m : λ θλ + i∈supp(x λ ) a i x(i), x ≥ 0    ,
and (x λ , θλ ) are some finite-precision approximation of (x λ , θ λ ). In practice, (x λ , θλ ) can for example correspond to the output of the numerical solver at a given iteration or, in a sequential implementation, to (an approximation of) (x λ , θ λ ) with λ > λ. We assess the performance of such a sphere test in the next section.

SIMULATION RESULTS

In this section, we assess the performance of the screening test presented in section 6. We compare our approach to GAP sphere test which is currently the most competitive safe method of the state of the art. Our simulation setup is as follows. The entries of A ∈ R 128×512 are drawn from a uniform distribution on [0, 1]. The columns of A are then normalized such that a i 2 = 1 for all i. y = Ax where x is a vector with 50 nonzero elements whose amplitude is drawn from a uniform distribution on [0, 1]. We consider a sequential implementation of LASSO where the solution of (1) has to be computed for λ t /λ max = 0.95 × 10 -2t/[T -1] , t ∈ {1, . . . , T -1} and T = 30. For each λ t , we search for a solution of (1) with a FISTA procedure [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] initialized with the solution obtained for λ t-1 (warm start). The solver is run until a duality gap P (y, xλt ) -D(y, θλt ) smaller than = 10 -5 is reached. For each value of λ t , we apply a dynamic screening strategy as suggested in [START_REF] Bonnefoy | A dynamic screening principle for the lasso[END_REF][START_REF] Bonnefoy | Dynamic screening: Accelerating first-order algorithms for the lasso and group-lasso[END_REF]: a screening test is carried out every 10 iterations by exploiting the output (x λt , θλt ) of FISTA; the zeros which have been identified are removed from the problem.

Fig. 1 illustrates the proportion of zeros (with respect to the total number of zeros in x λt ) identified by the GAP and the proposed RFNE sphere test. The x-axis (resp. yaxis) corresponds to the logarithm of the ratio (λ t /λ max ) -1 (resp. the number of iterations). One can notice that the proposed RFNE test allows for the identification of many more zeros of x λ than the GAP method at the very first iteration of the numerical solver. This can be understood as follows. The first screening test performed when considering problem (1) with λ t is based on (x λt , θλt ) = (x λt-1 , θλt-1 ) where (x λt-1 , θλt-1 ) is the final approximation of (x λt-1 , θ λt-1 ) computed by FISTA; now, provided the FISTA solver has reached a fair convergence, the gap in the complementary slackness condition (and thus r slack in ( 16)) must be very small. In this case, the RFNE test presented in section 6 is close to the FNE test in [START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF]. We can thus expect the result in Lemma 1 to apply, that is the (R)FNE sphere is strictly included in the GAP sphere. This is indeed what we observe in terms of screening performance in Fig. 1. On the other hand, during the subsequent iterations, the two screening methods have similar performance. We have run simulations in different setups and with different dictionaries (not presented here for conciseness) and always observed this same behavior.

CONCLUSIONS

In this report, we proposed a new safe sphere screening test, namely RFNE. Our method generalizes state of the art methods and is ensured to be safe. It relies on estimated primaldual solutions rather than exact ones which are unreachable in practice. We compared the proposed method to the best safe sphere test of the state of the art, namely GAP. We showed that RFNE performs at least as well as GAP in terms of zeros identification. Moreover, RFNE is able to identify far many more zeros at early iterations of the resolution process.

APPENDIX

Proof of Theorem 1: Let θ ∈ D and y be defined as in [START_REF] Zhen | Fast lasso screening tests based on correlations[END_REF] for some x such that

x(i) ≥ 0 i ∈ acts(θ), x(i) = 0 otherwise. ( 18
)
Clearly, θ, y and x satisfy the optimality conditions (3)-( 5). As a consequence, θ is a solution of the dual problem (2) with y and λ as input: θ can thus also be seen as the projection of y /λ onto D (see section 2). The same remark applies for θ λ and y/λ. Hence, θ λ , y/λ, θ and y /λ must satisfy the firmly non-expansiveness property of projections onto convex sets, see [START_REF] Wang | Lasso screening rules via dual polytope projection[END_REF]Th. 12]. More specifically, we have

θ λ -θ 2 2 + y λ -θ λ - y λ -θ 2 2 ≤ y λ - y λ 2 2 . (19)
Inequality [START_REF] Zhen | Learning sparse representations of high dimensional data on large scale dictionaries[END_REF] follows by rearranging the terms.

Proof of Lemma 1: Assume we search for the solution of the LASSO problem (1) for some 0 < λ < λ max . Suppose moreover that a primal-dual solution (x λ , θ λ ) is known for some λ = λ, λ < λ max . Consider the sphere S(q fne , r fne ) built from [START_REF] Wu | The 2-codeword screening test for lasso problems[END_REF] by setting θ = θ λ and y ∈ Y(θ λ ). From inequality [START_REF] Bonnefoy | Dynamic screening: Accelerating first-order algorithms for the lasso and group-lasso[END_REF], it is easy to see that any θ λ ∈ S(q fne , r fne ) must also verify θ λ ∈ S(q ne , r ne ) where

q ne = θ λ , r ne = y λ -y λ 2 . (20)
Hence, S(q fne , r fne ) ⊆ S(q ne , r ne ). To prove the statement of Lemma 1, it is therefore sufficient to show that S(q ne , r ne ) ⊂ S(q gap , r gap ),

for some y ∈ Y(θ λ ). Since q ne = q gap = θ λ , this is equivalent to proving that r ne < r gap for some y ∈ Y(θ λ ).

First, particularizing the definition of r gap in (13) to (x, θ) = (x λ , θ λ ), and taking optimality conditions (3)-( 5) into account, we find:

r gap = 1 - λ λ θ λ 2 . (23)
Moreover, evaluating r ne in (20) for y = λ θ λ + λ λ Ax λ ∈ Y(θ λ ), we obtain:

r ne = 1 - λ λ θ λ 2 . (24)
Hence,

min y ∈Y(θ λ ) r ne ≤ r gap . (25)
The above inequality is actually strict because of the following arguments. Let us first exploit the definition of Y(θ λ ) to rewrite r ne as a function of x:

r ne = y λ -λ θ λ -λ -1 i∈acts(θ λ ) a i x(i) 2 . (26)
Clearly, optimizing r ne over Y(θ λ ) in ( 25) is equivalent to optimizing the right-hand side of (26) over x ≥ 0. The particular value of r ne obtained in (24) corresponds to the choice x = λ λ x λ . We next show that x = λ λ x λ is not a minimizer of r ne because optimality conditions cannot be satisfied.

Let x ne be a minimizer of r ne ; then it must satisfy [17, Prop. 2.1.2]: i ∂r ne ∂x(i) x=x ne (x(i)x ne (i)) ≥ 0 for all x ≥ 0 (27)

First note that supp(x λ ) = ∅ (and thus acts(θ λ ) = ∅) because we assume λ < λ max . Now we have for any i ∈ acts(θ λ ):

∂r ne ∂x(i) x= λ λ x λ = -2a T i y λ -θ λ - Ax λ λ , = 2 1 - λ λ a T i θ λ , = 2 1 - λ λ , (28)
where the second equality follows from the fact that y = λ θ λ + Ax λ and the last one from a T i θ λ = 1 for all i ∈ acts(θ λ ). If λ < λ, then (1λ /λ) > 0 and (27) cannot be satisfied with x ne = λ λ x λ because setting x as

x(i) < λ λ x λ (i), i ∈ supp(x λ ), x(i) = 0, otherwise.

(29) leads to a violation of the inequality in (27). Similarly, if λ > λ, (1λ /λ) < 0 and a violation of (27) with x ne = λ λ x λ occurs by setting x(i) > λ λ x λ (i), i ∈ supp(x λ ), x(i) = 0, otherwise.

This proves that r ne < r gap for some y ∈ Y(θ λ ) and thus S(q fne , r fne ) ⊂ S(q gap , r gap ).

Finally, the last assertion of Lemma 1 directly follows from the fact that, by definition, r fne = r ne /2.

Proof of Theorem 2: Let y be defined as in [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF] and let θ λ (y ) denotes the projection of y /λ onto D. Applying Theorem 1, we have that (9) holds (with the substitution θ ← θ λ (y )). Using a triangle inequality leads to

θ λ -θ + 1 2 y λ - y λ 2 ≤ 1 2 y λ - y λ 2 + θ λ (y ) -θ 2 .
Since θ λ (y ) ∈ D, we can use Ferocq's inequality [START_REF] Zhen | Screening tests for lasso problems[END_REF] to bound the second term in the right-hand of this inequality.

More specifically, let x ≥ 0, θ ∈ D and y = λ θ + Ax as in [START_REF] Fercoq | Mind the duality gap: safer rules for the lasso[END_REF], we find after some algebraic manipulations that θ λ (y )θ 2 ≤ (λ ) -1/2 i x(i) 1a T i θ . (31)

Fig. 1 .

 1 Fig. 1. Proportion of zeros identified by the screening procedures as a function of -log 10 (λt/λmax) (x-axis) and the (log 10 of the) number of iterations (y-axis): GAP (top) and safe FNE (bottom).

This error is related for instance to the finite numerical precision of numerical solvers.

Without loss of generality we assume that θλ ∈ D because this configuration can always be achieved by dual scaling, see[START_REF] Ghaoui | Safe feature elimination in sparse supervised learning[END_REF] Section 3.4].

* Cédric Herzet was supported by the French National Research Agency through the GERONIMO and BECOSE projects. 1 instance of (1), see [1, Section 2].