François Boulier

François Lemaire

A computer scientist point of view on Hilbert's differential theorem of zeros *

Keywords: computer algebra, differential algebra, theorem of zeros, normal form, Rosenfeld-Gröbner AMS Classification 12H05

What is a solution of a system of polynomial differential equations ? This paper provides an original presentation of well-known theorems, with a computer scientist flavor, relying on an improved normal form algorithm.

Introduction

According to the reference book [START_REF] Fels | Differential Algebra[END_REF] on differential algebra by Ritt, a solution (or a zero) of a polynomial differential system Σ in n differential indeterminates, m derivations, with coefficients in some differential field of characteristic zero (say, the field Q of the rational numbers for simplicity), is not a n-tuple of functions depending on m variables but a n-tuple of quantities living in some differential field extension of the base field of Σ which annihilates the system. One refers to such a solution as an abstract solution in this paper. This viewpoint is actually the analogue of the classical viewpoint for usual (non differential) polynomial systems: a solution of a polynomial system in n indeterminates and coefficients in Q is a n-tuple of values taken in some finite field extension of Q or, more simply, in the field C of the complex numbers since every finite field extension of Q can be embedded in C. Indeed, Ritt wrote in his preface that his presentation of differential algebra was deeply influenced by the works of Emmy Noether in the 1920's. However, the theory is much less intuitive in differential than in non differential algebra. In particular, the universal differential field extensions which would play, in the differential setting, the role of the field C, are much less familiar than C for the majority of scientists. See [START_REF] Robert | Differential Algebra and Algebraic Groups[END_REF]chap. III] or [11, sect. 1.5]. In his founding book, Ritt does not neglect the point of view of Analysis and which are assumed to commute pairwise. This paper is mostly concerned by a differential polynomial ring R in n differential indeterminates u 1 , . . . , u n with coefficients in a commutative differential field K of characteristic zero, say K = Q. Letting U = {u 1 , . . . , u n }, one denotes R = K{U }, following Ritt and Kolchin. The u i can be thought of as the unknown functions of the differential equations but, at this stage, they are plain symbols. The set of derivations generates a commutative monoid w.r.t. the composition operation.

It is denoted:

Θ = {δ a1 1 • • • δ am m | a 1 , .
. . , a m ∈ N} where N stands for the set of the nonnegative integers. The elements of Θ are the derivation operators. If θ = δ a1 1 • • • δ am m is a derivation operator then ord θ = a 1 + • • • + a m denotes its order. The monoid Θ acts on U , giving the infinite set ΘU of the derivatives. One indices derivations with letters e.g. δ x , δ y and one denotes derivatives using subscripts e.g. u xy denotes δ x δ y u.

An important construction in the rings theory is that of ideals for it permits to build factor rings of a ring R and, when R = K[X] is a polynomial ring over a field K, to build field extensions of K. One defines differential ideals in the differential rings theory for a similar purpose. By definition, a differential ideal A of a differential ring R is an ideal of R which is stable under the action of derivations: a ∈ A ⇒ δa ∈ A for all a ∈ R and derivation δ. Since the concept of factor ring is central in this paper, let us briefly introduce it, for casual readers, starting by analogy with the ring Z of the integer numbers. If n is a nonzero integer, Z/nZ denotes the set of the n residue classes of the equivalence relation modulo the ideal nZ of Z. The set Z/nZ is endowed with a ring structure by letting (the "bar" stands for "residue class")

a + b = a + b, a × b = a × b.
This definition makes sense for the class of a+b (resp. a×b) only depends on the classes, not on the chosen representatives. If A is an ideal of a ring R, one defines the factor ring R/A exactly the same way. Now, if A is a differential ideal of a differential ring R, the factor ring R/A can be endowed with derivations (indeed, as many derivations as R has), thereby becoming a differential ring, by letting δa = δa. Again, the definition makes sense because the ideal is differential: the class of δa only depends on the class of a, not on a [18, chap. I, §2].

If A is a finite subset of R, one denotes (A) the smallest ideal containing A w.r.

t. the inclusion relation and [A] the smallest differential ideal containing A.

If A is an ideal, then √ A, which is called the radical of A, is the set of all the ring elements a power of which lies in A [41, chap. III, §7]. The radical of a (differential) ideal is a (differential) ideal [32, chap. I, §9]. A radical (perfect in the Ritt-Kolchin terminology) ideal is an ideal equal to its radical. If S = {s 1 , . . . , s t } is a finite subset of R \ K then 3 Two inference rules and a theorem Throughout this paper, Σ denotes a finite subset of the polynomial differential ring R = K{U } endowed with m abstract derivations δ 1 , . . . , δ m . Naively, a solution of Σ is a n-tuple of "values" which, when substituted in the equations of Σ, annihilate them. We are concerned by the type of algebraic structure G in which these values can lie. The differential elimination methods cited in the introduction rely on two inference rules and one theorem. The inference rules are, for all differential polynomials p, q ∈ R:

A : S ∞ = {p ∈ R | ∃ a 1 , . . . , a t ∈ N, s a1 1 • • • s at t p ∈ A}
1. p = 0 ⇒ θp = 0 where θp denotes a derivative of p of any order,

2. p q = 0 ⇒ [p = 0 or q = 0].
The key theorem is a Nullstellensatz. See [32, Theorem 1 (Nullstellensatz) Every radical differential ideal of R is an intersection of prime differential ideals.

To enlighten the consequences of the inference rules, let us take for first example an ordinary polynomial differential system made of a unique equation, a famous example [32, chap. II, example 1] of Ritt:

u 2 x -4 u = 0.
The first inference rule implies that one does not change the solutions of this system by augmenting it with the infinite set of the derivatives of the equation:

u 2 x -4 u = 0, 2 ux uxx -4 ux = 0, 2 ux uxxx -2 u 2 xx -4 uxx = 0, . . . (1)
Observe that the second equation factors:

2 u x u xx -4 u x = 2 u x (u xx -2).
The second rule implies that any solution of the system annihilates either the first or the second factor. Thus the system is equivalent to the disjunction:

u 2 x -4 u = 0, u x = 0 or u 2 x -4 u = 0, u xx -2 = 0
If one solves these systems by means of Analysis, one actually gets two solutions of the initial equation: the zero function u(x) = 0 and the family of parabolas u(x) = (x+c) 2 where c is some constant. With the wording of Analysis, the first rule implies that one needs to look for solutions in terms of smooth functions (over some open set which would need to be precised). This is a restriction: consider the function f (x) of one real variable, which is zero over R -and equal to x 2 over R + . It is only differentiable once at x = 0. If one looks for solutions over some open set containing zero, this solution is lost. Our second example is given by the "differential" equation u v = 0 of the differential polynomial ring Q{u, v} endowed with the derivation δ x = ∂/∂x. Applying the second inference rule, one sees that it is equivalent to:

u = 0 or v = 0.
Now, consider the function f (x) of one real variable, which is zero over R -and equal to e -1

x 2 over R + and the function g(x) the graph of which is symmetrical to that of f (x) w.r.t. the ordinates axis. These two functions are smooth but non analytic over any open set containing zero. Over any such open set, the pair (f (x), g(x)), which is a solution of the initial equation, does not annihilate any of the two systems produced after the splitting cases process: it is lost.

Summary 1

• The algebraic structures G in which one seeks solutions for Σ must be Kalgebras, differential (one needs to be able to differentiate their elements infinitely many times) and integral domains.

• Whatever the differential polynomial p ∈ [Σ] the systems Σ and Σ ∪ {p} have the same set of solutions.

Abstract solutions

Theorem and definition 1 Define an abstract solution of Σ as a pair:

1. a differential field extension G of K, . One needs to show that Σ admits an abstract solution which does not annihilate p. Theorem 1 implies that there exists a prime differential ideal p which contains Σ but not p. The ring R/p is a domain since p is prime. It is differential since p is differential. Take for G the ring of fractions of the residue class ring R/p and for u 1 , . . . , u n the images of the differential indeterminates by the natural ring homomorphism R → G. Evaluating a differential polynomial at u 1 , . . . , u n amounts to taking its image by φ. The elements of Σ are mapped to zero. The polynomial p is mapped to some nonzero element of G.

Abstract solutions are very satisfactory from an algebraic point of view but, in practice, one would like to interpret the abstract derivations as derivations w.r.t. independent variables (δ i = ∂/∂x i ) and one would like solutions to be n-tuples of "functions" of m variables u j (x 1 , . . . , x m ). This is done in section 7 but first, one introduces characteristic sets, normal forms and purely algebraic solutions of differential ideals.

Characteristic sets and normal forms

Definition 1 A ranking is a total ordering over ΘU which satisfies the two following axioms:

1. v ≤ θv for every v ∈ ΘU and θ ∈ Θ, 2. v < w ⇒ θv < θw for every v, w ∈ ΘU and θ ∈ Θ.

See [18, chap. I, sect. 8]. Rankings such that ord θ < ord φ ⇒ θu < φv for every θ, φ ∈ Θ and u, v ∈ U are called orderly. Rankings such that θu < φu ⇒ θv < φv for every θ, φ ∈ Θ and u, v ∈ U are called Riquier. These two special types of rankings will be especially useful in section 8.

Fix a ranking. Consider some differential polynomial p / ∈ K. The highest derivative v w.r.t. the ranking such that deg(p, v) > 0 is called the leading derivative of p. It is denoted ld p. The leading coefficient of p w.r.t. v is called the initial of p. The differential polynomial ∂p/∂v is called the separant of p. If C is a finite subset of R \ K then I C denotes its set of initials, S C denotes its set of separants and

H C = I C ∪ S C .
A differential polynomial q is said to be partially reduced w.r.t. p if it does not depend on any proper derivative of the leading derivative v of p. It is said to be reduced w.r.t. p if it is partially reduced w.r.t. p and deg(q, v) < deg(p, v). A set of differential polynomials of R \ K is said to be autoreduced if its elements are pairwise reduced. Autoreduced sets are necessarily finite [18, chap. I, sect. 9]. To each autoreduced set C, one may associate the set L = ld C of the leading derivatives of C and the set N = ΘU \ ΘL of the derivatives which are not derivatives of any element of L (the derivatives "under the stairs" defined by C).

Example. The following system

C v xx -u x , v y - u x u y 4 , u 2 x -4 u, u 2 y -2 u
is autoreduced w.r.t. the Riquier orderly ranking:

u < v < u y < u x < v y < v x < u yy < u xy < u xx < v yy < • • •
The set of leading derivatives is L = {v xx , v y , u x , u y }. The set of the derivatives which are not derivatives of any element of

L is N = ΘU \ ΘL = {u, v, v x }.
It turns out to be finite here.

Ritt's reduction algorithm is a generalization for differential polynomials of the classical pseudoremainder algorithm (prem) defined in [17, vol. 2, page 407]. Ritt's algorithm is presented in [18, chap. I, sect. 9]. Given a differential polynomial p and an autoreduced set C, it permits to compute a set of exponents a 1 , . . . , a t ∈ N and a differential polynomial p ′ partially reduced w.r. Every radical differential ideal can be decomposed as a finite intersection of differential ideals A i defined by characteristic sets C i . Algorithms performing this task are described in [START_REF] Boulier | Computing representations for radicals of finitely generated differential ideals[END_REF][START_REF] Li | Coherent, regular and simple systems in zero decompositions of partial differential systems[END_REF][START_REF] Hubert | Factorization free decomposition algorithms in differential algebra[END_REF]. The characteristic sets produced by these algorithms hold an extra property:

A i = [C i ] : H ∞ Ci .
They are called characterizable in [START_REF] Hubert | Factorization free decomposition algorithms in differential algebra[END_REF]. The next lemma is well-known.

Lemma 1 If C is a characteristic set of a differential ideal A of R then every element of A is reduced to zero by C. If moreover A = [C] : H ∞ C then
Proof Denote C = {c 1 , . . . , c t }. Assume ld c 1 < • • • < ld c t . For each 1 ≤ k < t, denote C k = {c 1 , . . . ,
H ∞ C are equal. The set C is a characteristic set, in the non differential sense, of (C) : I ∞ C since it is a characteristic set of [C] : H ∞ C and (C) : I ∞ C ⊂ [C] : H ∞ C . According to [1, Theorem 6.1], C is thus a regular chain [9, Definition 3.1] whence the initial i k of c k is regular modulo the ideal (C k-1 ) : I ∞ C k-1 for each 2 ≤ k ≤ t. By [9, Corollary 3.2], in the ring K(N )[L], the initial i k of c k is thus invertible modulo the ideal (C k-1 ):I ∞ C k-1 , for each 2 ≤ k ≤ t. Let us now place ourselves in K(N )[L]. The initial of c 1 lies in K(N ) and is invertible. Thus (C 1 ) = (C 1 ):I ∞ C1 . Assume that, for some 1 < k ≤ t one has (C k-1 ) = (C k-1 ) : I ∞ C k-1 . Then i k is invertible modulo (C k-1 ) and (C k ) : I ∞ C k = (C k ).
Putting the above argument in an inductive proof, the lemma is proven.

Definition 3 Let C be an autoreduced set, L = ld C and N = ΘU \ ΘL. Let h be an initial or a separant of some element of C. If h ∈ K then a pseudoinverse pair of h is defined as (1/h, 1) else it is defined as any pair (p, q) of nonzero differential polynomials such that p ∈ K[N ∪L], q ∈ K[N ] and h p ≡ q mod (C).

Proposition 1 Take the same notations as in definition 3 and assume more-

over that C is a characteristic set of [C] : H ∞ C .
Then every initial or separant h of C admits a pseudoinverse pair.

Proof One only needs to consider the case

h / ∈ K. Since h ∈ H C , it is regular modulo (C) : H ∞ C in the ring K[N ∪ L]. By [9, Theorem 1.1 and Corollary 1.15], it is thus invertible modulo (C) : H ∞ C in the ring K(N )[L]. In this ring, (C) = (C):H ∞
C by Lemma 2 whence there exists a polynomial r such that r h-1 ∈ (C). Multiplying by some suitable nonzero polynomial q ∈ K[N ] in order to clear denominators and denoting p = r q, one gets a relation p h-q ∈ (C) in K[N ∪L] hence a pseudoinverse pair (p, q) of h.

Proposition 1 is essentially algorithmic since pseudoinverse pairs can be computed by means of the function algebraic inverse given in [START_REF] Boulier | Well known theorems on triangular systems and the D 5 principle[END_REF] which is based on [START_REF] Moreno | Polynomial gcd computations over towers of algebraic extensions[END_REF]. The restriction comes from the fact that this function may fail to compute the inverse of h though h is invertible for it needs to check the regularity of polynomials different from h. If such a failure occurs, the characteristic set C can be split as two smaller characteristic sets and the whole process restarted over these ones, following the "D 5 principle".

Example (continued). The separant of u 2

x -4 u is 2 u x . A pseudoinverse pair of 2 u x is (u x , 8 u). The function algebraic inverse of [START_REF] Boulier | Well known theorems on triangular systems and the D 5 principle[END_REF] would obtain it by computing a Bézout identity between 2 u x and u 2

x -4 u in the ring

Q(u)[u x ].
Proposition 2 The function NF given in Figure 1 returns a rational fraction f /g satisfying the following properties:

1. f is reduced w.r.t. C, 2. g ∈ K[N ]
and all its irreducible factors divide the second component of the pseudoinverse pair of some initial or separant of C,

3. g is regular modulo A, 4. g p ≡ f mod A, 5. for all p, p ′ ∈ R, one has p ≡ p ′ mod A iff NF(p, C) = NF(p ′ , C), 6. for all p ∈ R, one has p ∈ A iff NF(p, C) = 0. function NF(p, C) Assumptions p is a differential polynomial of R C = {c 1 , . . . , c t } is a characteristic set of A = [C] : H ∞ C
One assumes that pseudoinverse pairs of the initials and separants of the elements of C can be computed (see the remark following Proposition 1). begin denote s 1 , . . . , s t the separants of the elements of C denote (p i , q i ) a pseudoinverse pair of s i (1 ≤ i ≤ t) using Ritt's reduction algorithm, compute a 1 , . . . , a t ∈ N and

r t+1 ∈ K[N ∪ L] such that s a1 1 • • • s at t p ≡ r t+1 mod A f t+1 := p a1 1 • • • p at t r t+1 g t+1 := q a1 1 • • • q at t denote v i = ld c i (1 ≤ i ≤ t) and assume v t > • • • > v 1 for ℓ from t to 1 by -1 do r ℓ := prem(f ℓ+1 , c ℓ , v ℓ ) denote (p ℓ , q ℓ ) a pseudoinverse pair of the initial i ℓ of c ℓ let a ℓ ∈ N be such that ı a ℓ ℓ f ℓ+1 ≡ r ℓ mod (c ℓ ) f ℓ := p a ℓ
ℓ r ℓ g ℓ := q a ℓ ℓ g ℓ+1 od return f 1 /g 1 One may make the rational fraction irreducible by computing the gcd of f 1 and g 1 as multivariate polynomials over the field K end

(f ℓ , v k ) < deg(c k , v k ) for each t ≥ k ≥ ℓ.
Putting the above argument in an inductive proof, one sees that f = f 1 is partially reduced w.r.t. C and deg(f

1 , v k ) < deg(c k , v k ) for each t ≥ k ≥ 1 i.e. that f is reduced w.r.t. C.
Item [START_REF] Boulier | The BLAD libraries[END_REF]. All polynomials g i are power products of the second components of the pseudoinverse pairs of the initials and separants of C. They belong to K[N ] by Proposition 1. The final simplification of the rational fraction f 1 /g 1 may remove some factors of g 1 . Item (3). One assumes that there exists some g ∈ R such that g g ∈ A. One proves that g ∈ A. The polynomial g may be chosen partially reduced w.r.t. C (if not, replace it by its partial remainder w.r.t. C). The polynomial g g is reduced to zero by C (Lemma 1). Since it is partially reduced w.r.t. C, the reduction process is purely algebraic hence g g ∈ (C) : I ∞ C . By the equidimensionality argument of Lazard's lemma [9, Theorem 1.6], the associated prime ideals of (C) :

I ∞ C do not meet K[N ] \ {0}
(the fact that N may be infinite does not raise any theoretical problem since one may restrict N to the derivatives which actually occur in the polynomials). Thus g does not lie in any associated prime ideal of (C) : I ∞ C and, by [41, chap. IV, §6, Corollary 3], is regular modulo that ideal. Therefore g ∈ (C) : I ∞ C ⊂ A and the proof of item (3) is complete. Item (4). At the beginning of the function, s a1 1 • • • s at t p ≡ r t+1 mod A. Multiplying both sides of the congruence by p a1 1 • • • p at t and simplifying each s i p i by q i according to Proposition 1, one gets the relation g t+1 p ≡ f t+1 mod A. Let now t ≥ ℓ ≥ 1 be a loop index, consider the sequence of instructions of the loop body and assume that g ℓ+1 p ≡ f ℓ+1 mod A. Multiply both sides of this congruence by p a ℓ ℓ ı a ℓ ℓ . On the lefthand-side, replace each p ℓ i ℓ by q ℓ according to Proposition 1. On the righthand-side, replace ı a ℓ ℓ f ℓ+1 by r ℓ . Using the fact that c ℓ ∈ A one gets g ℓ p ≡ f ℓ mod A. Putting the above argument in an inductive proof, item (4) is proven. Item [START_REF] Boulier | Étude et implantation de quelques algorithmes en algèbre différentielle[END_REF]. Denote f /g = NF(p, C) and f ′ /g ′ = NF(p ′ , C). The implication from left to right. Assume p ≡ p ′ mod A. Then g g ′ p ≡ g g ′ p ′ mod A. By item (4) g ′ f -g f ′ ∈ A. Since g, g ′ ∈ K[N ] by item (2) and f, f ′ are reduced w.r.t. C by item (1), the difference g ′ f -g f ′ is reduced w.r.t. C hence equal to zero by the definition of characteristic sets. Thus f /g = f ′ /g ′ . The implication from right to left. Assume f /g = f ′ /g ′ . Then g ′ f = g f ′ hence, by item (4), g g ′ p ≡ g g ′ p ′ mod A. Since g and g ′ are regular modulo A by item (3), one has p ≡ p ′ mod A and item (5) is proven. Item (6) follows from item (5) and the fact that NF(0, C) = 0.

Example (continued).

Here are the normal forms of some elements of ΘU , computed with the help of the BLAD libraries over the example. See [START_REF] Boulier | The BLAD libraries[END_REF] and [3, chap. 6].

derivative normal form derivative normal form u u u xx 2 v v u xy u x u y /(2 u) u y u y u yy 1 u x u x v xx u x v y (1/4) u x u y v xy u y v x v x v yy (1/2) u x
6 Purely algebraic solutions of differential ideals Definition 4 Let A be a differential ideal of the polynomial differential ring R = K{U } and G 0 be a field extension of K. A map φ : ΘU → G 0 , which extends to a ring homomorphism K[ΘU ] → G 0 , is a purely algebraic solution of A if φ annihilates all the elements of A.

Informally speaking, a purely algebraic solution of a differential ideal A is obtained by viewing A as a nondifferential ideal of the ring K[ΘU ] and determining a solution of it. The difficulty, which comes from the fact that the set of unknowns is infinite, is overcome by means of the normal form algorithm.

Lemma 3 Let A be a differential ideal of the polynomial differential ring R = K{U } and G 0 be a field extension of K. Let C be a characteristic set of A and φ : ΘU → G 0 be a map, which extends to a ring homomorphism K[ΘU ] → G 0 . Let h be an initial or a separant of C and (p, q) be a pseudoinverse pair of h. Assume φ annihilates all the elements of C. Then φ(h) = 0 if and only if φ(q) = 0. If φ(h) = 0 for each initial or separant h of C then φ does not annihilate any denominator of NF(R, C).

Proof Since h p ≡ q mod (C), the first statement is clear. The second statement then follows from item (2) of Proposition 2. 1. for all v ∈ N ∪ L, assign to φ(v), values, taken in some field extension G 0 of K, which annihilate the elements of C but does not annihilate their initials and separants.

2. for all v ∈ ΘL \ L, assign then to φ(v) the value of NF(v, C).

Proof The map φ is well-defined. Since C is a characteristic set of [C] :

H ∞ C , the ideal (C) : H ∞ C of the ring K[N ∪ L] is not

Formal power series solutions

This section is dedicated to the construction of formal power series solutions of systems of polynomial differential equations. It is the first half of the way leading to analytic solutions. Reference texts for this section are [START_REF] Seidenberg | Abstract differential algebra and the analytic case[END_REF][START_REF] Seidenberg | Abstract differential algebra and the analytic case II[END_REF]. See also [START_REF] Rust | Existence and Uniqueness Theorems for Formal Power Series Solutions of Analytic Differential Systems[END_REF][START_REF] Hubert | Computing Power Series Solutions of a Nonlinear PDE System[END_REF]. The m derivations δ 1 , . . . , δ m are interpreted as m partial derivations w.r.t.

m independent variables x 1 , . . . , x m . If θ = δ a1 1 • • • δ am m is a derivation operator, one denotes x θ = x a1 1 • • • x am m and θ! = a 1 ! • • • a m !.
One looks for formal power series solutions of A i.e. solutions of the form:

u j = c j,θ x θ θ! •
The coefficients c j,θ belong to some field extension G 0 of K which depends on the considered system Σ or, more simply, in the field C. First remark: the above formal power series is centered on the origin for simplicity but the arguments hold for formal power series centered on any element of R m . Second remark: the above setting covers also the case of differential systems with coefficients in the field Q(x 1 , . . . , x m ). Indeed, it is then sufficient to encode each independent variable x i as a new differential indeterminate z i and to append to the system under study, the equations δ j z i = 1 if i = j and 0 otherwise. One thus assumes w.o.l.o.g. that K is a field of constants.

Proposition 4 Let G 0 be a field extension of K and φ : ΘU → G 0 be a map, extending to a ring homomorphism K[ΘU ] → G 0 . Then φ is a purely algebraic solution of A if and only if the n-tuple u = (u 1 , . . . , u n ) is a formal power series solution of A where

u j = θ∈Θ φ(θu j ) x θ θ! , 1 ≤ j ≤ n.
Moreover, for each differential polynomial p ∈ R, if φ(p) = 0 then p(u) = 0.

Proof See [START_REF] Seidenberg | Abstract differential algebra and the analytic case[END_REF]Lemma]. If p ∈ R is a differential polynomial then p(u) = φ(θp) x θ /θ!. Therefore p(u) is zero if and only if φ(θp) is zero for all θ ∈ Θ. Thus φ is a purely algebraic solution of A if and only if u is a formal power series solution of A. The last part of the proposition is clear.

Example (continued). One illustrates the proposition over the example of section 5. The map φ should be understood as the evaluation over the expansion point of the series i.e. φ(w) = w(0, 0) for any derivative w. One assigns to u(0, 0) any nonzero value (since u is a denominator of NF(ΘU, C) and must not vanish). One assigns to v(0, 0) and v x (0, 0) any value. The values assigned to u x (0, 0) and u y (0, 0) must then be compatible with the equations of C (differential equations, which impose equalities between functions, must be satisfied for all values of x and y hence, in particular, for x = y = 0). The equations to be satisfied are:

u x (0, 0) 2 -4 u(0, 0) = 0, u y (0, 0) 2 -2 u(0, 0) = 0.
Let us thus choose three arbitrary constants c 0 , c 1 , c 2 ∈ R such that c 0 = 0 and

c 1 , c 2 ≥ 0 then let (u(0, 0), v(0, 0), v x (0, 0), u x (0, 0), u y (0, 0)) = (c 0 , c 1 , c 2 , 2 √ c 0 , √ 2 c 0 ).
The values assigned to all the other derivatives w are then uniquely determined for we have:

w(0, 0) = NF(w, C)(0, 0).
It turns out that all normal forms of derivatives are identically zero at some order hence that the formal power series solutions are polynomials:

u(x, y) = c 0 + 2 √ c 0 x + √ 2 c 0 y + x 2 + √ 2 x y + 1 2 y 2 , v(x, y) = c 1 + c 2 x + √ 2 c 0 2 y + √ c 0 x 2 + √ 2 c 0 x y + √ c 0 2 y 2 + 1 3 x 3 + √ 2 2 x 2 y + 1 2 x y 2 + √ 2 12 y 3 .
Theorem and definition 2 Define a formal power series solution of Σ as a pair:

1. a field extension G 0 of K,

2. a n-tuple (u 1 , . . . , u n ) ∈ G = G 0 [[x 1 , . . . , x m ]
] n which annihilates the elements of Σ.

Then a differential polynomial p ∈ R vanishes over all the formal power series solutions of Σ if and only if p ∈ [Σ]. In particular, Σ has no formal power series solution if and only if

1 ∈ [Σ].
Proof The implication from right to left is immediate using the arguments given in Summary 1. For the implication from left to right, consider some differential polynomial p / ∈ [Σ]. One needs to show that Σ admits a formal power series solution which does not annihilate p. Theorem 1 implies that there exists some prime differential ideal p which contains Σ but not p. This ideal admits characteristic sets w.r.t. any ranking. Let C be one of them. Since p is prime, p = [C] : H ∞ C [32, chap. II, §5] and one may apply Proposition 3. The map φ may be chosen so that φ(NF(p, C)) = 0 whence φ(p) = 0, taking e.g. G 0 to be the field of fractions of

K[N ∪ L]/(p ∩ K[N ∪ L])
. By Proposition 4, the map φ provides a formal power series solution of Σ which does not annihilate p.

Analytic solutions

Let us proceed on the second half of the way started in the former section and address the case of analytic solutions i.e. formal power series solutions which converge in some open set D. The proof of the Theorem and Definition 3 is split into Propositions 5 and 7.

Proposition 5 Assume that every prime differential ideal of R admits an analytic solution. Then, for each p ∈ R, if p / ∈ [Σ] then Σ admits an analytic solution which does not annihilate p.

Proof By Theorem 1, it is sufficient to show that, if p is a prime differential ideal and p / ∈ p then p admits an analytic solution which does not annihilate p. Consider the differential ideal [p, p u n+1 -1] where u n+1 is some new differential indeterminate. This ideal admits abstract solutions (as well as formal power series solutions) according to the hypotheses and one of the already proven differential theorems of zeros. It is thus different from the unit ideal and is contained in some prime differential ideal p ′ of R{u n+1 }. On the one hand, no solution of p ′ annihilates p. On the other hand, there is a bijection between the solutions of p ′ and the solutions of p which do not annihilate p. Since every prime differential ideal admits an analytic solution, p ′ admits an analytic solution, and p admits an analytic solution which does not annihilate p.

The fact that every prime differential ideal admits an analytic solution is proven in Proposition 7. This result is known since the work [START_REF] Riquier | Les systèmes d'équations aux dérivées partielles[END_REF] of Riquier. Riquier's theorem, which is a generalization of the Cauchy-Kovalevska theorem, is the basis of [32, chap. VIII] and of the Embedding Theorem [START_REF] Seidenberg | Abstract differential algebra and the analytic case[END_REF][START_REF] Seidenberg | Abstract differential algebra and the analytic case II[END_REF] of Seidenberg. Germa [START_REF] Péladan-Germa | Tests effectifs de Nullité dans des extensions d'anneaux différentiels[END_REF] clarified the relationship between characteristic sets and the hypotheses of Riquier's theorem. More recently, Lemaire [START_REF] Lemaire | Contribution à l'algorithmique en algèbre différentielle[END_REF] completely proved this latter anew, by using a more modern formalism and by distinctly separating the proof of the existence of formal power series solutions and the analyticity proof. The key result is Proposition 6 Let C be a characteristic set defining some prime differential ideal p, for some orderly Riquier ranking. Let L be the set of the leading derivatives of C and N = ΘU \ ΘL. Let (u 1 , . . . , u n ) be a formal power series solution of p, the coefficients c j,θ lying in the field of the complex numbers. Let (ũ 1 , . . . , ũn ) be the restriction to N of the solution i.e:

ũj = θ∈Θ cj,θ x θ θ! , 1 ≤ j ≤ n
defined by cj,θ = c j,θ if θu j ∈ N else zero. In the neighborhood of the origin, the series ũj are analytic if and only if the series u j are analytic.

Proof See [20, Théorème d'analyticité, page 50].

Proposition 7 Every prime differential ideal admits an analytic solution.

Proof Let p be some prime differential ideal. Let C be some characteristic set of p, for some orderly Riquier ranking. Let L be the set of the leading derivatives of C and N = ΘU \ ΘL. Among all the purely algebraic solutions of p, choose one such that only finitely many nonzero values are assigned to the elements of L ∪ N (there is no theoretical difficulty since there are only finitely many derivatives occuring in C). The restrictions to N of these formal power series are analytic since they are polynomials. to Proposition 6, the formal power series are analytic whence p admits an analytic solution.

Let us illustrate Proposition 6 over some famous linear example (historically, this is the very example used by Sophie Kovalevska to show the importance of expressing the most differentiated derivatives in terms of the other ones i.e. the importance of the orderly rankings): the heat equation

∂ 2 u ∂x 2 = ∂u ∂t •
This equation forms a characteristic set of the prime differential ideal that it generates, whatever the ranking. Over this example, the only thing which depends on the ranking is the leading derivative of the equation. If the ranking is orderly then the leading derivative is ∂ 2 u/∂x 2 else it is ∂u/∂t. The purely algebraic solution ∂ k+ℓ u ∂x k ∂t ℓ → (k + 2ℓ)! of the heat equation provides a formal power series solution

u(x, t) = (k + 2ℓ)! k! ℓ! x k t ℓ .
For x > 0 and t > 0, the series does not converge since it grows faster than the well-known divergent series: ℓ! t ℓ .

However, the restriction to

N = ∂ k u ∂x k | k ≥ 0
of the formal power series is indeed a convergent series:

u(x, 0) = x k = 1 1 -x •
The proposition (indeed, the Cauchy-Kovalevska theorem is sufficient here) tells us that this does not happen if the leading derivative is ∂ 2 u/∂x 2 . The following example, borrowed from [START_REF] Lemaire | An orderly linear PDE system with analytic initial conditions with a non analytic solution[END_REF], shows the importance of Riquier rankings:

∂ 2 u ∂x 2 = ∂ 2 u ∂x ∂t + ∂ 2 u ∂t 2 + v, ∂ 2 v ∂t 2 = ∂ 2 v ∂x ∂t + ∂ 2 v ∂x 2 + u.
One chooses the lefthand sides of the equations as leading derivatives. This is possible only if the chosen ranking is not Riquier. The ranking may however be orderly. The set N is formed of the derivatives of u differentiated at most once w.r.t. c and of the derivatives of v differentiated at most once w.r.t. t. One can form a formal power series solution (u, v) whose restriction to N is defined by

u(0, t) = ∂u ∂x (0, t) = e t , v(x, 0) = ∂v ∂t (x, 0) = e x .
It can be established that the formal power series u and v are not analytic in the neighborhood of the origin. However their restrictions to N are analytic. Proof By Propositions 5 and 7.

For functions of m complex variables, the following properties are equivalent: being differentiable once (i.e. being holomorphic), being smooth and being analytic. This is not the case for functions of m real variables (cf. the examples given at the beginning of this paper). It is worth noticing that the theorem of zeros also holds for smooth functions of m real variables. Indeed, if p ∈ [Σ] then every smooth solution of Σ is a solution of p (first, this is immediate if p lies in the differential ideal generated by Σ; second, if a power of a smooth function f is zero over some open set then f itself is zero over this set). Conversely, if p / ∈ [Σ] then Σ admits an analytic solution (hence a smooth solution) which does not annihilate p. It is the splitting cases mechanism implemented in the algorithms cited in the introduction which does not apply to smooth functions of m real variables. Last, observe that the theorem of zeros forces us to search analytic solutions with images in the field of the complex numbers but not necessarily analytic functions of m complex variables. As an example, consider the "differential" equation u 2 + 1 = 0. It admits for solutions the constant functions u(x) = ±i. These functions have images in C but the variable x may be real as well as complex.

On Denef and Lipshitz undecidability result

As shown in section 7, one can compute formal power series solutions of differential ideals defined by characteristic sets for all initial conditions (or purely algebraic solutions) which do not annihilate some finite set of polynomials. This restriction on admissible initial conditions is sometimes superfluous. Sometimes it is not, the following theorem shows, which is an almost immediate consequence of the undecidability result [START_REF] Denef | Power Series Solutions of Algebraic Differential Equations[END_REF]Theorem 4.11].

Theorem 2

The problem "given a characteristic set C and an expansion point α = (α 1 , . . . , α m ) ∈ Q m , determine if the differential ideal defined by C admits a formal power series solution centered on α" is undecidable for m ≥ 9.

Proof The proof starts exactly as in [START_REF] Denef | Power Series Solutions of Algebraic Differential Equations[END_REF]. Let P ∈ Z[a 1 , . . . , a m ] be a polynomial and u be a differential indeterminate. The next expression defines a linear partial differential equation 1 :

P x 1 ∂ ∂x 1 , . . . , x m ∂ ∂x m u = 0. (2)
First remark: if one substitutes a formal power series Second remark: a1,...,am

x a1 1 • • • x am m = 1 1 -x 1 • • • 1 1 -x m .
Combining both remarks, one concludes that, the following partial differential equation

P x 1 ∂ ∂x 1 , . . . , x m ∂ ∂x m u = 1 1 -x 1 • • • 1 1 -x m
has a formal power series solution u (which, if it exists, is necessarily convergent) if and only if the coefficients c a1,...,am satisfy: c a1,...,am = 1 P (a 1 , . . . , a m ) 1 Let us develop an example for casual readers. Take P (a 1 , a 2 ) = 3 a 2 1 + 2 a 2 . Then

P " x 1 ∂ ∂x 1 , x 2 ∂ ∂x 2 « u = 3 x 1 ∂ ∂x 1 " x 1 ∂ ∂x 1 u « + 2 " x 2 ∂ ∂x 2 « u = 3 x 1 ∂ ∂x 1 (x 1 ux 1 ) + 2 x 2 ux 2 = 3 x 2 1 ux 1 x 1 + 3 x 1 ux 1 + 2 x 2 ux 2 .
whence P (a 1 , . . . , a m ) = 0 for all (a 1 , . . . , a m ) ∈ N m . According to a celebrated theorem [START_REF] Matijasevic | Enumerable sets are diophantine[END_REF] of Matijasevic, the problem of determining whether a polynomial in Z[a 1 , . . . , a m ] admits an integer solution is undecidable for m ≥ 9 (negative answer to Hilbert's tenth problem). These arguments immediately apply to polynomial differential systems whose coefficients do not depend on the independent variables x i (the setting of this paper). It is sufficient to encode each independent variable x i by a differential indeterminate z i and to consider the following differential system C, which is a characteristic set for any ranking u ≫ (z 1 , . . . , z m ) such that every derivative of u is greater than any derivative of any z i :

(1 -z 1 ) • • • (1 -z m ) P z 1 ∂ ∂x 1 , . . . , z m ∂ ∂x m u = 1 ∂ ∂x j z i = 1 if i = j else 0.
What is the relationship between this theorem and the construction of formal power series solutions detailed in section 7 ? Consider the characteristic set at the bottom of the above proof. All the monomials of the first equation of C admit one of the z i differential indeterminates as a factor. Therefore, the initial of the first equation of C has the form z r i (1 -z 1 ) • • • (1 -z m ) where r is a positive integer and 1 ≤ i ≤ m is an index. In order to compute a formal power series solution of C, centered at (α 1 , . . . , α m ) ∈ R m , one must take care to the fact that the values associated to the derivatives z 1 , . . . , z m necessarily are the numbers α 1 , . . . , α m . The formal power series defined in [START_REF] Denef | Power Series Solutions of Algebraic Differential Equations[END_REF] is centered at (α 1 , . . . , α m ) = (0, . . . , 0) however, these initial conditions annihilate the initial of the first equation of C. The construction of formal power series solutions, based on Proposition 3 avoid them. There is thus no contradiction between all these results.

Conclusion

Differential algebra can be generalized in order to handle non commuting derivations. A generalization of Hilbert's differential theorem of zeros holds in this setting in the context of abstract solutions as well as in the context of formal power series solutions. See [START_REF] Hubert | Differential algebra for derivations with nontrivial commutation rules[END_REF][START_REF] Lemaire | Non-commutative riquier theory in moving frames of differential operators[END_REF]. However, formulating formal power series solutions by means of some normal form algorithm still needs to be done. Observe also that, to our knowledge, no analogues of the analyticity theorem (our Proposition 6) whence of Hilbert's differential theorem of zeros for analytic solutions are proven in the setting of non commuting derivations. This task is left for the future.

  following axioms: δ(a + b) = δ(a) + δ(b), δ(a b) = δ(a) b + aδ(b), (∀ a, b ∈ R)

  is called the saturation of A by the multiplicative family generated by S. The saturation of a (differential) ideal is a (differential) ideal [18, chap. I, Corollary toLemma 1].

  every element of R reduced to zero by C is an element of A. Proof Let p ∈ A be reduced to p ′ by C. Then p ′ ∈ A and is reduced w.r.t. C. It is thus zero. Let p ∈ R be reduced to zero by C. Then there exists a power product h of initials and separants of C such that h p ∈ A. If A = [C] : H ∞ C then p ∈ A according to the definition of saturations. Lemma 2 Let C be a characteristic set of the differential ideal [C] : H ∞ C . Denote L = ld C and N = ΘU \ ΘL. Then, in the ring K(N )[L], the ideals (C) and (C) : H ∞ C are equal.

Figure 1 :

 1 Figure 1: The NF function

Proposition 3

 3 Let A be a differential ideal of R and C be a characteristic set of A such that A = [C] : H ∞ C . Let L = ld C and N = ΘU \ ΘL. Then any map φ built as follows provides a purely algebraic solution of A.

  trivial and there exists a prime ideal p which contains C and does not contain any element of H C . The field G 0 may thus be chosen to be the field of fractions of K[N ∪ L]/p. Since the map φ does not annihilate the initials and separants of C, it does not annihilate any denominator of any element of NF(ΘU, C) by Lemma 3. The map φ is thus well-defined. The map φ provides a purely algebraic solution of A. It is sufficient to prove that, for any p ∈ R one has φ(p -NF(p, C)) = 0 since, in the case p ∈ A, one has NF(p, C) = 0 by item (6) of Proposition 2 whence φ(p) = 0. Now, φ(v -NF(v, C)) = 0 for all v ∈ ΘU . It is thus sufficient to prove that, for all p, p ′ ∈ R, if φ(p -NF(p, C)) = 0 and φ(p ′ -NF(p ′ , C)) = 0 then φ(p + p ′ -NF(p + p ′ , C)) = 0 and φ(p p ′ -NF(p p ′ , C)) = 0. The case of the sum is clear since NF(p + p ′ , C) = NF(p, C) + NF(p ′ , C). Let us prove that φ(p p ′ -NF(p p ′ , C)) = 0. One has NF(p p ′ , C) ≡ NF(p, C) NF(p ′ , C) mod A by item (4) of Proposition 2. Since normal forms are partially reduced w.r.t. C, the computation of NF(p p ′ , C) from the product NF(p, C) NF(p ′ , C) does not imply any differentiation of elements of C. Therefore, the congruence NF(p p ′ , C) ≡ NF(p, C) NF(p ′ , C) mod (C) : I ∞ C holds. Since φ annihilates the elements of C and does not annihilate their initials, one has φ(NF(p p ′ , C)) = φ(NF(p, C)) φ(NF(p ′ , C)) hence φ(p p ′ -NF(p p ′ , C)) = 0.

Theorem and definition 3

 3 Define an analytic solution of Σ as a n-tuple of functions (u 1 , . . . , u n ) of m real or complex variables, analytic over some open set D. Then a differential polynomial p ∈ R vanishes over all the analytic solutions of Σ if and only if p ∈ [Σ]. In particular, Σ has no analytic solution if and only if 1 ∈ [Σ].

  c a1,...,am x a1 1 • • • x am m whose coefficients are still to be determined in equation (2), one gets an expression: c a1,...,am P (a 1 , . . . , a m ) x a1 1 • • • x am m .

  2. a n-tuple (u 1 , . . . , u n ) ∈ G n which annihilates the elements of Σ.

	Then a differential polynomial p ∈ R vanishes over all the abstract solutions of Σ if and only if p ∈ [Σ]. In particular, Σ has no abstract solution if and only if 1 ∈ [Σ].
	Proof See [32, chap. II, sect. 7] or [11, sect. 1.4]. The implication from right to
	left is immediate, using the arguments given in Summary 1. For the implication
	from left to right, consider a differential polynomial p / ∈ [Σ]

  t. C (i.e. w.r.t. each element of C) such that s a1 1 • • • s at t p ≡ p ′ mod [C] where s 1 , . . . , s t denote the separants of the elements of C. Given a differential polynomial p ′ partially reduced w.r.t. C, it permits to compute a set of exponents b 1 , . . . , b t ∈ N and a differential polynomial p ′′ reduced w.r.t. C such that ı b1 1 • • • ı bt t p ′ ≡ p ′′ mod (C) where i 1 , . . . , i t denote the initials of the elements of C. When p ′′ = 0 one says that p ′ is reduced to zero by C. Definition 2 Let A be a differential ideal of R. A non empty subset C of A is said to be a characteristic set of A if it is autoreduced and A involves no nonzero element reduced w.r.t. C.

  c k }. Let us first place ourselves in the ring R. The ideal (C) : H ∞ C is radical by Lazard's lemma. See [6, Lemma 2], [26] or [9, Corollary 3.3]. Thus by [13, Proposition 3.3], the ideals (C) : I ∞

C and (C) :


Ioane Muni Toke

Stationary distribution of the volume at the best quote in a Poisson order book model

Keywords: limit order book, volume of the best quote, aggressive limit orders, aggressive market orders, killing and resurrecting Markov processes

We develop a Markovian model that deals with the volume offered at the best quote of an electronic order book. The volume of the first limit is a stochastic process whose paths are periodically interrupted and reset to a new value, either by a new limit order submitted inside the spread or by a market order that removes the first limit. Using applied probability results on killing and resurrecting Markov processes, we derive the stationary distribution of the volume offered at the best quote. All proposed models are empirically fitted and compared, stressing the importance of the proposed mechanisms.

Introduction

The limit order book has been for the past few years the subject of a growing interest among academics and practitioners studying financial markets. This electronic structure centralizes all the orders submitted to a given market by all participants, finds matchable buy and sell orders, and therefore defines the price of the financial product exchanged. The fundamental question is thus to understand how the sequences of submitted orders -the orders flows -are translated into price dynamics. [START_REF] Biais | An empirical analysis of the limit order book and the order flow in the paris bourse[END_REF] and [START_REF] Bouchaud | Statistical properties of stock order books: empirical results and models[END_REF] are pioneer investigations on the empirical properties of the limit order book. [START_REF] Smith | Statistical theory of the continuous double auction[END_REF] is a pioneer theoretical framework for the study of the continuous double auction that is used in limit order books.

The order book is a complex system. Basic mathematical models, such as [START_REF] Cont | A stochastic model for order book dynamics[END_REF], rely on simplifying assumptions: only three main types of orders are submitted (limit, market and cancellations, ignoring exchange-specific rules and specificities) ; all orders flows are Poisson processes ; all orders have the same unit size. [START_REF] Abergel | A mathematical approach to order book modeling[END_REF] shows that under appropriate assumptions, some limit theorems apply and such Markovian models lead to a diffusion equation for the price. Muni Toke (2015) shows that with similar Poisson models, the average shape of the order book is analytically computable, even when relaxing the unit-volume hypothesis.

Among the important quantities that describe a limit order book, the volume offered at the best quote (bid or ask), i.e. the total number of shares available at the first limit of the order book, is fundamental. One reason is that this quantity is often the only information easily available to market participants (known as Level-1 data). Another (linked) reason is that this quantity is heavily used in trading strategies by market participants : [START_REF] Farmer | What really causes large price changes?[END_REF] shows that the majority of market orders that move the price have a size exactly equal to the volume of the best quote at the time of submission (see below for more details). However, this volume remains difficult to model. When the volume of the best quote drops to zero (because of large market orders or cancellations that remove all the liquidity of the best quote), or when a new best quote is submitted inside the spread, the price changes, and the volume of the best quote is reset to a new quantity that may have no link to the quantities describing the last order submitted. Therefore, computing the volume of the best quote after a new event requires to keep track of the whole order book.

Recently, [START_REF] Cont | Order book dynamics in liquid markets: limit theorems and diffusion approximations[END_REF] proposes a model in which the order book is restricted to its first limits. When the price does not move, the volume at the best quote obviously varies according to the arriving orders flows, and when this volume drops to zero, the price moves and the volume at the best quote is immediately reset to some random value. Therefore, the volume of the best quotes (bid and ask) is a two-dimensional process with values on the positive orthant that jumps randomly inside the orthant each time it reaches an axis. [START_REF] Cont | Order book dynamics in liquid markets: limit theorems and diffusion approximations[END_REF] shows that under appropriate assumptions and using limit theorems in the spirit of queueing theory, this volume may approximately exhibit a jump-diffusive behaviour. There is however a very restrictive assumption for this model to be valid: the spread has to always be equal to one tick. Indeed, one cannot allow for limit orders submitted inside the spread in this framework, since it would make the process jumps even when it does not reach an axis. Such an assumption may be an appropriate model for busy periods of trading of so-called large tick stocks, but probably not in the general case.

Even more recently, [START_REF] Huang | Simulating and analyzing order book data: The queue-reactive model[END_REF] studied a limit order book modelled (with some constraints) by a collection of queueing systems, one per limit price, in which the intensities of arrival of orders (market, limit and cancellations) are dependent on the size of the queue at this limit price. It is shown that this model with size-dependent intensities is able to give a more realistic distribution of the volume available at the first limit than the classic Poisson model. Figure 1 (left panel) reproduces the distribution of the best quote observed in this model. It appears that such models of limit order books based on point processes with state-dependent intensities may provide fruitful results. Muni Toke & Yoshida (2017) obtain similar figures, also reproduced in Figure 1 (right panel), with a model in which the intensities of the orders flows depend on the spread and q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0 5 10 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Empirical Poisson Model several volumes characterizing the order book.

In this paper, we show that taking a different route, namely keeping the classical zero-intelligence order book model with Poisson processes, can still lead to interestingly similar results. In the full

Poisson model of the order book in this work, the stationary distribution of the volume offered at the best quote can be analytically and then numerically computed. The proposed model is basic but flexible. It does not assume that the spread is always equal to one tick, i.e. all types of events that make the volume of the best quote jump are taken into account: aggressive market orders that matches the full first limit, as well as aggressive limit orders submitted inside the spread as well.

The main idea is that such jumps of the volume at the best quote can be identified as killing and resurrecting a Markov process [START_REF] Pakes | Killing and resurrection of markov processes[END_REF]. The assumptions that all orders have to be unit-sized can even be lifted, with additional restrictions on the volume of market orders.

The remainder of the paper is organized as follows. Section 2 describes precisely the general zero-intelligence model of the order book with Poisson processes that is used here. The main result on killing and resurrecting Markov processes is recalled and adapted to the order book context. Sections 3 and 4 then explore two types of restrictive assumptions that allow the analytical computation of the stationary distribution of the volume at the best quote: Section 3 excludes market orders that partially match the best quote, while Section 4 allows for all types of market orders but with some size restrictions. Finally, Section 5 provides empirical fittings of all the analytical models proposed, with a comparison to the simulated "best effort" of the unrestricted Poisson model.

2 A Markovian model of the one-side order book

Model definition

Let us consider the best ask quote of an electronic order book (the model for the best bid is strictly identical). Three types of events can alter the quantity offered at the best quote : market orders, limit orders and cancellation of existing limit orders. For each type of order, we will distinguish between orders that move the price, called "aggressive" from now on, and orders that do not move the price, labelled "passive" hereafter1 .

Let us start with passive orders. We assume that passive limit orders (i.e. submitted at the best quote) are submitted according to a Poisson process with rate λ 1 and that the size of these passive limit orders form a set of independent and identically distributed random variables with probability distribution (g 1,n ) n∈N . We then assume that passive market orders are submitted according to a

Poisson process with rate µ and are all unit-sized (one share). Since a passive market order should not move the price, it cannot be submitted when there is only one share left. The third type of passive orders, passive cancellations, are modelled as follows: each unit-size component of a limit order (i.e. each share) standing at the best quote is cancelled some random time after its submission. All these random times are assumed to form a set of independent and identically distributed random variables with exponential distribution with parameter θ 1 > 0. Since passive cancellations should not move the price, the last share standing should not be removed by this process, so that if there is n 1 shares at the best quote, the total cancellation intensity is (n 1 -1)θ 1 .

Let us now turn to aggressive orders. Aggressive limit orders are limit orders submitted inside the spread, i.e. at a price lower than the current best ask. We will assume that aggressive limit orders are submitted according to a Poisson process with rate λ 0 , and that the size of all aggressive limit orders form a set of independent and identically distributed random variables with probability distribution (g 0,n ) n∈N . The effect of the submission of an aggressive limit order is simple: at the moment of the submission, this order instantly becomes the best quote, i.e. the ask price is reset to the price of the aggressive limit order, and the quantity available at the best quote is reset to the volume of the submitted limit order.

Aggressive market orders are submitted according to a Poisson process µ A , and their size is equal to the available quantity at the best quote at the time of the submission. In other words, aggressive q q q q q q q q q q q q q q qq q q q q q qq q q q q q q q q q q qqq q q qq q q q q q q q q q q q q q q q q q q q q q q q qq 2011 2012 2013 2014 2015 2016 0.5 0.6 0.7 0.8 0.9

1.0

Fraction of aggressive market orders exactly matching the best quote

Date Fraction q q q q q q q qq q q q q q q q q q qq qq q q q q q q q q q q q qq q q qq q q q q q q qq q qq q q q q q q q q q q q qq q q q q BNPP.PA ACCP.PA market orders match all the liquidity available at the best quote. This is not an unreasonable assumption: [START_REF] Farmer | What really causes large price changes?[END_REF] shows that on a 16-stock sample from the London stock exchange, 86% of the buy market orders that change the price have a size that is exactly equal to the volume offered at the best ask. It turns out that this figure is still valid with recent data: on Figure 2, the fraction of aggressive market orders that have a size equal to the volume of the best quote is plotted from 2011 to 2016 for two stocks traded on the Paris stock exchange, and in this period it indeed varies between roughly 80% and 90%. When an aggressive market order is submitted, the volume available at the best quote drops to zero, the price moves up and the quantity available at the best limit is instantaneously reset to the quantity available at the second limit of the order book (we'll say second limit for convenience, it is more precisely the next non-empty limit of the order book).

Note that an aggressive cancellation would be the cancellation of the last share at the best quote with volume one. Its effect is therefore strictly equivalent to the one of an aggressive market order. We can then without loss of generality for our model assume that the intensity µ A includes aggressive cancellations.

Because of the effect of aggressive market orders and cancellations, we also need to model the second limit of the order book. Using assumptions coherent with the Markovian setting we are establishing, we will assume the following: limit orders are submitted at the second limit (or more generally at any limit inside the book) according to a Poisson process with rate λ 2 ; the sizes of these limit orders form a set of independent and identically distributed random variables with probability distribution (g 2,n ) n∈N ; each unit-size component of a limit order (i.e. each share) standing at the second limit is cancelled some random time after its submission, and all these random times are assumed to form a set of independent and identically distributed random variables with exponential distribution with parameter θ 2 > 0.

Figure 3 summarizes the types of orders and notations introduced.

Remark 1. It is of course very well known that the memoryless assumptions made to build this stylized model (Poisson processes, exponentially distributed lifetimes of orders) are not satisfied in practice on financial markets, and that long-memory phenomena, clustering of events, etc. are commonly observed (see e.g. [START_REF] Abergel | Limit order books[END_REF] and references therein). More realistic modeling of the limit order book can for example rely on Hawkes processes (see e.g. [START_REF] Bacry | Hawkes processes in finance[END_REF] for a review), or non-Poisson point processes with state-dependent intensities (see e.g. [START_REF] Huang | Simulating and analyzing order book data: The queue-reactive model[END_REF], Muni Toke & Yoshida ( 2017)). The interest of this work is to show that even with basic non-realistic assumptions, our purely mechanistic description of the order book can produce empirically realistic distributions otherwise obtained with different principles.

Remark 2. In a full model, submission of aggressive limit orders should be spread-dependent, since these orders cannot be submitted when the spread is equal to one tick. This restriction is not included in the model described here, which is not state-dependent. This assumption makes the model more suitable for small tick stocks, for which the spread is generally not constrained to one tick, rather than for large tick stocks.

Stationary distribution of the best quote

In this general Poisson model, the continuous-time stochastic process X = {X(t), t ∈ [0, ∞)} describing the volume available at the best quote evolves as follows. Let τ 1 be the random time of the first price move. During the time interval [0, τ 1 ), in the absence of events that move the price (aggressive market orders/cancellations, aggressive limit orders), X evolves as the stochastic

process 1 + Y = {1 + Y (t), t ∈ [0, ∞)}
, which is one (the last share that cannot be cancelled or executed without moving the price) plus the size of a queue with the infinitesimal generator:

         -λ 1 λ 1 g 1,1 λ 1 g 1,2 λ 1 g 1,3 λ 1 g 1,4 . . . µ + θ 1 -(µ + λ 1 + θ 1 ) λ 1 g 1,1 λ 1 g 1,2 λ 1 g 1,3 . . . 0 µ + 2θ 1 -(µ + λ 1 + 2θ 1 ) λ 1 g 1,1 λ 1 g 1,2 . . . 0 0 µ + 3θ 1 -(µ + λ 1 + 3θ 1 ) λ 1 g 1,1 . . . . . . . . . . . . . . . . . . . . .          . (1)
Now, at time τ 1 , the price moves because of an aggressive limit order or an aggressive market order. The process X is instantaneously reset to a new random variable X τ 1 = H that, depending on the direction of the price move, represents either the size of the incoming aggressive limit order (downward price move), or the volume offered at the second limit inside the order book (upward price move). Then, if τ 2 is the random time of the next price movement, X on [τ 1 , τ 2 ) behaves according to the infinitesimal generator (1), and so on.

This mechanism is identifiable to what is known in applied probability as killing and resurrecting a Markov process. The process of the volume of the best quote starts at time 0 and evolves according to the infinitesimal generator (1). Then, upon the submission of an aggressive limit or market order, it is killed, and (instantaneously) resurrected to a random variable H with distribution (h i ) i∈N * , from where it restarts its course according the previous dynamics. Such a mechanism is studied in [START_REF] Pakes | Killing and resurrection of markov processes[END_REF], where the following result is proved.

Theorem 1 (rephrased from [START_REF] Pakes | Killing and resurrection of markov processes[END_REF].

Let Z = {Z t , t ∈ [0, ∞)} be a Markov process on N with initial distribution (h i ) i∈N . Zero state is assumed to be absorbing for Z. Let R = {R t , t ∈ [0, ∞)}
be the process constructed as follows : R starts following some path of the process Z ; at some random time (exponentially distributed with parameter β > 0), R is killed, i.e. reset to 0 ; after some random time (exponentially distributed with parameter α > 0), R is resurrected, i.e. restarts following a new path of the process Z ; and so on.

Then the process R admits a stationary distribution (π j ) j∈N) given by:

π 0 = β α + β -αβ f0 (β) , π j = απ 0 fj (β), ( 2
)
where fj is the Laplace transform of the series

i∈N h i p i,j (t), in which p i,j (t) = P(Z(t) = j|Z(0) = i)
is the transient probability of the (non-killed) process Z from state i to state j.

In our order book model, the resurrection is instantaneous, i.e. α → +∞ ; the killing events are aggressive limit and market orders, i.e. β = λ 0 + µ A by standard properties of the Poisson processes ; the state 0 is not accessible without killing (classic cancellations and partial market orders cannot deplete the best limit), i.e. f0 = 0. Another consequence of the last fact is that the distribution (h i ) i∈N * of H represents exactly the new volume available at the best quote after an aggressive event. This distribution is therefore a mix of the distribution (g 0,i ) i∈N * with probability λ 0 µ A + λ 0 and the stationary distribution of the volume at the second limit, denoted (π 2,i ) i∈N , with

probability µ A µ A + λ 0
. We thus obtain the following result.

Proposition 1. In the general Poisson order book model described in this section, the stationary distribution (π j ) j∈N * of the total volume offered at the best quote is written for any j ≥ 1 :

π j = (λ 0 + µ A ) fj (λ 0 + µ A ) (3)
where fj (•) is the Laplace transform of the series

i∈N h i p i,j (t) in which ∀i ∈ N * , h i = λ 0 g 0,i λ 0 + µ A + µ A π 2,i λ 0 + µ A , (4)
and p i,j (t

) = P(1 + Y (t) = j|1 + Y (0) = i)
is the transient probability of the (non-killed) process 1 + Y from state i to state j.

This result is central in this work. In the following, we will study several specifications of the above general model, all of them allowing analytical tractability at some cost. The first criterion dividing the different types of models is the presence or absence of "partial" market models. In the first type of model (Type-1 models), we assume that all market orders are aggressive market orders. In other words µ = 0, and there are no "partial" market orders that match only partially the best limit. In the second type of models (Type-2 Models), this restriction is lifted, i.e. market orders may or may not be aggressive (µ > 0), but some restrictions on the distributions of the volumes will be added. These different types of models are studied in the next two sections.

Models with aggressive market orders exclusively

Type-1 models assume that all market orders are aggressive, i.e. that µ = 0. In this setting, we are able to analytically compute the stationary distribution π of the process X through a direct approach: we compute the transient probabilities (p i,j (t)) i,j∈N by a standard generating function method, as well as the stationary distribution (π 2,i ) i∈N * by a direct method.

Let us start with the transient probabilities (p i,j (t)) i,j∈N . Let p i,j = r i-1,j-1 for any (i, j) ∈ (N * ) 2 . (r i,j (t)) i,j∈N are the transition probabilities of the process Y . The Kolmogorov forward equations are written for any (i, j) ∈ N 2 :

r ij (t) = -(λ 1 + jθ 1 )r ij (t) + (j + 1)θ 1 r i,j+1 (t) + j-1 k=0 λ 1 g 1,j-k r i,k (t). ( 5
) Let G 1 (z) = +∞ j=1
g 1,j z j be the generating function of the distribution of the sizes of incoming limit orders at the best limit. By multiplicating this equation by z j and summing over j, we obtain that the generating function

ϕ i (z, t) = ∞ j=0
r ij (t)z j is solution of the partial differential equation:

0 = ∂ϕ i ∂t (z, t) -θ 1 (1 -z) ∂ϕ i ∂z (z, t) + λ 1 (1 -G 1 (z))ϕ i (z, t), (6)
subject to the initial condition ϕ i (z, 0) = z i .

As for the stationary distribution (π 2,i ) i∈N * , we use the Markovian setting described in Section 2 : λ 2 > 0 is the rate of arrival of limit orders, (g 2,n ) n∈N is the distribution of their sizes, and 1/θ 2 is the average lifetime of a share standing inside the book. Similarly to what has been assumed for the best quote, we assume that the last share cannot be cancelled, so that the size of the queue does not drop to zero (it is by definition the next-non empty limit of the order book). With these assumptions, the size of the book at the second limit is the process

{1 + Y 2 (t), t ∈ [0, ∞)} with infinitesimal generator          -λ 2 λ 2 g 2,1 λ 2 g 2,2 λ 2 g 2,3 λ 2 g 2,4 . . . θ 2 -(λ 2 + θ 2 ) λ 2 g 2,1 λ 2 g 2,2 λ 2 g 2,3 . . . 0 2θ 2 -(λ 2 + 2θ 2 ) λ 2 g 2,1 λ 2 g 2,2 . . . 0 0 3θ 2 -(λ 2 + 3θ 2 ) λ 2 g 2,1 . . . . . . . . . . . . . . . . . . . . .          . ( 7
)
The process Y 2 admits a stationary distribution (ρ 2,i ) i∈N , and obviously π 2,i = ρ 2,i-1 . Writing the classical balance equations and solving the derived ODE for the generating function ψ(z) = +∞ n=0 ρ 2,n z n , we obtain :

ψ(z) = ρ 2,0 e λ θ z 0 1-G 2 (u) 1-u du ( 8
)
where G 2 (u) = ∞ g 2,i u i is the generating function of the distribution of the sizes of limit orders submitted inside the book.

Therefore, if we specify the distributions g 1 and g 2 of the sizes of incoming limit orders respectively at the best quote and inside the book, and if subsequent computations are analytically tractable, then we can derive the distribution π. We study two variants 1a and 1b of the model 1 setting. On the one hand, model 1a assumes that all limit orders submitted at the best quote or inside the book are unit-sized, i.e. g 1,1 = g 2,1 = 1 and g 1,n = g 2,n = 0 for any n ≥ 2. This assumptions is the one usually made in zero-intelligence models that look for some analytical tractability (see e.g. [START_REF] Cont | A stochastic model for order book dynamics[END_REF]). On the other hand, model 1b assumes that all limit orders submitted at the best quote or inside the book are geometrically distributed with parameters 0 < q 1 < 1 and 0 < q 2 < 1 respectively. This assumption has been used in Muni Toke (2015) in which it has been used to compute a general average shape of an order book. The results in these two cases are now stated.

Proposition 2 (Model 1a). If all limit orders at the best quote or inside the book are unit-sized, then the stationary distribution (π j ) j∈N * of the volume offered at the best quote is:

π j = (λ 0 + µ A ) ∞ i=1 h i min(i-1,j-1) k=0 i -1 k 1 (j -1 -k)! λ 1 θ 1 j-1-k × ∞ 0 e -(λ 0 +µ)t e -kθ 1 t (1 -e -θ 1 t ) i+j-2-2k e - λ 1 θ 1
(1-e -θ 1 t ) dt, (9) and

h i = λ 0 g 0,i µ A + λ 0 + µ A µ A + λ 0 e - λ 2 θ 2 (λ 2 ) i-1 (θ 2 ) i-1 (i -1)! . ( 10
)
Proof. The unit-size assumption gives G 1 (z) = z, and inserting this in equation ( 6) allows a direct solving of the latter as:

ϕ i (z, t) = 1 -(1 -z)e -θ 1 t i exp λ 1 θ 1 z -(1 -z)e -θ 1 t , (11)
which then gives after some computations, using Leibniz differentiation formula, the transition probabilities:

r ij (t) = min(i,j) k=0 i! k!(i -k)!(j -k)! λ 1 θ 1 j-k e -kθ 1 t (1 -e -θ 1 t ) i+j-2k e - λ 1 θ 1 (1-e -θ 1 t ) . ( 12
)
Shifting both indices by one, multiplying by h i , summing over i and taking the Laplace transform yields equation ( 9). Furthermore, still using the unit-size assumption, the stationary distribution of a process with defined in equation ( 7) is a Poisson distribution with parameter λ 2 θ 2 . This readily gives equation (10).

Proposition 3 (Model 1b). If all limit orders submitted at the best quote and inside the book are i.i.d. and geometrically-distributed with parameter q 1 and q 2 respectively, then the stationary distribution (π j ) j∈N * of the volume offered at the best quote is:

π j =(λ 0 + µ A ) ∞ i=1 h i q 1 λ 1 θ 1 min(i-1,j-2) k=0 i -1 k 1 (j -1 -k)! j-2-k l=0 j -1 -k l (-1) l × l α=1 λ 1 θ 1 -α(1 -q 1 ) j-2-k-l β=1 λ 1 θ 1 + β(1 -q 1 ) × +∞ 0 (1 -e -θ 1 t ) i-k e -(l+k)θ 1 t q 1 + (1 -q 1 )e -θ 1 t λ 1 θ 1 (1-q 1 ) -l-1 e -(λ 0 +µ)t dt + ∞ i=j h i i -1 j -1 +∞ 0 e -(j-1)θ 1 t (1 -e -θ 1 t ) i-j q 1 + (1 -q 1 )e -θ 1 t λ 1 θ 1 (1-q 1 ) e -(λ 0 +µ)t dt , (13)
and

h i = λ 0 g 0,i µ A + λ 0 + µ A µ A + λ 0 q λ 2 (1-q 2 )θ 2 2 (1 -q 2 ) i-1 (i -1)! Γ(i -1 + λ 2 (1-q 2 )θ 2 ) Γ( λ 2 (1-q 2 )θ 2 ) . ( 14
)
Proof.

The assumption of a geometric distribution of the sizes of limit orders inside the book gives

G 1 (z) = q 1 z 1 -(1 -q 1 )z
. With this definition of G 1 , we can solve equation (6) to obtain:

ϕ i (z, t) = [1 -(1 -z)e -θ 1 t ] i q 1 + (1 -q 1 )(1 -z)e -θ 1 t 1 -(1 -q 1 )z λ 1 θ(1-q 1 )
.

(15)

The Leibniz differentiation formula and some computations lead to the transient probabilities:

r ij (t) =q 1 λ 1 θ 1 min(i,j-1) k=0 i! k!(i -k)!(j -k)! (1 -e -θ 1 t ) i-k+1 × j-1-k l=0 j -1 -k l (-1) l e -(l+k)θ 1 t q 1 + (1 -q 1 )e -θ 1 t λ 1 θ 1 (1-q 1 ) -l-1 × l α=1 λ 1 θ 1 -α(1 -q 1 ) l β=1 λ 1 θ 1 + β(1 -q 1 ) + 1 j≤i i j e -jθ 1 t (1 -e -θ 1 t ) i-j q 1 + (1 -q 1 )e -θ 1 t λ 1 θ 1 (1-q 1 ) . ( 16
)
As in the previous case, shifting the indices by one, multiplying by h i , summing over i and taking the Laplace transform yields equation ( 13).

as for the stationary distribution of the volume offered at the second limit, the assumption of geometrically distributed sizes of limit orders gives G 2 (z) = q 2 z 1 -(1 -q 2 )z , and equation ( 8) gives by derivation and after some computations:

∀i ∈ N, ρ 2,i = q λ 2 (1-q 2 )θ 2 2 (1 -q 2 ) i i! Γ(i + λ 2 (1-q 2 )θ 2 ) Γ( λ 2 (1-q 2 )θ 2 ) , (17)
hence the result. Note that the distribution (ρ 2,i ) i∈N is a negative binomial distribution (or Polya distribution) with non-integer size parameter λ 2 (1 -q 2 )θ 2 and probability parameter q 2 (see e.g.

Feller 1968, Chap. VI.).

Models with both partial and aggressive market orders

Type-2 models allow for both partial and aggressive market orders to be submitted, i.e. µ > 0 and µ A > 0. With both types of market orders, the direct approach of the previous section does not provide analytically tractable results. Therefore we propose a different strategy. In this new setting, we can keep the tractability of the model at the cost of assuming that classic orders directly affecting the best quote are unit-sized. This is the only restriction: orders submitted inside the spread or inside the book can be kept with a general distribution, and the aggressive market orders are still defined the same way, obviously, with a size equal to the volume at the best quote. With this assumption, the best quote is a birth-and-death process, for which we can compute the Laplace transform of its transition probabilities, which can be expressed using continuous fractions. The original result dates back to [START_REF] Murphy | Some properties of continued fractions with applications in markov processes[END_REF] but a modern derivation of the result is found in [START_REF] Crawford | Transition probabilities for general birth-death processes with applications in ecology, genetics, and evolution[END_REF]. Therefore, we are able to study the stationary distribution of the volume available at the best quote without computing the transient probabilities of the process Y with infinitesimal generator (1) and µ > 0 (to our knowledge, such a computation is still an unresolved challenge).

Assume that both partial market orders and limit orders submitted at the best quote are unitsized. Then the process Y , which translates the evolution of the volume at the best quote (minus one) without any price movement, is a birth-and-death process with constant birth-immigration rate λ 1 and linear death-emigration rate µ+nθ 1 for any

n ≥ 0. Let (q m,n (t)), (m, n) ∈ N 2 , t ∈ [0, ∞)
be the transition probabilities of the process Y , and (q m,n (s)), (m, n) ∈ N 2 , s ∈ C their Laplace transform, if it exists. Let (B n (s)) n∈N the real sequence defined by the two-step recurrence:

B 0 (s) = 1, B 1 (s) = s + λ 1 , B n (s) = (s + λ 1 + µ + (n -1)θ 1 ) B n-1 -λ 1 (µ + (n -1)θ 1 ) B n-2 , n ≥ 2. ( 18
)
adapting Crawford & Suchard (2012, Theorem 1) to our special case, we have for any

(m, n) ∈ N 2 such that m ≤ n : qm,n (s) = λ n-m 1 â1 b1 + â2 b2 + â3 b3 +... λ n-m 1 â1 (s) b1 (s)+ â2 (s) b2 (s)+ â3 (s) b3 (s)+ . . . (19)
(The symbol is the definition equality that introduce a simplified notation for the continuous fractions.) In the above equation the sequences (â i ) i∈N * and ( bi ) i∈N * are defined as follows:

âi =          B m (s) if i = 1, -λ 1 (µ + (n + 1)θ 1 ) B n (s) if i = 2, -λ 1 (µ + (n + i -1)θ 1 ) if i ≥ 3, (20) and bi
=    B n+1 (s) if i = 1, s + λ 1 + µ + (n + i -1)θ 1 if i ≥ 2. ( 21
)
The result for any (m, n) ∈ N 2 such that m ≥ n is similarly written:

qm,n (s) =   m j=n+1 (µ + jθ 1 )   α1 (s) β1 (s)+ α2 (s) β2 (s)+ α3 (s) β3 (s)
+ . . . (22)
where the sequences ( αi ) i∈N * and ( βi ) i∈N * are defined as follows:

αi =          B n (s) if i = 1, -λ 1 (µ + (m + 1)θ 1 ) B m (s) if i = 2, -λ 1 (µ + (m + i -1)θ 1 ) if i ≥ 3, (23) and βi
=    B m+1 (s) if i = 1, s + λ 1 + µ + (m + i -1)θ 1 if i ≥ 2. ( 24
)
Hence, the Laplace transforms (q m,n (s)), (m, n) ∈ N 2 , s ∈ C are numerically computable using appropriate numerical methods for the computation of continuous functions. If we now go back to the killing and resurrection of Markov processes, we have the following result.

Proposition 4 (Type-2 models). If all orders submitted at the best quote are unit-sized, then the stationary distribution of the volume offered at the best quote is given by equation (3), i.e.

π j = (λ 0 + µ A ) ∞ m=1 h m qm-1,j-1 (λ 0 + µ A )
, where the qm,n 's are given by ( 19) and ( 22).

If limit orders submitted inside the are assumed to be unit-sized as well (model 2a), then the probabilities h m are given by equation (10). If the sizes of these limit orders are assumed to be geometrically distributed (model 2b), then the probabilities h m are obtained with equation (14).

5 Empirical results

Data and estimation

We use Thomson-Reuters tick-by-tick data for the stock BNPP.PA traded on the Paris stock exchange, from January 3rd, 2011 to May 20th, 2016, i.e. a five-year-and-five-month long sample.

This stock among the largest market capitalizations and most liquid stocks on the Paris stock exchange.

For each available trading day, we consider the data from 10:00 a.m. to 16:00 p.m., i.e. a six-hour period at the heart of the trading day. The idea is to get rid of the very busy opening and closing period where the assumption of a stationary model may be difficult to fulfil. It is well-known that even on the six-hour period considered, one does observe a seasonal activity (the U-shaped pattern of financial activity), and one might get better "stationary" results by shortening the daily period under investigation. However, it will appear that our models actually provides satisfying results even using the full day sample. For each stock, for each trading day, we compute the total numbers and the distributions of the sizes of: limit orders inside the spread; limit orders at the best quote; limit orders at the second best limit; partial market orders; and aggressive market orders.

We also compute the time-weighted empirical distribution of the volume offered at the best quote and at the second best limit. Details on data preparation can be found in Muni Toke (2016).

Straightforwardly, the estimators of the Poisson parameters λ 0 , λ 1 , λ 2 , µ and µ A (if needed by the model) are defined as the number of the associated events (aggressive limit order, limit order at the best quote, limit order inside the book, partial market orders, aggressive market orders)

divided by the length of the time interval. For each of these types of orders, we also compute their respective mean order size σ 0 , σ 1 , σ 2 , σ µ and σ µ A . As for the cancellation parameters, we do not have any data allowing us to track the submitted orders individually, and therefore we cannot easily estimate an average lifetime θ -1 1 and θ -1 2 for cancelled orders at the best quote and inside the book. However, we can get an order of magnitude by using equilibrium relations of incoming and outgoing flows of the order book. Our data let us compute the time-weighted average volume offered at the best quote L 1 and at the second best quote L 2 . Then equating the average number of incoming and outgoing share in the order book, we set θ 1 and θ 2 so that λ

1 σ 1 = µσ µ +µ A σ µ A +θ 1 L 1 and λ 2 σ 2 = θ 2 L 2 .
Finally, following our theoretical framework, we will assume that all partial market orders are unit-sized, and therefore rescale all size and volume quantities by the median trade size. The rescaling gives us the empirical versions of the distributions (g 0,i ), (g 1,i ), (g 2,i ) and (π 2,i ) (if needed the model) with a support roughly included in 1, . . . , 40. It may happen that the average rescaled limit order size at the best quote is actually smaller than the median trade size, forbidding a geometric modelling of the distribution (expectation lower than 1). In such cases (frequent from 2014 in our data, very rare before), the scaling size is set to a fraction of the median trade size, so that the average rescaled limit order size at the best quote is larger slightly larger that 1 (we've arbitrarily chosen 1.1 in the following empirical work).

Fitted models and benchmarks

In the previous section we have presented two types of models (namely type-1, without partial market order, and type-2, with unit-sized partial market orders), each type having two variants (namely, a and b). In variants a, the distribution (g 2,i ) i∈N * , which represents the volume of the limit orders submitted inside the book, is a Dirac distribution on the atom 1. In variants b, it is geometric with parameter 0 < q 2 ≤ 1. The distribution (g 0,i ) i∈N * , which represents the volume of the limit orders submitted inside the spread, has not been specified up to now. In line with the other assumptions, we will assume in this empirical section that this distribution is a Dirac on 1 in variants a, and a geometric distribution with parameter 0 < q 0 ≤ 1 in variants b.

We now add further elements of comparison for our models. First, for each type of model, we add a variant c in which both distributions (g 0,i ) i∈N * and (g 2,i ) i∈N * are taken equal to their empirical counterpart. Furthermore, in order to underline the importance of the mechanism that takes into account aggressive orders and consequent upward and downward movements of the best price, we recall as benchmark the following simplistic model of the best quote, in which aggressive market and limit orders are ignored, which is equivalent to assume a constant price in our setting. This benchmark will be referred to as the Type-0 model. In the Type-0 model, limit orders arrive at rate λ 1 with volume distribution (g 1,i ) i∈N ; market orders are unit-sized and arrive at rate µ ; all standing shares have a (i.i.d.) exponential lifetime with parameter θ 1 > 0. It is thus easily shown that the volume at the best quote in the Type-0 model is the Markov process with infinitesimal generator given at equation (1). This process admits a stationary distribution (π i ) i∈N satisfying the following recurrence :

     0 = -λ 1 π 0 + (µ + θ 1 )π 1 , 0 = -(λ 1 + µ + nθ 1 )π n + (µ + (n + 1)θ 1 )π n+1 + λ 1 n i=1 g 1,i π n-i (n ≥ 1), (25)
with

π 0 = µ θ 1 1 0 u µ θ 1 -1 e λ 1 θ 1 1 u H(v) dv du, -1 (26)
where

H(u) = 1 -G 1 (u) 1 -u
, G 1 being the generating function of the distribution (g 1,i ) i∈N (see e.g. Figure 5: Distribution (π i ) i∈N of the volume offered at the best quote for all the models described, compared to the empirical one, in semi-log-scale, for January 2014.

type 1 and 2 outperform the basic models of type 0, the latter failing to reproduce the empirical distribution. This outlines the importance of the flows of aggressive limit orders and aggressive market orders when describing the volume at the best quote. This quantity cannot be modeled by a simple queue with limit order, partial cancellation and partial market order.

It is enlightening to compare these shapes with the ones produced by more complete statedependent order book models such as the ones mentioned in Section 1. We complement these observations on the main body of the distribution by looking at the tail on Figure 5 (for brevity only one period is shown, but the analysis is valid for all periods). As expected, large differences between the models are observed when looking at the tail of the distribution.

Variants a, with unit-sized orders, exhibit the thinner tails. The geometric distributions for the size of orders at the best quote and in the book (variants b) allows for slightly heavier tails, but still much thinner than the empirically observed one. Interestingly, variants c exhibit a tail of the analytical distribution of the volume at the best quote that is much heavier. This hints that using the empirical distributions for the distributions (g 0,i ) i∈N (aggressive limit orders) and

(π 2,i ) i∈N (after an aggressive market order) is sufficient to obtain a heavy tail at the best quote, even if the distribution of the size of the limit orders arriving at the best quote is thin-tailed. This q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qqq q q q q q q 2011 2012 2013 again underlines the prime importance of the aggressive order flows modeled with the killing and resurrecting mechanism in our models.

We finally investigate the performances of the model over time. For each period, we plot on 6 the L 2 -distance between the computed (or simulated) distributions and the empirical one. For readability we have only included the versions of the models with geometric sizes (variants b), but other versions are very close. As observed above, the Poisson benchmark is outperformed by the proposed models. The performances of the proposed models are roughly constant through time on the tested sample, with a temporary decrease in the first part of 2013. The quality of the fit of models of type 1 and 2 is very similar, yet on this sample models of type 1 are in average slightly better that models of type 2. Recall that models of type 1 have only aggressive market orders (no partial market orders) but allow for a flexible (geometric) size of limit orders at the best quote, while models of type 2 require that all limit orders at the best quote are unit-sized. This observation underlines the potential importance of allowing general sizes of orders in a limit order book model. We also observe that the performances of the proposed models (of both types 1 and 2) is comparable to the one of model 3. This is a good achievement, since model 3 is the result of a simulation of a complete limit order book with all zero-intelligence parameters available while others models are limited. We may also observe a bit surprisingly that models of types 1 and 2 even provide in average a better fit of the volume at the best quote than the model 3. It may not be straightforward to explain this fact, so we will not risk a conjecture at the moment.

Remark 3. Models 1b is on average the best model on the whole sample. However, formula ( 14) involves several series and integrals that have to be numerically evaluated, which makes this model much more time-costly than the others. Using basic (non-optimized) straightforward Python implementations of the above formulas, using Scipy for the numerical integration with default numerical parameters, model 1b/1c require about 4 minutes to compute the whole distribution while models 1a needs less than 1 second and models of type 2 less than 2 seconds. These absolute values are obviously only indicative, since they are hardware-dependent and numerical optimization and enhancements might be performed, but the relative values may be important in selecting the appropriate model for a potential use.

Conclusion

This paper has shown that a basic zero-intelligence model of the limit order book is able to accurately describe the stationary distribution of volume offered at the best quote providing it includes a proper mechanism to take into account aggressive orders that move the price: aggressive limit orders submitted inside the spread, as well as aggressive market orders that remove the whole liquidity available at the first level of the book. We have modelled these aggressive orders using results on killing and resurrecting a Markov process (this process being here the quantity at the best quote when the price is constant), which allows us to provide analytical formulas for the distribution of interest.

We end this section by one last observation that may trigger future enhancements. Figure 7 shows that the theoretical models for (π 2,i ) i∈N have the same defects in modeling the empirical

Figure 1 :

 1 Figure 1: Distribution of the best quotes obtained in state-dependent limit order book models. Left panel reproduced from Huang et al. (2015) and right panel reproduced from Muni Toke & Yoshida (2017).

Figure 2 :

 2 Figure 2: Fraction of aggressive market orders that have a size exactly equal to the volume of the best quote from 2011 to 2016 for BNPP.PA and ACCP.PA.

Figure 3 :

 3 Figure3: Schematic diagram describing the stylized model of the order book and its three type of orders: limit orders (↓), market orders (←) and cancellations ( ).

  Figure 1 reproduces two distributions of the best quotes obtained by state-dependent models. More precisely, to obtain these shapes, Huang et al. (2015) use a model in which the intensities of submission of orders depend and the volume of the queue in which it is submitted, while Muni Toke & Yoshida (2017) use a model in which intensities of submission of orders depend on the spread, the volume at the best quote and the total volume of the book. It is very interesting to observe that a basic non-state-dependent time-homogeneous model such as the one proposed here is still able to reproduce sound shapes of the distribution of the volume at the best quote, very similar to the ones obtained by fuller models.

Figure 6 :

 6 Figure 6: Distance in L 2 -norm between the distribution of the volume at the best quote computed by each type of models and the empirical observation.

Figure 7 :

 7 Figure 7: Distribution (π 2 , i) i∈N (empirical, Poisson obtained with models 1a and 2a, and negative binomial obtaind with models 1b and 2b) of the volume at the second best quote, main body (left panel) and tail in semi-log-scale (right panel) for January 2014.

The concept of aggressiveness of orders is somewhat common in the financial microstructure literature, even though the precise definition of "aggressive" may vary with frameworks and authors. Such a terminology is already used in early works such as[START_REF] Harris | Market vs. limit orders: the superdot evidence on order submission strategy[END_REF] and[START_REF] Biais | An empirical analysis of the limit order book and the order flow in the paris bourse[END_REF] to classify orders: a limit order submitted inside the spread (i.e. moving the price) is labeled "more aggressive" than a limit order submitted at the best quote, which in turn is labeled "more aggressive" than a limit order submitted inside the book ; similarly, a market order larger than the volume available at the best quote (hence moving the price) is more aggressive than a market order matching only partially the first limit.

Acknowledgements

The author wishes to thank the participants of the 2015 IPAM Workshop on The Mathematics of High Frequency Financial Markets, as well as an anonymous referee for comments that helped improved the manuscript.

) i∈N ) in these variants is not a free parameter, but a consequence of the choice of (g 2,i ) i∈N (resp. (π 2,i ) i∈N ).

Muni Toke 2015, section 4). We will consider two cases: unit-sized limit orders (Model 0a) and limit orders with geometrically-distributed size with parameter q 1 (Model 0b). In line with the general models, one may assume that the last share cannot be cancelled or executed by shifting the indices of distribution (π i ) i∈N by 1 (i.e. on N * ).

Finally, we add a second benchmark by simulating our general zero-intelligence model of the best quote with all distributions of the model equal to their empirical counterpart. This could be considered as the "best effort" of a zero-intelligence mechanism with both classic and aggressive market and limit orders to compute the distribution of the volume offered at the best quote. Note that we cannot solve analytically the distribution in this general setting: the distribution in this case is numerically estimated by simulation. This simulated benchmark will be referred to as Type-3 model.

Table 1 summarizes the models that are under study here.

Empirical results

We split the sample into 65 monthly calendar periods. For each period, we compute the analytical distribution of the volume offered at the best quote for all our models and variants, as well as the distribution obtained by simulation of the model 3.

On figure 4 distribution of the volume inside the book as Type-0 models with respect to the volume at the best quote: namely, a body slightly shifted to the right and a tail too thin (only one period is plotted, but the observation is valid on the whole sample). This is not surprising as the volume inside the book as been treated here as one entity, without taking into account killing and resurrecting (as in models of Type-0). Future work may include the killing and resurrecting as a cascading effect:

when the price move, all the limits in the book are shifted, i.e. are killed and resurrected.