Jérémy Belot

Abdelkarim Cherkaoui

Raphaël Laurent

Laurent Fesquet

An Area and Power Efficient Stochastic Number Generator for Bayesian Sensor Fusion Circuits

In recent years, stochastic computing became popular in Bayesian circuits implementation because it enables compact and low power architectures. These architectures use Stochastic Number Generators (SNGs) that encode data in random bit-streams. SNGs are composed of Random Number Generators (RNGs) which contribute significantly to the circuit area and power consumption: according to our measurements, up to 29% of the area and 85% of the circuit power consumption, excluding memories. In this paper, we compare SNG implementations in terms of accuracy, area and power consumption. Furthermore, we propose a new SNG architecture that uses a single RNG for the whole design in order to generate the required stochastic bit-streams. The proposed architecture allows to save up to 11% of area and 58% of power consumption compared to the state of the art, with no significant accuracy loss.

I. INTRODUCTION

In the last few years, the advent of the IoT (Internet of Things) and the need for low-power integrated circuits sparked the interest in new computing paradigms. In many applications, such as autonomous systems powered by a battery, computing speed is a secondary requirement compared to energy efficiency. One of the approaches for designing such low-power circuits, called Stochastic Computing, is a non-standard computing method that encodes data using the probability of the bits at '1' occurring in a random bitstream. This approach was proposed more than 50 years ago [START_REF] Gaines | Stochastic computing[END_REF]. Although it was quickly abandoned in favor of a faster classical binary representation, this approach regained interest due to the increase of power and surface constraints for applications where speed is not of primary importance.

Its principle is to encode data in a stochastic bit-stream where the encoded value is related to the ratio r between the number of zeros and ones in the bit-stream. For the unipolar stochastic representation, the encoded value corresponds directly to this ratio r. This approach is particularly interesting in that it only requires a small amount of logic resources to process computations which are demanding in standard representation, such as multiplication. Indeed, if we consider two independent unipolar stochastic bit-streams, the multiplication of their encoded values is done by a simple 2input AND gate. For example, let s 0 = 0101100100100011 and s 1 = 0110110010111001 be two unipolar stochastic bitstreams, respectively having the values P (s 0 ) = 7/16 and P (s 1 ) = 9/16. Their AND gated bit-stream is s 0 ∧ s 1 = 0100100000100001 and P (s 0 ∧ s 1 ) = 4/16 63/256.

Apart from area reduction, other advantages of the stochastic representation are an increased robustness (bit flips have a lower impact on the encoded value than in base-2 representation) and progressive precision (the longer is the bit-stream, the higher is the precision). On the one hand, the increased robustness allows to reduce the circuit voltage, which reduces its power consumption. On the other hand, precision can be adapted dynamically without major hardware modification. This can be exploited for reducing the power consumption by doing a fast evaluation with low energy when the application allows it.

In recent years, architectures based on stochastic computing have been successfully used to implement Bayesian inference in sensor fusion models and temporal filters [START_REF] Faix | Cognitive computation: a bayesian machine case study[END_REF]. Such circuits use Stochastic Number Generators (SNGs) to encode probability values in stochastic bit-streams. These SNGs are critical in the implementation of stochastic circuits: their bitstreams must be pairwise independent as well as non biased in order to maximize the computation precision for a given bit-stream length. Moreover, their contribution to the circuit power consumption and area is significant and a number of previous works have focused on reducing their impact on the circuit with methods sharing common resources [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF]- [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF].

In this paper, we consider a Bayesian sensor fusion problem implemented in a dedicated stochastic circuit [START_REF] Coninx | Bayesian sensor fusion with fast and low power stochastic circuits[END_REF], for which we compare, in terms of area, power consumption, and computation accuracy different SNG implementations sharing hardware resources. We introduce a new solution of Random Number Generator (RNG) sharing over a large amount of stochastic bit-streams, which significantly enhances the circuit area and power efficiency.

II. RELATED WORKS A. Stochastic circuits for Bayesian sensor fusion

Sensor fusion circuits combine data from several sensors to synthesize information on a state variable or to reduce sensor noise and enhance measurements accuracy. For many AI systems where most of the computation power is in the cloud, they provide computing capability at the edge to transmit only essential data to remote servers and save precious communication bandwidth.

In this context, Bayesian inference provides a theoretical framework that allows building models for sensor fusion (see for instance [START_REF] Coninx | Bayesian sensor fusion with fast and low power stochastic circuits[END_REF], [START_REF] Frisch | A Bayesian stochastic machine for sound source localization[END_REF]). In addition to fusing sensor data, such explainable models allow sensor diagnosis by inferring values for one sensor knowing the output states and the other sensors data.

In a Bayesian sensor fusion model, a state variable S is usually inferred from n independent sensor readings K i using sensor models P (K i |S) thanks to Bayes' theorem:

P (S| ∧ n i=1 K i ) ∝ P (S) n i=1 P (K i |S) (1)
The probability distribution P (S), usually called prior, encodes a priori knowledge about the state S. The conditional probability distribution P (K i |S) on sensor reading K i knowing the state S, called a likelihood, encodes knowledge related to a physical model of the sensor.

When S is a discrete variable with cardinal m, and given a set {k 1 , . . . , k n } of acquired sensor samples, for each 1 ≤ j ≤ m, Eq. 1 becomes:

P (S = s j |∧ n i=1 K i = k i ) ∝ P (S = s j ) n i=1 P (K i = k i |S = s j )
(2) As the inference of Eq. 2 only involves computing products, it may be efficiently implemented as a multiplication matrix of 1+n columns (for the prior and the likelihoods) computing in parallel on m rows the posterior distribution for all values of S [START_REF] Coninx | Bayesian sensor fusion with fast and low power stochastic circuits[END_REF]. Consequently, the stochastic circuit dedicated to Bayesian sensor fusion, shown in Fig. 1, is comprised of the following blocks:

• Memories that store sensor models P (K i |S = s j ), • Stochastic Number Generators, which are comprised of RNGs and Probability Converter Circuits (PCC), usually a comparator, that convert likelihood values into stochastic bit-streams, • AND gates that perform the multiplication of likelihoods and priors, • and finally, counters that convert the resulting stochastic bit-steams into standard binary representations. When a new sample k i is acquired, the likelihood P (K i = k i |S = s j ) is read from memory. Then, this value is compared to a random number in the PCC to generate a bit at '1' or at '0' with probability P (K i = k i |S = s j ) according to a Bernoulli trial. Since rows are independent, it is possible to share one RNG per column. Thus, only n + 1 RNGs are needed to generate m * (n + 1) stochastic bit-streams. These RNGs are usually implemented using Linear-Feedback Shift Registers (LFSR). Although LFSRs are pseudo-deterministic RNGs, they are popular in these implementations due to their small area and power consumption while having good bias properties.

B. Methods to reduce SNG area and power consumption

Previous works proposed solutions to make the SNGs more power and area efficient, mainly by sharing logical resources.

First, in [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF], Chen and Hayes developed the concept of stochastic bit-stream isolation, aiming at reducing correlation between bit-streams while sharing a SNG over several of them.

To do so, a so called isolator is implemented, which actually corresponds to a register, to shift the bit-streams in time and, thus, reduce their cross-correlation. However, this single shared RNG needs to have low auto-correlation to prevent a decrease in computation accuracy. LFSRs do not satisfy this requirement, and more sophisticated RNGs have higher area and power consumption.

In [START_REF] Neugebauer | Building a better random number generator for stochastic computing[END_REF], Neugebauer et. al. propose to use an RNG based on a substitution box (S-Box), the SBoNG. These RNGs are larger than LFSRs, but they provide bit-streams with lower autocorrelation. They can therefore be shared over several SNGs using the isolators mentioned above. This method allows to save up to 20% of area compared to the LFSR implementation when sharing one RNG over 100 SNGs.

Other works focus on the PCC part of the SNG.

[5] describes an efficient PCC, based on the Weighted Binary Generator (WBG). The WBG in itself is larger than a comparatorbased PCC. However, a part of the WBG, the Weight Generator (WG), can be shared over one whole column since it does not depend on the likelihood to be encoded, as shown in Fig. 2a. Consequently, area and power consumption can be saved this way. On the contrary, a comparator cannot be split with a common part sharing resources, making mandatory the whole PCC implementation for each cell.

Finally, recent works proposed to share the same random numbers, even with a simple LFSR, to generate several stochastic bit-streams by using bit permutations between the RNG and the PCC. While [START_REF] Ichihara | Compact and accurate stochastic circuits with shared random number sources[END_REF] proposes to use circular shifts on the same random numbers, in [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF], Salehi defines an algorithm to determine the set of k permutations over a n-bit random number that minimize pairwise correlations between the stochastic bit-streams. This method achieves less correlated stochastic bit-streams than in [START_REF] Ichihara | Compact and accurate stochastic circuits with shared random number sources[END_REF], and saves up to 50% area and power consumption of the SNGs, while maintaining equivalent computation accuracy.

In conclusion, wire permutations of [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF] allow to share one RNG over several SNGs. However, if the RNG is shared over more than two SNGs, accuracy starts dropping. When using isolators as in [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF], one RNG can be shared over more than two SNGs without accuracy loss, but the hardware overhead can be significant. In the next section, we propose a new method for sharing one RNG over several SNGs, with minimal accuracy loss, and minimal hardware overhead.

III. A SNG BASED ON SHIFT REGISTER ISOLATOR

In this proposition, we introduce two improvements to the method proposed in [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF]:

• Firstly, we insert isolators at the output of one RNG instead of at the SNGs outputs. We therefore shift random numbers instead of bit-streams. This RNG is shared over all the SNGs. This way, we limit the hardware overhead when adding new rows and columns to the design. • Secondly, as in [START_REF] Yang | Towards theoretical cost limit of stochastic number generators for stochastic computing[END_REF], we reduce the hardware cost of the PCCs by mutualizing a part of the WBG, the WG, and attaching it to the RNG, before the isolators. This amounts to factorising a part of the hardware resources which is used in every Bayesian cell. Fig. 2a shows the architecture of the WBG. It can be separated into two parts. Firstly, the WG associates a weight to each output bit. Then, the Probability Encoder generates the stochastic bit-stream according to the associated likelihood or prior.

The architecture proposed in this paper, called Shift Register Isolator (SRI), is depicted in Fig. 2b. Only one RNG is used in this design. The WG is connected to the output of the RNG. Its output is then shifted using a register pipeline. Finally, the pipelined random numbers are connected to the encoders for each Bayesian cell.

Contrarily to [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF], the SRI can share one RNG over all SNGs if its output has sufficiently low auto-correlation. Moreover, one WG is shared over all the columns, which is not possible when permutations are used. Indeed, permutations have to be applied before the WG.

Compared to the method proposed in [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF], AND gates are no longer separated with registers. Therefore, they are optimized during synthesis into one larger AND gate per row. Moreover, when adding new columns to the design, the number of additional registers is no longer dependent on the number of lines, but only on the RNG output data width which is fixed (it is associated to the data coding precision). Consequently, this method saves area and power consumption in designs with a large number of rows and columns. For example, in a design with 128 rows, if data is encoded with 8 bits, each added column involves adding 8 registers instead of 128 registers for the method of [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF].

As in [START_REF] Chen | Analyzing and controlling accuracy in stochastic circuits[END_REF], using isolators introduces a latency corresponding to the number of columns. However, this latency is negligible compared to the computing time associated with the bit-stream length.

IV. ACCURACY, AREA AND POWER COMPARISONS OF SNG

ARCHITECTURES

This section compares different SNG implementations, including the proposition of Sec. III, in terms of accuracy, area and power consumption.

A. SNG quality metrics

In this paper, we use two complementary metrics for computation accuracy: the Stochastic Computing Correlation quantifies at the component level the RNG capacity to generate uncorrelated bit-streams, and the Kullback-Leibler Divergence measures at the application level the quality of the output probability distribution.

1) Stochastic Computing Correlation: [START_REF] Alaghi | Exploiting correlation in stochastic circuit design[END_REF] introduces a metric to measure the correlation between two stochastic bitstreams X and Y, the Stochastic Computing Correlation (SCC), defined by Eq. 3:

SCC(X, Y ) =      0 if δ(X, Y ) = 0 δ(X,Y ) min(p X ,p Y )-p X .p Y if δ(X, Y ) > 0 δ(X,Y ) p X .p Y -max(p X +p Y -1,0) if δ(X, Y ) < 0
(3) where p X and p Y are respectively the encoded values of the bit-streams X and Y , p X∧Y is the encoded value of the bitstream at the output of the AND gate with X and Y as inputs, and δ(X, Y ) = p X∧Y -p X .p Y . The SCC measure varies in the [-1; 1] segment. SCC = 0 means that the two bit-streams are uncorrelated, SCC = 1 means that the bit-streams are equal, and SCC = -1 means that they are opposite, that is, each bit of X at '0' corresponds to a '1' for Y and vice versa.

To compute the correlation between two SNGs S and S as defined in [START_REF] Ichihara | Compact and accurate stochastic circuits with shared random number sources[END_REF], we perform the SCC average on all possible values of X and Y :

SCC avg (S, S ) = 2 s -1 i=0 2 s -1 j=0 |SCC(S i , S j )| (2 s × 2 s ) (4)
where s is the data precision, and S i and S j are the generated bit-streams with the SNG S (respectively S ) and with the encoded value i/2 s (respectively j/2 s ). Then, SCC avg is always positive, and the lower it is, the less correlated are the SNGs.

To measure the stochastic quality of a set of n SNGs, we therefore perform the average over the n 2 pairwise SCC averages.

2) Kullback-Leibler Divergence: Another way to measure the quality of SNGs in this application is to compare the resulting distribution of the stochastic circuit P stoc with a reference distribution P float computed with floating point multiplications. For this purpose, we use the Kullback-Leibler Divergence (KLD), which provides a measure of distance between probability distributions which is grounded in information theory:

D KL (P stoc P float ) = m j=1 P stoc (j) log P stoc (j) P float (j) (5)
where P stoc (j) (respectively P f loat (j)) corresponds to the result of inference P (S = s j |∧ n i=1 K i ) computed in stochastic (respectively floating point) representation.

The KLD is always positive. The lower it is, the closer are the output and reference distributions, so the better is the set of SNGs.

B. Protocol

This study is divided into two parts. Firstly, a comparison in terms of correlation and accuracy is realized at software level, by simulating RNGs and architecture behaviors in C language. Secondly, a comparison in terms of area and power is done at hardware level by implementing these architectures in a STMicroelectronics 65 nm CMOS technology and using retro annotated simulations.

The studied RNGs architectures are the following:

• 8-bit, 16-bit and 32-bit LFSR,

• 8-bit, 16-bit and 32-bit SBoNG of [START_REF] Neugebauer | Building a better random number generator for stochastic computing[END_REF],

• 16-bit and 32-bit Xoroshiro,

• STRNG, a True Random Number Generator (TRNG) based on a Self-Timed Ring, introduced in [START_REF] Cherkaoui | A self-timed ring based true random number generator[END_REF], and simulated in software via a set of recorded output data. Note that simple RNGs such as LFSRs have highly autocorrelated outputs, while the STRNG has low to nonexistant auto-correlation at its output.

These RNG implementations are combined with different PCCs (comparator or WBG), and with or without RNG sharing using the permutation method of [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF], or our proposed SRI.

We set the problem dimensions as follows:

• likelihoods are encoded on 8 bits and so are the random numbers (which correspond to the 8 least significant bits of the RNG outputs), • the counters have a size of 8 bits,

• the number of columns (number of sensors + 1) is fixed to 8 for the software simulation and ranges from 8 to 16 for the hardware comparison, • the discretization of the state variable S (number of rows) varies in the set {8, 16, 32, 64} for the hardware comparison, and is chosen as large as possible for the software comparison in order to get stable results in a reasonable computation time, • the bit-stream lengths vary exponentially from 2 3 to 2 23 cycles. To put these numbers into perspective, let us note that the sound source localisation application presented in [START_REF] Frisch | A Bayesian stochastic machine for sound source localization[END_REF] implements Bayesian sensor fusion with 4096 lines and 104 columns (grouped in slices of 10 columns) and considers typical bit-stream lengths varying between 2 12 and 2 23 .

For a fair comparison, we perform beforehand a study on RNG seeds, similar to the one developed in [START_REF] Anderson | Effect of lfsr seeding, scrambling and feedback polynomial on stochastic computing accuracy[END_REF], looking for those minimizing the pairwise SCC avg . This study is carried out in an exhaustive manner for the 8-bit LFSR, but the problem quickly becomes intractable with the growing size of RNGs. Therefore, we use Monte Carlo samples to compute the pairwise SCC avg with a set of randomly generated seeds N trials times (with N trials ≥ 1000), and register the ones with the lowest pairwise SCC avg . Our study shows that optimized seeding reduces KLD up to 30% compared to a fully random seeding, which is significant and has to be properly studied. Notice that it is not in the scope of this paper.

Likewise, computing SCC avg is intractable over the 8 columns, so it is also done with randomly generated likeli-hoods values over a large number of rows (around 10000). KLD measurements are done at the same time with this same set of random data. Fig. 3a shows the impact of RNGs on the KLD in a design without the SNG optimizations of Sec. II-B and Sec. III. Independently of the chosen RNG, if the bit-stream length is shorter than the RNG period (2 s -1 for LFSR and 2 2s for SBoNG and Xoroshiro, s being the RNG output precision), all studied RNGs lead to similar KLD (even the TRNG). In other words, in terms of SC multiplication accuracy, even RNGs with high auto-correlation such as LFSRs tend to behave like ideal RNGs as long as the stochastic bit-stream is shorter than the period. Beyond this period, the KLD curve reaches a plateau, and the SC precision can no longer be enhanced with the bit-stream length. Fig. 3b shows the impact of the proposed SRI on the KLD. Simple, high auto-correlated RNGs such as LFSRs are not compatible with our SRI proposition and lead to significant accuracy loss due to the use of isolation. Accuracy is also impacted when using SBoNGs but if the stochastic bit-stream length does not exceed 2 13 cycles, the KLD loss remains negligible. For RNGs with low auto-correlation, such as Xoroshiro or STRNG, isolation does not affect the KLD.

C. Computation accuracy results

LFSR8

Table I proposed in this paper for a bit-stream length of 2 13 . We can see that the use of WBG does not decrease computation accuracy. Furthermore, the inverse permutation of [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF], which, to the best of our knowledge, corresponds to the state of the art, shows almost the same ideal KLD and SCC as the bare implementation with the use of any studied RNG. Until this breaking point of 2 13 , the proposed SRI architecture also achieves equivalent ideal accuracy for low auto-correlated RNG such as SBoNG and Xoroshiro.

In conclusion, when using pseudo-deterministic RNGs, computation accuracy increases with the bit-stream length as long as it is shorter than the RNG period. This result tends to support the exclusive use of simple RNGs such as LFSRs for SC since larger RNGs such as Xoroshiro or the STRNG do not significantly enhance accuracy. However, to allow the use of our proposed SRI, the RNG output must have a low auto-correlation. Thus, these more sophisticated RNGs can paradoxically allow a more compact design (cf Sec. IV-D) without accuracy loss. The proposed SRI architecture with both Xoroshiro-16 and SBoNG-8 satisfies these requirements and shows similar accuracy than state of the art implementations.

For a given application, the required bit-stream length L depends on the number of sensors and on the target accuracy. According to our analysis and to Fig. 3, for a given bitstream, some architectures are more accurate than others. Consequently, L is set depending on the application, and the choice of an adequate architecture is set depending on L. In the following, we compare architectures with similar accuracy for L ranging from 2 10 to 2 20 cycles.

D. Power and area results

Since area and power measurements are independent of the computation time, the hardware results presented in this section do not depend on the bit-stream length. For the hardware simulations, this length is arbitrarily chosen at 10000 cycles, a number large enough to obtain representative results. These results are therefore consistent with any value of L, as long as the studied architecture achieves ideal accuracy, according to Fig. 3.

A first hardware simulation of the bare architecture of Fig. 1 using LFSR32, with 8 rows and 16 columns, shows that the the RNGs represent 29% of the circuit area (8135 out of 27775 µm 2 ), and 85% of its power consumption (2.451 out of 2.883 mW). This first result strongly motivates the use of schemes sharing RNGs to reduce their implementation cost.

In a second set of experiments, we compare the 4 more compact SNG architectures reaching ideal accuracy within the studied range of use (2 10 ≤ L ≤ 2 20 ), and using or not our proposed SRI:

• Inverse permutation architectures of [START_REF] Salehi | Low-cost stochastic number generators for stochastic computing[END_REF] sharing either LFSR16 or LFSR32 with WBG as PCC. These architectures can be used until 2 16 and 2 32 cycles without accuracy loss, and are respectively noted SOTA16 and SOTA32 (for State Of The Art); • SRI architectures either a sharing of a SBoNG-8 or a Xoroshiro-16, which can be used respectively until 2 13 and 2 32 cycles, and respectively noted SRI13 and SRI32. We plot in Fig. 4a the power consumption comparison of these architectures, for circuits of 8 to 64 rows and 8 to 16 columns.

Since these implementations are not usable in the same range of use, we have to do 3 pairwise comparisons according to the bit-stream length L required in the application:

• between SOTA16 and SRI13 when 2 10 < L < 2 13 , • between SOTA16 and SRI32 when 2 13 < L < 2 16 , • between SOTA32 and SRI32 when 2 16 < L < 2 20 . For the sake of brevity, we do not present the full comparative study made on circuit areas for the different implementations (which show little variations) but only describe the main results.

Circuits using the SRI13 always have a smaller area and power consumption than their SOTA16 counterparts, as well as SRI32 compared to SOTA32.

Indeed, when comparing SOTA16 and SRI13 (for L < 2 13 ), for the worst case, (64 rows and 8 columns), the SRI13 architecture achieves a slight reduction of 0.2% in terms of area (from 70223 to 70075 µm 2 ) but is significantly better in power consumption compared to SOTA16 with more than 20% of reduction (from 1.175 to 0.931 mW). These results become, as expected, much better with the growing number of columns, with up to 4.5% of area (from 18227 to 17398 µm 2 ) and 41% of power consumption reduction (from 0.833 to 0.488 mW) for the best case (16 columns and 8 rows).

Besides, when comparing SOTA32 and SRI32, (for L > 2 16 ), the hardware comparison is also in favor of our propo- nb col 8 16 sition, with an area reduction of 11% in the best case (from 20155 to 17845 µm 2 ), and a power reduction ranging from 18% (from 1.611 to 1.307 mW) to almost 58% (from 1.48 to 0.623 mW) by using the SRI.

L 2 10 -2 13 SRI13 SRI13 2 13 -2 16 SOTA16 SRI32 2 16 -2 20 SRI32 SRI32 (b)
However, when 2 13 < L < 2 16 , we can see that the SRI32 implementation consumes from 6% (from 0.423 to 0.449 mW) to 11% (from 1.175 to 1.307 mW) more power than the SOTA16 implementation with 8 columns. But the trend is reversing with a 16 columns architecture, where our proposition becomes more power-efficient again, with 15 (from 2.278 to 1.924 mW) to 25% (from 0.833 to 0.623 mW) saved power.

In other words, and as shown in Fig. 4b, the proposed SRI architecture achieves better results for almost every scenario except when using a bit-stream of length between 2 13 and 2 16 with a circuit of 8 columns or less.

Finally, even though this SRI was introduced for a Bayesian circuit, it could be interest for other applications: it could typically provide gains when a) the number of parallel computations (analogous to our circuit rows) gets higher ; and b) the number of operands involved in these parallel computations (analogous to our circuit columns) gets higher too.

Note that for future works on different applications, other metrics than those used in this paper may be required, and the Root Mean Square Error could be used to replace the KLD for applications which do not compute an output probability distribution.

V. CONCLUSION In this article, we introduced a new method for sharing a single RNG over a large number of stochastic bit-streams by shifting random numbers at its output. For this purpose, the RNG output needs to have lower auto-correlation than a standard LFSR and so has to be larger. However, the smaller is not always the better, since this method saves area and power by allowing to use one single RNG for the whole design. We also performed comparisons of different RNGs combined with different resource sharing methods, including the one proposed in this paper, on a Bayesian circuit for sensor fusion, in terms of area and power consumption in a 65 nm CMOS technology. The proposed architecture allows to save up to 11% of area and 58% of power consumption compared to the state of the art. Finally, we believe that our proposition can benefit to the stochastic computing community as it should generalize to other applications than the Bayesian sensor fusion circuits.

Figure 1 :

 1 Figure 1: A stochastic circuit architecture for Bayesian sensor fusion: a matrix of Bayesian cells (BC).

Figure 2 :

 2 Figure 2: Proposed Shift Register Isolator implementation. (a) WBG decomposition adapted from [5] for 4-bits random number (r i,i∈[0;3] ) and 4-bits likelihood (l i,i∈[0;3] ). (b) Global architecture.

Figure 3 :

 3 Figure 3: KLD measurement for different RNGs as a function of the bit-stream length. (a) Bare implementation. (b) With our proposed SRI.

Figure 4 :

 4 Figure 4: Comparison between state of the art and proposed SRI architectures. (a) Power consumption of the Bayesian computing core on different architectures and circuit dimensions. (b) Best architecture according to the required bit-stream length and number of columns.

Table I :

 I provides more detailed KLD and SCC measurements for different SNG configurations, including SRI architecture Comparison of the accuracy of SNGs, measured at the component level by the SCC and at the application level by the KLD.

			Error measurement
	Sharing version	RNG	after 2 13 cycles (×10 -2 )
			SCC	KLD
		LFSR-16	3.71	1.50
		LFSR-32	3.83	1.47
	Bare	SBoNG-8	3.52	1.35
		Xoroshiro-16	3.44	1.30
		STRNG	3.67	1.35
		LFSR-16	3.08	1.28
		LFSR-32	3.37	1.33
	WBG	SBoNG-8	3.45	1.47
		Xoroshiro-16	3.34	1.47
		STRNG	3.47	1.41
	Inverse	LFSR-16	4.26	1.42
	Permutation [7]	LFSR-32	4.35	1.47
	+ WBG	STRNG	4.30	1.46
	Isolator + WBG	SBoNG-8 Xoroshiro-16 STRNG	4.72 3.52 3.31	1.65 1.41 1.40
	Shift	SBoNG-8	4.67	1.64
	Register	Xoroshiro-16	3.20	1.35
	Isolators	STRNG	3.26	1.40

ACKNOWLEDGMENT

This work has been supported by the grant number 2019/0311 from ANRT.


Raphaël Cerf -

Carlo Mariconda

ORIENTED MEASURES WITH CONTINUOUS DENSITIES AND THE BANG-BANG PRINCIPLE

Keywords: . 15A15, 28B20, 34H05, 49B10, 93C15

We introduce the notion of an oriented measure. For such a measure µ, given ν in L 1 ([a, b]), 0 < ν < 1, there exist two sets E ⊂ [a, b] whose characteristic functions have less than n discontinuity points and such that R ν dµ = µ(E). Given a solution x to the control problem

there exist two bang-bang solutions y, z having a contact of order n with x at a and b such that y ≤ x ≤ z. Reachable sets of bang-bang constrained solutions are convex; an application to the calculus of variations yields a density result.

1991 Mathematics Subject Classification

Introduction

A classical theorem of Liapunov [START_REF] Cesari | Optimization-theory and applications[END_REF] states that given a finite dimensional vector measure µ on an interval [a, b] which admits a density function f = (f 1 , • • • , f n ) and given a measurable function ν defined on [a, b] with values in [0, 1], there exists a measurable subset E of [a, b]

such that ( * ) ∀i ∈ {1, • • • , n} b a f i χ E = b a f i ν.
However the proofs of this theorem are not constructive and thus do not give any information about the set E.

Halkin [START_REF] Halkin | On a generalization of a theorem of Lyapounov[END_REF] showed that if for each vector p ∈ R n the set

t ∈ [a, b] : p • f (t) > 0
(where • is the usual scalar product) is a finite (respectively countable) union of intervals then there exists a set E satisfying ( * ) which is a finite (resp. countable) union of intervals.

As far as we know this condition has not been applied apart the case of piecewise analytical functions [START_REF] Halkin | On a generalization of a theorem of Lyapounov[END_REF][START_REF] Halkin | A generalization of La Salle's bang-bang principle[END_REF][START_REF] Olech | Extremal solutions of a control system[END_REF]. The results we present here are based on the following new Orientation condition ∆. We say that n real functions f 1 , • • • , f n verify condition ∆ on an interval [a, b] if for each k in {1, • • • , n}, the determinant

f 1 (x 1 ) f 1 (x 2 ) • • • f 1 (x k ) f 2 (x 1 ) f 2 (x 2 ) • • • f 2 (x k ) . . . . . . . . . . . . f k (x 1 ) f k (x 2 ) • • • f k (x k )
is not equal to zero whenever the x i ∈ [a, b] are distinct and its sign is constant on the k-uples (x 1 ,

• • • , x k ) such that a ≤ x 1 < x 2 < • • • < x k ≤ b.
A measure µ whose components µ 1 , • • • , µ n admit continuous density functions f 1 , • • • , f n which satisfy the orientation condition ∆ is said to be oriented. Although this condition implies Halkin's one, it possesses various advantages:

• it allows to build a set E satisfying ( * ) whose characteristic function has at most n points of discontinuity;

• in the case where 0 < ν < 1 there exist exactly two such sets E 1 and E 2 and in addition the associated characteristic functions χ E 1 and χ E 2 have exactly n discontinuity points; moreover, one set is a neighbourhood of a whereas the other is not.

We give two proofs of this result, neither of which uses the traditional convexity-extremal points arguments. Both use algebraic tricks directly related to condition ∆; the first one is based on the Implicit Function Theorem and the second one on Caccioppoli Global Inversion Theorem. Consequence of our theorem is that if the interval [a, b] can be partitioned as a finite (respectively countable) union of intervals on which the orientation condition ∆ holds then we can build a set E satisfying ( * ) which is a finite (resp. countable) union of intervals.

We also point out an operational criterion which ensures the validity of the orientation condition ∆: if [a, b] for ∆ to hold. This allows us to formulate a new result concerning bang-bang solutions to linear control systems described by a generic linear differential equation

f 1 , • • • , f n are of class C n-1 on [a, b] it is enough that the Wronskians W (f 1 ), • • • , W (f 1 , • • • , f n ) do not vanish on
L(x) = x (n) + a n-1 (t)x (n-1) + • • • + a 1 (t)x + a 0 (t) ∈ [φ 1 , φ 2 ]
where φ 1 and φ 2 belong to L 1 . More precisely we show that given a solution x to the above problem there exist two bang-bang solutions y and z (i.e. L(y), L(z

) ∈ { φ 1 , φ 2 }) such that ∀t ∈ [a, b] y(t) ≤ x(t) ≤ z(t) ∀k ∈ {0, • • • , n -1} y (k) (a) = x (k) (a) = z (k) (a), y (k) (b) = x (k) (b) = z (k) (b)
and L(D)y and L(D)z are of the form χ E φ 1 + (1 -χ E )φ 2 where the set E is a finite union of intervals, i.e. y and z are solutions associated to relay controls. The relay principle was studied by Andreini and Bacciotti in [START_REF] Andreini-A | Bang-bang and relay principles for time-dependent constraint sets[END_REF] under the strong assumption that φ 1 , φ 2 , a 0 , • • • , a n-1 be analytical. In order to apply our Liapunov's type theorem we explicit the solutions to

L(x) = ν ∈ [0, 1], x(a) = • • • = x (n-1) (a) = 0 through the integral representation formulas ∀k ∈ {0, • • • , n -1} x (k) (t) = t a ∂ k R ∂t k (t, s)ν(s) ds
where R(t, s) is the resolvent of the operator L. Our Wronskian criterion then applies directly to the functions

R(b, •), ∂R ∂t (b, •), • • • , ∂ n-1 R ∂t n-1 (b, •)
and thus our main theorem yields a bang-bang solution

y(t) = t a R(t, s)χ E (s) ds
satisfying the required tangency conditions; moreover the set E is a finite union of intervals which does not contain the point a.

Surprisingly the same Wronskian conditions allow us to apply an extended version of Pólya's generalized Rolle theorem for linear differential operators of order n and functions whose n-th derivative are only piecewise continuous. We obtain that if 0 < ν < 1 then the graphs of x and y do not intersect. Since y (n) (a) < x (n) (a) then y < x on the whole interval ]a, b[. We give two applications of this result.

• The reachable set of solutions which are constrained by a given obstacle and subject to prescribed initial conditions coincides with the reachable set of bang-bang solutions submit to the same conditions, so that this last one is convex.

• We consider the problem of minimizing the integral functionals

I(x, u) = b a f (t, x(t), u(t)) dt where x : [a, b] → R n is such that x (k) (a), x (k) (b) (0 ≤ k ≤ n-1)
are fixed and u is a control belonging to U (t, x) ⊂ R n . The classical approach to obtain existence of a minimum is to impose conditions in order to have the lower semicontinuity of I with respect to u (for instance convexity of u → f (t, x, u)).

Recently in an effort to provide existence criteria other than convexity in u some sufficient conditions have been given: for problems of the calculus of variations (x = u in the above setting) and for maps of the form f (t, x, x ) = g(t, x) + h(t, x ), existence of solutions has been obtained by requiring that the real map x → g(t, x) be monotonic [START_REF] Marcellini | Alcune osservazioni sull'esistenza del minimo di integrali del calcolo delle variazioni senza ipotesi di convessitá[END_REF] or, for x in R n , that the same function be concave [START_REF] Cellina | On a classical problem of the calculus of variations without convexity assumptions[END_REF]. Optimal control problems escaping to convexity conditions have been handled in [START_REF] Raymond | Existence theorems in optimal control problems without convexity assumptions[END_REF]. It has been proved further in [START_REF] Cellina | The existence question in the calculus of variations: a density result[END_REF] that there exists a dense subset D of C(R) such that, for g in it, the problem

minimize b a g(x(t)) dt + b a h(x (t)) dt : x(a) = x 0 , x(b) = x 1
admits a solution for every lower semicontinuous h satisfying growth conditions. Our theorem gives a straightforward generalization of the above result. Let us remark that the elementary case n = 1 of our n-dimensional Liapunov's type theorem appeared as a technical tool in [START_REF] Amar-A | On passing to the limit for non convex variational problems[END_REF]Lemma 3.4]; the case n = 2 was handled in our previous paper [START_REF] Cerf | On bang-bang constrained solutions of a control system[END_REF] with very different techniques which are not applicable to higher dimensions. This work deals only with measures having continuous densities; the general case will be treated in a forthcoming paper.

Preliminary results

One of the two proofs of theorem 1 relies on the following powerful but not enough appreciated

Caccioppoli Global Inversion Theorem. Let E be an arcwise connected metric space, F be a simply connected metric space, f be a proper map from E with values in F . If f is a local homeomorphism at each point of E then f is a global homeomorphism between E and F .

Proof. The proof and several applications of this theorem can be found in [START_REF] Ambrosetti | Global inversion theorems and applications to nonlinear problems[END_REF][START_REF] Ambrosetti | Analisi Non Lineare, I Quaderno[END_REF].

Let us introduce some notations. Let A be an n × n matrix with real coefficients. By det A or |A| we denote its determinant. For each i, j ∈ {1, • • • , n}, by A ij we mean the (n -1) × (n -1) matrix obtained by removing the i-th row and the j-th column from A. Surprisingly, the following simple algebraic trick will play an essential role in the existence part of the proof of theorem 1 which does not involve Caccioppoli Theorem.

Lemma S. Let A = (a ij ) 1≤i,j≤n be an n × n matrix with real coefficients. Let

x 1 , • • • , x n be such that        a 1,1 x 1 + • • • + a 1,n-1 x n-1 + a 1,n x n = 0 a 2,1 x 1 + • • • + a 2,n-1 x n-1 + a 2,n x n = 0 . . . . . . . . . . . . a n-1,1 x 1 + • • • +a n-1,n-1 x n-1 +a n-1,n x n = 0 If det A nn = 0 then a n1 x 1 + • • • + a nn x n = |A| |A nn | x n .
Proof. Cramer rule applied to the above system yields

∀i ∈ {1, • • • , n -1} x i = (-1) n+i |A ni | |A nn | x n so that a n1 x 1 + • • • + a nn x n = n i=1 (-1) n+i a ni |A ni | |A nn | x n = |A| |A nn | x n since |A| = n i=1 (-1) n+i a ni |A ni | is the development of the determinant of |A| along the first row.
The main tool in the inductive proof of theorem 1 is the existence and uniqueness of maximal implicit functions passing through a prescribed point.

Lemma M. Let Ω be an open subset of R n-1 × [a, b] and F a continuously differentiable map from Ω into R n-1 such that ∂F ∂(x 1 ,••• ,x n-1 ) is invertible everywhere. Let (x 1 , • • • , xn ) verify F (x 1 , • • • , xn ) = 0.
Then there exists a unique couple (I, Ψ) verifying Property P below such that I is maximal for the set inclusion with respect to this property.

Property P. I is an interval containing xn , Ψ is a continuous map from

I into R n-1 , Ψ(x n ) = (x 1 , • • • , xn-1 ), F (Ψ(x n ), x n ) = 0 for every x n in I.
Proof of Lemma. Suppose first (I, Ψ I ) and (J, Ψ J ) both satisfy property P. Put

Z = { x n ∈ I ∩ J : Ψ I (x n ) = Ψ J (x n ) }.
This set is not empty (since xn ∈ Z) and is closed because Ψ I and Ψ J are continuous. Let

x * n ∈ Z and (x * 1 , • • • , x * n-1 ) = Ψ I (x * n ) = Ψ J (x * n ) so that F (x * 1 , • • • , x * n ) = 0. We have ∂F ∂(x 1 , • • • , x n-1 ) (x * 1 , • • • , x * n ) = 0
and we can thus apply the implicit function theorem at the point

(x * 1 , • • • , x * n ). There exist an open interval ]x * n -, x * n + [, a neighbourhood O of (x * 1 , • • • , x * n-1 ) and a function φ from ]x * n -, x * n + [ into O such that φ(x * n ) = (x * 1 , • • • , x * n-1 )
and

∀x n ∈ ]x * n -, x * n + [ ∀(x 1 , • • • , x n-1 ) ∈ O F (x 1 , • • • , x n ) = 0 ⇐⇒ (x 1 , • • • , x n-1 ) = φ(x n ).
Thus for every The orientation condition ∆ and some related facts Orientation condition ∆. We say that n real functions

x n in I ∩ J∩ ]x * n -, x * n + [ φ(x n ) = Ψ I (x n ) = Ψ J (x n ) whence Z is
f 1 , • • • , f n verify condition ∆ on an interval [a, b] if for each k in {1, • • • , n}, the determinant f 1 (x 1 ) f 1 (x 2 ) • • • f 1 (x k ) f 2 (x 1 ) f 2 (x 2 ) • • • f 2 (x k ) . . . . . . . . . . . . f k (x 1 ) f k (x 2 ) • • • f k (x k )
is not equal to zero whenever the x i ∈ [a, b] are distinct and its sign is constant on the k-uples (

x 1 , • • • , x k ) such that a ≤ x 1 < x 2 < • • • < x k ≤ b.
Example 1. For n = 1, condition ∆ states that the function f 1 is positive. For n = 2, the functions f 1 , f 2 satisfy ∆ if and only if f 1 > 0 and f 2 /f 1 is increasing.

Example 2. The functions f i (t) = t i-1 (i ≥ 1) satisfy condition ∆ on R (the corresponding determinants are Vandermonde determinants).

Our interest in condition ∆ relies on the following nice facts.

Lemma 1. Let f 1 , • • • , f n be n measurable bounded functions satisfying ∆ on [a, b]. Let ν 1 , • • • , ν n be n positive functions in L 1 ([a, b]). Then for each (n -1)-uple (γ 1 , • • • , γ n-1 ) such that a < γ 1 < • • • < γ n-1 < b the determinant γ 1 a f 1 ν 1 γ 2 γ 1 f 1 ν 2 • • • b γ n-1 f 1 ν n γ 1 a f 2 ν 1 γ 2 γ 1 f 2 ν 2 • • • b γ n-1 f 2 ν n . . . . . . . . . . . . γ 1 a f n ν 1 γ 2 γ 1 f n ν 2 • • • b γ n-1 f n ν n
is not equal to zero.

Proof. Since the determinant is a multilinear continuous form, we can write

γ 1 a f 1 ν 1 • • • b γ n-1 f 1 ν n . . . . . . . . . γ 1 a f n ν 1 • • • b γ n-1 f n ν n = γ 1 a ds 1 • • • b γ n-1 ds n f 1 (s 1 )ν 1 (s 1 ) • • • f 1 (s n )ν n (s n ) . . . . . . . . . f n (s 1 )ν 1 (s 1 ) • • • f n (s n )ν n (s n ) = • • • [a,γ 1 ]×[γ 1 ,γ 2 ]ו••×[γ n-1 ,b] ν 1 (s 1 )ν 2 (s 2 ) • • • ν n (s n ) ω(s 1 , s 2 , • • • , s n ) ds 1 ds 2 • • • ds n where ω(s 1 , • • • , s n ) = f 1 (x 1 ) • • • f 1 (x n ) . . . . . . . . . f n (x 1 ) • • • f n (x n )
.

However the function

(s 1 , • • • , s n ) -→ ν 1 (s 1 ) • • • ν n (s n )ω(s 1 , • • • , s n )
is either positive a.e. or negative a.e. on the open non-empty domain

]a, γ 1 [×]γ 1 , γ 2 [× • • • ×]γ n-1 , b[ so that its integral over [a, γ 1 ] × [γ 1 , γ 2 ] × • • • × [γ n-1 , b] cannot vanish. Lemma 2. Let f 1 , • • • , f m be m measurable bounded functions satisfying condition ∆ on [a, b]. Let ν 1 , • • • , ν m be m positive functions in L 1 ([a, b]). Let (γ 1 , • • • , γ m-1 ) be an (m -1)-uple such that (γ 0 =) a < γ 1 < • • • < γ m-1 < b (= γ m ). If x 1 , • • • , x m are m real numbers not all equal to zero then there exists k in {1, • • • , m} such that m i=1 x i γ i γ i-1 f k (s)ν i (s) ds = 0. Proof. Assume ∀k ∈ {1, • • • , m} m i=1 x i γ i γ i-1 f k (s)ν i (s) ds = 0.
Then the determinant whose elements are the coefficients of x 1 , • • • , x m in the above system

γ 1 a f 1 ν 1 γ 2 γ 1 f 1 ν 2 • • • b γ m-1 f 1 ν m γ 1 a f 2 ν 1 γ 2 γ 1 f 2 ν 2 • • • b γ m-1 f 2 ν m . . . . . . . . . . . . γ 1 a f m ν 1 γ 2 γ 1 f m ν 2 • • • b γ m-1 f m ν m
is necessarily equal to zero, thus contradicting Lemma 1.

Lemma 3. Let f 1 , • • • , f n be n measurable bounded functions satisfying condition ∆ on the interval [a, b]. Let α 1 , • • • , α n be such that (α 0 =) a < α 1 < • • • < α n < b (= α n+1 ).
Then, given a positive , there exist n + 1 positive real numbers λ

0 , • • • , λ n such that ∀l ∈ {0, • • • , n} 0 < λ l < and ∀k ∈ {1, • • • , n} n l=0 (-1) l λ l α l+1 α l f k = 0.
Proof. Consider the n × n linear system

                       λ 0 α 1 a f 1 -λ 1 α 2 α 1 f 1 + • • • +(-1) n-1 λ n-1 α n α n-1 f 1 = (-1) n-1 λ n b α n f 1 λ 0 α 1 a f 2 -λ 1 α 2 α 1 f 2 + • • • +(-1) n-1 λ n-1 α n α n-1 f 2 = (-1) n-1 λ n b α n f 2 . . . . . . . . . . . . . . . λ 0 α 1 a f n -λ 1 α 2 α 1 f n + • • • +(-1) n-1 λ n-1 α n α n-1 f n = (-1) n-1 λ n b α n f n
where λ n is a parameter. The determinant of the system is

ω n = (-1) n(n-1) 2 α 1 a f 1 • • • α n α n-1 f 1 . . . . . . . . . α 1 a f n • • • α n α n-1 f n .
By condition ∆, its sign is (-1)

n(n-1) 2
. Moreover, for each i in {0, • • • , n -1},

ω i = α 1 a f 1 • • • (-1) i-2 α i-1 α i-2 f 1 (-1) n-1 b α n f 1 (-1) i α i+1 α i f 1 • • • (-1) n-1 α n α n-1 f 1 α 1 a f 2 • • • (-1) i-2 α i-1 α i-2 f 2 (-1) n-1 b α n f 2 (-1) i α i+1 α i f 2 • • • (-1) n-1 α n α n-1 f 2 . . . . . . . . . . . . . . . . . . . . . α 1 a f n • • • (-1) i-2 α i-1 α i-2 f n (-1) n-1 b α n f n (-1) i α i+1 α i f n • • • (-1) n-1 α n α n-1 f n i.e
.

ω i = (-1) n(n-1) 2 α 1 a f 1 • • • α i-1 α i-2 f 1 α i+1 α i f 1 • • • b α n f 1 α 1 a f 2 • • • α i-1 α i-2 f 2 α i+1 α i f 2 • • • b α n f 2 . . . . . . . . . . . . . . . . . . α 1 a f n • • • α i-1 α i-2 f n α i+1 α i f n • • • b α n f n
Thus λ i which by Cramer formula equals λ n ω i /ω n has, by condition ∆ and lemma 1, the sign of λ n ; choosing λ n such that

0 < λ n < min( ω n ω 0 , • • • , ω n ω n-1 , )
we obtain an (n + 1)-uple which solves the problem.

We give now a criterion for the fulfilment of the orientation condition ∆.

If f 1 , • • • , f k+1 are of class C k on [a, b]
we will denote their Wronskian by

W (f 1 , • • • , f k+1 )(t) = f 1 (t) • • • f k+1 (t) . . . . . . . . . f (k) 1 (t) • • • f (k) k+1 (t)
.

Proposition 1. Let h 1 , • • • , h n ∈ C n-1 ([a, b]) be such that ∀t ∈ [a, b] W (h 1 )(t) = 0, • • • , W (h 1 , • • • , h n )(t) = 0. Then h 1 , • • • , h n satisfy the orientation condition ∆. Proof. By [13, Theorem V], for each k-uple (t 1 , • • • , t k ) such that a ≤ t 1 < • • • < t k ≤ b, there exists ξ ∈]t 1 , t k [ such that W (h 1 (ξ), • • • , h k (ξ)
) has the same sign as the determinant

h 1 (t 1 ) h 1 (t 2 ) • • • h 1 (t k ) h 2 (t 1 ) h 2 (t 2 ) • • • h 2 (t k ) . . . . . . . . . . . . h k (t 1 ) h k (t 2 ) • • • h k (t k )
.

It follows that the above determinant does not vanish and by continuity, it keeps a constant sign on the connected set of the k-uples Remark 2. For n = 2, the Wronskian conditions on f 1 , f 2 state exactly that f 1 > 0 and

(t 1 , • • • , t k ) such that a ≤ t 1 < • • • < t k ≤ b. Remark 1. It is easy to prove that if h 1 , • • • , h n satisfy the orientation condition ∆ on [a, b] and are of class C n-1 then W (h 1 ), • • • , W (h 1 , • • • , h n ) are
f 1 f 2 -f 1 f 2 > 0 whence f 2 /f 1
is strictly monotonic. However these conditions are not necessary for property ∆ to hold (a function may be strictly monotonic without having a positive derivative).

The range of a finite dimensional oriented measure

In this section we study the range of a finite dimensional measure µ whose components µ 1 , • • • , µ n admit continuous density functions f 1 , • • • , f n which satisfy the orientation condition ∆: such a measure is said to be oriented.

Theorem 1. Let ν ∈ L 1 ([a, b]) be such that 0 ≤ ν ≤ 1. Let f 1 , • • • , f n be n real valued continuous functions on [a, b] satisfying condition ∆ on [a, b]. Then there exist a n-uple α = (α 1 , • • • , α n ) and a n-uple β = (β 1 , • • • , β n ) such that a ≤ α 1 ≤ • • • ≤ α n ≤ b, a ≤ β 1 ≤ • • • ≤ β n ≤ b and if we define E - α = 0≤i≤n i odd [α i , α i+1 ], E + β = 0≤i≤n i even [β i , β i+1 ]
(where

β 0 = a, α n+1 = β n+1 = b) then we have ( * ) ∀k ∈ {1, • • • , n} b a f k (s)χ E - α (s) ds = b a f k (s)ν(s) ds = b a f k (s)χ E + β (s) ds. If in addition 0 < ν < 1 then (α 1 , • • • , α n ) and (β 1 , • • • , β n ) are unique and verify a < α 1 < • • • < α n < b, a < β 1 < • • • < β n < b.
Remark. This theorem has already been proved for n = 2 in [START_REF] Cerf | On bang-bang constrained solutions of a control system[END_REF], but the orientation condition ∆ was not formulated in such a precise way (see remark 1 after proposition 1).

Example. There exist a non-oriented measure µ on an interval, a measurable subset A which is not a finite union of intervals such that for every measurable subset E

µ(A) = µ(E) ⇒ A = E a.e.
Consider for instance the measure µ = (µ 1 , µ 2 ) whose density functions are

f 1 (t) = 1, f 2 (t) = 1 + t sin(1/t)
and the set A = { t ∈ [0, 1] : t sin(1/t) > 0 } (in this case the measure µ is positive but condition ∆ is not fulfilled). We will deal only with the situation where 0 < ν < 1: the fact that the number of intervals corresponding to ν does not depend on ν together with a classical approximation argument yields the general case (this is done explicitly in the proof of theorem 5). We will give two proofs of the theorem. The first one relies on an induction whereas the second one is based on Caccioppoli Global Inversion Theorem. The following lemma will be used in both proofs.

Lemma. Assume 0 < ν < 1 and let l be an integer smaller than n. Then if the l-uple

α = (α 1 , • • • , α l ) (respectively β = (β 1 , • • • , β l )) and its corresponding set E - α (respectively E + β ) satisfy ( * ) with a ≤ α 1 ≤ • • • ≤ α l ≤ b (respectively a ≤ β 1 ≤ • • • ≤ β l ≤ b) then l = n and a < α 1 < • • • < α l < b (resp. a < β 1 < • • • < β l < b).
Proof of the lemma. We first show that under the above assumption there exists a m-uple γ

= (γ 1 , • • • , γ m ), m ≤ l, such that a < γ 1 < • • • < γ m < b and either E -
γ or E + γ satisfy ( * ). Assume for instance there exists i ∈ {0, • • • , l} such that α i = α i+1 (where possibly α 0 = a and α l+1 = b). We have the following cases:

• i = 0 so that a = α 1 . Put m = l -1, γ = (α 2 , • • • , α l ); then E + γ satisfies ( * ). • 0 < i < l. Put m = l -2, γ = (α 1 , • • • , α i-1 , α i+2 , • • • , α n ); then E - γ satisfies ( * ). • i = l. Put m = l -1, γ = (α 1 , • • • , α l-1 )
; then E - γ satisfies ( * ). If two components of the m-uple γ are equal we iterate the above operation on γ until after a finite number of steps we obtain an uple having distinct components and whose one of the associated sets satisfies ( * ). We are thus led to prove the result for a l-uple α such that a < α 1 < • • • < α l < b, similar arguments hold for a l-uple of type β. Suppose l < n. Then by ( * ) we have

∀k ∈ {1, • • • , n} 0≤i≤l i even α i+1 α i f k (s)ν(s) ds - 0≤i≤l i odd α i+1 α i f k (s)(1 -ν(s)) ds = 0 (where α 0 = a, α l+1 = b).
We restrict our attention on the first l + 1 equations of the above system i.e. k belongs to {1, • • • , l + 1}. Application of Lemma 2 with m = l + 1 and

γ 1 = α 1 , • • • , γ l = α l x i = (-1) i+1 , ν i = ν i odd 1 -ν i even , 1 ≤ i ≤ l + 1
shows that these equations cannot hold simultaneously, thus yielding a contradiction.

(α 1 , • • • , α n ) such that a ≤ α 1 ≤ • • • ≤ α n ≤ b F k (α 1 , • • • , α n ) = 0≤i≤n i odd α i+1 α i f k (s) ds - b a f k (s)ν(s) ds
and put

S = { (α 1 , • • • , α n ) ∈ R n : a ≤ α 1 < α 2 < • • • < α n ≤ b, ∀k ∈ {1, • • • , n -1} F k (α 1 , • • • , α n ) = 0 }.
The set S is not empty: ( ᾱ1

, • • • , ᾱn-1 , b) and (a, β1 , • • • , βn-1 ) belong to S. i) Existence of (α 1 , • • • , α n ). Let D be the open subset of R n-1 × [a, b] defined by D = { (α 1 , • • • , α n ) ∈ R n : a < α 1 < • • • < α n ≤ b } and define F : D → R n-1 by F (α 1 , • • • , α n ) = (F 1 (α 1 , • • • , α n ), • • • , F n-1 (α 1 , • • • , α n )) .
The map F is C 1 on D and its jacobian matrix is

Jac F (α 1 , • • • , α n ) =     -f 1 (α 1 ) +f 1 (α 2 ) • • • (-1) n f 1 (α n ) -f 2 (α 1 ) +f 2 (α 2 ) • • • (-1) n f 2 (α n ) . . . . . . . . . . . . -f n-1 (α 1 ) +f n-1 (α 2 ) • • • (-1) n f n-1 (α n )     We see that ∂F ∂(α 1 , • • • , α n-1 ) (α 1 , • • • , α n ) = (-1) n(n-1) 2 f 1 (α 1 ) • • • f 1 (α n-1 ) . . . . . . . . . f n-1 (α 1 ) • • • f n-1 (α n-1 )
which by the orientation condition ∆ does not vanish and keeps a constant sign when

α 1 < α 2 < • • • < α n-1 . Consider the equation ( †) F ((α 1 , • • • , α n-1 ), α n ) = 0. Let (ξ 1 , • • • , ξ n ) ∈ D verify ( †) i.e. (ξ 1 , • • • , ξ n ) ∈ S \ (a, β1 , • • • , βn-1 ) .
Such a point exists: for instance (ᾱ 1 , • • • , ᾱn-1 , b). We apply the implicit function theorem at (ξ

1 , • • • , ξ n ).
There exists an open interval

I containing ξ n , an open neighbourhood U of (ξ 1 , • • • , ξ n-1
), a continuous function

ψ : I -→ U α n -→ (α 1 (α n ), • • • , α n-1 (α n )) such that ∀ ((η 1 , • • • , η n-1 ), η n ) ∈D ∩ (U × I) F ((η 1 , • • • , η n )) = (c 1 , • • • , c n-1 ) ⇐⇒ (η 1 , • • • , η n-1 ) = ψ(η n ).
Moreover, ψ is C 1 and we have

α j (α n ) = f 1 (α 1 ) • • • f 1 (α j-1 ) f 1 (α j+1 ) • • • f 1 (α n ) . . . . . . . . . . . . . . . . . . f n-1 (α 1 ) • • • f n-1 (α j-1 ) f n-1 (α j+1 ) • • • f n-1 (α n ) f 1 (α 1 ) • • • f 1 (α n-1 ) . . . . . . . . . f n-1 (α 1 ) • • • f n-1 (α n-1 )
so that α j (α n ) > 0 on I and the functions α j are increasing. Lemma M yields a maximal interval I M on which ψ can be extended. Let ξ * n = inf I M . The functions α 1 , • • • , α n-1 being increasing on I M , they admit limits

ξ * j = lim η n →ξ * n η n >ξ * n α j (η n ). Remark that ξ * n < b since ξ n ≤ b. By continuity F (ξ * 1 , • • • , ξ * n ) = (0, • • • , 0). 14
We claim that ξ * 1 = a. Suppose ξ * 1 > a. By the maximality of

I M , (ξ * 1 , • • • , ξ * n ) belongs to D \ D so that there exists i ∈ {1, • • • , n -2} such that ξ * i = ξ * i+1 . The (n -1)-uple (ξ * 1 , • • • , ξ * i-1 , ξ * i+2 , • • • , ξ * n , b) and its associated set E - ξ * satisfy ∀k ∈ {1, • • • , n -1} b a f k (s)χ E - ξ * (s) ds = b a f k (s)ν(s) ds
so that the induction hypothesis implies

a < ξ * 1 < • • • < ξ * i-1 < ξ * i+2 < • • • < ξ * n < b < b which is absurd. Since ξ * 1 = a, the (n -1)-uple (ξ * 1 , • • • , ξ * n-1
) is the one given by the theorem at rank n -1 so that ξ

* i = βi-1 for each i in {2, • • • , n}. Thus for each point (ξ 1 , • • • , ξ n ) of S \ {(a, β1 , • • • , βn-1 )} there exists a continuous arc in S joining (ξ 1 , • • • , ξ n ) to (a, β1 , • • • , βn-1 )
. This proves that S is arcwise connected. At this stage we prove that F n (a, β1 , • • • , βn-1 ) and

F n ( ᾱ1 , • • • , ᾱn-1 , b) have opposite signs. Since F (ᾱ 1 , • • • , ᾱn-1 , b) = 0 then for each k in {1, • • • , n -1} - 0≤i≤n-1 i even ᾱi+1 ᾱi f k (s)ν(s) ds + 0≤i≤n-1 i odd ᾱi+1 ᾱi f k (s)(1 -ν(s)) ds = 0 (where ᾱ0 = a, ᾱn = b). Put for k, j in {1, • • • , n} x α j = (-1) j , a α kj = ᾱj ᾱj-1 f k ν α j , A α = a α kj 1≤k,j≤n
where

ν α j = ν if j is odd 1 -ν if j is even so that the above equations become ∀k ∈ {1, • • • , n -1} n j=1 a α kj x α j = 0. Since F n (ᾱ 1 , • • • , ᾱn-1 , b) = n j=1 a α nj x α j , application of Lemma S gives F n ( ᾱ1 , • • • , ᾱn-1 , b) = |A α | |A α nn | (-1) n .
Similarly if we define for k, j in {1, • • • , n} ( β0 = a, βn = b)

x β j = (-1) j+1 , a β kj = βj βj-1 f k ν β j , A β = a β kj 1≤k,j≤n
where

ν β j = ν if j is even 1 -ν if j is odd then we have F n (a, β1 , • • • , βn-1 ) = n j=1 a β nj x β j = |A β | |A β nn | (-1) n+1 . By condition ∆ on f 1 , • • • , f n and
∀k ∈ {1, • • • , n -1} F k (α 1 , • • • , α n ) = 0 so that (α 1 , • • • , α n ) solves the problem. ii) Uniqueness of (α 1 , • • • , α n ) Let (α 1 , • • • , α n ) be in S with a < α 1 < • • • < α n <
d dα n F n (ψ(α n ), α n ) = n i=1 ∂F n ∂α i α i (α n ) = n i=1 (-1) i f n (α i ) f 1 (α 1 ) • • • f 1 (α i-1 ) f 1 (α i+1 ) • • • f 1 (α n ) . . . . . . . . . . . . . . . . . . f n-1 (α 1 ) • • • f n-1 (α i-1 ) f n-1 (α i+1 ) • • • f n-1 (α n ) f 1 (α 1 ) • • • f 1 (α n-1 ) . . . . . . . . . f n-1 (α 1 ) • • • f n-1 (α n-1 ) = (-1) n f 1 (α 1 ) • • • f 1 (α n ) . . . . . . . . . f n (α 1 ) • • • f n (α n ) f 1 (α 1 ) • • • f 1 (α n-1 ) . . . . . . . . . f n-1 (α 1 ) • • • f n-1 (α n-1 )
Thus F n is strictly monotonic along the arc joining (a, β1 , • • • , βn-1 ) and (ᾱ 1 , • • • , ᾱn-1 , b) so that F n vanishes only for one value α n . Since this path is unique then the n-uple

(α 1 , • • • , α n ) is unique.
Existence and uniqueness of a n-uple β corresponding to ν at rank n follows from the fact that it coincides with the n-uple α corresponding to 1 -ν.

Second proof of the theorem.

We only deal with n-uples α, similar arguments hold for n-uples β.

Let Ω = (α 1 , • • • , α n ) ∈ R n : a < α 1 < • • • < α n < b and F = b a f 1 ν, • • • , b a f n ν : ν ∈ L 1 ([a, b]), 0 < ν < 1 . Put for each (α 1 , • • • , α n ) ∈ Ω θ(α 1 , • • • , α n ) = b a f 1 χ E - α , • • • , b a f n χ E - α where E - α = 0≤i≤n i odd [α i , α i+1 ] (α n+1 = b).
We first show that θ takes its values in

F . Let (α 1 , • • • , α n ) in Ω; applying lemma 3 to (f 1 , • • • , f n ), (α 1 , • • • , α n ) and = 1/4, we obtain an (n + 1)-uple (λ 0 , • • • , λ n ) such that: ∀l ∈ {0, • • • , n} 0 < λ l < and ∀k ∈ {1, • • • , n} n l=0 (-1) l λ l α l+1 α l f k = 0. Put ν = 0≤i≤n i even λ i χ [α i ,α i+1 ] + 0≤i≤n i odd (1 -λ i )χ [α i ,α i+1 ]
.

By construction we have 0 < ν < 1 and

∀k ∈ {1, • • • , n} b a f k ν = b a f k χ E - α so that θ(α 1 , • • • , α n ) belongs to F .
The purpose of what follows is to show that the map θ : Ω → F satisfies the hypotheses of Caccioppoli Theorem. 1) Obviously Ω is arcwise connected.

2) The set F , being convex, is simply connected.

3) The map θ is a local homeomorphism at each point of Ω. In fact, θ is differentiable at each point (α 1 , • • • , α n ) of Ω and its jacobian is

det Jac θ(α 1 , • • • , α n ) = (-1) n(n+1) 2 f 1 (α 1 ) • • • f 1 (α n ) . . . . . . . . . f n (α 1 ) • • • f n (α n )
does not vanish on Ω by condition ∆. 4) Finally θ is proper. Let K be a compact subset of F and let

α k = (α k 1 , • • • , α k n
) be a sequence of points in θ -1 (K). Since the sequence (θ(α k )) k∈N is contained in K ⊂ F then by compactness we may assume that there exists

ν * ∈ L 1 ([a, b]), 0 < ν * < 1 such that (•) lim k→∞ θ(α k ) = b a f 1 ν * , • • • , b a f n ν * . The closure Ω = { (α 1 , • • • , α n ) ∈ R n : a ≤ α 1 ≤ • • • ≤ α n ≤ b } of Ω is compact and therefore (α k ) k∈N admits a subsequence which converges to α * = (α * 1 , • • • , α * n ) ∈ Ω. By (•) we have ∀k ∈ {1, • • • , n} b a f k χ E - α * = b a f k ν * and the initial lemma implies a < α * 1 < • • • < α * n < b. Thus α * belongs to Ω and θ -1 (K) is compact. By Caccioppoli Theorem, θ is a global homeomorphism.
As a consequence of theorem 1, we deduce the following

Theorem 2. Let ν be a measurable function on [a, b] such that 0 ≤ ν ≤ 1. Let f 1 , • • • , f n be n continuous functions on [a, b]. Assume that the interval [a, b] is a finite (respectively countable) union of intervals on which the orientation condition ∆ for f 1 , • • • , f n holds.
Then there exists a set E which is finite (resp. countable) union of intervals such that

∀k ∈ {1, • • • , n} b a f k χ E = b a f k ν.
Proof. Under the hypothesis of the theorem, there exists a finite (respectively countable) family of disjoint open intervals (I j ) j∈J included in [a, b] such that [a, b] \ j∈J I j is a negligeable set (with respect to Lebesgue measure) and the functions f 1 , • • • , f n satisfy condition ∆ on each interval I j , j ∈ J. We apply theorem 1 to f 1 , • • • , f n and ν on the interval I j : there exists a set E j included in I j whose characteristic function has less than n discontinuity points such that ∀k ∈ {1, • • • , n}

I j f k χ E j = I j f k ν.
The set E = j∈J E j solves the problem.

Proposition 1 shows that the hypotheses of the theorem are fulfilled as soon as

• f 1 , • • • , f n are of class C n-1 on [a, b], • the set Z = { t ∈ [a, b] : ∃k ∈ {1, • • • , n} W (f 1 , • • • , f k )(t) = 0 } is finite (respectively is negligeable).
This result weakens Halkin's condition [START_REF] Halkin | On a generalization of a theorem of Lyapounov[END_REF] that the interval is a countable union of intervals on which the functions f 1 , • • • , f n are analytical.

Some results on linear differential equations

We consider a linear differential operator

L(D) = D n + a n-1 (t)D n-1 + • • • + a 1 (t)D + a 0 (t)
W (f 1 , • • • , f k+1 )(t) = f 1 (t) • • • f k+1 (t) . . . . . . . . . f (k) 1 (t) • • • f (k) k+1 (t)
.

Definition (see [START_REF] Pólya | On the mean-value theorem corresponding to a given liner homogeneous differential equation[END_REF]). The operator

L possesses property W on [a, b] if there exist n -1 functions h 1 , • • • , h n-1 satisfying ∀i ∈ {1, • • • , n -1} L(D)(h i ) = 0 on [a, b] ∀t ∈ [a, b] W (h 1 )(t) > 0, • • • , W (h 1 , • • • , h n-1 )(t) > 0.
We will use the fact that property W always holds locally: for each fixed

t 0 in [a, b], the n -1 solutions h 1 , • • • , h n-1 to the n -1 Cauchy problems (1 ≤ i ≤ n -1) L(D)(h i ) = 0, h (k) i (t 0 ) = δ(i -1, k) 0 ≤ k ≤ n -1 (where δ(j, k) = 0 if j = k and δ(j, k) = 1 if j = k) are such that ∀i ∈ {1, • • • , n -1} W (h 1 , • • • , h i )(t 0 ) = 1.
Therefore the inequalities

W (h 1 )(t) > 0, • • • , W (h 1 , • • • , h n-1 )(t) > 0 hold in a neighbourhood of t 0 .
The interest of property W is that it allows us to decompose the linear differential operator L into a "product" of differential expressions of the first order.

Let us remark that property W is essential for theorem 4 to hold.

L(D)y = 0 y(s) = • • • = y (n-2) (s) = 0, y (n-1) (s) = 1.
As it is well known, R is of class

C n+k on [a, b] × [a, b] whenever the functions a 0 , • • • , a n-1 are of class C k . Proposition 2. Let R(t, s) be a function in C 2n-2 ([a, b] × [a, b]) satisfying ∀s ∈ [a, b] R(s, s) = ∂R ∂t (s, s) = • • • = ∂ n-2 R ∂t n-2 (s, s) = 0, ∂ n-1 R ∂t n-1 (s, s) = 1.
Then, for each t 0 in [a, b], there exists δ > 0 such that for every t in

[t 0 -δ, t 0 + δ] ∩ [a, b],
the functions

h t i (s) = ∂ n-i R ∂t n-i (t, s) 1 ≤ i ≤ n satisfy condition ∆ on the interval [t 0 -δ, t 0 + δ] ∩ [a, b]. Proof. For each t 0 ∈ [a, b] and for each k ∈ {1, • • • , n}, we have W (h t 0 1 (t 0 ), • • • , h t 0 k (t 0 )) = 1; in fact W (h t 0 1 (t 0 ), • • • , h t 0 k (t 0 )) = ∂ n-1 R ∂t n-1 (t 0 , t 0 ) • • • ∂ n-k R ∂t n-k (t 0 , t 0 ) . . . . . . . . . ∂ n+k-2 R ∂t n+k-2 (t 0 , t 0 ) • • • ∂ n-1 R ∂t n-1 (t 0 , t 0 ) = 1 0 • • • • • • 0 * 1 0 • • • 0 . . . . . . . . . . . . . . . * • • • * 1 0 * • • • • • • * 1 = 1.
By continuity, there exists δ > 0 such that

∀t, s ∈ [t 0 -δ, t 0 + δ] ∩ [a, b] ∀k ∈ {1, • • • , n} W (h t 1 (s), • • • , h t k (s)) > 0.
Proposition 1 yields the conclusion.

Bang-bang constrained solutions

We consider the n-dimensional linear control system

(P) L(D)x = x (n) + a n-1 (t)x (n-1) + • • • + a 1 (t)x + a 0 (t)x ∈ [φ 1 , φ 2 ] a.e. on [a, b]
where the n functions a 0 ,

• • • , a n-1 belong to C n-2 ([a, b]) and φ 1 , φ 2 in L 1 ([a, b]) verify φ 1 ≤ φ 2 .
The function y is said to be a bang-bang solution to (P) if it solves (P) and moreover L(D)y ∈ {φ 1 , φ 2 }.

Given a solution x to (P), existence of a bang-bang solution y satisfying

∀k ∈ {0, • • • , n -1} y (k) (a) = x (k) (a), y (k) (b) = x (k) (b)
has been proven for instance by Cesari [START_REF] Cesari | Optimization-theory and applications[END_REF] and Olech [START_REF] Olech | Extremal solutions of a control system[END_REF].

Theorem 5. Let x in W n,1 ([a, b]
) be a solution to the control problem (P ). Then there exist two bang-bang solutions y and z satisfying the tangency conditions

∀k ∈ {0, • • • , n -1} y (k) (a) = x (k) (a) = z (k) (a), y (k) (b) = x (k) (b) = z (k) (b) and the inequalities ∀t ∈ [a, b] y(t) ≤ x(t) ≤ z(t).
Moreover L(D)y and L(D)z are of the form χ E φ 1 + (1 -χ E )φ 2 where the set E is a finite union of intervals i.e. y, z are solutions associated to relay controls (see [START_REF] Andreini-A | Bang-bang and relay principles for time-dependent constraint sets[END_REF]).

Proof. We will only prove the existence of the function y; similar arguments hold for z.

Let R(t, s) ∈ C 2n-2 ([a, b] × [a, b]
) be the resolvent of the operator L. By proposition 1, there exists δ > 0 such that the functions

h t i (s) = ∂ n-i R ∂t n-i (t,
= 0, φ 2 = φ ≥ 0, x(a) = x (a) = • • • = x (n-1) (a) = 0. In fact, let x satisfy L(D)x ∈ [φ 1 , φ 2 ]. Then, if we set x a (t) = x(a) + x (a) 1! (t -a) + • • • + x (n-1) (a) (n -1)! (t -a) n-1 the function x defined by x = x -x a verifies L(D)x ∈ [ψ 1 , ψ 2 ], ∀k ∈ {0, • • • , n -1} x(k) (a) = 0 where ψ i = φ i -L(D)x a , i = 1, 2.
Clearly the function x defined by

x(t) = x(t) - t a R(t, s)ψ 1 (s) ds satisfies L(D)x = L(D)x -ψ 1 ∈ [0, ψ 2 -ψ 1 ], ∀k ∈ {0, • • • , n -1} x(k) (a) = 0.
If we assume that the theorem holds in this situation, there exists a function ȳ such that ȳ(n) has at most n first-kind discontinuity points and

L(D)ȳ ∈ {0, ψ 2 -ψ 1 }, ∀k ∈ {0, • • • , n -1} ȳ(k) (a) = 0, ȳ(k) (b) = x(k) (b), ∀t ∈ [a, b] ȳ(t) ≤ x(t).
It is now easy to check that the function y defined by

y(t) = ȳ(t) + t a R(t, s)ψ 1 (s) ds + x a (t)
solves our problem.

We assume now

0 ≤ ρ ≤ φ, L(D)x = ρ, ∀k ∈ {0, • • • , n -1} x (k) (a) = 0
so that, with the notations of proposition 2, we have

∀k ∈ {0, • • • , n -1} x (k) (t) = t a ∂ k R ∂t k (t, s)ρ(s) ds = t a h t n-k (s)ρ(s) ds.
Let (ρ m ) m∈N and (φ m ) m∈N be two sequences of continuous functions such that

∀t ∈ [a, b] 0 < ρ m (t) < φ m (t), ρ m L 1 -→ρ, φ m L 1 -→φ and set x m (t) = t a R(t, s)ρ m (s) ds. Clearly, ∀k ∈ {0, • • • , n -1} x (k) m (t) = t a ∂ k R ∂t k (t, s)ρ m (s) ds = t a h t n-k (s)ρ m (s) ds.
Since each φ m is positive then the functions

f i (s) = h b i (s)φ m (s) = ∂ n-i R ∂t n-i (b, s)φ m (s) 1 ≤ i ≤ n satisfy condition ∆ on [a, b]. Then by theorem 1 applied to f 1 , • • • , f n and ν = ρ m /φ m , corresponding to each m there exists a unique n-uple (α m 1 , • • • , α m n ) such that (α m 0 =) a < α m 1 < • • • < α m n < b (= α m n+1 )
and if we set By compactness we may assume

E - m = i odd 0≤i≤n [α m i , α m i+1 ], y m (t) = t a R(t, s)φ m (s)χ E - m (s) ds then we have ∀i ∈ {1, • • • , n} b a f i (s)χ E - m (s) ds = b a f i (s)ν(s) ds i.e. ( * ) ∀k ∈ {0, • • • , n -1} b a ∂ k R ∂t k (b, s)φ m (s)χ E - m (s) ds = b a ∂ k R ∂t k (b, s)ρ m (s) ds so that ∀k ∈ {0, • • • , n -1} D k (y m -x m )(a) = D k (y m -x m )(b) = 0 and L(D)(y m -x m ) = φ m χ E - m -ρ m does not
∀i ∈ {1, • • • , n} lim m→∞ α m i = α i . Clearly (α 0 =) a ≤ α 1 ≤ • • • ≤ α n ≤ b (= α n+1 ). Put E -= i odd 0≤i≤n [α i , α i+1 ], y(t) = t a R(t, s)φ(s)χ E -(s) ds.
Obviously, for all k in {0, • • • , n -1}, y (k) (a) = 0. Moreover, by passing through the limit in ( * ) and ( * * * ), we obtain Proof. With our theorem 5 and the preceding application, the proof is a direct adaptation of the proof given in [START_REF] Cellina | The existence question in the calculus of variations: a density result[END_REF] for the case L(D) = D.

  also open. Since I ∩ J is connected then Z = I ∩ J. Put T = {(I, Ψ I ) satisfying property P} and let I M = (I,Ψ I )∈T I. The previous uniqueness property allows us to define a function Ψ M on I M such that Ψ M = Ψ I on I. The couple (I M , Ψ M ) solves our problem.

  either non-negative or non-positive on the whole interval [a, b].

First proof of thef 1 (s) ds = b a f 1

 11 theorem. Consider the case n = 1. Let f 1 ∈ C([a, b]) satisfy ∆ i.e. f 1 does not vanish on [a, b]. Since f 1 has a constant sign on [a, b] there exist unique real numbers α, β in [a, b] such that b α (s)ν(s) ds = β a f 1 (s) ds. Clearly E - α = [α, b] and E + β = [a, β] satisfy ( * ). Assume the theorem is true at rank n -1. Let f 1 , • • • , f n , ν be functions satisfying the hypothesis of the theorem. By the induction assumption there exist (n -1)-uples ( ᾱ1 , • • • , ᾱn-1 ) and ( β1 , • • • , βn-1 ) satisfying ( * ). Define for each k in {1, • • • , n} and n-uple

  b and build (I M , ψ) as in the existence part. The maximal interval I M is in fact [ βn-1 , b] so that (α 1 , • • • , α n ) belongs to a continuous path in S joining (a, β1 , • • • , βn-1 ) and (ᾱ 1 , • • • , ᾱn-1 , b). By local unicity of ψ near ( ᾱ1 , • • • , ᾱn-1 , b), the arc does not depend on (α 1 , • • • , α n ) (recall that we apply the Implicit Function Theorem on the space R n-1 × [a, b] and that b is an interior point of the topological space [a, b]). For each α n ∈ ] βn-1 , b[, we have

  where D is the derivative operator D = d/dt and a 0 , • • • , a n-1 are n real-valued continuous functions on an interval [a, b]. A generalized Rolle Theorem. If f 1 , • • • , f k+1 are of class C k on [a, b] we will denote their Wronskian by

Example.

  Let f (t) = sin t -αt where α is chosen so that f admits three zeroes on the interval [π/2, 3π]. If we set L(D) = D 2 + 1 we have L(D)(f )(t) = -αt which does not vanish on [π/2, 3π]. However, it is easy to check that the operator L possesses property W on the interval [a, b] if and only if b -a < π. The resolvent and property ∆. Definition. We say that R : [a, b] × [a, b] → R is the resolvent of the operator L if for each fixed s in [a, b] the function t → R(t, s) solves the Cauchy problem

  vanish on [a, b]; since L possesses property W on [a, b], the corollary to theorem 4 then implies that( * * ) ∀t ∈]a, b[ y m (t) = x m (t).Since by constructiony (n) m (a) = L(D)y m (a) -a n-1 (a)D n-1 y m (a) + • • • + a 1 (a)Dy m (a) + a 0 (a)y m (a) = 0 and analogously x (n) m (a) = ρ(a) > 0 then by continuity y m < x m in a neighbourhood ]a, a + [ of a, which together with ( * * ), yields the global inequality ( * * * ) ∀t ∈]a, b[ y m (t) < x m (t).

xTheorem 6 . 7 . 2 k

 672 (k) (b) = b a ∂ k R ∂t k (b, s)ρ(s) ds = b a ∂ k R ∂t k (b, s)φ(s)χ E -(s) ds = y (k) (b) for all k in {0, • • • , n -1} and ∀t ∈ [a, b] y(t) ≤ x(t).The function y solves our problem.The general case. Since the functionsh t i (s) = ∂ n-i R ∂t n-i (t, s) 1 ≤ i ≤ nsatisfy locally condition ∆ and the operator L(D) possesses property W then by compactness there exists a subdivisionc 0 = a < c 1 < • • • < c l < b = c l+1 of [a, b] such that properties W and ∆ hold on each interval I j = [c j , c j+1 ], 0 ≤ j ≤ l. Let x solve L(D)x = ρ, φ 1 ≤ ρ ≤ φ 2; by the first case, for each j in {0, • • • , l} there exists a 27 function y j in W n,1 (I j ) such that y(n) j has only a finite number of first-kind discontinuities satisfyingL(D)y j ∈ {φ 1 , φ 2 } on I j ∀k ∈ {0, • • • , n -1} y (k) j (c j ) = x (k) (c j ), y (k) j (c j+1 ) = x (k) (c j+1 )and ∀t ∈ I j y j (t) ≤ x j (t).The function y ∈ W n,1 ([a, b]) obtained by glueing together the functions y 0 , • • • , y l is a solution to our problem.Remark. The proof of the theorem shows that if there existn solutions h 1 , • • • , h n to L(D)y = 0 on [a, b] satisfying W (h 1 ) > 0, • • • , W (h 1 , • • • , h n ) > 0 on [a, b]then the resolvent of the operator L satisfies condition ∆ on [a, b] and therefore the bangbang solutions y and z can be built in such a way that L(D)y and L(D)z are of the form χ E φ 1 + (1 -χ E )φ 2 where the characteristic function of the set E has less than n discontinuity points on [a, b].For instance, this is the case when L(D) = D n (see example 2 following the definition of condition ∆) or whenL(D) = D n + a n-1 D n-1 + • • • + a 1 D + a 0and the algebraic equationX n + a n-1 X n-1 + • • • + a 1 X + a 0 = 0 has n distinct real roots.The reachable set of bang-bang constrained solutionsLet a 0 , • • • , a n-1 ∈ C n-2 ([a, b]) and φ 1 , φ 2 in L 1 ([a, b]) verify φ 1 ≤ φ 2 . Consider the control problem (P a ) L(D)x = x (n) + a n-1 (t)x (n-1) + • • • + a 1 (t)x + a 0 (t)x ∈ [φ 1 , φ 2 ] a.e. on [a, b] with the initial conditions ∀k ∈ {0, • • • , n -1} x (k) (a) = x k where x 0 , • • • , x n-1 are n fixed real numbers. Let c be an arbitrary function defined on I = [a, b] and consider the reachable sets X c I and Y c I associated to (P a ) defined byX c I = {(x(b), x (b), • • • , x (n-1) (b)) : ∀t ∈ I x(t) ≤ c(t), x solution to (P a )}, Y c I = {(y(b), y (b), • • • , y (n-1) (b)) : ∀t ∈ I y(t) ≤ c(t), y bang-bang solution to (P a )}.Then theorem 5 yields the following result. The sets X c I and Y c I coincide; in particular, the reachable set associated to bang-bang constrained solutions Y c I is convex.An Application to the Calculus of VariationsTheorem Let a 0 , • • • , a n-1 ∈ C n-2 ([a, b]), φ 1 , φ 2 ∈ L 1 ([a, b]) verify φ 1 ≤ φ 2 and let L be the linear differential operator of order n defined byL(D) = D n + a n-1 (t)D n-1 + • • • + a 1 (t)D + a 0 (t). Let x 1 0 , • • • , x 1 n-1 and x 2 0 , • • • , x2n-1 be 2n fixed real numbers. Then there exists a dense subset D of C(R) for the uniform convergence such that for g in D the problem min b a g(x(t)) dt + b a h(L(D)x(t)) dt : x ∈ W n,1 ([a, b]), ∀k ∈ {0, • • • , n -1} x (k) (a) = x 1 k , x (k) (b) = x admits at least one solution for every lower semicontinuous function h satisfying the growth condition h(u) ≥ cψ(|u|), ψ being l.s.c. and convex, lim r→+∞ ψ(r)/r = +∞.

  Lemma 1, |A α | and |A β | have the same sign, as do |A α nn | and |A β nn |. It follows that F n (a, β1 , • • • , βn-1 ) and F n (ᾱ 1 , • • • , ᾱn-1 , b) have opposite signs. Moreover the set S is connected, the map F n is continuous on S and thus must vanish at a point (α 1 , • • • , α n ) of S. By the very definition of S we have also

Theorem 3(see [START_REF] Pólya | On the mean-value theorem corresponding to a given liner homogeneous differential equation[END_REF]). Let the linear differential operator L(D) possess property W on [a, b]. Then there exist n + 1 functions u 0 , • • • , u n such that for each i in {0, • • • , n}, u i is of class C n-i on [a, b] and

As a consequence of this decomposition, we derive a generalized Rolle theorem. We say that the function

By applying Rolle Theorem successively on the intervals [t

Taking into account the multiple zeroes of f we see that D(u 0 f ) admits n + k zeroes on [a, b]. At step n -1, this process yields the existence of k + 2 zeroes for the function

Either one of these zeroes is double or g possesses k + 2 distinct roots: in this situation, at least two of them must lie in one of the k + 1 intervals on which g is C 1 and Rolle Theorem yields a zero of Dg. In both cases, we obtain the existence of a zero of the function u n D(g) = L(D)(f ).

We will use the following straightforward corollary of this theorem.