Cyrille Siclet
email: cyrille.siclet@gipsa-lab.grenoble-inp.fr

Damien Roque
email: damien.roque@isae.fr

Huaqiang Shu
email: huaqiang.shu@gipsa-lab.grenoble-inp.fr

Pierre Siohan
email: pierre.siohan@orange.com

On the Study of Faster-than-Nyquist Multicarrier Signaling Based on Frame Theory

Multicarrier transmissions are classically based on undercomplete or exact Weyl-Heisenberg Riesz (biorthogonal or orthogonal) bases implemented thanks to oversampled filterbanks. This can be seen as a transmission below the Nyquist rate. However, when overcomplete Weyl-Heisenberg frames are used, we obtain a "faster-than-Nyquist" (FTN) system and it is theoretically impossible to recover exactly transmitted symbols using a linear receiver. Various studies have shown the interest of this high density signaling scheme as well as practical implementations based on trellis and/or iterative decoding. Nevertheless, there is still a lack of theoretical justifications with regard to pulse design in the FTN case. In this paper, we consider a linear transceiver operating over an additive white Gaussian noise channel. Using the frame theory and simulation results, we show that the mean squared error (MSE) is minimized when tight frames are used.

I. INTRODUCTION

It is usually recognized that perfect reconstruction of the symbols is one of the necessary conditions for reliable information transmission. This constraint implies biorthogonal synthesis and analysis bases (used respectively by the transmitter and the receiver). In the particular case of T -spaced waveforms, it leads to the Nyquist inter-symbol interference (ISI) free criterion [START_REF] Nyquist | Certain topics in telegraph transmission theory[END_REF]. This strategy has the advantage to allow a low-complexity optimal detector (linear receiver) at the expense of a maximum signaling density: the bandwidth has to be greater or equal than 1/T .

With an increasing need for spectral efficiency, it has been suggested to override the Nyquist criterion leading to "faster-than-Nyquist" (FTN) transceivers. The first approach developed by J. Mazo was based on an orthogonal single carrier system with cardinal sine pulses and binary antipodal symbols [START_REF] Mazo | Faster than Nyquist signaling[END_REF]. From this setup, he showed that an increase of the signaling rate up to 25 % has no consequence on the minimum euclidean distance between sequences of symbols. According to G.D. Forney's optimal detection over ISI channels, it follows from this result that error probability can remain unchanged even if the receiver's complexity is increased [START_REF] Forney | Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference[END_REF].

Three decades later, F. Rusek et al. provided a generalization of FTN transmission to non-binary alphabets with an emphasis on reconstruction techniques [START_REF] Rusek | Non binary and precoded faster than Nyquist signaling[END_REF]. Simplified trellis detector as well as iterative decoders have been proposed in order to target practical implementations [START_REF] Prlja | Receivers for faster-than-Nyquist signaling with and without turbo equalization[END_REF], [START_REF] Prlja | Reduced-complexity receivers for strongly narrowband intersymbol interference introduced by faster-than-Nyquist signaling[END_REF]. It confirms that binaryerror-rate (BER) over additive white Gaussian noise (AWGN) channels are similar to orthogonal systems when the density is increased up to 30 %.

When facing time-frequency selective channels, multicarrier modulations are usually justified since they allow to distribute information in the time-frequency plane using appropriate pulse shapes [START_REF] Kozek | Nonorthogonal pulseshapes for multicarrier communications in doubly dispersive channels[END_REF], [START_REF] Strohmer | Optimal OFDM design for time-frequency dispersive channels[END_REF]. However, in the context of a FTN linear system with limited output power, the challenge is to determine appropriate time-frequency spacing and pulse shaping in order to reach a trade-off between throughput, bandwidth and reconstruction error. If one further assumes a fixed bandwidth, it follows that channel-induced interference mitigation is tied to the signaling density.

Despites attractive practical implementations of FTN multicarrier systems [START_REF] Rusek | Multistream faster than Nyquist signaling[END_REF], [START_REF] Dasalukunte | Multicarrier faster-than-Nyquist transceivers: Hardware architecture and performance analysis[END_REF], a lack of theoretical justifications appears concerning their design. Such systems are usually derived from (bi)orthogonal transceivers where higher density time-frequency lattices are used. In this paper, we restrict our study to linear transceivers and focus on the minimization of the normalized mean squared error (NMSE) in presence of inter-pulse interference and additive white Gaussian noise. Our main contributions include an analysis based on the frame theory as well as practical guidelines for FTN multicarrier modulations design. This paper is organized as follows. After presenting notations and definitions used throughout the document, section 2 describes the multicarrier transceiver based on Weyl-Heisenberg families. In this context, a general definition of FTN signaling is given based on the density of its timefrequency lattice. Section 3 discusses the design of the pulse shapes in order to minimize the MSE introduced by a linear transceiver operating over an AWGN channel. Section 4 confirms the theoretical study based on simulation results. Finally, conclusions are presented in section 5.

II. SYSTEM MODEL

In this section, we first present our notations and recall basic definitions from the frame theory. Afterwards, we establish the input-output relations of a linear multicarrier transceiver in a faster-than-Nyquist context.

A. Notations and definitions

Let V be an Hilbert space. For two vectors x, y ∈ V, the inner product is denoted x, y and the norm of x is given by x =

x, x . In particular, we define for p ∈ {1, 2} the spaces

L p (R) = {x : R → C/ +∞ -∞ |x(t)| p dt < +∞} and p (I) = {x : I → C/ k∈I |x[k]| p < +∞} with I a countable index set.
Let us define f = {f k } k∈I a family of vectors in V. We say that f is a frame of V if there exist two constants 0 < A ≤ B < +∞ such that

A f 2 ≤ k∈I | f, f k | 2 ≤ B f 2 , ∀f ∈ V. (1)
The constants A, B are called lower and upper frame bounds (respectively) for the frame. If A = B, f is a tight frame. Let us define g = {g k } k∈I another frame of V; we say that f and g are dual frames if and only if

f = k∈I g k , f f k , ∀f ∈ V. (2)
If there exist not all zero coefficients {c k } k∈I ⊂ 2 (I) such that k∈I c k f k = 0 then the frame is overcomplete and several dual frames exist [11, p. 107]. Conversely, if k∈I c k f k = 0 only if c k = 0, ∀k ∈ I, the frame f is a Riesz basis and a unique dual frame exists.

In order to introduce compact notations related to frame operations, we define the synthesis and analysis operators D f and D * f associated to f :

D f : 2 (I) → V, {c k } k∈I → k∈I c k f k , (3)
D * f : V → 2 (I), f → { f k , f } k∈I (4)
where • * is the adjoint operator. It is then possible to define the frame operator S based on successive analysis and synthesis:

S f f = D f D * f f = k∈I f k , f f k . (5)
Notice that S is bounded, invertible and self-adjoint. It follows that f = { fk = S -1 f f k } k∈I is also a frame with bounds 1/B and 1/A [11, p. 100]. The frame f is called the canonical dual frame of f and it verifies the following property: among all scalar sequences {c k } k∈I for which f = k∈I c k f k , the coefficient sequence { f, fk } k∈I has minimal 2 -norm [11, p. 6].

With the aim of representing multicarrier systems, it is convenient to introduce the particular class of Weyl-Heisenberg frames (sometimes called Gabor frames) [START_REF] Feichtinger | Gabor analysis and algorithms: Theory and applications[END_REF]. We start by defining translation and modulation operators, denoted respectively T T0 and M F0 , with F 0 , T 0 ∈ R:

M F0 : L 2 (R) → L 2 (R), f (t) → f (t)e j2πF0t , (6)
T T0 : L 2 (R) → L 2 (R), f (t) → f (t -T 0 ). (7)
We consider a lattice {mF 0 , nT 0 } (m,n)∈Λ ⊂ R 2 with Λ ⊂ Z 2 ; its density is denoted ρ = 1/(F 0 T 0 ). The family of regularly modulated and translated function g ∈ L 2 (R) is written as g = {M mF0 T nT0 g} (m,n)∈Λ ; it forms a Weyl-Heisenberg frame if it fulfills (1).

B. Back-to-back input-output relation

At the transmitter side, let us define a sequence of complex

coefficients c = {c m,n } (m,n)∈Λ ∈ 2 (Λ) with Λ ⊂ Z 2 . Let g = {g m,n } (m,n
)∈Λ be a Weyl-Heisenberg frame with parameters F 0 , T 0 > 0, bounds 0 < A ≤ B < +∞ and whose vectors are derived from a generator g(t) ∈ L 2 (R):

g m,n (t) = g(t -nT 0 )e j2πmF0t . ( 8
)
The signal s(t) at the output of the multicarrier transmitter can be written as a synthesis operation based on the sequence c and the Weyl-Heisenberg family g:

s(t) = (D g c)(t) = (m,n)∈Λ c m,n g m,n (t), t ∈ R. (9)
As a result of this expansion, information carried by the complex symbol sequence is regularly spread in the timefrequency plane (fig. 1) with a minimum distance T 0 in time and F 0 in frequency. At the receiver side, we consider a frame ǧ = {ǧ p,q } (p,q)∈Λ with bounds 0 < Ǎ ≤ B < +∞. A linearly estimated sequence of coefficients ĉ = {ĉ p,q } (p,q)∈Λ is obtained by an analysis operation based on the received signal r(t) and the analysis frame ǧ:

ĉ = {ĉ p,q } (p,q)∈Λ = D * ǧ r = { ǧp,q , r } (p,q)∈Λ . ( 10
)
The convergence of the double sum mentioned in ( 9) is guaranteed by the upper bound of g and ensures a stable synthesis. Moreover, the lower bound of the frame also ensures that a non-zero input sequence generates a non-zero transmitted signal. Conversely the frame structure of ǧ guarantees the stability of the analysis operation specified in [START_REF] Dasalukunte | Multicarrier faster-than-Nyquist transceivers: Hardware architecture and performance analysis[END_REF].

We first consider a perfect channel, i.e. r(t) = s(t), such that an estimated symbol ĉp,q , with (p, q) ∈ Λ is given by ĉp,q = ǧp,q , s =

(m,n)∈Λ c m,n ǧp,q , g m,n (11)
For brevity, we define Λ p,q = Λ\{(p, q)} and we rewrite [START_REF] Christensen | Frames and bases: An introductory course[END_REF] in order to identify a useful signal term and an interference term:

ĉp,q = c p,q ǧp,q , g p,q

useful signal + (m,n)∈Λp,q c m,n ǧp,q , g m,n interference . (12)
In order to recover the transmitted symbols without ambiguity (i.e. with no interference), it is necessary to choose g and ǧ as biorthogonal Riesz sequences. This constraint requires ρ ≤ 1 which limits the signaling density in the time-frequency plane.

In this study, we consider faster-than-Nyquist transceivers that fulfill the relation ρ > 1. A consequence of this high signaling density prevents g to be a Riesz sequence. It follows that biorthogonality can't be obtained, leading to inter-pulse interference.

The FTN constraint raises several questions for the multicarrier transceiver design. For a given time-frequency lattice, how to choose ǧ in order to minimize the interference and noise power? Are there practical methods to derive ǧ from g? The following section discusses these questions using the frame theory.

III. NMSE STUDY IN PRESENCE OF INTERFERENCE AND

NOISE

In this section, we develop the conditions for NMSE minimization over an AWGN channel. We assume a given timefrequency lattice with parameters T 0 , F 0 > 0 and a generator function g(t) ∈ L 2 (R). In a more realistic scenario, these parameters would be determined with regard to the time and frequency selectivity introduced by the channel, considering a target signal-to-interference ratio or signaling density. Such considerations are explained in [START_REF] Kozek | Nonorthogonal pulseshapes for multicarrier communications in doubly dispersive channels[END_REF], [START_REF] Strohmer | Optimal OFDM design for time-frequency dispersive channels[END_REF] with ρ ≥ 1 and won't be discussed in the following. The noise is denoted z(t) such that the received signal is r(t) = s(t) + z(t) and the estimated coefficients are ĉp,q = ǧp,q , s + ǧp,q , z .

The symbols are assumed zero-mean, independent and with same variance σ 2 c . The noise z(t) is a centered complex Gaussian process, independent of the symbols, characterized by its power spectral density σ 2 z /W for |f | ≤ W/2 and 0 otherwise (with 0 < W < +∞). Let us define the received normalized symbol cp,q with (p, q) ∈ Λ: cp,q = ĉp,q ǧp,q , g p,q = c p,q + (m,n)∈Λp,q c m,n ǧp,q , g m,n ǧp,q , g p,q ip,q + ǧp,q , z ǧp,q , g p,q zp,q [START_REF] Roque | A performance comparison of fbmc modulation schemes with short perfect reconstruction filters[END_REF] Denoting E(•) the expected value operator, the NMSE of the received symbol can be expressed as:

E(|c p,q -c p,q | 2 ) σ 2 c = (m,n)∈Λp,q | ǧp,q , g m,n | 2 | ǧp,q , g p,q | 2 σ 2 ip,q /σ 2 c + ǧp,q 2 | ǧp,q , g p,q | 2 σ 2 z σ 2 c σ 2 zp,q /σ 2 c ( 14
)
Finally, the NMSE splits into two parts: the first, σ 2 ip,q /σ 2 c ties to the inter-pulse-interference and the second, σ 2 zp,q /σ 2 c is related to the noise. In the following, we discuss the separated minimization of both terms under the constraint of a non-null estimated symbol energy.

A. Interference term minimization

In view of ( 14) and according to [11, lemma 5.3.6], the minimization of the 2 -norm of { ǧp,q , g m,n } (m,n)∈Λp,q requires g and ǧ to be canonical dual frames, that is {ǧ m,n = S -1 g m,n } (m,n)∈Λp,q which implies Ǎ = 1/B and B = 1/A.

Since g has a Weyl-Heisenberg structure, it is useful to notice that S M mF0 T nT0 = M mF0 T nT0 S and S -1 M mF0 T nT0 = M mF0 T nT0 S -1 [11, lemma 9.3.1]. As a consequence, g and ǧ share the same time-frequency lattice: ǧp,q (t) = ǧ(t -qT 0 )e j2πpF0t .

(15)

This important simplification means that it is enough to find ǧ = S -1 g in order to derive the canonical dual frame of g [11, theorem 9.3.2]. Moreover, in this case,

| ǧp,q , g m,n | = | ǧ, g m-p,n-q | such that σ 2 ip,q σ 2 c = (m,n)∈Λp,q | ǧ, g m-p,n-q | 2 | ǧ, g | 2 (16) σ 2 zp,q σ 2 c = ǧ 2 | ǧ, g | 2 σ 2 z σ 2 c ( 17
)
In the following, we assume that g and ǧ are canonical dual frames.

B. Noise term minimization

Then, the Cauchy-Schwartz inequality yields | ǧ, g | ≤ ǧ g or equivalently

ǧ 2 | ǧ, g | 2 ≥ 1 g 2 . ( 18
)
The equality is satisfied when g and ǧ are proportional, which means that g and ǧ are tight Weyl-Heisenberg frames that fulfill the relation ǧ = (1/A)g. In this case assumed hereafter, A = B and we obtain from ( 16) and ( 17)

σ 2 ip,q σ 2 c = (m,n)∈Λp,q 1 A 2 | g, g m-p,n-q | 2 1 A 2 | g, g | 2 = (m,n)∈Λp,q | g, g m-p,n-q | 2 | g, g | 2 (19) σ 2 zp,q σ 2 c = 1 A 2 g 2 1 A 2 | g, g | 2 σ 2 z σ 2 c = g 2 | g, g | 2 σ 2 z σ 2 c (20)
Furthermore, the tight frame equality yields

(m,n)∈Λ | f, g m,n | 2 = A f 2 , ∀f ∈ L 2 (R). (21)
Particularly, for f = g, we have

σ 2 ip,q σ 2 c = A g 2 -g 4 g 4 = A -g 2 g 2 (22)
σ 2 zp,q σ 2 c = 1 g 2 σ 2 z σ 2 c . (23)
C. On the derivation of g 2 According to the Wexler-Raz duality theorem [11, theorem 9.3.4], g = {M mF0 T nT0 g} (m,n)∈Λ is a tight Weyl-Heisenberg frame with bound A if and only if g = {M m/T0 T n/F0 g} (m,n)∈Λ is an orthogonal family with bound A/ρ:

g t - n F 0 e j2πm t T 0 , g t - q F 0 e j2πp t T 0 = A ρ δ m,p δ n,q .
(24) Particularly, for m = p = 0 and n = q = 0, we obtain

g, g = g 2 = A ρ . (25)
Finally the theoretical interference and noise terms are obtained:

σ 2 ip,q σ 2 c = 1 -F 0 T 0 F 0 T 0 = ρ -1 and σ 2 zp,q σ 2 c = ρ A σ 2 z σ 2 c . (26)
This result confirms that interference and noise power increases with the signaling density ρ.

There are two ways to normalize the system:

• by imposing A, which yields g = A/ρ;

• by imposing g , which yields A = ρ g 2 and ǧ = g/(ρ g 2 ).

Particularly the case A = 1 implies that the transmitter and the receiver share the same generator function ǧ = g with g = 1/ √ ρ. Moreover, the symbol energy is preserved over transmission, since for a tight frame, we have:

s 2 = A (m,n)∈Λ |c m,n | 2 = (m,n)∈Λ |c m,n | 2 . ( 27
)
These results can be summarized in the following theorem. Theorem 1: A multicarrier linear transceiver based on Weyl-Heisenberg families with density ρ > 1 achieves a minimal mean squared error with AWGN channel when it uses a tight Weyl-Heseinberg frame for transmission and reception. Moreover the NMSE is then given by

E(|c p,q -c p,q | 2 ) σ 2 c = (ρ -1) + ρ A σ 2 z σ 2 c . (28)
IV. SIMULATIONS UNDER AWGN CHANNEL

In this section, we measure the performances of various FTN multicarrier systems in terms of NMSE. The linear transceiver is characterized by a number of subcarriers M = 128 and a lattice density ρ ∈ {16/15, 16/14, 16/12, 16/10}. Simulations are performed using K = 1000 multicarrier blocks composed of symbols taken in a quaternary alphabet forming a quadrature phase-shift keying (QPSK) modulation. Four types of generators (or pulse shape filters) are used: square-root-raised cosine (SRRC), rectangular (RECT) as specified for CP-OFDM [START_REF] Roque | A performance comparison of fbmc modulation schemes with short perfect reconstruction filters[END_REF], time-frequency localization (TFL) maximized and out-of-band energy (OBE) minimized [START_REF] Pinchon | Closed-form expressions of optimal short pr fmt prototype filters[END_REF]. We notice that the SRRC filter is truncated at length of 32 blocks (32T 0 ), and the three last pulse-shapes are characterized by an impulse response equal to T 0 which ensures a lowcomplexity implementation [START_REF] Roque | A performance comparison of fbmc modulation schemes with short perfect reconstruction filters[END_REF].

We start by using SRRC filters with roll-off parameter 0 ≤ α ≤ 1 in order to investigate the mean interference power introduced by a FTN signaling over an ideal channel (fig. 2). In figure 2, we plot the theoretical mean interference power given by ( 16), the simulated interference power (by letting σ 2 z = 0), as well as the theoretical interference for tight frame expressed by (26). For each ρ, the minimum value of σ 2 ip,q /σ 2 c is reached below a given value of α. In order to explain this result, it is convenient to consider a system based on the dual lattice with a fixed T 0 parameter: since the bandwidth of a given subcarrier is (1+α)F 0 the system is orthogonal if (1+α)F 0 ≤ 1/T 0 or equivalently if α ≤ ρ -1. In the FTN case, this appropriate choice of α makes g a tight frame. Notice that the suboptimal results obtained when α is close to zero is due to the truncation of the filters. This effect becomes inconspicuous when α increases.

Figure 3 extends the previous observation to several other filters. Since TFL and OBE filters form orthogonal systems in the dual lattice configuration, they lead to tight frames in the FTN case. However, the rectangular short filters which corresponds to CP-OFDM does not generate tight frames since ǧ = (1/A)g. Furthermore, the suboptimal performances of rectangular filters are justified because ǧ and g are neither canonical dual frames.

Finally, we examine tight frame signaling schemes over an AWGN channel. TFL and SRRC filters (α = ρ -1) are chosen for this simulation. Figure 4 shows the global NMSE of the two filters and the corresponding theoretical values as a function of σ 2 c /σ 2 z . We observe that the simulation results perfectly coincide with the theoretical values, the tight frame NMSE equation is thus validated.

Fig. 1 :

 1 Fig.1: Representation of transmitted signal energy in the timefrequency plane. In this example, a Gaussian-shaped generator function g is used and the lattice parameters allow a clear separation between pulses in the frequency domain and an overlap in the time domain.

10 Fig. 2 :Fig. 3 : 10 Fig. 4 :

 1023104 Fig.2: Mean interference power over an ideal channel using SRRC filters with roll-off factor α.

V. CONCLUSION

We have expressed the input-output relations of a linear multicarrier transceiver operating at a high signaling density that prevents perfect reconstruction of the symbols. In this "faster-than-Nyquist" context, we have shown several conditions in order to minimize the MSE of such transceivers based on Weyl-Heisenberg frames. First of all, inter-pulse interference is minimized if canonical dual frames are used. Futhermore, the use of tight frames is optimal when a white gaussian noise is added.

Future investigations to be performed on FTN multicarrier signaling consist of designing efficient implementation schemes, including low-complexity equalizers. A performance analysis over time-frequency selective channels would also be interesting in order to target practical applications.

VI. ACKNOWLEDGEMENT

This work has been supported by Orange-Labs, under a research contract on faster-than-Nyquist signaling.


domain: math info

text:
Shouyu Ma
email: shouyu.ma@centralesupelec.fr

Evren Sahin
email: evren.sahin@centralesupelec.fr

Yves Dallery
email: yves.dallery@centralesupelec.fr

Ziad Jemai
email: zied.jemai@centralesupelec.fr

Assortment decision in the Multi-Product News-Vendor Problem with Demand Substitution

Retailers are confronted to make ordering decisions for a large category of products offered to end consumers. In this paper, we extend the classical mono-product News-Vendor Problem to a multi-product News-Vendor Problem with demand transferring and demand substitution. We focus on the joint determination of optimal product assortment and optimal order quantities. Computational algorithms are presented to solve the problem. We compare the global optimization policy with some other policies used in practice by numerical examples.

I. INTRODUCTION

Product variety is a key element of competitive strategy. Many retailers become successful by offering a wide selection of products. Supermarkets such as Wal-Mart and Carrefour are good examples from grocery retailing. Demand for variety comes from both the taste of diversity for an individual consumer and diversity in tastes for different consumers. However, despite the advantages of product variety, the full degree of variety cannot be supplied generally, owning to the increase of cost in inventory, shipping, and merchandise presentation, etc. Thus, the optimization of product assortment (the products to sell), and the order quantity for each product, is a relevant decision that retailers face.

The News-Vendor Problem is a classical problem in inventory management aiming at finding the optimal order quantity which maximizes the expected profit under probabilistic demand [START_REF] Khouja | The single-period (news-vendor) problem: literature review and suggestions for future research[END_REF], [START_REF] Qin | The newsvendor problem: Review and directions for future research[END_REF]. The demand for products is unknown, thus the order quantity for each product should be optimized due to the trade-off between two situations: if the order quantity is not enough, underage happens and lost sale causes lost profit; if the order quantity is too large, overstock happens. The classical mono-product News-Vendor Problem is in the situation that only one product is considered. In our case, we consider multiple products. Thus, to optimize the assortment, two other important factors should also be considered. First, product variety brings possible substitution when underage happens: different colors or styles, for example, act as substitutes when the client finds a product is out of stock. Second, beside of the purchasing cost which increases with the order quantity, other fixed costs are associated with stocking a product, e.g. the cost related to a fixed space for each product, the related labor cost, etc. In these situations, the fixed cost will clearly reduce the assortment size. This paper extends the classical News-Vendor Problem to determine the product assortment and product order quantities considering product substitution. We develop a model for the demand transferring effect when some products are abandoned. We use the Monte Carlo method to solve the multi-product News-Vendor Problem under substitution. Analysis of illustrative examples shows that assortment optimization and substitution have significant effects on the optimal order quantities and on the expect profit. The rest of the paper is organized as follows. Section 2 presents the related literature review. In section 3, we formulate the News-Vendor Problem with multiproducts under demand substitution. In section 4, we solve the joint optimization of assortment and optimal order quantities and give computational algorithms. In section 5, numerical examples are provided. Section 6 contains concluding remarks.

II. LITERATURE REVIEW

A survey of the literature on the News-Vendor Problem is provided by [START_REF] Khouja | The single-period (news-vendor) problem: literature review and suggestions for future research[END_REF], [START_REF] Qin | The newsvendor problem: Review and directions for future research[END_REF]. Over the last decades, interest for multi-product News-Vendor Problem continues unabated. The special case where different products have independent demand and no possible substitution is considered by [START_REF] Lau | The multi-product multiconstraint newsboy problem: Applications, formulation and solution[END_REF]. The topic of substitution in inventory management first appears in [START_REF] Mcgillivray | Some concepts for inventory control under substitutable demand[END_REF]. Papers on this topic can be divided into 3 categories according to their substitution types: papers of the first category deal with one-direction substitution or firm-driven substitution, where only higher grade product can substitute a lower grade product, because the supplier makes decisions for consumers on choosing substitutes (see, e.g., [START_REF] Bitran | Ordering policies in an environment of stochastic yields and substitutable demands[END_REF]- [START_REF] Rao | Multi-product inventory planning with downward substitution, stochastic demand and setup costs[END_REF]). For example, the retailer provides a high quality product as a substitute for a consumer who prefers a product with lower quality but it is out of stock. The second category consists of papers where arriving consumers' number follows a stochastic function and consumers make purchasing decisions under probabilistic substitution when their preferred product is out of stock (see, e.g., [START_REF] Smith | Management of multi-item retail inventory systems with demand substitution[END_REF] and [START_REF] Mahajan | Inventory competition under dynamic consumer choice[END_REF]). Here the consumers come one by one and choose their substitutes within the remaining products by themselves. The third category consists of papers considering that each product can substitute for other products and the fraction that one out-of-stock product is substituted by another product is deterministic. Moreover, this category can be divided into subcategories as either the two-product (see [START_REF] Mcgillivray | Some concepts for inventory control under substitutable demand[END_REF], [START_REF] Parlar | Optimal ordering decisions for two substitutable products with stochastic demands[END_REF]- [START_REF] Nagarajan | Inventory models for substitutable products: Optimal policies and heuristics[END_REF]) or multi-product case (see [START_REF] Lippman | The competitive newsboy[END_REF]- [START_REF] Zhao | Newsvendors under simultaneous price and inventory competition[END_REF] and centralized or competitive case. [START_REF] Netessine | Centralized and competitive inventory models with demand substitution[END_REF] obtained optimality conditions for both competitive and centralized versions of the single period multi-product inventory problem with substitution. [START_REF] Huang | A competitive multiple-product newsboy problem with partial product substitution[END_REF] study a multi-product competitive News-Vendor problem with shortage penalty cost and product substitution. They characterize the unique Nash equilibrium of the competitive model. An iterative algorithm is developed based on approximating the effective demand by a service-rate approximation approach. Most of earlier works focus on optimizing order quantities for a given assortment of products. [START_REF] Smith | Management of multi-item retail inventory systems with demand substitution[END_REF] and [START_REF] Shah | The retailer multi-item inventory problem with demand cannibalization and substitution[END_REF] deal with optimal assortment decision as well as optimal order quantity decision. [START_REF] Shah | The retailer multi-item inventory problem with demand cannibalization and substitution[END_REF] considers also the demand cannibalization of the standard product demand owning to retailing its customized extensions. The work of this paper differs from earlier research in many ways. Unlike [START_REF] Smith | Management of multi-item retail inventory systems with demand substitution[END_REF] who model demand by a negative binomial process and [START_REF] Shah | The retailer multi-item inventory problem with demand cannibalization and substitution[END_REF] who model demand as a Poisson process, our method can be adapted to general demand distributions. We consider the transfer of demand owning to the abandonment of some products, while the demand of the abandoned products is totally lost in [START_REF] Smith | Management of multi-item retail inventory systems with demand substitution[END_REF]. In addition, we do not approximate of the effective demand, while [START_REF] Smith | Management of multi-item retail inventory systems with demand substitution[END_REF] who approximate the effective demand by a service-rate approximation approach. Furthermore, we develop heuristic solutions to solve the problem.

III. PROBLEM MODELING

The News-Vendor model is appropriate for seasonal product retailing problems where decisions should be made before the beginning of the selling season. In addition, the News-Vendor (NV) is often faced with a choice set of similar products (we call the set as a product category) with different colors, sizes, etc. Each product is associated with a market share p i , which represent the percentage of a market defined in term of unit. Each product has a unit selling price, unit purchasing cost and in case of over-stock, the product is recycle with a salvage value. Considering a product category consists of n substitutable products in the market, intuitively more products will bring more sale and thus the NV might realize more profit. But the fact of fixed cost K i related to each product will surely reduce assortment size. In these reasons, the NV might choose a product assortment denoted M to stock for the selling season and other products (subclass R) will not be stocked. The demand transferring happens: the demand of not stocked product will partly be transferred to stocked products. When the selling season begins, customers will purchase the stocked products and when under-stock happens, they make substitutions. Before the selling season, the NV decides both the products to sell in the selling season and the purchase quantity for each product. The objective is to maximize the expected profit, subject to several constraints. The sequence of events is shown in figure 1. x a random variable: total demand for the product category, with a continuous probability function f (x) and cumulative function F (x), who has a mean µ and standard deviation σ, X realized value of x, x i demand for products i, with a probability function f i (x i ) and cumulative function F i (x i ), X i realized value of x i , p i the market share proportion of demand for product i, L i the probability that a consumer who prefers product i is unwilling to substitute, K i fixed cost related to displaying product i, v i unit selling price for product i, w i unit purchasing price cost product i, s i unit salvage price for product i, x m net demand for product m after the transfer of demand, with a probability function f m (x m ) and cumulative function F m (x m ), who has a mean µ m and standard deviation σ m , X m net realized value of x m , p m the new market share proportion of demand for product m after the transfer of demand, m ∈ M α ij the fraction of consumers that purchase product j as a substitute when product i is out of stock, i, j = 1, 2, , m,

Decision variables:

M the subclass of products to be displayed,

Q the vector of order quantities, Q = [Q m ], m ∈ M .
Here Q m is the order quantity for product m.

The assumptions can be stated formally as follows:

ASSUMPTION 1: The total demand distribution for the product category is known. ASSUMPTION 2: Given the realized total demand X, the initial realized demand X i equals to p i X.

ASSUMPTION 3: A part of demand for abandoned subclass R is lost (lost sale, the probability is represented by L i ). The other part of demand for abandoned subclass R will be transferred to subclass M in proportion to their original market shares. ASSUMPTION 4: Consumers will purchase the products that will be stocked for the selling season, i.e. product in subclass M .

ASSUMPTION 5: If their first choice product is not available, consumers may choose to purchase a substitute product with the portion of substitution denoted as α ij . If this substitute product is out of stock, the consumer will leave (a lost sale ), i.e. there is no second substitute attempt. ASSUMPTION 6: A fixed cost is related to each product, if the NV wants to stock it for the selling season.

A. Transfer of demand modeling

When product r of subclass R is abandoned, a percentage L r of demand is lost. Other demand is distributed to the products of subclass M . The additional demand transferred to product m(m ∈ M ) is:

p m m p m r [(1 -L r )X r ], r ∈ R, m ∈ M (1)
After the transfer of demand, the net realized demand X m for product m is obtained as:

p m X+ p m m p m r [(1 -L r )X r ] = p m (1+ r [p r (1 -L r )] m p m )X
(2) The new demand proportion p m for product m is:

p m (1 + r [p r (1 -L r )] m p m ) (3)
Property 1: The probability distribution for the net demand x m for product m denoted as f m (x m ) follows:

f m (x m ) = f ( x p m ) p m (4)
Proof: The proof is provided in the Appendix (c.f. annex 1)

Other properties can then be derived from Property 1.

Property 2: The cumulative distribution for the net demand x m for product m denoted as F m (x m ) follows:

F m (x m ) = F ( x p m ) (5)
Property 3: The standard deviation of x m is :

σ m = p m σ (6)
Property 4: The mean value of x m is:

µ m = p m µ (7)

IV. PROBLEM FORMULATION

The NV decides both which products to stock (the assortment) and the order quantity for each product. The objective of our method is to optimize the expected profit, with fixed cost K i associated with stocking product i. We use two policies to solve the problem: sequential optimization and global optimization. The first policy determines the optimal product assortment considering only the transfer of demand in the first step, then in the second step determines the optimal order quantities considering the substitutions within this assortment. The global optimization policy considers simultaneously the transfer of demand and substitution to determine the optimal assortment. While the global optimization policy gives a solution outperforming the first one, sequential optimization policy shows close results with less computation time.

A. Sequential optimization

Assortment decision M * : The sequential optimization policy determines the optimal assortment in the first step. We obtain the optimal subclass M * by considering only the transfer of demand. Then for a given product subclass M , the demand follows continuous probability functions f m , m ∈ M . The profit for product m can be easily developed, see equation 8.

π m = v m x m -w m Q m + s m (Q m -x m ) -K m if x m < Q m v m Q m -w m Q m -K m otherwise (8)
The total profit is the sum of the profits for each product and the second derivative of the expected profit function proves that it is concave with Q m , ∀m ∈ M . The optimal order quantity Q m for product m respects:

f i ( Q m ) = v m -w m v m -s m (9) E(π( Q)) = m∈M [ Qm 0 (v m -s m )x m f m (x m )dx m -K m ] (10
) We find same order quantity conditions as the classical News-Vendor problem because we consider no substitution effects in this step. The optimal expected profit is developed in equation 10. Enumeration of all possible M gives M * that maximize the optimal expected profit without considering the substitution effect.

Considering the substitution to solve Q * : Once the NV decides the optimal product subclass M * , it is a multi-product substitution problem similar to the one considered by [START_REF] Netessine | Centralized and competitive inventory models with demand substitution[END_REF]. As the selling period continues, stock-out will happen, a part of unsatisfied demand will be lost with the proportion L i . The remaining demand will be shared by other products of M * in proportion to their market shares. The substitution fractions α ij are developed as:

α ij = p j (1 -L i ) k =i p k = p j (1 -L i ) k =i p k , i, j, k ∈ M * (11)
Define x s i as the effective demand for product i, which is the sum of the net demand x i and the additional demand for product i received from other out-of-stock products caused by substitution. We have

x s i = x i + j =i α ji (x j -Q j ) + (12)
Here x + = max(0, x). The profit for a product is the revenue subtracting the overage cost, the underage cost and the fixed cost. Then the expected profit function is:

(13) E(π(Q)) = E i [(v i -w i )x s i -(v i -w i )(x s i -Q i ) + -(w i -s i )(Q i -x s i ) + -K i ]
The first-order necessary optimality conditions are derived from equation 13 as follows:

(

) P r(x i < Q * i ) -P r(x i < Q * i < x s i ) + j =i v j -s j v i -s i α ij P r(x s j < Q * j , x i > Q * i ) = v i -w i v i -s i 14
Q * i denotes the optimal order quantity for product i in subclass M * . The second and third term in equation 14 equal to zero for the special case where no substitution is considered, then equation 14 becomes the order quantity optimality condition for a classical News-Vendor problem (equation 9). Let's note that equation 14 is the same as the solution of Serguei and Nils [START_REF] Netessine | Centralized and competitive inventory models with demand substitution[END_REF]. Thus, for a fixed product subclass M * , the fixed cost has no effect on the optimal order quantities.

B. Global optimization

For a subclass M , if we consider the substitution effect, the optimal expected profit will be different from equation 10. Thus, the subclass M * determined by the sequential optimization policy can be not optimal. To obtain the optimal subclass, we need to consider simultaneously the demand transfer and substitution effects.

Given a product subclass M , the net demand x and the effective demand x s i are derived in equation 4 and 12. The expected profit and the optimal order quantities have same equations as equation 13 and 14. The difference is that the subclass M is no longer given, but to be determined. There are 2 n possibilities for M , enumerate all of them and we can find M * who maximizes of the expected profit.

C. Policies used in practice

We propose 3 decision policies that can be used in practice and compare them with the sequential optimization (Policy 4) and global optimization (Policy 5) policies. Our goals in examining these policies are: 1. to understand qualitatively any distortions that might be introduced in inventory decisions if one ignores (or approximates) substitution effects, 2. to understand any distortions that might be introduced if one considers the assortment and substitution effects separately, and 3. to gauge the impact of substitution effects on assortment and profits.

Policy 1: NV with n initial products, no product abandonment nor substitution. It makes the assumption that substitution effects are ignored entirely. Thus there is neither demand transferring nor substitution. The total expected profit is developed in the same way as equation 10. We have: The optimal order quantity for product i is:

(15) E(π(Q)) = n i=1 [ Qi 0 (x i (v i -w i ) -(Q i -x i )(w i -s i ))f i (x i )dx + inf Qi Q i (v i -w i )f i (x i )dx i -K i ]
Q * i = p i F -1 ( v i -w i v i -s i ) (16)
Then the optimal expected profit is derived as:

E(π(Q * )) = n i=1 [ Q * i 0 x i (v i -s i )f i (x i )dx -K i ] (17)
Policy 2: NV with assortment, the News-Vendor considers only the transferring of demand. For a given product subclass M , the demand probability functions are changed from f m to g m , m ∈ M . The optimal expected profit is obtained by equation 10 and the optimal order quantities by equation 9. Enumeration of all possible M gives M * that maximize the optimal expected profit.

Policy 3: NV with substitution, the News-Vendor Problem for n products considering the substitution. We have same optimal order quantities as equation 4 with M * identical to the product category and the optimal expected profit function is:

(18) E(π(Q)) = E n i [(v i -w i )x s i -(v i -w i )(x s i -Q i ) + -(w i -s i )(Q i -x s i ) + -K i ]
Policy 4: Sequential optimization, the News-vendor considers sequentially the transferring of demand and the substitution. We get the value of M * obtained by policy 2 then consider the substitution effect to get the optimal order quantities and expected profit.

D. Algorithm

Caused by the complexity of equation 14, we cannot get the optimal order quantities directly. Thus we use a Random-walk method to find the solution. The procedure is as follows:

Step 1: Initialize Q with the values obtained by the optimal order quantity condition of M independent classic News-Vendor Problems; initialize the walk length λ and the limit of it: .

Step 2: generate n random points around Q with a distance λ to Q. And get the best point Q among these n points;

Step 3: if Q is better than Q, assign the value of Q to Q, go to step 2. If not, halve the value of λ, if λ > , go to step 2, otherwise, go to step 4;

Step 4: if Q satisfies the optimality condition, stop, otherwise go to step 1.

We use two methods to determine in step 3 that Q is better than Q or not. Both of these methods are carried out by Monte Carlo method.

First, we define an objective function as the difference between the left side and right side of equation 14. If the order quantities are optimal, equation 14 should be satisfied, thus the objective equation should be equal to zero. But in fact, zero can not be strictly realized in computation. So we regard Q is better than Q if h(Q ) < h(Q) and the optimality condition is obtained when h(Q ) < 0.1; Second, we regard Q is better than Q if Q brings a better expected profit than Q. The value of expected profit is obtained from equation 18.

V. NUMERICAL ANALYSIS

We use normally distributed demand in our example, other demand distributions will also work. We consider a product category of 6 products with mean total demand µ = 100, the selling price, purchasing cost, salvage value, fixed cost and unwilling-to-substitute fraction are the same for all products: v = 9, w = 6, s = 3, K i = K, and L i = L. The market shares are set as an approximate linear increase: p i = (0.09, 0.12, 0.15, 0.18, 0.21, 0.25). These simplifications facilitate the comparison with other heuristic policies and make it easier to see how different performances vary with the market shares. We use the Monte Carlo method to compute the optimal order quantities and expected profits. In this example, we use the default random generator in Matlab generating 10000 samples to represent the demand with normal distribution (at about a confidence level of 98% with a sampling relative error 2.3%).

Considering K = 15 and L = 0.5, the profit comparison for the five policies is given in figure 3. The results show that the global optimization policy outperforms other policies and the sequential optimization does very well particularly, achieving 100%, 100%, 99.9%, 100% and 100% of the profits generated by the global optimization policy, respectively, at σ = 10, 20, 25, 30 and 40. Intuitively the expected profit decreases with σ for every policy we use. Considering the assortment, the total order quantity is remarkably reduced comparing with the Independent News-Vendor policy, see figure 4. Order quantities for each product obtained by different policies with σ = 30 are shown in figure 5. We find that the order quantity increases with the market share value for each policy. Similar results are found with other values of σ. As shown in table I, the value of assortment size is reduced comparing with the Independent News-Vendor policy in using the sequential optimization or global optimization policy. Comparing policy 1 with policy 2 and 3: If we fix the value of σ, the optimal order quantities for each product can be determined, and these quantities do not change with K or L. While the expected profit is the smallest, the total order quantity obtained by policy 1 is the largest compared with policy 2 and 3.

Considering the assortment or substitution both increase the profit in our examples. As the assortment size decreases, the total fixed cost decrease, thus the profit could increase. The substitution improves the profit in two aspects: on one hand, the unit underage cost is lower because the unsatisfied demand for one product may be substituted by another product; on the other hand, the unit overage cost for a product is lower too, because it receives some additional substitute demand from other products.

Policy 2 and 3 both decrease the total order quantity. When the assortment is considered, some product could be abandoned and some demand is lost, thus the total order quantity should be less than that of the News-Vendor Problem with n initial products. When substitution is considered, the underage cost is reduced, which creates the intensive to decrease the order quantity; and overage cost is also reduced, which creates the opposite effect: to increase the order quantity. In our examples the first effect dominates. In fact, we can find that the lost sale related to the substitution caused by an underage is smaller than that caused by an overage. Thus, the substitution has more important effect on underage rather than overage.

Moreover, the abandonment begins with the product with the smallest market share. As the value of σ increases more products will be abandoned. The intuition to these is the following: firstly, the stocking cost K i leads to abandon the less popular products because the cost of these products is bigger than the revenue. As the uncertainty increases, the revenue decreases, and then more products become unprofitable. Secondly, popular products can bring more profit. They have larger demand, thus more demand will be lost when they are abandoned, while abandoning less popular products will lose less demand.

Comparing policy 4 with policy 2 and 3: The sequential optimization policy brings more profit compared with these two models. The difference of the expected profit between the sequential optimization policy and Substituted News-Vendor policy can be more obvious when we change the parameters, e.g. let K=25. The combination of assortment and substitution seems to significantly improve the profit.

The total order quantity obtained by the sequential optimization policy is smaller than that of policy 2 and 3. This is intuitive because the News-Vendor with assortment obtains less total order quantity than News-Vendor with substitution and further reduction is made if we consider the substitution effect consecutively after the assortment.

Comparing policy 5 with policy 4: In our examples, global optimization policy obtains same results as the sequential optimization policy, but the case σ=25. In this case, the assortment size is bigger than that obtained by sequential optimization policy, the order quantities for each product are not the same either, and the profit is smaller but very close. We try different combinations of parameters (K, L, σ), and get same results: the assortment size and total profit are not smaller but close to that obtained by sequential optimization policy.

The substitution makes it possible to expand the assortment size, because while one product is not profitable in Assorted News-Vendor policy, the substitution can make it receive some additional substitute demand from other products, thus this product can be profitable and not abandoned.

A. Impact of L

This example shows the performance under different value of unwilling-to-substitute fraction L. Considering σ=10, 25, 40, the profit, assortment size and total order quantity are calculated by the global optimization policy.

For a fixed σ, the assortment size increases with L and the expected profit decreases. For a fixed value of L, the expected profit decreases with σ; the assortment size for σ = 10 is equal to or larger than others but the special cases L = 1, 0.1; the total order quantity increases with σ when L = 1, while in other cases, we have no clear rules. But we can find that in our case, the total order quantity is smallest for L = 0.3 and reaches maximum when L = 1 or L = 0. Intuitions to these results are the following: The increase of L results in more lost sale in two aspects: when one product is abandoned on one hand and when one product in stock comes to an underage on the other hand. The first one leads to a bigger assortment size, and the second one reduces the expected profit. Intuitively the expected profit decreases with σ for a normally distributed demand. For a fixed L, we know that a larger assortment size reduces the lost sale but brings more stocking cost, so its a trade-off to determine the size. When σ is smaller, the profit coming from reducing the lost sale is bigger, Fig. 8. the expected profit as a function of L, for σ = 10, 25, 40 so the trade-off tends to bigger assortment size. Special case is when L = 0 and 0.1, the assortment size for σ=10 is 1, this means there is no alternate product to choose when the product is at underage. The reason is: when L and σ are both small, e.g. L = 0, 0.1, σ = 10, the demand substitution benefit is less than the stocking cost of an additional product. The total order quantity does not respect clear rules for different σ, because the quantity depends on the assortment size (not the same for different σ). In the special case when L = 1, each of them have 6 products in the assortment, and there is no transfer of demand nor substitution, thus same as a classic News-Vendor Problem. The reason why the order quantity reaches maximums for L = 0 and L = 1 is that, the lost sale is zero when L = 0 and very small when L = 1 (no abandoned product).

B. Impact of K

This example shows the performance under different value of stocking cost. We consider L = 0.5. The profit and the assortment size are calculated by the global optimization policy with σ=10, 25, 40, see figure 9, 10.

For a fixed σ, the assortment size decreases with K with the same σ and decreases with σ for same value of K. As we discussed before, the trade-off between lost sale and stocking cost determine the assortment size. When K is larger, the stocking cost has more important influence and when σ is bigger, the influence of lost sale is less important, thus both leading a smaller stocking size. Intuitively the expected profit decreases with σ and K.

VI. CONCLUSION

This paper extends the classical News-Vendor Problem to solve the joint optimization of the product assortment and the order quantities considering the demand transferring effect and the substitution effect within the assortment.

We developed the transferring fractions and substitution fractions in proportion to the market shares. The randomwalk Monte Carlo method provides an efficient computational approach to get the value of expected profit and optimal order quantities for a product assortment. An enumeration of all possible product assortments is done to search the best one. The numerical examples show insights regarding the performances of the News-Vendor Problem. Our examples indicate that the demand transferring and substitution have remarkable effects on the assortment, expected profit, and optimal order quantities. And the sequential optimization policy and global optimization policy both bring better profit performance than separately. Global optimization obtains the best profit, but the sequential optimization policy shows close results and the computing time is considerably reduced.

With the global optimization policy, several results can be derived from numerical results: The expected profit decreases with the fixed cost value, the fraction of lost sale and demand uncertainty. Assortment size increases with the fraction of lost sale but decrease with the fixed cost value. The total order quantity does not respect strict behaviors but it shows that the order quantity reaches the maximums when lost sale fraction is zero or 100%, and tends to decrease with fixed cost value.

VII. APPENDIX

Annex 1: X m = P m X, thus the probability that X ∈ (a, b) equals to the probability that X m ∈ (P m a, P m b), regardless the value of a and b:

Fig. 1 .

 1 Fig. 1. Sequence of events

Fig. 2 .

 2 Fig. 2. Decision policies

Policy 5 :

 5 Global optimization, the News-Vendor Problem considers simultaneously the demand transfer and substitution effects. See more details in section 4.B.

Fig. 3 .

 3 Fig. 3. Expected profit for different policies with σ=10, 20, 25, 30, 40.

Fig. 4 .

 4 Fig. 4. Total order quantity for different policies with σ=10, 20, 25, 30, 40.

Fig. 5 .

 5 Fig. 5. Order quantities for σ=30, K=15, L=0.5 σ = 10 σ = 20 σ = 25 σ = 30 σ = 40 Independent News-Vendor 6 6 6 6 6 Assorted News-Vendor 5 5 4 4 4 Substituted News-Vendor 6 6 6 6 6 Sequential Optimization 5 5 4 4 4 Global Optimization 5 5 5 4 4TABLE I. THE ASSORTMENT SIZE FOR DIFFERENT POLICIES WITH σ = 10, 20, 25, 30, 40

Fig. 6 .Fig. 7 .

 67 Fig. 6. the assortment size as a function of L, for σ = 10, 25, 40

Fig. 9 .

 9 Fig. 9. the assortment size as a function of K, for σ = 10, 25, 40

  This equation should be available for any value of a and b, thus we have equation 4.


A NOTE ON HYPERQUADRATIC CONTINUED FRACTIONS IN CHARACTERISTIC 2 WITH PARTIAL QUOTIENTS OF DEGREE 1 by A. Lasjaunias

Keywords: Continued fractions, Fields of power series, Finite fields. 2000 Mathematics Subject Classification: 11J70, 11T55

.

Introduction

Let p be a prime number, q = p s with s ≥ 1, and let F q be the finite field with q elements. We let F q [T ], F q (T ) and F(q) respectively denote, the ring of polynomials, the field of rational functions and the field of power series in 1/T with coefficients in F q , where T is a formal indeterminate. These fields are valuated by the ultrametric absolute value (and its extension) introduced on F q (T ) by |P/Q| = |T | deg(P )-deg (Q) , where |T | > 1 is a fixed real number. Hence a non-zero element of F(q) is written as α = k≤k 0 a k T k with k 0 ∈ Z, a k ∈ F q , and a k 0 = 0 and we have |α| = |T | k 0 . This field F(q) is the completion of the field F q (T ) for this absolute value.

We recall that each irrational (rational) element α of F(q) can be expanded as an infinite (finite) continued fraction. This will be denoted α = [a 1 , a 2 , . . . , a n , . . . ] where the a i ∈ F q [T ], with deg(a i ) > 0 for i > 1, are the partial quotients. In this note we are concerned with infinite continued fractions in F(q) which are algebraic over F q (T ). Indeed we consider algebraic elements of a particular type. Let r = p t with t ≥ 0, we say that α belonging to F(q) is hyperquadratic (of order t) if α is irrational and satisfies an algebraic equation of the particular form Aα r+1 +Bα r +Cα+D = 0, where A, B, C and D belong to F q [T ]. For more details on these particular power series, the reader may see the introduction of [BL]. Note that quadratic elements are hyperquadratic. We recall that an element in F(q) is quadratic if and only if its sequence of partial quotients is ultimately periodic. Many explicit continued fractions are known for nonquadratic but hyperquadratic elements, see the references below. However, these particular algebraic elements play an important role in diophantine approximation and this is why they were first considered. For a general account on continued fractions in power series fields and diophantine approximation, also for more references on this matter, the reader can consult [S] and [L2].

The origin of the study of continued fractions for hyperquadratic power series is due to Baum and Sweet ([BS1] and [START_REF] Baum | Badly approximable power series in characteristic 2[END_REF]). It has been developped in the 1980's by Mills and Robbins [MR]. Mills and Robbins pointed out the existence of such hyperquadratic continued fractions with all partial quotients of degree one, in odd characteristic with a prime base field. Different approaches were developped to explain this phenomenon (see [L1] and [START_REF] Lasjaunias | Flat power series over a finite field[END_REF], [START_REF] Lasjaunias | On a family of sequences defined recursively in F * q (II)[END_REF]), first with the base field F 3 , then in all characteristic with an arbitrary base field. However these methods left many unanswered questions and the study could not be achieved. In [L3] a new approach was introduced and this led to the presentation of different families of explicit hyperquadratic continued fractions, also with unbounded partial quotients. In a recent work with Yao [START_REF] Lasjaunias | Hyperquadratic continued fractions in odd characteristic with partial quotients of degree one[END_REF], with this new approach, in the case of an arbitrary base field of odd characteristic, we could give the description of a large family, including the historical examples due to Mills and Robbins, of hyperquadratic continued fractions with all partial quotients of degree one.

As often, the case of even characteristic appears to be singular. The simplest case, where the base field is F 2 , has been fully treated by Baum and Sweet in [BS2]. They could describe the set of all the continued fractions with partial quotients of degree one (i.e. equal to T or T + 1). Among them, certain are algebraic and for every even integer d ≥ 2 there is, in this set, an element algebraic of degree d. However, it was proved later that none of these algebraic elements (for d > 2) were hyperquadratic (see [L2, p. 225]). Later, in a joint work with Ruch we could exhibit hyperquadratic continued fractions in F(2 s ), with partial quotients all of the form λT where λ ∈ F 2 s (see [START_REF] Lasjaunias | Flat power series over a finite field[END_REF]p. 280], with r = 2 and also [START_REF] Lasjaunias | On a family of sequences defined recursively in F * q (II)[END_REF]p. 556]). Other examples were introduced by Thakur [T, p. 290]. Finally, we shall not omit the impressive note left by Robbins on arXiv [R], in which several conjectures on continued fractions for particular cubic power series in F(4) and F(8), with partial quotients of bounded degree, are presented.

Here we present a family of hyperquadratic (for each order t ≥ 1) continued fractions in F(2 s ) of the form α = [λ 1 T, λ 2 T, ...., λ n T, ...]. In the next section, we state a theorem showing how this sequence (λ n ) n≥1 in F * 2 s is defined recursively from an arbitrary number of initial values. Moreover, in a final remark, we make a comment on the poperties of this sequence. However, the main goal of this note is to show that this family has a common origin with another family of continued fractions in the case of odd characteristic, introduced earlier and fully studied in [START_REF] Lasjaunias | Hyperquadratic continued fractions in odd characteristic with partial quotients of degree one[END_REF]. Indeed, eventhough the case of characteristic 2 is simpler, it appears that the existence of both families is directly connected to a particular universal quadratic power series ω = [T, T, ..., T, ....] belonging to F(p) for all prime numbers p. Note that this element ω is actually the analogue, in the formal case, of the celebrated quadratic real number [1, 1, . . . , 1, . . . ] = (1 + √ 5)/2.

Results

Our method, to obtain the explicit continued fraction for certain hyperquadratic power series, has been introduced in [L3]. We shall also use the notation, concerning continued fractions and continuants, presented in [LY1, Section 2], to which the reader is invited to refer.

Let α be an irrational element in F(q) with α = [a 1 , . . . , a n , . . .] as its continued fraction expansion. We denote by F(q) + the subset of F(q) containing the elements having an integral part of positive degree (i.e. with deg(a 1 ) > 0). For all integers n ≥ 1, we put α n = [a n , a n+1 , . . .] (α 1 = α), called the n-th complete quotient. We introduce the usual continuants x n , y n ∈ F q [T ] such that x n /y n = [a 1 , a 2 , . . . , a n ] for n ≥ 1. As usual we extend the latter notation to n = 0 with x 0 = 1 and y 0 = 0. So, in the sequel, with our notation [LY1, p. 266], given a vector A = (a 1 , a 2 , . . . , a n ), the polynomials x n and y n are the continuants a 1 , a 2 , . . . , a n and a 2 , . . . , a n .

As above we set r = p t , where t ≥ 0 is an integer. Let P, Q ∈ F q [T ] such that deg(Q) < deg(P ) < r. Let ≥ 1 be an integer and A = (a 1 , a 2 , . . . , a ) a vector in (F q [T ]) such that deg(a i ) > 0 for 1 ≤ i ≤ . Then by Theorem 1 in [L3, p. 333], there exists an infinite continued fraction in F(q) defined by α = [a 1 , a 2 , . . . , a , α +1 ] such that α r = P α +1 + Q. We consider the four continuants x , y , x -1 and y -1 , in F q [T ], built from the vector A . Then, this element α is hyperquadratic and it is the unique root in F(q) + of the following algebraic equation:

y X r+1 -x X r + (y -1 P -y Q)X + x Q -x -1 P = 0.
(1)

A continued fraction defined as above will be called of type (r, , P, Q). Note that such a continued fraction is depending on the choice of the vector A = (a 1 , a 2 , . . . , a ) in (F q [T ]) . Now, let us introduce an important sequence of polynomials in F p [T ], for all prime numbers p (see [L3, p. 331]). This sequence (F n ) n≥0 is defined by induction as follows:

F 0 = 1, F 1 = T and F n+1 = T F n + F n-1 for n ≥ 1.
Note the similarity with the celebrated sequence of Fibonacci integers. With our notation, for n ≥ 1, we clearly have Note that ω is quadratic and satisfies ω = T + 1/ω. We have the following lemma. Lemma 1. Let p be a prime, the sequence (F n ) n≥0 in F p [T ] and ω ∈ F(p) be defined as above. As above, let r = p t where t ≥ 1 is an integer. Then we have

F n /F n-1 = [T,
F n-1 = (ω n -(-ω -1 ) n )/(ω + ω -1 ) for n ≥ 1. If p = 2 then F r-1 = T r-1 and if p > 2 then F r-1 = (T 2 + 4) (r-1)/2 .
Proof: For n ≥ 0, we set Ω n = ω n -(-ω -1 ) n . Then we have

T Ω n + Ω n-1 = ω n-1 (T ω + 1) -(-ω -1 ) n-1 (-T ω -1 + 1). ( 2
)
Since ω = T + ω -1 , we get ω 2 = T ω + 1 and ω -2 = -T ω -1 + 1. Hence (2) becomes

T Ω n + Ω n-1 = ω n+1 -(-ω -1 ) n+1 = Ω n+1 . (3)
Hence, by (3), the sequence (Ω n ) n≥0 satisfies the same recurrence as the sequence (F n ) n≥0 . We observe that Ω 1 /(ω + ω -1 ) = 1 = F 0 and Ω 2 /(ω + ω -1 ) = ω -ω -1 = T = F 1 . Since the sequences (F n ) n≥0 and (Ω n+1 /(ω + ω -1 )) n≥0 satisfy the same linear recurrence relation and are equal on the first two values, they coincide and we have F n-1 = Ω n /(ω + ω -1 ), for n ≥ 1, as stated in the lemma. If p = 2, using the Frobenius isomorphism, we have Ω r = (ω + ω -1 ) r and also ω + ω -1 = T . Therefore, we can write F r-1 = (ω + ω -1 ) r /(ω + ω -1 ) = (ω + ω -1 ) r-1 = T r-1 . If p > 2, again using the Frobenius isomorphism, we also have Ω r = (ω + ω -1 ) r . But here ω -ω -1 = T and (ω -ω -1 ) 2 + 4 = (ω + ω -1 ) 2 . Consequently, we get F r-1 = (ω + ω -1 ) r-1 = ((ω -ω -1 ) 2 + 4) (r-1)/2 = (T 2 + 4) (r-1)/2 . So the proof is complete.

It is easy to check that, for n ≥ 2, we have ω n = F n-1 ω +F n-2 . Since ω = ω l+1 for l ≥ 1, with our terminology, we observe that ω is a continued fraction of type (r, , F r-1 , F r-2 ), for all r = p t and ≥ 1. We are now interested in the family of continued fractions of type (r, , 1 F r-1 , 2 F r-2 ), for a pair ( 1 , 2 ) ∈ (F * q ) 2 . Besides ω, this family contains continued fractions with all partial quotients of degree one, hence the first partial quotients must be chosen as polynomial of degree 1 in F q [T ].

Note that, in the first works on hyperquadratic continued fractions with bounded partial quotients, the role played by the pair (F r-1 , F r-2 ) was not put in evidence. There are two distinct cases according to the characteristic p = 2 or p > 2. The case of characteristic p > 2 was the first to be considered. In [MR], Mills and Robbins described, in the case q = r = p > 3 , with = 2 and (a 1 , a 2 ) = (aT, bT ), a family of such examples (see also the introduction of [L3, p. 332]). However in that case, in general, the solution of (1) will not have all partial quotients of degree 1. This will happen if a mysterious condition, between the coefficients of the polynomials in A and the pair ( 1 , 2 ), is satisfied. It has been long and complicated to obtain this condition (see [START_REF] Lasjaunias | Hyperquadratic continued fractions in odd characteristic with partial quotients of degree one[END_REF] and particularly the first section for the background information on the matter). Here, we shall now only consider the case of characteristic 2. Due to the simpler form of F r-1 , given in the previous lemma, we will avoid the sophistication appearing in odd characteristic.

The following general lemma, on the continued fraction algorithm, is the basic tool of our method. It can be found in several articles (see [START_REF] Lasjaunias | Continued fractions for hyperquadratic power series over a finite field[END_REF]Lemma 3.1,p. 336] or [START_REF] Lasjaunias | Hyperquadratic continued fractions in odd characteristic with partial quotients of degree one[END_REF]p. 267]). Lemma 2. For n ≥ 2, given n + 1 variables x 1 , x 2 , . . . , x n and x, we have formally

[[x 1 , x 2 , . . . , x n ], x] = [x 1 , x 2 , . . . , x n , y],
where

y = (-1) n-1 x 2 , . . . , x n -2 x -x 2 , . . . , x n-1 x 2 , . . . , x n -1 .
As a consequence of Lemma 1 and Lemma 2, we have now the following lemma. Lemma 3. Let q = 2 s and r = 2 t where s, t ≥ 1 are integers. Let α = [a 1 , a 2 , . . . , a n , . . . ] be an infinite continued fraction in F(q). We assume that there is a pair ( 1 , 2 ) ∈ (F * q ) 2 and a pair of integers (i, j), where 1 ≤ i < j, such that we have

α r i = 1 F r-1 α j + 2 F r-2 . If a i = λ i T where λ i ∈ F *
q , then we have

a j = -1 1 λ r i T and a j+k = ( 2 / 1 ) (-1) k T for 1 ≤ k ≤ r -1 and also α r i+1 = 1 -2 2 F r-1 α j+r + -1 2 F r-2 . Proof: From the equality α r i = 1 F r-1 α j + 2 F r-2 , and since α r i = [a i , α i+1 ] r = [a r i , α r i+1 ], we obtain [ a r i + 2 F r-2 1 F r-1 , 1 F r-1 α r i+1 ] = α j . (4)
We denote by W i the word T, T, ...T , where T is repeated i times. We have

( 1 / 2 )F r-1 /F r-2 = ( 1 / 2 )[W r-1 ]. By Lemma 1, we have F r-1 = T r-1 , therefore (4) becomes [[ -1 1 λ r i T, ( 1 / 2 )[W r-1 ]], 1 F r-1 α r i+1 ] = [[ -1 1 λ r i T, x 2 , x 3 , . . . , x r ], 1 F r-1 α r i+1 ] = α j , (5)
where

x i = ( 1 / 2 ) (-1) i T for 2 ≤ i ≤ r.
We shall now apply Lemma 2. Using classical properties of continuants (see [START_REF] Lasjaunias | Hyperquadratic continued fractions in odd characteristic with partial quotients of degree one[END_REF]p. 266]), we can write

x 2 , . . . , x r = ( 1 / 2 )T, ( 2 / 1 )T, . . . , ( 1 / 2 )T = ( 1 / 2 ) T, T, . . . , T = ( 1 / 2 )F r-1
and also

x 2 , . . . , x r-1 = ( 1 / 2 )T, ( 2 / 1 )T, . . . , ( 2 / 1 )T = T, T, . . . , T = F r-2 .

We set x 1 = -1 1 λ r i T and x = 1 F r-1 α r i+1 . Thus, according to Lemma 2, we get

[[x 1 , x 2 , x 3 , . . . , x r ], x] = [x 1 , x 2 , . . . , x r , (( 1 / 2 )F r-1 ) -2 x + (( 1 / 2 )F r-1 ) -1 F r-2 ]. (6)
Combining ( 5) and ( 6), since x = 1 F r-1 α r i+1 , we obtain

α j = [x 1 , x 2 , . . . , x r , ( 2 2 / 1 )F -1 r-1 α r i+1 + ( 2 / 1 )F -1 r-1 F r-2 ] = [x 1 , x 2 , . . . , x r , y]. (7)
Since |α i+1 | > 1, we observe that |y| > 1. Comparing (7) to α j = [a j , a j+1 , . . . , a j+r-1 , α j+r ], we get a j = x 1 , a j+1 = x 2 , . . . a j+r-1 = x r and α j+r = y. With the values given to x i , for 1 ≤ i ≤ r -1, we obtain the values for the partial quotients from a j to a j+r-1 . Finally, with the value of y in (7), we obtain the last formula of the lemma. So the proof is complete.

We can now state and prove the following theorem. Theorem. Let q = 2 s and r = 2 t where s, t ≥ 1 are integers. Let ≥ 1 be an integer and the pair (F r-1 , F r-2 ) in (F 2 [T ]) 2 be defined as above. Let Λ +2 = (λ 1 , λ 2 , . . . , λ , 1 , 2 ) be given in (F * q ) +2 . Let x , y , x -1 and y -1 be the four continuants, in F q [T ], built from the vector A = (λ 1 T, λ 2 T, . . . , λ T ). We consider the following algebraic equation

y X r+1 + x X r + ( 1 y -1 F r-1 + 2 y F r-2 )X + 2 x F r-2 + 1 x -1 F r-1 = 0. (E)
Then (E) has a unique root α in F(q) + and we have α = [λ 1 T, λ 2 T, . . . , λ T, . . . , λ n T, . . . ]. The sequence (λ n ) n≥1 in F * q is defined recursively, from the vector Λ +2 , as follows :

λ +rm+1 = ( 2 / 1 ) (-1) m+1 2
λ r m+1 and λ +rm+i = ( 1 / 2 ) (-1) i for m ≥ 0 and 2 ≤ i ≤ r.

Proof: We observe that (E) is simply equation (1), stated above, built from the vector A = (λ 1 T, λ 2 T, . . . , λ T ) and the pair (P, Q) = ( 1 F r-1 , 2 F r-2 ). According to the theorem from [L3], mentioned before, we know that (E) has a unique root α in F(q) + . This element is the infinite continued fraction defined by α = [λ 1 T, λ 2 T, . . . , λ T, α +1 ] and α r = 1 F r-1 α +1 + 2 F r-2 . Since a 1 = λ 1 T , we can apply Lemma 3, with i = 1 and j = + 1. Hence, we get

a +1 = -1 1 λ r 1 T and a +i = ( 1 / 2 ) (-1) i T for 2 ≤ i ≤ r. (8)
We also have

α r 2 = 1 -2 2 F r-1 α +r+1 + -1 2 F r-2 .
Let us consider the application f from (F * q ) 2 into (F * q ) 2 , defined by f (x, y) = (xy -2 , y -1 ). We observe that f is an involution. Hence, we can apply again Lemma 3 (note that a 2 = λ 2 T even if = 1), replacing (i, j) by (2, l + r + 1) and the pair ( 1 , 2 ) by the pair f ( 1 , 2 ). We obtain

a +r+1 = 2 2 -1 1 λ r 2 T and a +r+i = ( 1 / 2 ) (-1) i T for 2 ≤ i ≤ r (9) and α r 3 = 1 F r-1 α +r+1 + 2 F r-2 .
Hence, by repeated application of this lemma, we see that

a i = λ i T for i ≥ 1. Note that ( 2 / 1 ) (-1) m+1 2 is either -1 1 or 2 2 -1
1 , according to the parity of the integer m ≥ 0. From ( 8) and ( 9), we get the formulas defining the sequence (λ n ) n≥1 in F * q , stated in the theorem. So the proof is complete.

Remark. In a recent joined work with J-Y. Yao [START_REF] Lasjaunias | Hyperquadratic continued fractions and automatic sequences[END_REF], we have observed that the sequence of the leading coefficients of the partial quotients for an hyperquadratic continued fraction could be an automatic sequence. Naturally, the question arises for the sequence described in this theorem. In the particular case r = 2, with the terminology introduced above, we note that the element α is of type (2, , 1 T, 2 ). Indeed, we have proved in [START_REF] Lasjaunias | Hyperquadratic continued fractions and automatic sequences[END_REF]Theorem 3] that the corresponding sequence is 2-automatic. Let us indicate another criterion for a sequence in F q to be automatic (see [AS,p. 356]) : (λ n ) n≥1 in F q is p-automatic if the power series i≥1 λ i T -i ∈ F(q) is algebraic over F q (T ). Concerning the sequence (λ n ) n≥1 described in our theorem, we conjecture the following : Set θ = i≥1 λ i T -i ∈ F(q), then there exist two elements A and B in F q (T ), depending on r and on the vector Λ +2 , such that we have θ r + Aθ + B = 0. Accordingly, by the criterion cited, the conjecture would imply the 2-automaticity of the sequence (λ n ) n≥1 for all r = 2 t and t ≥ 1. This conjecture is based on a partial study of the sequence (λ n ) n≥1 . Indeed, in the simplest case r = 2, the conjecture is true and this study was complete enough to allow us to obtain the following :

θ = i=1 λ i T -i + ( 1 / 2 )T -(T + 1) -2 ( (-1) 2 T + 1) + ( 1 / 2 ) (-1) 2
T -1 ρ and

ρ 2 + ρ + T -2 i=1 (1 + λ 2 i ( 2 / 1 ) 2 (-1) i -(-1)
2

)T -2i+2 = 0.

  T, . . . , T ] and F n = T, T, . . . , T , where the finite sequence of T has length n. Then we define in F(p) the following infinite continued fraction ω = [T, T, . . . , T, . . . ] = lim n→∞ F n /F n-1 .


F Colombini

Guy Métivier

Counterexamples to the well posedness of the Cauchy problem for hyperbolic systems

This paper is concerned with the well posedness of the Cauchy problem for first order symmetric hyperbolic systems in the sense of Friedrichs. The classical theory says that if the coefficients of the system and if the coefficients of the symmetrizer are Lipschitz continuous, then the Cauchy problem is well posed in L 2 . When the symmetrizer is Log-Lipschtiz or when the coefficients are analytic or quasi-analytic, the Cauchy problem is well posed C ∞ . In this paper we give counterexamples which show that these results are sharp. We discuss both the smoothness of the symmetrizer and of the coefficients.

Introduction

This paper is concerned with the well posedness of the Cauchy problem for first order symmetric hyperbolic systems in the sense of Friedrichs [START_REF] Friedrichs | Symmetric hyperbolic linear differential equations[END_REF], who proved that if the coefficients of the system and if the coefficients of the symmetrizer are Lipschitz continuous, then the Cauchy problem is well posed in L 2 . This has been extended to hyperbolic systems which admits Lipschitzean microlocal symmetrizers (see [Me]).

The main objective of this paper is to discuss the necessity of these smoothness assumptions and to provide new counterexamples to the well posedness. In the spirit of [START_REF] Colombini | Some Examples of Hyperbolic Equations without Local Solvability[END_REF][START_REF] Colombini | Two by two strongly hyperbolic systems and Gevrey classes[END_REF], we make a detailed analysis of systems in space dimension one, with coefficients which depend only on time. Even more, we concentrate our analysis on 2 × 2 system (1.1)

Lu := ∂ t u + a(t) b(t) c(t) d(t) ∂ x u = ∂ t u + A(t)u.
The symbol is assumed to be strongly hyperbolic or uniformly diagonalizabe, which means that there is a bounded symmetrizer S(t), with S -1 is bounded, which is a definite positive and such that S(t)A(t) is symmetric. This is equivalent to the condition that there is δ > 0 such that

(1.2) δ (a -d) 2 + b 2 + c 2 ≤ 1 4 (a -d) 2 + bc.
If the symmetrizer S and the coefficients are Lipschitz continuous then the Cauchy problem is well posed in L 2 . Indeed, in this case, solutions on

[0, T ] × R of Lu = f satisfy (1.3) u(t) L 2 ≤ C u(0) L 2 + Lu L 2 with C = C 0 exp T 0 |∂ t S(s)|ds .
Lipschitz smoothness of the symmetrizer is almost necessary for the well posedness in L 2 , even for very smooth coefficients: Theorem 1.1. For all modulus of continuity ω such that t -1 ω(t) → +∞ as t → 0, there is a system (1.1) with coefficients in ∩ s>1 G s ([0, T ]), with a symmetrizer satisfying

(1.4) S(t) -S(t ) ≤ Cω(|t -t |)
such that the Cauchy problem is ill posed in L 2 in the sense that there is no constant C such that the estimate (1.3) is satisfied.

Here and below, we denote by G s ([0, T ]] the Gevrey class of functions of order s. They are C ∞ functions f such that, for some constant C which depends on f , there holds

∀j ∈ N, ∂ j t f L ∞ ≤ C j+1 (j!) s .
This theorem extends to systems a similar result obtained in [CiCo] for the strictly hyperbolic wave equation

(1.5) ∂ 2 t u -a(t)∂ 2 x u = f.
Indeed, there is a close parallel between the energy |∂ t u| 2 +a(t)|∂ x u| 2 for the wave equation and (S(t)u, u) for the system, and in this case, the smoothness of S(t) plays a role analogue to the smoothness of a. For the wave equation, when a is Log-Lipschitz, i.e. admits the modulus of continuity ω(t) = t| ln t|, the Cauchy problem is well posed in C ∞ with a loss of derivatives proportional to time ( [CDGS]). An intermediate cases between Lipschitz and Log-Lipschitz, that is when (t| ln t|) -1 ω(t) → 0 and t -1 ω(t) → +∞, then the loss of derivative is effective but is arbitrarily small on any interval ( [CiCo]). The proof of these results extends immediately to systems (1.1) where the smoothness of the symmetrizer plays the role of the smoothness of the coefficient a.

The next result extends to systems the result in [START_REF] Colombini | Sur les équations hyperboliques avec des coefficients qui ne dépendent que du temps[END_REF][START_REF] Colombini | Some Examples of Hyperbolic Equations without Local Solvability[END_REF] showing that the Log-Lipschitz smoothness of the symmetrizer is a sharp condition for the well posedness in C ∞ , even for C ∞ coefficients: Theorem 1.2. For all modulus of continuity ω satisfying (t| ln t|) -1 ω(t) → +∞ as t → 0, there are systems (1.1), with C ∞ coefficients, with symmetrizers which satisfy the estimate (1.4) such that the Cauchy problem is ill posed in C ∞ , meaning that for all n and all T > 0, there is no constant C such that the estimate

(1.6) u L 2 ≤ C Lu H n is satisfied for all u ∈ C ∞ 0 ([0, T ] × R).
In [CoNi] the question of the well posedness of the Cauchy problem is considered under the angle of the smoothness of the coefficients alone. In this aspect, the analysis is related to the analysis of the weakly hyperbolic wave equation (1.5) (see citeCJS). If the coefficients are C ∞ , the problem is well posed in all Gevrey classes G s , but the well posedness in C ∞ is obtained only when the coefficients are analytic or belong to a quasi-analytic class. Indeed, the next theorem shows that this is sharp.

Theorem 1.3. There are example of systems (1.1) on [0, T ] × R, with uniformly hyperbolic symbols and coefficients in the intersection of the Gevrey classes ∩G s for s > 1, admitting continuous symmetrizers, such that the Cauchy problem is ill posed in C ∞ . This theorem improves the similar result obtained in [CoNi] where the counterexample had coefficients in ∩G s for s > 2. The same construction can be used to provide a similar improvement to the known result in [START_REF] Colombini | An example of a weakly hyperbolic Cauchy problem not well posed in C ∞[END_REF] for the wave equation:

Theorem 1.4. There are nonnegative functions a ∈ ∩ s>1 G s ([0, T ]), such that the Cauchy problem for the weakly hyperbolic wave equation

(1.5) is ill posed in C ∞ .
The theorems above show that the smoothness of both the coefficients and the symmetrizer play a role in the well posedness in C ∞ . The next theorem is a kind of interpolation between the two extreme cases of Theorem 1.2 and Theorem 1.3: Theorem 1.5. For all s > 1 and µ < 1 -1/s, there are example of systems (1.1) on [0, T ] × R, with uniformly hyperbolic symbols, coefficients in the Gevrey classes G s , symmetrizer in the Hölder space C µ , and such that the

Cauchy problem is ill posed in C ∞ .
This leaves open the question of the well posedness in C ∞ when the coefficients belong to G s and the symmetrizer to C µ when µ + 1/s ≥ 1.

We end this introduction by several remarks about symmetrizers or 2×2 system (1.1). For simplicity, we assume that the coefficients are real. Write

A(t) = 1 2 trA(t)Id + A 1 (t). Then A 2 1 = hId with h = 1 4 (a -d) 2 + bc satisfying (1.2). In particular, Σ(t) = A * 1 (t)A 1 (t) + h(t)Id
is a symmetrizer for A in the sense that Σ and ΣA = 1 2 (trA)Σ + hA * 1 + hA 1 are symmetric. In general, Σ is not a symmetrizer in the sense of Friedrichs, since it is not uniformly positive definite, unless h > 0, which means that the system is strictly hyperbolic. More precisely, Σ ≈ hId. But Σ has the same smoothness as the coefficients of A.

On the other hand, since the system is uniformly diagonalizable, there are bounded symmetrizers Σ 1 (t) which are uniformly positive definite. For instance h -1 Σ is a bounded symmetrizer. More generally, writing

(1.7) 1 2 (a -d) = h 1 2 a 1 , b = b 1 h 1 2 , c = c 1 h 1 2 , one has a 2 1 + b 1 c 1 ≥ δ(a 2 1 + b 2 1 + c 2 1
) ≥ δ > 0 and the symmetrizer are of the form

(1.8) Σ 1 = α β β γ with 2a 1 β = b 1 α -c 1 γ.
Therefore there is a cone of positive symmetrizers of dimension 2. Their smoothness depend on the smoothness of

a 1 , b 1 , c 1 , that is of h -1 2 A 1 .
There might be better choices than others. For instance, if the system is symmetric, Σ 1 = Id is a very smooth symmetrizer. Our discussion below concerns the smoothness of both Σ and Σ 1 and their possible interplay.

The counterexamples

We consider systems of the form (2.1)

LU := ∂ t U + 0 a(t) b(t) 0 ∂ x U.
with a and b real. We always assume that it is uniformly strongly hyperbolic, that is that σ = a/b > 0 and 1/σ are bounded. Our goal is to contradict the estimates (1.3) and (1.6). We contradict the analogous estimates which are obtained by Fourier transform in x, and more precisely, we construct sequences of functions

u k , v k and f k in C ∞ ([0, T ]), vanishing near t = 0, satisfying (2.2) ∂ t u k + ih k a(t)v k = f k , ∂ t v k + ih k b(t)u k = 0 with h k → +∞ and such that (2.3) f k L 2 / (u k , v k ) L 2 → 0 as k → ∞
in the first case or, for all j and l ,

(2.4)

h j k ∂ l t f k L 2 / (u k , v k ) L 2 → 0 as k → ∞
in the second case. Moreover, the support of these function is contained in an interval

I k = [t k , t k ] with 0 < t k < t k and t k → 0,
showing that the problem is ill posed on any interval [0, T ] with T > 0.

Exponentially amplified solutions of the wave equation

In this section we review and adapt the construction of [START_REF] Colombini | Some Examples of Hyperbolic Equations without Local Solvability[END_REF]. The key remark is that the function w ε (t) = e -εφ(t) cos t satisfies (2.5)

∂ 2 t w ε + α ε w ε = 0 if (2.6) φ(t) = t 0 (cos s) 2 ds, α ε (t) = 1 + 2ε sin 2t -ε 2 (cos t) 4 .
The important property of the w ε is their exponential decay at +∞. More precisely e 1 2 εt w ε (t) = e 1 4 ε sin 2t cos t is 2πperiodic and

(2.7) w ε (t + 2π) = e -επ w ε (t).

Next, one symmetrizes and localizes this solution. More precisely, consider χ ∈ C ∞ (R), supported in ] -7π, 7π[, odd, equal to 1 on [-6π, -2π] and thus equal to -1 on [2π, 6π], and such that for all t, 0 ≤ χ(t) ≤ 1 and

|∂ t χ(t)| ≤ 1. For ν ∈ N, let (2.8) Φ ν (t) = t 0 χ ν (s)(cos s) 2 ds, χ ν (t) = χ(t/ν).
For ε > 0, w ε,ν (t) = e εΦν (t) cos t satisfies (2.9)

∂ 2 t w ε,ν + α ε,ν w ε,ν = 0 where (2.10) α ε,ν (t) = 1 + εχ ν sin 2t -εΦ ν -(εΦ ν ) 2 = 1 + 2εχ ν sin 2t -εχ ν (cos t) 2 -ε 2 χ 2 ν (cos t) 4 .
For ε ≤ ε 0 = 1/10 and for all ν

(2.11) |α ε,ν -1| ≤ 1 2
and we always assume below that the condition ε ≤ ε 0 is satisfied. We note also that α ε,ν = 1 for |t| ≥ 7νπ since χ ν vanishes there. The final step is to localize the solution in [-6νπ, 6νπ]. Introduce an odd cut off function ζ(t) supported in ] -6π, 6π[ and equal to 1 for |t| ≤ 4π and let

(2.12) wε,ν (t) = ζ(t/ν)w ε,ν (t).
It is supported in [-6νπ, 6νπ] and equal to w ε,ν on [-4νπ, 4νπ]. Then

(2.13)

f ε,ν = ∂ 2 t wε,ν + α ε,ν wε,ν = 2ν -1 ζ (t/ν)∂ t w ε,ν + ν -2 ζ (t/ν)w ε,ν is supported in [-6νπ, -4νπ] ∪ [4νπ, 6νπ].
Lemma 2.1. For all j, there is a constant C j such that for all ε ≤ ε 0 and all ν ≥ 1

(2.14)

∂ j t f ε,ν L 2 ≤ C j ν -1 e -ενπ wε,ν L 2 .
Proof. By symmetry, it is sufficient to estimate f ε,ν for t ≥ 0, that is on [4νπ, 6νπ]. On [2νπ, 6νπ], χ ν = -1, hence Φ ν -φ is constant and 2νπ) .

w ε,ν (t) = c ν,ε w ε (t), c ν,ε = e εΦν (
Moreover, on this interval α ε,ν = α ε is bounded with derivatives bounded independently of ε , and hence

∂ j t f ε,ν L 2 ≤ C j ν -1 c ν,ε (w ε , ∂ t w ε ) L 2 ([4νπ,6νπ]) .
By (2.7), this implies

∂ j t f ε,ν L 2 ≤ C j ν -1 c ν,ε e -ενπ (w ε , ∂ t w ε ) L 2 ([2νπ,4νπ]) .
On the other hand

w ε,ν L 2 ≥ c ν,ε w ε L 2 ([2νπ,4νπ]) .
Therefore it is sufficient to prove that there is a constant C such that for all ν and ε:

(w ε , ∂ t w ε ) L 2 ([2νπ,4νπ]) ≤ C w ε L 2 ([2νπ,4νπ]) .
Using again (2.7), one has

(w ε , ∂ t w ε ) 2 L 2 ([2νπ,4νπ]) = ν-1 k=0 e -2(εk+ν)π (w ε , ∂ t w ε ) 2 L 2 ([0,2π])
and

w ε 2 L 2 ([2νπ,4νπ]) = ν-1 k=0 e -2(εk+ν)π w ε 2 L 2 ([0,2π]) .
On [0, 2π] the H 1 norm of the w ε are uniformly bounded while their L 2 norm remain larger than a positive constant.

Construction of the coefficients and of the solutions

For k ≥ 1, let ρ k = k -2 . We consider intervals I k = [t k , t k ] and J k = [t k , t k-1 ] of the same length ρ k = t k -t t = t k -1 -t k , starting at t 0 = 2 ∞ k=1 ρ k , and thus such that t k → 0.
The functions a and b are defined on ]0, t 0 ] as follows: we fix a function β ∈ C ∞ (R) supported in ]0, 1[ and with sequences ε k , ν k and δ k to be chosen later on, (2.15) on I k :

a(t) = δ k α ε k ,ν k -8πν k + 16π(t -t k )ν k /ρ k , b(t) = δ k on J k : a(t) = b(t) = δ k + (δ k-1 -δ k )β (t -t k )/ρ k .
Because α ε,ν = 1 for |t| ≥ 7νπ, the coefficient a = δ k near the end points of I k . The use of the function β on J k makes a smooth transition between δ k and δ k-1 . Therefore, a and b are C ∞ on ]0, t 0 ]. The coefficients will be chosen so that they extend smoothly up to t = 0. This is quite similar to the choice in [CoNi], except that we introduce a new sequence ε k , which is crucial to control the Hölder continuity of σ = a/b.

We use the family (2.12) to construct solutions of the system supported in I k , for k large. On I k , b is constant and the equation (2.2) reads (2.16)

∂ t u k + ih k δ k α k v k = f k , ∂ t v k + ih k δ k u k = 0, with α k (t) = α ε k ,ν k -8πν k + 16π(t -t k )ν k /ρ k . Therefore, a C ∞ solution of (2.2) supported in I k is (2.17) u k (t) = i∂ t wε k ,ν k -8πν k + 16π(t -t k )ν k /ρ k v k (t) = wε k ,ν k -8πν k + 16π(t -t k )ν k /ρ k with (2.18) f k (t) = 16iπ(ν k /ρ k )f ε k ,ν k -8πν k + 16π(t -t k )ν k /ρ k provided that (2.19) h k = 16πν k /ρ k δ k .

Properties of the coefficients

We always assume that

(3.1) ε k ≤ ε 0 , ε k ν k → +∞, δ k → 0.

Conditions for blow up

Lemma 3.1.

If (3.2) (ρ k ) -1 e -ε k ν k π → 0,
then the blow up property in L 2 (2.3) is satisfied.

Proof. By Lemma 2.1

f k L 2 ≤ Cρ -1 k e -ε k ν k π v k L 2 . Lemma 3.2. If (3.3) 1 ε k ν k ln(h k ν k /ρ k ) → 0, then the blow up property in C ∞ (2.4) is satisfied.
Proof. By Lemma 2.1 one has

∂ l t h j k f k L 2 / (u k , v k ) L 2 ≤ C l ν -1 k h j k (16πν k /ρ k ) l+1 e -ε k ν k π .
This tends to 0 if

ε k ν k π -j ln h k -(l + 1) ln(ν k /ρ k ) → +∞. If (3.
3) is satisfied, this is true for all j and l.

Smoothness of the coefficients

Lemma 3.3.

If (3.4) ln(ν k /ρ k )/| ln(δ k ε k )| → 0
then the functions a and b are C ∞ up to t = 0.

Proof. a and b are O(δ k ) and thus converge to 0 when t → 0. Moreover, for j ≥ 1,

|∂ j t a| ≤ C j δ k ε k (ν k /ρ k ) j on I k , δ k ρ -j k on J k .
The worst situation occurs on I k and the right hand side is bounded if

j ln(ν k /ρ k ) -| ln(δ k ε k )|
is bounded from above. This is true for all j under the assumtion (3.4), implying that a is C ∞ on [0, t 0 ]. The proof for b is similar and easier.

Next, we investigate the possible Gevrey regularity of the coefficients. For that we need make a special choice of the cut-off functions χ and β which occur in the construction of a and b. We can choose them in a class contained in ∩ s>1 G s and containing compactly supported function, (see e.g. [Ma]). We choose them such that there is a constant C such that for all j

(3.5) sup t ∂ j t χ(t) + ∂ j t β(t) ≤ C j+1 j!(ln j) 2j . Lemma 3.4. If (3.5) is satisfied, then for j ≥ 1 (3.6) sup t∈I k ∪J k ∂ j t a(t) + ∂ j t b(t) ≤ K j+1 δ k ε k (ν k /ρ k )) j + (1/ρ k ) j j!(ln j) 2j .
Proof. On I k we take advantage of the explicit form (2.10) of α ε,ν : it is a finite sum of sin and cos with coefficients of the form χ(t/ν). Scaled on I k , each derivative of the trigonometric functions yields a factor ν k /ρ k , while the derivatives of χ ν k have only a factor 1/ρ k . Since χ and χ 2 satisfy estimates similar to (3.5), we conclude that a satisfies

∂ j t a(t) ≤ ε k δ k K j l≤j (ν k /ρ k ) j-l C l+1 l!(ln l) 2l
implying the estimate (3.6) on I k . On I k , b is constant. On J k things are clear by scaling since the coefficients are functions of β((t -t k )/ρ k ).

To estimate quantities such as δ k (ν k /ρ k ) j we use the following inequalities for a > 0 and x ≥ 1 (3.7) e -x x a ≤ a a and (3.8) e -e x x a ≤ | ln a| a when a ≥ e 1 when a ≤ e.

Corollary 3.5. Suppose that δ k = e -η k and that for s > s > 1

(3.9) (ν k /ρ k ) ≤ Cη s k , (1/ρ k ) j ≤ Cη s -1 k .
Then the coefficients belong to the Gevrey class G s . If for some p > 0 and q > 0,

(3.10) η k ≥ e k q , (ν k /ρ k ) ≤ Ck p η k then the coefficients belong to ∩ s>1 G s .
Proof. We neglect ε k and only use the bound ε k ≤ ε 0 . In the first case, we obtain from (3.7) that

δ k (ν k /ρ k ) j ≤ e -η k (Cη k ) sj ≤ (C j) js , δ k (1/ρ k ) j ≤ (C j) j(s -1)
implying that |∂ j t (a, b)| ≤ K j+1 j sj . In the second case, combining (3.7) and (3.8)

e -η k (ν k /ρ k ) j ≤ C j j j k pj e -1 2 η k ≤ C j j j (1 + ln j) pj/q .
Using again (3.8) for the second term, we obtain that

|∂ j t (a, b)| ≤ K j+1 j j (ln j) rj
with r = max{p, 4}/q. In particular, the right hand side is estimated by K k+1 s j js for all s > 1, proving that the functions a and b belong to ∩ s>1 G s .

Smoothness of the symmetrizer

Lemma 3.6. Suppose that ω is a continuous and increasing function on

[0, 1] such that t -1 ω(t) is decreasing. If (3.11) ε k ≤ ω(ρ k /ν k ) then σ = a/b satisfies (3.12) σ(t) -σ(t ) ≤ Cω(|t -t |).
In particular, if µ ≤ 1 and

(3.13) lim sup k ε k (ν k /ρ k ) µ < +∞ then σ is Hölder continuous of exponent µ. If (3.14) ε k (ν k /ρ k ) ≤ C ln(ν k /ρ k ) θ
then ω(t) = t| ln t| θ is a modulus of continuity for σ.

Proof. On J k , σ = σ -1 vanishes and on

I k σ = ε k α ε k ,ν k (-8πν k + 16π(t -t k )ν k /ρ k ),
and thus

(3.15) |σ| ≤ Cε k , |∂ t σ| ≤ Cε k ν k /ρ k .
Hence, for t and

t in I k , σ(t) -σ(t ) ≤ Cε k min{1, |t -t |ν k /ρ k }. If ρ k /ν k ≤ |t -t | we use the first estimate and σ(t) -σ(t ) ≤ Cε k ≤ Cω(ρ k /ν k ) ≤ Cω(|t -t |).
If |t-t | ≤ ρ k /ν k we use the second estimate and the monotonicity of t -1 ω(t)

σ(t) -σ(t ) ≤ Cε k (ν k /ρ k )|t -t | ≤ C(ν k /ρ k )ω(ρ k /ν k )|t -t | ≤ Cω(|t -t |).
This shows that (3.12) is satisfied when t and t belong to the same interval I k . If t belong to I k and t ∈ J k , then σ(t ) = σ(t k ) = 0 and

|σ(t) -σ(t )| ≤ Cω(|t -t k |) ≤ Cω(|t -t |).
Similarly, if t < t and t and t do not belong to the same I k ∪ J k , there are end points t j and t l such that t j ≤ t ≤ t j-1 ≤ t l ≤ t ≤ t l-1 . Since σ vanishes at the endpoints of I k and on J k ,

|σ(t) -σ(t )| ≤ C|σ(t) -σ(t j )| + |σ(t) -σ(t j )| ≤ Cω(|t -t j-1 ) + Cω(|t l -t |) ≤ Cω(|t -t |)
and the lemma is proved.

Proof of the theorems

We now adapt the choice of the the parameters ε k , ν k and δ k so that the coefficients and the symmetrizer satisfy the properties stated in the different theorems. We will choose two increasing functions, f and g, on {x ≥ 1} and define ε k and δ k in terms of ν k through the relations:

(4.1) ε k ν k /ρ k = f (ν k /ρ k ), δ k = e -η k , η k = g(ν k /ρ k ).
Recall that ρ k = k -2 . The sequence of integers ν k will be chosen to converge to +∞ and thus ν k /ρ k → +∞. The conditions (3.1) are satisfied if at +∞:

(4.2) f (x) x, g(x) → +∞.
Here φ(x) ψ(x) means that ψ(x)/φ(x) → ∞. In particular, the first condition implies that ε k → 0 so that the condition ε ≤ ε 0 is certainly satisfied if k is large enough.

One has

| ln(δ k ε k )| = η k + ln(ν k /ρ k ) + ln f (ν k /ρ k )
Hence, by Lemma 3.3, the coefficients a and b are C ∞ when (4.3) ln x g(x)

x.

since with (4.

2) it implies that | ln(δ k ε k )| ∼ η k ln(ν k /ρ k ).

Proof of Theorem 1.1

Given the modulus of continuity ω, we choose f (x) = xω(x -1 ). The assumption on ω is that f is increasing and f (x) → +∞ at infinity. The spirit of the theorem is that f can grow to infinity as slowly as one wants. Lemma 3.6 implies that ω is a modulus of continuity for σ = a/b. By Lemma 3.1, the blow up property (2.3) occurs when

k 2 e -k -2 f (k 2 ν k )π → 0. This condition is satisfied if ν k satisfies (4.4) f (k 2 ν k ) ≥ k 3 , Let f 1 (x) = min{f (x), ln x}. We choose g(x) = x/f 1 (x) and ν k such that 2k 3 ≤ f 1 (k 2 ν k ) ≤ 4k 3 .
Note that this implies (4.4). We show that the conditions (3.10) are satisfied with p = q = 3 and C = 4 and a suitable choice of ν k , so that by Corollary 3.5 the coefficients belong to ∩ s>1 G s and the theorem is proved. Indeed, since f 1 (k 2 ν k ) ≤ 4k 3 , the condition ν k /ρ k ≤ 4k 3 η k is satisfied. Moreover, since ln(k 2 ν k ) ≥ 2k 3 , ν k ≥ k -2 e 2k 3 ≥ e k 3 . for k large.

Proof of Theorem 1.2

The proof is similar. Given the modulus of continuity ω, we choose f (x) = xω(x -1 ). The assumption on ω is now that (4.5) ln x f (x).

The spirit of the theorem is now that f (x)/ ln x can grow to infinity as slowly as one wants. By Lemma 3.6, ω is a modulus of continuity for σ = a/b. By Lemma 3.2, the blow up property (2.4) is satisfied if

ln h k = η k + ln(ν k /ρ k ) + ln(16π) ε k ν k that is if (4.6) ρ k f (ν k /ρ k ) g(ν k /ρ k ) + ln(ν k /ρ k ).
Let ψ(x) = f (x)/ ln x and g(x) = ψ(x) ln x. Then ψ(x) 1, ln x g(x) f (x).

Therefore, the condition (4.6) is satisfied when ρ k √ ψ(ν k /ρ k ) → +∞ and for that it is sufficient to choose ν k such that (4.7) ψ(k 2 ν k ) ≥ k 5 .

The condition g(x) ln x implies that the coefficients are C ∞ and the theorem is proved. By Corollary 3.5, to finish the proof of Theorem 1.3, is is sufficient to show that one can choose ν k satisfying (4.10) and such that ν k /ρ k ≤ 4k 6 η k . This condition reads ln(k 2 ν k ) ≤ 2k 3 , or ν k ≤ k -2 e 2k 3 which is compatible with (4.10) if k is large enough.

Proof of Theorem 1.4

Let a ∈ ∩ s>1 G s denote the coefficient constructed for the proof of Theorem (1.3). The definition (2.15) shows that a ≥ 0 and indeed a > 0 for t > 0. The functions v k defined at (2.17) are supported in I k and are solutions of the wave equation (1.5) with source term f k and we have shown that

h j k ∂ l t f k L 2 / v k L 2 → 0 as k → ∞.

  amplified solutions of the wave equation . . . . 2.2 Construction of the coefficients and of the solutions . . . . . . 3 Properties of the coefficients 3.1 Conditions for blow up . . . . . . . . . . . . . . . . . . . . . 3.2 Smoothness of the coefficients . . . . . . . . . . . . . . . . . . 3.3 Smoothness of the symmetrizer . . . . . . . . . . . . . . . . .

Proof of Theorem 1.5

With s > 1 and 0 < µ < 1 -1/s, we choose (4.8)

The choice of f implies that σ = a/b ∈ C µ . The choice of g implies that

In this case, Corollary 3.5 implies that the coefficients a and b belong to the Gevrey class G s . The blow up property (2.4) is satisfied when (4.6) holds, that is when

Therefore, if ν k ≥ k 2 max{p,q} , the system satisfies the conclusions of Theorem 1.5.

Proof of Theorem 1.3

The analysis above shows that if one looks for coefficients in ∩ s>1 G s , one must choose g and thus f , close to x. We choose here

Since f (x)/x → 0 at infinity, the symmetrizer is continuous up to t = 0 but in no C µ for all µ > 0.

The ill posedness in C ∞ is again garantied by the condition (4.6), that is ln(k 2 ν k ) k 2 . In particular, it is satisfied when (4.10) ν k ≥ e k 3 .