Eelco Eggen

M Niels De Keijzer

Bela M Mulder

Self-regulation in tip growth: the role of cell wall ageing

Keywords: tip growth, modelling, self-regulation, morphogenesis

We develop a model to describe the effect of cell wall ageing on the local expansion rate of tip growing cells. Starting from an exact equation for the stationary age-distribution of the wall material, we propose a generic measure for the local expansion propensity of the wall if the ageing process is described by a constant rate Poissonian decay process. This ageing process may be either interpreted as biochemical in nature describing the finite lifetime of regulatory proteins, or as mechanical in nature describing the gradual "hardening" of the wall through cross-linking or gelation of the wall polymers. In this way we can construct models for tip-growth in which material deposition, evolving wall properties and surface expansion are selfconsistently intertwined. As a proof of principle, we implement our ageing approach in two different idealized models of tip-growth, obtaining the stationary tip shapes as a function of the ageing parameter. In the first, the spatial distribution of delivery of growth material is determined by the local curvature of the cell and the growth mode is orthogonal. In the second, the growth material originates from a Vesicle Supply Center, a point-like representation of the Spitzenkörper as found in fungal hyphae, and the growth mode is isometric.

Introduction

Tip growth, the localized extension of walled cells at just one of their ends leading to a filamentous cell morphology, occurs in algae, fungi and higher plants (for an overview see Geitmann et al., 2001). This unique growth morphology is exploited by various organisms e.g. in reproduction (pollen tubes in plants, fungal hyphae) and for surface-area enhancement and mechanical anchoring (root hairs in plants). At first sight, tip growth seems to be a beguilingly simple example of biological morphogenesis: In general both growth velocity and tip shape remain approximately constant over time and in the absence of additional spatial cues the cell shape has cylindrical symmetry. In reality, it is quite a complex dynamical process which, first of all, involves the intracellular production of vesicles containing wall-building materials, the transport and localized delivery of these vesicles to the site of growth, where they subsequently undergo exocytosis, simultaneously adding phospholipids to the plasma membrane and depositing their contents to the nascent cell wall. [START_REF] Reinhardt | Das wachstum der pilzhyphen[END_REF], in one of the first papers that attempted to model tip growth, already concluded that the material properties of the cell wall over the apical region could not be homogeneous. He argued that the newly delivered material right at the tip should be easily deformable to allow for extensional growth, while the material farther from the tip should effectively rigidify to resist further expansion in the radial direction. Indeed, over the past few years a number of papers have appeared that recognize that a proper mechanical description of growth must involve the notion of a gradient in material properties over the apical region (Goriely and Tabor, 2003a,b;[START_REF] Dumais | An anisotropic-viscoplastic model of plant cell morphogenesis by tip growth[END_REF][START_REF] Fayant | Finite element model of polar growth in pollen tubes[END_REF]. In these approaches, however, this gradient is at the outset chosen to have a fixed, usually phenomenologically motivated, functional form. Almost two decades ago, [START_REF] Kataoka | Colchicine-induced expansion of Vaucheria cell apex. Alteration from isotropic to transversally anisotropic growth[END_REF], however, was the first to suggest that tip growth is possibly homeostatically controlled by a feedback mechanism whereby the local material state of the wall controls the local rate of incorporation of new material. Although his so-called "soft spot" hypothesis (see also [START_REF] Koch | The problem of hyphal growth in streptomycetes and fungi[END_REF]) rests on, with hindsight, physically and biologically shaky foundations, the idea by itself that there is feedback on the growth process due to some form of intrinsic dynamics of the wall material is plausible. In fact, the gradient of mechanical properties over the apical region must be the result of the interplay between the intrinsic wall dynamics and the growth process.

As far as we are aware, however, to date no attempt was made to selfconsistently include the intrinsic dynamics of the cell wall into the description of tip-growth. Here we formulate a generic model to account for the feedback of an ageing process of the wall material, whatever its precise microscopic origin, on the local expansion rate of tip-growing cells, showing that it leads to an additional level of self-organisation of the tip-growth process. We start by formulating an explicit model for the space-time evolution of the age distribution of the wall material during the growth process, and derive the equation that determines its form in steady state. We assume that the ageing process is well described by constant rate Poissonian decay process, describing either the finite life-time of co-deposited regulatory factors, or the on-going physico/chemical cross-linking of the wall polymers. On this basis we derive a phenomenological quantity that locally describes the "propensity" of the nascent wall to expand, given the availability of new growth material. We then show that this approach leads to analytically or numerically tractable models of tip growth that allow the systematic exploration of the influence of wall ageing on tip morphologies.

The outline of the paper is as follows: In Section 2 we introduce the geometrical setting of our tip growth model. In Section 3 we discuss the two main regulatory factors that determine the growth process, the so-called expansion propensity, which determines the rate at which locally available growth material contributes to growth, and the supply factor which describes the spatial dependence of the available material. In Section 4 we then present the application of our framework to two specific examples of simple models of tip growth, a purely geometrical model and a classical model for fungal hyphae. After the discussion in Section 5, a number of appendices collect some of the more technical details.

Geometrical setting

Surface shape

We assume that the tip-growing cell is in a stationary state. In this state growth proceeds at a constant velocity v, and while individual material points on the cell surface are undergoing a continuous dynamics, the shape of the cell as a whole is unchanged, apart from an overall translation in space in the direction of growth. Assuming the stationary shape is cylindrically symmetric, we can parametrize it through

r(s, ϕ) = (ρ(s) cos ϕ, ρ(s) sin ϕ, z (s)) , ( 1
)
where s is the arclength from the apex along a meridional section of the cell, ϕ is an azimuthal angle around the symmetry-axis, ρ the radial distance from the symmetry-axis to the surface, and z a coordinate along the symmetry axis. The unit vector normal to the surface is given by n(s, ϕ) = (-z (s) cos ϕ, -z (s) sin ϕ, ρ (s)).

(

) 2
where the prime throughout denotes differentiation with respect to s. If we define ψ as the angle between the surface normal and the positive z-axis we have

cos ψ = ρ (s), (3) sin ψ = -z (s). ( 4
)
The position of the apex is given by

ρ(0) = 0, z(0) = z 0 ,
where z 0 can be freely chosen to fix the origin of the reference frame along the axis of symmetry. This geometrical setting is illustrated in Figure 1. We further assume that the tip is smooth at the apex and consequently,

ρ (0) = 1, z (0) = 0,
and that as the distance to the apex becomes large, the shape tends to a cylinder with a constant radius

lim s→∞ ρ(s) = R, lim s→∞ ρ (s) = 0.
The infinitesimal element of surface area of the cell is simply given by dA (s, ϕ) = ρ (s) dsdϕ.

(5)

Finally, an important quantity characterizing the local properties of the surface is the mean curvature, which, in terms of our parametrization, is given by

H(s) = 1 2 1 -ρ (s) 2 ρ(s) - ρ (s) 1 -ρ (s) 2 . ( 6
)
We refer the reader to Appendix A for the relevant details.

Surface expansion

The growth process causes the surface to expand, but because of the anisometric tip shape this expansion rate is not constant over the surface. We define the local expansion rate Φ (s) as the increase of surface area per unit of existing area at a point a distance s away from the apex. In order for a stationary state to exist, where the apex moves with the constant growth velocity v, the local expansion rate must vanish as s → ∞.

For a co-moving observer the surface expansion reveals itself as a motion of material points within the surface in the direction pointing away from the apex. This flow speed of the material points again depends on the distance from the tip and is denoted by v (s). Clearly, lim s→∞ v(s) = v. In Appendix B we derive the following relationship between the local expansion rate and the flow speed:

ρ(s)Φ (s) = dρ(s)v(s) ds = ρ (s)v(s) + ρ(s)v (s) ( 7 )
To obtain the rate at which the surface area of an "apical cap", i.e. a part of the surface bounded by a longitudinal circle and containing the apex, increases, we integrate (7) over the appropriate area yielding Letting s → ∞ we find the expected result that total surface area increases as Ȧtot = 2πRv, where R = ρ(∞) is the final cell radius. This latter result illustrates how the stationary tip growing cell can keep its shape constant by effectively adding a cylindrical segment of area infinitely far away from the apex.

Growth mode

A three dimensional surface growth process is not fully specified by the local areal expansion rate Φ (s) alone. Generically, an initially circular infinitesimal element of surface area at time t will expand under the growth process into a shape that an infinitesimal time dt later is well approximated by an ellipse. Only the surface area of this ellipse ∝ a × b, where a and b are the length of the minor and major axes respectively, is fixed by the local areal expansion rate. The aspect ratio of the ellipse, i.e. the ratio b/a of the lengths of the axes, still needs to be determined. This quantity follows from the components of the rate of strain tensor (B.9) as derived in Appendix B. The orientation of the ellipse, however, is fixed by our assumption of cylindrical symmetry, which constrains the axes of the ellipse to lie along the meridional and azimuthal directions respectively. To give a realistic account of the full growth dynamics clearly requires considering the mechanical properties of the cell wall, which currently is an active area of research (see e.g. Goriely and Tabor (2003a); [START_REF] Dumais | An anisotropic-viscoplastic model of plant cell morphogenesis by tip growth[END_REF]; [START_REF] Campàs | Shape and dynamics of tip-growing cells[END_REF]; [START_REF] Fayant | Finite element model of polar growth in pollen tubes[END_REF]). However, this is beyond the scope of the current work, which focusses on the generic aspects of wall ageing on the overall expansion rate. In the illustrative examples presented in Section 4 we therefore limit ourselves to two geometrical models of growth that have been discussed in previous modelling efforts [START_REF] Gierz | A three-dimensional model of fungal morphogenesis based on the vesicle supply center concept[END_REF]. Both growth modes, either implicitly or explicitly, fix the ratio of the diagonal elements of the rate of strain tensor. For the relevant derivations we refer the reader to Appendix C.

The first growth mode we consider requires the motion of material points to be always perpendicular to the surface, yielding so-called orthogonal growth. This growth mode has in the past been suggested to be in accord with experimental observations [START_REF] Bartnicki-García | Mapping the growth of fungal hyphae: orthogonal cell wall expansion during tip growth and the role of turgor[END_REF] and is at the same time simply stated geometrically. In orthogonal growth both the flow speed of material points

v (s) = -vz (s) ( 9 )
and the local expansion rate

Φ(s) = 2vρ (s)H (s) (10)
are fully fixed by the geometry of the surface alone.

In the second growth mode we consider, the local element of surface area expands isotropically during growth, yielding so-called isometric growth. Although experiments have shown that in most cases filamentous growth displays clear strain anisotropies [START_REF] Castle | The topography of tip growth in a plant cell[END_REF]; [START_REF] Chen | The kinetics of tip growth in the Nitella rhizoid[END_REF]; [START_REF] Kataoka | Colchicine-induced expansion of Vaucheria cell apex. Alteration from isotropic to transversally anisotropic growth[END_REF]; [START_REF] Dumais | The mechanics of surface expansion anisotropy in Medicago truncatula root hairs[END_REF]), this growth mode has the advantage of greatly simplifying both the derivation of the shape equations as well as their numerical analysis. In isometric growth the flow speed is given by

v (s) = v R ρ(s), (11)
and the local expansion rate

Φ(s) = 2 v R ρ (s) . (12)

Regulation of expansion

We assume that the local rate of areal expansion the cell of is regulated by two distinct factors. The first is obviously the availability of new wallbuilding material which is delivered by intracellular mechanisms to specific location. We model this by a position dependent rate of delivery of material g (s) we call the supply factor. The second factor represents the regulatory influence of the material state of the cell wall on the degree to which the available wall material is actually used to contribute to expansion. In the simplest possible realization of this notion we model these effects through a multiplicative factor f (s), which we term the expansion propensity. With these assumptions we write

Φ(s) ∝ f (s) g (s) . ( 13
)
Below we address both the modelling of these two factors separately, but not before first considering the age distribution of the wall material.

Age distribution of wall material

Our basic assumption on the expansion propensity is that it depends only on the local properties of the existing wall material. These properties will in principle change over time, as the growth process is constantly altering the cell wall composition, due to the absorption of new wall building material and its subsequent ageing. In order to describe these ageing effects in the cell wall, we must give a description of the time elapsed since the incorporation of a certain portion of wall material. Therefore, each position on the cell surface is characterized by an age distribution defined as follows: Ψ(τ, s)dτ is the fraction of wall material at position s that has spent a time between τ and τ + dτ as a part of the wall. This distribution is normalized, such that

∞ 0 Ψ(τ, s)dτ = 1. ( 14
)
Given that we have a stationary growth process, the age distribution itself is time independent. This means that it is invariant under a set of transformations representing the growth dynamics. We can distinguish four processes due to the growth dynamics in the cell wall that affect the age distribution. First of all there is the intrinsic ageing process itself: with the passage of time physical and chemical processes cause changes in the material state of the wall. Then there are two kinematic effects due to the growth process: flow, the motion of material points away from the apex as the surface expands, and dilution, the same material is spread out over a larger area due to the expansion. Finally, there is rejuvenation, as new material is incorporated. These four processes are illustrated in Figure 2. We now consider a cohort of material points in small area ΔA(t) centered on a point at distance s from the apex, with ages between τ and τ + Δτ . Under the action of the growth process during an infinitesimal time dt this cohort will now occupy a slighter larger area ΔA(t+dt) = (1+Φ(s)dt)ΔA(t)+ O(dt 2 ), effectively 'diluting' the (surface) concentration. The area occupied by the cohort is now centered on s + v(s)dt + O(dt 2 ) due to the flow, and the ages of the cohort now range from τ + dt to τ + dt + Δτ due to the ageing process. In the steady state the local age distribution does not change over time and hence we require that to first order in dt

Ψ(τ + dt, s + v(s)dt)ΔA(t + dt)Δτ = Ψ(τ, s)ΔA(t)Δτ (15)
Expanding the left hand side to first order in dt, subtracting the right hand side, and canceling all common factors, then yields a first order PDE for the which is analogous to the well-known McKendrick-von Foerster equation describing the dynamics of age-structured populations in theoretical ecology [START_REF] Kot | Elements of mathematical ecology[END_REF], see e.g.), here, however, with a position dependent spatial drift term and a dilution effect, due to the surface expansion. Finally, the continuous influx of new material rejuvenates the age distribution. We assume that the amount of matter added per unit area per unit time is proportional to the increase in area. Then, the fractional increase in area in an infinitesimal time interval ∝ Φ(s)dt must be equal to fraction of material ∝ Ψ(0, s)dt younger than dt, and hence we are led to the boundary condition

Ψ(0, s) = Φ(s). ( 17
)
In principle, for given functions v(s) and Φ(s), this linear first order PDE can be solved by the using the method of characteristics. The line of initial value points {(0, s)|s ∈ [0, ∞)} is a sufficient set of boundary points for this problem, as the tangent vector to the characteristics is given by (1, v(s)), where 0 ≤ v(s) ≤ v, and hence never tangent to the initial value curve. In the following, however, we do not solve this equation directly, but rather an integral transform of it, whose boundary condition is explicitly derived.

The expansion propensity

We now need to address how the expansion propensity depends on the age distribution of the wall material. Here we make the assumption that there is a single Poissonian process with which the contribution to the propensity to expand of a given amount of wall material decays with increasing age. With this definition we set

f (s) = ∞ 0 dτ Ψ(τ, s)e -ατ , ( 18
)
where α is the ageing rate. In the limiting case α = 0 (no ageing) the expansion propensity is normalized to unity, whereas as required it vanishes for α → ∞ (very fast ageing).

A few candidates for such an ageing process have already been discussed in the literature. One proposed mechanism for the regulation of cell wall deposition in tip growth (for a recent review see [START_REF] Cárdenas | New findings in the mechanisms regulating polar growth in root hair cells[END_REF] is through the fact that calcium ions are required to lower the energy barrier for vesicle fusion at the plasma membrane. The influx of these ions into the cell is effected by calcium channels. These channels in turn are deposited into the membrane through exocytosis. If we now assume that to a first approximation the incorporation rate is proportional to the local calcium concentration, itself taken to be proportional to the ion-channel density, and that the active channels have an exponentially distributed lifetime, we have a first example of such a Poissonian ageing process. Another example is the increasing stiffening of the cell wall due to the ongoing de-esterification of pectins under the action of co-deposited pectin methylesterases [START_REF] Fayant | Finite element model of polar growth in pollen tubes[END_REF]. If these enzymes are present in abundance, and the rate of cleavage per methyl group is constant, one expects an exponential decay of the number of uncleaved methyl groups per amount of pectin as a function of time after insertion. As the de-esterified groups can cross-link using calcium ions as linkers causing the pectins to gel, we can in a very rough approximation posit that the expansion propensity is proportional to the mean number of surviving methyl groups. The latter approximation is essentially equivalent to the so-called "soft spot" hypothesis, originally proposed by [START_REF] Koch | The problem of hyphal growth in streptomycetes and fungi[END_REF]. This hypothesis stated that the increasing degree of cross-linking of wall polymers with time since deposition (illustrated in Figure 3) would physically prevent the incorporation of new wall material. For a constant cross-linking rate one would again find that the available number of cross-linking sites per unit amount of material decreases exponentially with age. Although obviously highly simplistic, this hypothesis does provide a concrete metaphor to illustrate our otherwise fairly generic ageing mechanism. Combining the definition (18) with the equation for the age distribution (16), and using (17), we arrive at a one-dimensional initial value problem for the expansion propensity f (s)

v(s)f (s) + (Φ(s) + α)f (s) = Φ(s), (19)
To obtain a boundary condition, we consider the limit s → 0 of the expression (7) for the local expansion rate, which shows that for a smooth tip the flow speed v(0) = 0 vanishes at the apex. Using this in (19) evaluated at s = 0 then yields

f (0) = Φ(0) Φ(0) + α . ( 20
)
In order for the uptake propensity to be a proper autonomous regulator of tip growth, we require that it vanishes as s → ∞. As the expansion rate also vanishes in this limit, this requires that the two terms on the left hand side of ( 19) must balance each other asymptotically, i.e.

v lim s→∞ f (s) f (s) = lim s→∞ Φ(s) f (s) -α ≤ 0. ( 21
)
Further on we will make use of an equivalent integral formulation for the evolution of the expansion propensity. We arrive at this formulation by rearranging ( 19), eliminating Φ(s) using ( 7) and multiplying by ρ(s)

αρ(s)f (s) = (ρ(s)v(s)) (1 -f (s)) -ρ(s)v(s)f (s) = (ρ(s)v(s) (1 -f (s))) (22) Integration then yields α s 0 ds ρ(s )f (s ) = ρ(s)v(s)(1 -f (s)), (23)
and specially its useful limiting case (cf. ( 8))

∞ 0 ds ρ(s)f (s) = Rv α . ( 24
)

Supply factor

How much wall-building material is delivered to a certain location could in principle depend on all the details of the intracellular processes involved in the delivery of vesicles to the plasma membrane. From a formal perspective within our framework, however, the only constraint on the supply factor comes from the requirement that the expansion propensity vanishes for s → ∞ (Eq. ( 21)). Indeed, if, without loss of generality, we choose

Φ(s) = Φ(0) f (0) g (0) f (s) g (s) = (Φ(0) + α) f (s) g (s) g (0) (25)
then, because of the limit (21),

lim s→∞ g (s) g (0) ≤ α Φ(0) + α = 1 -f (0) . ( 26
)
This constraint rules out the potentially simplest choice g (s) = g (0), i.e. a constant delivery rate independent of the position, as this is only compatible with the limit of infinite fast ageing, α → ∞, in which case Eq. ( 19) yields

f (s) = f (0) = 0.
Arguably, a physically realistic description of the supply factor should involve the active transport and/or the diffusion of vesicles in the volume of the cell, with the local rate of exocytosis playing the role of a flux-type boundary conditions. We ourselves have pursued such an approach in the context of fungal growth in earlier work [START_REF] Tindemans | The diffusive vesicle supply center model for tip growth in fungal hyphae[END_REF]. For the examples in Section 4 we again limit ourselves to two specific and highly simplified choices for the supply factor, both of wich have been discussed in the literature. These choices for the supply factor have the advantage of being much simpler from a computational perspective, yet retain many of the essential features of tip-focussed vesicle delivery.

The first was already suggested by [START_REF] Goriely | Growth induced curve dynamics for filamentary micro-organisms[END_REF], and assumes that the delivery rate is solely dependent on the local curvature of the surface

g (s) = H (s) (27)
This choice ignores all details of the delivery process, but achieves focussed delivery by assuming more supply at the more strongly curved areas on the surface. The second choice, appropriate to the case of tip growing fungi, is the assumption that the wall material is delivered by vesicles that reach the cell surface by ballistic transport after their release from a "Spitzenkörper", here represented as a point-like Vesicle Supply Center (VSC), as it was introduced by Gierz and [START_REF] Gierz | A three-dimensional model of fungal morphogenesis based on the vesicle supply center concept[END_REF]. In this case the supply factor is given by g (s) ∝

The flux of additional surface material delivered to an element of cell surface at position s by a point source located at the origin.

(

) 28
and achieves focussing by projecting more vesicles per unit area to regions closer to the VSC, i.e. the apical region, than areas farther away along the tube. Finally, it should be mentioned that there is strong experimental evidence that in several tip-growing cells the maximum rate of vesicle delivery is not at the apex, but rather at an annular region just downstream from the apex [START_REF] Bove | Magnitude and direction of vesicle dynamics in growing pollen tubes using spatiotemporal image correlation spectroscopy and fluorescence recovery after photobleaching[END_REF][START_REF] Zonia | Vesicle trafficking dynamics and visualization of zones of exocytosis and endocytosis in tobacco pollen tubes[END_REF]. This could in principle be modelled by a non-monotonic supply factor, with a maximum at an apex distance s max > 0, but we chose to forego these additional complexities here.

Application to specific examples of growth models

4.1. Curvature-driven delivery In our first model, where take the supply function g(s) to be proportional to the mean surface curvature H(s), and we employ the orthogonal growth mode. One hand, by the definition (25), we then have

Φ(s) Φ(0) = f (s) f (0) H(s) H(0) . (29)
On the other hand, the orthogonal growth condition (10) implies

Φ(s) Φ(0) = ρ (s)H(s) ρ (0)H(0) = ρ (s) H(s) H(0) . (30)
Combining these two identities, then yields a direct relationship between the shape of the cell and the expansion propensity,

f (s) f (0) = ρ (s). (31)
If we insert this expression into the condition (24), we fix the apical value of the expansion propensity

f (0) = 2v αR . (32)
Combining this result with the boundary condition (20) and the orthogonal growth prescription we obtain

RH(0) = κ κ -2
, where κ = αR/v.

Note that this uniquely determines the curvature of the tip at the apex as a function of the ageing rate, the final radius and the growth velocity. Also, this relation tells us that we here we must require κ > 2 in order to have a finite tip curvature. Equation ( 23) can now be rewritten as a first-order nonlinear ordinary differential equation for ρ(s)

ρ(s) = R 1 -ρ (s) 2 1 - 2 κ ρ (s) . (34)
Parametrizing all shape functions in terms of the angle ψ between the surface normal and the z-axis, enables us to solve the problem explicitly, yielding

ρ(ψ) = R sin ψ 1 - 2 κ cos ψ , (35)
z(ψ) = z 0 -R 1 -cos ψ - 2 κ sin 2 ψ + log cos ψ , (36)
s(ψ) = R ψ + 2 κ log 1 + sin ψ cos ψ -2 sin ψ . (37)
The resulting solutions for several values of κ are shown in Figure 4. It is interesting to note that the slow growth/fast ageing limit (κ → ∞) of this solution yields the extremely simple form

ρ ∞ (ψ) = R sin ψ, (38) z ∞ (ψ) = z 0 -R (1 -cos ψ) , (39) s ∞ (ψ) = Rψ. ( 40
)
for ψ ≤ π/2, i.e. a hemispherical cap, which can be continued into an arbitrarily long cylinder of radius R. Intriguingly, a 2D version of such a solution was already found in the early simulations by van [START_REF] Van Batenburg | Rhizobium induces marked root hair curling by redirection of tip growth: a computer simulation[END_REF] of a tip growth model where the orthogonal expansion rate of the surface was assumed to decrease linearly with the axial distance to the tip. Indeed, here we find that in terms of this distance Δz = z 0 -z ∞ (ψ) the uptake propensity is given by

f ∞ (Δz) = f ∞ (0) 1 -Δz R Δz ≤ R 0 Δ z > R , (41)
whilst the curvature H ∞ (Δz) = 1/R is constant for Δz ≤ R, implying the full identity of these models in this limit.

The VSC model

In the VSC model we position an isotropic, constant-rate source of growth material at the origin of our coordinate frame. The appropriate supply factor can then be derived by making the rate of growth material impinging on a patch of cell surface area proportional to the solid angle subtended by this patch as seen from the VSC. This yields

g(s) ∝ r(s) • n(s) |r(s)| 3 = z(s)ρ (s) -z (s)ρ(s) (ρ 2 (s) + z 2 (s)) 3 2 . ( 42
)
For this application we choose the isometric growth mode, which through Eq. ( 12) also expresses the local expansion rate in terms of the geometry.

Using the normalization Eq. ( 25) also allows us to express the expansion propensity in terms of the surface geometry

f (s) = Φ(s) (Φ(0) + α) g(0) g(s) = 1 z 2 (0) 2 (2 + κ) ρ (s) (ρ 2 (s) + z 2 (s)) 3 2 (z(s)ρ (s) -z (s)ρ(s)) . ( 43
)
Inserting these expressions into the steady-state equation for the expansion propensity then yields a single closed form second order differential equation involving ρ(s), z(s) and their derivatives. Using the parametrization Eq. ( 3), the dependency between ρ(s) and z(s) can be resolved, finally yielding a set of two coupled first order equations, which we show in full in (D.6) and (D.7).

Note that these equations contain the as yet undetermined quantity z(0), i.e. the distance between the VSC and the apex of the cell. This quantity can be determined self-consistently from the solutions to the equations, when the ultimate cell radius R is considered as fixed. In practice this is done using a standard "shooting approach", which is described in Appendix D. In Figure 5 we show the computed tip shapes for a number of different ageing rates. These results show that, while the shape itself only becomes slightly more "blunt" at higher ageing rates, the tip-VSC distance does increase markedly on the ageing rate. From the inner most to the outer most shape κ ranges through 0 (orange), 1 (green), 5 (blue), 10 (red). Faster ageing tips are blunter, and have a larger apex-VSC distance.

Finally, in Figure 6 we plot the expansion propensity f (s) for different values of the ageing rate, showing that as ageing increases the region where growth is possible becomes limited to the area close to the apex.

Discussion and outlook

We have presented what are arguably the first, albeit simplified, models of tip growth that self-consistently couple material deposition, evolving wall properties and growth. This additional mechanism significantly enlarges the dynamical phase space of growth models. To date most models essentially only involve a single timescale related to the growth rate , t growth = R/v, 0.2 0.4 0.6 0.8 1.0 0 1 2 3 4

Figure 6: The expansion propensity f (s) plotted as a function of the distance from the apex measured in units of the tube radius R. From the outer most to the inner most shape, κ ranges through 0 (orange), 1 (green), 5 (blue), 10 (red). With increasing rate of ageing the region where growth is possible shrinks to an area close to the apex.

which is readily observable at the global scale. In the ageing approach, a new timescale, t ageing , appears, which is associated with the intrinsic dynamics of the newly deposited wall material, and hence more difficult to observe. It is the interplay between these two timescales that allows the new class of models to account for a much wider variety of tip-shapes than hitherto possible, as illustrated e.g. in Figure 2.

A key assumption in our model is the generic notion of a feedback of the local material state of the wall on the propensity to expand in surface area, given that enough wall building material is available. We have obviously chosen a very generic functional form for this feedback, allowing only a phenomenological interpretation at this stage. Our underlying dynamics of the age distribution of the cell wall material, could, however, serve as the basis for more detailed microscopic ageing mechanisms. From an experimental point of view, it is obviously very challenging to probe the dynamical processes going on in the nascent cell wall. Nevertheless, we may hope that a combination of micromechanical (see e.g. [START_REF] Zerzour | Polar growth in pollen tubes is associated with spatially confined dynamic changes in cell mechanical properties[END_REF] and biochemical (see e.g. [START_REF] Fayant | Finite element model of polar growth in pollen tubes[END_REF] measurements that probe the local properties of the wall with quantitative measurement on the local rate of exocytosis (see e.g. [START_REF] Zonia | Vesicle trafficking dynamics and visualization of zones of exocytosis and endocytosis in tobacco pollen tubes[END_REF]) may serve to validate some of the ideas presented here.

What is still clearly lacking from our model is the true physics of growth and expansion, which requires the application of the principles of continuum mechanics (for a nice recent review see [START_REF] Goriely | Mathematical modeling of hyphal tip growth[END_REF], coupled to perhaps more realistic microscopic models of the developing cell wall. Goriely and Tabor (2003a,b) and later [START_REF] Dumais | An anisotropic-viscoplastic model of plant cell morphogenesis by tip growth[END_REF] have already formulated models in which the mechanics is explicitly taken into account. However, these models essentially impose a stationary gradient of mechanical properties along the growing tip, rather than having this gradient emerge selfconsistently on the basis of the combined process of material incorporation, ageing and extension. By combining the approach of our present work which with the explicit use of elasticity theory, by having the relevant mechanical constants depend explicitly on the "age" of the wall material, one can hope to achieve a synthesis which is reasonable both from a biological as well as physical point of view. We are currently working to formulate such a model. Note that both the equation (D.7) and the boundary condition for z(0) actually contain the as yet undetermined amplitude F 0 . The latter, however, can be replaced with the known condition z (0) = 0. The resulting set equations is amenable to a shooting approach (see e.g. Press et al., 2007, Chapter 18), which solves the two point boundary value problem by turning into into an initial value problem, where a subset of initial conditions at one point is varied until the boundary conditions at the other point are met. In our case we vary z(0), through changing F 0 , and ψ (0). For each choice we solve the initial value problem using a standard PDE solver (Mathematica's NDSolve), and then use a tailor-made root-finding algorithm to adjust the free parameters until the boundary conditions at infinity are met.

Figure 1 :

 1 Figure 1: Coordinate system for describing stationary tip growth.

Ȧ

Figure 2 :

 2 Figure2: Illustration of the four dynamic effects of cell wall growth: ageing, here conceived as increasing cross-linking between the wall polymers, flow, dilution and rejuvenation .

Figure 3 :

 3 Figure 3: Illustration of the concept of cell wall ageing. The highlighted polymer has five locations where cross-linkers can bind, of which two are occupied.

Figure 4 :

 4 Figure 4: Calculated shapes for the simple geometrical model. Values for the dimensionless ageing parameter κ are 2.02 (lower left), 4 (middle) and 202 (upper right).

Figure 5 :

 5 Figure5: The shape of the tip in the VSC-model for different values of the ageing parameter κ with distances measured in units of the tube diameter R, and using the location of the VSC (filled disk) as origin. From the inner most to the outer most shape κ ranges through 0 (orange), 1 (green), 5 (blue), 10 (red). Faster ageing tips are blunter, and have a larger apex-VSC distance.

  In our parametrization the rate of strain tensor takes the explicit involved is readily calculated from the Jacobi formula for the derivative of the determinant of an invertible matrixd dx det A(x) = det A(x) Tr A(x) z(s) and ρ(s) are related through z (s) = -1ρ (s) 2 , so that z (s) = ρ (s)ρ (s) 1ρ (s) 2 . (D.4)By introducing the angle ψ (cf. Eq. (3)) as a dependent variable, we can switch to ρ as our independent variable. We readily find dψ Eq. (D.3) and simplifying yieldsF 0 ρ 2 + z 2 (ρ) {[ρ sin ψ(ρ) + z(ρ) cos ψ(ρ)] × ρ 2 (5 cos ψ(ρ) + κ) -3ρz(ρ) sin ψ(ρ) + z 2 (ρ)(2 cos ψ(ρ) + κ) -ρ 2 [ρ 2 + z 2 (ρ)]ψ (ρ) -2[ρ sin ψ(ρ) + z(ρ) cos ψ(ρ)] 2 = 0. (D.7)This last equation needs to be solved in conjunction with Eq. (D.6

:

  H PRGHO WKH UROH RI FHOO ZDOO DJHLQJ LQ WLS JURZLQJ FHOOV :H GHULYH DQ HTXDWLRQ IRU WKH DJH GLVWULEXWLRQ RI WKH ZDOO EXLOGLQJ PDWHULDO :H GHILQH D JHQHULF IHHGEDFN PHFKDQLVP ZKLFK UHJXODWHV FHOO H[SDQVLRQ EDVHG RQ WKLV DJH GLVWULEXWLRQ :H VKRZ WKDW RXU DSSURDFK OHDGV WR ULFK FODVV RI WUDFWDEOH PRGHOV RI WLS JURZWK

Acknowledgements. This work is part of the research program of the "Stichting voor Fundamenteel Onderzoek der Materie (FOM)", which is financially supported by the "Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)". The work of NdK is made possible by grant no. 05DOP04 from the NWO-FOM programme "Dynamics of Patterns".

Appendix A. The geometry of axisymmetric surfaces

In this Appendix, and the two following ones, we give a very concise overview of the differential geometry of surfaces relevant to the problem of tip-growth. Readers interested in more background are urged to consult a reference on the geometry surfaces such as [START_REF] Carmo | Differential Geometry of Curves and Surfaces[END_REF] and a primer on tensors such as [START_REF] Joshi | Matrices and Tensors in Physics[END_REF].

Consider a parameterization of a tip-shaped axisymmetric surface using the variables (σ, ϕ), where σ is an arbitrary parameter along the meridional direction and ϕ is the usual azimuthal (cylindrical) angle. Because of the axial symmetry, the shape of the surface is fully described by the functions ρ(σ) and z(σ). The arc length from the apex to σ is then defined by

where σ = σ 0 denotes the position of the apex. It is convenient to choose the arc length s itself as the meridional parameter, as already done in the main text. From the definition of the arc length it follows that

This relationship implies that the surface shape can essentially be described solely by the function ρ(s). However, we also use z(s) for notational simplicity. Using Eq. (A.2), we can solve for z(s)

The negative root is chosen for the derivative of z(s) because we have defined the positive z-axis in the direction of growth, so that the surface itself evolves towards the negative z-axis and, hence, z(0) is the maximum of z(s). We note that the function z(s), and more specifically its starting value z(0), is of significance only if there is a preferred location of the origin, such as a vesicle supply center. We use Eq. (1) to define the cell surface, parameterized by s and ϕ. Locally, the geometry of this surface is characterized by the set of basis vectors which span the plane tangential to the surface

Note that in this parametrization r s • r s = 1. The outward normal unit vector n(s, ϕ) on the surface, already presented in Eq. ( 2) is determined from the

For the further development, we need a few more geometrical quantities related to the surface. The first is the metric tensor

where the Greek indices run over s and ϕ respectively. Note that the offdiagonal zeroes mean that {r s , r ϕ } form an orthogonal basis. This metric tensor has an inverse denoted by

(A.9)

Given an arbitrary (covariant) tensor T μν we use g μν to "raise" an index and obtain the mixed form that allows us to calculate invariants, such as the trace which is defined through

where we employ the Einstein summation convention. Next, we calculate the curvature tensor

The curvature tensor can be used to calculate the two invariant scalar curvatures, the extrinsic (mean) curvature and the intrinsic (Gaussian) curvature of the surface. The mean curvature is given by

and the Gaussian curvature is given by

where η μν is the rank-two Levi-Cevita tensor. Finally we note that the element of surface area is given by

Appendix B. Surface deformations and growth

In order to describe surface deformations and growth we first introduce the notion of a material point. At an arbitrary initial t = 0 such a point is, up to a rotation around the z-axis, uniquely identified by its distance from the tip s 0 . In the co-moving frame the distance to the tip of this material will increase, which we describe by the function S (t) with S (0) = s 0 . Because of the assumed axisymmetry the motion of this point will be purely meridional, so that the azimuthal angle ϕ is constant. The flow velocity of the material point in the co-moving frame is therefore given by

In the steady state these quantities no longer depend explicitly on time and we can write

which defines the flow speed used in the main text. To obtain the track, X (t|r(s 0 , ϕ)) with X(0|r(s 0 , ϕ)) = r(s 0 , ϕ), of the material point in the spacefixed laboratory frame, it suffices to realize that in the steady state the tip as a whole by definition simply shifts with a constant velocity in the direction of the symmetry axis, so that X (t|r (s 0 , ϕ)) = r (S (t) , ϕ) + vtẑ,

where ẑ is the unit vector in the positive z-direction. The time derivative of this quantity yields the velocity of the material points at a certain position

The components of this vector in a local frame are given by

The surface deformation induces a change in the metric of the surface, which defines the rate of strain tensor εμν = 1 2

Appendix C. The growth modes

In the orthogonal growth mode the meridional velocity component of growth Eq. (B.5) vanishes, yielding

and the velocity of material points is given by

We now note that in this case

where we have used the symmetry of k μν . We therefore have

In the isometric growth rate, the two components of the mixed index rate of strain tensor εμ ν (cf. Eq. (B.9)) are equal, so that

This implies that v(s) and ρ(s) are proportional, where the proportionality constant is readily found by considering v(∞) = v and ρ(∞) = R. This yields the flow velocity

and the local expansion rate


Emmanuel Ramasso
email: emmanuel.ramasso@femto-st.fr

Noureddine Zerhouni
email: noureddine.zerhouni@ens2m.fr

Thierry Denoeux
email: thierry.denoeux@hds.utc.fr

Partially-Hidden Markov Models

Introduction

Hidden Markov Models (HMM) are powerful tools for sequential data modelling and analysis. Many applications for several decades have found solutions based on HMM such as discovering word sequences based on speech audio recordings [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF], gene finding based on a DNA sequence [START_REF] Murphy | Dynamic Bayesian networks: Representation, inference and learning[END_REF], and performing prognostics and health detection of ball bearings degradation based on noisy sensors [START_REF] Dong | A segmental hidden semi-markov model (hsmm)-based diagnostics and prognostics framework and methodology[END_REF][START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF]. In the sequel, we consider sequential data taking the form of a time-series of length T where each element is a multidimensional feature vector x t ∈ ℜ F ,t = 1 . . . T also called vector of observations [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. The modelling part assumes that the system (a speaker, a DNA sequence or a ball bearing) generating the time-series is a Markov process with unobserved (hidden, latent) discrete states. In HMMs, the states are not visible but when the system is entering in one of the states, the features follow a particular probability distribution. The sequence of observations thus provides information about the sequence of states. One of the most powerful characteristics of HMMs, accounting for its wide range of applications, is the possibility to estimate the parameters efficiently and automatically. Given a training dataset composed of the observed data X = {x 1 , . . . , x t , . . . , x T } (where x t can be continuous or discrete), and denoting by K the number of hidden states such that the state variable y t at time t can take a value in

Ω Y Y Y = {1, . . . , j, . . . , K} , (1)
the following parameters have to be estimated:

• Φ Φ Φ = {φ φ φ 1 , .
. . ,φ φ φ j , . . . ,φ φ φ K } is the set of parameters characterising the probability distribution of observations given each state:

b j (x t ) = P(x t |y t = j;φ φ φ j ), j = 1 . . . K (2) • A A A = [a i j ] with a i j = P(y t = j|y t-1 = i), i = 1 . . . K, j = 1 . . . K (3)
that is the probability of the system to be in state j at time-instant t, given the system was in state i at t -1, with ∑ j a i j = 1. • Π Π Π = {π 1 , . . . , π j , . . . , π K }, where

π j = P(y 1 = j) (4)
is the probability of state j at t = 1, such that ∑ i π i = 1.

In the sequel, all these parameters are aggregated in a vector θ :

θ = {A,Π Π Π ,Φ Φ Φ} . (5)
These parameters can be estimated using an iterative procedure called the Baum-Welch algorithm [START_REF] Baum | A maximization technique occurring in statistical analysis of probabilistic functions of markov chains[END_REF][START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] and relying on the Expectation-Maximisation process.

There are applications where some observations x t in the training data X are associated to a label that actually represents the state at time t. Instead of considering the labelling process as a binary one, where states can be known or unknown, we address the problem of partially-supervised HMM training, assuming the labels to be represented by belief functions. These functions can represent uncertainty and imprecision about the states and can be in time-series modelling and analysis.

The contribution of this paper holds in the development of a model called Partially-Hidden Markov Model (PHMM) that manages partial labelling of the training dataset in HMMs. Compared to [START_REF] Côme | Learning from partially supervised data using mixture models and belief functions[END_REF], we take into account the temporal dependency into account, helping in time-series modelling. The proposed approach is based on the Evidential Expectation-Maximisation (E2M) algorithm [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF].

Partially-Hidden Markov Models (PHMM)

Given the observation sequence X = {x 1 , x 2 , . . . , x T }, there are three main problems of interest in connection with HMMs [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]: Problem 1: Given a model θ = {Π Π Π ,A A A,Φ Φ Φ}, how to compute its likelihood L(θ ; X)? Problem 2: Given a model θ , how to choose the state sequence Y * = {y * 1 , y * 2 , . . . , y * T } that best explains observations? Problem 3: How to estimate parameters θ = {Π Π Π ,A A A,Φ Φ Φ} of a model? These problems have been solved in different ways for some decades in HMM [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF]. In the sequel, we present the solutions for the case where partial information on states is available in the form of a set of belief functions m defined on the set of states Ω Y Y Y . States are then "partially hidden" and the case of completely hidden states is recovered when all the masses are vacuous.

The main idea behind the solutions of partially-supervised training in statistical models is to combine the probability distributions on hidden variables with the belief masses m. This combination can be computed from the contour function pl associated to m.

The next paragraph describes the main features of the E2M algorithm in order to introduce the conditioning process that plays a central role in solutions for problems 1, 2 and 3. The E2M algorithm will be used in the last paragraph dedicated to parameter estimation in PHMMs.

Generalized likelihood function and E2M algorithm

The Evidential EM (E2M) [START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF] is an interative algorithm dedicated to maximum likelihood estimation in statistical models based on uncertain observations encoded by belief functions. As for the usual EM algorithm, the E2M algorithm does not maximise directly the observed-data likelihood function denoted here L(θ ; X, m) but it focuses instead on a lower bound called the auxiliary function [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF], and usually denoted by Q and defined as:

Q(θ , θ (q) ) = E θ (q) [log L(X, Y; θ )|X, pl] , (6)
where pl denotes the contour function associated to m and θ (q) is the fit of parameter θ at iteration q, and Q represents the conditional expectation of the completedata log-likelihood. In the E-step of the E2M algorithm, the conditional expectation in the auxiliary function Q is taken with respect to γ

′ def = P(•|X, pl; θ (q) ) = P(•|X; θ (q) )
⊕ pl, that is the combination of the expectation, denoted γ t , with the plausibilities using Demspter's rule [START_REF] Dempster | Upper and lower probabilities induced by multiple valued mappings[END_REF][START_REF] Denoeux | Maximum likelihood estimation from uncertain data in the belief function framework[END_REF]. The new expectation is then defined for each state j at time t by γ ′ t ( j|pl; θ (q) ) = P(y t = j|X, pl; θ (q) ):

γ ′ t ( j|pl; θ (q) ) = γ t ( j; θ (q) ) • pl t ( j)
L(θ (q) ; X, pl) [START_REF] Forney | The viterbi algorithm[END_REF] and the auxiliary function becomes:

Q(θ , θ (q) ) = ∑ Y P(Y|X; θ (q) ) • pl(Y) • log L(X, Y; θ ) L(θ (q) ; X, pl) . ( 8
)
The M-step is similar to to that of the usual EM algorithm and consists in maximising Q with respect to θ . The maximisation is ensured to increase the likelihood of observed data since E2M inherits the monotonicity of EM as for any sequence L(θ (q) ; X, pl), q = 1, 2 . . . , we have L(θ (q+1) ; X, pl) ≥ L(θ (q) ; X, pl).

Solution to problem 1 in PHMM

Using a similar process as in usual HMM (see [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF] for details on HMM), the marginal posterior distribution on latent variables for the set of parameters θ (q) at iteration q of E2M can be rewritten as:

γ ′ t = P(y t |X; θ (q) ) ⊕ pl t = α ′ t • β t (9)
with α ′ t def = P(X 1:t , y t |pl; θ (q) ) and β

′ t def = P(X t+1:T |y t ; θ (q)
). The definition of β remains the same as in the standard algorithm with β t (i; θ (q) ) = ∑ j β t+1 ( j; θ (q) ) • b j (x t+1 )•a ji , t = 2 . . . T starting from β T (i; θ (q) ) = 1, ∀i. The probability of jointly observing a sequence X 1:t up to t and state j at time t given the parameters and the uncertain data is given by the modified forward variable α ′ t such that α ′ t ( j; θ (q) ) = P(X 1:t , y t = j|pl; θ (q) ) with:

α ′ t ( j; θ (q) ) = α t ( j; θ (q) ) • pl t ( j)
L(θ (q) ; X, pl) [START_REF] Ramasso | Contribution of belief functions to hidden markov models[END_REF] and therefore

γ ′ t ( j; θ (q) ) = α t ( j; θ (q) ) • pl t ( j) • β t ( j; θ (q) ) L(θ (q) ; X, pl) . (11)
Variables α and β are the same as in HMM [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. Summing Eq. 11 over latent variables gives the observed data likelihood. Therefore, to assess the likelihood function L(θ (q) ; X, pl) at the current iteration of the E2M algorithm, we simply need to choose a time index t. A good candidate is the index T since in this case we do not need to evaluate β T (that equals to 1) reducing the computation load:

L(θ (q) ; X, pl) = K ∑ j=1 α T ( j; θ (q) ) • pl T ( j) (12)
Practically, we can use the normalization process proposed in [START_REF] Rabiner | A tutorial on hidden Markov models and selected applications in speech recognition[END_REF] in order to cope with the limited machine precision range.

Solution to problem 2 in PHMM

The Viterbi algorithm [START_REF] Forney | The viterbi algorithm[END_REF] was defined in order to retrieve the best sequence of hidden states within the noisy observations. The best sequence is found in K 2 × T operations (instead of K T for a greedy search) and is ensured to be the one with the highest likelihood. Given the observed data X, the Viterbi algorithm finds the maximum a posteriori (MAP) sequence Y * = {y * 1 , . . . , y * t , . . . , y * T }, y * t ∈ Ω Y . In PHMM, the MAP criterion is modified by taking soft labels into account, i.e., P(Y * |X, pl; θ (q) ) or, equivalently, log P(X, Y * |pl; θ (q) ). In HMMs, the Viterbi algorithm is called the max-sum product algorithm and it is equivalent to a forward propagation with conditioning at each time-step by the potential predecessors of each state. In PHMMs, a similar reasoning can be applied where conditioning (by singletons states) naturally leads to the use of plausibilities. The MAP criterion can be written as:

δ ′ t ( j; θ (q) ) = max i δ ′ t-1 (i; θ (q) ) • a i j • b j (x t ) • pl t ( j), t = 2 . . . T (13) starting from δ ′ 1 ( j; θ (q) ) = π j • pl t ( j) • b j (x 1
). Keeping track of the argument maximising this expression as

ψ ′ t ( j) = argmax i δ ′ t-1 (i; θ (q) )
• a i j , the backtracking of the best state sequence ending in y * t = j at time t is given by y

* t-1 = ψ ′ t (y * t ).

Solution to problem 3 in PHMM

In the E2M algorithm, the auxiliary function is given by Eq. 8. In order to define the maximisation step, the Q-function has to be computed. For that purpose, we introduce the multinomial representation of variables such that y t j = 1 if state j at time t is true, else y t j = 0. Then, we can write:

P(Y, X; θ ) = K ∏ j=1 π y 1 j j • T ∏ t=2 K ∏ i=1 K ∏ j=1 a y t-1,i ,y t j i j • T ∏ t=1 K ∏ j=1 b j (x t ) y t j (14)
Taking the logarithm of the above expression leads to the complete-data loglikelihood. In this paper, partial knowledge on y t j is assumed to be represented by a belief function (and in particular by its contour function pl t ( j), ∀t = 1 . . . T, j = 1 . . . K). The auxiliary function Q thus becomes:

Q(θ , θ (q) ) = E θ (q) [log P(X, Y; θ )|X, pl] (15a) = Q π (θ , θ (q) ) + Q A (θ , θ (q) ) + Q Φ Φ Φ (θ , θ (q) ) , (15b)
with Q π (θ , θ (q) ) = ∑ K j=1 E θ (q) y 1 j |X, pl • log π j given by:

Q π (θ , θ (q) ) = K ∑ j=1 γ ′ 1 ( j; θ (q) ) • log π j , (16)
and

Q A (θ , θ (q) ) = ∑ T t=2 ∑ K i=1 ∑ K j=1 E θ (q) [y t-1,i y t j |X, pl]
• log a i j with:

Q A (θ , θ (q) ) = T ∑ t=2 K ∑ i=1 K ∑ j=1 ξ ′ t-1,t (i, j; θ (q) ) log a i j , (17)
and

Q Φ Φ Φ (θ , θ (q) ) = ∑ T t=1 ∑ K j=1 E θ (q) [y t j |X, pl] • log b j (x t )
given by:

Q Φ Φ Φ (θ , θ (q) ) = T ∑ t=1 K ∑ j=1 γ ′ t ( j; θ (q) ) • log b j (x t ) . (18)
In the above expressions we have:

γ ′ t ( j; θ (q) ) = γ t ( j; θ (q) ) • pl t ( j) ∑ K l=1 γ t (l; θ (q) ) • pl t (l) , (19)
which is the marginal posterior distribution of a latent variable y j at t given pl, and

ξ ′ t-1,t (i, j; θ (q) ) = ξ t-1,t (i, j; θ (q) ) • pl t-1 (i) • pl t ( j) ∑ K l=1 ξ t-1,t (i, l; θ (q) ) • pl t-1 (i) • pl t (l) (20)
is the joint probability of two consecutive latent variables y t-1,i and y t j given pl. The optimal parameters at each iteration of E2M are given by using a similar reasoning as in the standard algorithm, but the posterior probability over latent variables now depends on the plausibilities:

π (q+1) j = γ 1 ( j; θ (q) ) • pl 1 ( j) K ∑ l=1 γ 1 (l; θ (q) ) • pl 1 (l) (21a) a (q+1) i j = T ∑ t=2 ξ t-1,t (i, j; θ (q) ) • pl t-1 (i) • pl t ( j) T ∑ t=2 K ∑ l=1 ξ t-1,t (i, l; θ (q) ) • pl t-1 (i) • pl t (l) (21b)
The maximisation of Q Φ Φ Φ (θ , θ (q) ) depends on the form of the distribution of observations given the latent variable j.

Partial results, conclusion and further work

Partial results: To illustrate this approach, we considered that observations can be modelled by mixtures of Gaussians. We proceeded as in standard HMM to derive the M-step in PHMM and to estimate the parameters of the distributions. Equations are however not reported in this paper.

For illustration purpose, we used the dataset of the PHM'08 data challenge [START_REF] Saxena | Damage propagation modeling for aircraft engine run-to-failure simulation[END_REF] concerning the health state of a turbofan engine. It was manually segmented into four states (to evaluate the results) such that each time-series is accompanied by a set of labels reflecting the current state of the fan, that is normal, transition, degrading or faulty mode. Each label corresponds to a mass function focused on a singleton, except in the transitions where doubt between two labels is defined. The segmentation and the associated BBA are available at http://www.femto-st.fr/ ˜emmanuel.ramasso/PEPS_INSIS_2011_PHM_by_belief_functions. html. The BBA were then transformed into plausibilities. For these tests, we corrupted them by additive noise: pl t ( j) ← pl t ( j)+σ k •ε t ( j), where σ k ∈ {0, 0.1, . . . , 1} and ε t ( j) ∼ U [0,1] was drawn from a uniform distribution. For each noise level, we considered the influence of the number of unlabelled data ν k ∈ {0%, 10%, . . . , 100%}. The partitioning of time-series in the testing dataset estimated by HMM and PHMM using the Viterbi algorithm as defined in HMM (since we do not know the labels for the testing) were compared using the Folkes and Mallows index (F ∈ [0, 1]) [START_REF] Saporta | Comparing two partitions: Some proposals and experiments[END_REF] by computed the relative performance improvement G = F pshmm /F hmm -1 with G ∈ [-1, 1] such that if G > 0 (resp. G < 0), the proposed PHMM provided a better (resp. worse) segmentation of the time-series into states.

The evolution of G is given in Figure 1 that shows an improvement by several percents when using the proposed PHMM (up to 12%). When all data were unlabelled and with no noise (bottom right hand-side corner), both models provided exactly the same results, as expected. When the noise increased, the performance decreased but was still higher than that of the standard HMM. The most difficult cases were encountered when the noise was high (top of figure), where PHMM improvements were between [2%, 5%].

Conclusion and further work:

Taking partial knowledge into account is of crucial importance in many statistical models. Encoding prior information by belief functions leads to simple modifications of the initial estimation formula while remaining theoretically sound. The statistical model considered in this paper was the Hidden Markov Models. Further work remains to be done in order to compute in developing reestimation formula for various distributions of observations given latent states.

Acknowledgements: This work was partially supported by a PEPS-INSIS-2011 grant from the French National Center for Scientific Research (CNRS) under the administrative authority of the French Ministry of Research.

Fig. 1

 1 Fig. 1 Performance (G-index): median value over 10 runs with different initialisation. Positive value reflects an improvement provided by PHMM. Here almost all values are positive except darkest areas.


Mireille Bousquet-Mélou

Guillaume Chapuy

Louis-Franc ¸ois Préville-Ratelle

The representation of the symmetric group on m-Tamari intervals

Keywords:

An m-ballot path of size n is a path on the square grid consisting of north and east unit steps, starting at (0, 0), ending at (mn, n), and never going below the line {x = my}. The set of these paths can be equipped with a lattice structure, called the m-Tamari lattice and denoted by T (m) n , which generalizes the usual Tamari lattice Tn obtained when m = 1. This lattice was introduced by F. Bergeron in connection with the study of diagonally coinvariant spaces in three sets of n variables. The representation of Sn on these spaces is conjectured to be closely related to the natural representation of Sn on (labelled) intervals of the m-Tamari lattice studied in this paper.

An interval

is labelled if the north steps of Q are labelled from 1 to n in such a way the labels increase along any sequence of consecutive north steps. The symmetric group Sn acts on labelled intervals of T (m) n

by permutation of the labels. We prove an explicit formula, conjectured by F. Bergeron and the third author, for the character of the associated representation of Sn. In particular, the dimension of the representation, that is, the number of labelled m-Tamari intervals of size n, is found to be (m + 1) n (mn + 1) n-2 . These results are new, even when m = 1.

The form of these numbers suggests a connection with parking functions, but our proof is not bijective. The starting point is a recursive description of m-Tamari intervals. It yields an equation for an associated generating function, which is a refined version of the Frobenius series of the representation. The form of this equation is highly nonstandard: it involves two additional variables x and y, a derivative with respect to y and iterated divided differences with respect to x. The hardest part of the proof consists in solving it, and we develop original techniques to do so.

Introduction and main result

An m-ballot path of size n is a path on the square grid consisting of north and east unit steps, starting at (0, 0), ending at (mn, n), and never going below the line {x = my}. It is well-known that there are 1 mn + 1 (m + 1)n n subm. to DMTCS c by the authors Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France such paths [START_REF] Dvoretzky | A problem of arrangements[END_REF], and that they are in bijection with (m + 1)-ary trees with n inner nodes.

Franc ¸ois Bergeron recently defined on the set T (m) n of m-ballot paths of size n an order relation. It is convenient to describe it via the associated covering relation, exemplified in Figure 1.

Definition 1 Let P and Q be two m-ballot paths of size n. Then Q covers P if there exists in P an east step a, followed by a north step b, such that Q is obtained from P by swapping a and S, where S is the shortest factor of P that begins with b and is a (translated) m-ballot path. It was shown in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF] that this order endows T (m) n with a lattice structure, which is called the m-Tamari lattice of size n. When m = 1, it coincides with the classical Tamari lattice [START_REF] Bernardi | Intervals in Catalan lattices and realizers of triangulations[END_REF][START_REF] Friedman | Problèmes d'associativité: Une structure de treillis finis induite par une loi demi-associative[END_REF][START_REF] Huang | Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law[END_REF][START_REF] Knuth | The art of computer programming[END_REF].

The interest in these lattices is motivated by their -still conjectural -connections with trivariate diagonal coinvariant spaces [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF][START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF]. Some of them are detailed at the end of this introduction. In particular, it is believed that the representation of the symmetric group on these spaces is closely related to the representation of the symmetric group on labelled m-Tamari intervals. The aim of this paper is to characterize the latter representation, by describing explicitly its character.

So let us define this representation and state our main result. Let us call ascent of a ballot path a maximal sequence of consecutive north steps. An m-ballot path of size n is labelled if the north steps are labelled from 1 to n, in such a way the labels increase along ascents (see the upper paths in Figure 2). These paths are in bijection with (1, m, . . . , m)-parking functions of size n, in the sense of [START_REF] Stanley | A polytope related to empirical distributions, plane trees, parking functions, and the associahedron[END_REF][START_REF] Yan | Generalized parking functions, tree inversions, and multicolored graphs[END_REF]: the function f associated with a path Q satisfies f (i) = k if the north step of Q labelled i lies at abscissa k -1. Using the cycle lemma [START_REF] Riordan | Ballots and trees[END_REF], it is easy to prove that the number of labelled m-ballot paths of size n is (mn + 1) n-1 .

(1)

Now an m-Tamari interval [P, Q] is labelled if the upper path Q is labelled. The symmetric group S n acts on labelled intervals of T (m) n by permuting labels, and then reordering them in each ascent (Figure 2). This is the representation that we study here. We call it the m-Tamari representation of S n . Our main result is an explicit expression for the character χ m of this representation, which was conjectured by Bergeron and the third author [BPRar].

Theorem 2 Let λ = (λ 1 , . . . , λ ℓ ) be a partition of n and σ a permutation of S n having cycle type λ. Then for the m-Tamari representation of S n , Since S n acts by permuting labelled intervals, this is also the number of labelled m-Tamari intervals left unchanged under the action of σ.

χ m (σ) = (mn + 1) ℓ-2 1≤i≤ℓ (m + 1)λ i mλ i . (2)
In particular, the dimension of the representation, that is, the number of labelled m-Tamari intervals of size n, is χ m (id) = (m + 1) n (mn + 1) n-2 .

(3)

We were unable to find a bijective proof of these amazingly simple formulas. Instead, our proof uses generating functions and goes as follows. We introduce a generating function F (m) (t, p; x, y) counting labelled intervals according to multiple parameters, where p is an infinite sequence of variables p 1 , p 2 , . . ., which can be thought of as power sums. We call this series the refined Frobenius series of the m-Tamari representation (Section 2). Then, we describe a recursive construction of intervals and translate it into a functional equation defining F (m) (t, p; x, y) (Proposition 7, Section 3). The form of this equation is new to us, and its solution is the most difficult and original part of the paper. Due to lack of space, we only give the proof for m = 1, after having explained the general principles of our approach, which are valid for all m (Section 4). The complete version of this paper has appeared on the ArXiv [START_REF] Bousquet-Mélou | The representation of the symmetric group on m-Tamari intervals[END_REF].

In the remainder of this section, we recall some of the conjectured connections between Tamari intervals and trivariate diagonal coinvariant spaces. They seem to parallel the (now proved) connections between ballot paths and bivariate diagonal coinvariant spaces, which have attracted considerable attention in the past 20 years [START_REF] Garsia | A proof of the q, t-Catalan positivity conjecture[END_REF][START_REF] Haglund | Conjectured statistics for the q, t-Catalan numbers[END_REF][START_REF] Haglund | The q,t-Catalan numbers and the space of diagonal harmonics[END_REF][START_REF] Haglund | A conjectured combinatorial formula for the Hilbert series for diagonal harmonics[END_REF][START_REF] Haiman | Conjectures on the quotient ring by diagonal invariants[END_REF][START_REF] Haiman | Vanishing theorems and character formulas for the Hilbert scheme of points in the plane[END_REF][START_REF] Loehr | Multivariate analogues of Catalan numbers, parking functions, and their extensions[END_REF] and are still a very active area of research today, as shown by recent papers by Armstrong, Garsia, Haglund, Hicks, Loehr, Rhoades, Stout, Xin, Zabrocki... which we do not cite in details here for the sake of concision. Let X = (x i,j )1≤i≤k

1≤j≤n

. The diagonal coinvariant space DR k,n is defined as the quotient of the ring C[X] of polynomials in the coefficients of X by the ideal J generated by constant-term free polynomials that are invariant under permuting the columns of X. For example when k = 2, denoting x 1,j = x j and x 2,j = y j , the ideal J is generated by constant-term free polynomials f such that for all σ ∈ S n ,

f (X) = σ(f (X)), where σ(f (X)) = f (x σ(1) , . . . , x σ(n) , y σ(1) , . . . , y σ(n) ).
An m-extension of these spaces is of great importance here [START_REF] Garsia | A remarkable q, t-Catalan sequence and q-Lagrange inversion[END_REF]. Let A be the ideal of C[X] generated by alternants under the diagonal action described above. There is a natural action of S n on the quotient space A m-1 J A m-1 . Let us twist this action by the (m -1) st power of the sign representation ε: this gives rise to spaces

DR m k,n := ε m-1 ⊗ A m-1 J A m-1 , so that DR 1 k,n = DR k,n . It is now a famous theorem of Haiman [Hai02, HHL + 05] that, as representa- tions of S n , DR m 2,n ∼ = ε ⊗ P ark m (n)
where P ark m (n) is the m-parking representation of S n . This representation is defined as the action on labelled m-ballot paths (i) that permutes the labels and then reorders them so that they increase in each ascent. The character of this representation, evaluated at a permutation of cycle type λ = (λ 1 , . . . , λ ℓ ) is (mn + 1) ℓ-1 . This formula, which generalizes (1), is easily proved using the cycle lemma.

In the case of three sets of variables, it is conjectured by Bergeron and the third author [BPRar] that, as

representations of S n , DR m 3,n ∼ = ε ⊗ T am m (n),
where T am m (n) is the representation of the symmetric group on labelled m-Tamari intervals that we study in this paper. The fact that the dimension of this space seems to be given by ( 3) is an earlier conjecture due to F. Bergeron (also observed for small values of n by Haiman [START_REF] Haiman | Conjectures on the quotient ring by diagonal invariants[END_REF] in the case m = 1).

2 The refined Frobenius series

Definitions and notation

Let L be a commutative ring and t an indeterminate. We denote by

L[t] (resp. L[[t]]
) the ring of polynomials (resp. formal power series) in t with coefficients in L. If L is a field, then L(t) denotes the field of rational functions in t. This notation is generalized to polynomials, fractions and series in several indeterminates. We denote by bars the reciprocals of variables: for instance, ū = 1/u, so that L[u, ū] is the ring of Laurent polynomials in u with coefficients in L. The coefficient of u n in a Laurent polynomial

F (u) is denoted by [u n ]F (u).
We use classical notation relative to integer partitions, which we recall briefly. A partition λ of n is a non-increasing sequence of integers λ 1 ≥ λ 2 ≥ • • • ≥ λ ℓ > 0 summing to n. We write λ ⊢ n to mean that λ is a partition of n. Each component λ i is called a part. For i ≥ 1, the number of parts equal to i in λ is denoted by m i (λ). The cycle type of a permutation σ ∈ S n is the partition of n whose parts are the lengths of the cycles of σ. This partition is denoted by λ(σ). The number of permutations σ ∈ S n having cycle type λ ⊢ n equals n! z λ where z λ := i≥1 i mi(λ) m i (λ)!. We let p = (p 1 , p 2 , . . . ) be an infinite list of independent variables, and for λ a partition of n, we let p λ = p λ1 . . . p λ ℓ(λ) . The reader may view the p λ 's as the power sums in some ground set of variables. This point of view is not really needed in this paper, but it explains why we call refined Frobenius series our main generating function. Throughout the paper, we denote by K = Q(p 1 , p 2 , . . . ) the field of rational fractions in the p i 's with rational coefficients.

Given a Laurent polynomial P (u) in a variable u, we denote by [u ≥ ]P (u) the non-negative part of P (u) in u, defined by

[u ≥ ]P (u) = i≥0 P i u i if P (u) = i∈Z P i u i .
The definition is then extended by linearity to power series whose coefficients are Laurent polynomials in u. We define similarly the positive part of P (u), denoted by [u > ]P (u).

(i) which, as discussed above, are equivalent to parking functions

We now introduce several series and polynomials which play an important role in this paper. They depend on two independent variables u and z. First, we let v ≡ v(u) be the following Laurent polynomial in u:

v = (1 + u) m+1 u -m .
We now consider the following series:

V (u) = k≥1 p k k v k z k . ( 4
)
It is is a formal power series in z whose coefficients are Laurent polynomials in u over the field K. Finally we define the two following formal power series in z:

L ≡ L(z, p) := [u 0 ]V (u) = k≥1 p k k (m + 1)k mk z k , (5)
K(u) ≡ K(z, p; u) := [u > ]V (u) = k≥1 p k k z k (m+1)k i=mk+1 (m + 1)k i u i-mk . (6)
In our notation, we will often omit the dependence of series in t, z, and p, just keeping track, as above, of the variables u, x and y, which play a special role in our equations.

A refined theorem

As stated in Theorem 2, the value of the character χ m (σ) is the number of labelled intervals fixed under the action of σ, and one may see (2) as an enumerative result. Our main result is a refinement of (2) where we take into account two more parameters, which we now define. The first parameter is the number of contacts of the interval: A contact of an m-ballot path P is a vertex of P lying on the line {x = my}, and a contact of an m-Tamari interval [P, Q] is a contact of the lower path P . We denote by c(P ) the number of contacts of P . By definition of the action of S n on m-Tamari intervals, a labelled interval I = [P, Q] is fixed by a permutation σ ∈ S n if and only if σ stabilizes the set of labels of each ascent of Q. Equivalently, each cycle of σ is contained in the label set of an ascent of Q. If this holds, we let r σ (I) be the number of cycles of σ occurring in the first ascent of Q: this is our second parameter.

The main object we handle in this paper is a generating function for pairs (σ, I), where σ is a permutation and I = [P, Q] is a labelled m-Tamari interval fixed by σ. In this series F (m) (t, p; x, y), pairs (σ, I) are counted by the size (variable t), the number c(P ) of contacts (variable x), the parameter r σ (Q) (variable y), and the cycle type of σ (one variable p i for each cycle of size i in σ). Moreover, F (m) (t, p; x, y) is an exponential series in t. That is,

F (m) (t, p; x, y) := n≥0 t n n! I=[P,Q] σ∈Stab(I) x c(P ) y rσ(Q) p λ(σ) , (7)
where the second and third sum are taken respectively on all labelled m-Tamari intervals I of size n, and on all permutations σ ∈ S n fixing I. Note that when (x, y) = (1, 1), we have:

F (m) (t, p; 1, 1) = n≥0 t n n! I=[P,Q] σ∈Stab(I) p λ(σ) = n≥0 t n n! σ∈Sn χ m (σ)p λ(σ) = n≥0 t n λ⊢n χ m (λ) p λ z λ ,
since the value of character depends only on the cycle type (which justifies the notation χ m (λ)), and n! z λ is the number of permutations of cycle type λ. Hence, in representation theoretic terms, [t n ]F (m) (t, p; 1, 1) is the Frobenius characteristic of the m-Tamari representation of S n , also equal to λ⊢n c(λ)s λ , where s λ is the Schur function of shape λ and c(λ) is the multiplicity of the irreducible representation associated with λ in the m-Tamari representation. For this reason, we call F (m) (t, p; x, y) a refined Frobenius series.

Our most general result is a (complicated) expression of F (m) (t, p; x, y), which becomes simple when y = 1. We state here the result for y = 1.

Theorem 3 Let F (m) (t, p; x, y) ≡ F (t, p; x, y) be the refined Frobenius series of the m-Tamari representation, defined by (7). Let z and u be two indeterminates, and write

t = ze -mL and x = (1 + u)e -mK(u) , ( 8
)
where L ≡ L(z, p) and K(u) ≡ K(z, p; u) are defined by (5) and (6). Then F (t, p; x, 1) becomes a series in z with polynomial coefficients in u and the p i , and this series has a simple expression:

F (t, p; x, 1) = (1 + ū)e K(u)+L (1 + u)e -mK(u) -1 (9)
with ū = 1/u. In particular, in the limit u → 0, we obtain

F (t, p; 1, 1) = e L   1 -m k≥1 p k k z k (m + 1)k mk + 1   .
Extracting the coefficient of p λ /z λ (via Lagrange's inversion) shows that for a permutation σ ∈ S n of cycle type (λ 1 , . . . , λ ℓ ), the value of the m-Tamari character at σ is given by (2). Discovering the parametrization (8) of t in terms of z was easy using the conjectured value (2) of the character. Finding the parametrization of x in terms of u was difficult, but essential, since the variable x is crucial in our approach (see ( 11)). Our expression of F (m) (t, p; x, y) will appear in the complete version of the paper. When m = 1, it takes a reasonably simple form. Theorem 4 Let F (1) (t, p; x, y) ≡ F (t, p; x, y) be the refined Frobenius series of the 1-Tamari representation, defined by (7). Let z and u be two indeterminates, define V (u), L and K(u) by (4-6) (with m = 1) and set t = ze -L and x = (1 + u)e -K(u) . Then F (t, p; x, y) becomes a formal power series in z with polynomial coefficients in u and y, given by

F (t, p; x, y) = (1 + u) [u ≥ ] e yV (u)-K(u) -ūe yV (u)-K(ū) . ( 10
)
Remarks 1. It is easily seen that the case y = 1 of (10) reduces to the case m = 1 of (9) . 2. When p 1 = 1 and p i = 0 for i > 1, the only permutation that contributes is the identity. We are thus simply counting labelled 1-Tamari intervals, by their size (variable t), the number of contacts (variable x) and the size of the first ascent (variable y). We have

V (u) = v = (1 + u)(1 + ū), K(u) =
zu and the extraction of the positive part in u in (10) can be performed explicitly:

F (t, 1, 0, . . . ; x, y) = (1 + u)[u ≥ ] e yzv-zu -ūe yzv-z ū = (1 + u)e 2yz   0≤i≤j u j-i z i+j y i (y -1) j i!j! - 0≤j<i u i-j-1 z i+j y i (y -1) j i!j!   .
When x = 1, that is, u = 0, the double sums in this expression reduce to simple sums, and the generating function of labelled Tamari intervals, counted by the size and the length of the first ascent, is expressed in terms of Bessel functions:

F (t, 1, 0, . . . ; 1, y) e 2yz = i≥0 z 2i y i (y -1) i i! 2 - j≥0
z 2j+1 y j+1 (y -1) j (j + 1)!j! .

A functional equation

In this section, we describe a recursive construction of labelled m-Tamari intervals, and translate it into a functional equation satisfied by the generating function F (m) (t, p; x, y).

We encode the north (resp. east) steps of a ballot path by the letters N and E. We first recall a result that allows us to see the m-Tamari lattice as a sublattice of the standard 1-Tamari lattice (called Tamari lattice for short; similarly, a 1-ballot path is called below a ballot path).

Proposition 5 ([BMFPR11, Prop. 4]) Replacing each north step of an m-ballot path by a sequence of m north steps induces an order preserving bijection between T (m) n and the sublattice of T nm consisting of the paths that are larger than or equal to

N m E m . . . N m E m .
The functional equation of Proposition 7 below follows, although not in a straighforward manner, from a recursive description of Tamari intervals that can be found in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF]. We say that a Tamari interval I = [P, Q] is pointed if its lower path P has a distinguished contact. Such a contact splits P into two ballot paths P ℓ and P r , respectively located to the left and to the right of the contact. We use the notation

I = [P ℓ P r , Q] to denote a pointed Tamari interval. Proposition 6 ([BMFPR11]) Let I 1 = [P ℓ 1 P r 1 , Q 1 ]
be a pointed Tamari interval, and let I 2 = [P 2 , Q 2 ] be a Tamari interval. Construct the ballot paths P = NP ℓ 1 EP r 1 P 2 and Q = NQ 1 EQ 2 . Then I = [P, Q] is a Tamari interval. Moreover, the mapping (I 1 , I 2 ) → I is a bijection between pairs (I 1 , I 2 ) formed of a pointed Tamari interval and a Tamari interval, and Tamari intervals I of positive size.

We do not give here the proof of the following proposition, but refer the reader to [START_REF] Bousquet-Mélou | The representation of the symmetric group on m-Tamari intervals[END_REF].

Proposition 7 For m ≥ 1, let F (m) (t, p; x, y) ≡ F (x, y) be the refined Frobenius series of the m-Tamari representation, defined by (7). Then

F (x, y) = exp   y k≥1 p k k tx(F (x, 1)∆) (m) (k)   (x), ( 11
)
where ∆ is the following divided difference operator

∆S(x) = S(x) -S(1) x -1 ,
and the powers m and k mean respectively that the operator Γ : G(x, y) → F (x, 1) • ∆G(x, y) is applied m times, and that the operator G(x, y)

→ tx • Γ m G(x, y) is applied k times. Equivalently, F (x, 0) = x and ∂F ∂y (x, y) = k≥1 p k k tx(F (x, 1)∆) (m) (k) (F (x, y)). ( 12
)
4 Principle of the proof, and the case m = 1

Principle of the proof

Let us consider the functional equation ( 12), together with the initial condition F (t, p; x, 0) = x. Perform the change of variables (8), and denote G(z, p; u, y) ≡ G(u, y) = F (t, p; x, y). Then G(u, y) is a series in z with coefficients in K[u, y], satisfying

∂G ∂y (u, y) = k≥1 p k k z(1 + u)e -m(K(u)+L) uG(u, 1) (1 + u)e -mK(u) -1 ∆ u (m) (k) G(u, y), (13)
with ∆ u H(u) = H(u)-H(0) u , and the initial condition

G(u, 0) = (1 + u)e -mK(u) . ( 14
)
This pair of equations defines G(u, y) ≡ G(z, p; u, y) uniquely as a formal power series in z. Indeed, the coefficient of z n in G can be computed inductively from these equations (one first determines the coefficient of z n in ∂G ∂y , which can be expressed, thanks to (13), in terms of the coefficients of z i in G for i < n. Then the coefficient of z n in G is obtained by integration with respect to y, using the initial condition ( 14)). Hence, if we exhibit a series G(z, p; u, y) that satisfies both equations, then G(z, p; u, y) = G(z, p; u, y). We are going to construct such a series.

Let

G 1 (z, p; u) ≡ G 1 (u) = (1 + ū)e K(u)+L (1 + u)e -mK(u) -1 .
Then G 1 (u) is a series in z with coefficients in K[u], which, as we will see, coincides with G(u, 1). Consider now the following equation, obtained from (13) by replacing G(u, 1) by G 1 (u):

∂ G ∂y (z, p; u, y) = k≥1 p k k z(1 + u)e -m(L+K(u)) uG 1 (u) (1 + u)e -mK(u) -1 ∆ u (m) (k)
G(z, p; u, y), (15) with the initial condition G(z, p; u, 0) = (1 + u)e -mK(u) .

Eq. ( 15) can be rewritten as

∂ G ∂y (u, y) = k≥1 p k k z(1 + u)e -mK(u) Λ (m) (k) G(u, y) (17)
where Λ is the operator defined by

Λ(H)(u) = (1 + u)e K(u) H(u) -H(0) u .
Again, it is not hard to see that (17) and the initial condition (16) define a unique series in z, denoted G(z, p; u, y) ≡ G(u, y). The coefficients of this series lie in K[u, y]. The principle of our proof can be described as follows.

If we prove that G(u, 1) = G 1 (u), then the equation (15) satisfied by G coincides with the equation (13) that defines G, and thus G(u, y) = G(u, y). In particular, G 1 (z, p; u) = G(z, p; u, 1) = G(z, p; u, 1) = F (t, p; x, 1), and Theorem 3 is proved.

The case m = 1

Take m = 1. We describe the three steps that, starting from (17), prove that G(u, 1) = G 1 (u). In passing, we establish the expression (10) of F (t, p; x, y) (equivalently, of G(z, p; u, y)) given in Theorem 4.

A homogeneous differential equation and its solution

When m = 1, the equation (17

) defining G(z; u, y) ≡ G(u, y) reads ∂ G ∂y (u, y) = k≥1 p k k z k (1 + u)(1 + ū) Ω (k) G(u, y), (18)
where ū = 1/u and the operator Ω is defined by ΩH(u) = H(u) -H(0), with the initial condition

G(u, 0) = (1 + u)e -K(u) . (19)
These equations imply that G(-1, y) = 0. The following lemma provides us with a crucial symmetry property.

Lemma 8 For all k ≥ 0 one has:

(1 + u)(1 + ū) Ω (k) G(u, y) = (1 + u)(1 + ū) k G(u, y) -P k (v, y)
where

P k (v, y) ∈ K[y][[z]][v] is a polynomial in v = (1 + u)(1 + ū).
Proof: By induction on k. Alternatively, readers well acquainted with lattice path enumeration may view this lemma as a form of the reflection principle. ✷

The quantity P k (v, y) is invariant under the substitution u → ū. This symmetry will enable us to eliminate some a priori intractable terms in (18). Replacing u by ū in (18) gives

A few words on the general case

Assume m > 1. Recall from Section 4.1 that we start from (17), and want to prove that G(u, 1) = G 1 (u).

We consider the m + 1 roots u 0 , . . . , u m of the equation v(u) = v(u i ), where v(u) = (1 + u) m+1 ūm . They play a role similar to u and ū in Section 4.2. This enables us to obtain a generalization of (20), involving a linear combination of the m + 1 series G(u i , y). The reconstruction of G(u, y) and G(u, 1) from this equation is possible, but difficult, and the expression it gives for G(u, 1) did not allow us to prove directly that G(u, 1) = G 1 (u). Instead, we first proved that the generalization of (20) has a unique solution when y = 1, and then checked that G 1 (u) is a solution. Proving uniqueness of the solution is difficult, and makes the proof for m > 1 significantly longer than for m = 1.

Fig. 1 :

 1 Fig. 1: The covering relation between m-ballot paths (m = 2).

Fig. 2 :

 2 Fig. 2: A labelled 2-Tamari interval, and its image under the action of σ = 2 3 5 6 1 4.

  u)(1 + ū)Ω (k) G(ū, y), so that, applying Lemma 8 and using v = (1 + u)(1 + ū) we obtain:∂ ∂y G(u, y) -G(ū, y) = k≥1 p k k z k (1 + u) k (1 + ū) k G(u, y) -G(ū, y) .This is now a homogeneous linear differential equation satisfied by G(u, y) -G(ū, y). It is readily solved, and the initial condition (19) yieldsG(u, y) -G(ū, y) = (1 + u) e -K(u) -ūe -K(ū) e yV (u) , u) k (1 + ū) k as in (4).

Acknowledgements

We are grateful to Franc ¸ois Bergeron for advertising in his beautiful lectures various conjectures related to Tamari intervals. We also thank Éric Fusy and Gilles Schaeffer for interesting discussions on this topic.

Reconstruction of G(u, y)

Recall that G(u, y) ≡ G(z, p; u, y) is a series in z with coefficients in K[u, y]. Hence, by extracting from the above equation the positive part in u (as defined in Section 2.1), we obtain

For any Laurent polynomial P , we have

As explained in Section 4.1, G(u, y) = G(u, y) will be proved if we establish that G(u, 1) = G 1 (u). This is the final step of our proof.

The case y = 1

Eq. ( 21) completely describes the solution of (18). It remains to check that G(u, 1) = G 1 (u), that is,

Let us set y = 1 in (21). Using V (u) = K(u) + L + K(ū), this gives:

which coincides with (22). Hence G(z, p; u, y) = G(z, p; u, y) = F (t, p; x, y) (with the change of variables (8)), and Theorem 4 is proved, using (21).