Clément Mouhot De

Giorgi-Nash-Moser De

H And

Örmander

Mouhot

Clément Mouhot
email: c.mouhot@dpmms.cam.ac.uk

come

1. Introduction 1.1. Kinetic theory. Modern physics goes back to Newton and classical mechanics, and was later expanded into the understanding of electric and magnetic forces were (Ampère, Faraday, Maxwell), large velocities and large scales (Lorentz, Poincaré, Minkowski, Einstein), small-scale particle physics and quantum mechanics (Planck, Einstein, Bohr, Heisenberg, Born, Jordan, Pauli, Fermi, Schrödinger, Dirac, De Broglie, Bose, etc.). However, all these theories are classically devised to study one physical system (planet, ship, motor, battery, electron, spaceship, etc.) or a small number of systems (planets in the Solar system, electrons in a molecule, etc.) In many situations though, one needs to deal with an assembly made up of elements so numerous that their individual tracking is not possible: galaxies made of hundreds of billions of stars, fluids made of more than 10 20 molecules, crowds made of thousands of individuals, etc. Taking such large numbers into account leads to new effective laws of physics, requiring different models and concepts. This passage from microscopic rules to macroscopic laws is the founding principle of statistical physics. All branches of physics (classical, quantum, relativistic, etc.) can be studied from the point of view of statistical physics, in both stationary and dynamical perspectives. It was first done with the laws of classical mechanics, which resulted in kinetic theory, discovered by Maxwell [START_REF] Maxwell | On the dynamical theory of gases[END_REF] and Boltzmann [START_REF] Boltzmann | Weitere studien über das wärmegleichgewicht unter gasmolekülen[END_REF] in the 19th century after precursory works by D. Bernoulli, Herapath, Waterston, Joule, König, Clausius.

Kinetic theory replaces a huge number of objects, whose physical states are described by a certain phase space, and whose properties are otherwise identical, by a statistical distribution over that phase space. The fundamental role played by the velocity (kinetic) variable inaccessible to observation was counter-intuitive, and accounts for the denomination of kinetic theory. The theory introduces a distinction between three scales: the macroscopic scale of phenomena which are accessible to observation; the microscopic scale of molecules and infinitesimal constituents; and an intermediate scale, loosely defined and often called mesoscopic. This is the scale of phenomena which are not accessible to macroscopic observation but already involve a large number of particles, so that statistical effects are significant.

1.2. Main equations of kinetic theory. Maxwell wrote the first (weak) form of the evolution equation known now as the Boltzmann equation: the unknown is a (nonnegative) density function f (t, x, v), standing for the density of particles at time t in the phase space (x, v); the equation, in modern writing and assuming the absence of external forces, is

(1.1) ∂f ∂t + v • ∇ x f = Q(f, f ).
The left-hand side describes the evolution of f under the action of transport, with the free streaming operator. The right-hand side describes elastic collisions, with the nonlinear a function of the angular variable: this is a general feature of long-range interactions, nowadays sometimes called "non-cutoff property". The case α = 5, γ = 0 and 2s = 1/2 is called Maxwell molecules [START_REF] Maxwell | On the dynamical theory of gases[END_REF], the case α ∈ (5, +∞), γ > 0 and 2s ∈ (0, 1/2) is called hard potentials (without cutoff ), the case α ∈ [START_REF] Alexandre | Entropy dissipation and long-range interactions[END_REF][START_REF] Alexandre | Littlewood-Paley theory and regularity issues in Boltzmann homogeneous equations. II. Non cutoff case and non Maxwellian molecules[END_REF], γ ∈ [-1, 0), 2s ∈ (1/2, 1] is called moderately soft potentials (without cutoff ), and finally the case α ∈ (2, 3), γ ∈ (-3, -1), 2s ∈ (1, 2) is called very soft potentials (without cutoff ). The limits between hard and soft potentials (γ = 0) and between moderately and very soft potentials (γ + 2s = 0) are commonly taken as defining the "hard" / "moderately soft" / "very soft" terminology in any dimension, for kernel of the form

B = |v -v * | γ b(cos θ) with b(cos θ) ≃ θ -(1+2s) .
In order to find the stationary solutions, that is, time-independent solutions of (1.2), the first step is to identify particular hydrodynamic density functions, which make the collision contribution vanish: these are Gaussian distributions with a scalar co-variance

f (v) = ρ (2πT ) -3/2 e -|v-u| 2 2T
, where the parameters ρ > 0, u ∈ R 3 and T > 0 are the local density, mean velocity, and temperature of the fluid. These parameters can be fixed throughout the whole domain (providing in this case an equilibrium distribution), or depend on the position x and time t; in both cases collisions will have no effect. As pointed out in Maxwell's seminar paper, and later proved rigorously at least in some settings [START_REF] Bardos | Fluid dynamic limits of kinetic equations. I. Formal derivations[END_REF][START_REF] Bardos | Fluid dynamic limits of kinetic equations. II. Convergence proofs for the Boltzmann equation[END_REF][START_REF] Golse | The Navier-Stokes limit of the Boltzmann equation for bounded collision kernels[END_REF][START_REF] Golse | Hydrodynamic limits for the Boltzmann equation[END_REF][START_REF] Golse | The incompressible Navier-Stokes limit of the Boltzmann equation for hard cutoff potentials[END_REF], the Boltzmann equation is connected to classical fluid mechanical equations on ρ, u and T , and leads to them in certain regimes. This provides a rigorous connection between the mesoscopic (kinetic) level and the macroscopic level. At the other end of the scales, a rigorous derivation of the Boltzmann equation from manybody Newtonian mechanics for short time and short-range interactions was obtained by Lanford [START_REF] Lanford | Time evolution of large classical systems[END_REF] for hard spheres; see also [START_REF] King | BBGKY hierarchy for positive potentials[END_REF] for an extension to more general shortrange interactions, and the recent works [START_REF] Gallagher | From Newton to Boltzmann: hard spheres and short-range potentials[END_REF][START_REF] Pulvirenti | On the validity of the Boltzmann equation for short range potentials[END_REF] that revisit and complete the initial arguments of Lanford and King. Note however that at the moment the equivalent of Lanford theorem for the Boltzmann equation with long-range interactions is still missing, see [START_REF] Ayi | From Newton's law to the linear Boltzmann equation without cut-off[END_REF] for partial progresses.

To summarise the key mathematical points: the Boltzmann equation is an integro-(partial)-differential equation with non-local operator in the kinetic variable v. Moreover for long-range interactions with repulsive force F (r) ∼ r -α , this non-local operator has a singular kernel and shows, as we will see, fractional ellipticity of order 2/(α -1). The Boltzmann equation "contains" the hydrodynamic, and it is a fundamental equation in the sense that it is derived rigorously, at least in some settings, from microscopic first principles. From now on, we consider the position variable in R 3 or in the periodic box T 3 .

In the limit case s → 1 (the Coulomb interactions), the Boltzmann collision operator is ill-defined. Landau [START_REF] Landau | Translation: The transport equation in the case of Coulomb interactions[END_REF] proposed an alternative operator for these Coulomb interactions that is now called the Landau-Coulomb operator

Q(f, f ) = ∇ v • ˆR3 P (v-v * ) ⊥ f (t, x, v * )∇ v f (t, x, v) -f (t, x, v)∇ v f (t, x, v * ) |v -v * | γ+2 dv * where P (v-v * ) ⊥ is the orthogonal projection along (v -v * ) ⊥ and γ = -3. It writes also Q(f, f ) = ∇ v • A[f ]∇ v f + B[f ]f (1.3) with        A[f ](v) = ˆR3 I - w |w| ⊗ w |w| |w| γ+2 f (t, x, v -w) dw, B[f ](v) = - ˆR3 |w| γ w f (t, x, v -w) dw.
This operator is a nonlinear drift-diffusion operator with coefficients given by convolutionlike averages of the unknown. This is a non-local integro-differential operator, with second-order local ellipticity. The resulting Landau equation (1.1)-(1.3) again "contains" the hydrodynamic. It is also considered fundamental because of its closed link to the Boltzmann equation for Coulomb interactions (note however that the equivalent to Lanford theorem for the Landau equation is lacking, even at a formal level, see [START_REF] Bobylev | From particle systems to the Landau equation: a consistency result[END_REF] for partial progresses). Because of the difficulty to handle the very singular kernel of the Landau-Coulomb operator, it is common to introduce artificially a scale of models by letting γ vary in [-3, 1] (or even [-d, 1] in general dimension d). The terminology hard potentials, Maxwell molecules, soft potentials are used as for the Boltzmann collision operator when γ > 0, γ = 0, γ < 0 respectively. The terminology moderately soft potentials corresponds here (since s = 1) to γ ∈ (-2, 0). [START_REF] Gualdani | Factorization for non-symmetric operators and exponential h-theorem[END_REF] and the references therein for some of the most recent results for the Boltzmann equation with short-range interactions, see [START_REF] Alexandre | The Boltzmann equation without angular cutoff in the whole space: I, Global existence for soft potential[END_REF][START_REF] Alexandre | The Boltzmann equation without angular cutoff in the whole space: II, Global existence for hard potential[END_REF][START_REF] Alexandre | Regularizing effect and local existence for the non-cutoff Boltzmann equation[END_REF][START_REF] Alexandre | Global existence and full regularity of the Boltzmann equation without angular cutoff[END_REF][START_REF] Gressman | Global classical solutions of the Boltzmann equation without angular cut-off[END_REF] for the Boltzmann equation with long-range interactions, and see [START_REF] Guo | The Landau equation in a periodic box[END_REF] for the Landau equation. However the construction of solutions "in the large" remains a formidable open problem. Since weak "renormalised" solutions have been constructed by DiPerna and Lions [START_REF] Diperna | On the Cauchy problem for Boltzmann equations: global existence and weak stability[END_REF] that play a similar role to the Leray [START_REF] Leray | Sur le mouvement d'un liquide visqueux emplissant l'espace[END_REF] solutions in fluid mechanics, this open problem can be compared with the millennium problem of the regularity of solutions to 3D incompressible Navier-Stokes equations.

1.3.2. Study of a priori solutions. Given that the Cauchy problem in the large seems out of reach at the moment, Truesdell and Muncaster [START_REF] Truesdell | Fundamentals of Maxwell's kinetic theory of a simple monatomic gas[END_REF] remarked almost 40 years ago that: "Much effort has been spent toward proof that place-dependent solutions exist for all time.

[. . . ] The main problem is really to discover and specify the circumstances that give rise to solutions which persist forever. Only after having done that can we expect to construct proofs that such solutions exist, are unique, and are regular." In other words, the Htheorem and the mathematical understanding of irreversibility are so important in the theory of Maxwell and Boltzmann that it cannot wait for the tremendously difficult issue of global well-posedness to be settled. Cercignani then formulated a precise conjecture along this idea, postulating in [START_REF] Cercignani | H-theorem and trend to equilibrium in the kinetic theory of gases[END_REF] a linear relation between the entropy production functional and the relative entropy functional of any a priori given classical solutions. The resolution of this conjecture, for certain interactions, lead to precise new quantitative information on a priori solutions of the Boltzmann and Landau equation (see [START_REF] Desvillettes | On the trend to global equilibrium for spatially inhomogeneous kinetic systems: the Boltzmann equation[END_REF][START_REF] Desvillettes | Celebrating Cercignani's conjecture for the Boltzmann equation[END_REF][START_REF] Mouhot | Rate of convergence to equilibrium for the spatially homogeneous Boltzmann equation with hard potentials[END_REF][START_REF] Gualdani | Factorization for non-symmetric operators and exponential h-theorem[END_REF][START_REF] Carrapatoso | Landau equation for very soft and Coulomb potentials near Maxwellians[END_REF]). And it lead to the related question of the optimal relaxation rates of a priori solutions, with minimal regularity and moments conditions. It is now fairly well understood for many interactions. The results obtained along this line of research can all be summarised into the following general form:

Conditional relaxation. Any solution to the Boltzmann (resp. Landau) equation in

L ∞ x (T 3 ; L 1 v (R 3 , (1 + |v|) k dv)), k > 2 (
or a closely related functional space as large as possible) converges to the thermodynamic equilibrium with the optimal rate dictated by the linearized equation.

Note however that an interesting remaining open question in this program is to obtain a result equivalent to [START_REF] Gualdani | Factorization for non-symmetric operators and exponential h-theorem[END_REF][START_REF] Carrapatoso | Landau equation for very soft and Coulomb potentials near Maxwellians[END_REF] in the case of the Boltzmann equation with long-range interactions (with fractional ellipticity in the velocity variable). 1.3.3. Regularity conjectures for long-range interactions. In the case of long-range interactions, the Boltzmann and Landau-Coulomb operators show local ellipticity provided the solution enjoys some pointwise bounds on the hydrodynamic fields ρ(t, x) := ´R3 f dv, e(t, x) := ´R3 f |v| 2 dv and the local entropy h(t, x) := ´R3 f ln f dv. Whereas it is clear in the case of the Landau-Coulomb operator, it was understood almost two decades ago in the case of the Boltzmann collision operator [START_REF] Lions | Régularité et compacité pour des noyaux de collision de Boltzmann sans troncature angulaire[END_REF][START_REF] Villani | Regularity estimates via the entropy dissipation for the spatially homogeneous Boltzmann equation without cut-off[END_REF][START_REF] Alexandre | Entropy dissipation and long-range interactions[END_REF]. This had lead colleagues working on non-local operators and fully nonlinear elliptic problems like Silvestre and Guillen and co-authors to attempt to use barriers' techniques reminiscent to the Krylov-Safonov theory [START_REF] Krylov | A property of the solutions of parabolic equations with measurable coefficients[END_REF] in order to obtain pointwise bounds for solutions to these equations. These first attempts, while unsuccessful, later proved crucial in attracting the attention of a larger community on this problem. And these authors rapidly reformulated the initial goal into, again, conditional conjectures on the regularity of the form:

Conditional regularity. Consider any solution to the Boltzmann equation with longrange interactions (resp. Landau equation) on a time interval [0, T ] such that its hydrodynamic fields are bounded:

(1.4) ∀ t ∈ [0, T ], x ∈ T 3 , m 0 ≤ ρ(t, x) ≤ m 1 , e(t, x) ≤ e 1 , h(t, x) ≤ h 1
where m 0 , m 1 , e 1 , h 1 > 0. Then the solution is bounded and smooth on (0, T ].

Note that this conjecture can be strengthened by removing the assumption that the mass is bounded from below and replacing it by a bound from below on the total mass ´T3 ρ(t, x) dx ≥ M 0 > 0. Mixing in velocity through collisions combined with transport effects indeed generate lower bounds in many settings, see [START_REF] Mouhot | Quantitative lower bounds for the full Boltzmann equation. I. Periodic boundary conditions[END_REF][START_REF] Filbet | Analysis of spectral methods for the homogeneous Boltzmann equation[END_REF][START_REF] Briant | Instantaneous filling of the vacuum for the full Boltzmann equation in convex domains[END_REF][START_REF] Briant | Instantaneous exponential lower bound for solutions to the Boltzmann equation with Maxwellian diffusion boundary conditions[END_REF]; moreover it was indeed proved for the Landau equation with moderately soft potentials in [START_REF] Henderson | Local existence, lower mass bounds, and smoothing for the Landau equation[END_REF].

This conjecture is now been partially solved in the case of the Landau equation, when the interaction is "moderately soft" γ ∈ (-2, 0). This result has been the joint efforts of several groups [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF][START_REF] Henderson | ∞ smoothing for weak solutions of the inhomogeneous Landau equation[END_REF][START_REF] Henderson | Local existence, lower mass bounds, and smoothing for the Landau equation[END_REF][START_REF] Imbert | A toy nonlinear model in kinetic theory[END_REF], and this is the object of the next section. It is currently an ongoing program of research in the case of the Boltzmann equation with hard and moderately soft potentials, and this is the object of the fourth and last section. The conjecture interestingly remains open in the case of very soft potentials for both equations, and making progress in this setting is likely to require new conceptual tools.

De Giorgi-Nash-Moser meet Hörmander

2.1. The resolution of Hilbert 19-th problem. The De Giorgi-Nash-Moser theory [START_REF] De Giorgi | analiticità delle estremali degli integrali multipli[END_REF][START_REF] De Giorgi | Sulla differenziabilità e l'analiticità delle estremali degli integrali multipli regolari[END_REF][START_REF] Nash | Continuity of solutions of parabolic and elliptic equations[END_REF][START_REF] Moser | A new proof of De Giorgi's theorem concerning the regularity problem for elliptic differential equations[END_REF][START_REF] Moser | A Harnack inequality for parabolic differential equations[END_REF] was born out of the attempts to answer Hilbert's 19th problem. This problem is about proving the analytic regularity of the minimizers u of an energy functional ˆU L(∇u) dx, with u : R d → R and where the Lagrangian L : R d → R satisfies growth, smoothness and convexity conditions and U ⊂ R d is a compact domain. The Euler-Lagrange equations for the minimizers take the form

∇ • ∇L(∇u) = 0 i.e. d i,j=1 (∂ ij L)(∇u) b ij ∂ ij u = d i,j=1 b ij ∂ ij u = 0.
For instance the Dirichlet energy L(p) = |p| 2 leads to linear Euler-Lagrange equations, whereas the minimal surface energy L(p) = 1 + |p| 2 leads to nonlinear Euler-Lagrange equations. With suitable assumptions on L and the domain, the pointwise control of ∇u was known in the 1950s. However applying the Schauder estimates to get higher regularity requires more information: if u ∈ C 1,α with α > 0 then b ij ∈ C α and Schauder estimates [START_REF] Schauder | über lineare elliptische Differentialgleichungen zweiter Ordnung[END_REF] imply u ∈ C 2,α ; a bootstrap argument then yields higher regularity, and analyticity follows from this C ∞ regularity [START_REF] Bernstein | Sur la nature analytique des solutions des équations aux dérivées partielles du second ordre[END_REF][START_REF] Petrowsky | Sur l'analyticité des solutions des systèmes d'équations différentielles[END_REF].

Hence, apart from specific result in two dimensions [START_REF] Morrey | On the solutions of quasi-linear elliptic partial differential equations[END_REF], the missing piece in solving Hilbert 19th problem, in the 1950s, was the proof of the Hölder regularity of ∇u. The equation satisfied by a derivative f := ∂ k u is the divergence form elliptic equation:

d i,j=1 ∂ i (∂ ij L)(∇u) a ij ∂ j f = ∇ • (A∇f ) = 0.
De Giorgi [START_REF] De Giorgi | Sulla differenziabilità e l'analiticità delle estremali degli integrali multipli regolari[END_REF] and Nash [START_REF] Nash | Continuity of solutions of parabolic and elliptic equations[END_REF] independently proved this Hölder regularity of f under the sole assumption that the symmetric matrix A := (a ij ) satisfies the controls 0 < λ ≤ A ≤ Λ, and is measurable (no regularity is assumed). The proof of Nash uses what is now called the "Nash inequality", an L log L energy estimate, and refined estimates on the fundamental solution. The proof of De Giorgi uses an iterative argument to gain integrability, and an "isoperimetric argument" to control how oscillations decays when refining the scale of observation. Moser later gave an alternative proof [START_REF] Moser | A new proof of De Giorgi's theorem concerning the regularity problem for elliptic differential equations[END_REF][START_REF] Moser | A Harnack inequality for parabolic differential equations[END_REF] based on one hand on an iterative gain of integrability, formulated differently but similar to that of De Giorgi, and on the other hand on relating Lebesgue norms on f and 1/f through energy estimates on the equation satisfied by g := ln f and the use of a Poincaré inequality; the proof of Moser had an important further contribution in that it also proved, as an intermediate step towards the Hölder regularity, the Harnack inequality for the equation considered, i.e. a universal control on the ratio between local maxima and local minima.

Let us mention that the De Giorgi-Nash-Moser (DGNM) theory only considers elliptic or parabolic equations in divergence form. An important counterpart result for nondivergence elliptic and parabolic equations was later discovered by Krylov and Safonov [START_REF] Krylov | A property of the solutions of parabolic equations with measurable coefficients[END_REF]. The extension of the DGNM theory to hypoelliptic equations with rough coefficients that we present in this section requires the equation to be in divergent form. It is an open problem whether the Krylov-Safonov theory extends to hypoelliptic non-divergent equations of the form discussed below.

2.2.

The theory of hypoellipticity. The DGNM theory has revolutionised the study of nonlinear elliptic and parabolic partial differential equations (PDEs). However it remained limited to PDEs where the diffusion acts in all directions of the phase space.

In kinetic theory, as soon as the solution is non spatially homogeneous, the diffusion or fractional diffusion in velocity is combined to a conservative Hamiltonian dynamic in position and velocity. This structure is called hypoelliptic.

The study of regularity properties of such equations can be traced back, at the linear level, to the short note of Kolmogorov [START_REF] Kolmogoroff | Zufällige Bewegungen (zur Theorie der Brownschen Bewegung)[END_REF]. This note considered the combination of free transport with drift-diffusion in velocity: the law satisfies what is now sometimes called the Kolmogorov equation, that writes

∂ t f + v • ∂ x f = ∆ v f on x, v ∈ R d in the simpler case.
It is the equation satisfied by the law of a Brownian motion integrated in time. Kolmogorov then wrote the fundamental solution associated with a Dirac distribution δ x 0 ,v 0 initial data:

G(t, x, v) = √ 3 2πt 2 d exp - 3|x -x 0 -tv 0 -t(v -v 0 )/2| 2 t 3 - |v -v 0 | 2 4t .
The starting point of Hörmander's seminal paper [START_REF] Hörmander | Hypoelliptic second order differential equations[END_REF] is the observation that this fundamental solution shows regularisation in all variables, even though the diffusion acts only in the velocity variable. The regularisation in (t, x) is produced by the interaction between the transport operator v • ∇ x and the diffusion in v. Hörmander's paper then proposes general geometric conditions for this regularisation, called hypoelliptic, to hold, based on commutator estimates. In short, given X 0 , X 1 , . . . , X n a collection of smooth vector fields on R N and the second-order differential operator L = -1 2.3. Extending the DGNM theory to hypoelliptic settings. The main question of interest here is the extension of the DGNM theory to hypoelliptic PDEs of divergent type. Hypoelliptic PDEs of second order L = -1 2 n i=1 X * i X i + X 0 naturally split into two classes: the simpler "type I" when X 0 = 0 and the operator is a sum of squares, and the "type II" such as the Kolmogorov equation above, where X 0 = 0 and the operator combines a first-order anti-symmetric operator with some partially diffusive second-order operator. Two main research groups had already been working on the question.

The extension of the DGNM theory to hypoelliptic operators of "type I" is relatively straightforward. Regarding the "type II", Polidoro and collaborators [START_REF] Polidoro | On a class of ultraparabolic operators of Kolmogorov-Fokker-Planck type[END_REF][START_REF] Lanconelli | On a class of hypoelliptic evolution operators[END_REF][START_REF] Polidoro | A global lower bound for the fundamental solution of Kolmogorov-Fokker-Planck equations[END_REF][START_REF] Manfredini | Interior regularity for weak solutions of ultraparabolic equations in divergence form with discontinuous coefficients[END_REF][START_REF] Polidoro | Hölder regularity for solutions of ultraparabolic equations in divergence form[END_REF][START_REF] Pascucci | The Moser's iterative method for a class of ultraparabolic equations[END_REF][START_REF] Cinti | Pointwise estimates for a class of non-homogeneous Kolmogorov equations[END_REF] had obtained the Hölder regularity for coefficients with various continuity assumptions, and had obtained the improvement of integrability and pointwise bound for measurable coefficients (see also the isolated result [START_REF] Di Francesco | Harnack inequality and Gaussian lower bound for Kolmogorov-type operators in non-divergence form[END_REF] for equations in non-divergence form). Wang and Zhang [START_REF] Wang | The C α regularity of a class of non-homogeneous ultraparabolic equations[END_REF][START_REF] Wang | The C α regularity of weak solutions of ultraparabolic equations[END_REF][START_REF] Zhang | The C α regularity of a class of ultraparabolic equations[END_REF] had extended the proof of Moser for the "type II" equations to obtain Hölder regularity, with technical calculations that did not seem easy to export. Note also that the use of the DGNM theory in kinetic theory had also been advocated almost a decade before in the premonitory lecture notes [START_REF] Villani | Cours Peccot at the Collège de France[END_REF].

We present here the work [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF] (see also the two previous related preprints [START_REF] Golse | Hölder regularity for hypoelliptic kinetic equations with rough diffusion coefficients[END_REF][START_REF] Imbert | Hölder continuity of solutions to hypoelliptic equations with bounded measurable coefficients[END_REF]) that (1) provides an elementary and robust proof of the gain of integrability and Hölder regularity in this "type II" hypoelliptic setting, (2) proves the stronger Harnack inequality for these equations (i.e. a quantitative version of the strong maximum principle).

Let us consider the following kinetic Fokker-Planck equation (2.1)

∂ t f + v • ∇ x f = ∇ v • (A∇ v f ) + B • ∇ v f + s, t ∈ (0, T ), (x, v) ∈ Ω,
where Ω is an open set of R 2d , f = f (t, x, v), B and s are bounded measurable coefficients depending on (t, x, v), and the d × d real matrices A, B and source term s are measurable and satisfy

(2.2) 0 < λI ≤ A ≤ ΛI, |B| ≤ Λ, s essentially bounded
for two constants λ, Λ > 0. Given z 0 = (t 0 , x 0 , v 0 ) ∈ R 2d+1 , we define the "cylinder" Q r (z 0 ) centered at z 0 of radius r that respects the invariances of the equation:

(2.3) Q r (z 0 ) := (t, x, v) ∈ R 2d+1 : |x -x 0 -(t -t 0 )v 0 | < r 3 , |v -v 0 | < r, t ∈ t 0 -r 2 , t 0 .
The weak solutions to equation (2.1) on

I × U x × U v with U x ⊂ R d open, U v ⊂ R d open, I = [a, b] with -∞ < a < b ≤ +∞, are defined as functions f ∈ L ∞ t (I, L 2 x,v (U x × U v ))) ∩ L 2 t,x (I × U x , H 1 v (U v )) such that ∂ t f + v • ∇ x f ∈ L 2 t,x (I × U x , H -1 v (U v )
) and f satisfies the equation (2.1) in the sense of distributions.

Theorem 1 (Hölder continuity [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF]). Let f be a weak solution of (2.1)

in Q 0 := Q r 0 (z 0 ) and let Q 1 := Q r 1 (z 0 ) with r 1 < r 0 . Then f is α-Hölder continuous with respect to (x, v, t) in Q 1 and f C α (Q 1 ) ≤ C f L 2 (Q 0 ) + s L ∞ (Q 0 )
for some α ∈ (0, 1) and C > 0 only depending on d, λ, Λ, r 0 , r 1 (plus z 0 for C).

In order to prove such a result, we first prove that L 2 sub-solutions are locally bounded; we refer to such a result as an L 2 -L ∞ estimate. We then prove that solutions are Hölder continuous by proving a lemma which is a hypoelliptic counterpart of De Giorgi's "isoperimetric lemma".

We moreover prove the Harnack inequality:

Theorem 2 (Harnack inequality [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF]). If f is a non-negative weak solution of (2.1) in Q 1 (0, 0, 0), then

(2.4) sup Q - f ≤ C inf Q + f + s L ∞ (Q 1 (0,0,0))
where Q + := Q R (0, 0, 0) and Q -:= Q R (0, 0, -∆) and C > 1 and R, ∆ ∈ (0, 1) are small (in particular Q ± ⊂ Q 1 (0, 0, 0) and they are disjoint), and universal, i.e. only depend on dimension and ellipticity constants.

Note that using the transformation T z 0 (t, x, v) = (t 0 + t, x 0 + x + tv 0 , v 0 + v), we get a Harnack inequality for cylinders centered at an arbitrary point z 0 = (t 0 , x 0 , v 0 ).

Our proof combines the key ideas of De Giorgi and Moser and the velocity averaging method, which is a special type of smoothing effect for solutions of the free transport equation (∂ t + v • ∇ x )f = S observed for the first time in [START_REF] Agoshkov | Spaces of functions with differential-difference characteristics and the smoothness of solutions of the transport equation[END_REF][START_REF] Golse | Un résultat de compacité pour les équations de transport et application au calcul de la limite de la valeur propre principale d'un opérateur de transport[END_REF] independently, later improved and generalized in [START_REF] Golse | Regularity of the moments of the solution of a transport equation[END_REF][START_REF] Diperna | Global weak solutions of Vlasov-Maxwell systems[END_REF]. This smoothing effect concerns averages of f in the velocity variable v, i.e. expressions of the form ´Rd f (t, x, v) φ(v) dv with, say, φ ∈ C ∞ c . Of course, no smoothing on f itself can be observed, since the transport operator is hyperbolic and propagates the singularities. However, when S is of the form

S = ∇ v • (A(t, x, v)∇ v f ) + s,
where s is a given source term in L 2 , the smoothing effect of velocity averaging can be combined with the H 1 regularity in the v variable implied by the energy inequality in order to obtain some regularity in all directions. A first observation of this type (at the level of a compactness argument) can be found in [START_REF] Lions | On Boltzmann and Landau equations[END_REF]; Bouchut [START_REF] Bouchut | Hypoelliptic regularity in kinetic equations[END_REF] had then obtained quantitative Sobolev regularity estimates.

Our proof of the L 2 -L ∞ gain of integrability follows the so-called "De Giorgi-Moser iteration", see [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF] where it is presented in both the equivalent formulations of De Giorgi and of Moser. We emphasize that, in both approaches, the main ingredient is a local gain of integrability of non-negative sub-solutions. This latter is obtained by combining a comparison principle and a fractional Sobolev regularity estimate following from (1) the velocity averaging method discussed above and (2) energy estimates. We then prove the Hölder continuity through a De Giorgi type argument on the decrease of oscillation for solutions. We also derive the Harnack inequality by combining the decrease of oscillation with a result about how positive lower bounds on non-negative solutions deteriorate with time. It is worth mentioning here that our "hypoelliptic isoperimetric argument" is proved non-constructively, by a contradiction method, whereas the original isoperimetric argument of De Giorgi is obtained by a quantitative direct argument. It is an interesting open problem to obtain such quantitative estimates in the hypoelliptic case.

Conditional regularity of the Landau equation

3.1. Previous works and a conjecture. The infinite smoothing of solutions to the Landau equation has been investigated so far in two different settings. On the one hand, it has been investigated for weak spatially homogeneous solutions (non-negative in L 1 and with finite energy), see [START_REF] Desvillettes | Smoothness of the solution of the spatially homogeneous Boltzmann equation without cutoff[END_REF] and the subsequent follow-up papers [START_REF] Alexandre | Littlewood-Paley theory and regularity issues in Boltzmann homogeneous equations. I. Non-cutoff case and Maxwellian molecules[END_REF][START_REF] Huo | Regularity of solutions for spatially homogeneous Boltzmann equation without angular cutoff[END_REF][START_REF] Alexandre | Uncertainty principle and kinetic equations[END_REF][START_REF] Alexandre | Littlewood-Paley theory and regularity issues in Boltzmann homogeneous equations. II. Non cutoff case and non Maxwellian molecules[END_REF][START_REF] Morimoto | Regularity of solutions to the spatially homogeneous Boltzmann equation without angular cutoff[END_REF][START_REF] Arsen ′ Ev | On a connection between the solution of the Boltzmann equation and the solution of the Landau-Fokker-Planck equation[END_REF][START_REF] Desvillettes | Plasma kinetic models: the Fokker-Planck-Landau equation[END_REF]128,[START_REF] Desvillettes | On the spatially homogeneous Landau equation for hard potentials. I. Existence, uniqueness and smoothness[END_REF], and see also the related entropy dissipation estimates in [START_REF] Desvillettes | On the spatially homogeneous Landau equation for hard potentials. II. H-theorem and applications[END_REF][START_REF] Desvillettes | Entropy dissipation estimates for the Landau equation in the Coulomb case and applications[END_REF], and see the analytic regularisation of weak spatially homogeneous solutions for Maxwellian or hard potentials in [START_REF] Chen | Analytic smoothness effect of solutions for spatially homogeneous Landau equation[END_REF]. Furthermore, Silvestre [START_REF] Silvestre | Upper bounds for parabolic equations and the Landau equation[END_REF] derives an L ∞ bound (gain of integrability) for spatially homogeneous solutions in the case of moderately soft potentials without relying on energy methods. Let us also mention works studying modified Landau equations [START_REF] Krieger | Global solutions to a non-local diffusion equation with quadratic non-linearity[END_REF][START_REF] Gressman | A non-local inequality and global existence[END_REF] and the work [START_REF] Gualdani | Estimates for radial solutions of the homogeneous Landau equation with Coulomb potential[END_REF] that shows, using barrier arguments, that any weak radial solution to the Landau-Coulomb equation that belongs to L 3/2 is automatically bounded and C 2 . On the other hand, fewer investigations of the regularity of spatially heterogeneous solutions have been done, focusing on the regularisation of classical solutions [START_REF] Chen | Smoothing effects for classical solutions of the full Landau equation[END_REF][START_REF] Liu | Regularizing effects for the classical solutions to the Landau equation in the whole space[END_REF].

The general question of conditional regularity hence suggests the following question in the context of the Landau equation: An important progress has been made by solving a weaker version of this conjecture when the exponent γ ∈ (-2, 0), which corresponds to moderately soft potentials, i.e. γ + 2s > 0 since here s = 1. We describe in this section the different steps and combined efforts of different groups.

DGNM theory and local Hölder regularity.

The first step is the work [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF] already mentioned. A corollary of Theorem 1 is the following: Theorem 3 (Local Hölder regularity for the LE [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF]). Given any γ ∈ [-3, 1], there are universal constants C > 0, α ∈ (0, 1) such that any essentially bounded weak solution f of (1.1)-( 1

.3) in (-1, 0] × B 1 × B 1 satisfying (1.4) is α-Hölder continuous with respect to (t, x, v) ∈ (-1/2, 0] × B 1/2 × B 1/2 and f C α (-1 2 ,0]×B 1 2 ×B 1 2 ≤ C f L 2 ((-1,0]×B 1 ×B 1 ) + f 2 L ∞ ((-1,0]×B 1 ×B 1 ) .
Note that this theorem includes the physical case of Coulomb interactions γ = -3. The adjective "universal" for the constants refers to their independence from the solution.

3.3. Maximum principles and pointwise bounds. This line of research originates in the work of Silvestre both on the spatially homogeneous Boltzmann (SHBE) and Landau (SHLE) equations [START_REF] Silvestre | A new regularization mechanism for the Boltzmann equation without cut-off[END_REF][START_REF] Silvestre | Upper bounds for parabolic equations and the Landau equation[END_REF]. These papers build upon the ideas of "nonlinear maximum principles" introduced in [START_REF] Constantin | Nonlinear maximum principles for dissipative linear nonlocal operators and applications[END_REF] in the case of the Boltzmann collision operator, and upon the so-called "Aleksandrov-Bakelman-Pucci Maximum Principle" in the case of the Landau collision operator, see for instance [START_REF] Caffarelli | Fully nonlinear elliptic equations[END_REF][START_REF] Caffarelli | Regularity theory for fully nonlinear integro-differential equations[END_REF].

The main result of [START_REF] Silvestre | Upper bounds for parabolic equations and the Landau equation[END_REF] is:

4).

Then f 1 + t -3/2 with constant depending only on the bounds (1.4).

As noted by the author, this estimate implies quite straightforwardly existence, uniqueness and infinite regularity for the spatially homogeneous solution. For the difficult case of very soft potentials γ ∈ [-3, 2), this paper includes a weaker result where the L ∞ bound depends on a certain weighted Lebesgue norms; unfortunately it is not yet known how to control such norm along time. This conceptual barrier, when crossing the "very soft potentials threshold", is reminiscent of the state of the art for the Cauchy theory in Lebesgue and Sobolev spaces by energy estimates, for both the spatially homogeneous Boltzmann with long-range interactions [START_REF] Desvillettes | Stability and uniqueness for the spatially homogeneous Boltzmann equation with long-range interactions[END_REF] and Landau equation [START_REF] Alexandre | Some a priori estimates for the homogeneous Landau equation with soft potentials[END_REF][START_REF] Wu | Global in time estimates for the spatially homogeneous Landau equation with soft potentials[END_REF].

The pointwise bounds estimates were then extended to the spatially inhomogeneous case in [START_REF] Cameron | Global a priori estimates for the inhomogeneous Landau equation with moderately soft potentials[END_REF]. The main result in this paper is: Theorem 5 (Pointwise bound for the LE). Let γ ∈ (-2, 0] (moderately soft potentials without the limit case) and let f be a bounded non-negative weak solution to the Landau equation (1.1)-(1.3) on [0, T ] × R 2d for some T > 0, satisfying the assumptions (1.4). Then f

(1 + t -3/2 )(1 + |v|) -1 with constant depending only on the bounds (1.4) (and not on the L ∞ norm of the solution). Moreover if f in (x, v) ≤ C 0 e -α|v| 2 , for some C 0 > 0 and a sufficiently small α > 0 (depending on γ and (1.4)), then f (t, x, v) ≤ C 1 e -α|v| 2 with C 1 > 0 depending only on C 0 , γ and the bounds (1.4).

The proof relies on using locally the Harnack inequality in Theorem 2 adapted to the Landau equation and on devising a clever change of variable to track how this local estimate behaves at large velocities. The Gaussian bound is then obtained by combining existing maximum principle arguments at large velocities (using that well-constructed Gaussians provide supersolutions at large v) in the spirit of [START_REF] Gamba | Upper Maxwellian bounds for the spatially homogeneous Boltzmann equation[END_REF], and the previous pointwise bound for not-so-large velocities. Finally the authors remarked that the Hölder regularity estimate of Theorem 3 can be made global using the Gaussian decay bound.

3.4. Schauder estimates and higher regularity. Once the L ∞ norm and the Hölder regularity is under control, the next step is to obtain higher-order regularity. The classical tool is the so-called Schauder estimates [START_REF] Schauder | über lineare elliptische Differentialgleichungen zweiter Ordnung[END_REF]. The purpose of such estimates in general is to show that the solution to an elliptic or parabolic equation whose coefficients are Hölder continuous gains two derivatives with respect to the data (source term, initial data). The gain of the two derivatives is obtained in Hölder spaces:

C δ → C 2+δ .
Two works have been obtained independently along this line of research. The first one [START_REF] Henderson | ∞ smoothing for weak solutions of the inhomogeneous Landau equation[END_REF] focuses on the use of combination of Hölder estimates, maximum principles and Schauder estimates to obtain conditional infinite regularity for solutions to the Landau equation with moderately soft potentials γ ∈ (-2, 0). The second one [START_REF] Imbert | A toy nonlinear model in kinetic theory[END_REF] focuses on the use of these ingredients to "break the super-criticality" of the nonlinearity for a toy model of the Landau equation. Both these works develop, in different technical ways, Schauder estimates for this hypoelliptic equation. The main result in [START_REF] Henderson | ∞ smoothing for weak solutions of the inhomogeneous Landau equation[END_REF] is: Theorem 6 (Conditional regularity for LE). Let γ ∈ (-2, 0) (moderately soft potentials without the limit case) and let f be a bounded non-negative weak solution to the Landau equation (1.1)-(1.3) on [0, T ] × R 2d for some T > 0, satisfying the assumptions (1.4) and f in (x, v) ≤ C 0 e -α|v| 2 , for some C 0 > 0 and a sufficiently small α > 0 (depending on γ and (1.4)). Then f is smooth and its derivatives have some (possibly weaker) Gaussian decay.

Note that: (1) the regularity and decay bounds are uniform in time, as long as the bounds (1.4) remain uniformly bounded in time, (2) further conditional regularity are given in the paper for very soft potentials γ ∈ [-3, -2] but they require higher L ∞ t,x L 1 v (1+ |v|) q moments and the constants depend on time when γ ∈ [-3, -5/2] in dimension 3, (3) a useful complementary result is provided by [START_REF] Henderson | Local existence, lower mass bounds, and smoothing for the Landau equation[END_REF] where a local existence is proved in weighted locally uniform Sobolev spaces and the lower bound on the mass is relaxed by using the regularity to find a ball where the solution is uniformly positive: the combination of the two papers provide a conditional existence, uniqueness and regularity result for moderately soft potentials, conditionally to upper bounds on the local mass, energy and entropy.

The work [START_REF] Imbert | A toy nonlinear model in kinetic theory[END_REF] considers the toy model:

(3.1) ∂f + v • ∇ x f = ρ[f ]∇ v (∇ v f + vf ) , ρ[f ] := ˆRd f dv, in x ∈ T d , v ∈ R d , d ≥ 1.
This model preserves the form of the steady state, the ellipticity in v, the non-locality, the bilinearity and the mass conservation of the LE. It however greatly simplifies the underlying hydrodynamic and the maximum principle structure.

Here H k (T d × R d ) denotes the standard L 2 -based Sobolev space. The main result states (note that solutions are constructed and not conditional here):

Theorem 7. For all non-negative initial data

f in such that f in / √ µ ∈ H k (T d × R d ) with k > d/2 and satisfying C 1 µ ≤ f in ≤ C 2 µ for some C 1 , C 2 > 0,
there exists a unique global-in-time solution f to (3.1) with initial data f in satisfying for all time t > 0:

f (t)/ √ µ ∈ H k (T d × R d ) and C 1 µ ≤ f ≤ C 2 µ and f (t, •, •) ∈ C ∞ .
Note that the initial regularity exponent k could be relaxed with more work. A key step of the proof is the Schauder estimate. It gives the following additional information on this solution: the hypoelliptic Hölder norm H α (defined below) of f / √ µ is uniformly bounded in terms of the L 2 norm of f in / √ µ for times away from 0. This norm is defined on a given open connected set Q by

g H α (Q) := sup Q |g| + sup Q |(∂ t + v • ∇ x )g| + sup Q |D 2 v g| + [(∂ t + v • ∇ x )g] C 0,α (Q) + [D 2 v g] C 0,α (Q)
where [•] C 0,α (Q) is a Hölder anisotropic semi-norm, i.e. the smallest C > 0 such that

∀ z 0 ∈ Q, r > 0 s.t. Q r (z 0 ) ⊂ Q, g -g(z 0 ) L ∞ (Qr(z 0 )) ≤ Cr α where Q r (z 0 ) := z : 1 r (z -1 0 • z) ∈ Q 1 = (t, x, v) : t 0 -r 2 < t ≤ t 0 , |x -x 0 -(t -t 0 )v 0 | < r 3 , |v -v 0 | < r
and rz := (r 2 t, r 3 x, rv) and

z 1 • z 2 := (t 1 + t 2 , x 1 + x 2 + t 2 v 1 , v 1 + v 2 ).
The specific contribution of this work is the study of the Cauchy problem: the maximum principle provides Gaussian upper and lower bounds on the solution, and we then provide energy estimates and a blow-up criterion à la Beale-Kato-Majda [START_REF] Beale | Remarks on the breakdown of smooth solutions for the 3-D Euler equations[END_REF]. We then use the extensions of the DGNM and Schauder theories to control the L ∞

x (H 1 v ) type norm that governs the blow-up. We prove Hölder regularity through the method of [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF]. We then develop Schauder estimates following the method of [START_REF] Krylov | Lectures on elliptic and parabolic equations in Hölder spaces[END_REF] (see also [START_REF] Polidoro | On a class of ultraparabolic operators of Kolmogorov-Fokker-Planck type[END_REF][START_REF] Manfredini | The Dirichlet problem for a class of ultraparabolic equations[END_REF][START_REF] Di Francesco | Harnack inequality and Gaussian lower bound for Kolmogorov-type operators in non-divergence form[END_REF][START_REF] Bramanti | Schauder estimates for parabolic nondivergence operators of Hörmander type[END_REF][START_REF] Lunardi | Schauder estimates for a class of degenerate elliptic and parabolic operators with unbounded coefficients in R n[END_REF][START_REF] Radkevich | Equations with nonnegative characteristic form. II. Sovrem. Mat. Prilozh[END_REF][START_REF] Henderson | ∞ smoothing for weak solutions of the inhomogeneous Landau equation[END_REF]). New difficulties arise compared with the parabolic case treated in [START_REF] Krylov | Lectures on elliptic and parabolic equations in Hölder spaces[END_REF] in relation with the hypoelliptic structure and we develop hypoelliptic commutator estimates directly at the level of trajectories to solve them. We also borrow some ideas from hypocoercivity [START_REF] Villani | [END_REF] in the proof of the so-called gradient estimate.

Note that it would be interesting to give a proof of Schauder estimates for such hypoelliptic equations that is entirely based on scaling arguments in the spirit [START_REF] Simon | Schauder estimates by scaling[END_REF] (see also the use of such scaling arguments in [START_REF] Hairer | A theory of regularity structures[END_REF], in the elliptic-parabolic case). This might indeed prove useful for generalising such estimates to the integral Boltzmann collision operator, see the next section. 2) was obtained in [START_REF] Alexandre | Regularizing effect and local existence for the non-cutoff Boltzmann equation[END_REF] for sufficiently regular initial data f 0 . Global existence was obtained in [START_REF] Desvillettes | Stability and uniqueness for the spatially homogeneous Boltzmann equation with long-range interactions[END_REF] for moderately soft potentials in the spatially homogeneous case. In the next subsections, we present the progresses made so far in the case of moderately soft potentials: the estimate in L ∞ for t > 0 was obtained in [START_REF] Silvestre | A new regularization mechanism for the Boltzmann equation without cut-off[END_REF], the local Hölder regularity in [START_REF] Imbert | Weak harnack inequality for the Boltzmann equation without cut-off[END_REF], and finally the polynomial pointwise decay estimates in [START_REF] Imbert | Decay estimates for large velocities in the Boltzmann equation without cut-off[END_REF]. The bootstrap mechanism to obtain higher regularity through Schauder estimates remains however unsolved at now.

Let us briefly review the existing results about regularisation. The very first mathematical observation that long-range interactions are associated with fractional ellipticity in the kinetic variable goes back to Desvillettes [START_REF] Desvillettes | About the regularizing properties of the non-cut-off Kac equation[END_REF] in the mid 1990s. In [START_REF] Alexandre | Regularizing effect and local existence for the non-cutoff Boltzmann equation[END_REF], the authors prove that if the solution f has five derivatives in L 2 , with respect to all variables t, x and v, weighted by (1 + |v|) q for arbitrarily large powers q, and in addition the mass density is bounded below, then the solution f is C ∞ . It is not known however whether these hypotheses are implied by (1.4). Note also the previous partial results [START_REF] Desvillettes | Smoothness of the solution of the spatially homogeneous Boltzmann equation without cutoff[END_REF][START_REF] Alexandre | Littlewood-Paley theory and regularity issues in Boltzmann homogeneous equations. I. Non-cutoff case and Maxwellian molecules[END_REF][START_REF] Huo | Regularity of solutions for spatially homogeneous Boltzmann equation without angular cutoff[END_REF][START_REF] Alexandre | Uncertainty principle and kinetic equations[END_REF][START_REF] Alexandre | Littlewood-Paley theory and regularity issues in Boltzmann homogeneous equations. II. Non cutoff case and non Maxwellian molecules[END_REF][START_REF] Morimoto | Regularity of solutions to the spatially homogeneous Boltzmann equation without angular cutoff[END_REF][START_REF] Chen | Smoothing estimates for Boltzmann equation with full-range interactions: Spatially inhomogeneous case[END_REF] in the spatially homogeneous case and with less assumptions on the initial data, and the work [START_REF] Chen | Smoothing estimates for Boltzmann equation with full-range interactions: spatially homogeneous case[END_REF] in the spatially inhomogeneous case but with much stronger a priori assumptions.

Note that, drawing inspiration from the case of the Landau equation, in order for the iterative gain of regularity in [START_REF] Henderson | ∞ smoothing for weak solutions of the inhomogeneous Landau equation[END_REF][START_REF] Imbert | A toy nonlinear model in kinetic theory[END_REF] to work, it is necessary to start with a solution that decays, as |v| → ∞, faster than any algebraic power rate |v| -q . We expect the same general principle to apply to the Boltzmann equation, even if the appropriate Schauder type estimates for kinetic integro-differential equations to carry out an iterative gain in regularity are not yet available.

The question of conditional regularity suggests the following conjecture in the context of the Boltzmann equation with long-range interactions: The rest of this section is devoted to describing the partial progresses made in the case of, again, moderately soft potentials γ + 2s > 0. 4.2. Maximum principle and pointwise L ∞ bound. This first breakthrough is due to Silvestre [START_REF] Silvestre | A new regularization mechanism for the Boltzmann equation without cut-off[END_REF]. This article draws inspiration from his own previous works on non-local operators and from the "nonlinear maximum principle" of Constantin and Vicol [START_REF] Constantin | Nonlinear maximum principles for dissipative linear nonlocal operators and applications[END_REF]. It is based on a maximum principle argument for a barrier supersolution that is constant in x, v and blowing-up as t → 0 + ; it uses the decomposition of the collision operator and "cancellation lemma" going back to [START_REF] Alexandre | Entropy dissipation and long-range interactions[END_REF], the identification of a cone of direction for (v ′ -v) is order to obtain lower bounds on the f -dependent kernel of the elliptic part of the operator, and finally some Chebycheff inequality and nonlinear lower bound on the collision integral. The main result is: Theorem 8 (Pointwise bound for the BE [START_REF] Silvestre | A new regularization mechanism for the Boltzmann equation without cut-off[END_REF]). Let γ ∈ [-2, 1], s ∈ (0, 1) with γ+2s > 0 (moderately soft potentials). Let f be a classical non-negative solution to the Boltzmann equation (1.1)-(1.3) on [0, T ] × T d × R d for some T > 0, satisfying the assumptions (1.4). Then f ≤ C(1 + t -β ) with C > 0 and β > 0 depending only on γ, s and the bounds (1.4).

Note that the paper also includes further results in the case of very soft potentials but conditionally to additional estimates of the form L ∞ t,x L p v (1 + |v| q ) for some p > 1, q > 0; it is not known at present how to deduce the latter estimates from the hydrodynamic bounds (1.4).

Weak Harnack inequality and local Hölder regularity.

The second breakthrough is the paper [START_REF] Imbert | Weak harnack inequality for the Boltzmann equation without cut-off[END_REF]. In comparison to the Landau equation, the Boltzmann equation has a more complicated integral structure, that shares similarity with "fully nonlinear" fractional elliptic operators. The main result proved is: Theorem 9 (Local Hölder regularity for the BE [START_REF] Imbert | Weak harnack inequality for the Boltzmann equation without cut-off[END_REF]). Given any γ ∈ (-3, 1] and s ∈ (0, 1) with γ + 2s > 0, there are universal constants C > 0, α ∈ (0, 1) such that any essentially bounded non-negative weak solution f to

(1.1)-(1.2) in (-1, 0] × B 1 × R 3 satisfying (1.4) is α-Hölder continuous with respect to (t, x, v) ∈ (-1/2, 0] × B 1/2 × B 1/2 ,
where C, α only depend on the L ∞ bound of f and the bounds (1.4).

The proof goes in two steps. The first step is a local L 2 → L ∞ gain of integrability, following the approach of De Giorgi and Moser as reformulated in a kinetic context in [START_REF] Pascucci | The Moser's iterative method for a class of ultraparabolic equations[END_REF] and [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF]. It requires further technical work to formulate the De Giorgi iteration for such integro-differential equations with degenerate kernels (see also the related works [START_REF] Kassmann | A priori estimates for integro-differential operators with measurable kernels[END_REF][START_REF] Felsinger | Local regularity for parabolic nonlocal operators[END_REF][START_REF] Bux | Quadratic forms and Sobolev spaces of fractional order[END_REF]). The regularity mechanism at the core of the averaging velocity method is used; it is however presented differently than in most papers on this topic, by relying on explicit calculations on the fundamental solution of the fractional Kolmogorov equation. In the second step of the proof, the authors establish a weak Harnack inequality, i.e. the control from above of local L ǫ t,x,v averages with ǫ > 0 small by a local infimum multiplied by a universal constant. This inequality is sufficient to deduce the Hölder regularity. Two different strategies are used depending on whether s ∈ (0, 1/2) or s ∈ [1/2, 1). In the first case, they construct a barrier function to propagate lower bounds as in the method by Krylov and Safonov for equations in nondivergence form. In the second case, they use a variant of the isometric argument of De Giorgi proved by compactness as in [START_REF] Golse | Harnack inequality for kinetic Fokker-Planck equations with rough coefficients and application to the Landau equation[END_REF]. Again the regularity of velocity averages plays a crucial role but is exploited by direct calculation on the fundamental solution of the fractional Kolmogorov equation. 4.4. Maximum principle and decay at large velocities. Finally in the paper [START_REF] Imbert | Decay estimates for large velocities in the Boltzmann equation without cut-off[END_REF], the nonlinear maximum principle argument of [START_REF] Silvestre | A new regularization mechanism for the Boltzmann equation without cut-off[END_REF] is refined to obtain "pointwise counterpart" of velocity moments. The main result established in this paper is: Theorem 10 (Decay at large velocities for the BE [START_REF] Imbert | Decay estimates for large velocities in the Boltzmann equation without cut-off[END_REF]). Given any γ ∈ (-3, 1] and s ∈ (0, 1) with γ + 2s ≥ 0, there are universal constants C > 0, α ∈ (0, 1) such that for any classical non-negative solution f to (1.1)-(1.2) in [0, T ] × T 3 × R 3 satisfying (1.4), it holds for any q > 0: (i) if f in (1 + |v|) -q then f (t, x, v) ≤ C(1 + |v|) -q for all t > 0, (ii) assuming furthermore that γ > 0, then f (t, x, v) ≤ C ′ (1 + t -β )(1 + |v|) -q for all t > 0. All the constants depend on γ, s, q and the bounds (1.4).

The study of large velocity decay in weighted L 1 spaces, known as the study of moments, is an old and important question in kinetic equations. The study of moments was initiated, for spatially homogeneous solutions, in [START_REF] Ikenberry | On the pressures and the flux of energy in a gas according to Maxwell's kinetic theory[END_REF] for Maxwellian potentials (γ = 0). In the case of hard potentials (γ > 0), Povzner identities [START_REF] Povzner | On the Boltzmann equation in the kinetic theory of gases[END_REF][START_REF] Elmroth | Global boundedness of moments of solutions of the Boltzmann equation for forces of infinite range[END_REF][START_REF] Wennberg | The Povzner inequality and moments in the Boltzmann equation[END_REF][START_REF] Bobylev | Moment inequalities for the Boltzmann equation and applications to spatially homogeneous problems[END_REF] play an important role. For instance, Elmroth [START_REF] Elmroth | Global boundedness of moments of solutions of the Boltzmann equation for forces of infinite range[END_REF] used them to prove that if moments are initially bounded, then they remain bounded for all times. Desvillettes [START_REF] Desvillettes | Some applications of the method of moments for the homogeneous Boltzmann and Kac equations[END_REF] then proved that only one moment of order q > 2 is necessary for the same conclusion to hold true. It is shown in [START_REF] Wennberg | The Povzner inequality and moments in the Boltzmann equation[END_REF][START_REF] Mischler | On the spatially homogeneous Boltzmann equation[END_REF] that even the condition on one moment of order q > 2 can be dispensed with, in both (homogeneous) cutoff and non-cutoff case. These moment estimates were used by Bobylev [START_REF] Bobylev | Moment inequalities for the Boltzmann equation and applications to spatially homogeneous problems[END_REF] in order to derive (integral) Gaussian tail estimates. In the case of soft potentials, Desvillettes [START_REF] Desvillettes | Some applications of the method of moments for the homogeneous Boltzmann and Kac equations[END_REF] proved for γ ∈ (-1, 0) that initially bounded moments grow at most linearly with time and it is explained in [START_REF] Villani | A review of mathematical topics in collisional kinetic theory[END_REF] that the method applies to γ ∈ [-2, 0). The case of measure-valued solutions is considered in [START_REF] Lu | On measure solutions of the Boltzmann equation, part I: moment production and stability estimates[END_REF].

However the extension of these integral moments estimates to spatially inhomogeneous solutions is a hard and unclear question at the moment. The only result available is [START_REF] Gualdani | Factorization for non-symmetric operators and exponential h-theorem[END_REF]Lemma 5.9 & 5.11] which proves the propagation and appearance of certain exponential moments for the spatially inhomogeneous Boltzmann equation for hard spheres (or hard potentials with cutoff), however in a space of the form W 3,1

x L 1 (1 + |v| q ). Another line of research opened by [START_REF] Gamba | Upper Maxwellian bounds for the spatially homogeneous Boltzmann equation[END_REF] consists in establishing exponential Gaussian pointwise decay by maximum principle arguments (see also [START_REF] Bobylev | Upper Maxwellian bounds for the Boltzmann equation with pseudo-Maxwell molecules[END_REF][START_REF] Alonso | Exponentially-tailed regularity and time asymptotic for the homogeneous Boltzmann equation[END_REF][START_REF] Gamba | On pointwise exponentially weighted estimates for the Boltzmann equation[END_REF]). But these works assumes exponential integral moments whose propagation in time is not known, therefore it is not clear how to use them in this context.

We finally recall that the last part of the research program, the Schauder estimates, is missing for the Boltzmann equation with moderately soft potentials, and is an interesting open question for future research.

Conjecture 1 .

 1 Any solutions to the Landau equation (1.1)-(1.3) (with Coulomb interaction γ = -3) on [0, T ] satisfying (1.4) is bounded and smooth on (0, T ].

Theorem 4 (

 4 Pointwise bound for the SHLE). Let γ ∈ [-2, 0] (moderately soft potentials) and let f be a classical non-negative spatially homogeneous solution to the Landau equation (1.1)-(1.3) on [0, T ] × R d for some T > 0, and satisfying the assumptions (1.

4 .

 4 Conditional regularity of the Boltzmann equation 4.1. Previous works and a conjecture. Short time existence of solutions to (1.1)-(1.

Conjecture 2 .

 2 Any solutions to the Boltzmann equation (1.1)-(1.2) with long-range interactions (γ ∈ (-3, 1], s ∈ (0, 1), γ + 2s ∈ (-1, 1)) on [0, T ] satisfying (1.4) is bounded and smooth on (0, T ].

n i=1 X * i X i + X 0 , then the semigroup e tL is regularising (hypoelliptic) as soon as the Lie algebra generated by X 0 , . . . , X n has dimension N throughout the domain of L.Let us also mention the connexion with the Malliavin calculus in probability, which gives a probabilistic proof to the Hörmander theorem in many settings, see[START_REF] Malliavin | Stochastic calculus of variation and hypoelliptic operators[END_REF] as well as the many subsequent works, for instance[START_REF] Kusuoka | Applications of the Malliavin calculus. I. In Stochastic analysis[END_REF][START_REF] Kusuoka | Applications of the Malliavin calculus[END_REF][START_REF] Bismut | the Malliavin calculus and hypoellipticity under general Hörmander's conditions[END_REF][START_REF] Norris | Simplified Malliavin calculus[END_REF].

Acknowledgement. This review article greatly benefited from the many discussions of the author with Cyril Imbert and Luis Silvestre, in particular concerning the works on the conditional regularity initiated by Luis Silvestre that form a key part of this review, and concerning their important joint work on the weak Harnack inequality for the Boltzmann equation. Moreover the author gratefully acknowledges the many crucial discussions with Alexis Vasseur about his insights on the De Giorgi method, and with François Golse about averaging lemma and homogeneisation. The author acknowledges partial funding by the ERC grants MATKIT 2011-2016 and MAFRAN 2017-2022.


Aybükë Oztürk

Stéphane Lallich

Jérôme Darmont
email: jerome.darmont@univ-lyon2.fryona.waksman@mom.fr

Sylvie Yona

Aybüke Öztürk

Sylvie Yona Waksman

MaxMin Linear Initialization for Fuzzy C-Means

Keywords: Clustering, Fuzzy C-Means, Seeding, Initialization, Maxmin Linear Method, Validity Indices

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Clustering is a useful technique for grouping a set of unlabelled data points (instances) described by attributes (variables), such that points belonging to the same cluster (group) have similar characteristics, while points in different clusters have dissimilar characteristics. There are several types of clustering schemes, such as crisp, overlapping or fuzzy partitions, and hierarchies. Crisp clustering considers that each data point belongs to one and only one cluster. Contrary to crisp clustering, fuzzy clustering [START_REF] Ruspini | Numerical methods for fuzzy clustering[END_REF] considers that a data point can belong to more than one cluster. There are some situations where fuzzy clustering is very useful. For instance, let us consider three clusters achieved when categorizing textual documents: an economy cluster (topic), an energy cluster, and a politics cluster. Then a document containing the keyword "petrol" could belong to all three clusters. Moreover, fuzzy clustering helps opening a discussion with domain experts regarding clustering results.

The primary objective of our paper is to avoid using highly complex clustering methods. One solution is to use iterative fuzzy methods such as Fuzzy C-Means (FCM) and Fuzzy K-Medoids. Both methods adapt the principle of the K-Means algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. FCM, proposed by [START_REF] Dunn | A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters[END_REF] and extended by [START_REF] Bezdek | Fcm: The fuzzy c-means clustering algorithm[END_REF], applies on numerical data, while Fuzzy K-Medoids [START_REF] Kaufman | Partitioning around medoids (program pam). Finding groups in data: an introduction to cluster analysis[END_REF] applies on categorical data. Since numerical data are the most common case, we choose to experiment our proposals with FCM.

The aim of the FCM algorithm is to minimize the fuzzy within-inertia F W (see Equation 1). Fuzzy inertia F I (see Equation 2) composes of the F W and the fuzzy between-inertia F B (see Equation 3). F W , F I, and F B are computed from a membership matrix U , which stores the membership coefficients u ik of data point i to cluster k. Note that F I = F W + F B. Moreover, F I is not constant because it depends on u ik value. When F W changes, the values of F I and F B also change.

F W = n i=1 K k=1 u m ik d 2 (x i , c k ) (1)
F I = n i=1 K k=1 u m ik d 2 (x i , x) (2)
F B = n i=1 K k=1 u m ik d 2 (c k , x) (3)
where n is the number of instances, K is the number of clusters, m is the fuzziness coefficient (by default, m = 2. If m = 1, clustering is crisp. If m > 1, clustering becomes fuzzy), c k is the center of the k th cluster ∀ k, 1 ≤ k ≤ K, x is the grand mean (the arithmetic mean of all data, see Equation 4), and function d 2 () computes the squared Euclidean distance.

x = 1 n n i=1 x i (4)
FCM starts by choosing K data points as initial centroids of the clusters. Then, membership matrix values u ik (see Equation 5) are assigned to each data point in the dataset. Centroids of clusters c k are updated based on Equation 6until a termination criterion is reached successfully. In FCM, this criterion can be a fixed number of iterations t, e.g., t = 100. Alternatively, a threshold ǫ can be used, e.g., ǫ = 0.0001. Then, the algorithm stops when the relative difference of objective function < ǫ.

u ik = 1 K j=1 ( xi-c k 2 xi-cj 2 ) 1 m-1 (5) c k = n i=1 (u m ik )x i n i=1 (u m ik ) (6)
When using FCM, an important point is the way of choosing K data points as initial centroids (seeds). An efficient initialization method should be linear, so that the FCM algorithm stays linear, too. Then, the initialization method must be evaluated using validity indices that are well suited to the fuzzy case.

To obtain a good validated clustering result, one has to minimize intra-cluster distance (compactness) and at the same times, one has to maximize inter-cluster distance (separability). The more often, proposed clustering validity indices associate a compactness index with a separability index.

Thence, we propose in this paper (1) a linear and efficient initialization method for FCM clustering called MaxMin Linear. Moreover, to compare our proposal with several initialization methods from the literature, we also propose (2) a new clustering validity index called Transformed Standardized Fuzzy Difference (TSFD), which is tailored to the fuzzy case. We perform validation experiments on several numerical real-world and artificial datasets.

The remainder of this paper is organized as follows. Section 2 presents initialization methods for iterative clustering and several clustering validity methods proposed in the literature. Sections 3 and 4 detail our contributions, i.e., the MaxMin Linear initialization method and the TSFD validity index, respectively. Section 5 deals with the experimental evaluation of the MaxMin Linear initialization method on several datasets, using several validity indices, including TSFD. Finally, we conclude this paper and provide some perspectives in Section 6.

Related Works

Most initialization methods are studied through K-Means clustering [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] concepts. We have reviewed various works from the literature, including much-cited papers [START_REF] Steinley | Initializing k-means batch clustering: A critical evaluation of several techniques[END_REF][START_REF] Maitra | A systematic evaluation of different methods for initializing the k-means clustering algorithm[END_REF][START_REF] Celebi | A comparative study of efficient initialization methods for the k-means clustering algorithm[END_REF]. In our study, we make use of commonly mentioned linear methods from these three papers.

The first initialization method by [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] uses the first K data points as centroids. This method is sensitive to the order of data. It is used by default in SPSS [START_REF] Norušis | IBM SPSS statistics 19 statistical procedures companion[END_REF]. The second method by MacQueen (MacQueen2 ) takes K random data points as centroids. Moreover, [START_REF] Faber | Clustering and the continuous k-means algorithm[END_REF] proposes to perform multiple relaunches of MacQueen2. Among the different relaunches, the one that optimizes F W (Equation 1) is considered the best candidate. This method is the standard way for initializing clusters. Its main disadvantage is that already selected points are not considered when a new seed is chosen. The second disadvantage is that outliers can be chosen. On the other hand, multiple runs ensure to improve the quality of the chosen sample.

Hand et al. [START_REF] Hand | Optimising k-means clustering results with standard software packages[END_REF], propose an extension of Faber's method that starts with a random set of seeds. It suggests iteratively modifying the partition by randomly moving some points to other clusters. The partition minimizing F W is chosen as the best candidate. To move each data point to another random cluster, a probability α, e.g., α = 0.3, must be set. The method is only interesting if parameter α is fixed for different datasets.

Bradley and Fayyad's method [START_REF] Bradley | Refining initial points for k-means clustering[END_REF] starts by randomly partitioning the dataset into J subsets. Then, each subset is clustered with the K-Means algorithm using MacQueen2 initialization. MacQueen2 produces J sets of centers, each containing K points. The centers of clusters are combined into a superset. Then, the superset is clustered by K-Means J times. Each time, K-Means is initialized with a different center set, and members of the center set that give the smallest F W are selected as final centers.

The PCA-Part method [START_REF] Su | In search of deterministic methods for initializing k-means and gaussian mixture clustering[END_REF] uses a divisive hierarchical approach based on Principal Component Analysis (PCA) [START_REF] Wold | Principal component analysis[END_REF]. The method starts with a single cluster containing the whole dataset. Then, it iteratively divides clusters with respect to F W . Clusters are divided into two sub-clusters by using a hyperplane that is orthogonal to the principal eigenvector of the cluster covariance matrix. The division process ends after K clusters are obtained.

The K-Means++ method [START_REF] Arthur | k-means++: The advantages of careful seeding[END_REF] selects centroids based on a distance probability to the nearest center. First, it randomly selects an initial center c 1 = x from the data point set X. Then, d(x) is denoted as the shortest euclidean distance from x to its closest center. The next center c i is randomly selected as

c i = x ′ ∈ X with probability d(x ′ ) 2 / d(x) 2 .
Finally, in the literature, there are other methods having quadratic complexity [START_REF] Lance | A general theory of classificatory sorting strategies: Ii. clustering systems[END_REF][START_REF] Astrahan | Speech analysis by clustering, or the hyperphoneme method[END_REF]. Among quadratic methods, MaxMin (also called Maximin) [START_REF] Gonzalez | Clustering to minimize the maximum intercluster distance[END_REF] is particularly interesting. MaxMin first calculates all the paired distances between data points. Then, it chooses two centroids from the data points, which have the greatest distance to each other. Finally, the next centroid is the data point that is the farthest from its centroid. This approach helps decrease F W , which improves the homogeneity of clusters.

To summarize, Hand and Krzanowski [START_REF] Hand | Optimising k-means clustering results with standard software packages[END_REF] rely on user-defined parameters that may not be easy to set. MacQueen2, though easy to understand and implement, uses only one random sample. Faber improves the MacQueen2 's random sample through relaunches. In K-Means++, the random choice is replaced by a probabilistic choice and cluster homogeneity is taken into account. However, since the probabilistic selection does not always select sufficiently the large enough distance, several probabilistic samples are required and the best centers are selected from all relaunches.

In contrast, MaxMin constructs only one sample by decreasing F W and is thus deterministic. Thus, we can be sure that a chosen center is the best. Yet, it can be less effective than K-Means++ in the presence of outliers.

To evaluate initialization methods, we need to use fuzzy validity indices. According to [START_REF] Wang | On fuzzy cluster validity indices[END_REF], there are two groups of validity indices. The first group is only based on membership values and includes the partition coefficient index V P C [START_REF] Bezdek | Cluster validity with fuzzy sets[END_REF] (see Equation 7; 1 K ≤ V P C ≤ 1; to be maximized) and the Chen and Linkens index V CL [START_REF] Chen | Rule-base self-generation and simplification for datadriven fuzzy models[END_REF] (see Equation 8; 0 ≤ V CL ≤ 1; to be maximized).

V P C = 1 n n i=1 K k=1 u 2 ik (7) V CL = 1 n n i=1 max k (u ik ) - 1 c K-1 k=1 K j=k+1 1 n n i=1 min(u ik , u ij ) , (8)
where c = K-1 k=1 k.

V CL takes in consideration both compactness (first term of V CL ) and separability (second term of V CL ). The second group of fuzzy validity indices is based on associating membership values to cluster centers and data. It includes the adaptation of the Ratio index V F Ratio to fuzzy clustering [START_REF] Caliński | A dendrite method for cluster analysis[END_REF] (see Equation 9; 0 ≤ V F Ratio ≤ +∞; to be maximized), the penalized version of V F Ratio index which is the Calinski and Harabasz index V F CH [START_REF] Caliński | A dendrite method for cluster analysis[END_REF] (see Equation 10; 0 ≤ V F CH ≤ +∞; to be maximized), the Fukuyama and Sugeno index V F S [START_REF] Fukuyama | A new method of choosing the number of clusters for the fuzzy c-mean method[END_REF] (see Equation 11; -F I ≤ V F S ≤ F I; to be minimized), and the Xie and Beni index V XB [START_REF] Xie | A validity measure for fuzzy clustering[END_REF][START_REF] Pal | On cluster validity for the fuzzy c-means model[END_REF] (see Equation 12; 0 ≤ V XB ≤ F I/n * min x j -v k 2 ; to be minimized).

V F Ratio = F B/F W (9)
V F CH = F B/(K -1) F W/(n -K) = n -K K -1 F B F W (10)
V F S = F W -F B (11)
V XB = K k=1 n i=1 u m ik x i -v k 2 n * min j,k v j -v k 2 (12)
Among all the above stated validity indices, there is no single validity index that gives the best result for any dataset. Thus, there is room for a new validity index that is specifically tailored for fuzzy validation. This is why we propose the Transformed Standardized Fuzzy Difference index.

MaxMin Linear Fuzzy Clustering Initialization Method

MaxMin's simplicity and ability to build homogeneous clusters sounds very interesting. Yet, considering all paired distance between data points makes the method quadratic with respect to the number of data points. Thus, we present in this section an enhancement of MaxMin that makes it linear. Before introducing our changes, we first detail how MaxMin works in Algorithm 1 (see Section 2 for MaxMin's principle).

In MaxMin Linear, we first calculate grand mean x (see Equation 4). Then, we choose as first centroid the data point that is nearest to x. The second

* i = 1, ..., n, k * = 1, ..., K * do d 2 m (xi) ← min(d 2 (xi, c k * )) end for K * ← K * + 1 cK * ← argmax(d 2 m (xi)) i = 1, ..., n end while return {c k * } k * = 1, ..., K *
centroid is the data point that has the largest distance to the first centroid. Thus, complexity remains linear with respect to the number of data points. Afterwards, the choice of the remaining centroids remains the same as in MaxMin. MaxMin Linear is formalized in Algorithm 2.

As a final note, the use of MaxMin Linear is not limited to use with FCM on numerical data, but also with Fuzzy K-Medoids [START_REF] Park | A simple and fast algorithm for k-medoids clustering[END_REF] for categorical data clustering. Thus, MaxMin Linear can also be applied with heterogeneous data to construct fuzzy clustering ensemble. This makes of MaxMin Linear a simple but noteworthy contribution, in our opinion.

Transformed Standardized Fuzzy Difference Validity Index

Several problems must be cleaned up to obtain a good clustering, including evaluation of the validity of the clusters and choosing the number of clusters. However, it is not an easy process. Compactness and separation level might raise problems. Firstly, if the chosen number of clusters is larger than optimal one, some clusters are broken while they could be more compact. Secondly, if the chosen number of clusters is smaller than optimal one, some clusters are merged and while they could be more separated. When it comes to addressing resolve those problems, many cluster validity indices are proposed for fuzzy clustering algorithms. The objective is to find the optimal number of clusters that can validate the best description of the data structure.

The optimal number of the cluster can be determined by considering the variation of clustering validity index. It is distinguished into two cases: The first case, if the index is not monotonic with the number of clusters, we choose the value of the number of clusters which optimizes the index. The second case, if the index is monotonic, one can prefer to use a penalized version of the index.

Algorithm 2 MaxMin Linear

Require: Set of data points X = {x1, ..., xn} Require: Number of clusters K {Select the first two centroids c1 and c2}

x ←

1 n n i=1 xi for i ← 1 to n do d 2 m (xi) ← min(d 2 (x, xi)) end for c1 ← argmin(d 2 m (xi)) i = 1, ..., n for i ← 1 to n do d 2 m (xi) ← max(d 2 (c1, xi)) end for c2 ← argmax(d 2 m (xi)) i = 1, ..., n K * ← 2 {Number of seeds} {Find the remaining seeds} while K * < K do for all xi = c k * i = 1, ..., n, k * = 1, ..., K * do d 2 m (xi) ← min(d 2 (xi, c k * )) end for K * ← K * + 1 cK * ← argmax(d 2 m (xi)) i = 1, ..., n end while return {c k * } k * = 1, ..., K *
In building TSFD, we first consider the difference F B -F W , which is similar to FS except for the sign). Unfortunately, F I = F B + F W is not constant and Finally, to obtain an index belonging to the [0, 1] interval, we linearly transform SF D as T SF D (see Equation 13; equal to F B/F I; ∈ [0, 1]; to be maximized)

T SF D = 1 + SF D 2 = F B F I (13)

Experimental Validation

In this section, we aim to compare MaxMin Linear to state of the art initialization methods for FCM-like clustering algorithms, i.e., MacQueen2, Faber's, K-Means++, and repeated K-Means++ (retaining the best result). These methods are indeed the most common linear methods and are good representatives for random, probability, and distance-based methods. Moreover, they do not require any parameterization. To achieve our comparison of initialization methods, we use the indices mentioned in Section 2.

Datasets

Initialization methods are compared on 15 commonly used real-life datasets from the UCI Machine Learning Repository1 and seven artificial datasets. Their characteristics are featured in Table 1. In the case of real-life datasets, the true number of clusters in each dataset is assimilated to the number of labels. Although using the number of labels as the number of clusters is debatable, it is acceptable if the set of descriptive variables explain the labels well. In artificial datasets, the number of clusters is known by construction.

In addition, we created new artificial datasets by introducing overlapping and noise to some of the existing artificial datasets such as E1071-3, Ruspini original, and E1071-5 datasets (see Table 1, ID 17,[START_REF] Gonzalez | Clustering to minimize the maximum intercluster distance[END_REF][START_REF] Chen | Rule-base self-generation and simplification for datadriven fuzzy models[END_REF].

To create the dataset, new data points are introduced and each must be labeled. To obtain a dataset with overlapping, we modified the construction of the E1071 artificial datasets [START_REF] Meyer | Package e1071[END_REF]. In the original datasets, there are three or five clusters of equal size (50). Cluster i is generated according to a Gaussian distribution N (i; 0.3). To increase overlapping while retaining the same cluster size, we only change the standard deviation from 0.3 to 0.4. Then, there is no labeling problem.

Noise is introduced in each cluster by adding noisy points generated by a Gaussian variable around each label gravity center. First, for each label, we calculate the coordinates of centers, and the mean and standard deviation of each variable. With Gaussian variables, points mainly lie between "center +/two standard deviations".

Noisy data are often generated by distributions with positive skewness. For example, in a two-dimensional dataset, for each label, we add points that are far away from the corresponding gravity center, especially on the right hand side, which generally contains the most points. Then, we draw a random number r between 0 and 1. If r ≤ 0.25, the point is attributed to the left hand side. Otherwise, the point is attributed to the right hand side. This method helps obtain noisy data that are 1 / 4 times smaller and 3 / 4 times greater, respectively, than the expected value for the considered label. We apply this process to the Ruspini dataset [START_REF] Ruspini | Numerical methods for fuzzy clustering[END_REF].

Experimental Settings

In our experiments, we parameterize the FCM algorithm as follows: default termination criterion ǫ = 0.0001 and default fuzziness coefficient value m = 2. We used these default settings as we are only interested in improving the tion of FCM algorithm. All initialization methods and clustering validity indices are written in Python version 2.7.4. Repeated K-Means++ runs are performed ten times.

Experimental Results

In our experiments, we compare our method MaxMin Linear to all initialization methods from Section 2, on all datasets. We account for the following comparison criteria: number of iterations, V P C , V CL , F B, F W , F I, V F Ratio , V T SF D , V F S , and V XB . We also rank the initialization methods with respect to all criteria.

Since presenting all results would take too much space, we only present three real-life datasets i.e., WineQuality-Red (Tables 2,3, and 4), Glass (Tables 5,6, and 7), and Segmentation (Tables 8,9, and 10), as well as two of the artificial datasets we modified to introduce noise and overlapping, i.e., Ruspini noised (Tables 11,12, and 13), and E1071-5-overlapped (Tables 14,15, and 16), respectively. Finally, the average ranking of initialization methods on all datasets is presented in Table 17.

From these experimental results, several observations can be drawn. In regard to the number of iterations, recall that Faber's and K-Means++ ×10 methods are relaunches of two stochastic initialization methods: MacQueen2 and K-Means++, respectively. With an average ranking of 1.68 (Table 17), MaxMin Linear outperforms all other methods, including single-run methods MacQueen2 (average ranking: 1.95) and K-Means++ (average ranking: 1.95).

Regarding clustering result quality, MaxMin Linear obtains the best average ranking for eight of the nine experimented quality indices (Table 17). Only the F B index yields a better result for the two multiple-runs methods, while the result of Maxmin Linear is similar to those of MacQueen2 and K-Means++. However, Maxmin Linear achieves the best trade-off between F B and F W , and thus maximizes the indices that take both F B and F W into account (V F Ratio , V T SF D , V F S and V XB ). The best result for MaxMin Linear is obtained with V T SF D (average ranking of 1.86; Table 17), the new index specially tailored for fuzzy clustering that we propose.

In conclusion, the results obtained with MaxMin Linear are a little better than those obtained with multiple-runs methods, but they require ten times fewer iterations. Moreover, MaxMin Linear is deterministic, whereas multipleruns methods are stochastic.

Conclusion and Perspectives

In this paper, we propose a new, fast, and easy to implement initialization method for FCM called MaxMin Linear. MaxMin Linear is compared to several initialization methods from the literature. It is experimentally shown that MaxMin Linear outperforms existing methods on 22 datasets. Moreover, we also propose an appropriate fuzzy validity index, TSFD, to evaluate initialization methods.

In addition, MaxMin Linear can be applied to algorithms other than FCM, such as Fuzzy K-Modes and Fuzzy K-Medoids, which apply on categorical. In particular, MaxMin Linear allows decreasing the complexity of Park's Fuzzy K-Medoids implementation.

In consequence, an immediate perspective to our work is to propose a new clustering ensemble method for heterogeneous datasets composed of both numerical and categorical data.

Algorithm 1

 1 MaxMin Require: Set of data points X = {x1, ..., xn} Require: Number of clusters K {Select the first two centroids c1 and c2} c1, c2 ← argmax(d 2 (xi, xj)) i, j = 1, ..., n K * ← 2 {Number of seeds} {Find the remaining seeds} while K * < K do for all xi = c k

  F B -F W ∈ [-F I, +F I]. To take this particularity of fuzzy clustering into account, we propose to standardize F B -F W by considering Standardized Fuzzy Difference SF D = (F B -F W ) ÷ F I instead. SF D ∈ [-1, +1].

Table 1 :

 1 Dataset features

	ID	Datasets	# of data points	# of variables	# of clusters	Sources
	1	Wine	178	13	3	UCI
	2	Iris	150	4	3	UCI
	3	Seeds	210	7	3	UCI
	4	Original Wisconsin Breast Cancer (WBCD)	683	9	2	UCI
	5	Wisconsin Diagnostic Breast Cancer (WDBC)	569	30	2	UCI
	6 BUPA Liver Disorder (BUPA)	345	6	2	UCI
	7	Pima	768	8	2	UCI
	8	Glass	214	9	6	UCI
	9	Vehicle	846	18	4	UCI
	10	Segmentation	2310	19	7	UCI
	11	Parkinson	150	22	2	UCI
	12	Movement Libras	360	90	15	UCI
	13	Ecoli	336	7	8	UCI
	14	Yeast	1484	8	10	UCI
	15	WineQuality-Red	1599	11	6	UCI
	16	Bensaid	49	2	3	[27]
	17	E1071-3	150	3	3	[28]
	18	Ruspini original	75	2	4	[1]
	19	E1071-3-overlapped	150	3	3	[28]
	20	Ruspini noised	95	2	4	[1]
	21	E1071-5	250	3	5	[28]
	22	E1071-5-overlapped	250	3	5	[28]

Table 2 :

 2 Experiment results on WineQuality-Red (1/2)

	Initialization Method # of iteration VP C	VCL	F B	F W
	MacQueen2	45	0.664 0.7455 110972.7 1224079.7
	Faber	430	0.664 0.7455 101440.4 1224079.7
	K-Means++	37	0.616 0.7029 101440.5 1089058.1
	K-Means++ ×10	393	0.664 0.7455 101440.4 1224073.7
	MaxMin Linear	34	0.665 0.7458 110972.7 1224384.8

Table 3 :

 3 Experiment results on WineQuality-Red (2/2)

	Initialization Method	F I	VF Ratio VT SF D	VF S	VXB
	MacQueen2	1335052.363 11.0305 0.9169 -1113107.01 0.1621
	Faber	1335052.363 11.0305 0.9148 -1113107.01 0.1621
	K-Means++	1190498.537 10.7359 0.9148 -987617.57 0.2388
	K-Means++ ×10	1335046.425 11.0304 0.9148 -1113101.04 0.1621
	MaxMin Linear	1335357.554 11.0332 0.9169 -1113412.13 0.1611

Table 4 :

 4 Ranking of initialization methods on WineQuality-RedVCL F B F W F I VF Ratio VT SF D VF S VXB

	Initialization Method VP C MacQueen2 # of iteration 3 2	2	4	2 2	2	2	2	2
	Faber	5	2	2	2	2 2	2	5	2	2
	K-Means++	2	5	5	3	5 5	5	3	5	5
	K-Means++ ×10	4	4	4	1	4 4	4	4	4	4
	MaxMin Linear	1	1	1 5	1 1	1	1	1	1

Table 5 :

 5 Experiment results on Glass (1/2)

	Initialization Method	# of iteration	VP C VCL F B F W
	MacQueen2	44	0.493 0.570 452.6 154.1
	Faber	456	0.493 0.570 452.6 154.1
	Kmeans++	56	0.493 0.570 452.6 154.1
	K-Means++ ×10	366	0.493 0.570 452.6 154.1
	MaxMin Linear	68	0.555 0.645 508.3 162.9

Table 6 :

 6 Experiment results on Glass (2/2)

	Initialization Method F I VF Ratio VT SF D VF S VXB
	MacQueen2	606.8 2.94 0.74596 -298.5 2.358
	Faber	606.8 2.94 0.74597 -298.5 2.358
	Kmeans++	606.7 2.94 0.74593 -298.4 2.358
	K-Means++ ×10	606.7 2.94 0.74604 -298.4 2.358
	MaxMin Linear	671.2 3.12 0.75725 -345.4 0.453

Table 7 :

 7 Ranking of initialization methods on Glass

	Initialization method	# of iteration	VP C VCL F B F W F I VF Ratio VT SF D VF S VXB
	MacQueen2	1	2	2	2	1 2	2	4	2	5
	Faber	5	3	3	3	2 3	3	3	3	2
	Kmeans++	2	5	5	5	4 5	5	5	5	4
	K-Means++ ×10	4	4	4	4	3 4	4	2	4	3
	MaxMin Linear	3	1	1 1	5 1	1	1	1	1

Table 8 :

 8 Experiment results on Segmentation (1/2)

	Initialization Method	# of iteration	VP C VCL	F B	F W
	MacQueen2	103	0.381 0.476 12384361.4 5781042.6
	Faber	731	0.398 0.488 14157566.6 5680259.6
	Kmeans++	146	0.381 0.476 12388277.9 5781061.6
	K-Means++ ×10	930	0.399 0.490 14254025.9 5666840.5
	MaxMin Linear	54	0.430 0.526 19234921.0 6344612.7

Table 9 :

 9 Experiment results on Segmentation (2/2)

	Initialization Method	F I	VF Ratio VT SF D	VF S	VXB
	MacQueen2	18165404.0 2.14 0.6818 -6603318.7 0.363
	Faber	19837826.2 2.49 0.7137 -8477307.1 0.464
	Kmeans++	18169339.6 2.14 0.6818 -6607216.3 0.361
	K-Means++ ×10	19920866.4 2.52 0.7136 -8587185.5 0.341
	MaxMin Linear	25579533.7 3.03 0.7520 -12890308.3 0.656

Table 10 :

 10 Ranking of initialization methods on Segmentation

	Initialization method	# of iteration	VP C VCL F B F W F I VF Ratio VT SF D VF S VXB
	MacQueen2	2	4	5	5	3 5	5	5	5	3
	Faber	4	3	3	3	2 3	3	2	3	4
	Kmeans++	3	5	4	4	4 4	4	3	4	2
	K-Means++ ×10	5	2	2	2	1 2	2	4	2	1
	MaxMin Linear	1	1	1 1	5 1	1	1	1	5

Table 11 :

 11 Experiment results on Ruspini noised (1/2)

	Initialization Method	# of iteration	VP C	VCL	F B	F W
	MacQueen2	9	0.775121 0.806518 219099.6 23421.0260
	Faber	130	0.775125 0.806517 219100.8 23421.0258
	Kmeans++	13	0.775122 0.806521 219101.1 23421.0258
	K-Means++ ×10	105 0.775128 0.806518 219102.3 23421.0256
	MaxMin Linear	7	0.775128 0.806523 219105.4 23421.0268

Table 12 :

 12 Experiment results on Ruspini noised (2/2)

	Initialization Method	F I	VF Ratio VT SF D	VF S	VXB
	MacQueen2	242520.7 9.3548 0.903427 -195678.6 0.063680
	Faber	242521.9 9.3549 0.903427 -195679.8 0.063681
	Kmeans++	242522.1 9.3549 0.903427 -195680.0 0.063676
	K-Means++ ×10	242523.3 9.3549 0.903426 -195681.3 0.063681
	MaxMin Linear	242526.4 9.3551 0.903429 -195684.4 0.063672

Table 13 :

 13 Ranking of initialization methods on Ruspini noisedVCL F B F W F I VF Ratio VT SF D VF S VXB

	Initialization Method	# of iteration	VP C

Table 14 :

 14 Experiment results on E1071-5-overlapped (1/2)

	Initialization Method	# of iteration	VP C	VCL	F B	F W
	MacQueen2	8	0.735646 0.762681 219.7337 48.715631
	Faber	103	0.735645 0.762683 219.7358 48.715630
	Kmeans++	12	0.735651 0.762685 219.7408 48.715632
	K-Means++ ×10	113	0.735645 0.762683 219.7363 48.715629
	MaxMin Linear	7	0.735652 0.762688 219.7445 48.715629

Table 15 :

 15 Experiment results on E1071-5-overlapped (2/2)

	Initialization Method	F I	VF Ratio VT SF D	VF S	VXB
	MacQueen2	268.4494 4.5105 0.818530 -171.0181 0.11574
	Faber	268.4514 4.5106 0.818535 -171.0202 0.11569
	Kmeans++	268.4565 4.5107 0.818534 -171.0252 0.11575
	K-Means++ ×10	268.4519 4.5106 0.818530 -171.0207 0.11569
	MaxMin Linear	268.4601 4.5108 0.818537 -171.0288 0.11572

Table 16 :

 16 Ranking of initialization methods on E1071-5-overlapped

	Initialization method	# of iteration	VP

C VCL F B F W F I VF Ratio VT SF D VF S VXB

Table 17 :

 17 Average ranking of initialization methods on all datasets VCL F B F W F I VF Ratio VT SF D VF S VXB

	Initialization method VP C MacQueen2 # of iteration 1.95 3.36 3.55 3.86 3.41 3.41 3.41	3.04 3.41 3.55
	Faber	4.45 2.73 2.82 1.73 2.73 2.73 2.73	3.27 2.73 2.91
	K-Means++	1.95 3.86 3.68 3.86 3.86 3.86 3.86	3.54 3.86 3.36
	K-Means++ ×10	4.41 2.68 2.55 1.64 2.86 2.86 2.86	3.22 2.86 2.82
	MaxMin Linear	1.68 2.27 2.32 3.82 2.05 2.05 2.05 1.86 2.05 2.27

http://archive.ics.uci.edu/ml/

Acknowledgments

This project is supported by the Rhône Alpes Region's ARC 5: "Cultures, Sciences, Sociétés et Médiations" through A. Öztürk's Ph.D. grant.


Clement Poncelet
email: cponcelet@cs.uni-salzburg.at

Christoph Kirsch

Clement Poncelet

Christoph Kirsch Symbolic

Clément Poncelet

Symbolic Execution in Selfie -a first step

  L'archive ouverte pluridisciplinaire

Introduction

Our project consists in designing and implementing a low-level symbolic emulator following selfie's philosophy: simplicity. More precisely, we tackle the question of how to implement a fully, sound and complete symbolic emulator capable of deducing properties for any machine code sequence given in input. Our first goal being to have no loss of information for at least the selfie code and define clearly the subset of RISC-U language it imply. This particular challenge is made possible thank to the simple languages handled by this independent software, alleging and preventing us from the usual assumptions in numerical analysis. All in all, we aim at using selfie's self-property to symbolically verify the selfie compilation and emulation.

Languages

High-level: C* RISC-U: Low-level C* a tiny subset of C, supports only two data types uint64_t and uint64_t*.

RISC-U a tiny subset of 64-bit RISC-V, contains 14 instructions for unsigned arithmetic only.

Selfie

Selfie a is an independent 64-bit implementation of (1) a self-compiling compiler written in C* targeting RISC-U, (2) a self-executing RISC-U emulator, and (3) a self-hosting hypervisor that virtualizes the emulated RISC-U machine.

Selfie is implemented in a single 8k-line file and can compile, execute, and virtualize itself any number of times. Selfie has originally been developed for educational purposes but has recently become a research platform as well.

Symbolic Execution

The symbolic execution emulates a given RISC-U binary, analysing numerically the instructions over abstract domains and operations.

A current version implements wintervals and initializes read system calls' return value as every possible value. The implementation logs each emulated instruction in a trace recording a triple inst, prev, value of the instruction binaries, the previous destination register value and the new abstract one. Moreover, each register and memory records the trace index of its last store. This data-structure allows us to apply constrains and back-propagation algorithms when the branch on equal instruction (beq) is emulated by simply moving backward or forward through the trace. An abstract domain for a complete and sound numerical analysis is still in investigation for the selfie binary, its simplicity allows us to avoid the usual overapproximations and fit exactly the possible values of each variable for all paths. [11,9] [13,11]

Logging trace

a

  http://selfie.cs.uni-salzburg.at self-hosting: ./selfie -c selfie.c -m 4 -c selfie.c -h 2 -c selfie.c