Waldemar Karpa
email: waldemar.karpa@malix.univ-paris1.fr

Barbara Despiney
email: barbara.despiney@univ-paris1.fr

Why It Is So Hard? A History

Keywords: Franchising, Contractual Design, Concession Contract, Public-Private Partnership JEL classification: D23, H11, H54, K12, L14

  L'archive ouverte pluridisciplinaire

Introduction

Among economists, there is a consensus concerning the need to improve infrastructure, especially in the transport sector, which is seen as a necessary condition for successful economic growth. However, in the case of a few, rather successful transition countries, the problem of a poor transport infrastructure

had not yet been resolved. The best example is Poland, where the quality of its transport infrastructure constitutes an important barrier to the country's development, especially in the context of European integration. Although the total length of the roads is relatively high, Poland lacks the minimum required standard of density of highways and expressways. In order to overcome this unfortunate situation, the State authorities have decided to launch the "Infrastructure -A Key to Development" program, formulating radical changes in the law as well as new methods of financing infrastructure projects. The core concept of the government's program was to turn to the private sector to provide infrastructure improvements, basically highways. One motivation was very limited tax resources, which led to the State borrowing as much as it could from development banks and private capital markets. A second motivation was the hope that the private sector -motivated by profit -would be more efficient than the State. The adopted solution was a Public-Private Partnership (PPP) concept, in the form of long-term concession contracts.

In this paper we investigate the reasons why highway construction projects have been delayed. We argue that some aspects of this unfortunate situation could have been avoided if the predictions of Transaction Cost (TCT), as well as Incomplete Contract (ICT) Theories had been taken into consideration. By halshs-00266971, version 1 -26 Mar 2008 taking as an example the concession allocation for the first section of the A2 highway (supposed to link the eastern and western parts of the country) we will explain why this project has partially failed. We enumerate some -in our opinion -blatant errors by both public and private parties. We especially focus on the control issue, as contract execution yielded flagrant deficiences. was bought by the State. However, the construction process was frustrated until the mid nineties, when the increase in lorry traffic became a serious problem.

Project schedule

Everybody who has ever been to Poland surely remembers its poor transportation network. In the early 90's, numerous ideas for financing highway construction were proposed. None of them, however, were applied. A short time later, the Polish government proposed the "National Plan for Highway Construction" based upon a PPP method. The government was encouraged by the World Bank's "private participation in infrastructure" policy. Indeed, by 1996, the project draft had been prepared. The program was launched in early 1997 within the first successful concession auction biding. In 2001, public opinion was shocked by the Supreme Chamber of Control report revealing that in 1998-2000 0 km of highways were built in the four PPP concession schemes. 2After a stormy period in Parliament and media, followed by some ministers' dismissal, no reconstruction project emerged. Therefore, one may ask, how could this happen?

3 The attribution problem

The story

Under the Polish law on toll highways 3 the building and exploitation of an highway requires a limited three-step auction process, which leads to the objective selection of the best concessionaire. The winning company for the A2 highway was "Autostrada Wielkopolska SA" 4 . Following the winning tender, the Concession Agreement was signed. As the concessionaire, "Autostrada Wielkopolska SA" was initially bound to build and operate the first section of the A2 Highway from Swiecko to Konin (the first segment of 148,7 km 2 ). Furthermore, "Autostrada Wielkopolska SA" did not become the owner of the A2; it ensured the performance of the Concession Agreement for the term of 40 years, that is by 2037. The land on which the highway is built remains the property of the State Treasury and the Company pays an annual rent to the State.

The party to the Concession Agreement on behalf of the Polish government is the Minister of Infrastructure, while the body responsible for its implementation is the Highway Construction and Exploitation Agency. In order to meet its obligation under the Concession Agreement, a Development Company was established -"A2 Bau Development GmbH"(founded by the shareholders of "AWSA": "Strabag AG" and "NCC international AB") which is responsible 3 1994 Toll Highways Act. The Act provides a legal framework for the construction of highways (procedures for location of the highways, acquisition of property on which the highways are to be built, tender proceedings, concessions for the construction and operation of highways). The Act also regulates financial issues related to the construction of highways.

4 "Autostrada Wielkopolska SA", the first Polish special purpose entity incorporated in 1993 was founded in 1994 with the goal of financing, building and operating the A2 Toll Highway. Its capital is made up with Polish and foreign shareholders' funds.

halshs-00266971, version 1 -26 Mar 2008

for the construction, and the operating company -"Autostrada Eksploatacja SA"(founded by the shareholders of "AWSA": "Transroute International SA", "Kulczyk Holding SA" and "Strabag AG"). In order to ensure proper performance under the contracts, in strict compliance with Polish law and the provisions of the Project Agreements, the parties to the concession: the Minister of Infrastructure and the Concessionaire, appointed an Independent Engineer -"WS Atkins" from the UK, whose duty was to supervise the design process, the construction and operation of the highway, as well as to oversee for the proper execution and adequate quality of the work. Though on first sight the contractual clauses seemed to be clear and sound, their interpretation and implementation were baffling.

What went wrong?

As we have already mentioned, once the Concession agreement was signed, a three-year period of astonishing inactivity in the construction process took place. After analyzing the Concession contract, some issues remain, at least, doubtful. Therefore, it seems clear that: 5 . As a result, the Concessionaire was not able to finalize his financial project.

•
• The other side of the same coin reveals that the auction jury members (the State Agency) were (at least should be) in perfect possession of information on the financial situation of the bidders, as required for the tender. Besides some restrictions on shareholders' equity, there were some other legal obligations such as minimum fund gathering by the Concessionaire 6 . Therefore, two possibilities emerge: either the jury members were incompetent, or the contracting offer was incomplete.

5 The Concessionaire was perfectly sure that (taking into consideration its equity weakness) he would not be able to build without the State's guarantees for credits. This is the best example of the Concessionaire's opportunism which is seen in his public statement stressing that "...based on the analysis of the toll revenues generated so far showing slight excess over the assumed levels, it may be said that there is no risk that the State Treasury guarantee will be exercised".

6 At the level of 100% coverage of the first segment. The final Financial Plan for the first section was settled down in 2000 (!) and annexed to the initial Concession Agreement. The lump sum contract price for the investment was agreed at EUR 875 million (EUR 637.5 milion excluding indirect costs). The funds required to meet the foregoing costs came from three major sources:

i equity coming from the Concessionaire's shareholders accounting for more than 27% of the total development cost;

ii loans in the form of the bond issue and supplier credit;

iii Senior Loan;

iv the loan from the European Investment Bank (never granted).

halshs-00266971, version 1 -26 Mar 2008

3.3 What are the theoretical suggestions?

When we look at the theory, some crucial questions must be clarified. Logically, one may ask whether a "perfect auction" exists. Surely, the trivial response is "no", but that does not explain some procedural errors. As highlighted by [START_REF] Williamson | Franchise Bidding for Natural Monopolies -In General and with Respect to CATV[END_REF], the effectiveness of franchise bidding firstly depends on the ability of the franchisor to characterize the service he wants to put to tender.

Yvrande-Billon [2005] explains that an adequate service specification is important in franchising, first as a basis for competition in the bidding process and, secondly, to set the benchmarks for evaluating bids. Therefore, it is important for the franchisor to refine his call for tender as much as possible. If he fails, the costs of bidding may increase and applicants may not be interested in the auction, discouraged by the high uncertainty of the project. Furthermore, as mentioned in [START_REF] Bajari | Auctions versus Negotiations in Procurement: An Empirical Analysis[END_REF], a vague description of the subject matter of auction may lead to adverse selection and end by selection of the most opportunistic candidate. If the call for tender is incomplete and investment is complex, the auction process may result in choosing the bidder who can exploit the contractual blanks and thus may make the most of the fact that the contract in question is likely to fail. A potential danger of this situation consists in the opportunistic anticipation of a renegotiation of contract by the auction winner, who may benefit from the financial compensation stipulated in avoidance clauses.

Another problem with the auction process is intrinsic to the nature of concession agreements. For instance [START_REF] Posner | The Appropriate Scope of Regulation in the Cable Television Industry[END_REF] stresses that "[p.113]...the concession method deprives the franchise system of one of its most attractive features, ease of administration, since when

halshs-00266971, version 1 -26 Mar 2008

the franchise is awarded to the higher bidder the process of choosing among applicants involves a minimum of administrative machinery and official discretion".

Indeed, the simplicity of the auction process could be preserved only if the concession concerned less complex investment. In the case of infrastructure concessions, one should remember that a highway concession in the PPP scheme typically covers the financing, building and operating of a road. Thus, is there a tenable means of anticipating for all factors? And, similarly, is there a solution for internalizing the plurality of states of nature that might occur?

With respect to the transaction cost economics framework, in the case of an undoubtedly incomplete long term contract, the extreme importance of the ex ante stage, that is the auction process, become obvious. It follows that in the ex ante stage it should be anticipated by the franchisor that contract renegotiation will inevitably occur. Summarizing, it appears that the contract incompleteness should be taken into consideration at the very beginning of the project.

On the other hand, one could imagine how difficult it is to decide ex ante what has to be done ex post. We fully agree with [START_REF] Crocker | Regulation and Administered Contracts Revisited: Lessons from Transaction-Cost Economics for Public Utility Regulation[END_REF] who argue that, as the transaction becomes more complex or uncertain, contracts are likely to become more "...'rational' in character. Rather than attempting to lay out a detailed specification of the terms of the agreement, relational contracts attempt simply to establish the process through which future terms of trade will be determined 7 , or, to establish, in effect, a constitution governing the ongoing relationships" [START_REF] Goldberg | Regulation and Administered Contracts[END_REF],

7 p.9

halshs-00266971, version 1 -26 Mar 2008

p.428).

Some remarks have to be made concerning the State guarantees for credit by the Concessionaire. Because of the high risk associated with highway franchises, lenders (investment banks) have refused to grant loans to the Concessionaire unless the government guarantee the debt. Engel et al.[2001] qualify this situation as an usual pitfall for the State. Firstly, guarantees reduce the incentives for lenders to screen projects and monitor their performance. A second danger concerns the overestimation of demand such that the Concessionaire could not face significant losses if traffic turns out to be below expectations, that is to say, the whole investment might become a "white elephant". In addition we argue that bailing out the Concessionaire stands against the idea of PPP, where the State is rather looking to be free of financial commitment, as its Treasury cannot afford the investment alone. Therefore, we are pointing out that the liability of the State8 in the case of the investment fiasco is excessive.

What should have been done?

We are trying here to enumerate some propositions in order to avoid an impasse situation in the future. We do not claim a "miracle" solution. Nevertheless, it seems that the call for tender needs to be more explicit in that the financing structure and risk sharing ought to be specified 9 . In our opinion, the weakness of Polish equities constituted a sufficient incentive to broaden the call for tender. A strong start-up capital mixed with the know-how of foreign investors (capital groups) would have accelerated the construction. But, paradoxically, foreign investors could not have felt attracted by the blanks in the project and the low chances of taking money out. Therefore, a preliminary independent financial audit should always be welcomed. Finally, the presence of clear and precise avoidance or retraction (annulation) clauses not only smoothes bilateral relations but also creates an atmosphere of trust.

4 The supervision problem

The story

The Ministry of Infrastructure entrusted the supervision of highway construction to The Highways Construction and Exploitation Agency (HCEA). This is a common example of delegation of authority, as The Head of Agency accomplishes public management and supervision tasks on behalf of the Government. We notify that The Head of Agency is directly subordinate to his administrative superior, and thus, supposed to execute his decisions. In the case of the A2 Concession, however, the coordination between those two institutions was not as smooth and efficient as it should have been.

As we remember from the previous section, the construction of the first segment of the A2 did not start because of the lack of financial closure. In order to avoid this unfortunate situation in the future, the Concession Agreement was annexed, providing a new deadline for financial closure. Furthermore, there were some new clauses setting forth the possibility of cancellation once the deadline was passed. The new deadline was scheduled for the end of July, and, unfortunately, was also missed.

What are the theoretical suggestions?

In the face of the story above, one can imagine that the public agency is a haven for inefficiency. However, this is a very simplistic view of reality. Generally, the "bureaucratic"inefficiencies (as we think they should be called) result from the lack of coordination in the decision-making process. In the TCT, the governance structure mainly depends on the asset specificity (nature of investment), degree of uncertainty and type of transaction (and its frequency)10 .

Therefore, in our case, "internalization" of Concession management and its follow-up in the form of hierarchy was appropriate. The problems rather come from misunderstanding of the authority-hierarchy relation. It should be remem-bered that " we can talk about hierarchical relations between the subsets of participants A and B when the subset B refers to the subset A's goals rather than to its own in decision-making process and subordinates to A's decision in the case of conflict". [START_REF] Guillaume | Les modeles de la decision[END_REF])

When we turn to analyze the situation between the public agency (The Highways Construction and Exploitation Agency) and its superior (The Ministry of Infrastructure) we can ascertain the lack of acceptance and validation of hierarchy by the public agency. There were two reasons for non-execution of the superior's decision: firstly, the conflict of goals, and secondly, the acquiescence to insubordination. The latter results from the absence of a control mechanism.

Furthermore, the control procedures undertaken by the superior and thus aimed at the subordinates are necessary for the execution of the decisions. It follows that the inefficiency of the State in the Concession-managing process was a direct consequence of the "weak" coercive mechanism. It is important to add that an efficient control procedure depends on an adequate span of control 11 . As we have already mentioned, the superior's decisions were ignored by the intermediary link in the hierarchical chain, namely the Minister's Secretary General. In spite of the fact that the hierarchical structure was simple, and thus the span of control limited (only one intermediary level), serious inefficiencies resulted.

The lack of control regarding the final subordinate -the Concessionaire (and the party of agreement at the same time !) had also contributed to the invest-

11
The span of control (SOC) is a simple managerial construct which identifies or regulates the amount of direct supervision that exists between a superior and his direct subordinates within an organization. For further readings see [START_REF] Yassine | Simple Models of hierarchical Organizations[END_REF] halshs-00266971, version 1 26 Mar 2008 ment fiasco. By adapting the initial [START_REF] Calvo | Supervision, Loss of Control and the Optimal size of the Firm[END_REF] model to the grantorconcessionaire relation, we will show the extreme importance of supervision.

Primarily, we assume that the concessionaire's utility index (U ) depends on its future profit12 (Π), and effort (e):

U = u(Π) -v(e), (1)
Π ≥ 0, 0 ≤ e ≤ 1, and u ≥ 0, v ≥ 0, u ≤ 0, v ≥ 0. If e = 1, the concessionaire is fully effective;

if e = 0, he is completely idle. The presence of a monitoring system implies that the supervision of the concessionaire's effort (i.e. progress of investment) is less costly than the direct measurement of his marginal product. Furthermore, effective supervision requires the imposition of penalties for substandard work.

Let P be the probability of the concessionaire task being checked by his superior (i.e. The Highways Construction and Exploitation Agency). If the concessionaire is not checked, he is presumed to have made the maximum effort (e = 1) and he is given a credit guarantee g (measured in units of future discounted toll revenue). On the other hand, if the concessionaire's real performance is checked, his level of effort e is revealed and he gets only a part of credit guarantee eg, involving a penalty equal to (1 -e)g. Assuming profit equals guarantee of credit attribution, expected utility, γ, associated with selecting a level of effort equal to e is given by:

γ = P [u(eg) -v(e)] + (1 -P )[u(g) -v(e)] (2)
In his turn, the concessionaire chooses e in order to maximize his welfare and defines

Γ(P, g) = max 0≤e≤1 γ (3)
For simplicity, we also assume that there exists a unique e associated with (3)

and denote it e = E(P, g) (4) Thus, it is easy to see that

∂E ∂P ≥ 0 (5)
and

∂E ∂g ≥ 0 ∪ ∂E ∂g < 0 (6)
Proposition 1 The implementation of a supervision scheme increases the level of effort of the supervisee. At the same time, one cannot be sure whether application of penalties in the case of substandard work has a negative or positive impact on the supervisee's performance. It is important to say that the very awareness of being checked works as an incentive mechanism, as each and every supervisee prefers not to be checked. It follows that for a supervisor, providing a spontaneous and random check seems to be the optimal solution.

Proof 1 (Immediate)

For any function E(), we know that e ≥ 0, P > 0 and g ≥ 0. In order to define the sign of partial derivatives of E(), we simply apply their definition formulas.

halshs-00266971, version 1 -26 Mar 2008 totally cancelling the initial one, so it is really difficult to call it a "rider").

E P (P 0 , g 0 ) = ∂E ∂P (P 0 , g 0 ) = lim P →P0 ≥0 E(P, g 0 ) - =0 E(P 0 , g 0 ) P -P 0 >0 ≥0 E g (P 0 , g 0 ) = ∂E ∂g (P 0 , g 0 ) = lim g→g 0 E(P 0 , g) -E(P 0 , g 0 ) g -
Furthermore, the renegotiation process placed the State in a suppliant position.

Finally, once the renegotiation had occurred, the State party should not have agreed to make the new text confidential, firstly, because the investment involved public expenditure and secondly, because the confidentiality excluded an independent audit.

halshs-00266971, version 1 -26 Mar 2008 5 Conclusion

In this paper we have emphasized the most striking problems which affected the very early stages of a highway construction program in Poland. The PPP concept failed to become successful because of the errors committed during the auction process. In the case of the A2 highway concession, it seems that the prequalification step was skimped, making impossible to shortlist bidders with the required financial means and expertise. A way to avoid this kind of situation in the future is to strengthen the domestic capital market. Strong domestic finance is preferable, all else being equal, because it raises fewer political sensitivities and avoids the complications of exchange rate risks. At the other extreme, it appears that more consideration should be given to the use of concession contracts that are shorter and simpler, so that they have a greater chance of being complete.

It is also clear that the management of concession agreements should be simplified and monitoring schemes ought to be implemented in order to prevent a contractor's opportunistic and/or free-rider behavior. Finally, the State should be extremely careful while delegating authority: as we have seen, softening of subordination in the hierarchical chain may lead to bureaucratical pitfalls one rather than of its more desirable features, such as ease of administration instead.

It is important to mention that the A2 highway construction is continuing, in spite of the renegotiation process, and one may expect that it will be possible to Poland, roughly EUR 20 bn of which will be spent on road and highway construction). Nevertheless, extreme vigilance is required concerning its spending.

The Ministry of Infrastructure's recent statement informs us that the "government's ambition" is to use all resources assigned for road construction, as in 2005 Poland had used only 63% all funds available for this purpose. Finally, the recent experiments with a new financing system called "Special Purpose

Issue" need to be watched, as the bureaucratic machinery is not very keen on recognizing its own errors.

Yvrande-Billon A.

  For each step of the A2 PPP agreement we indicate at least one possible solution, as they became evident from a theoretical point of view. To conclude, we propose a brief confrontation of the lessons to be learned for the future, especially as the new government program for land infrastructure has recently been published. 1 Unfortunately, this project was never realized because of the high construction costs, an extremely low level of car ownership and -the most important factor-the start of the 2 nd World War. After the War, because of the frontier change of about 250 km from East to West, Poland inherited 140 km of highways built by the Germans. During the socialist era, there were only 117 km of highway-like roads built, as well as 342 km of expressways. The relatively low level of cars to the kilometer (in 1957: 20 cars/km in Germany, 18 cars/km in France and only 3 cars/km in Poland) meant that the central planners paid much less attention to the road infrastructure issue. In spite of the fact that Poland had signed some COMECON co-operation agreements concerning the development and modernization of the Moscow-Warsaw-Berlin road linkage, the preparation for construction only started in 1980, as the necessity of this axis became indispensable for the organization of the Olympic Games in Moscow. At that time, the project of the future A2 highway was initiated and necessary land 1 "Program Budowy Autostrad i Drog Ekspresowych w Latach 2006-2013": national plan for the construction of highways and expressways published by the Ministry of Infrastructure January 19, 2006.

  The Concessionaire did not fulfill the definitive "commencement deadline for the first segment ", stipulated in the Concession contract for March 10, 1999. This situation resulted from the lack of financial closure for the project. Indeed, some contract clauses were too lax, especially those concerning the issue of risk distribution between the Concessionaire and the State. Particularly, there were no clauses making clear the State's guarantees given to the Concessionaire for credit with investment banks halshs-00266971, version 1 -26 Mar 2008

  should have been done? From now on it is clear, that the Concession agreement should have been unilaterally and immediately cancelled at the second financial closure deadline. The Infrastructure Ministry should have ordered its cancellation by his subordinate (i.e. Chief of The Highways Construction and Exploitation Agency). Tolerating the Concessionaire's inactivity brought about by two consecutive financial closures led to a contract renegotiation procedure (the renegotiation clauses added to the concession agreement constitute a brand new text,

  reach the German border by 2008. It seems that the government has learned its lesson and is keen to engage more budgetary sources in infrastructure projects. It has very strong monetary incentives to do so, as Poland will receive substantial aid from EU funds (the EU budget for 2007-2013 projects EUR 91 bn for halshs-00266971, version 1 -26 Mar 2008

  [2005], "The attribution Process of Delegation Contracts in the French Urban Transport Sector: Why is Competitive Tendering a Myth?", forthcoming Annals of Public and Cooperative Economics

  In this case, the Concession Agreement should have halshs-00266971, version 1 -26 Mar 2008 been cancelled by the State. But it did not happen. In spite of the Ministry of Infrastructure's wish to cancel, the Director of HCEA promoted his own vision of problem resolution, wanting to spread the Concession Agreement over a new consortium. This free-rider behavior was tolerated by The Minister of Infrastructure, who surely knew that -from the legal point of view -a kind of substitution of the Concession party was not possible (a new auction would have been required). Furthermore, the incorporation idea was a disaster, as the

Concessionaire (AW SA) would never agree to integrate with another firm, as it was not interested in sharing profits. It is also important to mention that the contract renegotiation feasibility studies ordered by the HCEA cannot be considered as objective, since the audit provider company (PriceWaterhouseCoopers) was formerly hired by the AW SA as a consultant body to negotiate the initial Concession Agrement.

Najwyzsza Izba Kontroli (NIK) -supreme state audit body. Its status is regulated by the Constitution of April 1997 and by the NIK Act of 23 December 1994.

By "the liability" we mean all legal responsibilities of the State excepting the statutory ones, such as being the the party to the Concession agreement or the land owner.

This can be done by simulating a least-present-value-of-revenue (LPVR) auction. For details seeEngel et al.[2002]

For an exhaustive review of organizational theory see[START_REF] Menard | Why Organizations Matter. A Journey Away from a Fairy Tale[END_REF].halshs-00266971, version 1 -26 Mar 2008

We assume that this is the present value of future tool incomes, and may be approximately given as LPVR.


Damian Terris
email: damian.terris@let.ensma.fr

Karl Joulain
email: karl.joulain@let.ensma.fr

David Lacroix
email: david.lacroix@lemta.uhp-nancy.fr

Denis Lemonnier
email: denis.lemonnier@let.ensma.fr

J Springer

A Poruba

L Mullerova

M Vanecek

O Kluth

B Rech Absorption

Modeling semi-conductor thermal properties: The dispersion role

Keywords: numbers: 63.22.-m, 65.40.-b, 66.70.Df

come

I. INTRODUCTION

Semiconductors are often used in high technology due to their mechanical (crystal structure) and electrical (band gaps) properties. They are found in many domains such as nanojunctions 1 , transistors 2 , or in solar panels 3 , and are even used in medicine [START_REF] Kovalev | Silicon nanocrystals: photosensitizers for oxygen molecules[END_REF] . The increasing use of semiconductor micro/nano-structures has brought, nowadays, a good knowledge on charge transport in spite of heat transfer effects at very short scales [START_REF] Kim | Nanostructuring expands thermal limits[END_REF] . The scope of this paper is to contribute to the charasterisation of semiconductor nanowire and nanofilm thermal properties. Semiconductor nanowires can be found for example in transistors [START_REF] Chen | Vertical nanowire transistor in flexible polymer foil[END_REF] and semiconductor nanofilms in solar cells.

At these low scale, Fourier's law may give an inaccurate description of heat transfer through these nanostructures. One has to deal with more fundamental physics [START_REF] Cahill | Nanoscale thermal transport[END_REF] . Several approaches as lattice dynamic simulation [START_REF] Gomes | In-plane and out-of-plane thermal conductivity of silicon thin films predicted by Molecular Dynamics[END_REF][START_REF] Chantrenne | An analytical model for the thermal conductivity of silicon nanostructures[END_REF][START_REF] Mingo | Calculation of Si nanowire thermal conductivity using complete phonon dispersion relations[END_REF][START_REF] Ju | Phonon scattering in silicon films with thickness of order 100 nm[END_REF] or solving the Boltzmann Transport Equation [START_REF] Yang | Thermal conductivity of core-shell and tubular nanowires[END_REF][START_REF] Chen | Ballistic-diffusive heat-conduction equations[END_REF][START_REF] Volz | Clamped nanowire thermal conductivity based on phonon transport equation[END_REF][START_REF] Goodson | Thermal conduction in nonhomogeneous CVD diamond layers in electronic microstructures[END_REF][START_REF] Lacroix | Monte Carlo transient phonon transport in silicon and germanium at nanoscales[END_REF][START_REF] Mazumder | Monte Carlo study of phonon transport in solid thin films including dispersion and polarization[END_REF] (BTE) have tried to explain experimental measurements [START_REF] Asheghi | Thermal conduction in doped single-crystal silicon films[END_REF][START_REF] Li | Thermal conductivity of individual silicon nanowires[END_REF] . In this paper, the BTE, which is a statistical physics equation, is solved by means of the discrete ordinate method (DOM) which is widely used in thermal radiation [START_REF] Modest | Radiative Heat Transfer[END_REF][START_REF] Lemonnier | Microscale and Nanoscale Heat Transfer[END_REF] . We employ an improved model for describing phonon conduction by taking into account spectral dependancy, found in velocities and relaxation times, using dispersion curves.

At macroscopic scale, conductive heat transfer is governed by the heat equation:

∂T (r, t) ∂t = ∇ [k∇T (r, t)] , (1)
where k is the thermal conductivity. This equation can be derived in the framework of statistical physics considering that individual heat carriers (here phonons) are submitted to a random walk [START_REF] Einstein | On the movement of small particles suspended in stationary liquids required by the Molecular-Kinetic theory of heat[END_REF] . In this diffusive regime, where collisions are numerous, the heat flux is related to the temperature gradient by Fourier's law : ϕ(r, t) = -k∇T (r, t).

(2)

When heat carriers do not undergo collisions, they cross the system like photons in thin optical layer. Heat carriers are then said to have a ballistic flight. A radiative-like form describes the steady state solution :

ϕ = σ(T 4 1 -T 4 2 ). (3)
When phonon mean free path is of the same order as the system length, then some of them undergo collisions, while others cross the structure without any interaction. The system is in the mesoscopic regime.

Theoretically, as long as wave effects are negligible, the BTE applies to the ballistic, mesoscopic and diffusive regimes. A key feature of this approach is to introduce a specific intensity for phonon [START_REF] Kittel | Introduction to solid state physics[END_REF] , similar to photon intensity used in radiative transfer [START_REF] Majumdar | Microscale heat conduction in dielectric thin films[END_REF] . Thus, the energy flux per apparent surface unit at point r in direction u reads:

I ω,p (r, u) = ωn ω (r, u) V g 4π , (4)
with the Planck constant, n ω (r, u) the phonon density at position r going in direction u and V g the heat carrier group velocity. The BTE collision term is classicaly approached by the single relaxation time approximation and, therefore, in steady state, the transport resolution reads:

u • ∇I ω,p = I 0 ω,p -I ω,p V g τ ω,p , (5)
where I 0 ω,p is the intensity at local equilibrium and τ ω,p the relaxation time.

II. NUMERICAL RESOLUTION

A. Nanostructure geometry modelling

We here consider nanofilms and nanowires made of semiconductor material. The wire geometry refers to a cylinder whose length (L) is much larger than its diameter (D), L >> D.

Cylindrical coordinates are obviously well adapted to this case. Films may also be viewed as cylinders in the limiting case where their thickness L is much lower than the diameter D. Therefore, BTE in cylindrical coordinates still applies, it reads, for an axisymmetric

problem 25 : µ r ∂(rI ω,p ) ∂r + ξ ∂I ω,p ∂z - 1 r ∂(ηI ω,p ) ∂φ + κ ω,p I ω,p = κ ω,p I 0 ω (T ), (6)
where κ ω,p = 1 Vgτω,p is the extinction coefficient and where µ, η and ξ (Eqn.7) are the direction cosines of the propagation direction u (fig. 1). They are linked to polar angles φ and ψ characterising u in a local frame by:

         µ = cos(φ) sin(ψ), η = sin(φ) sin(ψ), ξ = cos(ψ). (7)
The term ∂ ∂φ represents the angular redistribution and the variation over θ (fig. 1) is not written since ∂ ∂θ = 0 in an axisymmetric problem. Figure 1 shows a typical geometry under consideration. The two ending sections are always considered as black surfaces set at different temperatures: T hot on the left side and T cold on the right side (T hot > T cold ). They emit phonons with a blackbody intensity at their wall temperature (Eqn.8).

I 0 ω,p (T W all ) = ω 3 8π 3 V 2 p [exp( ω/k b T W all ) -1] , (8)
where V p is the phase velocity and T W all is either T hot or T cold .

The lateral (cylindrical) surface is treated as adiabatic, which amounts to consider pure reflection at the wall. In the wire configuration, wall reflection is in general partly specular and partly diffusive. In the film case, it is always specular so that there is no lateral boundary influence. Condition on the cylinder axis is due to symmetry specular reflection.

B. Discrete Ordinate Method -DOM

The DOM is based on the selection of a finite set of propagation directions (s m , m = 1, . . . , M) and corresponding weights (w m ) [START_REF] Jendoubi | Discrete-Ordinates solutions for radiatively participing media in a cylindrical enclosure[END_REF][START_REF] Balsara | Fast and accurate Discrete Ordinates Methods for multidimensional radiative transfer. Part I, basic methods[END_REF][START_REF] Koch | Evaluation of quadrature schemes for the Discrete Ordinates Method[END_REF] . S N quadrature (fig. 2) is the most commonly used. It is constructed with a maximum of symmetry requirements (to avoid directional bias) and the weight selection rules tend to preserve the exact values of some direction cosine key moments.

Boundary condition for any discrete direction leaving adiabatic surfaces are expressed as:

I m (x P ) = ρ π m ′ if s ′ m •n<0 w m ′ I m ′ (x P )|s ′ m • n| + (1 -ρ)I m(x P ), (9)
where, due to S N set symmetries, if s m belongs to the quadrature, so does the specularly reflected direction s m. ρ is the ratio of diffuse to specular reflection (ρ = 0 yields pure specular reflection).

In this equation, as in the rest of the text, spectral indices ω and p are omitted for sake of clarity.

In this work, S 8 quadrature is employed. It involves 80 directions, but thank to the symmetry only 40 directions are used, with their associate weight doubled.

C. Numerical procedures

The DOM is widely used to model radiative heat transfer and has already been employed to resolve steady or unsteady BTE for phonons [START_REF] Lemonnier | Microscale and Nanoscale Heat Transfer[END_REF][START_REF] Fiveland | A Discrete-Ordinates Method for predicting radiative heat transfer in axisymmetric enclosures[END_REF] . Following Lathrop's guidelines [START_REF] Lathrop | Spatial differencing of the transport equation: Positivity vs. accuracy[END_REF] , a variable weight scheme (Eqn. 10) is used to relate cell-face intensities to the central value I m,P in a node P , for a given propagation direction m, at a given frequency ω and polarization p. Considering phonon propagation directions s m represented in figure 3, the discretized intensities will be written as:

I m,E = I m,W + I m,P -I m,W a , I m,N = I m,S + I m,P -I m,S b , (10)
I m+ 1 2 ,P = I m-1 2 ,P + I m,P -I m-1 2 ,P c .
The four principal cardinal directions (N, E, S, and W ) refer to the cell nodes surrounding P (fig. 3). Indexes m ± 1 2 point in the two directions around m in a same latitude (ξ = C te ). Direction are swapped with increasing values of ξ and, at a given latitude, with increasing values of µ. In each direction (ξ,µ), a finite volume integration of the BTE yields:

I m,P = λ W I m,W + λ m-1 2 I m-1 2 ,P + λ S I m,S + λ o I o ω (T P ) |µ m |∆ z r E a -∆r∆z wm α m+ 1 2 c + λ S + λ o , (11)
with:

λ W = ∆z |µ m | r E a -µ m ∆r , λ m-1 2 = ∆r∆z w m c µ m w m (c -1) -α m-1 2 , λ S = |ξ m |∆r r P b , λ o = r P κ ω ∆r∆z, (12)
and

   α m+ 1 2 -α m-1 2 = µ m w m , α1 2 = 0.
Interpolation weights a, b and c have the following values, which guarantees positivity of the solution while keeping, as much as possible, a 2 nd order accurancy:

a = max   0.
As explained by Lemonnier [START_REF] Lemonnier | Microscale and Nanoscale Heat Transfer[END_REF] , at each new latitude, for a first direction m, the value of I m-1 2 ,P , corresponding to η = 0, has to be initialised. This particular direction is in (r, z) plane. Consequently, the angular redistribution contribution (-1 r ∂(ηIω,p) ∂φ ) is null. Therefore, by setting α m-1 2 = 0 and µ m = -1 -ξ 2 m , I m-1 2 ,P is computed with a and b becoming:

a ′ = max 0.5, 1 - r W ∆z 1 -ξ 2 m λ o + 2|ξ m |r P ∆r + ∆z∆r 1 -ξ 2 m , b ′ = max 0.5, 1 - |ξ m |r P ∆r λ o + (r E + r W )∆z 1 -ξ 2 . (14)

D. Energy conservation

At this step, we can determine spectral intensities at any nanostructure points, for a given direction m, at a frequency ω and polarisation p. The integration over the solid angle dΩ and over the spectrum (dω and p) yields a total intensity in a point P . To be able to obtain I m,P , temperature T is required and is deduced from the energy conservation(Eqn.15).

∂e ∂t + ∇ • q = 0, (15)
where e stands for the integrated phonon energy density, and q, the phonon total flux density:

q(r) = p ωmax 0 4π I ω,P (r, Ω) • ΩdΩdω. (16)
In steady state, the divergence of the phonon total flux density must be null. Therefore, integrating Eqn.5 over all directions and the entire spectrum yields equilibrium:

p ωmax 0 4π κ ω I ω,P dΩdω = p ωmax 0 4π κ ω I o ω (T )dΩdω. ( 17
)
This relation is then inverted to get point P temperature from local intesity (I ω,P ) knowledge in all direction, all frequencies and all relevant branches (Eqn.17).

E. Dispersion relations

Many studies have been done for calculating semiconductors thermal properties, using linear [START_REF] Yang | Thermal conductivity of core-shell and tubular nanowires[END_REF][START_REF] Asen-Palmer | Thermal conductivity of germanium crystals with different isotopic compositions[END_REF][START_REF] Yang | Simulation of nanoscale multidimensional transient heat conduction problems using ballistic-diffusive equations and phonon boltzmann equation[END_REF] or linear by section [START_REF] Holland | Analysis of lattice thermal conductivity[END_REF][START_REF] Singh | Dispersive effects and correction term in two-mode phonon conduction model for Ge[END_REF][START_REF] Liu | Thermal conductivity measurements of ultra-thin single crystal silicon layer[END_REF] spectral dispersion. Fewer litteratures are found with truly non-linear phonon dispersion [START_REF] Lacroix | Monte Carlo transient phonon transport in silicon and germanium at nanoscales[END_REF] . In this work, we use a polynomial phonon dispersion [START_REF] Pop | Analytic band Monte Carlo model for electron transport in Si including acoustic and optical phonon dispersion[END_REF] , for silicon (Fig. 4). For each polarisation branch, the wave vector is discretized into 60 equally spaced values. For germanium, as suggested by Lacroix [START_REF] Lacroix | Monte Carlo transient phonon transport in silicon and germanium at nanoscales[END_REF] , cubic splines are fitted on experimental data 36 (Fig. 5). Germanium wave vector is equally shared into 300 bands. Some assumptions are introduced, semiconductors are assumed as isotropic, where the studied propagation direction is along [100] lattice direction, and only bulk acoustical modes are used. Optical mode are neglected (their respective branches are ignored).

Real phonon dispersion curves for semiconductor are non-linear. Therefore, the group velocity V g (ω, p) = ∂ω ∂K is dissociated from the phase velocity V p (ω, p) = ω K , both being dependent on wave frequency. As a consequence, the blackbody intensity (Eqn.8) has a complex spectral behaviour. The analytical integration over the wave frequency of the equation ( 17) is not available. To overpass this complex behavior, V p (ω, p) is oftenly approximated, in litterature, to a constant V g (ω, p) (linear by section dispersion curves) or to a constant averaged velocity, whereas, in this work, we compute the equilibrium equation. As for the phase velocity, the group velocity spectral variation is introduced in the extinction coefficient κ ω,p = 1 Vgτω,p . This last definition shows that the extinction coefficient κ ω,p is a spectral and branch dependent quantity through V g (p, ω) and the relaxation time τ ω,p . Following Matthiessen's rule, τ ω,p may be expressed as:

τ -1 ω,p = τ -1 U (ω, p) + τ -1 N (ω, p) + τ -1 i (ω, p). (18)
In litterature, Holland relaxation times 32 are oftenly applyed. Therefore, as a starting point, we use, in this work, the same form (Tab. I) to define impurities, Normal and Umklapp processes [START_REF] Kittel | Introduction to solid state physics[END_REF] . Boundary relaxation time is not used since boundary conditions have been imposed further up. Note that the relaxation times can also be temperature dependent.

III. NEW PHONON RELAXATION TIMES IN DISPERSIVE SEMICONDUC-TORS

In this work, the solution of the spectral BTE requires group and phase velocitie determination, deduced from the chosen dispersion curve fit, and of the relaxation time approximation. This latter is done with Holland formulas. A compatibility problem thus occurs since Holland's dispersion curve fits and ours are not similar. Therefore, one can wonder about the relaxation time constants A, B L , B T , and B T U to input in the numerical simulation. For example, the transition between N and U process for transverse phonon is not the same.

Holland assumes that the cutoff frequency is ω 1 = k B Θ 1 whereas Han and Klemens [START_REF] Han | Anharmonic thermal resistivity of dielectric crystals at low temperatures[END_REF] state it occurs at Kmax 2 . Thus, these differences bring a new frequency variation and also a new spectral domain.

Consequently, setting this phonon dispersion to obtain thermal properties with Holland's method yields to an improper answer [START_REF] Chung | Role of phonon dispersion in lattice thermal conductivity modeling[END_REF] (Fig. 6 and Fig. 7). Therefore, the relaxation times have to be fitted to approach semiconductor conductivity with Holland's relaxation time forms but using non-linear dispersion curves.

A. Silicon

Silicon new relaxation times

Since, factors F (boundary) and A (impurity) are present in all the different conductivities k T , k T U , and k L defined by Holland [START_REF] Holland | Analysis of lattice thermal conductivity[END_REF] , we adjust them in a first place using Holland's method to predict conductivity (k T is the conductivity due to impurities, boundaries and Normal transverse collisions, k T U is the conductivity due to impurities, boundaries, and Umklapp transverse collisions, and k L accounts with impurities, boundaries, and longitudinal phonons collisions). Boundary and impurity interactions are dominant at low temperature [START_REF] Holland | Analysis of lattice thermal conductivity[END_REF][START_REF] Han | Anharmonic thermal resistivity of dielectric crystals at low temperatures[END_REF][START_REF] Klemens | Solid state physics[END_REF][START_REF] Srivastava | The physics of phonons[END_REF] , therefore F and A are fitted in this temperature range. Around 10K, close to transverse phonon Normal process highest value, factor B T is fixed.

At high temperature, the coefficient B T U is set where Umklapp processes for transverse phonons prevails. It is unimportant to determine B T before B T U , or conversely when one process is dominant the other is negligible. On the other hand, factor B L , corresponding to longitudinal contribution is fitted at last, hence k L major portion has transversal conductivities non negligible. This last coefficient is found around 100K.

At very high temperatures, optical phonons are not taken into account. Although conductivity values correspond to experimental data, the model does not describe entirely the submitted physics at these temperatures.

Silicon thick films and silicon thick cylinder

To simulate a bulk using our new parameters (Tab.II), we settle the cylinder with the film condition (ρ = 0) for a thickness of L = 7.16mm. In figure (6), for temperatures above 100K, one can notice that the results obtained for the film correspond to Holland's predictions, based on measurements [START_REF] Holland | Analysis of lattice thermal conductivity[END_REF][START_REF] Glassbrenner | Thermal conductivity of silicon and germanium from 3K to the melting point[END_REF] . For lower temperatures (T < 100K), the values obtained with BTE resolution are above the reference curve. Even if the dimensions are huge, Holland is working on a bulk with an equivalent sample size L = 7.16mm, which appears in the boundary reflection contribution (τ -1 b = V s /LF ). In our geometry, the sample size L corresponds more to our diameter D. Therefore, to simulate a wire, the ratio of diffuse to specular reflection ρ is set equal to one. Thus, having D = L = 7.16mm, conductivities obtained for T > 100K, as for the film, match with measurements [START_REF] Holland | Analysis of lattice thermal conductivity[END_REF][START_REF] Glassbrenner | Thermal conductivity of silicon and germanium from 3K to the melting point[END_REF] (Fig. 6). For T < 100K, the results are now below the curve.

A first set of calculations has been performed with a diffuse to specular reflection ratio ρ = 0 (film) and has brought conductivities above or equal to the reference curve. A second set has been examined with ρ = 1 (wire/cylinder, D ≃ L) and has given results below or identical to the curve. It can be then assumed that there exists a ratio of diffuse to specular reflection between 0 and 1 which will give conductivities similar to experimental data (the geometric parameter F is not use in BTE resolution since the boundary conditions are already made in section II A).

B. Germanium new relaxation times

A difficulty is found when we try to fit germanium relaxation time parameters with the equations employed by Holland. The obtained results always underestimate conductivity (Fig. 7), with L = D = 2.4mm (Holland's equivalent sample length and relaxation parameters) or with L = D = 3.8mm (Asen-Palmer's equivalent sample length and relaxation parameters). Germanium thermal property alters with various models and experimental data. Varying the sample length modifies conductivity values at low temperature where boundary scattering is important. Furthermore, germanium conductivity seems to be sensible to the material doping [START_REF] Asen-Palmer | Thermal conductivity of germanium crystals with different isotopic compositions[END_REF][START_REF] Singh | Dispersive effects and correction term in two-mode phonon conduction model for Ge[END_REF][START_REF] Geballe | Isotopic and other types of thermal resistance in germanium[END_REF][START_REF] Bird | Thermal conductivity of n-type germanium from 0.3 to 4.2 K[END_REF] These new germanium relaxation time parameters are given in Table III. The resulting conductivities have less than 5% of relative difference with experimental data for T ≥ 100K (Fig. 7). Just below 100K, a maximum of 7% of relative difference is seen. Under 60K, Glassbrenner's conductivities are always between our film and wire values. One can say that there exists a single ratio of diffuse to specular reflection, for each temperature, which will give conductivities similar to these experimental data. Therefore we are able to valid our germanium parameters.

Note that the spectral discretization is finer for germanium than for silicon. The first Brillouin zones are of the same order, but silicon wave vector is divided into 60 equal bands whereas, for germanium, it is splitted into 300 strips. Using 300 bands for silicon changes conductivity values by less than 1%. Therefore calculating over 60 wave frequencies saves calculation times while keeping accuracy to an acceptable level. On the other hand, using only 60 bands over the spectrum can change by up to 10% of the conductivity values. To take a maximum of spectral information, we have choosen a large number (300) of bands.

IV. HEAT TRANSFER IN SILICON NANOSTRUCTURES

A. Films

New parameters (Tab.II) have been fitted to provide correct thermal properties in silicon and they are now used to study films with BTE resolution. As said earlier, BTE gives the possibility to study ballistic, mesoscopic and diffusive problems. Therefore, a thickness variation brings us to study nanofilms to thick films (or bulk). Ballistic phenomena is then more expected for nanofilms whereas diffusion occurs in thick films. Another way to observe ballistic behavior is to work with low temperatures. In these condition, low frequency modes are dominant (due to Bose-Einstein distribution) which means that phonon mean free path is larger (due to the relaxation time frequency dependence). On the other hand, at high temperatures, high frequency modes are dominant, which amounts to small phonon mean free path. Three phonon collisions are then more frequent, which drive the process to a diffusive scheme.

Figure 8 shows silicon surface unit conductance (W/m 2 K) versus its film thickness for several temperatures. According to the film assumption, the section perpendicular to z is supposed to be infinite. Therefore, conductance (W/K) is not available. In a film, the surface unit conductance G" reads:

G" = ϕ -∆T = k ∆z . (19)
Furthermore, in diffusive regime, when Fourier's law (Eqn.2) is matching the heat transfer, the conductivity, at a given temperature, is constant. In that case we get ln(G") = -ln(∆z) + ln(k). This result correspond to the right part of Figure (8).

For small lengths and at a given temperature, the surface unit conductance becomes constant when thickness becomes thinner. This scheme is due to ballistic phenomena and is viewed on curves left side. On the contrary to Fourier's regime, when G" is constant, the conductivity concept is questionnable since it depends on the system size (Eqn. 19).

The curved parts of G" (Fig. 8) are the results obtained in mesoscopic regimes. In this scheme, phonon mean free path is of the same order than the film thickness. Some phonons act as they were in a diffusive system. On the other hand, many phonons have a purely ballistic behavior. Consequently, the thermal conductivity concept is again questionnable.

Another benefit in using BTE resolution is that temperature fields in nanostructures can be obtained. In a diffusive regime, the temperature gradient is constant. In ballistic regime, it is the temperature which is mostly constant. Figure 9 shows thermal profiles along the z axis for a two-micron-thick-film. We can clearly see that Fourier's regime is not reached before 300K, which correspond almost to the right mesoscopic limitviewed on Figure (8). Ballistic regime is nearly reached at 10K. Between these two temperatures, mesoscopic regime prevails. This result confirms that thermal conductivity terms have to be used with care. It seems that in silicon films, it is not appropriate to use this concept below the micrometer scale.

In comparison with a simple model [START_REF] Yang | Thermal conductivity of core-shell and tubular nanowires[END_REF] , the surface unit conductance, calculated with a single linear group velocity, is overestimated compared to our model (Fig. 10). At 300K, some points are 30% higher than ours for the film simulation. These results show how important is to take into account the spectral dependency. Consequently phonon mean free paths (ℓ) are also spectrally dependent since ℓ = V g (ω, p)τ (ω, p).

Note that for a thickness beneath 20.10 -9 m, there are less than 40 primitive cells across the nanofilm. In that case, bulk dispersion properties are, in principle, no longer valid.

Correspondant results for these thicknesses are given (Fig. 8) only to show the numerical behavior of our code despite a physical concordance.

B. Wires

Silicon new relaxation time parameters are used to determine nanowire thermal properties. In comparison with nanofilms, speaking about thermal conductivity in nanowire could be taken out of sense. Nevertheless, representing the surface unit conductance versus the length do not present much interest for wires, since the thermal property changes also with its diameter. Therefore, we plot the temperature field to see, with the thermal gradient along the z axis, in which regime, ballistic, mesoscopic or diffusive, the nanowire, at a given temperature, is. For a 2micron long nanowire whose diameter is 115nm, Fourier's law applies on a large temperature band (Fig. 11). Using thermal conductivity concept to describes nanowire thermal properties seems then possible.

A temperature rise leads to Umklapp process domination which is a resistive process and then yields a diffusive regime. Similarly, a diameter reduction increases phonon collisions with the border, also a resistive process, and favours a diffusive regime. Therefore, thermal conductivity as silicon nanowire thermal property is suitable for larger temperature or smaller diameter.

For a given diameter, a shorter wire gives more possibility to have phonon mean free path of the same order as the wire length. Low temperature can also accentuate this character as phonon traveling length grows up. Other results have been obtained with D = 500nm and L = 2µm, or with D = 37nm and L = 150nm. Their temperature fields have the same shape than those shown in figure (11). This tends to consider that thermal conductivity is a valid concept in nanowires. However mesoscopic and ballistic regime can always be obtained in any nanostructures by reducing hugely the dimensions or/and the temperature.

We have calculated the conductivity for 2µm length nanowires at diffenrent temperatures and diameters (Fig. 12). We retrieve a same profile than analytical 9 , experimental [START_REF] Li | Thermal conductivity of individual silicon nanowires[END_REF] and Monte Carlo 47 data. However, a better agreement is found at high temperature for large diameters and at low temperature for small diameters. The boundary has been set here as purely isotropically scattering surface.

As seen in section III A 2, a diffuse to specular reflection ratio ρ smaller than one is expected for low temperatures. A fit on ρ (Tab.IV), is then done on our 2µm long and 115nm of diameter nanowire. It is used for other diameters (Fig. 13). Conductivity matches better at low temperature for large diameters, with an adjusted ρ than with ρ fixed at 1. Note that the ratio decreases with temperature. When temperature goes down, low frequency phonons are dominant, and their wavelength average increases (due to Bose-Einstein distribution).

Consequently, phonons will scatter less with the borders since some of their wavelengths will be larger than the nanowire roughness. Therefore, the ratio of specular to diffuse reflection goes down with temperature.

On the other hand, for small diameters, the conductivity obtained does not match well experimental data. This can be explained by the fact that with a small diameter, bulk dispersion data are no longer pertinent. At small scale, phonon modes become discrete whereas bulk dispersion is continue. The contribution of non-existing modes probably overestimates heat transfer.

For a 37nm diameter nanowire with a ratio of specular to diffuse reflection set equal to 1, the difference between our model predictions and Yang's simple model [START_REF] Yang | Thermal conductivity of core-shell and tubular nanowires[END_REF] On the contrary, we have seen that thermal conductivity is a relevant quantity in nanowires due to phonon collision with borders. In extremely small nanostructures, we have noticed that our treatment can be inproper. Phonon wave behaviour should probably be taken into account. Note that the method developed here can easily be generalized for transient heat transfer in order to study heat pulse propagation in nanostructures [START_REF] Terris | Numerical simulation of transient phonon heat transfer in silicon nanowires and nanofilms[END_REF] . The ratio of diffuse to specular reflection is equal to 1. B L (K -3 ) 2.0 10 -24 1.18 10 -24

  which increases considerably conductivity curve highest point. Thus, changing the impurety parameter A alters considerably the conductivity around 10K. Fitting then the three first parameters F , A, and B T to obtain correct values for low temperature undergo a mismatch around 140K to 300K. To avoid this trouble, Singh 33 proposes different relaxation time forms based on three different sections of the dispersion curves. Here, as for silicon, we want to use Holland's relaxation time forms (Tab.I) to model germanium thermal properties, where only four parameters are needed against 10 for Singh. Therefore, we solve directly the BTE to fit our parameters. Inquired values are based on Glassbrenner and Slack experimental data 32,43,46 . The cylinder dimensions have the same lengths than their sample (L = 20mm and D = 4.4mm). A first fit is done for T ≥ 100 K, where conductivity is less sensible to boundary collisions and to Normal transversal processes. Thus, B T U , B L and A parameters are the conductivity action switchs over 100K. The dominant band for tranverse normal process conductivity contribution is under 100K, which permits to change B T without disturbing our new values obtained for T ≥ 100K.

FIG. 1 :FIG. 4 :FIG. 5 :FIG. 6 :

 1456 FIG. 1: (Color online) Geometry representation

FIG. 7 :

 7 FIG. 7: (Color online) This study is done in a Germanium structure. The solid line is the conductivity obtained with Holland's method (relaxation times and phonon dispersion), with a sample length of L = 2.4mm. The dot line is the conductivity obtained with Holland's method but with Asen relaxation time parameters and its dispersion. Asen sample length is L = 3.8mm. The dash dot line is the conductivity resulting from Holland's method with Nilsson's phonons dispersion (L = 2.4mm). The hyphen line is the conductivity calculated with Asen parameters on Holland relaxation time forms with Nilsson's dispersion (L = 3.8mm). Dots (•) and (•) are conductivities obtained with BTE resolution but with our new relaxation times and Nilsson's phonon dispersion, on a sample of L = 20mm and D = 4.4mm. The wire is corresponding to ρ = 1 represented with (•) and the film to ρ = 0 drawn with (•) (Eqn.9). Cross dots (+) are Glassbrenner experimental data on a sample of L = 20mm and D = 4.4mm.

FIG. 8 :FIG. 9 :

 89 FIG. 8: (Color online) Film surface unit conductance versus thickness at different temperature.

FIG. 10 :FIG. 11 :

 1011 FIG. 10: (Color online) Surface unit conductance comparison between a simple model(Yang) and our model(Terris), of films set at 300K.

FIG. 12 :

 12 FIG. 12: (Color online) Nanowire themal conductivity. Comparison with experimental results of Li et al.[START_REF] Li | Thermal conductivity of individual silicon nanowires[END_REF] , analytical data of Chantrenne et al.[START_REF] Chantrenne | An analytical model for the thermal conductivity of silicon nanostructures[END_REF] and Monte Carlo simulations of Lacroix et al.[START_REF] Lacroix | Monte Carlo simulation of phonon confinement in silicon nanostructures: Application to the determination of the thermal conductivity of silicon nanowires[END_REF]

47

 47

FIG. 13 47 Impureties≤- 45 B 13 B

 13474513 FIG. 13: (Color online) Nanowire themal conductivity. Comparison with experimental results of Li et al.[START_REF] Li | Thermal conductivity of individual silicon nanowires[END_REF] , analytical datats of Chantrenne et al.[START_REF] Chantrenne | An analytical model for the thermal conductivity of silicon nanostructures[END_REF] and Monte Carlo simulations of Lacroix et al.[START_REF] Lacroix | Monte Carlo simulation of phonon confinement in silicon nanostructures: Application to the determination of the thermal conductivity of silicon nanowires[END_REF]

  are below 7%, but with ρ = 0.8, ot reaches 13%. For every thin wire, boundary scattering has an important resistive role which favours diffusive regime. If we further change the boundary conditions, a larger difference is obtained between our model and Yang's. Therefore, neglecting the spectral dependency can yield a rough answer.Silicon nanofilm surface unit conductance as silicon nanofilm field temperature have shown that thermal conductivity is not always a relevant quantity, since diffusive regime is only reached, at 1500K, for one micron thick. Even if optical phonons are not described, it had been viewed that at lower temperatures diffusive regime is only reached for thick films.

	since phonon dispersion changes.
	V. CONCLUSION
	This paper presents the resolution of Boltzmann Transport Equation with the Discrete
	Ordinate Method in semiconductors. Spectral and temperature dependencies have been
	taken into account to define thermal properties. The polynomial function and the cubic
	spline approximations, representing frequencies ω versus wave vector, bring us closer to
	reality. Different relaxation time models, which are made to take into account spectral
	dependency, are proposed in litterature. We have focused on the same relaxation time forms
	applied by Holland, which is oftenly used in literature. Thus, new relaxation times have
	been found to balance non-linear dispersion relations. Sensibilities over parameters defining
	semiconductor relaxation times are different for silicon and germanium. Therefore, for each
	semiconductor, a strategy has been developped to find its own parameters. A comparison
	with a simple model has put in forward the spectral dependency problem. Differences over
	30% can be obtained. It seems that simple models are correctly fitted for specific samples
	or temperatures. Our new parameters, associated to this paper model, permit to describe
	correctly germanium and silicon thermal properties over a large temperature band and over a
	large spatial scale. However, this method does not treat optical phonons and therefore it does
	not represent properly high temperature phenomena. Futhermore, the dispersion relations
	are taken from the bulk modes. Working on very short scales can undergo incorrect answers

TABLE II :

 II Parameters for silicon relaxation times

		Holland Asen-Palmer	Present work
	L (mm)	2.4	3.8	D = 4.4 and L = 20
	F	0.8	0.8	none
	A (s 3 )	2.410 -44 1.778610 -44	3.510 -45
	B T O (K -3 ) 1.010 -11 1.510 -11	7.310 -11
	B T U (s)	5.010 -18 4.510 -18	0.8910 -18
	B L (K -3 )	6.910 -24 9.010 -24	8.610 -24

TABLE III :

 III Parameters for germanium relaxation times

	ρ	0.8 0.81 0.82 0.83 0.8 0.86 0.9 0.94 0.97 1
	T (K) 10 20 40 60 80 100 125 150 175 ≥200

TABLE IV :

 IV Ratio of specular to diffuse reflection used in figure13for silicon nanowires


Damien Regnault

Rapport de Recherche RR2008-12 : Directed Percolation arising in Stochastic Cellular Automata Analysis

. Understanding these "simple" rules is a key step to analyze more complex systems. We present here a coupling between oriented percolation and ECA 178 and confirms observations made in [5] that percolation may arise in cellular automata. As a consequence this coupling shows that there is a positive probability that the ECA 178 does not reach a stable configuration with positive probability as soon as the initial configuration is not a stable configuration and α > 0.996. Experimentally, this result seems to stay true as soon as α > αc ≈ 0.5.

Introduction

A cellular automaton is a process where several cells, characterized by a state, evolve according to the states of their neighboring cells. Cellular automata can both model parallel computing and real life systems [START_REF] Sarkar | A brief history of cellular automata[END_REF] .

Historically they have been studied under synchronous dynamics where all the cells update at the same time. Meanwhile models of probabilistic cellular automata have emerged. Several studies focus on a model of cellular automata evolving synchronously but where some random errors can occur. In [START_REF] Toom | Stable and attractive trajectories in multicomponent systems[END_REF], Toom gives a 2D cellular automata capable of remembering one bit of information in presence of random error. This result is used in [START_REF] Gács | A simple three-dimensional real-time reliable cellular array[END_REF] to develop a 3D cellular automaton capable of reliable computation. Later on Gács proves the existence of a 1D cellular automaton exhibiting the same reliability [START_REF] Gács | Reliable cellular automata with self-organization[END_REF]. In [START_REF] Balister | Large deviations for mean fields models of probabilistic cellular automata[END_REF] the authors try to apply the mean field approach on a probabilistic model of cellular automata and show that complex behaviors cannot be explained by this method.

Several empirical studies have shown that the behavior of cellular automata changes drastically under asynchronous dynamics [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF][START_REF] Buvel | Structure in asynchronous cellular automata[END_REF][START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF][START_REF] Lumer | Synchronous versus asynchronous dynamics in spatially distributed systems[END_REF][START_REF] Schönfisch | Synchronous and asynchronous updating in cellular automata[END_REF]. Only few theoretical results are known. Mainly, either they concern specific cellular automata or show that it is difficult to describe the global behavior of cellular automata under probabilistic updates [START_REF] Balister | Large deviations for mean fields models of probabilistic cellular automata[END_REF][START_REF] Gács | Reliable computation with cellular automata[END_REF][START_REF] Gács | Reliable cellular automata with self-organization[END_REF][START_REF] Fukś | Non-deterministic density classification with diffusive probabilistic cellular automata[END_REF][START_REF] Fukś | Probabilistic cellular automata with conserved quantities[END_REF][START_REF] Regnault | Abrupt behavior changes in cellular automata under asynchronous dynamics[END_REF][START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF][START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF][START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF].

Percolation theory was introduced to model the fact that a liquid or a gas can flow through a solid due to porosity. Other applications were found for this model and it has been extensively study in the last decades on which probability theory made a lot of progress. A good introduction to percolation theory can be found in [START_REF] Grimmett | of Grundlehren der mathematischen Wissenschaften[END_REF]. Ising models, Potts models and percolation were unified into the random cluster model [START_REF] Fortuin | On the random cluster model. i. introduction and relation to other models[END_REF][START_REF] Grimmett | The Random-Cluster Model[END_REF]. We define here a coupling between oriented percolation and a "simple" probabilistic cellular automaton. This coupling shows that "simple" rules may embed very complex phenomena. The link between elementary cellular automata and percolation theory was already observed in experiments in [5] but it is the first time that a correlation is proved.

The probabilistic dynamics we study here is the α-asynchronous dynamics where each cell has an independent probability α to be updated and a probability 1 -α to stay in its current state at each time step. A particular class of cellular automata is the 256 elementary cellular automata (ECA). This class gathers the "simplest" cellular automata : cells are placed on a line, they are characterized by a state which is 0 (white) or 1 (black) and they can communicate only with their two closest neighbors. Nevertheless, studies have shown that this class exhibits a wide range of behavior including Turing universality [START_REF] Cook | Universality in elementary cellular automata[END_REF]. Even if this class seems simple, questions remain open in the deterministic synchronous case such as the intrinsic universality of ECA 110 [START_REF] Ollinger | The intrinsic universality problem of one-dimensional cellular automata[END_REF]. Current works study this class under α-asynchronous dynamics [START_REF] Regnault | Abrupt behavior changes in cellular automata under asynchronous dynamics[END_REF][START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF][START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF], in particular the 64 cellular automata for which the two configurations all black and all white are stable. The understanding of these "simple" rules is a key step to understand more complex phenomena. First in [START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF] it was shown that when only one cell is updated at each time step (which may be under certain circumstances the limit as α → 0) the behavior of these cellular automata are similar to behavior of coupon collectors or random walks. In [START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF], the behavior of some of these cellular automata has been determined under α-asynchronous dynamics, and the authors have isolated some cellular automata exhibiting rich behavior such as phase transitions. The elementary cellular automaton studied here ECA 178, FLIP-IF-NOT-ALL-EQUAL is one of these complex automata. These automata are hard to study and only few results are known yet. Here we present a new result on the ECA 178 and show that there exists a positive probability that the process will never reach a stable configuration when α > 0.996 even when the initial configuration contains only one black cell. This is the first result proved for this automaton. Moreover ongoing work shows that ECA 178 arises naturally in the study of 2D Minority [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF] which is a model of anti-ferromagnetism in physics [START_REF] Ovchinnikov | Antiferromagnetic ising chain in a mixed transverse and longitudinal magnetic field[END_REF] and also one of the simplest non-monotonic gene network model in biology. Since the proof of this result is based on a coupling between the space-time diagram of ECA 178 and oriented percolation on a graph, it tends to support the fact that the behavior of this automaton is indeed complex since very little is known on directed percolation yet.

2 Asynchronous cellular automata

Definition

We give here a formal definition of ECA 178. The next part presents informally its behavior and the underlying difficulties of its analysis.

Definition 1 (Configuration). We denote by Z the set of cells and Q = {0, 1} the set of states (0 stands for white and 1 for black in the figures). The neighborhood of a cell i consists of the cells i -1, i and i + 1. A configuration c is a function c : Z → Q; c i is the state of the cell i in configuration c. Definition 2 (ECA 178: FLIP-IF-NOT-ALL-EQUAL). The rule of a cellular automaton is a function which associates a state to a neighborhood. The rule δ of the ECA 178 is defined as follows:

δ(c i-1 , c i , c i+1 ) = c i if c i-1 = c i = c i+1 1 -c i otherwise
Time is discrete and in the classic deterministic synchronous dynamics all the cells of a configuration are updated at each time step according to the transition rule of the cellular automaton (see figure 1). Here we consider a stochastic asynchronous dynamics where only a random subset of cells is updated at each time step. Definition 3 (Asynchronous dynamics). Given 0 < α 1, we call αasynchronous dynamics the following process : time is discrete and c t denotes the random variable for the configuration at time t. The configuration c 0 is the initial configuration. The configuration at time t + 1 is the random variable defined by the following process : each cell has independently a probability α to be updated according to the rule δ (we say that the cell fires at time t) and a probability 1 -α to remain in its current state. A cell is said active if its state changes when fired.

Definition 4 (Stable configuration). A configuration c is a stable if for all

i ∈ Z, δ(c i-1 , c i , c i+1 ) = c i .
ECA 178 (FLIP-IF-NOT-ALL-EQUAL) admits only two stable configurations : the configurations all white and all black.

Definition 5 (Convergence). We say that a random sequence (c t ) t 0 defined by ECA 178 converges under α-asynchronous dynamics if there exists t < ∞ such that c t is a stable configuration. We denote by P α (c 0 ) the probability that such a t exists.

From the definition of stable configuration, it follows that if there exists t such that c t is a stable configuration then for all t ′ t the configuration c t ′ is the same stable configuration. Note that since the configuration is infinite, only specific initial configurations may converge with positive probability. Here we will consider only a particular initial configuration which is very "close" to a stable configuration and show that when α is large enough, being this close is not enough to guarantee convergence almost surely.

Definition 6 (Initial configuration). We define c init as the configuration where c init 0 = 1 and for all i = 0, c init i = 0.

From now on, we will consider that the initial configuration is always c init . The configuration c init differs from the configuration all white by only one cell. Nevertheless we show the following result :

Theorem 1 (Main result). If α 3 80/81 ≈ 0.996 then P α (c init ) < 1.
Section 4 is dedicated to the proof of this result. This is the first result on ECA 178. This result shows that this rule can exhibit very complex behavior and shows how simple rules may turn out to be hard to analyze. Before the proof, the following section exposes experimental results on the behavior of ECA 178.

Discussion

In [START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF] it was conjectured that ECA 178 admits a phase transition which occurs experimentally at α = α c ≈ 0.5. Figure 1 illustrates the changes in the space time diagrams of ECA 178 when α varies. In [START_REF] Fatès | Asynchronous behaviour of double-quiescent elementary cellular automata[END_REF] it was proven that this automaton behaves as a non-biased random walk on a finite configuration with periodic boundary condition under the fully dynamics (when only one random cell fires at each time step). This proof can easily be extended to infinite configurations when c 0 = c init to prove that its converges in polynomial time to all white almost surely under the fully asynchronous dynamics.

When 0 < α < α c , despite of the fact that some small "errors" may occur, the global behavior seems to be similar to the fully asynchronous dynamics. When α > α c the behavior changes drastically : an alternating background pattern (0101010) appears and extends quickly in expense of the black and white regions preventing the configuration from ever reaching a fixed point. Cells inside a big white or black region are inactive whereas cells of a 010101 region are all active. When α is very small, regions of 010101 are highly unstable and the presence of patterns 010101 is marginal. Nevertheless this pattern does not exist in the fully asynchronous case and since the study of this dynamics relies on a perfect symmetry between black and white regions, the emergence of a third kind of region, which behave drastically differently, prevents us from deriving a lower bound from the fully asynchronous dynamics. We believe that any lower bound on α c would be a huge achievement.

We prove next that when α > 0.996 there is a strictly positive probability that the process will not reach the stable configuration all white even if only one cell is black in the initial configuration. The global behavior here is thus no more related to a unbiased random walk. Since rule 178 acts symmetrically on black and white states the same result holds when the initial configuration has only one white cells. Big white regions and big black regions tends to disappear in favor of 0101 patterns and our result confirms the fact that the pattern 0101 ends up dominating in the configuration when α > 0.996. Finally our proof is based on a coupling between cellular automaton and oriented percolation. This correlation was already spotted in [5] but it is the first time that it is theoretically proved and the emergence of oriented percolation in ECA 178 is also a strong evidence of the richness of its behavior.

3 Oriented percolation on (Z + ) 2 Definition 7 (Oriented bond percolation). Consider a probability p and the randomly labeled graph L(p) = ((Z + ) 2 , E) where (Z + ) 2 is called the set of sites and E the set of bonds. For all i, j ∈ Z + , there are oriented bonds between site (i, j) and sites (i + 1, j) and (i, j + 1). Each bond has independently a probability p to be labeled open and a probability 1 -p to be labeled closed. Definition 8 (Open cluster). We denote by C the open cluster of site (0, 0): a site (i, j) is in C if and only if there is an oriented path from site (0, 0) to site (i, j) only made of open bonds. We call θ(p) the propability that C is infinite ( i.e. that there exists an infinite open path from cell (0, 0)). It is easy to show that θ(p) is an increasing function of p. Moreover there exists a critical value p c such that θ(p) > 0 for p > p c . Bounds on this critical value can be found in [START_REF] Grimmett | of Grundlehren der mathematischen Wissenschaften[END_REF].

Theorem 2 (Critical value [START_REF] Grimmett | of Grundlehren der mathematischen Wissenschaften[END_REF]). There exists a critical value p c such that if p < p c then θ(p) = 0, and if p > p c then θ(p) > 0. Moreover, 0.6298 < p c < 2/3.

Coupling cellular automaton 178 with percolation

There is no notion of time in percolation but the height will stand for it in our coupling. Indeed in order to know if a site of height t + 1 is in the open cluster or not, we only need information about sites of height t. In a cellular automata in order to know the state of a cell at time t + 1, we only need to know the states of cells at time t. Definition 9 (Height). The height of a percolation site (i, j) is the length of any path from (0, 0) to (i, j) in L(p), that is to say i + j. We denote by C t the sites of height t which are in the open cluster C. The height of a bond is the height of its origin.

Definition 10 (Candidate).

A site is a candidate of height t + 1 if and only if at least one of its predecessors is in C t . We denote by Ĉt+1 the set of candidates of height of t + 1.

Clearly for all t > 0 we have C t ⊂ Ĉt . Figure 4 illustrates the notion of height and candidate. In this part, (c t ) 0 denotes the random sequence of configurations updated according to rule 178 under α-asynchronous dynamics where c 0 = c init . Definition 11 (Mapping). We define the set of cells T t of configuration c t as follows : cell c t i is in T t if and only if -t i t and i ≡ t mod 2. Let T = ∪ ∞ t=0 T t . We define g : (Z + ) 2 → T as the bijection which associates the percolation site (i, j) to the cell 2i -⌈ i+j 2 ⌉ of configuration c i+j . From these definitions, it follows that the image of the sites of height t in L(p) by g are the cells T t in configuration c t .

Figure 4 shows the mapping of L(p) on a space-time diagram. We can notice that the cells of T correspond exactly to the black cells of the space-time diagram of figure 1 under synchronous dynamics. Our aim is to define a coupling such that the corresponding cells of sites in C will always be active. The following criterion formulates this property. Definition 12 (Correspondence criterion). We say that a space-time diagram (c t ) t>0 and a labelled directed graph L(p) satisfy the correspondence criterion at time t if and only if the cells of g(C t ) are all active. We say that they satisfy the correspondence criterion if and only if they satisfy the correspondence criterion for all t 0( i.e. the cells of g(C) are all active).

Since in c init 0 site (0, 0) ∈ C is active, the configuration c 0 = c init and any randomly labeled directed graph L(p) always satisfy the correspondence criterion at time 0. Moreover if they satisfy the correspondence criterion and the open cluster is infinite in L(p) then for all t, c t admits at least one active cell and thus the sequence (c t ) does not converge. Figure 5 gives a configuration which satisfies the correspondence criterion with the directed graph of figure 4 at time 8.

Consider a configuration c t such that the correspondence criterion is true at time t. We want in our coupling that the correspondence criterion stays true at time t + 1. Consider a site in Ĉt+1 , this site may be in C. If it is the case, the cell c t+1 i corresponding to this site has to be active. Thus, we have to focus on c t i at time t and design a coupling such that this cell is active at time t + 1 if the corresponding site is in the open cluster. We say that there is a constraint on this cell.

Definition 13 (Constrained cells). A cell

c t i is constrained at time t if and only if c t+1 i ∈ T and g -1 (c t+1 i ) is in Ĉt+1 .
We may have to force a constrained cell to be active at time t + 1 in our coupling. This turn out to be possible because a constrained cell always has an active cell in its neighborhood when the correspondence criterion is verified (Lemma 1). It follows that one can associate to each constrained cell a partner which is an active cell in its neighborhood (Definition 14). Firing these two cells makes the constrained cell active at time t + 1 (Lemma 2) which can be coupled with the opening of the bonds when α is large enough (Theorem 3).

Lemma 1. If (c t ) t 0 and L(p) verify the correspondence criterion at time t ′ each constrained cell of configuration c t ′ has an active neighbor.

Proof. Suppose that cell c t i is constrained at time t. Then site (k, l) = g -1 (c t+1 i ) is in Ĉt+1 . Thus at least one of the two sites (k, l -1) and (k -1, l) is in C t . Since the correspondence criterion is verified at time t, at least one of the two cells g(k, l -1) = c t i+1 and g(k -1, l) = c t i-1 is active. Definition 14 (Partner). The partner of a constrained cell c t i is defined as follows :

-if c t i is the pointed cell in the neighborhood or then its partner is c t i-1 .

-if c t i is the pointed cell in the neighborhood or then its partner is c t i+1 . Figure 6 illustrates the constrained cells of Figure 4 and their partners. Since two cells of T cannot be neighbors, two constrained cells cannot be neighbors. Moreover since the partner of a constrained cell is a neighbor of this cell then a cell cannot be at the same time constrained and the partner of an other cell. Note that however a cell may be the partner of two constrained cells. Lemma 2. For all t ′ > 0, if (c t ) t 0 and L(p) verify the correspondence criterion at time t ′ , each constrained cell at time t ′ has a partner and if these two cells fire at time t ′ then the constrained cell is active at time t ′ + 1.

Proof. Suppose that cell c t i is constrained at time t. Then w.l.o.g. we suppose that the state of c t i is 1 (the other case is symmetric). We do a case study on the states of its neighboring cells and show that in every cases, if c t i and its partner fire then c t+1 i is active. This case study is done in figure 7. Proof. Consider a random sequence (c t ) t 0 of configurations updated according to rule 178 under α-asynchronous dynamics where c 0 = c init and a randomly labeled graph L(p). Assume α 3 1 -(1 -p) 4 . We design a coupling between these two processes.

The coupling is defined recursively for all t between c t and bonds of height t in L(p). At time t we have to label the edges of height t of L such that each edge open with independent probability p. We have to chose which cells fire such that each cell fires with independent probability α. We also design our coupling such that if at least one of the two bonds which ends to a site of Ĉt+1 is open then the corresponding cell c t+1 i is active. In order to do so, we use Lemma 2 and assuming that the correspondence criterion is true at time t, we force the constrained cell c t i and its partner to fire. Since the correspondence criterion is true at time 0, it will recursively stay true for all t.

To achieve this, we partition the cells of c t and the bonds of height t into buckets. Each bucket consists in :

type 1 : a unique cell c t i if it is neither constrained nor the partner of any other cell.

type 2 : a unique bond b if it does not end to a site of Ĉt+1 .

type 3 : two cells c t i and c t i+ǫ with ǫ = 1 or -1 and the two bonds of height t pointing to the site corresponding to cell c t+1 i+ǫ if c t i is the partner of only one constrained cell c t i+ǫ . -type 4 : three cells c t i-1 , c t i and c t i+1 and the four bonds of height t pointing to the sites corresponding to cells c t+1 i-1 and c t+1 i+1 if c t i is the partner of the two constrained cells c t i-1 and c t i+1 . One can easily verify that each bond of height t and each cell of c t belongs to exactly one bucket. We assign to each bucket k an independent random variable X t k uniformly distributed in [0, 1]. Now we define the coupling within each bucket:

type 1 : if X t k < α then c t i fires and if X t k > α then c t i does not fire. - The probability that all cells fire is α 3 and the probability that at least one bound is open is 1 -(1 -p) 4 . Since α 3 1 -(1 -p) 4 , the three cells always fire when at least one bond is open in this coupling.

Thus as soon as one edge ending to site of Ĉt+1 is open, the corresponding cell at time t + 1 is active. Thus the correspondence criterion stays true at time t + 1. Since the correspondence criterion is true at time 0, it will recursively stay true for all t. If p > p c then θ(p) > 0 which means that for all t 0 there exists a cell of height t which is in the open cluster with positive probability. Thus there exists an active cell in c t for all t 0, with positive probability. Then if α 3 1 -(1 -p c ) 4 then P α (c init ) < 1.

Theorem 2 and theorem 3 yields the theorem 1.

Figure 1

 1 Figure 1 presents different space-time diagrams of ECA 178 for different values of α. The initial configuration consists in one single black cell and is displayed horizontally at the bottom of the diagram (time flows upwards).

αFig. 1 .

 1 Fig. 1. ECA 178 under different dynamics (α = 0 stands for fully asynchronous dynamics, for this diagram only one every 50 time step is displayed).

Figure 2

 2 Figure 2 illustrates several examples of oriented percolation for different values of p. Only open bonds are shown in the figure. The main question of percolation theory is the size of the open cluster.

Fig. 2 .

 2 Fig. 2. Oriented percolation with different probability of open bonds.

Fig. 3 .

 3 Fig. 3. An example of sites and candidates of height 8 and 9. All bonds (indifferently open or closed) are represented.

Fig. 4 .

 4 Fig. 4. Mapping of the graph L(p) on the space-time of a cellular automaton; the cells of T are colored in black.

Time and Height 9 Time and Height 8 }Fig. 5 .

 985 Fig. 5. Cells of T 8 and T 9 are colored in red and blue. Active cells are marked by a red dot. Red arrows link the sites of C 8 to their corresponding cells in c 8 . In this example, these cells are active in c 8 . Thus the correspondence criterion is verified at time 8.

Fig. 6 .

 6 Fig.6. Blue arrows map the site of Ĉ9 to their corresponding constrained cells. These constrained cells are marked by a blue cross. Rounds surround a constrained cell and its partner.

:Fig. 7 . 2 Theorem 3 .

 723 Fig. 7. proof of lemma 2

  type 2 : if X t k < p then b is open and if X t k > p then b does is closed. -type 3 : bounds are open and cells fires according to this diagram : Each bond is open with probability Bonds b and b ′ are opened with probability p 2 , b is open and b ′ is closed with probability p(1 -p) and b is closed and b ′ is open with probability p(1 -p). Thus each bond is open independently of the other. Same thing holds for the cells. Since α 3 1 -(1 -p) 4 , we have α 2 -2p + p 2 > 0 and the probability that at least one bond is open is less than the probability that both cells fire.type 4 : As in the previous case we define a coupling which respect the distribution of probability and the independence of updates/labeling such that:

Acknowledgements: Thanks to Nicolas Schabanel and Éric Thierry for their useful remarks that helped to improve the writing of the paper.