Éphane St

Sabourau

ONE-CYCLE SWEEPOUT ESTIMATES OF ESSENTIAL SURFACES IN CLOSED RIEMANNIAN MANIFOLDS

Keywords: 2010 Mathematics Subject Classification. Primary 53C23; Secondary 53C20 Sweepouts, width, waist, min-max, volume, curvature-free geometric inequalities

We present new-curvature one-cycle sweepout estimates in Riemannian geometry, both on surfaces and in higher dimension. More precisely, we derive upper bounds on the length of one-parameter families of one-cycles sweeping out essential surfaces in closed Riemannian manifolds. In particular, we show that there exists a homotopically substantial one-cycle sweepout of the essential sphere in the complex projective space, endowed with an arbitrary Riemannian metric, whose one-cycle length is bounded in terms of the volume (or diameter) of the manifold. This is the first estimate on sweepout volume in higher dimension without curvature assumption. We also give a detailed account of the situation for compact Riemannian surfaces with or without boundary, in relation with questions raised by P. Buser and L. Guth.

Introduction

At the end of his essay on systolic geometry [Gr96, §4.A.7], M. Gromov suggested to consider min-max volumes over families of cycles (or sweepouts) satisfying nontrivial topological conditions as generalizations of the notion of systole. These min-max volumes -known under different names, e.g., waist, width, diastole, slicing -have recently been studied in numerous works, cf. [START_REF] Gromov | Isoperimetry of waists and concentration of maps[END_REF], [START_REF] Guth | Minimax problems related to cup powers and Steenrod squares[END_REF], [START_REF] Balacheff | Diastolic and isoperimetric inequalities on surfaces[END_REF], [L16], [S17], [START_REF] Glynn-Adey | Liokumovich: Width, Ricci curvature, and minimal hypersurfaces[END_REF], [START_REF] Liokumovich | Sweeping out 3-manifold of positive Ricci curvature by short 1-cycles via estimates of min-max surfaces[END_REF], [LMN] for a selection of references focusing on volume comparaison inequalities, and have led to several applications including major breakthroughs in Riemannian geometry, cf. [START_REF] Marques | Min-max theory and the Willmore conjecture[END_REF], [START_REF] Marques | Existence of infinitely many minimal hypersurfaces in positive Ricci curvature[END_REF]. Keeping in mind the analogy with systolic geometry, a natural question to ask is whether the different widths of a closed Riemannian manifold provide universal lower bounds on its volume (see [START_REF] Guth | Metaphors in systolic geometry[END_REF] for a general discussion). Occurrences of such lower bounds are referred to as width inequalities or sweepout estimates.

A prototype of a sweepout estimate is given by the following curvaturefree geometric inequality, cf. [START_REF] Balacheff | Diastolic and isoperimetric inequalities on surfaces[END_REF]. where f : M → R runs over all continuous (Morse) function and C is an explicit universal constant.

In this inequality, the fibers f -1 (t) define a homotopically nontrivial onecycle sweepout of the surface and the min-max length of the left-hand side of (1.1) represents the 1-width of M . Note that the rough dependence on the genus in this inequality, i.e., √ g + 1, is optimal and differs from the optimal one, equal to log(g) √ g , appearing in systolic inequalities, cf. [START_REF] Gromov | Filling Riemannian manifolds[END_REF], [START_REF] Gromov | Systoles and intersystolic inequalities[END_REF].

If we insist on the fibers to be connected, we have to consider continuous map f : M → Γ to graphs. Of course, the inequality (1.1) still holds, but it might be possible to improve the multiplicative constant. For instance, L. Guth asked in his ICM article [START_REF] Guth | Metaphors in systolic geometry[END_REF] if every closed Riemannnian surface M satisfies inf

f sup t∈Γ length f -1 (t) ≤ C area(M ) (1.2)
where f : M → Γ runs over all continuous function to some graph Γ and C is a universal constant. This is related to an old question of P. Buser about the sharp value of the Bers constant for pants decomposition of hyperbolic surfaces.

In higher dimension, one-cycle sweepout estimates have been obtained for closed 3-manifolds with positive Ricci curvature, cf. [START_REF] Liokumovich | Sweeping out 3-manifold of positive Ricci curvature by short 1-cycles via estimates of min-max surfaces[END_REF]. But the question remains open without curvature assumption (see [START_REF] Guth | Metaphors in systolic geometry[END_REF] for specific questions about one-cycle sweepout estimates on 3-manifolds). Similar "hypersurface" sweepout estimates have also been established for closed manifolds with nonnegative Ricci curvature, cf. [S17], [START_REF] Glynn-Adey | Liokumovich: Width, Ricci curvature, and minimal hypersurfaces[END_REF]. Contrarily to the surface case, "hypersurface" sweepout estimates do not exist without restriction on the Riemannian metrics, even on n-spheres with n ≥ 3, cf. [PS].

In this article, we present new curvature-free one-cycle sweepout estimates both on surfaces and in higher dimensions. More precisely, we derive upper bounds on the length of one-parameter families of one-cycles sweeping out essential surfaces in closed manifolds. A motivating example is given by the complex projective space CP n , endowed with an arbitrary Riemannian metric, along with its essential sphere CP 1 . By analogy with Theorem 1.1, we can ask whether there exists a homotopically substantial one-cycle sweepout of CP n (more precisely, a one-parameter family of one-cycles of CP n sweeping out CP 1 ) whose one-cycle length is at most ∼ vol(CP n ) 1 2n . Before stating our main results, we need to be more precise and define the k-width of a closed n-manifold M as there are many notions of width depending on the kind of sweepouts we look at. A first natural choice would be to consider the k-dimensional fibers of the continuous maps from M to the (n -k)-dimensional Euclidean space R n-k or to an (n -k)-dimensional simplicial complex (already here, the choice of the target space matters). However, this choice might be too rigid and presents a couple of drawbacks in some situations. Indeed, the sweepouts are made of pairwise disjoint cycles, which might appear too restrictive for some applications. Moreover, the family of k-cycles thus-obtained sweep out the whole manifold M with an (n-k)-dimensional parameter space. This prevents us from working with one-parameter families of one-cycles sweeping out the essential sphere CP 1 in CP n for instance. As a second choice, one could consider maps P → Z k (M ) from a p-dimensional simplicial complex P to Almgren's k-cycle space on M , cf. [A62]. But this raises continuity issues as we would like to include in our definition sweepouts of the classical "three-legged starfish" made of single loops and parameterized by the tripod tree T , see Figure 5 in the introduction of [P81]. Indeed, such a map T → Z 1 (S 2 ) is not continuous for any reasonable topology on the one-cycle space, including the flat norm topology.

Actually, the notion of width we will use -at least for surfaces (we will relax it a bit in higher dimension) -has been introduced by M. Gromov, see [START_REF] Gromov | Morse spectra, homology measures, spaces of cycles and parametric packing problems[END_REF]§6].

Definition 1.2. Let M be a closed surface. A one-cycle sweepout of M is a family of one-cycles ϕ[h -1 (t)] in M , with t ∈ Γ, where h : Σ → Γ is a continuous map from a closed surface Σ to a finite graph Γ and ϕ : Σ → M is a continuous map. Such a one-cycle sweepout is homologically substantial if

ϕ * ([Σ]) = 0 ∈ H 2 (M ; k).
Here, the homology coefficients are in k = Z, if M is orientable, and in k = Z 2 , otherwise.

In this definition, we will further assume that the vertices of Γ are of degree one or three, and that the preimages h -1 (t) are

• simple closed curves if t is not a vertex;

• point curves if t is a degree one vertex;

• figure-eight curves if t is a degree three vertex. Define the width of a closed Riemannian surface M as

W(M ) = inf ϕ, h sup t∈Γ length ϕ[h -1 (t)]
where the infimum is taken over all maps ϕ, h defining a homologically substantial one-cycle sweepout of M .

With this definition, we can prove the following curvature-free geometric inequalities.

Theorem 1.3. Every closed Riemannian surface M of genus g satisfies

W(M ) ≤ 144 √ 6 area(M ) (1.3) W(M ) ≤ 4 diam(M ). (1.4)
Observe that the first inequality (1.3) is similar to the inequality (1.1), except for the dependence on the genus. Note also that the second inequality (1.4) has no counterpart if one replaces h : Σ → Γ with a continuous function h : Σ → R in Definition 1.2, see [L14] for counterexamples.

Actually, we prove further width inequalities on surfaces, similar to (1.3) and (1.4). In particular, we establish sweepout estimates for compact Riemannian surfaces with boundary, cf. Section 4. We also bound the topological complexity of the homologically substantial one-cycle sweepouts required to have a width-diameter inequality, cf. Theorem 5.9.

The first inequality (1.3) is closely related to Buser-Guth's question, see (1.2). The difference is two-fold: first, the cycles in the one-cycle sweepouts we consider may intersect with each other, but more importantly, these cycles arise from a slicing of a surface Σ mapped to M with no control on the genus of Σ, and so on the "complexity" of the sweepout (at least for the area estimate (1.3)). We do not know whether this construction can be adapted to obtain one-cycle sweepouts satisfying an area estimate similar to (1.3) from a surface Σ with the same genus as M , which would solve Buser's problem.

In higher dimension, homotopically substantial one-cycle sweepouts of length at most ∼ vol(M ) 1 n do not exist in general. This can already be observed on the manifold S 2 × S 3 endowed with the product metric of the standard unit sphere S 2 with a sphere S 3 of small volume. Still, under some topological conditions on the manifold, similar upper bounds to (1.3) and (1.4) hold true if one replaces homologically substantial one-cycle sweepouts with homotopically substantial ones in the definition of the width. (We refer to Definition 2.1 for an extended definition of the width.) More specifically, we can state the following result, where the Φ-width W Φ (M ) is defined in Definition 2.1. Note that this is the first curvature-free geometric inequality involving sweepout volume in higher dimension.

Theorem 1.4. Let M be a closed n-manifold and Φ : M → K be a continuous map to a CW-complex K with π i (K) = 0 for every i ≥ 3. Suppose that Φ * [M ] = 0 ∈ H n (K; k). Then every Riemannian metric on M satisfies

W Φ (M ) ≤ c n vol(M ) 1 n W Φ (M ) ≤ c ′
n diam(M ) where c n and c ′ n are explicit constants depending only on n. Theorem 1.4 applies for instance to the torus T n (more generally, to closed manifolds admitting a nonpositively curved metric such as closed hyperbolic manifolds) and to the complex projective space CP n (more generally, to closed symplectic manifolds). A manifold satisfying the topological condition of Theorem 1.4 is sometimes called a two-essential manifold, at least when the manifold is simply connected.

There is no universal upper bound on the 2-systole -defined as the minimal area of a homologically nontrivial surface -of CP n , endowed with an arbitrary metric, in terms of the volume of the manifold, cf. [START_REF] Katz | Systolic freedom of loop space[END_REF]. On the other hand, a (sharp) systolic inequality relating the stable 2-systole of CP n to its volume can be found in [Gr99, Theorem 4.36]. However, even though the stable 2-systole is related to the area of some minimal surfaces, it is not clear how to combine this result with Theorem 1.1 to derive a sweepout estimate as in Theorem 1.4.

The proofs of Theorem 1.3 and Theorem 1.4 follow the same strategy and will therefore be carried out simultaneously in the first part of the paper. They both rely on the notion of filling radius, a Riemannian invariant introduced by M. Gromov, cf. Definition 3.1, and one of the main tool to establish curvature-free geometric inequalities. More specifically, we will show that the filling radius of a two-essential Riemannian manifold is bounded from below in terms of its width, cf. Theorem 3.3. The main results will immediately follow from general filling estimates. In the second part of the paper, we will focus on the surface case: proving sweepout estimates for compact Riemannian surfaces with nonempty boundary, cf. Section 4, and bounding the topological complexity of the one-cycle sweepouts in the width-diameter inequality, cf. Section 5.

Homotopically substantial one-cycle sweepouts

In this section, we introduce the notion of homotopically substantial onecycle sweepouts (relaxing the definition of homologically substantial onecycle sweepouts) and define the width in higher dimension. We also presents topological conditions ensuring the existence of homotopically substantial one-cycle sweepouts and generalize classical Morse-theoretical comparaison results to our setting. Definition 2.1. Let M be a closed manifold and Φ : M → K be a continuous map to a CW-complex

K. A one-cycle sweepout of M is a family of one-cycles ϕ[h -1 (t)]
in M , with t ∈ Γ, where h : Σ → Γ is a continuous map from a compact "surface" (more precisely, a compact two-dimensional complex) Σ to a finite graph Γ and ϕ : Σ → M is a continuous map. Such a one-cycle sweepout is homotopically Φ-substantial if the composite map

Φ • ϕ : Σ → K is not homotopic to any map Σ h -→ Γ → K which factors through h : Σ → Γ.
In this definition, we will further assume that the vertices of Γ are of degree one or three, and that the preimages h -1 (t) are

• simple closed curves if t is not a vertex; • point curves if t is a degree one vertex;

• simple closed curves or figure-eight curves if t is a degree three vertex.

As previously, define the Φ-width of a closed Riemannian manifold M as

W Φ (M ) = inf ϕ, h sup t∈Γ length ϕ[h -1 (t)]
where the infimum is taken over all maps ϕ, h defining a homotopically Φsubstantial one-cycle sweepout of M .

If homotopically Φ-substantial one-cycle sweepouts do not exist, we let W Φ (M ) = 0, but this case is not interesting for us.

Remark 2.2. Suppose that K is the Eilenberg-MacLane space K(Z, 2) = CP ∞ . Then a one-cycle sweepout of M given by ϕ : Σ → M and h : Σ → Γ is homotopically Φ-substantial if and only if the homotopy class of Φ • ϕ is nontrivial in [Σ, K(Z; 2)], since K is simply connected. Following the fundamental relationship between cohomology and Eilenberg-MacLane spaces, cf. [Ha02, Theorem 4.57], this is equivalent to

(Φ • ϕ) * (α) = 0
where α ∈ H 2 (K; Z) is the fundamental cohomology class of K = K(Z; 2) in H 2 (K; Z) = Hom(H 2 (K; Z); Z) given by the inverse of the Hurewicz isomorphism π 2 (K) = Z → H 2 (K; Z).

Remark 2.3. Working with homotopically substantial one-cycle sweepouts instead of merely homologically substantial ones allows us to consider more general manifolds. For instance, homologically substantial one-cycle sweepouts do not exist on hyperbolic integer homology 3-spheres since their second homology group is trivial. However, homotopically substantial onecycle sweepouts exist on these manifolds and, more generally, on closed n-manifolds admitting a nonpositively curved metric since such manifolds have nonfree fundamental groups (indeed, their fundamental groups have one end, while nontrivial free groups have two or infinitely many ends depending whether they are isomorphic to the infinite cyclic group or not), cf. Proposition 2.4. In particular, the Φ-width of every closed Riemannian n-manifold admitting a nonpositively curved metric is nontrivial when Φ is the identity map, cf. Proposition 2.5, and Theorem 1.4 applies to these manifolds.

The following immediate proposition gives a couple of criteria ensuring the existence of homotopically substantial one-cycle sweepouts.

Proposition 2.4. Let M be a closed n-manifold and Φ : M → M be the identity map.

(1) If π 1 (M ) is trivial, then M admits a homotopically Φ-substantial one-cycle sweepout if and only if H 2 (M ; Z) = π 2 (M ) is nontrivial. (2) If π 1 (M ) is nonfree, then M admits a homotopically Φ-substantial one-cycle sweepout.

Proof. For the point (1). If H 2 (M ; Z) (or π 2 (M )) is nontrivial, take a closed surface Σ representing a nontrivial homology (or homotopy) class along with a Morse function f : Σ → R on it. Then the induced map h : Σ → Γ to the Reeb graph Γ of f defines a homotopically Φ-substantial one-cycle sweepout. Conversely, let ϕ : Σ → M be a continuous map defined on a compact "surface" Σ. Since M is simply connected, there exists a deformation of ϕ : Σ → M taking the 1-skeleton of Σ to a single point of M . This deformation factors as Σ → Σ/Σ (1) → M , where the first map is the quotient map obtained by collapsing the 1-skeleton Σ (1) of Σ to a point. Now, since the quotient Σ/Σ (1) is a bouquet of two-spheres and π 2 (M ) is trivial, the second map Σ/Σ (1) → M is homotopically trivial. Therefore, no map ϕ : Σ → M gives rise to a homotopically Φ-substantial one-cycle sweepout of M . For the point (2). Consider the 2-skeleton Σ = M (2) of M for a given triangulation of the manifold. The inclusion map Σ ֒→ M , which induces a π 1 -isomorphism, is not homotopic to any map Σ → Γ → M factoring through a graph Γ. Otherwise, the isomorphism π 1 (Σ) → π 1 (M ) induced by the inclusion map would split as π 1 (Σ) → π 1 (Γ) → π 1 (M ) through π 1 (Γ). Thus, π 1 (M ) ≃ π 1 (Σ) would be a subgroup of the free group π 1 (Γ) and so would be a free group.

The min-max process over homotopically Φ-substantial one-cycle sweepouts shares similar properties with the classical min-max process over the loop space as illustrated by the following straightforward proposition.

Proposition 2.5. Let M be a closed Riemannian n-manifold and Φ : M → K be a continuous map to a CW-complex K. Suppose that homotopically Φ-substantial one-cycle sweepouts exist on M . Then

W Φ (M ) > 0.
Moreover, when M is a closed Riemannian surface, we have W(M ) ≥ scg(M ), where scg(M ) is the length of the shortest closed geodesic on M .

Proof. Let ϕ : Σ → M and h : Σ → Γ be the maps involved in the definition of a one-cycle sweepout of M , cf. Definition 2.1. By definition, the map h is a trivial circle bundle over the interiors of the edges of Γ. Furthermore, the fibers over the vertices of Γ are either point curves or figure-eight curves. It follows that Γ admits a lift Γ ′ on Σ under h. Thus, every fiber h -1 (t) has a distinguished basepoint x t given by its intersection with Γ ′ . If the length of every one-cycle ϕ[h -1 (t)] is less than the length sgl(M ) of the shortest pointed geodesic loop of M (for instance, less than twice the injectivity radius), then applying Birkhoff's curve shortening flow to this one-parameter family of one-cycles with basepoints ϕ(x t ) gives rise to a continuous retraction of the one-cycles ϕ[h -1 (t)] to x t . Therefore, the map ϕ : Σ → M is homotopic to the composite map

Σ h -→ Γ ≃ Γ ′ ϕ -→ M.
Consequently, the one-cycle sweepout ϕ[h -1 (t)] is not homotopically Φsubstantial for any map Φ : M → K. Hence, W Φ (M ) ≥ sgl(M ) > 0.

Suppose that M is a closed Riemannian surface. Let us argue by contradiction. As mentioned above, the map h : Σ → Γ is a trivial circle bundle over the interiors of the edges of Γ. Thus, the surface Σ is made of cylinders C foliated by the fibers of h over the non-vertex points of Γ. In this construction, the boundary components of the cylinders C collapse to point curves over the degree one vertices of Γ, while they agree either with the simple loops forming the figure-eight curves h -1 (τ ) or with the whole figureeight curves h -1 (τ ) (seen as limits of simple closed curves) over the degree three vertices τ of Γ. Now, we want to deform the images under ϕ of the boundary components of these cylinders to point curves in a way coherent with the gluing of the cylinders of Σ. To do so, we apply the disk flow [START_REF] Hass | Shortening curves on surfaces[END_REF] (which does not require a parametrization of the curves and does not increase their number of self-intersection points) to the images of the figure-eight curves h -1 (τ ) corresponding to the degree three vertices τ of Γ. These curves converge to point curves in finite time since they are shorter than any closed geodesic on M . The disk flow also preserves their decomposition into double loops as images of figure-eight curves. (Actually, one of the two loops forming the image of such figure-eight curve might shrunk to a point before the end of the flow convergence, but we can still consider this point as a loop and follow it along the flow.) Thus, the map ϕ : Σ → M is homotopic to a map Σ → Σ ′ → M , where the first map Σ → Σ ′ is the quotient map obtained by collapsing each fiber of h over a vertex point of Γ to a point.

By construction, the quotient space Σ ′ is formed of spheres C ′ attached to each other, where the spheres C ′ are obtained by collapsing the boundary components of the cylinders C of Σ to points (the two poles of the spheres). Observe that the spheres C ′ are foliated by latitude circles whose images under Σ ′ → M are given by the images under ϕ of the fibers of h foliating the cylinders C and the homotopies contracting the images of the boundary components of C to points. By construction, the length of the images of these latitude circles is at most W(M ). Now, if W(M ) < scg(M ), we deduce from the standard Birkhoff minmax principle over the loop space that the map C ′ → M is contractible. Putting together these maps, we deduce that the map Σ ′ → M , and so Σ → Σ ′ → M , induces a trivial homomorphism between the second homology groups. Therefore, the one-cycle sweepout ϕ[h -1 (t)] is not homologically substantial. Hence, W(M ) ≥ scg(M ).

Remark 2.6. In higher dimension, the Φ-width of M might be smaller than the length of the shortest closed geodesic on M . Indeed, the critical onecycles giving the Φ-width might include unions of two geodesic loops based at the same point with starting and ending unit tangent vectors which do not lie in the same tangent two-plane.

Curvature-free one-cycle sweepout estimates

In this section, we introduce the notion of filling radius and present a couple of filling inequalities. Then we prove a new filling inequality involving the width of two-essential Riemannian manifolds, which implies the sweepout estimates of Theorem 1.3 and Theorem 1.4.

Let us recall the notion of filling radius introduced by M. Gromov in [START_REF] Gromov | Filling Riemannian manifolds[END_REF] to established systolic inequalities on essential manifolds. Definition 3.1. Let (M, g) be a closed Riemannian n-manifold. Denote by d g the distance on M induced by the Riemannian metric g. The map

i : (M, d g ) ֒→ (L ∞ (M ), || • ||) defined by i(x)(•) = d g (x,
•) is an embedding from the metric space (M, d g ) into the Banach space L ∞ (M ) of bounded functions on M endowed with the sup-norm || • ||. This natural embedding, also called the Kuratowski embedding, is an isometry between metric spaces. We will consider M isometrically embedded into L ∞ (M ).

The filling radius of (M, g), denoted by FillRad(M, g), is the infimum of the positive reals ρ such that

(i ρ ) * ([M ]) = 0 ∈ H n (U ρ (M ); k) where i ρ : M ֒→ U ρ (M ) is the inclusion into the ρ-tubular neighborhood of M in L ∞ (M ), and [M ] ∈ H n (M ; k) is the fundamental class of M .
Here, the homology coefficients are in k = Z, if M is orientable, and in k = Z 2 , otherwise.

The filling radius satisfies the following fundamental bounds respectively obtained by M. Gromov [START_REF] Gromov | Filling Riemannian manifolds[END_REF] and M. Katz [K83].

Theorem 3.2 ([Gr83], [K83]). Let M be a closed Riemannian n-manifold. Then FillRad(M ) ≤ c n vol(M ) 1 n FillRad(M ) ≤ 1 3 diam(M )
where c n is an explicit constant depending only on n.

When n = 2, one can take c 2 = 12 √ 6.

Combining Theorem 3.2 with the filling estimate given by Theorem 3.3 below immediately lead to Theorem 1.3 and Theorem 1.4.

Theorem 3.3. Let M be a closed n-manifold and Φ : M → K be a continuous map to a CW-complex K with π i (K) = 0 for every

i ≥ 3. Suppose that Φ * [M ] = 0 ∈ H n (K; k). Then every Riemannian metric on M satisfies FillRad(M ) ≥ 1 12 W Φ (M ).
When M is a closed surface, the same inequality also holds with W(M ) instead of W Φ (M ).

We can now proceed to the proof of Theorem 3.3 indicating the changes to make along the way to cover the surface case.

I -Set-up. By definition of the filling radius, the fundamental class

[M ] of M vanishes in the ρ-neighborhood U ρ (M ) of M in L ∞ (M ), where ρ > FillRad(M ). More precisely, (i ρ ) * ([M ]) = 0 ∈ H n (U ρ (M ); k)
Therefore, there exists a continuous map σ : P → U ρ (M ) defined on an (n + 1)-pseudomanifold P with boundary such that the restriction σ :

∂P → M represents [M ] in H n (M ; k), that is, σ * [∂P ] = [M ] ∈ H n (M ; k). (3.1)
Recall that an (n+1)-pseudomanifold with boundary is an (n+1)-dimensional simplicial complex P such that • every simplex of P is a face of some (n + 1)-simplex of P ;

• every n-simplex of P is the face of at most two (n + 1)-simplices of P . The boundary ∂P of an (n + 1)-pseudomanifold P with boundary is the simplicial n-subcomplex of P formed of the n-simplices of P which are the faces of exactly one (n + 1)-simplex of P . Suppose that ρ < 1 12 W Φ (M ). The usual argument to obtain a contradiction and derive a lower bound on the filling radius of M consists in constructing a continuous map P → K which agrees with Φ • σ on ∂P , contradicting the assumption Φ * [M ] = 0. We will show how to carry out this argument in the higher dimensional case. However, this might not be possible in the surface case. In this special setting, we will construct a continuous map F : Q → M from a different 3-pseudomanifold Q with the same boundary as P which agrees with σ on ∂Q = ∂P . Combined with (3.1), this will yield the relation

[M ] = σ * [∂P ] = F * [∂Q] = 0 leading to a contradiction.
II -Extension to the 1-skeleton. Denote by P k the k-skeleton of P . Subdividing P if necessary, we can assume that the diameter of the images by σ of the simplices of P is less than ε > 0, with ε < min{W Φ (M ) -2ρ, 1 10 inj(M )}. We first define a map

f : P 0 ∪ ∂P → M
with f |∂P = σ by sending each vertex p i ∈ P 0 to a nearest point from σ(p i ) in M , as we wish. Since the inclusion i : M ֒→ U ρ (M ) is distance-preserving, every pair p i , p j of adjacent vertices of P satisfies

d M (f (p i ), f (p j )) ≤ d L ∞ (f (p i ), σ(p j )) + d L ∞ (σ(p i ), σ(p j )) + d L ∞ (σ(p j ), f (p j )) < δ with δ = 2ρ+ε < 1 6 W Φ (M ).
We extend the map f to P 1 by taking the edges of P \ ∂P to minimizing segments joining the images of their endpoints, as we wish. By construction, the boundary of every 2-simplex of P is sent by f to a loop of length less than 3δ. III -Local extension to part of the 2-skeleton. Let us examine the obstruction to extend f : P 1 ∪ ∂P → M to the 2-skeleton of P . Given a 2simplex ∆ of P , we apply the Birkhoff curve shortening flow, to the (simple) closed curve f (∂∆ 2 ). Without loss of generality, we can always assume that the metric is generic, and that the Birkhoff curve shortening flow converges either to a point curve or to a (nontrivial) closed geodesic. Actually, we could use any convergent curve shortening flow (leaving simple loops simple in the surface case such as the disk flow, cf. [START_REF] Hass | Shortening curves on surfaces[END_REF]). Two cases may occur:

(F 1 ) If the flow converges to a point curve, then the map f extends to ∆ 2 . (F 2 ) If the flow converges to a (nontrivial) closed geodesic, then the map f extends to the punctured face ∆ 2 ǫ obtained by removing a small ǫ-disk from ∆ 2 around its center.

The punctured face ∆ 2 ǫ is a topological annulus with outer boundary component the boundary of ∆ 2 and inner boundary component the boundary of the small ǫ-disk removed from ∆ 2 . By construction, the face ∆ 2 -in the case (F 1 ) -or the annulus ∆ 2 ǫ -in the case (F 1 ) -is foliated by concentric closed curves whose images by f correspond to the homotopy given by the curve shortening flow. Note that the images of these concentric closed curves are simple in the surface case since, in this case, simple loops remain simple through the Birkhoff curve shortening flow (except when reduced to a point). Anyway, in any case, the images of these concentric closed curves are of length at most 3δ.

The union of P 1 with the faces ∆ 2 corresponding to the case (F 1 ) and the punctured faces ∆ 2 ǫ corresponding to the case (F 2 ) forms a two-dimensional space denoted by P 2 0 . By construction, the map f : P 1 ∪ ∂P → M extends to f : P 2 0 ∪ ∂P → M. Consider the graph Γ lying in the dual 1-skeleton of P 1 in P 3 defined as follows:

• The vertices of Γ are formed of (i) the centers of the 3-simplices of P 3 ; (ii) the centers of the faces of P 3 corresponding to the case (F 2 ); (iii) the midpoints of the segments joining the centers of the 3simplices of P 3 to the centers of the faces of the same 3-simplex corresponding to the case (F 1 ). • The edges of Γ are the segments joining the centers of the 3-simplices of P 3 to the other vertices of Γ lying in the same 3-simplex. Thus defined, the graph Γ inherits a natural bipartite graph structure with the vertices corresponding to the centers of the 3-simplices of P 3 on one side, cf. (i), and the other vertices on the other side, cf. (ii)-(iii). Observe that the vertices of Γ given by (i) are of degree 4, the vertices of Γ given by (ii) are of degree at least 2 and the vertices of Γ given by (iii) are of degree 1. Actually, in the surface case, the vertices of Γ given by (ii) are of degree exactly 2 (and, therefore, can be considered as non-vertex points of Γ). Indeed, in this case, the faces of P = P 3 corresponding to the case (F 2 ) do not lie in ∂P and each of them is the face of exactly two 3-simplices of P by definition of a 3-pseudomanifold.

IV -Global extension to the whole 2-skeleton and the 3-skeleton. In the absence of obstructions, the map f : P 2 0 ∪ ∂P → M clearly extends to P 3 away from a small ǫ-tubular neighborhood U ǫ (Γ) of Γ in P 3 . This yields a map f : (P 3 \ U ǫ (Γ)) ∪ ∂P → M. However, the map f may not extend to the whole 3-skeleton P 3 . In particular, its restriction ϕ : Σ → M to the compact "surface" (more precisely, the compact 2-complex) Σ = ∂U ǫ (Γ) may not extend to U ǫ (Γ).

In the surface case, it follows from the discussion above that U ǫ (Γ) is a compact 3-manifold with boundary and that Σ = ∂U ǫ (Γ) is a genuine closed surface. In this case, we will show that the map ϕ : Σ → M , which does not necessarily extend to P = P 3 , extends to a different 3-complex with the same boundary. More precisely, we will show that the map F = ϕ : Σ → M induces a trivial homomorphism between the two-dimensional homology groups.

In the higher dimensional case, we consider the composite map

F = Φ • f : (P 3 \ U ǫ (Γ)) ∪ ∂P → K
and extend it to P 3 ∪ ∂P as follows.

For every 3-simplex ∆ 3 of P 3 , consider the radial projection π ∆ 3 : ∆ 3 \ { * } → P 2 which takes every point x distinct from the center * of ∆ 3 to the point of ∂∆ 3 lying in the ray [ * , x) arising from * and passing through x. The restriction of the radial projection π ∆ 3 to Σ gives rise to a homeomorphism

Σ ∩ ∆ 3 ∼ -→ ∂∆ 3 \ U ǫ (Γ). (3.2)
This homeomorphism allows us to decompose Σ ∩ ∆ 3 into four pieces corresponding to the preimages of the faces of ∂∆ 3 . Topologically, these pieces are either disks or annuli depending whether the matching faces correspond to the case (F 1 ) or (F 2 ). Now, we can define a map h : Σ → Γ by giving its restriction

h ∆ 3 : Σ ∩ ∆ 3 → Γ ∩ ∆ 3
to the intersection of Σ with each 3-simplex ∆ 3 of P 3 . Actually, identifying Σ∩∆ 3 with ∂∆ 3 \U ǫ (Γ) through the homeomorphism (3.2) given by π ∆ 3 , we define h ∆ 3 on each face ∆ 2 or punctured face ∆ 2 ǫ of ∂∆ 3 \U ǫ (Γ) corresponding to the case (F 1 ) or (F 2 ) as follows.

In this construction, the map h ∆ 3 maps ∆ 2 to the edge E of Γ ∩ ∆ 3 arising from the center of ∆ 3 and pointing to the center of ∆ 2 in such a way that

• it takes ∂∆ 2 to the vertex of Γ corresponding to the center of ∆ 3 ;

• the concentric closed curves foliating ∆ 2 previously described agree with the level curves of the restriction h ∆ 3 : ∆ 2 → E. In particular, the map h ∆ 3 sends the center of ∆ 2 to the endpoint of E opposite to the center of ∆ 3 , cf. (iii).

Similarly, the map h ∆ 3 maps ∆ 2 ǫ to the edge E of Γ ∩ ∆ 3 joining the center of ∆ 3 to the center of the face of ∆ 3 containing ∆ 2 ǫ in such a way that • it takes the outer boundary component of ∆ 2 ǫ to the vertex of Γ corresponding to the center of ∆ 3 ; • it takes the inner boundary component of ∆ 2 ǫ to the vertex of Γ corresponding to the face of ∆ 3 containing ∆ 2 ǫ ; • the concentric closed curves foliating ∆ 2 ǫ previously described agree with the level curves of the restriction h ∆ 3 : ∆ 2 ǫ → E. By construction, the preimages of the degree 1 vertices of Γ under h : Σ → Γ are points. The preimages of the (degree 4) vertices corresponding to the centers of the 3-simplices of P agree with the 1-skeleta of these 3-simplices under the homeomorphisms (3.2). Their images by ϕ : Σ → M are of length less than 6δ. Meanwhile, the preimages of all the other points of Γ are simple closed curves of Σ and their images by ϕ : Σ → M are of length less than 3δ. In any case, for every t ∈ Γ, we have

length ϕ[h -1 (t)] < 6δ.
Actually, we can do slightly better altering this construction (we only sketch some features of the new construction leaving the details to the reader). Inserting a new edge [v, w] at each degree 4 vertex u of Γ corresponding to the centers of the 3-simplices of P as in Figure 1 gives rise to a new graph Γ ′ .

• u • • v w Figure 1. Inserting an edge
Similarly, we define a new compact "surface" Σ ′ by inserting cylinders in Σ in such a way that the map h extends to a map h ′ : Σ ′ → Γ ′ where the circles foliating the added cylinders agree with the level curves over the new edges in Γ ′ . While h -1 (u) corresponds to the graph T given by the 1-skeleton of a tetrahedron, the level curves h ′-1 (v) and h ′-1 (w) correspond to the graph T with one edge removed, where the edges removed in h ′-1 (v) and h ′-1 (w) are in opposite position in T . Moreover, this construction can be performed so that the level curves over the edge [v, w] cover at most five of the six edges of T . Therefore, for every t ∈ Γ, we have

length ϕ ′ [h ′-1 (t)] < 5δ
where ϕ ′ : Σ ′ → Σ ϕ -→ M is the map obtained by collapsing the cylinders inserted in Σ and applying ϕ. Similarly, we can replace every degree k ≥ 4 vertex with k -2 trivalent vertices by inserting k -3 new edges at each of these vertices. Thus, the new graph so-obtained has only vertices of degree one or three. We can accordingly modify our sweepouts so that they are made of point curves, simple closed curves or figure-eight curves depending on the degree of the point t in the parameterizing graph. This can be performed without increasing the length of the image of the sweepout curves over 6δ. Further minor technical adjustments need to be made in the rest of the argument to be consistent, but we will skip them and work with the original sweepout ϕ[h -1 (t)]. Now, by our choice of δ, every curve in our sweepout is of length less than W Φ (M ). By definition of the Φ-width, it follows that the composite map

F = Φ • ϕ : Σ → K is homotopic to a map Σ h -→ Γ → K which factors through h. That is, the map F : Σ → K extends to U ǫ (Γ)
since the ǫ-tubular neighborhood U ǫ (Γ) of Γ in P 3 is homeomorphic to the quotient Σ × [0, 1]/ ∼, where (x, 1) ∼ (y, 1) if and only if h(x) = h(y). This yields a map F : P 3 ∪ ∂P → K. In the surface case, the argument is similar. By definition of the width, since every curve in our sweepout is of length less than W(M ), the map ϕ : Σ → M takes the fundamental class of the genuine closed surface Σ to zero. Therefore, this map extends to a 3-complex with boundary Σ. This yields a map F : Q → M defined on some 3-complex Q with the same boundary as P which agrees with σ on ∂Q = ∂P . Hence a contradiction in this case.

V -Extension to higher dimensional skeleta. Back to the higher dimension case, since π 3 (K) = 0, there is no obstruction to extend any map S 3 → K from the 3-sphere to the 4-ball. In particular, the restriction of F to the boundary ∂∆ 4 of every 4-simplex ∆ 4 of P not lying in ∂P extends to ∆ 4 . This yields a map

F : P 4 ∪ ∂P → K.
Applying this argument to higher-dimensional skeleta one at a time, we obtain the desired extension

F : P → K of Φ • σ : ∂P → K,
which finishes the proof of Theorem 3.3.

One-cycle sweepouts of compact surfaces with boundary

In this section, we establish width inequalities for compact Riemannian surfaces with nonempty boundary. We will first consider the simple case of the disk before moving to more general surfaces. Proof. Slightly perturbing the metric if necessary, we can assume that M has finitely many closed geodesics of length at most L M := max{2 length(∂M ), 16R}.

In the absence of such geodesic, the curve shortening flow applied to ∂M converges to a point and gives rise to a foliation of M . The curves of this foliation, of length at most length(∂M ), are the level curves of a continuous map h : M → [0, 1] satisfying the conclusion of Theorem 4.1. This concludes the proof of the theorem in this case.

Let us argue by induction on the number n M of closed geodesics of length at most L M . Applying the curve shortening flow to ∂M as previously, we can assume that M has a geodesic boundary. We will consider two cases.

Case I -Suppose that ∂M is not a length-minimizing closed geodesic. That is, there exist two antipodal points x 1 and x 2 on ∂M , separating ∂M into two arcs α 1 and α 2 of the same length, such that

d(x 1 , x 2 ) < 1 2 length(∂M ).
Let α be the length-minimizing arc of M joining x 1 to x 2 . Note that α is shorter than α 1 and α 2 . The loops α ∪ α 1 and α ∪ α 2 bound two convex domains of M and converge to two closed geodesics γ 1 and γ 2 (possibly reduced to point curves) in each of these domains under the curve shortening flow. Denote by P the region lying between ∂M and the two curves γ 1 and γ 2 . Since the curve shortening flow preserves the curve convexity, we obtain -after a slight perturbation -a foliation of P by simple closed curves, possibly point curves, and figure-eight curves, where the curves of this foliation are of length at most length(α ∪ α 1 ) + length(α ∪ α 2 ) < 2 length(∂M ).

The construction is rather obvious (first deforming ∂M along α back and forth) and will be omitted. This gives rise to a continuous map h P : P → T to the tripod tree T , sending the three boundary components ∂M , γ 1 and γ 2 of P to the three terminal vertices of T , where the fibers of h P are the curves of the foliation. In particular, length h -1 (t) ≤ 2 length(∂M ).

By construction, the disk D i bounded by γ i satisfies length

(∂D i ) ≤ length(∂M ) R i ≤ R where R i = max x∈D i d(x, ∂D i ). Moreover, we also have n D i < n M .
By induction, we obtain two maps h i : D i → Γ i to finite trees Γ i satisfying the conclusion of Theorem 4.1. Putting together h P : P → T and the maps h i : D i → Γ i , we define the desired map h : M → Γ, where Γ is the tree obtained by gluing Γ 1 and Γ 2 to the tripod tree T at the terminal vertices corresponding to γ 1 and γ 2 .

Case II -Suppose that ∂M is a length-minimizing closed geodesic. In this case, the isometric embedding i : ∂M ֒→ L ∞ (∂M ) given by the Kuratowski embedding, cf. Defintion 3.1, isometrically extends to M , cf. [Gr83, §1.1]. In particular, FillRad(∂M ) ≤ R.

Since length(∂M ) ≤ 6 FillRad(∂M ) from [Gr83, Lemma 1.2.B], we derive the upper bound length(∂M ) ≤ 6R.

Let x 0 ∈ M such that d(x 0 , ∂M ) = R. From [CE75, Lemma 8.15] (see also [CE75, Lemma 6.2]), whose proof relies on the first variation formula, we can show that there exist three geodesic arcs α 1 , α 2 and α 3 joining x 0 to ∂M of length R dividing M into three convex domains ∆ 1 , ∆ 2 and ∆ 3 . (Actually, two geodesic arcs might be enough, but in this case, one of the two convex domains will be empty.) Each boundary component ∂∆ i converges to a simple closed geodesic γ i (possibly reduced to a point curve) in ∆ i under the curve shortening flow. As previously, we obtain a foliation of the region Q bounded by ∂M and the three curves γ 1 , γ 2 and γ 3 by simple closed curves and figure-eight curves (deforming ∂M along the three arcs α i back and forth) of length at most length(∂M ) + 6R ≤ 8R. This gives rise to a continuous map h Q : Q → Γ Q to the union Γ Q of two tripod trees sending the four boundary components ∂M , γ 1 , γ 2 and γ 3 of Q to the four terminal vertices of Γ Q , where the fibers of h Q are the curves of the foliation. In particular, length h -1 (t) ≤ 8R.

By construction, the disk D

i bounded by γ i satisfies length(∂D i ) ≤ 8R R i ≤ R and n D i < n M .
By induction, we obtain three maps h i : D i → Γ i to finite trees Γ i , sending the boundary of D i to a terminal vertex of Γ i , such that the fibers of h i are simple closed curves, point curves or figure-eight curves of length at most 16R. Combining the map h Q : Q → Γ Q with the maps h i : D i → Γ i as previously, we obtain a map h : M → Γ satisfying the conclusion of Theorem 4.1, where Γ is the finite tree obtained by gluing together Γ 1 , Γ 2 and Γ 3 to Γ at the terminal vertices corresponding to γ 1 , γ 2 and γ 3 . Now, we consider the case of general surfaces with nonempty boundary and extend the notion of width to this setting. where C runs over the components of ∂M . Note that L(∂M ) does not represent the total length of ∂M , but the length of its longest boundary component.

Define the relative width of M as

W(M, ∂M ) = inf ϕ, h sup t∈Γ length ϕ[h -1 (t)] (4.1)
where the infimum is taken over • the (relative) degree ±1 maps ϕ : (Σ, ∂Σ) → (M, ∂M ) defined on a compact surface Σ with boundary; • the continuous maps h : Σ → Γ to a finite graph where every boundary component of Σ is sent to a terminal vertex of Γ and the preimage of every terminal vertex of Γ is either a point or a boundary component of Σ. As previously, the homology coefficients are in Z or Z 2 depending whether M is orientable or not. Note that W(M, ∂M ) ≥ L(∂M ).

Replacing Σ with another compact surface with boundary filling some of the boundary components of Σ, we can further assume that the images of the boundary components of Σ are noncontractible in M (but we will not make use of this feature).

Regarding the inequalities (1.3) and (1.4), two natural questions to ask are whether

W(M, ∂M ) ≤ C 1 area(M ) + C 2 L(∂M ) (4.2) and if W(M, ∂M ) ≤ C ′ 1 diam(M ) + C ′ 2 L(∂M ) (4.3) where C 1 , C 2 , C ′
1 and C ′ 2 are universal constants. In the following, we give a negative answer to the first inequality and a positive answer to the second. We also show that the first inequality holds true if one replaces L(∂M ) with the total length of ∂M .

More precisely, we first prove Proposition 4.3. There exists a compact Riemannian surface M with boundary such that

• the area of M and the length of each component of ∂M are arbitrarily small; • the relative width W(M, ∂M ) of M is arbitrarily large.

Proof. Consider a flat torus T of systole at least ℓ, where ℓ > 0 is large. Fix ε > 0 small. Remove sufficiently many disjoint disks D i of perimeter at most ε from T so that the area of the resulting surface M = T \ ∪ i D i is at most ε. Thus, area(M ) ≤ ε and L(∂M ) ≤ ε.

Let ϕ : (Σ, ∂Σ) → (M, ∂M ) and h : Σ → Γ be two maps involved in the definition of the relative width of M for which the min-max value (4.1) is attained up to ε. That is,

sup t∈Γ length ϕ[h -1 (t)] < W(M, ∂M ) + ε. (4.4)
Every component C of ∂Σ is sent to some circle ∂D i in T and can be contracted to a point inside D i through a length-nonincreasing homotopy of loops C t in D i . This gives rise to a continuous map φ : Σ → T from the closed surface Σ obtained by collapsing every boundary component of Σ to a point with φ([Σ]) = 0 ∈ H 2 (T ; Z). This also gives rise to a continuous map ĥ : Σ → Γ extending h, where Γ is a graph obtained from Γ by adding an interval to each terminal vertex of Γ corresponding to a component of ∂Σ, such that the image by φ of the fibers over these intervals are given by the homotopies C t . Thus, sup

t∈ Γ length φ[ ĥ-1 (t)] = sup t∈Γ length ϕ[h -1 (t)]. (4.5)
Observe that the family φ[ ĥ-1 (t)] defines a homologically substantial onecycle sweepout of T , cf. Definition 1.2. Combining the relation (4.5) with the bound (4.4) and Proposition 2.5, we immediately deduce that Proof. Applying the curve shortening flow, we can assume that the boundary components of M are closed geodesics. Let M be the closed surface obtained by isometrically attaching round hemispheres H i along the boundary components of M .

ℓ ≤ W(T ) ≤ W(M, ∂M ) + ε for every ε > 0. Hence, W(M, ∂M ) ≥ ℓ.
Since every arc of a round hemisphere with endpoint lying in its boundary can be deformed into an arc of the equator through a length-nonincreasing homotopy keeping its endpoints fixed, we derive that every length-minimizing arc of M joining two points of M entirely lies in M . As every point on a round hemisphere of equatorial length L is at distance at most L 4 from its boundary, we deduce that

diam( M ) ≤ diam(M ) + 1 2 L(∂M ). (4.6) Let us show that FillRad( M ) ≥ 1 8 W(M, ∂M ) - 1 4 L(∂M ). (4.7)
Consider an ε-fine geodesic triangulation of M for ε > 0 small enough, and extend it into a geodesic triangulation of M with extra vertices the poles x i of the hemispheres H i attached to M . Thus, all triangles of the triangulation of M are ε-small except for the triangles lying in the round hemispheres, which are of diameter less than 1 4 L(∂M ) + ε. Fix ρ > FillRad( M ). Consider M as embedded in L ∞ ( M ) and denote by U ρ ( M ) the ρ-neighborhood of M in L ∞ ( M ), cf. Definition 3.1. By definition of the filling radius, there exists a continuous map σ : P → U ρ ( M ) defined on a 3-pseudomanifold P with boundary such that the restriction σ |∂ P : ∂ P → M of σ to ∂ P is a simplicial homeomorphism. In particular,

σ * [∂ P ] = [ M ].
Subdividing the simplices of P (but not by barycentric subdivision in order to preserve the simplicial structure on ∂ P ), we can assume that the images by σ of the simplices of P are of diameter less than 1 4 L(∂M ) + ε. The vertices of P decompose into three parts, namely the isolated vertices, the peripheral vertices and the regular vertices, defined as follows:

• The isolated vertices of P are the vertices of ∂ P which are sent to the poles of the hemispheres of M by the simplicial homeomorphism σ |∂ P .

Without loss of generality, we can assume that every isolated vertex of the pseudomanifold P is adjacent to a single vertex of P \ ∂ P .

• The peripheral vertices of P are the vertices of P \ ∂ P adjacent to the isolated vertices of P . • The regular vertices of P are formed of all the other vertices of P . Let P be the 3-pseudomanifold with boundary formed of all the simplices of P with vertices the peripheral and regular vertices of P . There is a natural deformation retract of P onto P sending every isolated vertex p i of P to its adjacent peripheral vertex q i . Denote by D i the union of the 2-simplices of ∂P around the peripheral vertex q i . It is a cone with principal vertex q i over the preimage of ∂H i under σ |∂ P . Suppose that ρ < 1 8 W(M, ∂M ) -1 4 L(∂M ) -ε 4 . We define a continuous map f : P 1 ∪ ∂ P → M extending σ |∂ P as follows (compare with the proof of Theorem 3.3, Part II).

As the map f is given by σ |∂ P on ∂ P , it maps every isolated vertex p i of P to the pole x i of some hemisphere H i of M . We extend f to the peripheral vertex q i of P adjacent to p i by sending q i to some (generic) point in the connected component ∂H i of ∂M . The only requirement on this generic point of ∂H i is that it should not be antipodal to any vertex of the triangulation of M (for technical reasons). Thus, the image f (q i ) lies in ∂H i and

d L ∞ (f (q i ), σ(q i )) ≤ d L ∞ (f (q i ), σ(p i )) + d L ∞ (σ(p i ), σ(q i )) < 1 4 L(∂M ) + 1 4 L(∂M ) + ε (4.8) as σ(p i ) = x i and σ(q i ) ∈ ∂H i .
By definition, the map f also takes every regular vertex v of P to a nearest point from σ(v) in M ⊂ L ∞ ( M ) away from the hemispheres. The point σ(v) is at distance at most ρ from M , hence at distance at most ρ + 1 4 L(∂M ) from M since every point of an hemisphere H i is at distance at most 1 4 L(∂M ) from its boundary. Thus,

d L ∞ (f (v), σ(v)) < ρ + 1 4 L(∂M ). (4.9)
Note that if v is a regular vertex of ∂ P then f (v) = σ(v) as required. Now, we need to define the image of every edge [v 1 , v 2 ] of P under f . If both f (v 1 ) and f (v 2 ) lie in the same connected component ∂H i of ∂M , the map f sends [v 1 , v 2 ] to the shortest arc of ∂H i . Otherwise, the map f sends [v 1 , v 2 ] to a minimizing segment of M between f (v 1 ) and f (v 2 ). With this definition, the boundary of every 2-simplex of D i is sent to a contractible loop of ∂H i , except for one whose image by f agrees with the equatorial loop ∂H i of length at most L(∂M ). In general, arguing as in the proof of Theorem 3.3, Part II, we deduce from the bounds (4.8) and (4.9) that the image by f of every edge of P is a geodesic arc of M of length at most

ℓ := 2 ρ + 1 2 L(∂M ) + ε.
Thus, the map f sends the boundary of every 2-simplex of P to a simple loop of length at most 3 ℓ.

We now want to extend f : P 1 ∪ ∂ P → M to P . Observe that the edges of P between two non-isolated vertices have their images in M , while the edges of P joining an isolated vertex to a peripheral or regular vertex have their images in the hemispheres of M . This implies that the restriction of f to P 1 defines a map f : P 1 → M with values in M .

Arguing as in the proof of Theorem 3.3, Parts III and IV, we define an extension f : P \ U ǫ (Γ) → M of f : P 1 → M to P away from a small ǫ-tubular neighborhood U ǫ (Γ) of some finite graph Γ in the dual 1-skeleton of P 1 in P . The restriction of f to the compact surface with boundary Σ = ∂U ǫ (Γ) \ ∂P , defined as the closure of ∂U ǫ (Γ) \ ∂P , is denoted by

ϕ : (Σ, ∂Σ) → (M, ∂M ).
Observe that the boundary components of Σ correspond to the 2-simplices of the D i 's (one for each i) whose images are noncontractible in the ∂H i 's. By construction, the map ϕ gives rise to a homeomorphism between ∂Σ and ∂M . This implies that the relative degree of ϕ is ±1. Furthermore, the map ϕ comes with a map h : Σ → Γ taking every boundary component of Σ to a terminal vertex of Γ, such that the preimages of the terminal vertices of Γ are either points or boundary components of Σ. In addition, the images by ϕ of the fibers of h are of length at most 4ℓ. Thus,

length ϕ[h -1 (t)] < W(M, ∂M ).
This contradicts the definition of the relative width, cf. (4.1). Therefore, the filling radius estimate (4.7) holds true.

Combining the bounds (4.7) and (4.6) with the general estimate given by the second inequality of Theorem 3.2, we derive that

1 8 W(M, ∂M )- 1 4 L(∂M ) ≤ FillRad( M ) ≤ 1 3 diam( M ) ≤ 1 3 diam(M )+ 1 6 L(∂M ).
Hence,

W(M, ∂M ) ≤ 8 3 diam(M ) + 10 3 L(∂M ).
From Proposition 4.3, there does not exist any relative width inequality similar to (4.2). However, such an inequality holds true if one replaces L(∂M ) with the total length of ∂M .

Theorem 4.6. Let M be a compact Riemannian surface with boundary. Then

W(M, ∂M ) ≤ 96 √ 6 area(M ) + 96 3 π + 2 length(∂M ).
Proof. We consider the closed surface M obtained from M by gluing round hemispheres as in the proof of Theorem 4.5. The filling radius estimate (4.7) combined with Theorem 3.2 yields the bound

1 8 W(M, ∂M ) - 1 4 L(∂M ) ≤ FillRad( M ) ≤ 12 √ 6 area( M ). By construction, area( M ) ≤ area(M ) + 1 2π length(∂M ) 2 .
Hence, from the classical relation √ a + b ≤ √ a+ √ b, we derive the following bound

1 8 W(M, ∂M ) - 1 4 L(∂M ) ≤ 12 √ 6 area(M ) + 12 3 π length(∂M ).
The desired inequality immediately follows.

Topological complexity of the one-cycle sweepouts

The surface Σ involved in the definition of the width of a closed Riemannian surface M , cf. Definition 1.2, is not necessarily homeomorphic to M . A natural question to ask is whether the width inequalities (1.3) and (1.4) of Theorem 1.3 hold when Σ is homeomorphic to M .

In this section, we show that a width-diameter inequality similar to (1.4) holds for homologically substantial one-cycle sweepouts obtained from a surface Σ of genus at most twice the genus of M , cf. Theorem 5.9. Note, however, that our approach only works for the width-diameter inequality (1.4). We do not know how to impose an a priori bound on the Euler characteristic of Σ for a width-area inequality as in (1.3).

Before stating and proving a width-diameter inequality for homologically substantial one-cycle sweepouts of bounded topological complexity, we establish an intermediate result of independent interest regarding quantitative triangulations of Riemannian surfaces. Definition 5.1. Every closed surface M can be described by gluing together finitely many triangles along their edges. Such collection of triangles defines a "triangulation" of M . This amounts to saying that M is a ∆-complex, cf. [Ha02, §2.1].

With this definition, the 2-torus admits a "triangulation" with only two triangles, whose vertices are identified into a single point, while a genuine triangulation, whose triangles are uniquely determined by their vertices, has at least 14 triangles.

The following result, which is a direct consequence of Proposition 5.5 and Proposition 5.6, shows that we can control the number and the size of the triangles in the triangulations of Riemannian surfaces.

Theorem 5.2. Let M be a closed Riemannian surface of genus g. Then there exists a "triangulation" of M with 4g -2 triangles of side length at most 3 diam(M ).

Remark 5.3. By taking a barycentric subdivision, we can deduce a similar result for genuine triangulations. Specifically, there exists a triangulation of M with 24g -12 triangles of side length at most 9 2 diam(M ). Remark 5.4. It would be rather surprising if this result was not already known. However, we were unable to find a reference in the literature.

The proof we present is more involved than first expected. The starting point is Gromov's classical result asserting that the fundamental group of M can be generated by the homotopy classes of simple loops of length at most 2 diam(M ), cf. [Gr99, Proposition 3.22]. Using this result, we can easily open up the surface into a polygon. But it is not clear how to obtain a triangulation of this polygon from the previous simple loops. Proposition 5.6 is then required at this point.

Another way to proceed would be to make use of the length-three relations in the presentation of the fundamental group of M by homotopy classes of loops of length at most 2 diam(M ), cf. [Gr99, Proposition 5.28], since these relations correspond to triangles in the surface. However, these triangles may overlap and it is not clear how to derive a "triangulation" from them. (1) The sides of D are of length at most 2 diam(M ).

(2) Every point of D is at distance at most diam(M ) from one of its vertices.

Proof. The fundamental group of M , and so its first integral homology group, is generated by the homotopy classes of the loops of length at most 2 diam(M ) based at x 0 , cf. [Gr99, Proposition 3.22]. This immediately implies that length(γ i ) ≤ 2 diam(M ). As the sides of D correspond to the geodesic arcs γ i , we immediately derive the point (1).

Observe that no minimizing arc with endpoint x 0 intersects any loop γ i of M away from its endpoints. Otherwise, there would be a minimizing arc α intersecting γ i at exactly two points x 0 and x, which can be taken as the endpoints of α. Denote by γ ± i the two arcs of γ i with the same endpoints as α. Since α is length-minimizing, the piecewise geodesic loops α ∪ γ ± i are of length at most length(γ i ). Moreover, as the arc α forms a nonzero nonflat angle with γ ± i at x, the loops α ∪ γ ± i can be deformed into shorter arcs with the same basepoint x 0 . By construction of γ i , this implies that both loops α ∪ γ ± i are homologous to some linear combinations of the loops γ 1 , • • • , γ i-1 . As the loop γ i itself is homologous to the sum of the loops α ∪ γ ± i , it follows that γ i is homologous to a linear combination of the loops γ 1 , • • • , γ i-1 . Hence a contradiction.

Let x be a point of M not lying in any loop γ i . From the previous observation, every minimizing arc c from x to the basepoint x 0 intersects the curves γ i only at its endpoint x 0 . Thus, the arc c lies in D. As the vertices of D correspond to the basepoint x 0 , we deduce that the distance in D from x to one of the vertices of D equals the length of c, which is at most diam(M ). Hence the point (2).

Proposition 5.6. Let D be a Riemannian polygon with n vertices. Suppose that (1) the edges of D are of length at most 2δ;

(2) every point of D is at distance at most δ from the set of vertices of D.

Then there exists a "triangulation" of D with n -2 triangles compatible with the polygonal structure of D whose triangle side length is at most 3δ.

Proof. We argue by induction on the number n of vertices of D. The result is obvious for n = 3. So we can assume n > 3. Denote by v 1 , • • • , v n the vertices of D. Let V i be the Voronoi cells centered at v i V i = {x ∈ D | |xv i | ≤ |xv j | for every j = i}. The cells V i are topological disks since they are simply connected. Note that every point of V i is at distance at most δ from the center v i of the cell, cf. Item (2) of Proposition 5.6.

By definition, a barrier of D is an arc of the boundary ∂V i of some Voronoi cell V i , intersecting ∂D only at its endpoints.

Case I -Suppose that every pair of Voronoi cells with nonempty intersection are centered at adjacent vertices.

The following lemma describes the boundary components of the Voronoi cells and how these cells fit together.

Lemma 5.7.

(1) The boundary of a Voronoi cell contains one or two barriers of D.

( The vertices of D across from α from the vertex v (that is, the vertices of D lying in the connected component of D \ α not containing v) are not adjacent to v. Indeed, they are separated from v by the vertices of D across from α ± from v. Thus, the Voronoi cells intersecting V along α are centered at vertices non-adjacent to v, which is impossible in Case I.

Suppose the point (2) does not hold. In this case, there exists a point lying at the intersection of three Voronoi cells. Under the assumption of Case I, the centers of these three Voronoi cells are pairwise adjacent, which is impossible if n > 3.

The point (3) is an immediate consequence of the previous point.

For ε > 0 small enough, the ε-neighborhoods V ε i of the Voronoi cells V i deformation retract to V i and form an open cover U of D. Consider the nerve Γ of U defined as a simplicial complex with vertices x 1 , • • • , x n (in bijection with the centers of the Voronoi cells) such that for every k ≥ 0, the vertices

x i 0 , • • • , x i k span a k-simplex if and only if the intersection ∩ k p=0 V ε ip is nonempty.
The following lemma describes the structure of the nerve Γ.

Lemma 5.8. For ε > 0 small enough, the nerve Γ of U is an interval.

Proof. Observe that the nerve Γ is a graph since three distinct Voronoi cells (and so their ε-neighborhoods, for ε small enough) have an empty intersection from Lemma 5.7.(3). By Lemma 5.7.

(2)-(3), every nonempty intersection of sets in the cover U is contractible. From the nerve theorem, cf. [Ha02, Corollary 4G.3], we deduce that the nerve Γ of U is homotopically equivalent to D. Therefore, the graph Γ is a tree. This tree does not have any vertex of degree three or more, otherwise a Voronoi cell would meet at least three other Voronoi cells and so would have at least three barriers lying in its boundary, which would contradict Lemma 5.7.(1). Thus, we conclude that the graph Γ is an interval.

We deduce from Lemma 5.8 and Lemma 5.7.(1)-(2) that the barriers of D form a sequence of nonselfintersecting arcs α The vertices v 2 , • • • , v n-1 lie in the same arc of ∂D with endpoints v 1 and v n . Otherwise, there would be two Voronoi cells V i and V i+1 meeting along α i with 2 ≤ i ≤ n-2 whose centers, separated by v 1 and v n , would not be adjacent, which is impossible in Case I. We deduce that every vertex v i is adjacent to v i-1 and v i+1 , where the indices are taken modulo n. These vertices decompose the circle ∂D into n arcs v i v i+1 of length at most 2δ with endpoints v i and v i+1 .

1 , • • • , α n-1 such that for every i = 1, • • • , n-1, the arc α i separates α 1 , • • • , α i-1 from α i+1 , • • • , α n-1 in D, cf.
α i v 2 v 1 α 1 α 2 α i-1 α i+1 v n v i v i+1 u i D Figure 3. Sequence of ordered Voronoi cells in D
Denote by u i the intersection point of α i with v 1 v n . Clearly, the point u i is at distance at most 2δ from v 1 . Since u i lies in V i , the distance between u i and v i is at most δ. Combining these estimates, we derive that the segment [v 1 v i ] (choose one) is of length at most 3δ. These segments, for i running between 3 and n -1, decompose the polygon D into n -2 triangles with vertices v 1 , v j , v j+1 , where j = 2, • • • , n -1. By construction, the length of the edges of these triangles is at most 3δ. This finishes the proof in the Case I.

Case II -There exist two non-adjacent vertices v i and v j whose Voronoi cells intersect at some point p.

d D ′ (x, v) = d D (x, v) ≤ δ (5.1)
by the assumption (2) of Proposition 5.6. Otherwise, the segment

[x, v] intersects [p, v i ] or [p, v j ]. Say it intersects [p, v i ] at some point q. We have |qv i | ≤ |qv|, otherwise |pv i | = |pq| + |qv i | > |pq| + |qv| > |pv|
which contradicts the definition of v. Thus,

|xv| = |xq| + |qv| ≥ |xq| + |qv i | ≥ |xv i |.
Actually, by smoothing out at q the piecewise geodesic arc formed of the two segments [x, q] and [q, v i ], we derive that x is closer from v i than from v, that is, |x, v| > |xv i |, which contradicts the definition of v. Therefore, the distance with respect to d D ′ between x and the set of vertices of D ′ is at most δ, cf. (5.1). The same holds for points of D ′′ with the vertices of D ′′ . That is, both D ′ and D ′′ satisfy the assumption (2) of Proposition 5.6. Now, since the vertices v i and v j are non-adjacent in D, the numbers of vertices of D ′ and D ′′ , denoted by n ′ and n ′′ , are less than n. By induction, the polygons D ′ and D ′′ can be "triangulated" into n ′ -2 and n ′′ -2 triangles of side length at most 3δ. Putting together these "triangulations", we obtain a "triangulation" of D compatible with its polygonal structure with n ′ + n ′′ -4 triangles of side length at most 3δ. Now, as each of the vertices v i and v j are split into two vertices in the new configuration, we derive that n ′ + n ′′ = n + 2 which shows that the "triangulation" of D previously obtained has n -2 triangles as desired.

As previously mentioned, the combination of Proposition 5.5 and Proposition 5.6 immediately yields Theorem 5.2.

We can now prove the main result of this section about a topologically refined width-diameter inequality.

Theorem 5.9. Let M be a closed Riemannian surface of genus g. Then there exists a homologically substantial one-cycle sweepout of M defined from some maps ϕ : Σ → M and h : Σ → Γ as in Definition 1.2, where Σ is a closed surface of genus at most 2g, such that length ϕ[h -1 (t)] ≤ 18 diam(M ) for every t ∈ Γ.

Proof. For Riemannian two-spheres, i.e., g = 0, the theorem immediately follows from Theorem 4.1. Thus, we can assume that g ≥ 1.

Even though the proof of Theorem 5.9 does not rely on filling radius estimates as it was the case with Theorem 3.3, it is based on similar obstruction arguments.

Suppose the conclusion of Theorem 5.9 does not hold. We want to derive a contradiction by constructing a map f : Q → M from a 3-pseudomanifold Q with ∂Q = M such that the restriction of f to ∂Q is the identity map.

Choose a "triangulation" of M as in Theorem 5.2. Consider an abstract cone P over M with the coned-off "triangulation" induced from M . We extend the identity map on M to the 1-skeleton of P as follows. Send the principal vertex of P to any point in M . Then send every edge of P arising from the principal vertex to a segment of M joining the images of its endpoints. The length of this segment is at most diam(M ). Thus, the images of the boundaries of the 2-simplices of P based at its principal vertex are loops of total length at most 5 diam(M ). Note that the perimeter of each triangle in the "triangulation" of M is at most 9 diam(M ). Now, contract these loops to point curves -case (F 1 ) -or closed geodesics -case (F 2 ) -by applying a curve shortening flow as in the proof of Theorem 3.3, Part III. This gives rise to a map f : P 2 0 ∪ ∂M → M extending the identity map, where P 2 0 is the 2-skeleton of P with a small disk removed around the centers of the faces corresponding to the case (F 2 ).

Consider the graph Γ lying in the dual 1-skeleton of P 1 in P defined as in the proof of Theorem 3.3, Part III. For every 3-simplex ∆ 3 of P 3 , replace the edge of Γ ∩ ∆ 3 pointing to the center of the face ∆ 2 of ∂∆ 3 lying in M = ∂P with an edge of half its length. This ensures that the resulting graph Γ ′ does not have any terminal vertex lying in M (a property that may fail for Γ as the boundaries of the triangles of the "triangulation" of M may not converge to point curves under the curve shortening flow). For every 3-simplex ∆ 3 of P 3 , we can also replace the edge of Γ ∩ ∆ 3 pointing to the center of the face ∆ 2 of ∂∆ 3 lying in M = ∂P with the tree Γ ∆ 2 given in Theorem 4.1 along with a map h ∆ 2 : ∆ 2 ⊂ M → Γ ∆ 2 . The resulting graph is denoted by Γ ′′ .

As in the proof of Theorem 3.3, Part III, the map f : P 2 0 ∪ ∂M → M extends to f : (P \ U ǫ (Γ ′ )) ∪ ∂P → M. For ǫ > 0 small enough, the ǫ-neighborhood U ǫ (Γ ′ ) of Γ ′ is a compact 3-manifold. Its boundary Σ = ∂U ǫ (Γ ′ ) is a closed surface obtained by assembling punctured spheres, one for each 3-simplex of P . These spheres have at most three holes. Thus, the genus of Σ is bounded by half the number of 3-simplices in P plus one. That is, genus(Σ) ≤ 2g. Now, we want to define a map h : Σ → Γ ′′ by giving its restriction

h ∆ 3 : Σ ∩ ∆ 3 → Γ ′′
to the intersection of Σ with each 3-simplex ∆ 3 of P 3 by identifying Σ ∩ ∆ 3 with ∂∆ 3 ∩ U ǫ (Γ ′ ) as in the proof of Theorem 3.3. Specifically, we define h ∆ 3 on each face ∆ 2 or punctured face ∆ 2 ǫ of ∂∆ 3 \ U ǫ (Γ ′ ) not lying in M as in the proof of Theorem 3.3, Part IV. For the face ∆ 2 of ∆ 3 lying in M , the restriction of h ∆ 3 to ∆ 2 agrees with the map h ∆ 2 : ∆ 2 → Γ ∆ 2 whose fibers are of length at most 18 diam(M ), cf. Theorem 4.1. Thus, the restriction ϕ : Σ → M of f to Σ comes along with a map h : Σ → Γ ′′ such that the images by ϕ of the fibers of h are of length less than 18 diam(M ). (See the proof of Theorem 3.3, Part IV, for further details.) That is, for every t ∈ Γ, we have length ϕ[h -1 (t)] < 18 diam(M ).

By assumption, this implies that the map ϕ : Σ → M takes the fundamental class [Σ] of Σ to zero. Therefore, the map ϕ extends to a 3pseudomanifold with boundary Σ. This yields a map F : Q → M defined on some 3-pseudomanifold Q with the same boundary as P , which agrees with the identity map on ∂Q = M . Hence the desired contradiction.

Remark 5.10. Theorem 4.5 provides an upper bound on the relative width of a genus g surface M in terms of tis diameter and the length of its longest boundary component. As in Theorem 5.9, we can impose on this estimate an a priori 2g bound on the genus of the surface Σ involved in the homologically substantial one-cycle sweepouts considered in the definition of the relative width, cf. Definition 4.2.

  Theorem 1.1 ([BS10]). Every closed Riemannian surface M of genus g satisfies inf f sup t∈R length f -1 (t) ≤ C g + 1 area(M ) (1.1)

Theorem 4. 1 .

 1 Let M be a Riemannian disk. Then there exists a continuous map h : M → Γ to a finite tree Γ, sending the boundary of M to a terminal vertex of Γ, such that the fibers of h are simple closed curves, point curves or figure-eight curves with length h -1 (t) ≤ max{2 length(∂M ), 16R} for every t ∈ Γ, where R = max x∈M d(x, ∂M ).

  Definition 4.2. Consider a compact Riemannian surface M with nonempty boundary. Let L(∂M ) = max C length(C)

Remark 4. 4 .

 4 Working directly on M without introducing the width W(T ) of the flat torus T is more technical. At least, we do not have a short argument to conclude in this case. Now, we show that the inequality (4.3) holds. More precisely, we have Theorem 4.5. Let M be a compact Riemannian surface with nonempty boundary. Then W(M, ∂M ) ≤ 8 3 diam(M ) + 10 3 L(∂M ).

  Let us construct by induction a collection of geodesic loops γ 1 , • • • , γ 2g based at a fixed point x 0 in M as follows. The loop γ 1 is the shortest homologically nontrivial loop of M based at x 0 . Define by induction the loop γ i+1 as the shortest loop of M based at x 0 homologically independent with γ 1 , • • • , γ i . Cutting open the surface M along the loops γ 1 , • • • , γ 2g gives rise to a 4g-gon D satisfying the following geometric features. Proposition 5.5.

  ) Two Voronoi cells meet along a barrier of D or have an empty intersection.(3) Three distinct Voronoi cells have an empty intersection.Proof. Suppose there exists a Voronoi cell V whose boundary ∂V contains at least three barriers of D. Let α ± be two barriers of D lying in ∂V adjacent to the center v of V and let α be another barrier of D lying in ∂V different from α ± , cf.

Figure 2 .Figure 2 .

 22 Figure 2. Voronoi cell with at least three barriers

Figure 3 .

 3 Up to permutation of the indices in the Voronoi cells, each cell V i is bounded by α i-1 and α i (where α 0 and α n are empty sets).

  By construction, the point p is closer to v i and v j than to any other vertex v k . In particular, |pv i | = |pv j | ≤ δ. Thus, the arc formed of the two minimizing segments [p, v i ] and [p, v j ] (choose any) divide D into two polygons D ′ and D ′′ , which satisfy the assumption (1) of Proposition 5.6. (In this construction, the point p is not a vertex of D ′ and D ′′ .) We will denote by d D the distance induced on D and by d D ′ and d D ′′ the length distance induced on D ′ and D ′′ . Note that d D ≤ d D ′ and d D ≤ d D ′′ . Let x be a point in the interior of D ′ . Denote by v the closest vertex of D from x. If the (minimizing) segment [x, v] lies in D ′ , then


Arthur Da Cunha

Damien Rivet
email: damien.rivet@inria.fr

Emanuele Natale
email: emanuele.natale@inria.fr

Aurora Rossi
email: aurora.rossi@inria.fr

Une implémentation GPU de la méthode de recherche approximative FlyHash

Keywords: Data mining, Hashing, winner-take-all, Distributed algorithms, Federated learning, GPU

ouverte pluridisciplinaire HAL, est destinée au dépôt

I. INTRODUCTION

Locality-sensitive hashing (LSH) is a technique in computer science introduced in [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF] for hashing data so that similar data has a high probability of having similar hashes, while different data is likely to have different hashes. It is widely used, especially for similarity search in large databases using faster heuristics than traditional approaches, such as nearest neighbor searching. Locality-sensitive hashing is particularly effective in real-time applications, where the speed of similarity search is essential to handle a massive and continuous flow of incoming data.

In nature, animals are constantly faced with similarity recognition tasks. This is notably the case for fruit flies, which, when encountering new odors, seek to identify similarities with odors they have previously encountered in order to assess the potential quality of the available food. Observation of their olfactory nervous system revealed that some of these neural circuits bore striking similarities to well-known LSH algorithms. Based on these observations, researchers propose a new type of algorithm called FlyHash [START_REF] Charles | A neural algorithm for a fundamental computing problem[END_REF].

FlyHash is based on the use of random projections followed by a binarization process, as is notably the case of one of the most well-known LSH heuristics SimHash [START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF]. However, unlike SimHash, the binarization used by FlyHash is not based on thresholding, but on a process called winner-takeall (WTA), which we describe in detail below.

The adoption of winner-take-all is motivated on the one hand by its theoretical properties [START_REF] Yagnik | The power of comparative reasoning[END_REF], and on the other hand for modelling the brain, in particular in the model of Assemblies of Neurons proposed by [PVM + 20] as well as in Spiking Neural Networks [START_REF] Chen | Mechanisms of winner-take-all and group selection in neuronal spiking networks[END_REF], artificial neural networks that are biologically closer to the real ones.

Besides, the classical winner-take-all implementation is known to represent a major bottleneck when one wants to process multiple data at once, or using large hashlengths (indeed the accuracy of such hashing algorithms improves significantly with the increase of the size of the generated hashes). In addition, the majority of data mining applications are now massively parallelized, via the use of distributed algorithms and the dominant hardware architecture is now the Graphics Processing Unit (GPU).

Our contribution with this work is to demonstrate that such WTA hashing schemes are compatible with the GPU architecture, allowing to implement them on a pipeline fully executable on GPU (Section III-B). Some works have focused on GPU implementation of winner-take-all including [MVSG + 09], but this direction remains relatively unexplored.

II. MOTIVATIONS AND APPLICATIONS

The FlyHash has been first studied in [START_REF] Charles | A neural algorithm for a fundamental computing problem[END_REF], based on empirical observations of the functioning of the olfactory system of a fruit fly. In this section, we first provide a brief summary of such biological observations. We refer the reader to [START_REF] Charles | A neural algorithm for a fundamental computing problem[END_REF] for a more detailed description. A formal description of the FlyHash algorithm inspired by these observations, together with our new implementation, is given in section III-A. Subsequently, we illustrate two important applications of FlyHash in Machine Learning, namely in an efficient and secure classification scheme in Federated Learning and as a potential subroutine to speed up the training of neural networks.

a) Neurobiological basis for Flyhash: The neurons which are activated by a given odor are determined by a three step procedure which is exemplified in Fig. 1. The first step consists in direct nervous connections from odorant receptor neurons (ORNs) in the fly's nose to projection neurons (PNs) in particular structures called glomeruli. There are circa 50 ORN types which are activated by different odors. Thus, each input odor can be thought as having a corresponding location in a 50-dimensional space determined by the 50 ORN. For each odor, the distribution of ORN firing rates across the 50 ORN types follows an exponential distribution with a mean that depends on the concentration of the odor [START_REF] Charles | A neural algorithm for a fundamental computing problem[END_REF]. For the PNs, such distribution of firing rates across the 50 PN types is also exponential, but for all odors and all odor concentrations the mean is approximately the same. The second step, which is where neurobiology offer us the main algorithmic insight, then involves an expansion in the number of neurons by a factor roughly 40: Fifty PNs project to 2000 so-called Kenyon cells (KCs), connected by a sparse binary random connection matrix, with each KC receiving and summing the firing rates from about six randomly selected PNs. The final third step is then performed by strong inhibitory connections from a single inhibitory neuron, called APL (anterior paired lateral neuron), which results in the aforementioned winner-take-all (WTA) operation. As a consequence, all but the highest-firing KCs are silenced, with the firing rates of the still-active KCs corresponding to the neurons activated by the input odor.

b) kNN-like classification in Federated Learning: Fly-Hash has recently found an important application as the basis of the FlyNN algorithm introduced in [SR21], who exploited the work of [START_REF] Dasgupta | A neural data structure for novelty detection[END_REF], taking advantage once again of biological observations, to design a classification algorithm (see Fig. 2).

FlyNN has been deployed in the context of federated learning in [START_REF] Ram | Federated nearest neighbor classification with a colony of fruit-flies[END_REF] and is currently the state of the art ap-Fig. 2. Illustration of the FlyNN scheme to perform approximate k-Nearest Neighbors classification using FlyHash [START_REF] Ram | Federated nearest neighbor classification with a colony of fruit-flies[END_REF]. Each party, here represented by a square, hashes the data point it owns for each class (here orange squares and blue triangles) and sums them into a single hash vector. The parties then combine their hash vectors to obtain a single hash vector for each class across the entire dataset, called filter. The class of a new data point is then determined by the filter that has the highest similarity to the new data point's hash vector.

proximation of the k-nearest neighbor classification algorithm in the federated setting. FlyNN has in particular the advantage of being usable in the context of one-shot federated learning, where the communication among clients is restricted to a single round, and to be readily combinable with differential privacy schemes [START_REF] Ram | Federated nearest neighbor classification with a colony of fruit-flies[END_REF].

c) Speeding up neural network training via Localitysensitive Hashing: An important application of LSH schemes has recently been provided in [START_REF] Daghaghi | Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and More[END_REF], in which such schemes are leveraged to speed up training and inference of large artificial neural network architectures on the CPU, based on the empirical observation that only a small fraction of neurons is activated per layer. A simplistic diagram of the SLIDE framework proposed in [START_REF] Daghaghi | Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and More[END_REF] is outlined in Fig. 3. The purpose of the present work is not only to increase the efficiency of the FlyHash algorithm as an alternative that can be leveraged in SLIDE, but also to make it possible to leverage the aforementioned framework to speed up training on the GPU.

III. DESCRIPTION OF THE ALGORITHMS

A. FlyHash

Formally, the FlyHash algorithm takes as input a vector in R d and returns its hash, which is a binary vector of length N (the hashlength parameter). The algorithm has two main parts, a projection and a winner-take-all binarization part.

The projection matrix is a random binary matrix M of size N ×d with a fixed number s (the projection parameter) of ones in each row. The first part of the algorithm is the multiplication between M and the input vector.

The winner-take-all binarization is then applied to the outcome of the previous step, which is in R N , and transformed into a {0, 1} N vector by setting the k highest entries to one and the others to zero. The parameter k is also called number of winners parameter.

Algorithm 1 contains the FlyHash pseudocode. The WTA function is explained in detail in the next section.

Algorithm 1 FlyHash

Input: X ∈ R d×b , M ∈ {S ∈ {0, 1} N ×d : each row of S contains s ones}, k ∈ [1, N ] Output: X ∈ {0, 1} N ×b A = M × X return WTA(A, k)

B. A parallelized winner-take-all

We implement the FlyHash algorithm on the GPU to process large amounts of data. Our main contribution is a parallelized winner-take-all binarization algorithm that, rather than taking as input a single vector as mentioned before, processes a batch of vectors in a matrix X of size N × b, where b is the batch size. The binarization step is thus applied to each column simultaneously. More specifically, we perform a parallel binary search for the values that, when used to threshold the respective columns, give the desired number of ones k.

Algorithm 2 contains the winner-take-all pseudocode. It starts by computing, for each column, the lower bound lb and the upper bound ub of the search interval by taking, respectively, the minimum and the maximum with a small margin ε > 0 to allow for strict inequalities. It then calculates the middle value mid and updates the extremes according to the current number of ones tot (corresponding to the number of values greater than mid): if they are greater than k, we increase the lower bound of the interval by setting it equal to the middle value; instead, if they are less than k, we decrease the upper bound to be equal to the middle value. The process is repeated a given number of times, which is at most 278 for single-precision floats, but in practice it can be set to 64 if a small fraction of erroneous entries can be tolerated (for example, the average fraction of erroneous entries caused by such a limitation is around 2.095 × 10 -7 when the output is of size 20000 × 5000).

Algorithm 2 Winner-take-all (WTA). Functions preceded or followed by a dot (Julia's broadcasting operator) are applied element-wise.

Input: X ∈ R N ×b , k ∈ [1, N ] Output: X ∈ {0, 1} N ×b lb = minimum(X, dims = 1). -ε ub = maximum(X,

IV. EXPERIMENTS

In our experiments, we compare the performance of the FlyHash algorithm on an Intel(R) Xeon(R) Gold 6240 CPU @ 2.60GHz CPU and a NVIDIA Quadro RTX 8000 GPU with CUDA version: 11.8, focusing on the processing of large amounts of data. We implemented the algorithms in the Julia programming language, which is now one of the most popular languages for scientific computing, and we relied on CUDA.jl package for the GPU part. On the algorithm engineering side, some optimizations have been made to speed up the process, such as pre-allocating variables for the GPU version. As for the CPU implementation, it uses efficient partial sorting algorithms to select the k winners [START_REF] Ram | Federated nearest neighbor classification with a colony of fruit-flies[END_REF]. Our code is available in the following Github repository: https://github.com/AInnervate/flyhash.jl, along with the code to replicate the experiments explained in more detail below. First, we test the speed of the two versions of the algorithm on well-known datasets taken from the Machine Learning Datasets Julia library MLDatasets.jl. One of the two datasets we examine is the FashionMNIST dataset, which is a collection of 60000 greyscale images with a size of 28 × 28. We therefore transform each image into a vector of dimension d = 28 × 28 = 784 and collect them in a matrix of dimension 784 × 60000. Then we pass it as input to the FlyHash algorithm, choosing the following parameters according to previous work [START_REF] Charles | A neural algorithm for a fundamental computing problem[END_REF]: the hash length N is equal to the hash factor h = 32 multiplied by the input dimension d, the projection parameter s is set to 5% of the input dimension d and the number of winners k is set to 5% of the hash length N . The same configuration is used to compute the time to process the CIFAR10 dataset, which is a collection of 50000 coloured images with a size of 32×32, so the input dimension of the matrix is d × b, where d = 32 × 32 × 3 = 3072 (the factor 3 comes from the fact that the images are coloured) and the batchsize is b = 50000.

In addition to those datasets, we perform experiments on synthetic data, where each entry is uniformly sampled in [0,1].

To understand how the two architectures behave when dealing with large amounts of data, we run the code varying the batchsize b in the range {2 1 , ..., 2 15 } and fixing the other parameters: the projection parameter and number of winners are as above, the hash factor is set to h = 128 and the input dimension is d = 1024.

The results are shown in Figure 4 and Figure 5. They are obtained by averaging 10 independent runs after first running the code without taking the time to avoid Julia's just-in-time compilation overhead. Both plots show low standard deviation values, in the first case as bars and in the second as shadows.

V. CONCLUSIONS

In this work, we proposed a GPU implementation of the famous FlyHash locality sensitive algorithm. Experiments show that our GPU version can run one order of magnitude faster than the best CPU version, thus allowing to speed up the use of the FlyHash algorithm in settings where GPUs are more easily available than dozens of CPU cores. In future work, we expect that the GPU code can be further improved in terms of performance by writing a lower-level CUDA kernel.

Important directions consist in exploring the implications of our implementations for the use of FlyHash in real-world applications, such as the ones mentioned in Section II.

Fig. 1 .

 1 Fig. 1. The three steps of the olfactory system of a fruit fly as illustrated in [SDN17].

Fig. 3 .

 3 Fig. 3. Diagram illustrating the core idea of the SLIDE framework, in which activating neurons are predicted by computing the scalar product between the projection of the input x and the projection of the layer weight matrix W via a Locality-sensitive Hashing scheme. The actual input of the neurons that are predicted to activate is then computed via the original input x and the corresponding rows of the original weight matrix W .

  dims = 1). + ε mid = (lb. + ub)./2 for _ in 1 : 64 do tot = count(X. > mid, dims = 1) lb = ifelse.(tot. > k, mid, lb) ub = ifelse.(tot. < k, mid, ub) mid = (lb. + ub)./2 end for return X. > mid

Fig. 4 .

 4 Fig. 4. Comparison on two popular datasets. Hash factor parameter is set to h = 32.

Fig. 5 .

 5 Fig. 5. Comparison as batchsize increases with fixed hash factor h = 128 and input dimension d = 1024.

This work has been supported by the French government, through the UCA DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE-0004, and through the AID INRIA-DGA agreement n°2019650072. The authors are grateful to the OPAL infrastructure from Université Côte d'Azur for providing resources and support.

* Authors are listed in alphabetical order.