Jiří Dobeš

Mario Ricchiuto -Remi

Abgrall -Herman Deconinck

Mario Ricchiuto

Remi Abgrall

Herman Deconinck

Analysis of hybrid RD-Galerkin schemes for Navier-Stokes simulations

Keywords: numerical analysis, second order schemes, parabolic problems, residual distribution, uniform accuracy, unstructured grids numerical analysis, second order schemes, parabolic problems, residual distribution, uniform accuracy, unstructured grids

We present an extension of multidimensional upwind residual distribution schemes to viscous flows. Following [Ricchiuto et al. J.Comp.Appl.Math., 2007], we consider the consistent coupling of a residual distribution (RD) discretization of the advection operator with a Galerkin approximation for the second order derivatives. Consistency is intended in the sense of uniform accuracy with respect to variations of the mesh size or, equivalently, for the advection diffusion equation, of the Peclet number. Starting from the scalar formulation given in [Ricchiuto et al. J.Comp.Appl.Math., 2007], we perform an accuracy and stability analysis to justify and extend the approach to the time-dependent case. The theoretical predictions are cofirmed by numerical grid convergence studies. The schemes are formally extended to the system of laminar Navier-Stokes equations, and compared to more classical finite volume discretizations on the solution of standard test problems.

Introduction

In this work we focus on the development of second order discretizations for the simulation of compressible laminar flows. To analyze different approaches, we will study the simple model given by the advection-diffusion equation

u t + λ • ∇u = ∇ • (ν∇u) (1)
in d spatial dimensions. We will focus to the case of d = 2.

In particular, let us start by considering the approximation of solutions to the steady limit of (1). Suppose we are given a triangulation of the two-dimensional spatial domain, and denote by E the generic element of the mesh. In this paper, we will consider methods that can be put in the form

u n+1 i = u n i -α i E| i∈E ϕ E i , (2)
where, (at least) for ν = 0

j∈E ϕ E j = E λ • ∇u n h dx = ϕ E (3)
with u n h the piecewise linear continuous interpolation of the values of the unknown in the nodes of the grid at iteration n, denoted by u n i , and with α i > 0 a relaxation parameter. With ϕ E i we denote the contribution to the equation for node i coming from the element E. In particular, for pure advection, these local residuals can be seen as fractions of the element residual ϕ E , defined by [START_REF] Dobeš | Implicit space-time method for laminar viscous flow[END_REF]. In this case the schemes reduce to the well known Residual Distribution (RD) of Fluctuation Splitting (FS) schemes [START_REF] Paillère | Multidimensional Upwind Residual Distribution Schemes for the Euler and Navier-Stokes Equations on Unstructured Grids[END_REF] When diffusion is present, the approach often used in practice is to add to an upwind distribution of the residual (3) a Galerkin approximation of the diffusion operator [START_REF] Edwin | Compressible Flow Simulation on Unstructured Grids Using Multi-dimensional Upwind Schemes[END_REF][START_REF] Paillère | Multidimensional Upwind Residual Distribution Schemes for the Euler and Navier-Stokes Equations on Unstructured Grids[END_REF]. Several applications of this hybrid discretization are shown in [START_REF] Sermeus | Drag prediction validation of a multi-dimensional upwind solver. CFD-based aircraft drag prediction and reduction[END_REF].

As remarked in [START_REF] Nishikawa | On high-order fluctuation splitting schemes for Navier-Stokes equations[END_REF], and later in [START_REF] Ricchiuto | On uniformly high-order accurate residual distribution schemes for advectiondiffusion[END_REF], this approach is not satisfactory because it ultimately leads to a loss of accuracy. In particular, even though on coarse meshes second order might be obtained in practice, the accuracy reduces to first order as on refines the grid. The objective of this paper, is to study the approach proposed in [START_REF] Ricchiuto | High order residual distribution schemes: Discontinuity capturing crosswind dissipation and extension to advection-diffusion[END_REF][START_REF] Ricchiuto | On uniformly high-order accurate residual distribution schemes for advectiondiffusion[END_REF], where the residual discretizations of the viscous problem is written as the perturbation of the Galerkin discretization

ϕ E i = ϕ a,G i + ϕ d,G i + ξ(ϕ a,RD i -ϕ a,G i ), (4)
where ϕ a,RD i stands for the contribution from the residual discretization of advective terms, ϕ a,G i stands for the Galerkin discretization of advective terms and ϕ d,G i stands for the Galerkin discretization of the diffusive terms. The local switch ξ ∈ [0, 1] depends on the cell Peclet (or cell Reynolds) number as

ξ(Pe E ) = 0 for Pe E → 0 1 for Pe E → ∞ (5)
with e.g.

Pe E = λ h ν (6)
where h the characteristic size of element E. In the following text, we drop all the superscripts E, whenever the reference to the local element is clear from the context. Provided that second order RD discretization is used, this formulation gives stable and second order accurate solution for limiting cases Pe → 0 and Pe → ∞. In the first case, the discretization boils to the central scheme, which is positive (under certain conditions) for the diffusion problem. In the later case Pe → ∞ it gives the standard second order RD scheme.

2 Numerical schemes for steady problems 2.1 Scalar equation. Solution I First, we focus on the LDA scheme, with the nodal contribution given as

ϕ a,LDA i = β LDA i ϕ E , β LDA i = k + i j∈E k + j ( 7
)
with element residual

ϕ a,E = j∈E k j u j . (8)

INRIA

Here k j is the upwind parameter defined as

k j = λ • n j d , (9)
where n j is the normal perpendicular to the face opposite of node j scaled by its surface and d is the number of spatial dimensions. Distribution coefficient for the method (4) can be written as

β * i = [1 -ξ(Pe)]β Gal + ξ(Pe)β RD i = 1 -ξ(Pe) d + 1 + ξ(Pe)β RD i . (10)
The Galerkin scheme for advection problem (for linear advection equation) is obtained by simply taking distribution coefficient β = 1/3. Galerkin scheme for the diffusion problem is given by

ϕ d,G i = ν j∈E n i • n j d 2 µ(E) u j . ( 11
)
First question is, how to define the cell Peclet number for a number of spatial dimensions bigger than one, d > 1, how to approximate velocity and how to choose characteristic size of the element. The approach in [START_REF] Ricchiuto | High order residual distribution schemes: Discontinuity capturing crosswind dissipation and extension to advection-diffusion[END_REF] takes

Pe = λ L 2 h dD ν , h 2D = 2 µ(E) π , h 3D = 3 3 µ(E) 4π , (12)
what is chosen such that h recovers the circle or ball diameter in higher dimension. Anther approach is to define the Peclet number on a basis of the ratio of the cell residuals, namely advection and diffusion residual

Pe = E λ • ∇u dx E ν∆u xx ≈ µ(E) λ δu h µ(E)ν δu h 2 ≈ λ h ν , (13)
where δu stands for the value proportional to the variation of the solution u over the element. The problem is, that the diffusive element residual

ϕ d,E = i∈E ϕ d i (14)
is always zero for linear elements. Hence some norm of the nodal contributions has to be chosen. The advantage of this approach is, that it is not necessary to determine velocity and the characteristic size element. However, the choice of the norm of the residual is also not unique. Among the possible choices one can select e.g.

Pe = i∈E |ϕ a i | i∈E |ϕ d i | , Pe = i∈E (ϕ a i ) 2 i∈E (ϕ d i ) 2 . ( 15
)
We will use the first option in this work.

The blending coefficient has to be chosen such that

ξ(0) = 0, ξ(∞) = 1. (16)
Actually, any scheme written as ( 4) is second order accurate for h → 0 if it respects ξ → 0 for Pe → 0. 1 One choice is

ξ(Pe) = max(1, Pe). (17)
This is a simple choice and it respects our first requirement, i.e. RD method is obtained for Pe → ∞ and Galerkin method for Pe → 0. However, e.g. for 1D problem and Pe ≈ 1 we get the upwind discretization of advection term with central discretization of the diffusion term, and this discretization has the truncation error of first order.

To have better idea, how the blending coefficient should look like, we will examine advection-diffusion equation in 1D with Euler forward time integration procedure

u n+1 i -u n i ∆t = -ξ u n i -u n i-1 ∆x -(1 -ξ) u n i+1 -u n i-1 2∆x + ν u n i+1 -2u n i + u n i-1 ∆x 2 (18)
with a > 0 and we will find a lower bound on ξ(Pe) for scheme positivity. We gather terms into the form of

u n+1 i = c 0 u n i + c +1 u n i+1 + c -1 u n i-1 . (19)
For the positivity of the scheme, positivity of the coefficients is required c 0 ≥ 0,

c 1 ≥ 0, c -1 ≥ 0. The first condition gives us a time step restriction ∆t ≤ 1 ξ a ∆x + ν ∆x 2 (20)
and the last condition is always satisfied. The second condition gives us restriction for the blending coefficient

ξ ≥ 1 - 1 Pe , (21)
what is a lower bound for the positivity of the scheme. Since the central scheme has lower error than the upwind scheme, it is desirable to have ξ as small as possible. We can take

ξ(Pe) = max(0, 1 - 1 Pe ). (22)
In this case, the scheme reduces to the second order, positive Galerkin method for Pe ≤ 1.

In the case of two spatial dimensions, the Galerkin scheme for the diffusive part of the equation is positive if the triangulation is Delaunay. The positivity criterion for the Galerkin scheme for both advection and diffusion discretization can be found only for very special arrangements of the mesh.

Scalar equation. Solution II

The other approach is to use fully residual scheme, where the viscous part is included into the residual. The scheme looks like

ϕ i = β i (ϕ a + ϕ d i ), ( 23
)
1 As long as ξ(Pe) behaves as a linear function for Pe → 0.

INRIA

where β i is the distribution coefficient, ϕ a is the advection residual and ϕ d i is the diffusion residual.

We can compute gradient in nodes, denoted by (∇u) h , e.g. by the least square reconstruction from neighboring nodes. The diffusion residual is to be approximated as

ϕ d i ≈ E ∇[µ (∇u) h ] dx. ( 24
)
We will evaluate this scheme in one dimension. Nodal gradients (derivatives) are given by the central discretization

∂u ∂x h i ≈ u i+1 -u i-1 2∆x . ( 25
)
The fully discrete scheme is

u n+1 i -u n i ∆t + a u n i -u n i-1 ∆x = ν ∆x u n i+1 -u n i-1 2∆x - u n i -u n i-2 2∆x . ( 26
)
It can be written as

u n+1 i = ν∆t ∆x 2 u n i+1 + 1 - ∆ta ∆x - ν∆t ∆x 2 u n i + ∆ta ∆x - ν∆t ∆x 2 u n i-1 + ν∆t ∆x 2 u n i-2 .
(27) First and last term on the RHS are always positive, the second term is positive under a time step constrain eq. ( 20). The third term is positive if Pe > 1. As a conclusion, this scheme is positive for Pe > 1 under a time-step restriction.

In order to resolve problem with positivity, it can be blended with Galerkin scheme for Pe → 0, as in the previous approach. For this scheme we present only the theoretical result, we didn't include any numerical experiments.

Viscous compressible fluid flow

We present rather straight-forward extension of the method to the system of equations. We use the linearized Galerkin method, which reduces to the central discretization, with distribution matrix

β i = 1 d + 1 I. (28)
The Peclet number we define with the accordance with the definition for the scalar problem [START_REF] Sermeus | Drag prediction validation of a multi-dimensional upwind solver. CFD-based aircraft drag prediction and reduction[END_REF] as

Pe = i∈E ϕ a i L2 i∈E ϕ d i L2 . ( 29
)
We can easily modify the distribution coefficients analogously to the eq. ( 10). In the case, there the distribution matrices are not explicitly defined, and only nodal contribution ϕ i are known (and the element residual ϕ E as its sum), the following modification can be applied:

ϕ * i = ξ(Pe)ϕ i + 1 -ξ(Pe) d + 1 ϕ E . ( 30
)
The discretization of viscous terms is a strait-forward extension of [START_REF] Ricchiuto | High order residual distribution schemes: Discontinuity capturing crosswind dissipation and extension to advection-diffusion[END_REF], for more discussion see e.g. [START_REF] Edwin | Compressible Flow Simulation on Unstructured Grids Using Multi-dimensional Upwind Schemes[END_REF].

Finite volume scheme

We have used a cell centered finite volume scheme for the comparison. The variables are stored in centers of mesh elements. The method uses linear least square reconstruction, with Barth's limiter [START_REF] Barth | The design and application of upwind schemes on unstructured meshes[END_REF] as a option. The numerical flux is approximated by the Roe's Riemann solver [START_REF] Roe | Approximate Riemann solvers, parameter vectors, and difference schemes[END_REF] in the case of Navier-Stokes equations, or simple upwind flux in the case of scalar equations. The discretization of viscous fluxes is done on dual grid. Solution from elements centers are interpolated to vertices of the mesh. Derivatives are then approximated on auxiliary volumes connecting centroids of the cell with mesh vertices.

3 Numerical experiments for steady problems

Steady scalar advection-diffusion equation

First, we repeat test case from [START_REF] Nishikawa | On high-order fluctuation splitting schemes for Navier-Stokes equations[END_REF][START_REF] Ricchiuto | High order residual distribution schemes: Discontinuity capturing crosswind dissipation and extension to advection-diffusion[END_REF]. We solve the equation ( 1) on spatial domain [0, 1] 2 , with λ = (λ x , λ y ) = (0, 1), ν = 0.01. The problem has exact solution

u = -cos(2πη) exp( ζ(1 - √ 1 + 16π 2 ν 2 ) 2ν ), (31)
with η = λ y x -λ x y and ζ = λ x x + λ y y.

We use a sequence of unstructured meshes with h = 1/10, 1/20, 1/40, 1/80, 1/150, 1/300. This corresponds to the cell Peclet numbers of range Pe = [0.33, 10]. Results are shown in Fig. 1. One can see that the original scheme deviates from the second order slope for Pe 3, where both modifications continue in the second order convergence. The newer modification (22) gives the lower error, as expected.

Incompressible laminar boundary layer -Blasius's solution

The classical Blasius similarity solution provides data for the comparison. The text by White [START_REF] Frank | Viscous Fluid Flow[END_REF] or Schlichting [START_REF] Schlichting | Boundary-Layer Theory[END_REF] discusses this solution.

Parameters and mesh size were taken from the web page http://www.grc.nasa.gov/WWW/wind/valid/fp The grid points are evenly spaced along the plate. The normal grid points are placed at constant η coordinates, where

η = y u∞ 2νx , (32)
with the grid evenly spaced until η = 4 and then spaced by a factor of 1.1 until the outer boundary at η = 50 is reached. For x < 0.3 the y coordinate is the same as x = 0.3. Final grid resolution is 52 × 35 elements. There are 13 nodes in the x direction prior to leading edge of the flat plate. Fig. 2 shows how the grid looks like. We compute a flow over the flat plate with a free stream Mach number Ma = 0.3 and the Reynolds number based on the length of the flat plate is approx. 2 • 10 5 . We have set the following free stream conditions:

ρ ∞ = 1.4, u ∞ = 0.3, p ∞ = 1, ν = 1.5 • 10 -6 . The self-similar solution gives c f = ∂u ∂y w √ Re x , Re x = u e x ν , ∂u ∂y w = 0.664067. ( 33
)
Technically important is a value of c f coefficient

c f = τ w 1 2 ρ e u 2 e , τ w = ν ∂u ∂y y=0 . ( 34
)
The Fig. 3 shows the distribution of the cell Peclet number together with the blending coefficient away from the plate. Figs. 4 to 7 shows the solution in terms of isolines of the Mach number. One can notice that all the solutions are very similar. Distribution of the friction coefficient along the plate is shown in Fig. 8 and the cut of the u velocity in Fig. 9. This test case is taken from [START_REF] Bassi | A high-order accurate discontinous finite element method for the numerical solution of the compressible navier-stokes equations[END_REF]. The computational mesh is shown in Figs. 10 and11, solution with the LDA scheme in Fig. 12. The friction along the airfoil is plotted in Fig. 13. There is virtually no difference in the friction coefficient in the modified version of the RD scheme.

u t + λ • ∇u = ν∆u. ( 35
)
The dual-time (or space-time) nodal contribution is will be taken again as

ϕ i = ϕ a,G i + ϕ d,G i + ξ(ϕ a,RD i -ϕ a,G i ), ( 36
)
where ϕ a i include both contributions from the advection terms and time derivative

ϕ a ≈ E (u t + λ • ∇u) d x. ( 37
)
The nodal contribution from the Galerkin scheme including the mass matrix is

ϕ a,G i = µ(E) d + 1 j∈E 1 + δ ij d + 2 ∂u j ∂t + 1 d + 1 ϕ E , (38)
while for the LDA of Ferrante and Deconinck [START_REF] Ferrante | Solution of the unsteady Euler equations using residual distribution and flux corrected transport[END_REF] it is

ϕ a,LDA i = µ(E) d + 1 k + i N + 2 d + 2 I - 1 d + 1 I ∂u i ∂t + + µ(E) d + 1 j∈E j =i k + j N + 1 d + 2 I - 1 d + 1 I ∂u j ∂t + k + i N ϕ E . ( 39
)
Let us examine the Galerkin scheme first. In 1D, the semi-discrete equation is 1 6

∂u i+1 ∂t + 4 6
∂u i ∂t + 1 6 ∂u i-1 ∂t + a u i+1 -u i-1 2∆x = ν u i+1 + 2u i -u i-1 ∆x 2 . ( 40
)
The fully discrete version using the Crank-Nicholson time integration method is then 1 6

u n+1 i+1 -u n i+1 ∆t + 4 6
u n+1 i -u n i ∆t + 1 6
u n+1 i-1 -u n i-1 ∆t + 1 2 a u i+1 -u i-1 2∆x -ν u i+1 + 2u i -u i-1 ∆x 2 n+1 + 1 2 a u i+1 -u i-1 2∆x -ν u i+1 + 2u i -u i-1 ∆x 2 n = 0. ( 41
)
The fully discrete version of the LDA scheme with the Crank-Nicholson time integration and central discretization of the viscous terms is

5 12∆t - 1 2 a ∆x - 1 2 ν ∆x 2 u n+1 i-1 + 2 3∆t + 1 2 a ∆x + ν ∆x 2 u n+1 i + - 1 12∆t - 1 2 ν ∆x 2 u n+1 i+1 + - 5 12∆t - 1 2 a ∆x - 1 2 ν ∆x 2 u n i-1 + - 2 3∆t + 1 2 a ∆x + ν ∆x 2 u n i + 1 12∆t - 1 2 ν ∆x 2 u n i+1 = 0. ( 42
)
INRIA Now, we take a blend between the LDA and the Galerkin scheme with the blending coefficient ξ, giving

ξ 5 12∆t - 1 2
a ∆x + (1 -ξ) 1 6∆t - 1 4 a ∆x - 1 2 ν ∆x 2 u n+1 i-1 + 2 3∆t + ξ 2 a ∆x + ν ∆x 2 u n+1 i + ξ - 1 12∆t + (1 -ξ) 1 6∆t + 1 4 a ∆x - 1 2 ν ∆x 2 u n+1 i+1 + ξ - 5 12∆t - 1 2
a ∆x + (1 -ξ) - 1 6∆t - 1 4 a ∆x - 1 2 ν ∆x 2 u n i-1 + - 2 3∆t + ξ 2 a ∆x + ν ∆x 2 u n i + ξ 1 12∆t + (1 -ξ) - 1 6∆t + 1 4 a ∆x - 1 2 ν ∆x 2 u n i+1 = 0. ( 43
)
For x = 0 it is the Galerkin scheme, while for ξ = 1 it is the LDA scheme with mass matrix and the central viscous discretization. After following procedure in [START_REF] Warming | The modified equation approach to the stability and accuracy analysis of finite-difference methods[END_REF], we get modified equation

u t + au x = νu xx + 1 2 ξν∆x - 1 12 a 3 ∆t 2 u xxx + -ξ 1 24 a∆x 3 + 1 4 a 2 ν∆t 2 - 1 12 ν∆x 2 + ξ 2 1 4 ν∆x 2 u xxxx . ( 44
)
We will focus on the first term. We take a time-step as

∆t = σ a ∆x + ν ∆x 2 , 0 < σ ≤ 1, σ ≈ 1 (45)
and we get

1 2 ξν∆x - 1 12 a 3 ∆t 2 = 1 2 ν∆x     ξ - 1 6
σ 2 Pe 3 1 + Pe 2 α     = 1 2 ν∆x (ξ -α) . (46)
Following behavior can be observed:

Galerkin scheme (ξ ≡ 0): α is of O(Pe 3 ) ≈ O(∆x 3 ), it means that RHS term (46) is O(∆x 4
). In this case for ∆x → 0, in equation ( 44) term u xxxx is dominating, the scheme is second order accurate.

LDA scheme (ξ ≡ 1): for ∆x → 0 the equation (46) behaves as ν∆x/2, the scheme is first order accurate.

Case ∆x ν/a (i.e. Pe 1): We will check when α ≈ ξ, i.e. when u xxx truncation error of Galerkin scheme will be the same order as the truncation error of the LDA inviscid + Galerkin viscous scheme. After solving the nonlinear equation, we get Pe ≈ 7.66. For this particular value of the Peclet number the u xxx the two terms substract and the truncation error is zero, it might not true in more spatial dimensions. For Pe 7.66 the truncation error coming from the central discretization is of the same order as the truncation error coming from the mismatch of the central discretization of the viscous terms and the upwind discretization of the advection term. On another words, for Pe > 7.66 the idea of error reduction with blending of Galerkin and upwind schemes for advection terms does not make much sense anymore, it is good enough to use the upwind scheme for the advection terms and Galerkin scheme for diffusion terms.

Let us check, what is the condition on ξ for the positivity of the scheme (43). The stability analysis of the LDA scheme gives us a time step restriction ∆t ≤ 1

a 2∆x + ν ∆x 2 , ( 47
)
or equivalently

γ = a∆t ∆x ≤ 1 1 2 + 1 Pe . ( 48
)
After some algebra, one can conclude that the bound on ξ (if the maximal time

-step γ = 1 is used) is ξ ≥ max 0, Pe -1 Pe + 1 . ( 49
)
This restriction is actually more relaxed than the one given by the (22). In the following computations, we will still use the value given by (22).

Viscous compressible fluid flow

We apply the same extension as before.

5 Numerical experiments time dependent problems

Scalar rotational advection-diffusion problem

We consider an advection-diffusion equation ( 1) with λ = (λ x , λ y ) = (-y, x), i.e. case of rotation-diffusion, with rotation around origin (0, 0) by angular velocity ω = 1. The solution of a pure diffusion problem rotated with angular velocity ω is the solution of the problem. We first look at the problem

u t = ν∆u (50)
in cylindrical coordinates. The problem reads

u t = ν u rr + 1 r u r + 1 r 2 u θθ . (51)
We will look only to radial-symmetric solution, hence last term drops. We will search for the solution using Fourier method, i.e. the solution is in form

u(t, r) = T (t) R(r). (52)
u = u ∞ erf( y 2 √ νt ). ( 65
)
The same test case (on finer mesh) was already used in [START_REF] Dobeš | Implicit space-time residual distribution method for unsteady laminar viscous flow[END_REF][START_REF] Dobeš | Implicit space-time method for laminar viscous flow[END_REF][START_REF] Dobeš | Implicit space-time residual distribution method for unsteady viscous flow[END_REF][START_REF] Dobeš | Implicit space-time residual distribution method for unsteady laminar viscous flow. 33rd Computational Fluid Dynamics Course[END_REF]. We use a very coarse mesh with spacing h = 1/10 (217 nodes and 392 elements only). Two periods of the solution for the viscous hybrid scheme together with the mesh is plotted in Fig. 16. Unfortunately, there is no visual advantage of the hybrid scheme. Notice much worse performance of the FV scheme with comparison to the RD schemes. Figure 17: Rayleigh problem. Cut in the y direction for the LDA scheme with hybrid method and with standard method. The finite volume scheme with linear reconstruction is included.

Vortex shedding past a circular cylinder

Mach number Ma = 0.1, Reynolds number Re = 100. The laminar vortex shedding starts from Re ≈ 70, for Re ≤ 70 the solution is steady. 48 elements is placed around the cylinder. Computations by LDA scheme with and without the new approach was started from already periodic state, precomputed earlier.

The solution is plotted in Fig. 18. There are minor differences between the numerical schemes, even that the cell Reynolds number near the wall is of order 2.

Transonic vortex pairing

This test case involves a transonic vortex pairing in a mixing layer [START_REF] Yee | Low-dissipative highorder shock-capturing methods using characteriscic-based filters[END_REF]. The problem consists of a shear layer defined by two free streams with velocity profiles u = tanh(2y)/2, v = 0. To these velocity profiles we superimpose the velocity perturbations Isolines of entropy, LDA scheme, presented approach. Isolines of Peclet number.

v ′ =
Lift dependence on time.

The speed of sound (and hence the density) in the initial solution is determined from the assumption of constant stagnation enthalpy

a 2 = a 2 1 + γ -1 2 (u 2 1 -u) (67)
and Ma ∞ = 0.8. Constant initial static pressure p = 1 is assumed across the whole flow-field. The grid used consists of an isotropic triangulation stretched in the y-direction using the mapping

y = L y 2 sinh(b y η) sinh(b y ) , (68)
where η ∈ (-1, 1) and b y = 3.4. The mesh contains 201×201 nodes. The computation has been run with the B scheme. The solution at time t = 160 is shown in Fig. 19, where we plot 30 levels of isolines of the temperature. Comparing with the fourth order results of [START_REF] Yee | Low-dissipative highorder shock-capturing methods using characteriscic-based filters[END_REF], our method shows all features of flow-field. There is very little difference between the numerical methods. The map of the cell Peclet number is also included. [START_REF] Dobeš | Second order blended multidimensional residual distribution scheme for steady and unsteady computations[END_REF]). Left to right: Isolines of temperature -standard scheme, new approach. Isolines of Peclet number.

Figure 1 :

 1 Figure 1: 2D advection-diffusion equation, test eq. (31). a) Original distribution coefficients, i.e. LDA scheme for inviscid terms and Galerkin scheme for viscous terms. b) modification of the distribution coefficients given by eqns. (12), (17) (older modification) c) modification of the distribution coefficients given by eqns. (13), (22) (newer modification). d) comparison of different modifications in L 2 norm.

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Mesh for laminar incompressible flow over a flat plate

Figure 5 :Figure 6 :Figure 7 :Figure 8 :Figure 9 :

 56789 Figure 5: Isolines of Mach number. LDA scheme with ξ ≡ 1.

3. 3

 3 Steady flow past NACA0012: Ma = 2, Re = 106, α = 10 •

Figure 10 :

 10 Figure 10: NACA 0012 Ma = 2 Re = 106, α = 10 • . Computational mesh.

Figure 11 :INRIAFigure 12 :

 1112 Figure 11: NACA 0012 Ma = 2 Re = 106, α = 10 • . Computational meshzoom.

Figure 13 :

 13 Figure 13: NACA 0012 Ma = 2 Re = 106, α = 10 • . (Scaled) friction. Comparison of the LDA scheme with ξ ≡ 1 (denoted by old approach) and the blending coefficient given by (29), (22) (denoted as the new limiting).

4

  Numerical schemes for time dependent problems 4.1 Scalar equation. Solution I Now, we will investigate time-dependent problem

Figure 14 :

 14 Figure 14: Unsteady rotation-diffusion problem -initial conditions.

5 Figure 15 :INRIA 5 . 2

 51552 Figure15: Unsteady rotation-diffusion problem -LDA scheme with mass matrix, convergence study. Nolim.: original version LDA scheme with Galerkin treatment of viscous terms. Gal.: Galerkin central scheme both for advection and diffusion. Newl.: the novel approach, hybrid blending both formulations.

Figure 16 :

 16 Figure16: Rayleigh problem. Solution using the LDA scheme with the mass matrix and with viscous hybrid method. Solution at time t = 0.1. Two periods plotted together with the computational mesh.

2 k=1a

 2 k cos(2πkx/L x + φ k ) exp(-y 2 /b) (66) with parameters a 1 = 0.01, a 2 = 0.05, φ 1 = φ 2 = π/2, b = 10. The u ′ perturbation is computed from condition ∇(u ′ , v ′ ) = 0. The problem has been solved inside a rectangular area L x × L y with L x = 30 and L y = 100. The top and bottom boundaries are treated as inviscid walls, and periodic boundary conditions are set on the left and right boundaries. The kinematic viscosity in the free streams is set to ν ∞ = 10 -3 , corresponding to a Reynolds number Re = 1000. Sutherland's law for viscosity has been used in the computations.

Figure 18 :

 18 Figure 18: Top to bottom: Isolines of entropy, LDA scheme, standard approach. Isolines of entropy, LDA scheme, presented approach. Isolines of Peclet number. Lift dependence on time.

Figure 19 :

 19 Figure19: Transonic vortex pairing, mesh 201×201. Solution at t = 160. Bx scheme (see[START_REF] Dobeš | Second order blended multidimensional residual distribution scheme for steady and unsteady computations[END_REF]). Left to right: Isolines of temperature -standard scheme, new approach. Isolines of Peclet number.

Table 1 :

 1 Comparison of orders of accuracy for 2D unsteady advection-diffusion problem

	Scheme	L 1 order L 2 order L ∞ order
	LDA inviscid + Galerkin viscous	1.03	1.00	1.00
	Galerkin all (unstable for large Pe)	1.96	1.96	1.77
	LDA+Galerkin hybrid scheme	2.21	2.23	1.93
	log 10 ( err L 2		Nolim. L 2 Nolim. L ∞ Newl. L ∞ Newl. L 2 Newl. L 1 Gal. L ∞ Gal. L 2 Gal. L 1 Nolim. L 1
	h

RR n 7220

Dobeš, Ricchiuto, Abgrall and Deconinck

Conclusions

We have extended the approach of [12] for unsteady problems and system of Navier-Stokes equations. We have shown on numerically for scalar problem that the second order of accuracy is obtained, while with the previous attempt of [16,10] gives only first order accurate schemes. However, we have also theoretically shown, that for problems of cell Peclet number larger than approx. 7.5, the previous approach is qualitativelly similar to the new hybrid approach. In this case, the hybrid approach does not bring any advantage and it is enough to use the standard scheme of [16,10].

This gives us

The solution of the equation T ′ /T = c 1 is simply T (t) = c 2 exp(c 1 t). The second equation can be written as

with well known solution in form

where J 0 and Y 0 are the Bessel functions of the first and the second kind. Since Y 0 is singular at the r = 0, we will not consider this part of the solution. The problem has the solution

Now, we will turn out attention to the solution of the problem (1)

The solution is given by the equation ( 56) with rotated frame of reference. Now, we have to choose the parameters. First, maximal value of the solution after one rotation at the time t = 2π is chosen 0.2, starting with u 0 = 1. Hence, exp(2πc 1 ) = 0.2 (58)

giving c 1 = ln(0.2)/2/π. From the condition u 0 | max = 1 the c 0 = 1. Now, the viscosity has to be chosen. We set ν = 0.005. The implementation is easy, because the Bessel function is part of the standard C library in the same manner as e.g. sin() and it is called double j0(double x).

Finally, the solution is given by

with

x = x cos α -y sin α + 0.5 (62) ỹ = x sin α + y cos α (63)

Initial conditions are plotted in Fig. 14.

The problem was solved with the LDA scheme with original approach, i.e. LDA+Galerkin viscous terms, the Galerkin discretization for all the terms and finally, with above described hybrid approach.


Jean B Érard

Jean-Baptiste Gou

BRUNET-DERRIDA BEHAVIOR OF BRANCHING-SELECTION PARTICLE SYSTEMS ON THE LINE

We consider a class of branching-selection particle systems on R similar to the one considered by E. Brunet and B. Derrida in their 1997 paper "Shift in the velocity of a front due to a cutoff". Based on numerical simulations and heuristic arguments, Brunet and Derrida showed that, as the population size N of the particle system goes to infinity, the asymptotic velocity of the system converges to a limiting value at the unexpectedly slow rate (log N ) -2 . In this paper, we give a rigorous mathematical proof of this fact, for the class of particle systems we consider. The proof makes use of ideas and results by R. Pemantle, and by N. Gantert, Y. Hu and Z. Shi, and relies on a comparison of the particle system with a family of N independent branching random walks killed below a linear space-time barrier.

1. Introduction 1.1. Brunet-Derrida behavior. In [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF][START_REF] Brunet | Microscopic models of traveling wave equations[END_REF], E. Brunet and B. Derrida studied, among other things, a discrete-time particle system on Z, in which a population of particles with fixed size N undergoes repeated steps of branching and selection. As time goes to infinity, the population of N particles, taken as a whole, moves ballistically, with an asymptotic speed depending on the population size N . One remarkable property of this system is the following: as N goes to infinity, the asymptotic speed of the population of particles converges to a limiting value, but at the unexpectedly slow rate of (log N ) -2 , bringing to light an unusually large finite-size effect. This behavior was, on the one hand, observed by Brunet and Derrida on direct numerical simulations of the particle system (with large numbers of particles, up to N = 10 16 ). On the other hand, Brunet and Derrida provided a justification for this behavior through the following argument. First, in the limit where N goes to infinity, the time-evolution of the distribution of particles in the branching-selection system is governed by a deterministic equation, which can be viewed as a discrete version of the well-known F-KPP equation ( 1)

∂u ∂t = ∆u + u(1 -u),
where u = u(x, t), x ∈ R, t ≥ 0. To account for the fact that there is only a finite number N of particles in the system instead of an infinite one -whence a resolution equal to 1/N for representing distributions of mass -, one may introduce a cut-off value of 1/N in the equation, and expect that this modified equation still reflects at least some of the behavior of the original particle system. Whence the question of studying, for large N , an equation of the form:

(2) ∂u ∂t = ∆u + u(1u)1(u ≥ 1/N ).

In fact, Brunet and Derrida could provide heuristic arguments for this new problem, showing that, for large N , the effect of the cut-off is to shift the speed of travelling wave solutions of Equation ( 2) from the speed of those of Equation [START_REF] Athreya | Branching processes[END_REF], by an amount of order (log N ) -2 . In turn, these arguments were supported by numerical simulations of (discrete versions of) Equation ( 2). This result concerning the F-KPP equation with cut-off has recently been given a rigorous mathematical proof, see [START_REF] Benguria | On the speed of pulled fronts with a cutoff[END_REF][START_REF] Benguria | Validity of the Brunet-Derrida formula for the speed of pulled fronts with a cutoff[END_REF][START_REF] Dumortier | The critical wave speed for the Fisher-Kolmogorov-Petrowskii-Piscounov equation with cut-off[END_REF].

A related question (see [START_REF] Brunet | Effect of microscopic noise on front propagation[END_REF]), is that of the behavior of the F-KPP equation with small noise, i.e. of the equation ( 3)

∂u ∂t = ∆u + u(1 -u) + u(1 -u) N Ẇ ,
where Ẇ is a standard space-time white-noise, and N is large. Rigorous results have recently been derived for this model too, see [START_REF] Conlon | On travelling waves for the stochastic Fisher-Kolmogorov-Petrovsky-Piscunov equation[END_REF][START_REF] Mueller | Small noise asymptotics of traveling waves[END_REF][START_REF] Mueller | Effect of noise on front propagation in reaction-diffusion equations of KPP type[END_REF], establishing that the speed of the random travelling wave solutions of Equation ( 3) is, for large N , shifted from the speed of those of (1) by an amount of order (log N ) -2 . We thus have (at least) three examples of what may be called Brunet-Derrida behavior, in three different and more or less loosely related frameworks (branchingselection particle systems, F-KPP-equation with cut-off, F-KPP equation with noise), two of which have already been established rigorously.

1.2. Main result. The goal of this paper is to give a proof of Brunet-Derrida behavior for a class of branching-selection systems that is similar (but not exactly identical) to the one originally studied by Brunet and Derrida in [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF][START_REF] Brunet | Microscopic models of traveling wave equations[END_REF].

To be specific, we consider a discrete-time particle system with N particles on R evolving through the repeated application of branching and selection steps defined as follows:

• Branching: each of the N particles is replaced by two new particles, whose positions are shifted from that of the original particle by independently performing two random walk steps, according to a given distribution p; • Selection: only the N rightmost particles are kept among the 2N obtained at the branching step, to form the new population of N particles. Our assumptions on the random walk distribution p are listed below, and come from the need to apply the result of the paper [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] by N. Gantert, Y. Hu and Z. Shi on the survival probability of the branching random-walk killed below a linear space-time boundary, in the special case of deterministic binary branching.

Introduce the logarithmic moment generating function of p defined by Λ(t) := log exp(tx)dp(x).

Here are the assumptions on p: (A1) The number σ := sup{t ≥ 0; Λ(-t) < +∞} is > 0.

(A2) The number ζ := sup{t ≥ 0; Λ(t) < +∞} is > 0. (A3) There exists t * ∈]0, ζ[ such that t * Λ ′ (t * ) -Λ(t * ) = log 2. Under these assumptions, both numbers

χ(p) := π 2 2 t * Λ ′′ (t * ), v(p) := Λ ′ (t *
) are well-defined, and satisfy 0 < χ(p) < +∞ and v(p) ∈ R. Simple cases for which these assumptions hold are e.g. the Bernoulli case for α ∈]0, 1/2[, where p = αδ 1 + (1α)δ 0 , the uniform case, where p is the uniform distribution on the interval [0, 1], and the gaussian case, where p is the standard Gaussian distribution on R.

In Section 3 below, it is proved that, after a large number of iterated branchingselection steps, the displacement of the whole population of N particles is ballistic, with deterministic asymptotic speed v N (p), and that, as N goes to infinity, v N (p) increases to a limit v ∞ (p), which turns out to be equal to the v(p) defined above, and is thus finite under our assumptions. The main result concerning the branchingselection particle system is the following theorem:

Theorem 1. Assume that (A1)-(A2)-(A3) hold. Then, as N goes to infinity, (4) v ∞ (p) -v N (p) ∼ χ(p)(log N ) -2 .
1.3. Credits. The proof of Theorem 1 given in this paper is based on a comparison of the particle system with a family of N independent branching random walks killed below a linear space-time barrier, and makes use in a crucial way of ideas and results from the following two sources: the paper [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF] by R. Pemantle on complexity bounds for algorithms seeking near optimal paths in branching random walks, and the paper [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] by Gantert, Hu and Shi on the survival probability of the branching random-walk killed below a linear space-time boundary. A detailed description of exactly which ideas and results are used and how is given in Sections 4, 5 and 6 below. Note that the existence of a link between the Brunet-Derrida behavior of a branching-selection particle system such as the one studied here, and the asymptotics of the survival probability for branching random walks killed below a linear space-time barrier, was already suggested in the papers [START_REF] Derrida | The survival probability of a branching random walk in presence of an absorbing wall[END_REF][START_REF] Simon | Quasi-stationary regime of a branching random walk in presence of an absorbing wall[END_REF] by B. Derrida and D. Simon, where Brunet-Derrida-like features were observed for a quasi-stationary regime of killed branching random walks; the present paper gives an explicit and rigorous version of such a relation. Finally, let us mention that a first version [START_REF] Bérard | An example of Brunet-Derrida behavior for a branching-selection particle system on Z[END_REF] of the present work was completed by one of the authors (J.B.) before the results in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] became publicly available. In [START_REF] Bérard | An example of Brunet-Derrida behavior for a branching-selection particle system on Z[END_REF], only the (log N ) -2 order of magnitude of the difference v ∞ (p)v N (p) in the Bernoulli case was established. The results in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] then allowed us to prove Theorem 1, which is both more precise and more general.

1.4. Organization of the paper. The rest of the paper is organized as follows.

In Section 2, we provide the precise notations and definitions that are needed in the sequel. Section 3 contains a discussion of various elementary properties of the model we consider. Section 4 collects the results from [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] that are used in the sequel. Section 5 contains the proof of the lower bound part of Theorem 1, while Section 6 contains the proof of the upper bound part. Section 7 discusses the Bernoulli(α) case for α ≥ 1/2, showing that the conclusion of Theorem 1 may fail to hold when Assumption (A3) is not met. Section 8 is an attempt to provide a self-contained explanation of the (log N ) -2 order of magnitude appearing in Theorem 1. The arguments in this section are only discussed in an informal way.

Notations and definitions

2.1. Particle systems on R. It is convenient to represent finite populations of particles by finite counting measures on R. We use the notation C to represent the set of all finite counting measures on R.

For ν ∈ C, the total mass of ν (i.e. the number of particles in the population it describes) is denoted by M (ν). We denote by max ν and min ν respectively the maximum and minimum of the (finite) support of ν. We also define the diameter d(ν) := max νmin ν. Given µ, ν ∈ C, we use the notation ≺ to denote the usual stochastic ordering:

µ ≺ ν if and only if µ([x, +∞[) ≤ ν([x, +∞[) for all x ∈ R. In particular, µ ≺ ν implies that M (µ) ≤ M (ν), and it is easily seen that, if µ = M (µ) i=1 δ x i and ν = M (ν) i=1 δ y i , with x 1 ≥ • • • ≥ x M (µ) and y 1 ≥ • • • ≥ y M (ν) , µ ≺ ν is equivalent to M (µ) ≤ M (ν) and x i ≤ y i for all i ∈ [[1, M (µ)]].
For all N ≥ 1, let C N denote the set of finite counting measures on R with total mass equal to N . In the sequel, we use the notation (X N n ) n≥0 to denote a Markov chain on C N whose transition probabilities are given by the branchingselection mechanism with N particles defined in Section 1.2, and which starts at a deterministic value X N 0 ∈ C N . We assume that this Markov chain is defined on a reference probability space denoted by (Ω, F, P).

2.2.

Branching random walks. In the sequel, we use the notation BRW to denote a generic branching random walk on a regular rooted binary tree, with value zero at the root, and i.i.d. displacements with common distribution p along each edge. More formally, BRW consists of a pair (T, Φ), where T is a regular rooted binary tree, and Φ is a random map, associating to each vertex u ∈ T a random variable Φ(u) ∈ R in such a way that Φ(root) = 0 and that the collection (Φ(v) -Φ(u)) (u,v) is i.i.d. with common distribution p, where (u, v) runs over the set of pairs of vertices of T such that u is the father of v. We say that Φ(u) is the value of the branching random walk at vertex u. The probability measure governing BRW is denoted by Q.

Given m ≥ 1, we say that a sequence u 0 , . . . , u m of vertices in T is a descending path if, for all i ∈ [[1, m]], u i-1 is the father of u i . The set of vertices of T located at depth m is denoted by T(m).

Elementary properties of the model

As a first quite elementary property, note that, from Assumptions (A1) and (A2), E(max X N n ) and E(min X N n ) are finite for all n ≥ 0, for any choice of the (deterministic) initial condition X N 0 ∈ C N .

3.1. Estimates on the diameter.

Proposition 1. Let u N := ⌈ log N log 2 ⌉ + 1. For all N ≥ 1, all initial population X N 0 ∈ C N , and all n ≥ u N , d(X N n ) is stochastically dominated by u N × (m (2)
Nm

N ), where m N as the minimum of the 2N u N random walk steps performed by the system between times nu N and n.

Consider first the possibility that min

X N k < y + (k -n + u N )m (1)
N for all k ∈ [[n+1-u N , n]]. Since all the random walk steps that are performed during branching steps are ≥ m

(1)
N , this implies that all the particles descended by branching from a particle located at y at time nu N , are preserved by the successive selection steps performed from X N n-u N to X N n . Since there are at least 2 u N > N such particles at time n, this is a contradiction. As a consequence, we know that there must be an

index k ∈ [[n+1-u N , n]] such that min X N k ≥ y +(k-n+u N )m (1)
N . Again by the fact that random walk steps are ≥ m

(1) N , t → min X N t -(t-n+u N )m (1)
N is non-decreasing on the interval [[n + 1u N , n]], so we deduce that min

X N n ≥ y + u N m (1)
N . Now, let m

N denote the maximum of the 2N u N random walk steps that are performed at the branching steps between time nu N and time n. We see from the definition of y that max

X N n ≤ y + u N m (2)
N . We have also just seen that min

X N n ≥ y + u N m (1)
N , so that d(X

N n ) = max X N n -min X N n ≤ u N (m (2)
Nm

N ).

The following corollary is then a rather straightforward consequence, in view of Assumptions (A1) and (A2).

Corollary 1. For all N ≥ 1 and any initial population

X N 0 ∈ C N , lim n→+∞ n -1 d(X N n ) = 0
, both with probability one and in L 1 (P).

Proof. Using the notations of Proposition 1, let

F N := m (2) N -m (1)
N . From Assumptions (A1) and (A2), one deduces that E(F N ) < +∞. Then, by Proposition 1, one has that, for all n ≥ u N , E(n -1 d(X N n )) ≤ E(F N )/n, so that convergence to 0 in L 1 (P) is proved. Moreover, for any ι > 0, Proposition 1 yields that

n≥u N P(n -1 d(X N n ) ≥ ι) ≤ n≥u N P (F N ≥ ιn) ≤ E(F N )/ι
, so that convergence to 0 P-a.s. follows from the Borel-Cantelli lemma, since ι can be taken arbitrarily small.

Monotonicity properties.

The following lemma states a key monotonicity property of our branching-selection mechanism.

Lemma 1. For all 1 ≤ N 1 ≤ N 2 , and µ 1 ∈ C N 1 , µ 2 ∈ C N 2 such that µ 1 ≺ µ 2 , there exists a pair of random variables (Z 1 , Z 2 ) taking values in C N 1 × C N 2 , such that:
• the distribution of Z i for i = 1, 2 is that of the population of particles obtained by performing one branching-selection step (with N i particles) starting from the population µ i ;

• with probability one, Z 1 ≺ Z 2 . Proof. Consider an i.i.d. family (ε i,j ) i∈[[1,N 2 ]], j=1,2 with common distribution p. For k = 1, 2, write µ k = N k i=1 δ x i (k) , with x 1 (k) ≥ . . . ≥ x N k (k). Then let T k := N k i=1 j=1,2 δ x i (k)+ε i,j
, and define Z k as being formed by the N k rightmost particles in T k . From the assumption that µ 1 ≺ µ 2 , we deduce that x i (1)

≤ x i (2) for all i ∈ [[1, N 1 ]], whence the fact that x i (1) + ε i,j ≤ x i (2) + ε i,j , for all 1 ≤ i ≤ N 1 and j = 1, 2. It is easy to deduce that T 1 ≺ T 2 , whence Z 1 ≺ Z 2 . The conclusion follows.
An immediate corollary is the following.

Corollary 2. For all 1 ≤ N 1 ≤ N 2 , and µ 1 ∈ C N 1 , µ 2 ∈ C N 2 such that µ 1 ≺ µ 2 , there exists a coupling (Z 1 n , Z 2 n ) n≥0
between two versions of the branching-selection particle system, with N 1 and N 2 particles respectively, such that

Z 1 0 := µ 1 , Z 2 0 := µ 2 , and Z 1 n ≺ Z 2
n for all n ≥ 0. Proposition 2. There exists v N (p) ∈ R such that, with probability one, and in L 1 (P), for any initial population

X N 0 ∈ C N , lim n→+∞ n -1 min X N n = lim n→+∞ n -1 max X N n = v N (p).
Proof. Note that, in view of Corollary 1, if either of the two limits in the above statement exists, then the other must exist too and have the same value. Moreover, owing to the translation invariance of our particle system (the dynamics is invariant with respect to shifting all the particles by a translation on R), and to Corollary 2, we see that it is enough to prove the result when X N 0 = N δ 0 . The idea of the proof is to invoke Kingman's subadditive ergodic theorem (see e.g. [START_REF] Durrett | Probability: theory and examples[END_REF]), using the monotonicity property described by Lemma 1.

Consider an i.i.d. family (ε ℓ,i,j ) ℓ≥0,i∈[[1,N ]], j=1,2 with common distribution p (the index ℓ will be used to shift the origin of time when applying Kingman's theorem). For all ℓ ≥ 0, denote by (W N ℓ,k ) k≥0 the branching-selection system starting at W N ℓ,0 := N δ 0 and governed by the following steps. For k ≥ 0, write

W N ℓ,k = N i=1 δ x i , with x 1 ≥ . . . ≥ x N . The population T ℓ,k derived from W N ℓ,k by branching is then defined by T ℓ,k := (i,j)∈[[1,N ]]×{1,2} δ x i +ε ℓ+k,i,j . Then, W N ℓ,k+1
is obtained from T ℓ,k by keeping only the N rightmost particles.

Observe that (W N 0,n ) n≥0 has the same distribution as (X N n ) n≥0 . Moreover, the argument used in the proof of Lemma 1 shows that [START_REF] Brunet | Effect of selection on ancestry: an exactly soluble case and its phenomenological generalization[END_REF] for all n, m ≥ 0, max

W N 0,n+m ≤ max W N 0,n + max W N n,m
. Indeed, it is enough to note that (5) compares the maximum of two populations obtained by performing m branching-selection steps coupled as in Lemma 1, starting respectively from W N 0,n (for the l.h.s.) and from N δ max W N 0,n (for the r.h.s.).

Moreover, it is easily seen from the definition that, for each d ≥ 1, the random variables (W N dn,d ) n≥0 form an i.i.d. family, and that the distribution of (W N ℓ,k ) k≥0 clearly does not depend on ℓ. One can then check from the definition that the following inequality holds max

W N 0,n ≤ n-1 k=0 (i,j)∈[[1,N ]]×{1,2} |ε ℓ+k,i,j |.
Using assumptions (A1) and (A2), it is then quite clear that there exists ψ > -∞ such that, for all n ≥ 0, ψn ≤ E(W N 0,n ) < +∞. We conclude that the hypotheses of Kingman's subadditive ergodic theorem hold (see e.g. [START_REF] Durrett | Probability: theory and examples[END_REF]), and deduce that lim n→+∞ n -1 max X N n exists both a.s. and in L 1 (P), and is constant.

Proposition 3. The sequence (v N (p)) N ≥1 is non-decreasing.
Proof. Consequence of the fact that, when N 1 ≤ N 2 , N 1 δ 0 ≺ N 2 δ 0 , and of the monotonic coupling property given in Corollary 2.

We can deduce from the above proposition that there exists v ∞ (p) such that lim

N →+∞ v N (p) = v ∞ (p). A consequence of the proof of Theorem 1 below is that v ∞ (p) is in fact equal to the number v(p) := Λ ′ (t * )
, which is finite from our assumptions on p.

3.3.

Coupling with a family of N branching random walks. Let (BRW i ) i∈[[1,N ]] , denote N independent copies of a branching random walk BRW as defined in Section 2. Each BRW i thus consists of a binary tree T i and a map Φ i . For 1 ≤ i ≤ N , and n ≥ 0, remember that T i (n) denotes the set of vertices of T i located at depth n, and define the disjoint union

T N n := T 1 (n) ⊔ • • • ⊔ T N (n).
For every n, fix an a priori (i.e. depending only on the tree structure, not on the random walk values) total order on T N n . We now define by induction a sequence (G N n ) n≥0 such that, for each n ≥ 0, G N n is a random subset of T N n with exactly N elements. First, set G N 0 := T N 0 . Then, given n ≥ 0 and G N n , let H N n denote the subset of T N n+1 formed by the children (each with respect to the tree structure it belongs to) of the vertices in G N n . Then, define G N n+1 as the subset of H N n formed by the N vertices that are associated with the largest values of the underlying random walks Φ i s (breaking ties by using the a priori order on T N n ). Now let X N n denote the (random) empirical distribution describing the values taken by the Φ i s on the (random) set of vertices G N n . The sequence (X N n ) n≥0 has the same distribution as (X N n ) n≥0 , when started from X N 0 := N δ 0 . Thus, we can take for our reference probability space (Ω, F, P) the one on which BRW 1 , . . . , BRW N are defined, and let X N n be equal to the empirical distribution associated with the subset G N n , and so obtain a coupling between (X N n ) n≥0 (with X N n = N δ 0 ) and the N branching random walks BRW 1 , . . . , BRW N .

Results on the branching random walk killed below a linear space-time barrier

Let us start with the following definition, adapted from [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF]. Given v ∈ R and m ≥ 1, we say that a vertex u ∈ BRW is (m, v)-good if there exists a finite descending path u =:

u 0 , u 1 , . . . , u m such that Φ(u i ) -Φ(u 0 ) ≥ vi for all i ∈ [[0, m]].
Similarly, we say that u is (∞, v)-good if there exists an infinite descending path u =:

u 0 , u 1 , . . . such that Φ(u i ) -Φ(u 0 ) ≥ vi for all i ∈ [[0, +∞[[.
With this terminology, the main result in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] can be stated as follows, remembering that v(p) = Λ ′ (t * ) and χ(p) = π 2 2 t * Λ ′′ (t * ). Theorem 2. (Theorem 1.2 in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF]) Let ρ(∞, ǫ) denote the probability that the root of BRW is (∞, v(p)ǫ)-good. Then, as ǫ goes to zero,

ρ(∞, ǫ) = exp - χ(p) + o(1) ǫ 1/2 .
We shall need a result which, although not stated explicitly in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF], appears there as an intermediate step in a proof. [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF]) Let ρ(m, ǫ) denote the probability that the root of BRW is (m, v(p)ǫ)-good. For any 0 < β < χ(p), there exists θ > 0 such that, for all large m,

Theorem 3. (Proof of the upper bound part of Theorem 1.2 in

ρ(m, ǫ) ≤ exp - χ(p) -β ǫ 1/2
, with ǫ := θ/m 2/3 .

One should also consult the papers [START_REF] Derrida | The survival probability of a branching random walk in presence of an absorbing wall[END_REF][START_REF] Simon | Quasi-stationary regime of a branching random walk in presence of an absorbing wall[END_REF] for an approach of these results based on (mathematically non-rigorous) theoretical physics arguments. See also the discussion in Section 8.

The lower bound

The arguments used here in the proof of the lower bound, combine ideas from the paper [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF] by Pemantle, which deals with the closely related question of obtaining complexity bounds for algorithms that seek near optimal paths in branching random walks, and the estimate on ρ(m, ǫ) from the paper [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF], by Gantert, Hu and Shi. In fact, the proof given below is basically a rewriting of the proof of the lower complexity bound in [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF] in the special case of algorithms that do not jump, with the following slight differences: we are dealing with N independent branching random walks being explored in parallel, rather than with a single branching random walk; we consider possibly unbounded random walk steps; we use the estimate in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] instead of the cruder one derived in [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF].

We start with an elementary result adapted from [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF].

Lemma 2. (Adapted from Lemma 5.2 in [16].) Let v 1 , v 2 ∈ R be such that v 1 < v 2 , n ≥ 1, m ∈ [[1, n]
], K > 0, and let 0 =: x 0 , . . . , x n be a sequence of real numbers such that x i+1 -

x i ≤ K for all i ∈ [[0, n -1]]. Let I := {i ∈ [[0, n -m]]; x j -x i ≥ v 1 (j -i) for all j ∈ [[i, i + m]]}. If x n ≥ v 2 n, then #I ≥ v 2 -v 1 K-v 1 n m -K/(K -v 1
). Since Lemma 2 admits so short a proof, we give it below for the sake of completeness, even though it is quite similar to that in [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF].

Proof of Lemma 2. (Adapted from [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF].) Consider a sequence 0 =: x 0 , . . . , x n as in the statement of the lemma. Let then τ 0 := 0, and, given τ i ≤ n, define inductively

τ i+1 := inf{j ∈ [[τ i + 1, n]]; x j < x τ i + v 1 (j -τ i ) or j = τ i + m}, with the convention that inf ∅ = n + 1. Now "color" the integers k ∈ [[0, n -1]
], according to the following rules: if x τ i+1 ≥ x τ i + v 1 (τ i+1τ i ) and τ i+1 ≤ n, then τ i , . . . , τ i+1 -1 are colored red. Note that this yields a segment of m consecutive red terms, and that τ i then belongs to I. Then color in blue the remaining integers in [[0, n -1]].

Let V red (resp. V blue ) denote the number of red (resp. blue) terms in [[0, n -1]]. Then decompose the value of x n into the contributions of the steps x k+1x k such that k is red, and such that k is blue, respectively. On the one hand, the contribution of red terms is ≤ KV red . On the other hand, the contribution of blue terms is ≤ V blue × v 1 + Km, where the m is added to take into account a possible last segment colored in blue only because it has reached the index n. Writing that

n = V red + V blue , we deduce that v 2 n ≤ KV red + v 1 (n -V red ) + Km, so that V red ≥ v 2 -v 1 K-v 1 n -Km/(K -v 1 )
. Then use the fact that at least V red /m terms belong to I.

In [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF], the result corresponding to our Lemma 2, and an estimate of the type given by Theorem 3, are used in combination with an elaborate second moment argument. In the present context, the following first moment argument turns out to be sufficient.

Proof of the lower bound part of Theorem 1. Assume that X N 0 = N δ 0 . Let β > 0 and θ > 0 be as in Theorem 3. Then let λ > 0, and define

m := θ 3/2 (1 + λ)(log N ) (χ(p) -β) 1/2 3
, and ǫ := θ/m 2/3 , so that, by Theorem 3, Let also n := ⌊N ξ ⌋ for some 0 < ξ < λ. Now consider κ > 0, and let K := κ log(2N n). Consider the maximum of the random walk steps performed during the branching steps of (X N k ) k≥0 between time 0 and time n. There are 2N n such steps, so that, by assumption (A2), there exists a value of κ such that the probability that this maximum is larger than or equal to K is less than (2N n) -2008 for all large enough N . Now denote by B n the number of vertices in

G N 0 ∪ • • • ∪ G N n (see Section 3.
3) that are (m, v(p)-ǫ)-good (each with respect to the BRW i it belongs to). Observe that, with our definitions, for N large enough,

v 2 -v 1 K-v 1 n m -K/(K -v 1 ) > 0.
As a consequence, using Lemma 2, we see that, for N large enough, the event max X N n ≥ v 2 n implies that either there exists a random walk step between time 0 and n which is ≥ K, or B n ≥ 1. Using the union bound and the above estimate, we deduce that [START_REF] Brunet | Microscopic models of traveling wave equations[END_REF] P max

X N n ≥ v 2 n ≤ (2N n) -2008 + P(B n ≥ 1
). On the other hand, B n can be written as [START_REF] Brunet | Effect of microscopic noise on front propagation[END_REF] B n :=

u∈T 1 ∪•••∪T N 1( u is (m, v(p) -ǫ)-good)1(u ∈ G N 0 ∪ • • • ∪ G N n ).
Now observe that, by definition, for a vertex u at depth ℓ, the event u

∈ G N 0 ∪ • • • ∪ G N
n is measurable with respect to the random walk increments performed at depth at most ℓ, that is, the family of random variables Φ i (w) -Φ i (v), where i ∈ [[1, N ]], v, w ∈ T i , w is a child of v (with respect to the tree structure of T i ), and w, v are both located at a depth ≤ ℓ in T i . On the other hand, the event that u is (m, v(p)ǫ)-good is measurable with respect to the random walk increments performed at depth at least ℓ, that is, the family of random variables Φ i (w) -Φ i (v), where i ∈ [[1, N ]], v, w ∈ T i , w is a child of v, and w, v are both located at a depth ≥ ℓ in T i .

As a consequence, the two events {u ∈

G N 0 ∪• • •∪G N n } and {u is (m, v(p) -ǫ)-good} are independent. Since the total number of vertices in G N 0 ∪ • • • ∪ G N n is equal to N (n + 1)
, we deduce from ( 6) and ( 8) that E (B n ) ≤ N (n + 1)N -(1+λ) . Using Markov's inequality, we finally deduce from ( 7) that ( 9)

P(max X N n ≥ v 2 n) ≤ (2N n) -2008 + (n + 1)N -λ .
Now start with the obvious inequality, valid for all t, exp(t max

X N n ) ≤ N i=1 u∈T i (n) exp(tΦ i (u)).
Taking expectations, we deduce that E(exp(t max X N n )) ≤ N 2 n exp(nΛ(t)). Using the definition of t * and v(p), we then obtain that [START_REF] Derrida | The survival probability of a branching random walk in presence of an absorbing wall[END_REF] E(exp(t * (max

X N n -v(p)n)) ≤ N.
Using [START_REF] Derrida | The survival probability of a branching random walk in presence of an absorbing wall[END_REF], we deduce that1 , for all b > 0, and all large enough n,

(11) E max X N n 1(max X N n ≥ (v(p) + b)n) ≤ N exp -2007 2008 t * bn (1 + |v(p)|n).
Now observe that, by definition, E(n -1 max X N n ) is bounded above by

v 2 + (v(p) + b)P(max X N n ≥ v 2 n) + n -1 E max X N n 1(max X N n ≥ (v(p) + b)n) .
Choosing a b > 0 , we deduce from ( 9), [START_REF] Dumortier | The critical wave speed for the Fisher-Kolmogorov-Petrowskii-Piscounov equation with cut-off[END_REF], and the definition of v 2 , that, for all large enough N ,

E(n -1 max X N n ) ≤ (v(p) -(1 -γ)ǫ) + o((log N ) -2 ).
Using subadditivity (see the proof of Proposition 2), we have that v N (p) ≤ E(n -1 max X N n ), and we easily deduce that

v N (p) ≤ (v(p) -(1 -γ)ǫ) + o((log N ) -2 ).
Now remember that, as N goes to infinity, ǫ ∼ χ(p)-β (1+λ) 2 (log N ) -2 . Since the above estimates are true for arbitrarily small β, λ and γ, the conclusion follows.

The upper bound

The proof of the upper bound on v ∞ (p)v N (p) given in [START_REF] Bérard | An example of Brunet-Derrida behavior for a branching-selection particle system on Z[END_REF] was in some sense a rigorous version of the heuristic argument of Brunet and Derrida according to which we should compare the behavior of the particle system with N particles, to a version of the infinite population limit dynamics suitably modified by a cutoff. The proof given here relies upon a direct comparison with branching random walks, using the fact that, above the threshold induced by the selection steps, the behavior of our branching-selection particle system is exactly that of a branching random walk.

Consider 0 < λ < 1 and let ǫ :=

χ(p) ((1-λ) log N ) 2 .
With this choice of ǫ, as N goes to infinity, Theorem 2 yields that [START_REF] Durrett | Probability: theory and examples[END_REF] ρ(∞, ǫ) = N -(1-λ)+o (1) .

Let us now quote the following result, which is a consequence of Theorem 2 Section 6 Chapter 1 in [START_REF] Athreya | Branching processes[END_REF]. Lemma 3. Let (M n ) n≥0 denote the population size of a supercritical Galton-Watson process with square-integrable offspring distribution started with M 0 = 1. Then there exist r > 0 and φ > 1 such that, for all n ≥ 0,

P (M n ≥ φ n ) ≥ r.
Let R be such that R < v(p) and p([R, +∞)) ≥ 2/3. Consider a Galton-Watson tree whose offspring distribution is a binomial with parameters 2 and p([R, +∞)). The average number of offspring is thus equal to 2p([R, +∞)) ≥ 4/3 > 1 with our assumptions. In the sequel, we use the notations r and φ to denote the numbers given by Lemma 3 when we use this offspring distribution. Now, let s N := ⌈ log N log φ ⌉ + 1, consider 0 < η < 1, and define m := ⌈ (v(p)-R)s N ηǫ ⌉ and n := m + s N . Let u denote a vertex at depth m in a branching random walk BRW, and assume that Φ(u) ≥ (v(p)-ǫ)m. Consider the probability that, conditional upon the values of Φ on the vertices located at depth at most m, there are at least φ s N distinct descending paths u =: u m , . . . , u n starting at u and satisfying u i+1u i ≥ R for all i ∈ [[m, n -1]]. Lemma 3 above shows that this probability is ≥ r. Moreover, with our definition of m and n, and our assumption on the value of Φ(u), any such descending path has the property that Φ(u

i ) ≥ (v(p) -ǫ(1 + η))i for all i ∈ [[m, n]].
We conclude that the probability that there exist at least φ s N distinct descending paths of the form root = u 0 , . . . , u n such that Φ(u

i ) ≥ (v(p) -ǫ(1 + η))i for all i ∈ [[0, n]], is ≥ ρ(m, ǫ)r.
Now define A as the event that, for all j ∈ [[1, N ]], BRW j does not contain more than φ s N distinct descending paths of the form root = u 0 , . . . , u n such that Φ

j (u i ) ≥ (v(p) -ǫ(1 + η))i for all i ∈ [[0, n]].
Using the fact that BRW 1 , . . . , BRW N are independent and the above discussion, we see that

P(A) ≤ [1 -ρ(m, ǫ)r] N .
Using [START_REF] Durrett | Probability: theory and examples[END_REF], the obvious inequality ρ(m, ǫ) ≥ ρ(∞, ǫ), and the fact that 1x ≤ exp(-x) for all x, we deduce that (13) P(A) ≤ exp(-N λ+o (1) ).

Let δ := ǫ(1 + η). Define the event B := {min(X N k ) < (v(p)δ)k for all k ∈ [[1, n]]}, and assume that B ∩ A c occurs. From the definition of the selection mechanism, we conclude that there must be at least φ s N distinct vertices in the set G N n , which is a contradiction since φ s N > N . As a consequence, B ∩ A c = ∅, so that B ⊂ A.

From ( 13), we thus obtain that ( 14) P(B) ≤ exp(-N λ+o (1) ).

To exploit this bound, we use the following result.

Proposition 4. With the previous notations, for all N large enough,

v N (p) ≥ (v(p) -δ) -|v(p) -δ|nP(B) -nE(|Θ n |1(B)),
where Θ n is the minimum of 2nN i.i.d. random variables with distribution p.

Proof. We re-use the coupling construction given in the proof of Proposition 2, and assume that (X N n ) n≥0 is defined using this construction by the identity X N n := W N 0,n . Start with Γ 0 := 0 and J 0 := 0, and i := 0. Given i ≥ 0, Γ i and J i , let

L i+1 := inf{k ∈ [[1, n]]; min(W N Γ i ,k ) ≥ (v(p)-δ)k}
, with the convention that inf ∅ := n. Then let Γ i+1 := Γ i + L i+1 , and let J i+1 := J i + min(W N Γ i ,L i+1 ). Using an argument similar to the proof of Lemma 1, it is then quite easy to deduce that, a.s., [START_REF] Mueller | Effect of noise on front propagation in reaction-diffusion equations of KPP type[END_REF] for all i ≥ 0, min W N 0,Γ i ≥ J i . Observe that the sequence (Γ i+1 -Γ i ) i≥0 is i.i.d., and that the common distribution of the Γ i+1 -Γ i is that of the random variable L defined by L := inf{k ∈ [ [1, n]]; min(X N k ) ≥ (v(p)δ)k}, with the convention that inf ∅ := n. Similarly, the sequence (J i+1 -J i ) i≥0 is i.i.d., the common distribution of the J i+1 -J i being that of min X N L . From the law of large numbers and Proposition 2, we have that, a.s., lim i→+∞ i -1 min X N Γ i = v N (p)E(L), while the law of large numbers and (15) imply that lim

inf i→+∞ i -1 min X N Γ i ≥ E(min X N L ). We conclude that v N (p) ≥ E(min X N L ) E(L)
. Now, let Θ n denote the minimum of all the random walk steps performed by the branching-selection system between time 0 and n.

By definition we have that min

X N L ≥ (v(p) -δ)L1(B c ) + LΘ n 1(B), so that E(min X N L ) ≥ (v(p) -δ)(E(L) -E(L1(B))) + E(LΘ n 1(B)). Using the fact that 1 ≤ L ≤ n, we obtain that E(min X N L ) E(L) ≥ (v(p) -δ) -|v(p) -δ|nP(B) -nE(|Θ n |1(B)).

Proof of the upper bound part in Theorem 1. In view of Proposition 4, we deduce that

v N (p) ≥ (v(p) -(1 + η)ǫ)(1 -nP(B)) -nE(|Θ n |1(B)). Bounding above |Θ n |
by the sum of the absolute values of the 2nN corresponding i.i.d. variables, and using Schwarz's inequality thanks to Assumptions (A1) and (A2), we deduce that E(|Θ n |1(B)) ≤ 2nN CP(B) 1/2 for some constant C (depending only on p). From ( 14) and the definition of n, we deduce that, as N goes to infinity, nP(B) and

nE(|Θ n |1(B)) are o((log N ) -2 ), so we obtain that v N (p) ≥ v(p) - χ(p)(1 + η) (1 -λ) 2 (log N ) -2 + o((log N ) -2 ).
Since λ and η can be taken arbitrarily small in the argument leading to the above identity, the conclusion follows.

7. The Bernoulli case when 1/2 ≤ α < 1

In the Bernoulli case p = αδ 1 + (1α)δ 0 , with 1/2 ≤ α < 1, Assumption (A3) breaks down, and the behavior of the particle system turns out to be quite different from Brunet-Derrida, as stated in the following theorems. Note that, when

1/2 ≤ α < 1, v ∞ (p) = 1. Theorem 4. For α = 1/2, there exists 0 < c * (p) ≤ c * (p) < +∞ such that, for all large N , (16) c * (p)N -1 ≤ 1 -v N (p) ≤ c * (p)N -1 .
Theorem 5. For α > 1/2, there exists 0

< d * (p) ≤ d * (p) < +∞ such that, for all large N , (17) exp(-d * (p)N ) ≤ 1 -v N (p) ≤ exp(-d * (p)N ).
7.1. Lower bound when α = 1/2. It is easily checked that, for all m ≥ 0, the number of particles in the branching-selection system that are located at position m after m steps, that is, X N m (m), is stochastically dominated by the total population at the m-th generation of a family of N independent Galton-Watson trees, with offspring distribution binomial(2, 1/2). This corresponds to the critical case of Galton-Watson trees, and the probability that such a tree survives up to the m-th generation is ≤ cm -1 for some constant c > 0 and all large m. As a consequence, the union bound over the N Galton-Watson trees yields that, for large enough m, P(X N m (m) ≥ 1) ≤ cN m -1 . On the other hand, we have by definition that E max(X N m ) ≤ mP(X N m (m) ≥ 1) + (m -1)P(X N m (m) = 0). Choosing m := AN , where A ≥ 1 is an integer, we deduce that, for large N ,

m -1 E max(X N m ) ≤ 1 -1 AN (1 -c/A).
Using subadditivity (see the proof of Proposition 2), we have that v N (p) ≤ E(m -1 max X N m ). The lower bound in [START_REF] Pemantle | Search cost for a nearly optimal path in a binary tree[END_REF] follows by choosing A > c.

Upper bound when

α = 1/2. Given m ≥ 1, define U := inf{n ∈ [[1, m]]; X N n (n) ≤ 2N/3}, with the convention that inf ∅ := m. Observe that min X N U ≥ U -1, since, by definition, X N U -1 (U -1) ≥ 2N/3
, so that, after the branching step applied to X N U -1 , the number of particles whose positions are ≥ U -1 must be ≥ 2 × 2N/3, whence ≥ N .

Using an argument similar to the proof of Proposition 4, we deduce that

(18) v N (p) ≥ 1 - 1 E(U )
.

The lower bound in ( 16) is then a direct consequence of the following claim. Claim: for small enough ǫ > 0, with m := ⌊ǫN ⌋, there exists c(ǫ) > 0 such that E(U ) ≥ c(ǫ)N for all large N . To prove the claim, introduce for every x ∈ N the Markov chain (V x k ) k≥0 defined by the initial condition V x 0 := x, and the following transitions: given V x 0 , . . . , V x k , the next term V x k+1 is the minimum of N and of a random variable with a binomial(2V x k , 1/2) distribution. Clearly, the sequences (V N k ) k≥0 and (X N k (k)) k≥0 have the same distribution. Moreover, given two starting points x, y ∈ N such that x ≤ y, one can easily couple (V x k ) k≥0 and (V y k ) k≥0 in such a way that V x k ≤ V y k for all k ≥ 0. As a consequence, choosing x N := ⌊3N/4⌋, we see that U stochastically dominates the random variable T defined by

T := inf {n ∈ [[1, m]]; V x N n ≤ 2N/3} (again with inf ∅ := m), so that P(U = m) ≥ P (T = m).
Now let us define yet another Markov chain (Z k ) k≥0 by Z 0 := x N and the following transitions: given Z 0 , . . . , Z k , the next term Z k+1 is a random variable with a binomial(2Z k , 1/2) distribution. Clearly we can couple (Z k ) k and (V x N k ) k so that they coincide up to one unit of time before the first hitting of [[N, +∞[[. As a consequence, the two events

A 1 := {sup k∈[[0,m]] |V x N k -⌊3N/4⌋| < N/16} and A 2 := {sup k∈[[0,m]] |Z k -⌊3N/4⌋| < N/16}
have the same probability. Observing that (Z k ) k≥0 is a martingale, we can use Doob's maximal inequality to prove that

P (A c 1 ) = P (A c 2 ) ≤ E(Z m -⌊3N/4⌋) 2 (N/16) -2 . Then, it is easily checked from the definition that E(Z 2 k+1 |Z k ) = Z 2 k + Z k /2
for all k ≥ 0, and, using again the fact that (Z k ) k≥0 is a martingale, we deduce that E(Z m -⌊3N/4⌋) 2 ≤ mN/2. As a consequence, we see that, choosing ǫ > 0 small enough, we can ensure that P (A c 1 ) ≤ 1/2008 for all large N . Since, by definition, A 1 implies that T = m, we finally deduce that, for such an ǫ, and all N large enough, we have that P(U = m) ≥ P (T = m) ≥ 2007/2008. The conclusion follows. 7.3. Upper and lower bound when 1/2 < α < 1. As for the lower bound, observe that the probability that all the 2N particles generated during a branching step remain at the position from which they originated is (1-α) 2N , so that E(max

X N n ) ≤ n(1 -(1 -α) 2N
). As for the upper bound, observe that, starting from N particles at a site, the number of particles generated from these during a branching step and that perform +1 random walk steps has a binomial(2N, α) distribution, whose expectation is 2αN , with 2α > 1. Using a standard large deviations bound for binomial random variables, we see that the probability for this number to be less than N is ≤ exp(-cN ) for some c > 0. Using superadditivity E(min X N n ) (derived in exactly the same way as the subadditivity property of E(max X N n ), see the proof of Proposition 2), it is easy to deduce that E(min

X N n ) ≥ n(1 -exp(-cN ))
. The result follows.

Discussion

This section contains a discussion whose goal is to provide a self-contained qualitative explanation of the (log N ) -2 order of magnitude appearing in Theorem 1. Most of the discussion consists in explaining the ǫ -1/2 scaling of log ρ(∞, ǫ), and of log ρ(m, ǫ) when m ∝ ǫ -3/2 , in a way that is (hopefully) less technically demanding than the proofs presented in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF], although we follow the proof strategy of [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF] rather closely. Note that the discussion here deals mostly with the order of magnitude of terms, not with the precise value of the constants as in [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF]. For the sake of readability, some of the arguments are only discussed in a quite informal way. 8.1. Asymptotic behavior of ρ(∞, ǫ) and ρ(m, ǫ).

8.1.1. Connection between ρ(∞, ǫ) and ρ(m, ǫ). A first remark is that the asymptotic behavior of ρ(∞, ǫ) can be connected with that of quantities of the form ρ(m, ǫ) under appropriate conditions. One obvious inequality, valid for all m ≥ 0, is the following

(19) ρ(m, ǫ) ≥ ρ(∞, ǫ).
In the reverse direction, we have the following.

Proposition 5. There exist R < v(p) -1, φ > 1, r > 0 and c > 0, depending only on p, such that, for all m ≥ 0, and all 0 < ǫ < 1, the condition

(20) φ q ρ(m, (1 -α)ǫ) ≥ c
implies that the following inequality holds

(21) ρ(∞, ǫ) ≥ r 2 ρ(m, (1 -α)ǫ),
where α and ǫ are arbitrary numbers satisfying 0 < α < 1 and ǫ > 0, and

q := αǫm v(p) -ǫ -R .
The proof of the above proposition uses the following elementary lemma. Proof of Lemma 4. Let g(s) := +∞ k=0 Q(k)s k for s ∈ [0, 1[. By coupling, it is enough to prove the result under the additional assumption that only the values 0 and a have non-zero probability with respect to Q, so we may assume that g(s) = 1-Q(a)+s a Q(a). Since aQ(a) > 1, we have a super-critical Galton-Watson process, and, from standard theory, we know that the extinction probability d of the process is the unique solution in [0, 1[ of the equation g(d) = d, with g(s) > s for s ∈]0, d[ and g(s) < s for s ∈]d, 1[. Our assumption that a × Q(a) ≥ 2 log 2 easily yields the fact that g(1 -Q(a)/2) ≤ 1 -Q(a)/2, whence the fact that d must be ≤ 1 -Q(a)/2. The result follows.

Proof of Proposition 5. Consider the values of R, φ, r defined in Section 6, in the argument following Lemma 3. Then consider a descending path root = u 0 , . . . , u m+q ∈ T such that Φ(u

i ) ≥ (v(p) -(1 -α)ǫ)i for all i ∈ [[0, m]], and Φ(u i+1 ) -Φ(u i ) ≥ R for all i ∈ [[m, m + q -1]]. We see from the definition of q that Φ(u i ) ≥ (v(p) -ǫ)i for all i ∈ [[0, m + q]].
We now define a Galton-Watson branching process of vertices of T in which, for all n, the n-th generation of the process is formed by vertices in T((m + q)n). First, the zero-th generation of the process is formed by the root of T. Then, given a vertex x ∈ T((m+q)n) belonging to the n-th generation of the process, the offspring of this vertex in the branching process is formed by all the endpoints y of descending paths x =: u 0 , . . . , u m+q := y in T such that Φ(u i )-Φ(u 0 ) ≥ (v(p)-ǫ)i for all i ∈ [[0, m+q]]. From the definition of the branching mechanism of BRW, we see that we have defined a Galton-Watson branching process. Now, re-doing the argument following Lemma 3 in Section 6, we see that the offspring distribution of this branching process gives at least φ q children with probability at least ρ(m, (1α)ǫ)r. On the other hand, the definition of our branching process shows that if it never goes extinct, the root of T is (∞, v(p)ǫ)-good. As a consequence, the survival probability of our process is a lower bound for ρ(∞, ǫ). The result then follows from Lemma 4, choosing c > (2 log 2)/r.

We conclude this section by the following remark: using the above results, it is possible to deduce the conclusion of Theorem 3 from the conclusion of Theorem 2. In [START_REF] Gantert | Asymptotics for the survival probability in a supercritical branching random walk[END_REF], Theorem 3 is in fact an intermediate step in the proof of Theorem 2, so our remark does not lead to an alternative way of proving Theorem 3 from first principles. However, its interest is to show that, as soon as ǫ 1/2 log ρ(∞, ǫ) converges to some limit, this limit can be approached arbitrarily closely by expressions of the form ǫ 1/2 log ρ(m, ǫ), with ǫ = θ/m 2/3 for some large enough constant θ.

Proof of Theorem 3 from the conclusion of Theorem 2. Let 0 < α < 1, θ > 0 and m ≥ 1. Set ǫ := θ/m 2/3 . Let R, φ, r, c, q be defined as in the statement of Proposition 5. As m goes to infinity, we have that log φ q ∼ θα log(φ)(v(p) -R) -1 m 1/3 , and, by Theorem 2, log ρ(∞, (1α)ǫ) ∼ -χ(p) 1/2 θ -1/2 (1α) -1/2 m 1/3 . Therefore, provided that θ has been chosen large enough, Inequality (20) holds for large enough m. Given such θ and m, Proposition 5 and Theorem 2 yield that

ρ(m, (1 -α)ǫ) ≤ (2/r)ρ(∞, ǫ) = (2/r) exp - χ(p) + o(1) ǫ 1/2
.

Setting ǫ := (1α)θm -2/3 , one obtains that

ρ(m, ǫ) ≤ exp - χ(p)(1 -α) + o(1) ǫ 1/2
.

Since α can be chosen arbitrarily small, the conclusion follows.

8.1.2. Strategy and results. Given the results of the previous section, the strategy consists in studying the order of magnitude of log ρ(m, ǫ), when m has the scaling form m ∝ ǫ -u for some u > 0, seeking a value of u such that (20) is satisfied. We shall see that log ρ(m, ǫ) ∝ ǫ -h(u) , with h(u) = u/3 for all 0 < u ≤ 3/2, while the integer q in Proposition 5 satisfies q ∝ ǫ -(u-1) for all u > 1. For u * := 3/2, the identity h(u * ) = u * -1 holds, so that q and log ρ(m, (1α)ǫ) have the same order of magnitude and (20) can be satisfied. Then (19) and (21) imply that log ρ(∞, ǫ) ∝ -ǫ -h(u * ) = -ǫ -1/2 , and (using the fact that h is non-decreasing), h(u) = h(u * ) for all u ≥ u * . Thus, the ǫ -1/2 scaling exponent is "explained" by 3/2 being the solution of the equation h(u * ) = u * -1. We deduce from these results the existence of two distinct regimes for ρ(m, ǫ) with m ∝ ǫ -u :

• when 0 < u ≤ 3/2, log(ρ(m, ǫ)) ∝ -m 1/3 ; • when u ≥ 3/2, log(ρ(m, ǫ)) ∝ log(ρ(∞, ǫ)) ∝ -ǫ -1/2 . 8.1.3. Asymptotics of log ρ(m, ǫ) with m ∝ ǫ -u , 0 < u < 3/2.
Let us now explain how to compute h(u), and assume throughout this section that m ∝ ǫ -u , whence ǫm ∝ ǫ 1-u . A key idea is to perform a change of measure, replacing the step distribution p of the BRW by the distribution p defined by (see Section 1.2)

dp dp (x) := exp (t * x) exp(Λ(t * )) .
The mean value of a step with respect to p is now equal to v(p), and, if (S k ) k≥0 denotes a random walk started at S 0 := 0, with i.i.d. increments whose common distribution is p with respect to a probability measure P , and p with respect to a probability measure P , the following identity holds for all k:

(22) 2 k P [(S 0 , . . . , S k ) ∈ •] = Ẽ e -t * (S k -v(p)k) 1(S 0 , . . . , S k ) ∈ • ,
where Ẽ denotes expectation with respect to P . The raison d'être of Assumption (A3) is to allow for such a change of measure. Remember that ρ(m, ǫ) is the probability that at least one descending path root =: u 0 , u 1 , . . . , u m exists in T such that

(23) for all i ∈ [[0, m]], Φ(u i ) ≥ (v(p) -ǫ)i.
Observe that, for such a path, either

(24) for all i ∈ [[0, m]], Φ(u i ) ≤ v(p)i + ǫ -u/3 , or (25) there exists i ∈ [[0, m]] such that Φ(u i ) > v(p)i + ǫ -u/3 .
Denoting by Ξ m the (random) number of descending paths satisfying (23) and ( 24), and by ∆ m the number of those satisfying (23) and (25), we see that

ρ(m, ǫ) = Q({Ξ m ≥ 1} ∪ {∆ m ≥ 1}), so that, obviously, (26)
Q(Ξ m ≥ 1) ≤ ρ(m, ǫ) ≤ E(Ξ m ) + Q(∆ m ≥ 1). By definition, E(Ξ m ) = 2 m P ( for all i ∈ [[0, m]], v(p)i -ǫi ≤ S i ≤ v(p)i + ǫ -u/3
), which rewrites, using (22), as

Ẽ e -t * (Sm-v(p)m) 1( for all i ∈ [[0, m]], v(p)i -ǫi ≤ S i ≤ v(p)i + ǫ -u/3 ) . (27)
Since the only paths that contribute to the above expectation have

v(p)m -ǫm ≤ S m ≤ v(p)m + ǫ -u/3 , we see that (28) E(Ξ m ) ≤ e t * ǫm P for all i ∈ [[0, m]], v(p)i -ǫi ≤ S i ≤ v(p)i + ǫ -u/3 . and (29) E(Ξ m ) ≥ e -t * ǫ -u/3 P for all i ∈ [[0, m]], v(p)i -ǫi ≤ S i ≤ v(p)i + ǫ -u/3 .
Now observe that, under P , (S k -v(p)k) k≥0 is a random walk with centered squareintegrable increments. Moreover, (ǫ -u/3 ) 2 << m since u > 0, and, ǫ -u/3 >> ǫm as soon as u < 3/2. As a consequence, the usual Brownian scaling for random walks yields that when 0 < u < 3/2, (30

) log P ∀i ∈ [[0, m]], v(p)i -ǫi ≤ S i ≤ v(p)i + ǫ -u/3 ∝ - ǫ -u (ǫ -u/3 ) 2 = -ǫ -u/3 .
Since ǫ -u/3 >> ǫm when u < 3/2, we deduce from (28) and ( 29) that

(31) log E(Ξ m ) ∝ -ǫ -u/3 for 1 < u < 3/2.
As for ∆ m , the union bound yields that

Q(∆ m ≥ 1) ≤ m i=0 Q(∃x ∈ T(i); Φ(x) > v(p)i + ǫ -u/3 ), whence Q(∆ m ≥ 1) ≤ m i=0 2 i P (S i > v(p)i + ǫ -u/3 ).
For all i ∈ [[0, m]], the change of measure shows that 2 i P (S i > v(p)i + ǫ -u/3 ) = Ẽ e -t * (S i -v(p)i) 1(S i > v(p)i + ǫ -u/3 ) ≤ exp(-t * ǫ -u/3 ), so we easily deduce that

(32) -log Q(∆ m ≥ 1) is at least ∝ -ǫ -u/3 .
We conclude from (31), (32) and ( 26) that (33) log ρ(m, ǫ) is at least ∝ ǫ -u/3 for 0 < u < 3/2.

Using the same kind of argument that led to (31), but working a little more (we omit the details), it is possible to show that (34) log E(Ξ 2 m ) is at most ∝ ǫ -u/3 for 0 < u < 3/2. Then, we can use the classical second moment inequality:

Q(Ξ m > 0) ≥ E(Ξ m ) 2 E(Ξ 2 m )
, to deduce from (26), (31) and (34) that

(35) -log ρ(m, ǫ) is at most ∝ -ǫ -u/3 for 0 < u < 3/2.
As a consequence, we obtain that (36) log ρ(m, ǫ) ∝ -ǫ -u/3 for 0 < u < 3/2.

8.1.4. Asymptotics of ρ(m, ǫ) with m ∝ ǫ -u , u ≥ 3/2, and ρ(∞, ǫ). The above discussion dealt only with rough order of magnitudes (denoted by the ∝ symbol), but a more precise analysis is needed to study the competition between positive and negative terms of similar orders of magnitude when u = 3/2. For λ > 0, let m := ⌊λǫ From the monotonicity property: ρ(m, ǫ) ≥ ρ(m ′ , ǫ) when m ′ ≥ m, we deduce that λ → f + (λ) and λ → f -(λ) are non-decreasing. Similarly, from the monotonicity property ρ(m, ǫ) ≤ ρ(m, ǫ ′ ) when ǫ ≤ ǫ ′ , we deduce that λ → λ -1/3 f + (λ) and λ → λ -1/3 f -(λ) are non-increasing.

In particular, the fact that there exists some λ for which f + (λ) is finite (resp. positive) implies that f + (λ) is finite (resp. positive) for all λ > 0. The same property holds for f -. Now, rework the bounds in the previous section, replacing the ǫ -u/3 (= ǫ -1/2 since u = 3/2) terms in the definition of Ξ m and ∆ m , by λǫ -1/2 (more precision than only the order of magnitude of terms is needed in order to deal with the case u = 3/2). Consider the analog of the bound (28) in the present context, and observe that, for small ǫ, ǫm ∼ λǫ -1/2 . The Brownian scaling bound then yields the existence of a constant c > 0 such that, for small ǫ, log P ∀i ∈ [[0, m]], v(p)iǫi ≤ S i ≤ v(p)i + λǫ -1/2 ≤ -c m (λǫ -1/2 ) 2 ∼ -cλ -1 ǫ -1/2 .

For small enough λ, this term dominates the t * ǫm ∼ t * λǫ -1/2 term in the exponential, so that f -(λ) > 0. We deduce that f -(λ) > 0 for all values of λ > 0. On the other hand, it is straightforward to adapt the estimates in the previous section to show that f + (λ) < +∞ for all λ > 0. We can thus conclude that, when m ∝ ǫ -3/2 , (37) log ρ(m, ǫ) ∝ -ǫ -1/2 . Now, by Proposition 5, the asymptotic scaling log ρ(∞, ǫ) ∝ -ǫ -1/2 is a consequence of (37), provided that (20) is satisfied for u = 3/2 and, at least, large enough λ. Observe that, on the one hand, q ∼ αǫm v(p)-R ∼ αλǫ -1/2 v(p)-R . On the other hand, log ρ(m, (1α)ǫ) -f + (λ(1α) 3/2 )((1α)ǫ) -1/2 . The fact that λ → λ -1/3 f + (λ) is non-increasing and thus bounded above for large λ, implies that φ q ρ(m, (1α)ǫ) >> 1 for large enough λ, so that (20) is indeed satisfied. Indeed, since BRW 1 , . . . , BRW N are independent, ρ(∞, ǫ N ) >> 1/N would imply that, with probability close to one, at least one of the BRW i s survives killing, while ρ(∞, ǫ N ) << 1/N would imply that, with probability close to one, none of the BRW i s survives. Using the asymptotics log ρ(∞, ǫ) ∼ -χ(p) 1/2 ǫ -1/2 , it is then easily checked that (40) imposes the precise asymptotic behavior

ǫ N ∼ χ(p)(log N ) -2 .
To give an intuition of why ( 38) and (39) should be related, remember the coupling between the branching-selection particle system and BRW 1 , . . . , BRW N described in Section 3.3. If (38) holds, then, loosely speaking, v(p)ǫ is above the sustainable growth speed for a branching system with only N particles available, so the maximum of the branching-selection system should grow at a speed lower than v(p)ǫ. Conversely, if (38) holds, the population in BRW 1 , . . . , BRW N above the line with slope v(p)ǫ quickly exceeds N since the existing surviving particles quickly yield many surviving descendants. As a consequence, the threshold in the selection steps of the branching-selection system has to be above the line with slope v(p)ǫ.

A rigorous formulation of the preceding arguments is precisely what we do in Sections 5 and 6.

It should be noted that the key time scale over which we have to control the particle system to prove both the upper and the lower bound is ǫ -3/2 , with ǫ satisfying (40), that is, a time scale of order (log N ) 3 . This is the same order of magnitude as the one observed for coalescence times of the genealogical process underlying the branching-selection particle system (this question is investigated empirically and with heuristic arguments in e.g. [START_REF] Brunet | Effect of selection on ancestry: an exactly soluble case and its phenomenological generalization[END_REF]). Understanding more precisely the role of this time-scale for the dynamics of the particle system certainly deserves more investigation.

N

  are respectively the maximum and the minimum of a family of 2N u N i.i.d. random variables with common distribution p.Proof. Consider n ≥ u N , y = max X N n-u N , and let us study the evolution of the branching-selection system between times n-u N and n. Define m[START_REF] Athreya | Branching processes[END_REF]

( 6 )

 6 ρ(m, ǫ) ≤ N -(1+λ) for all large N. Then let 0 < γ < 1 and define v 2 := v(p) -(1γ)ǫ and v 1 := v(p)ǫ.

Lemma 4 .

 4 Consider a Galton-Watson process with offspring distribution Q. If there exists a ≥ 1 such that a × Q([a, +∞[) ≥ 2 log 2, then the survival probability is larger than or equal to Q([a, +∞[)/2.

- 3 / 2

 32 ⌋ andf + (λ) := lim sup ǫ→0 -ǫ 1/2 log ρ(m, ǫ), f -(λ) := lim inf ǫ→0 -ǫ 1/2 log ρ(m, ǫ).

8. 2 .

 2 Deducing the Brunet-Derrida behavior. Broadly speaking, our proof of the Brunet-Derrida behavior of branching-selection systems is based on the fact that there is a loose equivalence between the following two properties: (38) BRW 1 , . . . , BRW N do not survive killing below a line of slope vǫ, and (39) v N < vǫ. If one accepts this premise, it is then natural to expect the actual velocity shift ǫ N := v(p)v N to satisfy (40) ρ(∞, ǫ N ) ∝ 1/N.

Here are the details. Let M := max X N nv(p)n. From the fact that, for all large enough x, x ≤ exp(t * x/2008), we deduce that E(M 1(M ≥ bn)) ≤ E exp(t * M -2007

t * bn) for all large enough n. Similarly, E(v(p)n1(M ≥ bn)) ≤ |v(p)|nE exp(t * Mt * bn). The result follows from summing the two inequalities above and applying[START_REF] Derrida | The survival probability of a branching random walk in presence of an absorbing wall[END_REF].