Saleh Mousa Alzahrani
email: salzahrani@uqu.edu.sa

Xavier Antoine
email: xavier.antoine@univ-lorraine.fr

C Chniti
email: cachniti@uqu.edu.sa

A coupling between integral equations and on-surface radiation conditions for diffraction problems by non convex scatterers

published or not. The documents may come

A coupling between integral equations and on-surface radiation conditions for diffraction problems by non convex scatterers

Introduction

During the last decades, time-harmonic wave propagation has proved to be central in many engineering and technological key developments, based e.g. on acoustics, electromagnetism or elastic mechanisms. When one wants to simulate the associated boundary-value problem, one of the difficulties is related to the fact that the solution which has to be computed is set in an exterior unbounded domain Ω + defined as the complementary of a finite scatterer Ω -. Therefore, to use a standard numerical method, it is necessary to bound the computational domain. One well-known possibility is to use an absorbing boundary condition [START_REF] Antoine | Bayliss-Turkel-like radiation condition on surfaces of arbitrary shape[END_REF][START_REF] Antoine | An improved surface radiation condition for highfrequency acoustic scattering problems[END_REF][START_REF] Givoli | High-order local non-reflecting boundary conditions: a review[END_REF][START_REF] Hagstrom | Radiation boundary conditions for the numerical simulation of waves[END_REF][START_REF] Hagstrom | A new auxiliary variable formulation of high-order local radiation boundary conditions: corner compatibility conditions and extensions to first-order systems[END_REF][START_REF] Modave | Corner treatments for high-order local absorbing boundary conditions in high-frequency acoustic scattering[END_REF][START_REF] Tsynkov | Numerical solution of problems on unbounded domains. A review[END_REF] or a Perfectly Matched Layer [START_REF] Bérenger | A perfectly matched layer for the absorption of electromagnetic waves[END_REF][START_REF] Bérenger | Perfectly matched layer (PML) for computational electromagnetics[END_REF][START_REF] Bermúdez | Perfectly matched layers[END_REF][START_REF] Bermúdez | Perfectly matched layers for time-harmonic second order elliptic problems[END_REF][START_REF] Druskin | Near-optimal perfectly matched layers for indefinite Helmholtz problems[END_REF][START_REF] Turkel | Absorbing PML boundary layers for wave-like equations[END_REF] to bound the domain and then solve the resulting problem by the finite element method [START_REF] Bériot | Efficient implementation of high-order finite elements for Helmholtz problems[END_REF][START_REF] Ihlenburg | Finite Element Analysis of Acoustic Scattering[END_REF][START_REF] Solin | Higher-Order Finite Element Methods[END_REF]. Another widely used alternative is to rewrite equivalently the initial exterior PDE problem as an integral equation over the finite surface Γ of the scatterer Ω - based on the Green's function [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Antoine | Wave Propagation in Periodic Media -Analysis, Numerical Techniques and Practical Applications[END_REF][START_REF] Burton | The application of integral equation methods to the numerical solution of some exterior boundary-value problems[END_REF][START_REF] Colton | Inverse Acoustic and Electromagnetic Scattering Theory[END_REF][START_REF] Colton | Integral Equation Methods in Scattering Theory[END_REF][START_REF] Harrington | H-field, E-field and combined field solution for conducting bodies of revolution[END_REF][START_REF] Liu | Fast Multipole Boundary Element Method: Theory and Applications in Engineering[END_REF][START_REF] Martin | Multiple Scattering. Interaction of Time-Harmonic Waves with N Obstacles[END_REF][START_REF] Nédélec | Acoustic and Electromagnetic Equations[END_REF][START_REF] Thierry | Analyse et Simulations Numériques du Retournement Temporel et de la Diffraction Multiple[END_REF]. Then, this has the advantage of reducing from one the dimension of the problem. One of the main drawbacks is that, unlike the initial problem which involves partial differential operators, the integral equation is defined by construction as a nonlocal pseudodifferential operator. When a discretization technique is then applied, as the boundary element method, then the corresponding discrete version of the integral equation leads to the numerical solution of a highly indefinite complex-valued dense linear system which is particularly difficult to tackle in the high-frequency regime. Many technical aspects are then necessary to make it working correctly for some applications, for example to reduce the storage and to accelerate the solution of the linear system [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Antoine | Wave Propagation in Periodic Media -Analysis, Numerical Techniques and Practical Applications[END_REF][START_REF] Hackbusch | Hierarchical Matrices: Algorithms and Analysis[END_REF]. Various numerical methods were further developed to propose some other ways to solve, at least approximately, the initial scattering problem. One of them is the On-Surface Radiation Condition (OSRC) method introduced in [START_REF] Kriegsmann | A new formulation of electromagnetic wave scattering using an on-surface radiation boundary condition approach[END_REF] and further developed by many authors (see e.g. [START_REF] Antoine | Computational Methods for Acoustics Problems[END_REF]). Without giving too much details now, the OSRC approach also leads to solve an equation given over the surface of the scatterer, but defined through local surface partial differential operators. Therefore, after the application of the boundary element method, the linear system is highly sparse, yielding an efficient way to solve the scattering problem. The price to pay is that the method can be considered as a numerical asymptotic method, and therefore can lose some accuracy in some cases, in particular when the scatterer is not convex and includes some concave parts [START_REF] Antoine | Computational Methods for Acoustics Problems[END_REF]. The aim of this paper is to contribute to the improvement of the OSRC method for non convex obstacles by proposing a direct simple coupling between the OSRC and the surface integral equation method.

The plan of the paper is the following. In Section 2, we introduce the two-dimensional Dirichlet scattering problem and the basic informations about the integral equation representations and their numerical approximation. Section 3 presents the notion of OSRC and its numerical discretization after writing the variational formulation. Section 4 develops the coupling procedure for the Dirichlet problem. In particular, we explain how to formulate the problem and to improve its convergence properties if it is used in a Krylov solver, based on operator preconditioning. The coupling is validated in a simple two-dimensional example. The extension to the Neumann problem is shortly given in Section 5. Finally, Section 6 is a conclusion.

2 Two-dimensional scattering -integral equation formulations

The two-dimensional scattering problem

Let us consider Ω -as a scatterer with boundary Γ := Ω -. The homogeneous isotropic exterior domain of propagation is denoted by Ω + = R 2 \Ω -. For the sake of conciseness in the presentation, we first assume that the scatterer is acoustically sound-soft (i.e. Dirichlet boundary condition). Nevertheless, the case of a sound-hard scattering problem (Neumann boundary condition) is also treated shortly in Section 5. We now consider a time-harmonic incident plane wave u inc (x) = e ikθ inc •x (with x = (x 1 , x 2 ) ∈ R 2 ) illuminating Ω -, with an incidence direction θ inc = (cos(θ inc ), sin(θ inc )) for a time dependence e -iωt , setting ω as the wave pulsation and k as the wavenumber. The sound-soft scattering problem of u inc by Ω -leads to the computation of the scattered wavefield u as the solution to the boundary-value problem [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Martin | Multiple Scattering. Interaction of Time-Harmonic Waves with N Obstacles[END_REF]

     (∆ + k 2 )u = 0, in Ω + , u = -u inc , on Γ, lim ||x||→+∞ ||x|| 1/2 (∇u • x ||x|| -iku) = 0. (1)
We designate by (∆ + k 2 ) the Helmholtz operator, where ∆ = ∂ 2

x 1 + ∂ 2
x 2 is the laplacian. The gradient operator is ∇ and ||x|| = √ x • x, where x • y is the scalar product of two vectors x and y of R 2 . The last equation of ( 1) is the well-known Sommerfeld's radiation condition at infinity that ensures the uniqueness of the scattered wave field u. Finally, the outwardly directed unit normal vector to Ω -is n. A schematic representation of the problem is given in Figure 1.

Integral operators for scattering

Let us define G as the two-dimensional free-space Green's kernel

∀x, y ∈ R 2 , x = y, G(x, y) = i 4 H (1) 0 (k x -y ), (2)
where H

(1) 0

is the first-kind Hankel's function of order zero. Building an integral equation needs the Helmholtz integral representation formula [14, Theorems 3.1 and 3.3]. Proposition 1. If v is a solution to the Helmholtz equation in an unbounded domain Ω + which also satisfies the Sommerfeld radiation condition, then the following relation holds

Γ -G(x, y)∂ n v(y) + ∂ ny G(x, y)v(y) dΓ(y) = v(x) if x ∈ Ω + , 0 otherwise. (3)
In addition, let us assume that v -is solution to the Helmholtz equation in a bounded domain Ω -. One can write

Γ -G(x, y)∂ n v -(y) + ∂ ny G(x, y)v -(y) dΓ(y) = 0 if x ∈ Ω + , -v -(x) otherwise. (4)
In Proposition 1, all the integrals on Γ must be understood as duality brackets between the Sobolev space H 1/2 (Γ) and its dual space H -1/2 (Γ). Nevertheless, when the incident wavefield u inc and the curve Γ are sufficiently regular, the scattered field is smooth, implying that the duality bracket can be identified to the (non hermitian) inner product in L 2 (Γ)

f, g H -1/2 ,H 1/2 = Γ f gdΓ.
This identification is systematically used in the presentation.

Let us now introduce the volume single-and double-layer integral operators, respectively denoted by L and M , that are defined through

∀x ∈ R 2 \ Γ, L : ρ -→ L ρ(x) = Γ G(x, y)ρ(y) dΓ(y), ∀x ∈ R 2 \ Γ, M : λ -→ M λ(x) = - Γ ∂ ny G(x, y)λ(y) dΓ(y).
The wave fields v and v -(see ( 3) and ( 4)) can be expressed as

   v(x) = -L (∂ n v| Γ )(x) -M (v| Γ )(x), ∀x ∈ Ω + , v -(x) = L (∂ n v -| Γ )(x) + M (v -| Γ )(x), ∀x ∈ Ω -.
Furthermore, the single-and double-layer integral operators provide some outgoing solutions to the Helmholtz equation [START_REF] Colton | Inverse Acoustic and Electromagnetic Scattering Theory[END_REF].

Proposition 2. For any densities ρ ∈ H -1/2 (Γ) and λ ∈ H 1/2 (Γ), the functions L ρ and M λ are some outgoing solutions to the Helmholtz equation in R 2 \ Γ.

We now recall the expressions of the trace and normal derivative trace of the volume singleand double-layer potentials which are commonly called jump relations [START_REF] Colton | Inverse Acoustic and Electromagnetic Scattering Theory[END_REF]Theorem 3.1]. Proposition 3. For any x in Γ, the trace and normal derivative traces of the operators L and M are given by the following relations (the sign +/-indicates that z tends towards x from the exterior/interior of Γ)

lim z∈Ω ± →x L ρ(z) = Lρ(x), lim z∈Ω ± →x M λ(z) = ∓ 1 2 I + M λ(x), lim z∈Ω ± →x ∂ nz L ρ(z) = ∓ 1 2 I + N ρ(x), lim z∈Ω ± →x ∂ nz M λ(z) = Dλ(x), (5)
where I is the identity operator, and, for x ∈ Γ,

Lρ(x) = Γ G(x, y)ρ(y)dΓ(y), M λ(x) = - Γ ∂ ny G(x, y)λ(y)dΓ(y), N ρ(x) = Γ ∂ nx G(x, y)ρ(y)dΓ(y) = -M * ρ(x), Dλ(x) = -∂ nx Γ ∂ ny G(x, y)λ(y)dΓ(y). (6)
All along the paper, the boundary integral operators are denoted by a roman letter (e.g. L) while the volume integral operators use a calligraphic letter (e.g. L ). The operator M * = -N is the adjoint operator of M , that is

g, M f H -1/2 ,H 1/2 = -N g, f H -1/2 ,H 1/2 , ∀(f, g) ∈ H 1/2 (Γ) × H -1/2 (Γ).

Direct boundary integral equations for the Dirichlet problem

The aim of this section is to provide without any detail the standard integral equation formulations for solving the two-dimensional scattering problem with Dirichlet boundary condition that will be used later. More details can be found in [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Thierry | Analyse et Simulations Numériques du Retournement Temporel et de la Diffraction Multiple[END_REF] for the derivation and properties of these integral equations (well-posedness, existence of resonant modes,...).

A first formulation is based on the trace of the single-layer operator

Lρ = -u inc | Γ . ( 7
)
The equation is well-posed and equivalent to the exterior scattering problem (1) as soon as k is not an irregular interior frequency of the associated Dirichlet boundary-value problem [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Thierry | Analyse et Simulations Numériques du Retournement Temporel et de la Diffraction Multiple[END_REF]. This integral equation is called Electric Field Integral Equation (EFIE) in electromagnetism. In the sequel, this formulation will be denoted by Single-Layer Integral Equation (SLIE). In the case of a closed boundary Γ, which is the situation in the paper, it can be proved that the spurious internal modes do not radiate. Therefore, there is no pollution in the far-field computation, which justifies that the SLIE can be considered as a reference solution. In addition, for an open surface Γ, the SLIE is the only possible integral equation that can be written.

Another surface integral formulation is given by

( 1 2 I + N )ρ = -∂ n u inc | Γ . (8)
It is also well-posed and equivalent to the exterior scattering problem (1) if k is not an interior Neumann resonance [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Thierry | Analyse et Simulations Numériques du Retournement Temporel et de la Diffraction Multiple[END_REF]. This formulation is often designated by Magnetic Field Integral Equation (MFIE). Nevertheless, this integral equation is not recommended in practice since the spurious modes radiate and introduce some errors when computing the far-field pattern. To avoid the interior resonance problem, Burton and Miller [4,[START_REF] Burton | The application of integral equation methods to the numerical solution of some exterior boundary-value problems[END_REF][START_REF] Thierry | Analyse et Simulations Numériques du Retournement Temporel et de la Diffraction Multiple[END_REF] proposed to rather use a linear combination between the EFIE and MFIE. If α is a real-valued parameter such that 0 < α < 1 and if η is a complex parameter with (η) = 0, where (η) is the imaginary part of η, then one gets the Combined Field Integral Equation (CFIE) [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Harrington | H-field, E-field and combined field solution for conducting bodies of revolution[END_REF][START_REF] Thierry | Analyse et Simulations Numériques du Retournement Temporel et de la Diffraction Multiple[END_REF] or Burton-Miller Integral Equation (BWIE)

(1 -α)( 1 2 I + N ) + αηL ρ = -(1 -α)∂ n u inc | Γ -αηu inc | Γ . (9)
This integral equation is well-posed for any wavenumber k but can only be applied to closed surfaces. An important point is that all these integral equations are based on the single-layer represen-

tation ∀x ∈ Ω + , u(x) = L ρ(x), (10)
where the unknown surface field ρ is the physical quantity defined by the jump (set as the difference between the interior and exterior traces)

ρ = [∂ n u] Γ := -∂ n u + |Γ + ∂ n u - |Γ = -(∂ n u |Γ + ∂ n u inc |Γ ). ( 11
)
To compute the far-field pattern, let us recall that we have: u = L ρ + M λ, where ρ and λ are two unknown densities. In the polar coordinates system (r, θ), the use of asymptotic expansions when r → +∞ leads to the following relation [START_REF] Colton | Integral Equation Methods in Scattering Theory[END_REF] ∀θ

∈ [0, 2π], u(r, θ) = e ikr r 1/2 [a L (θ) + a M (θ)] + O 1 r 3/2 ,
where a L and a M are the radiated far-fields for the single-and double-layer potentials, respectively, defined for any angle θ of [0, 2π] by

       a L (θ) = 1 8 √ kπ e iπ/4 Γ e -ikθ•y ρ(y)dΓ(y), a M (θ) = 1 8 √ kπ e iπ/4 Γ - ik y θ • ye -ikθ•y λ(y)dΓ(y),
with θ := (cos(θ), sin(θ)). In addition, the Sonar Cross Section (SCS) (in dB) is such that

∀θ ∈ [0, 2π], σ(θ) = 10 log 10 (2π |a L (θ) + a M (θ)| 2 ). ( 12
)
When using the single-layer representation [START_REF] Bermúdez | Perfectly matched layers[END_REF], only a L is needed while a M is set to zero. In the paper, we will focus on the SLIE.

Numerical approximation

To numerically solve equation ( 7) (or ( 9)), we first introduce a polygonal interpolating surface Γ h which approximates Γ. The triangularization of Γ h is built by using n K segments K j . Therefore, we have Γ h = ∪ n K j=1 K j . The notation P designates the space of complex-valued polynomials of order . In (7) (or ( 9)), no derivative operator is applied to the unknown ρ. However, as seen below, the OSRC method, and the integral equation technique for the Neumann problems introduce some tangential derivatives that apply to the surface fields. For this reason, we propose to use the linear Boundary Element Method (BEM) all along the paper, where the conformal finite element space V h of P 1 piecewise continuous functions is defined by

V h := φ h ∈ C 0 (Γ h ); φ K j := φ h|K j ∈ P 1 , ∀j = 1, ..., n K .
For the Dirichlet problem, a P 0 (constant per segment) BEM could also be applied. For the numerical approximation, we use the weak form of the integral equation [START_REF] Bérenger | A perfectly matched layer for the absorption of electromagnetic waves[END_REF]. For the SLIE, this leads to ∀q ∈ L 2 (Γ),

Γ Γ G(x, y)ρ(y)q(x)dΓ(y)dΓ(x) = - Γ u inc | Γ (x)q(x)dΓ(x). (13)
Then, by using the interpolating surface Γ h and the linear approximations of both ρ and q in V h , the discrete form of (13) yields the linear system

Lρ = -Mu inc , ( 14
)
where L is the complex-valued matrix associated with the single-layer operator and M is the surface mass matrix. If n P is the number of points of the curve Γ h , then all the matrices are elements of the space M n P (C) of complex-valued matrices of size n P × n P . Indeed, assuming that Γ is a closed boundary, then the number of degrees of freedom of the linear boundary element method, i.e. the number of points n P := dim(V h ), is equal to the number of segments: n P = n K . In addition, the unknown complex-valued nodal vector ρ and the nodal incident vector u inc are in C n P . For computing the coefficients of L, some semi-analytical quadrature formula are used to integrate the kernel singularity. If one rather uses the BWIE (9), the discrete form leads to

[(1 -α)( 1 2 M + N) + αηV)]ρ = -(1 -α)M∂ n u inc -αηMu inc , (15)
where ∂ n u inc is the nodal complex-valued vector related to the normal trace of the incident field. Finally, we have

ρ = -(∂ n u + ∂ n u inc ). ( 16
)
3 Loss of accuracy of the OSRC method for non convex scatterers

First and second-order OSRCs

The On-Surface Radiation Condition (OSRC) method was introduced in the middle of the eighties by Kriegsmann, Taflove and Umashankar [START_REF] Kriegsmann | A new formulation of electromagnetic wave scattering using an on-surface radiation boundary condition approach[END_REF]. At that time, the main idea was to develop an approximate but efficient and low memory numerical solution for scattering problems, most particularly in the high-frequency regime. Starting from local approximations of the Dirichletto-Neumann (DtN) operator, they were able to propose the computation of the scattered field by two-dimensional simple obstacles. Since then, the OSRC method has received much attention from many researchers and many improvements and extensions have been proposed (see e.g. [START_REF] Antoine | Computational Methods for Acoustics Problems[END_REF]).

For the sake of conciseness, we restrict our presentation to the so-called first-and second-order Bayliss-Turkel-like radiation conditions [START_REF] Antoine | Fast approximate computation of a time-harmonic scattered field using the onsurface radiation condition method[END_REF].

The first-order OSRC (that we denote by OSRC 1 ) is given by

∂ n u 1 + (-ik + κ 2 )u 1 = 0, on Γ. (17)
In the above equation, (u 1 , ∂ n u 1 ) is the OSRC Cauchy data that approximate the exact Cauchy data (u, ∂ n u) on Γ. Here, let us remark that (u 1 , ∂ n u 1 ) must be understood as a notation since the OSRC is an approximate DtN map, which means that we do not a priori know if ∂ n u 1 is the normal derivative trace of a function u 1 . The function κ := κ(s) is the curvature at a point s of the surface, where s is the curvilinear abscissa counterclockwise directed along Γ. Equation ( 17) can be seen as a simple impedance boundary condition for the exterior domain Ω + . Various ways of deriving [START_REF] Hackbusch | Hierarchical Matrices: Algorithms and Analysis[END_REF] are available in the literature. Let us mention for example [START_REF] Antoine | Bayliss-Turkel-like radiation condition on surfaces of arbitrary shape[END_REF] were formal and rigorous approaches are developed. The first-order OSRC (17) can be improved, leading to the so-called symmetrical second-order Bayliss-Turkel condition (denoted by OSRC 2 in the sequel)

∂ n u 2 + (-ik + κ 2 - κ 2 8(κ -ik) )u 2 -∂ s ( 1 2(κ -ik) ∂ s )u 2 = 0, on Γ. (18)
In ( 18), the curvilinear derivative operator is written ∂ s u = ∇u • τ , where τ is the tangent vector to Γ (n • τ = 0). In the same spirit, an Engquist-Majda-like OSRC can be derived [START_REF] Antoine | Computational Methods for Acoustics Problems[END_REF][START_REF] Antoine | Bayliss-Turkel-like radiation condition on surfaces of arbitrary shape[END_REF]. However, some numerical simulations in various papers show that the boundary condition (18) provides a higher accuracy. Therefore, in the present paper, we restrict our study to [START_REF] Hagstrom | Radiation boundary conditions for the numerical simulation of waves[END_REF].

Numerical approximation

To solve [START_REF] Hagstrom | Radiation boundary conditions for the numerical simulation of waves[END_REF], we introduce the weak formulation

Γ ∂ n u 2 vdΓ + Γ (-ik + κ 2 - κ 2 8(κ -ik) )u 2 vdΓ + Γ 1 2(κ -ik) ∂ s u 2 ∂ s vdΓ = 0, on Γ, (19)
for some suitable test-functions v in H 1 (Γ). The pair of approximate Cauchy data (u 2 , ∂ n u 2 ) is discretized in the finite element space V h ×V h . When the BEM is introduced, then the discretization of ( 19) can be rewritten at the matrix level as

M∂ n u 2 + (M β + S α )u 2 = 0, (20)
where the functions α and β are defined for OSRC 2 by

α = 1 2(κ -ik) , β = -ik + κ 2 - κ 2 8(κ -ik)
.

The matrices S α and M β are respectively the (sparse) n P × n P generalized stiffness and mass matrices associated with the functions α and β. In addition, the vectors u 2 and ∂ n u 2 are complexvalued vector fields of C n K . Finally, the second-order OSRC method requires the following stable approximation scheme for the curvature [START_REF] Antoine | Fast approximate computation of a time-harmonic scattered field using the onsurface radiation condition method[END_REF]: let K = (a 1 a 2 a 3 ) be a triangle whose vertices a j , j = 1, 2, 3, are points on Γ h , then, the curvature at the vertex a 2 can be approximated by

κ(a 2 ) = 4 × area(K) a 1 a 2 a 3 ,
where a j , for j = 1, ..., 3, are the lengths of the edges of K ordered with respect to the increasing size. This formula is directly applied on the triangles associated with the surface mesh and built on two adjacent segments.

Since we are solving a scattering problem with given Dirichlet boundary condition, then u 2 is given by -u inc and then

M∂ n u 2 = (M β + S α h )u inc . (21)
This means that ∂ n u 2 is simply obtained through the solution of a complex-valued sparse linear system defined by the mass matrix. Once the unknown is obtained then one can compute an approximation of the jump of the normal derivative trace by the relation

ρ 2 = -(∂ n u 2 + ∂ n u inc ). ( 22
)
Another way of writing this relation is that ρ 2 is solution to

Mρ 2 = -(M β 2 + S α 2 h )u inc -M∂ n u inc := g 2 . ( 23
)
The far-field can be directly obtained through expressions [START_REF] Burton | The application of integral equation methods to the numerical solution of some exterior boundary-value problems[END_REF]. Even if the boundary condition ( 17) can be a priori applied to any scatterer Ω -, we will see during the numerical simulations that a serious loss of accuracy is observed when the scatterer presents some concave parts (see [START_REF] Antoine | Fast approximate computation of a time-harmonic scattered field using the onsurface radiation condition method[END_REF] and Figures 1, 2 and3). Indeed, in the concavity, the presence of multiply bounced rays cannot be modeled by local differential operators since the nature of this phenomena is nonlocal. Therefore, the aim of the next sections is to provide a way to directly couple the OSRC formulation in the convex part of the scatterer to the SLIE restricted to the concave part to improve the accuracy. [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF] The coupling procedure for non convex scatterers

Weak coupling procedure and boundary element approximation

Since the OSRC solution is locally inaccurate in the non convex part of the domain, we propose to build a solution which is computed first by the OSRC method and improved thanks to the integral equation where the quality of the OSRC approximation deteriorates. To this end, let us assume that the geometry Γ can be decomposed into two non-overlapping parts Γ := Γ 1 ∪Γ 2 , with Γ 1 ∩Γ 2 = {a 1 ; a 2 }. The geometry Γ 1 is related to the boundary part of Γ which is convex, the complementary (where we will use an integral equation) is Γ 2 (see Figure 1). The proposed procedure uses 1) a global computation of an approximate surface density ρ 2 through the OSRC on Γ and 2) injects the restriction of this approximation to Γ 1 into the global integral equation formulation on Γ to obtain an approximate density on Γ 2 . This way of partitioning the computation allows us to solve a smaller size boundary element system and can be seen as a "one shot" computation.

In the following, if A is a global matrix on Γ, we denote by A j the extracted matrix related to the interaction between the part Γ j of the boundary and Γ , j, = 1, 2. We then have

A = A 11 A 12 A 21 A 22 . (24)
In a similar way, the restriction of a nodal complex-valued vector z to the part of the boundary Γ is written z , for = 1, 2. Then, we propose the following algorithm for the SLIE formulation: compute

ρ 2 := (ρ 2 1 , ρ2 2 ) ∈ C n P such that 1) OSRC: extract ρ 2 1 = (ρ 2 ) 1 ∈ C n P 1 -2 from the computation of Mρ 2 = g 2 , 2) SLIE: compute ρ2 2 ∈ C n P 2 as the solution to L 22 ρ2 2 = -L 21 ρ 2 1 -(Mu inc ) 2 . (25)
Even if other coupling possibilities are available, this one has the advantage that no modification of an existing code is required. Let us denote by n Kj (respectively n P j ) the number of segments (respectively points) of the boundary Γ j , j = 1, 2. Then, we have n K = n K1 + n K2 and n P = n P 1 + n P 2 -2 (the two junction points a 1 and a 2 must be counted once). In step 1), we only retain the values of the OSRC solution that are not considered in the cavity, including the two endpoints a 1 and a 2 . This first step needs O(n K ) operations to solve the sparse complex-valued linear system (by using an LU factorization or a preconditioned iterative Krylov solver [START_REF] Saad | Iterative Methods for Sparse Linear Systems[END_REF]) while the memory storage is O(n K1 ). In the second step, the solution to a complex-valued full matrix is necessary. If a full storage is considered, then the linear system solution needs O(n 3 K2 ) elementary operations and the memory storage is O(n 2 K2 ). Usually, in integral equation solvers, most particularly for highfrequency scattering, it is preferable to use a subspace Krylov solver [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF][START_REF] Saad | Iterative Methods for Sparse Linear Systems[END_REF][START_REF] Saad | GMRES: A Generalized Minimal Residual algorithm for solving nonsymmetric linear systems[END_REF] in conjunction with a fast matrix-vector product algorithm like for example the Multilevel Fast Multipole Method (FMM) [START_REF] Liu | Fast Multipole Boundary Element Method: Theory and Applications in Engineering[END_REF], high-order solvers [START_REF] Antoine | Wave Propagation in Periodic Media -Analysis, Numerical Techniques and Practical Applications[END_REF] or the recent direct Adaptive Cross Approximation (ACA) techniques [START_REF] Hackbusch | Hierarchical Matrices: Algorithms and Analysis[END_REF]. In this case, the memory requirement is O(n K2 ) for a computational cost O(n K2 log n K2 ). In addition, it is well-known that preconditioning is a requirement to get a fast convergence. The second equation of ( 25) is defined through the single-layer integral operator. Then, the integral equation is a first-kind Fredholm equation which is known to be badly conditioned. To improve this, we propose a preconditioned version of the algorithm (25) based on the Caldèron relations [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF] and well-adapted to fast iterative solvers but without modifying the solution of the initial coupling procedure. Let D be the discrete version of the normal derivative trace operator D and D 22 its restriction to Γ 2 . Then, the preconditioned version of ( 25) is given by: find ρ

2 := (ρ 2 1 , ρ2 2 ) ∈ C n P such that 1) compute ρ 2 1 = (ρ 2 ) 1 ∈ C n P 1 -2 solution to Mρ 2 = g 2 , 2) obtain ρ2 2 ∈ C n P 2 as the solution to D 22 L 22 ρ2 2 = -D 22 L 21 ρ 2 1 -D 22 (Mu inc ) 2 . ( 26
)
The second equation of ( 26) is defined by a second-kind integral equation formulation which has better clustering properties for the convergence of Krylov subspace solvers. The price to pay is that each iteration of a Krylov solver requires to apply L 22 first and next D 22 . The preconditioned Caldèron SLIE coupling procedure ( 26) is called SLIE-OSRC 2 . Once ρ2 := (ρ 2 1 , ρ2 2 ) ∈ C n P has been computed, all the usual quantities of interest can be obtained like for the SCS given by [START_REF] Burton | The application of integral equation methods to the numerical solution of some exterior boundary-value problems[END_REF].

The SLIE-OSRC 2 formulation may suffer from the existence of interior resonances. Even if the spurious modes do not radiate for the SLIE, it can be better to have access to a stable formulation. To this end, following BWIE-OSRC 2 coupling procedure could alternatively be used: compute

ρ2 := (ρ 2 1 , ρ2 2 ) ∈ C n P such that 1) ρ 2 1 = (ρ 2 ) 1 ∈ C n P 1 -2 is solution to Mρ 2 = g 2 , 2) extract ρ2 2 ∈ C n P 2 from the solution to [(1 -α)( 1 2 M 22 + N 22 ) + αηV 22 )]ρ 2 2 = -[(1 -α)( 1 2 M 21 + N 21 ) + αηV 21 )]ρ 2 1 -(1 -α)(M∂ n u inc ) 22 -αη(Mu inc ) 22 . (27)
Unlike the SLIE-OSRC 2 formulation, the BWIE-OSRC 2 approach is defined by a second-kind Fredholm integral equation and does not really need to be preconditioned when correctly choosing α and η (see e.g. [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF]). An extra computational cost and memory storage is required since the evaluation of the double-layer potentials N 22 and N 21 are required.

In the following examples, we will report only the results related to the SLIE-OSRC 2 formulation since no resonance were met and we always plot the SCS. In addition, we do not use any iterative solver for the resulting linear systems because we are considering toys problems for a proof of concept. However, for three-dimensional problems, where the method directly extends, the difference between all the formulations may be important in terms of convergence rate. Here, we rather focus on the accuracy improvement. Further investigations are therefore needed, as well as improved formulations and implementation of higher order OSRCs.

A numerical example -validation of the procedure

As previously said, we use the SLIE-OSRC 2 formulation. The model toy problem is the following. We consider the obstacle Ω -as being composed of the square cylinder centered at the origin and with side length 2, with an inner square cavity defined by the corners (1/3, -1/3), (1, -1/3), (1, 1/3) and (1/3, 1/3). The boundary Γ 2 is then defined as the internal boundary to the cavity (blue curve on Figure 1) and Γ 1 is the complementary boundary on Γ (red curve on Figure 1). For an incident plane wave, the reference solution is given by the SLIE [START_REF] Colton | Integral Equation Methods in Scattering Theory[END_REF] discretized by the BEM (with 10 points per wavelength). The results are clearly improved compared to the pure OSRC approach for wave numbers k ≤ 15 and this, independently of the angle of attack θ inc . As it can be observed on the first picture of Figure 2 (Case 1, for k = 2), we almost obtain the reference solution by using the SLIE-OSRC 2 approach while a pure OSRC approximation gives a poor accuracy which deteriorates as k increases. For a higher wave number (Case 2, k = 8), the results are still accurate (see Figure 2). By increasing the frequency, we still have an acceptable solution as seen on the third example of Figure 2 (Case 3, k = 14). For both the integral equations and OSRCs, since we consider a mesh with ten elements per wavelength, the size of the matrix L 2,2 is about n K2 = 2.5k, which is more than four times less than for a pure SLIE solution.

The Neumann scattering problem

The Neumann scattering problem, i.e. considering (1) but with the boundary condition: ∂ n u = -∂ n u inc on Γ, can be treated similarly with the EFIE [START_REF] Antoine | An introduction to operator preconditioning for the fast iterative integral equation solution of time-harmonic scattering problems[END_REF] based on the normal derivative trace of the double-layer potential written under its weak form (called DLIE). A hyper-singular kernel must then be integrated carefully by semi-integration techniques. For the OSRC, the method applies quite similarly and leads to the solution of a sparse linear system.

In general, the coupling procedure (called DLIE-OSRC 2 ) has proved to be less accurate than for the Dirichlet problem (i.e. for SLIE-OSRC 2 ). We think that this is due to the fact that the OSRC approach requires a higher order operator to provide a suitable fast solution during the first step of the method. We recommend to rather use the square-root OSRC developed in [START_REF] Antoine | An improved surface radiation condition for highfrequency acoustic scattering problems[END_REF]. The resulting coupling technique will be analyzed in a forthcoming work. For low and moderate wave numbers (k ≤ 4), we still get quite acceptable results having always in mind the lower computational cost of the DLIE-OSRC 2 method. However, there is a moderate accuracy for wave numbers such that k ≥ 10 as seen on the two cases reported in Figures 3. Nevertheless, this must be counterbalanced by the lower cost of the procedure and the possibility to increase the OSRC accuracy in the convex part. In addition, we always obtain a good prediction of the main lobs where the energy is mostly radiating. As a general concluding remark, the coupling DLIE-OSRC 2 algorithm provides an interesting alternative to the DLIE. Furthermore, the method is always more accurate than a classical OSRC approach and gives a possibility of its extension to non-convex obstacles.

Conclusion

In this paper, we introduced a simple algorithm coupling the surface integral equation method and the OSRC technique for solving the scattering problem by nonconvex scatterers. While simple, the coupling method leads to an improved accuracy compared with the pure OSRC approach and reduces the computational cost of a direct integral equation formulation. In addition, we explain how operator preconditioning can be directly included into the formulations. The method is validated on a simple two-dimensional problem as a proof of concept. In particular, the method is accurate for the Dirichlet problem, but still needs to be further investigated by using highorder OSRCs in the case of the Neumann problem. We expect that the formulation can be useful for three-dimensional high-frequency scattering problems solved iteratively by Krylov solvers with acceleration algorithms.

2

 2

Figure 1 :

 1 Figure 1: Scattering configuration and notations.

Figure 2 :

 2 Figure 2: Bistatic SCS for the unit square cylinder with cavity and Dirichlet boundary condition: Case 1: k = 2 and θ inc = 135 deg., Case 2: k = 8 and θ inc = 160 deg. and Case 3: k = 14 and θ inc = 150 deg. 12

Figure 3 :

 3 Figure 3: Bistatic SCS for the unit square cylinder with cavity and Neumann boundary condition: Case 1: k = 9 and θ inc = 140 deg.; Case 2: k = 13 and θ inc = 160 deg.

Acknowledgments. The authors would like to thank the Deanship of Scientific Research at Umm Al-Qura University for supporting this work by grant code 18-SCI-1-01-0017.


Pierre Gaillard
email: pierre.gaillard@u-bourgogne.fr

Riemann theta functions, Fredholm and wronskian representations of the solutions to the KdV equation +

We degenerate the finite gap solutions of the KdV equation from the general formulation given in terms of abelian functions when the gaps tends to points, to get solutions to the KdV equation given in terms of Fredholm determinants and wronskians. For this we establish a link between Riemann theta functions, Fredholm determinants and wronskians. This gives the bridge between the algebro-geometric approach and the Darboux dressing method.

Introduction

We consider the KdV equation in the following normalization

u t = 6uu x -u xxx , (1)
where the subscripts x and t as usual denote partial derivatives. This equation [START_REF] Ablowitz | On solutions of the KdV equation[END_REF] was introduced for the first time in 1895 by Korteweg and de Vries [START_REF] Korteweg | On the change of form of long wawes adwancing in a rectangular canal, and on a new type of long stationary waves[END_REF]. This equation appears in a wide range of physical problems and describes the propagation of waves with weak dispersion in various nonlinear media.

A method of resolution was given in 1967 by Gardner et al. [START_REF] Gardner | Method for solving the Korteweg-de Vries equation[END_REF]. It was proven that this equation is a complete integrable system by Zakharov and Faddeev in 1971 [START_REF] Zakharov | Korteweg-de Vries equation: A completely integrable Hamiltonian system[END_REF]. Solutions were constructed by Hirota in 1971 by using the bilinear method [START_REF] Hirota | Exact solution of the Korteweg-de Vries equation for multiple collisions of solitons[END_REF].

Its and Matveev present solutions in terms of Riemann theta functions [START_REF] Its | Hill's operator with finitely many gaps[END_REF] in 1975. Lax gives in the same year the expressions of periodic and almost periodic solutions [START_REF] Lax | Periodic solutions of the KdV equation[END_REF]. A lot of works have been realized in the following years. We can mention for example Airault et al. in 1977 [3], Adler and Moser in 1978 [START_REF] Adler | On a class of polynomials connected with the Kortewegde-Vries equation[END_REF], Ablowitz and Cornille in 1979 [START_REF] Ablowitz | On solutions of the KdV equation[END_REF], Freeman and Nimmo in 1984 [START_REF] Freeman | Nimmo Rational solutions of the KdV equation in wronskian form[END_REF], Matveev in 1992 [START_REF] Matveev | Generalized Wronskian Formula for solutions of the KdV equation[END_REF], Ma in 2004 [START_REF] Ma | Solving the KdV equation by its bilinear form wronskian solutions[END_REF], Kovalyov in 2005 [START_REF] Kovalyov | On a class of solutions of KdV[END_REF] and more recently Ma in 2015 [START_REF] Ma | Lump solutions to the KP equation[END_REF].

1

In the following, we are interested in the algebro-geometric approach given by Its and Matveev in 1975. We degenerate the solutions to the KdV equation given in terms of Riemann theta functions to get solutions in terms of Fredholm determinants. Then we give a representation in terms of wronskians. This gives the correspondence between the algebro-geometric approach and the Darboux dressing method.

2 The KdV equation and its solutions in terms of theta functions

We consider the Riemann surface Γ of the algebraic curve defined by

ω 2 = 2g+1 j=1 (z -E j ), with E j = E k , j = k.
Let D be some divisor D = g j=1 P j , P j ∈ Γ. The so-called finite gap solution of the KdV equation

u t = 6uu x -u xxx (2)
can be expressed in the form [START_REF] Its | Hill's operator with finitely many gaps[END_REF] u

(x, t) = -2∂ 2 x [ln θ(xg + tv + l)] + C. (3)
We recall briefly, the notations. In (3), θ is the Riemann function defined by

θ(z) = k∈Z g exp{πi(Bk|k) + 2πi(k|z)}, (4)
constructed from the matrix of the B-periods of the surface Γ, and the vectors g, v, l are defined by

g j = 2ic j1 , (5)
v j = 8i( c j1 2 2g+1 k=1 E k + c j2 ), (6)
l j = - g k=1 P k ∞ dU j + j 2 - 1 2 g k=1 B kj , (7)
C = 2g+1 k=1 E k -2 g k=1 a k zdU k , (8)
the coefficients c jk being relating with abelian differential dU j by

dU j = g k=1 c jk z g-k 2g+1 k=1 (z -E k ) dz, (9)
and coefficients c jk can be obtained by solving the system of linear equations

a k dU j = δ jk , 1 ≤ j ≤ g, 1 ≤ k ≤ g.

Degeneracy of solutions

We suppose that E j are real, E m < E j if m < j and try to evaluate the limits of all objects in formula (3) when E 2m , E 2m+1 tends to -α m , -α m = -κ 2 m , κ m > 0, for 1 ≤ m ≤ g, and E 1 tends to 0 (these ideas were first presented by A. Its and V.B. Matveev, exposed for example in [START_REF] Belokolos | Algebro-geometric approach to nonlinear integrable equations[END_REF]).

Degeneracy of the components of the solution

3.1.1 Limit of P (z) = 2g+1 j=1 (z -E j )
The limit of

P (z) = 2g+1 j=1 (z -E j ) is evidently equal to P (z) = z g j=1 (z + α j ) 2 3.1.2 Limit of dU m = g k=1 c mk z g-k 2g+1 k=1 (z -E k ) dz The limit of dU m is equal to dU m = ϕ m (z) √ z g j=1 (z + α j )
dz, where ϕ m (z) = g k=1 cmk z g-k . The normalization condition takes the form in the limit

a k dU j → 2πiϕ j (-α k ) -iκ k m =k (-α k + α m ) = δ kj , (10)
which proves that the numbers -α m , m = k are the zeros of the polynomials ϕ k (z), and so ϕ k (z) can be written as ϕ k (z) = ck1 m =k (z + α m ). By (10), we get in the limit ck1 = -

κ k 2πi . So d Ũk = - κ k 2πi √ z(z + α k ) dz 3.1.3 Limit of v k and g k
By identification of the powers of z g-2 in ( 11)

φk (z) = c k1 l =k (z + α l ) = g j=1 c kj z g-j , (11)
we get in the limit For

λ 0 = -α m = -κ 2 m , I = 0 λ0 dU k → 1 2
Bmk . The integral I can be easily evaluate along the real axis on the upper sheet of surface Γ and we get

I → i 2π ln κ m + κ k κ m -κ k .
So we have the limit values of matrix B :

Bmk = i π ln κ m + κ k κ m -κ k .
Therefore iB kk tends to -∞. As previously, we have

P ∞ dU j → - i 2π ln κ j - √ z P κ j + √ z P . (12)

Limit of argument of exponential in θ(p)

Let us denote A 0 the argument of exponential in θ(p) = k∈Z g exp{πi(Bk|k) + 2πi(k|p)}.

A 0 can be rewritten in the form

A 0 = πi g j=1 B jj k j (k j -1) + 2πi j>m B mj k m k j + g j=1 πi(2p j + B jj )k j . ( 13
)
Using the inequality k j (k j -1) ≥ 0 for all k ∈ Z g and the fact that iB kk tends to -∞, we can reduce the limit θ of θ(p) to a finite sum taken over vectors k ∈ Z g such that each k j must be equal to 0 or 1. So, if we denote A the argument of θ(xg + tv + l), it can be written in the form

A = πi g j=1 B jj k j (k j -1) + 2πi j>m B mj k m k j + g j=1 k j [2πi(g j x + v j t) -πi(-j + 2 g k=1 P k ∞ dU j + m =j B mj )].
In other words

A = πi g j=1 B jj k j (k j -1) + 2πi j>m B mj k m k j + g j=1 k j Q j , with Q j = 2πi(g j x + v j t) + β j and β j = -πi(-j + 2 g k=1 P k ∞ dU j + m =j B mj ).
The quantity β j has a finite limit value βj independent from x and t.

Limit of θ(xg

+ vt + l)
By means of the inequality k j (k j -1) ≥ 0 for all k ∈ Z g and the previous relation iB kk tends to -∞, it turns out that the limit θ of θ(xg + tv + l) reduce to a finite sum taken over vectors k ∈ Z g with the property that each k j must be equal to 0 or 1.

θ = k∈Z g , kj =0 or 1 exp{ m>j 2 ln κ m -κ j κ m + κ j k m k j +( g j=1 2κ j x-8κ 3 j t+2κ j x j +πji+ m =j ln κ m + κ j κ m -κ j )k j }, with x j = 1 2κ j g k=1 ln √ z k -iκ j √ z k + iκ j .
It can be rewritten as θ = J⊂{1,...,g} j∈J (-1) j j∈J k / ∈J κ j + κ k κ jκ k exp j∈J 2(κ j x -4κ 3 j t + κ j x j ). ( 14)

Limit of the coefficient C

The coefficient C is defined in [START_REF] Gaillard | New formulas for the eigenfunctions of the two-particle Calogero-Moser system[END_REF] by

C = 2g+1 k=1 E k -2 g k=1 a k zdU k = C 1 + C 2 ,
can be evaluated as follows.

C 2 = -2 g k=1 a k zdU k = -2 g k=1 a k -κ k zdz 2π √ z(z + α k ) = g k=1 κ k π a k √ zdz (z + α k ) = g k=1 κ k π 2iπ(-iκ k ) = g k=1 2κ 2 k = 2 g k=1 α k .
Thus when the gaps tends to points,, the coefficient C tends to C equal to

C = 2 g k=1 -α k + 2 g k=1 α k = 0.
(-1) j j∈J k / ∈J κ j + κ k κ j -κ k exp   j∈J 2(κ j x -4κ 3 j t + κ j x j )     , ( 15
)
with κ j , and x j arbitrary real parameters, is a solution to the KdV equation (1).

4 From theta function to Fredholm determinant

The link between the degenerate solution and the Fredholm determinant

In a recent paper, Kirillov and Van Diejen [START_REF] Van Diejen | Kirillov Determinantal formulas for zonal spherical functions on hyperboloids[END_REF] have given formulas in terms of determinants for zonal spherical functions on hyperboloids. In particular, they compute det(I + A), where I is the unit matrix and A = (a jk ) 1≤j,k≤m the matrix defined as :

a jk = 2ǫ j κ j κ j + κ k exp(-2κ j x) l =j κ l + κ j κ l -κ j , (16)
where ǫ j ∈ {-1; +1} and κ j > 0 for 1 ≤ j ≤ N . Then det(I + A) has the following form

det(I + A) = J⊂{1,...,N } exp   -2x j∈J κ j   j∈J ǫ j j∈J k / ∈J κ j + κ k κ j -κ k . ( 17
)
Using the same strategy, we can compute det(I + A) where A = (a jk ) 1≤j,k≤m is the matrix defined as :

a jk = (-1) j 2κ j κ j + κ k exp 2(κ j x -4κ 3 j t + κ j x j ) l =j κ l + κ j κ l -κ j ,
x j being an arbitrary parameter.

Then det(I + A) has the following form

det(I + A) = J⊂{1,...,N } exp   j∈J 2(κ j x -4κ 3 j t + κ j x j )   j∈J (-1) j j∈J k / ∈J κ j + κ k κ j -κ k , (18)
By the previous section, θ = J⊂{1,...,g} j∈J

(-1) j j∈J k / ∈J κ j + κ k κ j -κ k exp   j∈J (2(κ j x -4κ 3 j t + κ j x j )   . ( 19
)
If we compare the expression ( 18) to ( 19), we have clearly the equality with

g = N θ = det(I + A). ( 20
)

Solution to the KdV equation in terms of Fredholm determinant

So we have the following representation of the solutions to the KdV equation Theorem 4.1 The fonction u defined by

u(x, t) = -2∂ 2 x ln(det(I + A)), (21)
with A the matrix defined by A = (a jk ) 1≤j,k≤N

a jk = (-1) j 2κ j κ j + κ k exp 2(κ j x -4κ 3 j t + κ j x j ) l =j κ l + κ j κ l -κ j , (22)
and κ j , x j arbitrary real parameters, is a solution to the KdV equation (1).

If we consider the matrix B defined by b jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j )

l =k κ l + κ j κ l -κ k ,
it is easy to verify that det(I + A) = det(I + B), and so we can give another representation of the solutions to the KdV equation. We get the following statement :

Theorem 4.2 The fonction u defined by

u(x, t) = -2∂ 2 x ln(det(I + B)), (23)
with B the matrix defined by B = (b jk ) 1≤j,k≤m

b jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j ) l =k κ l + κ j κ l -κ k , (24)
and κ j , x j arbitrary real parameters, is a solution to the KdV equation (1).

We can also consider the matrix C defined by

c jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j ) l =k |κ l + κ j | l =j |κ l -κ j | .
It is easy to check that det(I + A) = det(I + C), and so we can give a third representation of the solutions to the KdV equation :

Theorem 4.3
The fonction u defined by

u(x, t) = -2∂ 2 x ln(det(I + C)), (25)
with C the matrix defined by C = (c jk ) 1≤j,k≤m

c jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j ) l =k |κ l + κ j | l =j |κ l -κ j | , (26)
and κ j , x j arbitrary real parameters, is a solution to the KdV equation (1).

Another possibility is to choose the matrix D defined by

d jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j ) l =j κ l + κ k κ l -κ j .
It is also easy to check that det(I + A) = det(I + D), and so we can give another representation of the solutions to the KdV equation :

with C the matrix defined by D = (d jk ) 1≤j,k≤m d jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j )

l =j κ l + κ k κ l -κ j , (28)
and κ j , x j arbitrary real parameters, is a solution to the KdV equation [START_REF] Ablowitz | On solutions of the KdV equation[END_REF].

It remains to find the link between this Fredholm determinant and a certain wronskian.

5 From Fredholm determinants to wronskians

Link between Fredholm determinants and wronskians

In this section, we consider the following functions

φ j (x) = sinh(κ j x -4κ 3 j t + κ j x j ), (29)
where κ j are real numbers such that κ 1 ≤ . . . ≤ κ N , and x j an arbitrary constant independent of x.

We use the following notations : θ j = (κ j x -4κ 3 j t + κ j x j ). W = W (φ j , . . . , φ N ) is the classical Wronskian W = det[(∂ j-1

x φ i ) i, j∈ [1,...,N ] ]. We consider the matrix A = (a jk ) j, k∈[1,...,N ] defined by a jk = (-1) j exp 2(κ j x -4κ 3 j t + κ j x j )

l =j κ l + κ k κ l -κ j . (30)
Then we have the following statement Theorem 5.1

det(I + A) = 2 N (-1) N (N +1) 2 exp( N j=1 θ j ) N j=2 j-1 i=1 (κ j -κ i ) W (φ 1 , . . . , φ N ) (31)

Solutions to the KdV equation in terms of wronskians

From the previous subsection, we can give the following wronskian representation of the solutions to the KdV equation.

Theorem 5.2 The function u defined by

u(x, t) = -2∂ 2 x (ln [W (φ 1 , . . . , φ N )]) , (32) where
= W (φ 1 , . . . , φ N ) = det[(∂ j-1 x φ i ) i, j∈[1,...,N ]
] is the wronskian of the functions φ defined by φ j (x, t) = sinh(κ j x -4κ 3 j t + κ j x j ), κ j , x j being real numbers, is a solution to the KdV equation [START_REF] Ablowitz | On solutions of the KdV equation[END_REF].

It is relevant to note that we recover the result given by the Darboux dressing [START_REF] Matveev | Generalized Wronskian Formula for solutions of the KdV equation[END_REF]. This realize the connection between the algebro-geometric approach and the Darboux dressing method.

Remark 5.1 The choices of functions φ j are not unique. For example, we can choose : φ j (x) = cosh(κ j x -4κ 3 j t + κ j x j ), or φ j (x) = exp(κ j x -4κ 3 j t + κ j x j ), or φ j (x) = exp(-(κ j x -4κ 3 j t + κ j x j )) or any combinations of these different last functions. We can also choose the following functions : φ j (x) = sin(κ j x + 4κ 3 j t + κ j x j ), or φ j (x) = cos(κ j x + 4κ 3 j t + κ j x j ), or φ j (x) = exp(i(κ j x + 4κ 3 j t + κ j x j )), or φ j (x) = exp(-i(κ j x + 4κ 3 j t + κ j x j )) any combinations of these different last functions.

Conclusion

In this paper, we succeed to construct different types of representations of the solutions to the KdV equation. First, it was essential to express the degenerate θ function into an explicit Fredholm determinant. The second step was to get the transformation of the Fredholm determinant into a wronskian. I have to mention a paper of Whitham [START_REF] Whitham | Comments on Periodic Waves and Solitons[END_REF] in connection with this work, and I would like to thank the referee about this information. The article [START_REF] Whitham | Comments on Periodic Waves and Solitons[END_REF] deals with equations as the KdV equation and the representation of solutions as sum of solitons, and also the relation of these solutions with Riemann theta functions in particular. It can be compared with the solutions given in the present work expressed in terms of Fredholm determinant and wronskians.

4

 4 So we have the limit values of v k and g k : Limit of U k (P ) and B mk

3. 2 3 . 1

 231 Degenerate solution to the KdV equation Therefore, we have the following representation of the degenerate solution to the KdV equation Theorem The fonction u defined by u(x, t) = -2∂ 2 x ln   J⊂{1,...,g} j∈J

Theorem 4 . 4

 44 The fonction u defined by u(x, t) = -2∂ 2x ln(det(I + D)),


Nathan Grosshans

A Note on the Join of Varieties of Monoids with LI

Keywords: 2012 ACM Subject Classification Theory of computation → Formal languages and automata theory; Theory Varieties of monoids, join, LI

In this note, we give a characterisation in terms of identities of the join of V with the variety of finite locally trivial semigroups LI for several well-known varieties of finite monoids V by using classical algebraic-automata-theoretic techniques. To achieve this, we use the new notion of essentially-V stamps defined by Grosshans, McKenzie and Segoufin and show that it actually coincides with the join of V and LI precisely when some natural condition on the variety of languages corresponding to V is verified.

This work is a kind of rediscovery of the work of J. C. Costa around 20 years ago from a rather different angle, since Costa's work relies on the use of advanced developments in profinite topology, whereas what is presented here essentially uses an algebraic, language-based approach.

Introduction

One of the most fundamental problems in finite automata theory is the one of characterisation: given some subclass of the class of regular languages, find out whether there is a way to characterise those languages using some class of finite objects. This problem is often linked to and motivated by the problem of decidability: given some subclass of the class of regular languages, find out whether there exists an algorithm testing the membership of any regular language in that subclass. The obvious approach to try to find a characterisation of a class of regular languages would be to look for properties shared by all the minimal finite automata of those languages. If we find such characterising properties, we can then ask whether they can be checked by an algorithm to answer the problem of decidability for this class of languages. However, one of the most fruitful approaches of those two problems has been the algebraic approach, in which we basically replace automata with morphisms into monoids: a language L over an alphabet Σ is then said to be recognised by a morphism φ into a monoid M if and only if L is the inverse image by φ of a subset of M . Under this notion of recognition, each language has a minimal morphism recognising it, the syntatic morphism into the syntactic monoid of that language, that are minimal under some notion of division. The fundamental result on which this algebraic approach relies is that a language is regular if and only if its syntactic monoid is finite. One can thus try to find a characterisation of some class of regular languages by looking at the algebraic properties of the syntactic monoids of these languages. And many such characterisations that are decidable were indeed successfully obtained since Schützenberger's seminal work in 1965 [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF]. His famous result, that really started the field of algebraic automata theory, states that the star-free regular languages are exactly those whose syntactic monoids are finite and aperiodic. Another important early result in that vein is the one of Simon [START_REF] Simon | Piecewise testable events[END_REF] characterising the piecewise testable languages as exactly those having a finite J-trivial syntactic monoid. Eilenberg [START_REF] Eilenberg | Automata, Languages, and Machines. B. Pure and applied mathematics[END_REF] was the first to prove that such algebraic characterisations actually come as specific instances of a general bijective correspondence between varieties of finite monoids and varieties of languages -classes of, respectively, finite monoids and regular languages closed under natural operations. Thus, a class of regular languages can indeed be characterised by the syntactic monoids of these languages, as soon as it verifies some nice closure properties. Eilenberg's result was later completed by Reiterman's theorem [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF], that uses a notion of identities defined using profinite topology and states that a class of finite monoids is a variety of finite monoids if and only if it is defined by a set of profinite identities. Therefore, one can always characterise the variety of finite monoids associated to a variety of languages by a set of profinite identities and, additionally, this characterisation often leads to decidability, especially when this set is finite. A great deal of research works have been conducted to characterise varieties of finite monoids or semigroups by profinite identities (see the book of Almeida [START_REF] Almeida | Finite Semigroups and Universal Algebra[END_REF] for an overview; see also the book chapter by Pin [START_REF] Pin | Syntactic semigroups[END_REF] for more emphasis on the "language" part).

A kind of varieties of finite monoids or semigroups that has attracted many research efforts aiming for characterisations through identities are the varieties defined as the join of two other varieties. Given two varieties of finite monoids V and W, the join of V and W, denoted by V ∨ W, is the least variety of finite monoids containing both V and W. One of the main motivations to try to understand V ∨ W is that the variety of languages corresponding to it by the Eilenberg correspondence, L(V ∨ W), is the one obtained by considering direct products of automata recognising languages from both L(V) and L(W), the varieties of languages corresponding to, respectively, V and W. This is a fundamental operation on automata, and while it is straightforward that L(V ∨ W) is simply the least variety of languages containing both L(V) and L(W), this does not at all furnish a decidable characterisation of L(V ∨ W), let alone a set of identities defining V∨W. Generally speaking, the problem of finding a set of identities defining V ∨ W is difficult (see [START_REF] Almeida | Finite Semigroups and Universal Algebra[END_REF][START_REF] Zeitoun | On the join of two pseudovarieties. Semigroups, Automata and Languages[END_REF]): in fact, there exist two varieties of finite semigroups that have a decidable membership problem but whose join has an undecidable membership problem [START_REF] Albert | Undecidability of the identity problem for finite semigroups[END_REF]. However, sets of identities have been found for many specific joins: have a look at [START_REF] Almeida | Some pseudovariety joins involving the pseudovariety of finite groups[END_REF][START_REF] Almeida | The join of the pseudovarieties of R-trivial and L-trivial monoids[END_REF][START_REF] Azevedo | The join of the pseudovariety J with permutative pseudovarieties[END_REF][START_REF] Zeitoun | On the decidability of the membership problem of the pseudovariety J∨B[END_REF][START_REF] Zeitoun | The join of the pseudovarieties of idempotent semigroups and locally trivial semigroups[END_REF][START_REF] Azevedo | Three examples of join computations[END_REF][START_REF] Carlos | Some pseudovariety joins involving locally trivial semigroups[END_REF][START_REF] Carlos | Some pseudovariety joins involving groups and locally trivial semigroups[END_REF] for some examples.

In this paper, we give a general method to find a set of identities defining the join of an arbitrary variety of finite monoids V and the variety of finite locally trivial semigroups LI, as soon as one has a set of identities defining V and V verifies some criterion. Joins of that sort have been studied quite a lot in the literature we mentioned in the previous paragraph (e.g. in [START_REF] Azevedo | The join of the pseudovariety J with permutative pseudovarieties[END_REF][START_REF] Zeitoun | The join of the pseudovarieties of idempotent semigroups and locally trivial semigroups[END_REF][START_REF] Carlos | Some pseudovariety joins involving locally trivial semigroups[END_REF][START_REF] Carlos | Some pseudovariety joins involving groups and locally trivial semigroups[END_REF]), but while these works usually rely heavily on profinite topology with some in-depth understanding of the structure of the elements of the so-called free pro-V monoids and free pro-LI semigroups, we present a method that reduces the use of profinite topology to the minimum and that relies mainly on algebraic and language-theoretic techniques. The variety LI is well-known to correspond to the class of languages for which membership only depends on bounded-length prefixes and suffixes of words. In [START_REF] Grosshans | Tameness and the power of programs over monoids in DA[END_REF], McKenzie, Segoufin and the author introduced the notion of essentially-V stamps (surjective morphisms φ : Σ * → M for Σ an alphabet and M a finite monoid) to characterise the built-in ability that programs over monoids in V have to treat separately some constant-length beginning and ending of a word. Informally said, a stamp is essentially-V when it behaves like a stamp into a monoid of V as soon as a sufficiently long beginning and ending of the input word has been fixed. Our method builds on two results, that we prove in this article. all identities x ω yuzt ω = x ω yvzt ω for u = v an identity in E and where x, y, z, t do appear neither in u nor in v.

2.

The second result says that EV and V ∨ LI do coincide if and only if V verifies some criterion, that can be formulated in terms of quotient-expressibility in L(V): any language L ∈ L(V) must, for an arbitrary choice of x, y, be such that the quotient u -1 Lv -1 for u and v long enough can be expressed as the quotient (xu) -1 K(vy) -1 for a K ∈ L(V). Using these results, we can find a set of identities defining V ∨ LI as soon as a set of identities defining V is known by proving that V verifies the criterion in point 2. Note that actually, for technical reasons, we work with the so-called ne-variety of stamps corresponding to V ∨ LI rather than directly with the variety of finite semigroups V ∨ LI, but this is not a problem since a variety of finite semigroups can always be seen as an ne-variety of stamps and vice versa. We apply this method to reprove characterisations of the join of LI with each of the well-known varieties of finite monoids R, L, J and any variety of finite groups.

The author noticed after proving those results that his work actually forms a kind of rediscovery of the work of J. C. Costa in [START_REF] Carlos | Some pseudovariety joins involving locally trivial semigroups[END_REF]. He defines an operator U associating to each set of identities E the exact same new set U (E) of identities as in point 1. Costa then defines a property of cancellation for varieties of finite semigroups such that for any V verifying it, U (E) defines V ∨ LI for E defining V. He finally uses this result to derive characterisations of V ∨ LI for all the cases we are treating in our paper and many more.

What is, then, the contribution of our article? In a nutshell, it does mainly use algebraic and language-theoretic techniques while Costa's work relies heavily on profinite topology. In our setting, once the stage is set, all proofs are quite straightforward without real difficulties and rely on classical language-theoretic characterisations of the varieties under consideration. This is to contrast with Costa's work, that for instance draws upon the difficult analysis of the elements of free pro-R monoids by Almeida and Weil [START_REF] Almeida | Free profinite R-trivial monoids[END_REF] to characterise R ∨ LI.

Organisation of the article. Section 2 is dedicated to the necessary preliminaries. In Section 3, we recall the definition of essentially-V stamps and prove the characterisation by identities of point 1 above. Section 4 is then dedicated to the necessary and sufficient criterion for EV and V ∨ LI to coincide presented in point 2 and finally those results are applied to specific cases in Section 5. We finish with a short conclusion.

Preliminaries

We briefly introduce the mathematical material used in this paper. For the basics and the classical results of automata theory, we refer the reader to the two classical references of the domain by Eilenberg [START_REF] Eilenberg | Automata, Languages, and Machines. A. Pure and applied mathematics[END_REF][START_REF] Eilenberg | Automata, Languages, and Machines. B. Pure and applied mathematics[END_REF] and Pin [START_REF] Pin | Varieties of Formal Languages[END_REF]. For definitions and results specific to varieties of stamps and associated profinite identities, see the articles by Straubing [START_REF] Straubing | On logical descriptions of regular languages[END_REF] and by Pin and Straubing [START_REF] Pin | Some results on C-varieties[END_REF]. We also assume some basic knowledge of topology.

General notations.

Let i ∈ N be a natural number. We shall denote by [i] the set of all natural numbers n ∈ N verifying 1 ≤ n ≤ i.

Words and languages.

Let Σ be a finite alphabet. We denote by Σ * the set of all finite words over Σ. We also denote by Σ + the set of all finite non empty words over Σ, the empty word being denoted by ε. Our alphabets and words will always be finite, without further mention of this fact. Given a word w ∈ Σ * , we denote its length by |w| and the set of letters it contains by alph(w). Given n ∈ N, we denote by Σ ≥n , Σ n and Σ <n the set of words over Σ of length, respectively, at least n, exactly n and less than n.

A language over Σ is a subset of Σ * . A language is regular if it is recognised by a deterministic finite automaton. The quotient of a language L over Σ relative to the words u and v over Σ is the language, denoted by u -1 Lv -1 , of the words w such that uwv ∈ L.

Monoids, semigroups and varieties.

A semigroup is a non-empty set equipped with an associative law that we will write multiplicatively. A monoid is a semigroup with an identity. An example of a semigroup is Σ + , the free semigroup over Σ. Similarly Σ * is the free monoid over Σ. A morphism φ from a semigroup S to a semigroup T is a function from S to T such that φ(xy) = φ(x)φ(y) for all x, y ∈ S. A morphism of monoids additionally requires that the identity is preserved. A semigroup T is a subsemigroup of a semigroup S if T is a subset of S and is equipped with the restricted law of S. Additionally the notion of submonoids requires the presence of the identity. A semigroup T divides a semigroup S if T is the image by a semigroup morphism of a subsemigroup of S. Division of monoids is defined in the same way. The Cartesian (or direct) product of two semigroups is simply the semigroup given by the Cartesian product of the two underlying sets equipped with the Cartesian product of their laws. An element s of a semigroup is idempotent if ss = s.

A variety of finite monoids is a non-empty class of finite monoids closed under Cartesian product and monoid division. A variety of finite semigroups is defined similarly. When dealing with varieties, we consider only finite monoids and semigroups, so we will drop the adjective finite when talking about varieties in the rest of this article.

Varieties of stamps.

Let f : Σ * → Γ * be a morphism from the free monoid over an alphabet Σ to the free monoid over an alphabet Γ, that we might call an all-morphism. We say that f is an ne-morphism (non-erasing morphism) whenever f (Σ) ⊆ Γ + .

We call stamp a surjective morphism φ : Σ * → M for Σ an alphabet and M a finite monoid. We say that a stamp φ : Σ * → M all-divides (respectively ne-divides) a stamp ψ : Γ * → N whenever there exists an all-morphism (respectively ne-morphism) f : Σ * → Γ * and a surjective morphism α :

Im(ψ • f ) → M such that φ = α • ψ • f . The direct product of two stamps φ : Σ * → M and ψ : Σ * → N is the stamp φ × ψ : Σ * → K such that K is the submonoid of M × N generated by {(φ(a), ψ(a)) | a ∈ Σ} and φ × ψ(a) = (φ(a), ψ(a)) for all a ∈ Σ.
An all-variety of stamps (respectively ne-variety of stamps) is a non-empty class of stamps closed under direct product and all-division (respectively ne-division).

We will often use the following characteristic index of stamps, defined in [START_REF] Chaubard | First order formulas with modular predicates[END_REF]. Consider a stamp φ : Σ

* → M . As M is finite there is a k ∈ N >0 such that φ(Σ 2k ) = φ(Σ k ): this implies that φ(Σ k ) is a semigroup. The least such k is called the stability index of φ.

Varieties of languages.

A language L over an alphabet Σ is recognised by a monoid M if there is a morphism φ : Σ * → M and F ⊆ M such that L = φ -1 (F ). We also say that φ recognises L. It is well known that a language is regular if and only if it is recognised by a finite monoid. The syntactic congruence of L, denoted by ∼ L , is the equivalence relation on Σ * defined by u ∼ L v for u, v ∈ Σ * whenever for all x, y ∈ Σ * , xuy ∈ L if and only if xvy ∈ L. The quotient Σ * /∼ L is a monoid, called the syntactic monoid of L, that recognises L via the syntactic morphism η L of L sending any word u to its equivalence class [u] ∼ L for ∼ L . A stamp φ : Σ * → M recognises L if and only if there exists a surjective morphism

φ : M → Σ * /∼ L verifying η L = α • φ.
A class of languages C is a correspondence that associates a set C(Σ) to each alphabet Σ. A ( all-)variety of languages (respectively an ne-variety of languages) V is a non-empty class of regular languages closed under Boolean operations, quotients and inverses of allmorphisms (respectively ne-morphisms). A classical result of Eilenberg [12, Chapter VII, Section 3] says that there is a bijective correspondence between varieties of monoids and varieties of languages: to each variety of monoids V we can bijectively associate L(V) the variety of languages whose syntactic monoids belong to V. This was generalised by Straubing [START_REF] Straubing | On logical descriptions of regular languages[END_REF] to varieties of stamps: to each all-variety (respectively ne-variety) of stamps V we can bijectively associate L(V) the all-variety (respectively ne-variety) of languages whose syntactic morphisms belong to V. Given two all-varieties (respectively ne-varieties)

of stamps V 1 and V 2 , we have V 1 ⊆ V 2 ⇔ L(V 1 ) ⊆ L(V 2 ).
For V a variety of monoids, we define ⟨V⟩ all the all-variety of all stamps φ : Σ * → M such that M ∈ V. Of course, in that case L(V) = L(⟨V⟩ all ). Similarly, for V a variety of semigroups, we define ⟨V⟩ ne the ne-variety of all stamps φ : Σ * → M such that φ(Σ + ) ∈ V.

In that case, we consider L(V) to be the ne-variety of languages corresponding to ⟨V⟩ ne . The operations ⟨•⟩ all and ⟨•⟩ ne form bijective correspondences between varieties of monoids and all-varieties of stamps and between varieties of semigroups and ne-varieties of stamps, respectively (see [START_REF] Straubing | On logical descriptions of regular languages[END_REF]).

Identities. Let Σ be an alphabet. Given u, v ∈ Σ * , we set v) , using the conventions that min ∅ = +∞ and 2 -∞ = 0. Then d is a metric on Σ * . The completion of the metric space (Σ * , d), denoted by ( Σ * , d), is a metric monoid called the free profinite monoid on Σ * . Its elements are all the formal limits lim n→∞ x n of Cauchy sequences (x n ) n≥0 in (Σ * , d) and the metric d on Σ * extends to a metric d on Σ * defined by d(lim n→∞ x n , lim n→∞ y n ) = lim n→∞ d(x n , y n ) for Cauchy sequences (x n ) n≥0 and (y n ) n≥0 in (Σ * , d). Note that, when it is clear from the context, we usually do not make the metric explicit when talking about a metric space. One important example of elements of Σ * is given by the elements x ω = lim n→∞ x n! for all x ∈ Σ * .

r(u, v) = min{|M | | ∃φ : Σ * → M stamp s.t. φ(u) ̸ = φ(v)} and d(u, v) = 2 -r(u,
Every finite monoid M is considered to be a complete metric space equipped with the discrete metric d defined by

d(m, n) = 0 if m = n
1 otherwise for all m, n ∈ M . Every stamp φ : Σ * → M extends uniquely to a uniformly continuous morphism φ : Σ * → M with φ(lim n→∞ x n ) = lim n→∞ φ(x n ) for every Cauchy sequence (x n ) n≥0 in Σ * . Similarly, every all-morphism f : Σ * → Γ * extends uniquely to a uniformly continuous morphism f :

Σ * → Γ * with f (lim n→∞ x n ) = lim n→∞ f (x n ) for every Cauchy sequence (x n ) n≥0 in Σ * .
For u, v ∈ A * with A an alphabet, we say that a stamp φ : Σ * → M all-satisfies (respectively ne-satisfies) the identity u = v if for every all-morphism (respectively nemorphism) f :

A * → Σ * , it holds that φ • f (u) = φ • f (v).

Given a set of identities E, we denote by [[E]] all (respectively [[E]

] ne ) the class of stamps all-satisfying (respectively nesatisfying) all the identities of E. When [[E]] all (respectively [[E]] ne ) is equal to an all-variety (respectively ne-variety) of stamps V, we say that E all-defines (respectively ne-defines) V.

▶ Theorem 1 ([16, Theorem 2.1]). A class of stamps is an all-variety (respectively ne-variety) of stamps if and only if it can be all-defined (respectively ne-defined) by a set of identities.

To give some examples, the classical varieties of monoids J, R and L can be characterised by identities in the following way:

⟨R⟩ all = [[(ab) ω a = (ab) ω ]] all = [[(ab) ω a = (ab) ω ]] ne ⟨L⟩ all = [[b(ab) ω = (ab) ω ]] all = [[b(ab) ω = (ab) ω ]] ne ⟨J⟩ all = [[(ab) ω a = (ab) ω , b(ab) ω = (ab) ω ]] all = [[(ab) ω a = (ab) ω , b(ab) ω = (ab) ω ]] ne .
Finite locally trivial semigroups and the join operation. The variety LI of finite locally trivial semigroups is well-known to verify ⟨LI⟩ ne = [[x ω yx ω = x ω ]] ne and to be such that for any alphabet Σ, the set L(LI)(Σ) consists of all Boolean combinations of languages of the form uΣ * or Σ * u for u ∈ Σ * , or equivalently of all languages of the form U Σ * V ∪ W with U, V, W ⊆ Σ * finite (see [14, p. 38]).

Given a variety of monoids V, the join of V and LI, denoted by V ∨ LI, is the inclusionwise least variety of semigroups containing both V and LI. In fact, a finite semigroup S belongs to V ∨ LI if and only if there exist M ∈ V and T ∈ LI such that S divides the semigroup M × T . (See [12, Chapter V, Exercise 1.1].) We can prove the following adaptation to ne-varieties of the classical results about joins (see the appendix for the proof).

▶ Proposition 2. Let V be a variety of monoids. Then ⟨V ∨ LI⟩ ne is the inclusion-wise least ne-variety of stamps containing both ⟨V⟩ all and ⟨LI⟩ ne . Moreover, L(V ∨ LI) is the inclusion-wise least ne-variety of languages containing both L(V) and L(LI) and verifies that

L(V ∨ LI)(Σ) is the Boolean closure of L(V)(Σ) ∪ L(LI)(Σ) for each alphabet Σ.

Essentially-V stamps

In this section, we give a characterisation of essentially-V stamps (first defined in [START_REF] Grosshans | Tameness and the power of programs over monoids in DA[END_REF]), for V a variety of monoids, in terms of identities. We first recall the definition.

▶ Definition 3. Let V be a variety of monoids. Let φ : Σ * → M be a stamp and let s be its stability index. We say that φ is essentially-V whenever there exists a stamp µ : Σ * → N with N ∈ V such that for all u, v ∈ Σ * , we have

µ(u) = µ(v) ⇒ φ(xuy) = φ(xvy) ∀x, y ∈ Σ s .
We will denote by EV the class of all essentially-V stamps. 1 Now, we give a characterisation for a stamp to be essentially-V, based on a specific congruence depending on that stamp.

▶ Definition 4. Let φ : Σ * → M be a stamp and let s be its stability index. We define the equivalence relation ≡ φ on Σ * by u ≡ φ v for u, v ∈ Σ * whenever φ(xuy) = φ(xvy) for all x, y ∈ Σ ≥s . 1 Essentially-V stamps are called that way by analogy with quasi-V stamps and the class of essentially-V stamps is denoted by EV by analogy with QV, the notation for the class of quasi-V stamps. This makes sense since the initial motivation for the definition of essentially-V stamps was to capture the class of stamps into monoids of V that have the additional ability to treat separately some constant-length beginning and ending of a word. This ability can indeed be seen as orthogonal to the additional ability of stamps into monoids in V to perform modular counting on the positions of letters in a word, which is often handled by considering quasi-V stamps. (See [START_REF] Grosshans | Tameness and the power of programs over monoids in DA[END_REF] for more.) Our definition of EV does unfortunately not coincide with the usual definition of EV, that classically denotes the variety of monoids M such that the submonoid generated by the idempotents of M is in V. (This comes, among others, from the fact that the obtained variety of monoids does always contain at least all finite groups.)

▶ Proposition 5. Let φ : Σ * → M be a stamp. Then ≡ φ is a congruence of finite index and for any variety of monoids V, we have φ ∈ EV if and only if Σ * /≡ φ ∈ V.

Proof. Let us denote by s the stability index of φ.

The equivalence relation ≡ φ is a congruence because given u, v ∈ Σ * verifying u ≡ φ v, for all α, β ∈ Σ * , we have αuβ ≡ φ αvβ since for any x, y ∈ Σ ≥s , it holds that φ(xαuβy) = φ(xαvβy) because xα, βy ∈ Σ ≥s . Furthermore, this congruence is of finite index because for all u, v ∈ Σ * , we have that φ(u) = φ(v) implies u ≡ φ v.

Let now V be a variety of monoids. Assume first that Σ * /≡ φ ∈ V. It is quite direct to see that φ ∈ EV, as the stamp µ : Σ * → Σ * /≡ φ defined by µ(w) = [w] ≡φ for all w ∈ Σ * witnesses this fact. Assume then that φ ∈ EV. This means that there exists a stamp µ : Σ * → N with N ∈ V such that for all u, v ∈ Σ * , we have

µ(u) = µ(v) ⇒ φ(xuy) = φ(xvy) ∀x, y ∈ Σ s . Now consider u, v ∈ Σ * such that µ(u) = µ(v).
For any x, y ∈ Σ ≥s , we have that x = x 1 x 2 with x 1 ∈ Σ * and x 2 ∈ Σ s as well as y = y 1 y 2 with y 1 ∈ Σ s and y 2 ∈ Σ * , so that φ(xuy) = φ(x 1 )φ(x 2 uy 1 )φ(y 2 ) = φ(x 1 )φ(x 2 vy 1 )φ(y 2 ) = φ(xvy). Hence, u ≡ φ v. Therefore, for all u, v ∈ Σ * , we have that µ(u) = µ(v) implies u ≡ φ v, so we can define the mapping α : N → Σ * /≡ φ such that α(µ(w)) = [w] ≡φ for all w ∈ Σ * . It is easy to check that α is actually a surjective morphism. Thus, we can conclude that Σ * /≡ φ , which divides N , belongs to V. ◀

Using this characterisation, we prove that given a set of identities ne-defining ⟨V⟩ all for a variety of monoids V, we get a set of identities ne-defining EV.

▶ Proposition 6. Let V be a variety of monoids and let E be a set of identities such that ⟨V⟩ all = [[E]] ne . Then EV is an ne-variety of stamps and

EV = [[x ω yuzt ω = x ω yvzt ω | u = v ∈ E, x, y, z, t / ∈ alph(u) ∪ alph(v)]] ne . Proof. Let F = {x ω yuzt ω = x ω yvzt ω | u = v ∈ E, x, y, z, t / ∈ alph(u) ∪ alph(v)} .
Central to the proof is the following claim.

▷ Claim 7. Let φ : Σ * → M be a stamp. Consider the stamp µ : Σ * → Σ * /≡ φ defined by µ(w) = [w] ≡φ for all w ∈ Σ * . It holds that for all u, v ∈ Σ * ,

µ(u) = µ(v) ⇔ φ(α ω βuγδ ω ) = φ(α ω βvγδ ω ) ∀α, β, γ, δ ∈ Σ + .
Before we prove Claim Let us consider any identity x ω yuzt ω = x ω yvzt ω ∈ F . It is written on an alphabet B that is the union of the alphabet A on which u = v ∈ E is written and of x, y, z, t ∈ B \ A. Let f : B * → Σ * be an ne-morphism. Since µ ∈ ⟨V⟩ all , we have that µ ne-satisfies the identity u = v, so that µ( f (u)) = µ( f (v)). Notice that we have that f

(x ω ) = f (x) ω as well because [u k ] ≡φ = µ(u) = µ(v) = [v k ] ≡φ . Thus, we have that φ(α ω βuγδ ω ) = φ(α ω βvγδ ω ) for all α, β, γ, δ ∈ Σ + .
Assume then that φ(α ω βuγδ ω ) = φ(α ω βvγδ ω ) for all α, β, γ, δ ∈ Σ + . Take any α, β ∈ Σ ≥s . Since φ(Σ s ) is a finite semigroup and verifies that φ(Σ s ) = φ(Σ s ) 2 , by a classical result in finite semigroup theory (see e.g. [14, Chapter 1, Proposition 1.12]), we have that there exist α 1 , e, f, β 2 ∈ Σ s and α 2 , β 1 ∈ Σ ≥s such that φ(α 1 eα 2 ) = φ(α) and φ(β 1 f β 2 ) = φ(β) with φ(e) and φ(f ) idempotents. Now, since φ(e) is idempotent, we have that

φ(e ω ) = φ( lim n→∞ e n! ) = lim n→∞ φ(e n! ) = lim n→∞ φ(e) n! = φ(e)
and similarly, φ(f ω ) = φ(f ). So it follows that

φ(αu k β) = φ(α 1 eα 2 u k β 1 f β 2 ) = φ(α 1 e ω α 2 uβ 1 f ω β 2 ) = φ(α 1 e ω α 2 vβ 1 f ω β 2 ) = φ(α 1 eα 2 v k β 1 f β 2 ) = φ(αv k β) .
As this is true for any α, β ∈ Σ ≥s , by definition it holds that

u k ≡ φ v k , hence µ(u) = µ(u k ) = µ(v k ) = µ(v). ◁
This concludes the proof of the proposition. ◀

Essentially-V stamps and the join of V and LI

In this section, we establish the link between essentially-V stamps and V ∨ LI and give a criterion that characterises exactly when they do correspond. More precisely, consider the following criterion for a variety of monoids V.

▶ Criterion (A). For any L ∈ L(V)(Σ) with Σ an alphabet, we have xLy ∈ L(V ∨ LI)(Σ) for all x, y ∈ Σ * .

It is a kind of mild closure condition that appears to be a sufficient and necessary condition for EV and V ∨ LI to correspond.

▶ Proposition 8. Let V be a variety of monoids. Then ⟨V ∨ LI⟩ ne ⊆ EV and equality holds if and only if V verifies criterion (A).

Why this proposition is useful to give characterisations of V ∨ LI in terms of identities will become clear in the next section. For now, we focus on its proof, that entirely relies on the following characterisation of the languages recognised by essentially-V stamps.

▶ Proposition 9. Let V be a variety of monoids. For any alphabet Σ, the set L(EV)(Σ) consists of all Boolean combinations of languages of the form xLy for L ∈ L(V)(Σ) and x, y ∈ Σ * .

Proof. Let C be the class of languages such that for any alphabet Σ, the set C(Σ) consists of all Boolean combinations of languages of the form xLy for L ∈ L(V)(Σ) and x, y ∈ Σ * .

Let Σ be an alphabet. We need to show that L(EV)(Σ) = C(Σ).

Inclusion from right to left. Let L ∈ L(V)(Σ) and x, y ∈ Σ * . Let µ : Σ * → N be the syntactic morphism of L: this implies that N ∈ V and that there exists F ⊆ N such that L = µ -1 (F ). Let also φ : Σ * → M be the syntactic morphism of the language xLy = xΣ * y ∩ Σ |x| µ -1 (F )Σ |y| and let s be its stability index. We then consider u, v ∈ Σ * such that µ(u) = µ(v). Take any x ′ , y ′ ∈ Σ * such that |x ′ | ≥ |x| and |y ′ | ≥ |y|. We clearly have that x ′ uy ′ ∈ xΣ * y if and only if x ′ vy ′ ∈ xΣ * y. Moreover,

x ′ = x ′ 1 x ′ 2 for x ′ 1 ∈ Σ |x| and x ′ 2 ∈ Σ * and y ′ = y ′ 1 y ′ 2 for y ′ 1 ∈ Σ * and y ′ 2 ∈ Σ |y| , so that x ′ uy ′ ∈ Σ |x| µ -1 (F )Σ |y| ⇔ µ(x ′ 2 uy ′ 1 ) ∈ F ⇔ µ(x ′ 2 vy ′ 1 ) ∈ F ⇔ x ′ vy ′ ∈ Σ |x| µ -1 (F )Σ |y| . Hence, x ′ uy ′ ∈ xLy if and only if x ′ vy ′ ∈ xLy for all x ′ , y ′ ∈ Σ * such that |x ′ | ≥ |x| and |y ′ | ≥ |y|,
so that, by definition of the stability index s of φ and as φ is the syntactic morphism of xLy, we have φ(x ′ uy ′ ) = φ(x ′ vy ′ ) for all x ′ , y ′ ∈ Σ s . Thus, it follows that φ ∈ EV.

This implies that xLy ∈ L(EV)(Σ). Therefore, since this is true for any L ∈ L(V)(Σ) and x, y ∈ Σ * and since L(EV)(Σ) is closed under Boolean operations, we can conclude that C(Σ) ⊆ L(EV)(Σ).

Inclusion from left to right. Let L ∈ L(EV)(Σ) and let φ : Σ * → M be its syntactic morphism: it is an essentially-V stamp. Given s its stability index, this means there exists a stamp µ : Σ * → N with N ∈ V such that for all u, v ∈ Σ * , we have

µ(u) = µ(v) ⇒ φ(xuy) = φ(xvy) ∀x, y ∈ Σ s .
For each m ∈ N and x, y ∈ Σ s consider the language xµ -1 (m)y. For any two words w, w ′ ∈ xµ -1 (m)y, we have w = xuy and w ′ = xvy with µ(u) = µ(v) = m, so that φ(w) = φ(w ′ ). By definition of the syntactic morphism, this means that for all m ∈ N and x, y ∈ Σ s , either xµ -1 (m)y ⊆ L or xµ -1 (m)y ∩ L = ∅. Therefore, there exists a set

E ⊆ N × Σ s × Σ s such that L ∩ Σ ≥2s = (m,x,y)∈E xµ -1 (m)y, hence L = (m,x,y)∈E xµ -1 (m)y ∪ F for a certain F ⊆ Σ <2s .
Take w ∈ F . We have that {w} = wΣ * ∩ a∈Σ (Σ * \ waΣ * ) with Σ * ∈ L(V)(Σ). Thus, the singleton language {w} belongs to C(Σ) and since this is true for any w ∈ F and F is finite, we can deduce from this that F is in C(Σ), as the latter is trivially closed under Boolean operations. Now, for all m ∈ N , the language µ -1 (m) belongs to L(V)(Σ), so we finally have L ∈ C(Σ). This is true for any L ∈ L(EV)(Σ), so in conclusion, L(EV)(Σ) ⊆ C(Σ). ◀ Proposition 8 then follows from the two next lemmata, that are both easy consequences of Proposition 9. For completeness, we give the proofs in the appendix. ▶ Lemma 10. Let V be a variety of monoids. Then ⟨V ∨ LI⟩ ne ⊆ EV.

▶ Lemma 11. Let V be a variety of monoids. Then EV ⊆ ⟨V ∨ LI⟩ ne if and only if V verifies criterion (A).

Applications

In this last section, we use the link between essentially-V stamps and V ∨ LI to reprove some characterisations of joins between LI and some well-known varieties of monoids in terms of identities.

One thing seems at first glance a bit problematic about proving that a variety of monoids V satisfies criterion (A). Indeed, to this end, one needs to prove that certain languages belong to L(V ∨ LI); however, this poses a problem when one's goal is precisely to characterise V ∨ LI, because one shall a priori not know more about L(V ∨ LI) than what is given by Proposition 2. Nevertheless, there is a natural sufficient condition for criterion (A) to hold that depends only on L(V): if given any language L ∈ L(V)(Σ) and any x, y ∈ Σ * with Σ an alphabet, there exists a language K ∈ L(V)(Σ) such that L is equal to the quotient x -1 Ky -1 , then V verifies criterion (A). We don't know whether this quotient-expressibility condition that solely depends on the variety V (without explicit reference to LI) is actually equivalent to it satisfying criterion (A), but we can prove such an equivalence for a weaker quotient-expressibility condition for V. The proof is to be found in the appendix.

▶ Proposition 12. Let V be a variety of monoids. Then V satisfies criterion (A) if and only if for any L ∈ L(V)(Σ) and any x, y ∈ Σ * with Σ an alphabet, there exist k, l ∈ N such that for all u ∈ Σ k , v ∈ Σ l , there exists a language K ∈ L(V)(Σ) verifying

u -1 Lv -1 = (xu) -1 K(vy) -1 .
This quotient-expressibility condition appears to be particularly useful to prove that a variety of monoids V does not satisfy criterion (A) without needing to understand what L(V ∨ LI) is. We demonstrate this for the variety of finite commutative and idempotent monoids J 1 .

▶ Proposition 13. J 1 does not satisfy criterion (A).

Proof. Given an alphabet Σ, the set L(J 1 )(Σ) consists of all Boolean combinations of languages of the form Σ * aΣ * for a ∈ Σ (see [START_REF] Pin | Varieties of Formal Languages[END_REF]Chapter 2,Proposition 3.10]).

Let L = {a, b} * b{a, b} * ∈ L(J 1 )({a, b}) and x = b, y = ε. Take any k, l ∈ N and set u = a k and v = a l . Consider a K ∈ L(J 1 )({a, b}). We have that xuavy ∈ K ⇔ xuabvy ∈ K so that a ∈ (xu) -1 K(vy) -1 ⇔ ab ∈ (xu) -1 K(vy) -1 . But a / ∈ u -1 Lv -1 and ab ∈ u -1 Lv -1 , hence u -1 Lv -1 ̸ = (xu) -1 K(vy) -1 and this holds for any choice of K. So for any k, l ∈ N, there exists u ∈ Σ k , v ∈ Σ l such that no K ∈ L(J 1 )({a, b}) verifies u -1 Lv -1 = (xu) -1 K(vy) -1 .

In conclusion, by Proposition 12, J 1 does not satisfy criterion (A). ◀

We now prove the announced characterisations of joins between LI and some well-known varieties of monoids in terms of identities. ▶ Theorem 14. We have the following.

⟨R ∨ LI⟩

ne = ER = [[x ω y(ab) ω azt ω = x ω y(ab) ω zt ω ]] ne . 2. ⟨L ∨ LI⟩ ne = EL = [[x ω yb(ab) ω zt ω = x ω y(ab) ω zt ω ]] ne . 3. ⟨J ∨ LI⟩ ne = EJ = [[x ω y(ab) ω azt ω = x ω y(ab) ω zt ω , x ω yb(ab) ω zt ω = x ω y(ab) ω zt ω ]] ne .

⟨H ∨ LI⟩ ne = EH for any variety of groups H.

Proof. In each case, we prove that the variety of monoids under consideration satisfies criterion (A) using Proposition 12. We then use Propositions 8 and 6.

Proof of 1.

It is well-known that given an alphabet Σ, the set L(R)(Σ) consists of all languages that are disjoint unions of languages that are of the form [START_REF] Pin | Varieties of Formal Languages[END_REF]Chapter 4,Theorem 3.3]).

A * 0 a 1 A * 1 • • • a k A * k where k ∈ N, a 1 , . . . , a k ∈ Σ, A 0 , A 1 , . . . , A k ⊆ Σ and a i / ∈ A i-1 for all i ∈ [k] (see
Let Σ be an alphabet and take a language

A * 0 a 1 A * 1 • • • a k A * k where k ∈ N, a 1 , . . . , a k ∈ Σ, A 0 , A 1 , . . . , A k ⊆ Σ and a i / ∈ A i-1 for all i ∈ [k]
. Take x, y ∈ Σ * . Observe that y can be uniquely written as y = zt where z ∈ A * k and t ∈ {ε} ∪ (Σ \ A k )Σ * . We have

A * 0 a 1 A * 1 • • • a k A * k = x -1 xA * 0 a 1 A * 1 • • • a k A * k t ∩ v∈A <|z| k (Σ * \ xA * 0 a 1 A * 1 • • • a k vt) y -1 using the convention that xA * 0 a 1 A * 1 • • • a k vt = xvt for all v ∈ A <|z| k when k = 0. The language xA * 0 a 1 A * 1 • • • a k A * k t∩ v∈A <|z| k (Σ * \xA * 0 a 1 A * 1 • • • a k vt) does belong to the set L(R)(Σ)
because the latter is closed under Boolean operations and by definition of z and t. Thus, we can conclude that for each L ∈ L(R)(Σ) and x, y ∈ Σ * , there exists K ∈ L(R)(Σ) such that L = x -1 Ky -1 by using the characterisation of L(R)(Σ), the fact that quotients commute with unions [14, p. 20] and closure of L(R)(Σ) under unions.

Proof of 2.

It is also well-known that given an alphabet Σ, the set L(L)(Σ) consists of all languages that are disjoint unions of languages that are of the form

A * 0 a 1 A * 1 • • • a k A * k where k ∈ N, a 1 , . . . , a k ∈ Σ, A 0 , A 1 , . . . , A k ⊆ Σ and a i / ∈ A i for all i ∈ [k] (see [14, Chapter 4, Theorem 3.4]
). The proof is then dual to the previous case.

Proof of 3.

Given an alphabet Σ, for each k ∈ N, we define the equivalence relation ∼ k on Σ * by u ∼ k v for u, v ∈ Σ * whenever u and v have the same set of subwords of length at most k. This relation is a congruence of finite index on Σ * . Simon proved [START_REF] Simon | Piecewise testable events[END_REF] that a language belongs to L(J)(Σ) if and only it is equal to a union of ∼ k -classes for a k ∈ N.

Let Σ be an alphabet and take L ∈ L(J)(Σ) as well as x, y ∈ Σ * . Thus, there exists k ∈ N such that L is a union of ∼ k -classes. Define the language K = w∈L [xwy] ∼ |xy|+k : it belongs to L(J)(Σ) by construction. We now show that L = x -1 Ky -1 , which concludes the proof. Let w ∈ L: we have that xwy ∈ [xwy] ∼ |xy|+k ⊆ K, so that w ∈ x -1 Ky -1 . Let conversely w ∈ x -1 Ky -1 . This means that xwy ∈ K, which implies that there exists w ′ ∈ L such that xwy ∼ |xy|+k xw ′ y. Actually, it holds that any u ∈ Σ * of length at most k is a subword of w if and only if it is a subword of w ′ , because xuy is a subword of xwy if and only if it is a subword of xw ′ y. Hence, w ∼ k w ′ , which implies that w ∈ L.

Proof of 4.

Consider any variety of groups H. Take a language L ∈ L(H)(Σ) for an alphabet Σ and let x, y ∈ Σ * . Consider the syntactic morphism η : Σ * → M of L: we have that M is a group in H. Define the language K = η -1 η(x)η(L)η(y) : it belongs to L(H)(Σ). We now show that L = x -1 Ky -1 , which concludes the proof. Let w ∈ L: we have that η(xwy) ∈ η(x)η(L)η(y), so that w ∈ x -1 Ky -1 . Conversely, let w ∈ x -1 Ky -1 . We have that xwy ∈ K, which means that η(xwy) = η(x)η(w ′ )η(y) for a w ′ ∈ L, so that η(w) = η(w ′ ) ∈ η(L), as any element in M is invertible. Thus, w ∈ L. ◀

Conclusion

The general method presented in this paper actually allows to reprove in a straightforward language-theoretic way even more characterisations of the join of LI with some variety of finite monoids. This can for instance be done for the variety of finite commutative monoids Com or the variety of finite commutative aperiodic monoids ACom.

In fact, as already observed in some sense by Costa [START_REF] Carlos | Some pseudovariety joins involving locally trivial semigroups[END_REF], many varieties of finite monoids seem to verify criterion (A). The main question left open by this present work is to understand better what exactly those varieties are. Another question left open is whether Proposition 12 can be refined by using the stronger quotient-expressibility condition alluded to before the statement of the proposition. The answers to both questions are unclear to the author, but making progress on them may also lead to a better understanding of joins of varieties of finite monoids with LI. uΣ * and Σ * u belong to L(LI)(Σ). Thus, as L(EV)(Σ) is closed under Boolean operations, it follows that L(LI)(Σ) ⊆ L(EV)(Σ).

This concludes the proof, since it holds for any alphabet Σ. ◀ Proof of Lemma 11. Assume that EV ⊆ ⟨V ∨ LI⟩ ne . For any L ∈ L(V)(Σ) and any x, y ∈ Σ * with Σ an alphabet, by Proposition 9, we have that xLy ∈ L(EV)(Σ) ⊆ L(V ∨ LI)(Σ). Hence, V verifies criterion (A). Conversely, assume that V verifies criterion (A). For any alphabet Σ, the set L(V ∨ LI)(Σ) contains all languages of the form xLy for L ∈ L(V)(Σ) and x, y ∈ Σ * , so it contains all Boolean combinations of languages of that form, since it is closed under Boolean operations. Therefore, by Proposition 9, we have L(EV) ⊆ L(V ∨ LI), so that EV ⊆ ⟨V ∨ LI⟩ ne . ◀ Proof of Proposition 12. Let us first observe that given any alphabet Σ, given any language K on that alphabet and given any two words x, y ∈ Σ * , we have that x(x -1 Ky -1 )y = xΣ * y ∩ K and x -1 (xKy)y -1 = K.

Implication from right to left. Assume that for any L ∈ L(V)(Σ) and any x, y ∈ Σ * with Σ an alphabet, there exist k, l ∈ N such that for all u ∈ Σ k , v ∈ Σ l , there exists a language K ∈ L(V)(Σ) verifying u -1 Lv -1 = (xu) -1 K(vy) -1 . Take L ∈ L(V)(Σ) for an alphabet Σ and take x, y ∈ Σ * . Consider also k, l ∈ N that are guaranteed to exist by the assumption we just made. For all u ∈ Σ k , v ∈ Σ l , there exists a language K ∈ L(V)(Σ) verifying u -1 Lv -1 = (xu) -1 K(vy) -1 , so that by our observation at the beginning of the proof, we have Implication from left to right. Assume that V satisfies criterion (A). Take L ∈ L(V)(Σ) for an alphabet Σ and take x, y ∈ Σ * . By hypothesis, we know that xLy ∈ L(V ∨ LI)(Σ).

By Proposition 2, this means that xLy is a Boolean combination of languages in L(V)(Σ)∪ L(LI)(Σ). Further, this implies that xLy can be written as the union of intersections of languages of L(V)(Σ) and L(LI)(Σ) or their complements, which in turn implies, by closure of L(V)(Σ) and L(LI)(Σ) under Boolean operations, that xLy can be written as a finite union of languages of the form K ∩ (U Σ * V ∪ W ) with K ∈ L(V)(Σ) and U, V, W ⊆ Σ * finite. Since any word in xLy must be of length at least |xy| and have x as a prefix and y as a suffix, we can assume that any language K ∩ (U Σ * V ∪ W ) appearing in a finite union as described above verifies that U ⊆ xΣ * , that V ⊆ Σ * y and that W ⊆ xΣ * y. Now, if we take k, l ∈ N big enough, we thus have that

xLy = u∈Σ k ,v∈Σ l (K u,v ∩ xuΣ * vy) ∪ F
where K u,v ∈ L(V)(Σ) for all u ∈ Σ k , v ∈ Σ l and F ⊆ Σ <|xy|+k+l . Hence, for all u ∈ Σ k , v ∈ Σ l , we have

u -1 Lv -1 = u -1 x -1 (xLy)y -1 v -1 = (xu) -1 u ′ ∈Σ k ,v ′ ∈Σ l (K u ′ ,v ′ ∩ xu ′ Σ * v ′ y) ∪ F (vy) -1 = u ′ ∈Σ k ,v ′ ∈Σ l (xu) -1 xu ′ (xu ′ ) -1 K u ′ ,v ′ (v ′ y) -1 v ′ y (vy) -1 ∪ (xu) -1 F (vy) -1
= (xu) -1 K u,v (vy) -1 , using classical formulae for quotients [14, p. 20] and observing that (xu) -1 K(vy) -1 = ∅ for any K ⊆ Σ * such that K ∩ xuΣ * vy = ∅. ◀

7 ,

 7 we use it to prove that EV = [[F ]] ne . Inclusion from left to right. Let φ : Σ * → M be a stamp in EV. Consider the stamp µ : Σ * → Σ * /≡ φ defined by µ(w) = [w] ≡φ for all w ∈ Σ * . Since φ ∈ EV, Proposition 5 tells us that Σ * /≡ φ ∈ V, hence µ ∈ ⟨V⟩ all .

  x(uΣ * v ∩ L)y = xu(u -1 Lv -1 )vy = xu (xu) -1 K(vy) -1 vy = xuΣ * vy ∩ K .Using Proposition 2, we thus have that x(uΣ* v ∩ L)y ∈ L(V ∨ LI)(Σ) for all u ∈ Σ k , v ∈ Σ l .Moreover, since we have that the set of words of L of length at least k + l isΣ ≥k+l ∩ L = u∈Σ k ,v∈Σ l (uΣ * v ∩ L)and sinceL = (Σ ≥k+l ∩ L) ∪ Fwhere F is a finite set of words on Σ of length less than k + l, we have thatxLy = x (Σ ≥k+l ∩ L) ∪ F y = u∈Σ k ,v∈Σ l x(uΣ * v ∩ L)y ∪ xF y .We can thus conclude that xLy ∈ L(V ∨ LI)(Σ) since xF y ∈ L(LI)(Σ) and because L(V ∨ LI)(Σ) is closed under unions.

as f (t ω ) = f (t) ω and that f (x), f (y), f (z), f (t) ∈ Σ + because f is non-erasing. Therefore, we have

by Claim 7. As this holds for any ne-morphism f : B * → Σ * , we can conclude that φ ne-satisfies the identity x ω yuzt ω = x ω yvzt ω . This is true for any identity in

Inclusion from right to left. Let φ : Σ * → M be a stamp in [[F ]] ne . Consider the stamp µ : Σ * → Σ * /≡ φ defined by µ(w) = [w] ≡φ for all w ∈ Σ * . We are now going to show that µ ∈ ⟨V⟩ all . Take any identity u = v ∈ E written on an alphabet A. There exists an identity

Take any α, β, γ, δ ∈ Σ + . Let us define the ne-morphism g : B * → Σ * as the unique one which extends f by letting g(x) = α, g(y) = β, g(z) = γ and g(t) = δ. Observe in particular that g(w) = f (w) for any w ∈ A * and that g(x ω ) = g(x) ω = α ω as well as g(t ω ) = δ ω . Now, as φ ne-satisfies x ω yuzt ω = x ω yvzt ω , we have that

Since this holds for any α, β, γ, δ ∈ Σ + , by Claim 7, we have that µ( f

Therefore, µ( f (u)) = µ( f (v)) for any ne-morphism f : A * → Σ * , which means that µ ne-satisfies u = v.

Since this holds for any u = v ∈ E, we have that µ ∈ ⟨V⟩ all , which implies that Σ * /≡ φ ∈ V and thus φ ∈ EV by Proposition 5. In conclusion, [[F ]] ne ⊆ EV.

The claim still needs to be proved.

Proof of Claim 7. Let φ : Σ * → M be a stamp of stability index s. Consider the stamp µ : Σ * → Σ * /≡ φ defined by µ(w) = [w] ≡φ for all w ∈ Σ * . We now want to show that for all u, v ∈ Σ * ,

Let u, v ∈ Σ * . There exist two Cauchy sequences (u n ) n≥0 and (v n ) n≥0 in Σ * such that u = lim n→∞ u n and v = lim n→∞ v n . As Σ * /≡ φ and M are discrete, we have that all four Cauchy sequences µ

Assume first that µ(u) = µ(v). Take any α, β, γ, δ ∈ Σ + . Since M is discrete, both Cauchy sequences φ(α n! ) n≥0 and φ(δ n! ) n≥0 are ultimately constant. So there exists l ∈ N such that for all m ∈ N, m ≥ l, we have φ(α ω ) = φ(α m! ) and φ(δ ω ) = φ(δ m! ). Hence, taking m ∈ N, m ≥ l such that α m! β ≥ s and γδ m! ≥ s, it follows that φ(α ω βuγδ ω ) = φ(α m! βu k γδ m! ) = φ(α m! βv k γδ m! ) = φ(α ω βvγδ ω )