format: text

text:
# Turbo codes: the phase transition.

## 1 Introduction.

Communication through a noisy channel is a central problem in Information Theory . Error correcting codes are a widespread method for compensating the information corruption due to the noise, by cleverly increasing the redundancy of the message. Turbo codes  are a recently invented class of error correcting codes with nearly optimal performances. They allows reliable communication (i.e. very low error per bit probability) with practical communication rates.

It is known, since the work of Sourlas , that there exists a close relationship between the statistical behavior of error correcting codes and the physics of some disordered spin models. Recently the tools developed in statistical physics have been employed in studying Gallager-type codes .

In Ref.  the equivalence discovered by Sourlas is extended to turbo codes, and the basic features of the corresponding spin models are outlined. A remarkable property of a large family of turbo codes, presented in Ref. , is the existence of a no-error phase. In other words the error probability per bit vanishes beyond some critical (finite) signal to noise ratio. In Ref.  some intuitive arguments supporting this thesis are given. Some analytical results concerning the critical value of the signal to noise ratio are announced without giving any derivation. These results are compared with numerical simulations.

In this paper we present the analytical results in their full generality, and explain their derivation. We prove the existence of the no-error phase and find the condition for its local stability. This condition is derived in two different approaches. In the first one we study the asymptotic dynamics of the decoding algorithm. In the second approach we use replicas and establish the condition for stability in the full replica space. Local stability is a necessary but not sufficient condition for the stability of the no-error phase. The critical signal to noise ratio obtained from local stability is the correct one only if the phase transition is a second order one: in the general case it is only a lower bound.

The spin models which are equivalent to turbo codes have the following statistical weight :

$`𝒫(𝝈^{(1)},𝝈^{(2)}|𝑱,\beta )`$ $``$ $`{\displaystyle \frac{1}{Z(𝑱,\beta )}}{\displaystyle \underset{i=1}{\overset{N}{}}}\delta (ϵ_{\rho (i)}(𝝈^{(1)}),ϵ_i(𝝈^{(2)}))e^{\beta _{k=1}^2H^{(k)}(𝝈^{(k)})}`$ (1.1)
$`H^{(k)}(𝝈)`$ $``$ $`{\displaystyle \underset{i=1}{\overset{N}{}}}J_i^{(k)}ϵ_i(𝝈){\displaystyle \underset{i=1}{\overset{N}{}}}h_i^{(k)}\eta _i(𝝈)`$ (1.2)
The dynamical variables of the model are the spins $`𝝈^{(k)}\{\sigma _1^{(k)},\mathrm{},\sigma _N^{(k)}\}`$ with $`k=1,2`$. We shall choose them to be Ising spins 222This corresponds to considering codes which works with a binary alphabet., that is $`\sigma _i^{(k)}=\pm 1`$. The spins enters in the hamiltonians $`H^{(k)}(𝝈)`$ through the local interaction terms $`ϵ_i(𝝈)`$ and $`\eta _i(𝝈)`$ which are products of $`\sigma `$’s. Their exact form can be encoded in two set of numbers $`\kappa (j;1)=0,1`$ and $`\kappa (j;2)=0,1`$ as follows: $`ϵ_i(𝝈)_{j=0}^r\sigma _{ij}^{\kappa (j;1)}`$ and $`\eta _i(𝝈)_{j=0}^r\sigma _{ij}^{\kappa (j;2)}`$. In order to fix completely our notation we set $`\kappa (0;1)=\kappa (0;2)=1`$. The quenched variables are:

* the couplings $`𝑱\{J_i^{(k)};h_i^{(k)}\}`$, whose distribution $`𝒫(𝑱)_{i,k}P(J_i^{(k)})P(h_i^{(k)})`$ satisfies the conditions $`𝑑J_i^{(k)}P(J_i^{(k)})J_i^{(k)}>0`$ and $`𝑑h_i^{(k)}P(h_i^{(k)})h_i^{(k)}>0`$;
* the permutation $`\rho :\{1,\mathrm{},N\}\{1,\mathrm{},N\}`$, which has uniform distribution.

It is convenient to impose a fixed boundary condition at one end of the chain (i.e. $`\sigma _i=+1`$ for $`i0`$) and a free boundary condition at the other end. The model is composed by two one dimensional substructures (chains), which interact through the Kronecker delta functions in Eq. (1.1). When the average over permutations is taken into account this interaction turns into a mean field one. This interplay between the two subsystems, each one possessing a one dimensional structure, and the mean field interaction which couples them is clearly displayed by the analytical calculations. For further explanations on Eqs. (1.1-1.2) and their motivation we refer to .

The paper is organised as follows. In Sections 2 and 3 we present a first derivation of the stability condition. We write a “mean field” equation which describes the dynamics of the decoding algorithm (Sec. 2), we show that it possesses a no-error fixed point and then study its behavior in a neighbourhood of this fixed point (Sec. 3). Thanks to this derivation we will understand how this fixed point is reached. In Section 4 replicas are introduced in order to compute the average over the permutations. We exhibit the no-error saddle point. In Section 5 the stability of the no-error saddle point is studied by diagonalizing the second derivative of the free energy. Finally in Section 6 the validity of our calculations is discussed. Appendix A collects some useful (although simple) facts of algebra. In Appendix B the type of integral equations which appear in Section 3 is studied in detail.

## 2 A “mean field” equation for the decoding algorithm.

Some properties concerning the models defined by Eqs. (1.1-1.2) can be obtained by considering the “turbo decoding” algorithm and making some factorization hypothesis. These hypothesis enable us to obtain a recursive integral equation for the probability distribution of a local field. They can be justified on heuristic grounds and arguments of this kind will be given later in this Section. Moreover the replica calculation presented in the Section 4 does support our arguments. In particular this approach allows us to derive the critical noise below which “perfect” decoding is possible.

Turbo decoding is an iterative algorithm. The iteration variables are the fields $`𝚪^{(k)}\{\mathrm{\Gamma }_1^{(k)},\mathrm{},\mathrm{\Gamma }_N^{(k)}\}`$ with $`k=1,2`$. The step $`t`$ of the turbo decoding algorithm is defined as follows :

$`\mathrm{\Gamma }_i^{(1)}(t+1)`$ $`=`$ $`{\displaystyle \frac{1}{\beta }}\text{arctanh}\left[ϵ_{\rho ^1(i)}(𝝈)_{\mathrm{\Gamma }^{(2)}(t)}^{(2)}\right]\mathrm{\Gamma }_{\rho ^1(i)}^{(2)}(t)`$ (2.1)
$`\mathrm{\Gamma }_i^{(2)}(t+1)`$ $`=`$ $`{\displaystyle \frac{1}{\beta }}\text{arctanh}\left[ϵ_{\rho (i)}(𝝈)_{\mathrm{\Gamma }^{(1)}(t)}^{(1)}\right]\mathrm{\Gamma }_{\rho (i)}^{(1)}(t)`$ (2.2)
The expectation value $`_{\mathrm{\Gamma }^{(k)}}^{(k)}`$ is intended to be taken with respect to the Boltzmann weight with the modified hamiltonian $`H^{(k)}(𝝈)_{i=1}^N\mathrm{\Gamma }_i^{(k)}ϵ_i(𝝈)`$. The iteration variables $`\mathrm{\Gamma }_i^{(k)}`$ should be interpreted as external fields conjugate to the operators $`ϵ_i(𝝈^{(k)})`$. They describe, in an approximate way, the action of each of the two chains on the other one.

In order to lighten the notation, let us write Eqs. (2.1-2.2) in the form:

$`𝚪^{(k)}(t+1)=F_\rho ^{(k)}(𝚪^{(k^{})}(t),𝑱^{(k^{})})`$ (2.3)
with $`k^{}=2`$ if $`k=1`$, and $`k^{}=1`$ if $`k=2`$. Due to the randomness in the couplings $`𝑱`$, the fields $`𝚪`$ are random variables. Equation (2.3) implies an integral equation for the probability distribution of $`𝚪`$:

$`𝒫_{t+1}(𝚪^{(k)})={\displaystyle 𝑑𝚪^{(k^{})}𝑑𝑱^{(k^{})}𝒫_t(𝚪^{(k^{})},𝑱^{(k^{})})\delta \left[𝚪^{(k)}F_\rho ^{(k)}(𝚪^{(k^{})},𝑱^{(k^{})})\right]}`$ (2.4)
Let us state a few approximations which allow us to reduce Eq. (2.4) to a much simpler one.

* We make the substitution $`𝒫_t(𝚪^{(k^{})},𝑱^{(k^{})})𝒫_t(𝚪^{(k^{})})𝒫(𝑱^{(k^{})})`$ in Eq. (2.4). This yields a closed integral equation describing the evolution of the distribution $`𝒫_t(𝚪^{(k)})`$.
* We neglect correlations between the fields at different sites:

$`𝒫_t(𝚪^{(k)}){\displaystyle \underset{i=1}{\overset{N}{}}}\pi _{i,t}^{(k)}(\mathrm{\Gamma }_i^{(k)})`$ (2.5)

These two hypothesis imply that Eq. (2.4) is equivalent to:

$`\pi _{i,t+1}^{(k)}(y)`$ $`=`$ $`{\displaystyle _{\mathrm{}}^+\mathrm{}}𝑑\pi _t^{(k^{})}[𝒙]{\displaystyle 𝑑𝒫[𝑱]\delta \left(y\frac{1}{\beta }\text{arctanh}\left(ϵ_{\widehat{\rho }(i)}(𝝈)_{𝑱,𝒙}\right)+x_{\widehat{\rho }(i)}\right)}`$ (2.6)
$`d\pi _t^{(k^{})}[𝒙]`$ $``$ $`{\displaystyle \underset{i=1}{\overset{N}{}}}dx_i\pi _t^{(k^{})}(x_i)`$ (2.7)
where $`\widehat{\rho }`$ is the appropriate permutation of $`\{1,\mathrm{},N\}`$, i.e. $`\widehat{\rho }=\rho ^1`$ if $`k=1`$ and $`\widehat{\rho }=\rho `$ if $`k=2`$. The expectation value $`_{𝑱,𝒙}`$ on the right hand side of Eq. (2.6) has to be taken with respect to the hamiltonian $`H(𝝈)_{i=1}^N(J_i+x_i)ϵ_i(𝝈)_{i=1}^Nh_i\eta _i(𝝈)`$.

Let us now define a field distribution averaged over the permutations and the sites:

$`\pi _t^{(k)}(x){\displaystyle \frac{1}{N!}}{\displaystyle \underset{\rho }{}}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}\pi _{i,t}^{(k)}(x|\rho )`$ (2.8)
where we made explicit the dependence of $`\pi _{i,t}^{(k)}`$ upon the specific permutation $`\rho `$ which defines the code. We can now state our last approximation.

* We make the substitution $`\pi _{i,t}^{(k)}(x|\rho )\pi _t^{(k)}(x)`$ on the right hand side of Eq. (2.6).

This yields a recursive equation for $`\pi _t^{(k)}`$:

$`\pi _{t+1}(y)={\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle _{\mathrm{}}^+\mathrm{}}𝑑\pi _t[𝒙]{\displaystyle 𝑑𝒫[𝑱]\delta \left(y\frac{1}{\beta }\text{arctanh}\left(ϵ_i(𝝈)_{𝑱,𝒙}\right)+x_i\right)}`$ (2.9)
The indices $`(k)`$ and $`(k^{})`$ have been dropped since we can define $`\pi _t=\pi _t^{(1)}`$ for $`t`$ odd, and $`\pi _t=\pi _t^{(2)}`$ for $`t`$ even, or vice-versa. A byproduct of this heuristic derivation is the expression for the probability distribution of the expectation values $`ϵ_i(𝝈)`$ after $`t`$ iterations of the turbo decoding algorithm: $`𝒫_t(ϵ)=\frac{1}{N}_{i=1}^N_{\mathrm{}}^+\mathrm{}𝑑\pi _t[𝒙]𝑑𝒫[𝑱]\delta \left(ϵϵ_i(𝝈)_{𝑱,𝒙}\right)`$.

Let us discuss the validity of the approximations made in deriving Eq. (2.9).

* These approximations should be accurate in the thermodynamic limit for a generic random permutation $`\rho `$. The reason is that the correlations produced by Eqs. (2.1-2.2) have short range: $`ϵ_i(𝝈)`$ and $`ϵ_j(𝝈)`$ have a significant correlation only if $`|ij|`$ is less than some characteristic length. The random permutation $`\rho `$ reshuffles the sites so that the correlation between two fields $`\mathrm{\Gamma }_i^{(k)}`$ and $`\mathrm{\Gamma }_j^{(k)}`$ is vanishing with high probability if $`|ij|`$ is required to be “small”. The correlations which “survive” (non vanishing only between “distant” sites) are irrelevant when computing the expectation values of local operators. In order to make this last assertion plausible, let us suppose that, for each site $`i`$, we can find a “large” 333Here “large” means that $`lim_N\mathrm{}L(N)=\mathrm{}`$. interval $`[iL(N),i+L(N)]`$ of the chain, such that the correlations between the couplings inside the interval are negligible. The expectation value $`ϵ_i(𝝈)_{𝑱,𝒙}`$ will not depend (as $`N\mathrm{}`$) upon the couplings outside $`[iL(N),i+L(N)]`$ (this is always true in one dimension at non zero temperature) and can be then safely computed without taking into account the correlations. It is easy to find a similar argument concerning the correlations between $`𝚪^{(k^{})}`$ and $`𝑱^{(k^{})}`$ in Eq. (2.4).
* This is the probabilistic analogue of the replica symmetric approximation. Let us consider the fixed point equation $`\pi _{t+1}=\pi _t`$ corresponding to the dynamics defined by Eq. (2.9). It is remarkable that this fixed point equation coincides with the saddle point equation obtained by the standard replica method in the replica symmetric approximation (see Section 4). This fact confirms our conclusions about the relevance of the various approximations.

## 3 The behavior of the decoding algorithm.

Equation (2.9) is the final outcome of our heuristic derivation. We want to study its behavior when the distribution $`\pi (x)`$ is concentrated on large values of the field $`x`$, that is when the error probability is very small. In this regime the most relevant spin configuration satisfies $`ϵ_i(𝝈)=+1`$ for each $`i=1,\mathrm{},N`$. The lowest excitations are such that $`ϵ_i(𝝈)=1`$ only on a few sites. The first crucial point will be to understand that, for a class of hamiltonians of the type (1.2) (which will be defined as “recursive ”), the energy to be paid for flipping a single $`ϵ`$ variable diverges in the thermodynamic limit. The second point will be to evaluate the energy to be paid for flipping two $`ϵ`$ variables. In order to treat both these passages in full generality it is convenient to use an algebraic bookkeeping technique which we shall soon explain. The results concerning these two points will be useful again in Section 5.

A preliminary step consists in making the change of variables $`X_ie^{2\beta x_i}`$ and introducing the corresponding distribution function $`Q_t(X)dX=\pi _t(x)dx`$. Low $`X`$’s correspond then to large local fields, i.e. to low error probability. The result is

$`Q_{t+1}(Y)={\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle _0^{\mathrm{}}}𝑑Q_t[𝑿]{\displaystyle 𝑑𝒫[𝑱]\delta \left(Y\frac{1}{X_i}\frac{Z(ϵ_i(𝝈)=1;𝑱,𝑿)}{Z(ϵ_i(𝝈)=+1;𝑱,𝑿)}\right)}`$ (3.1)
where

$`Z(ϵ_i(𝝈)=ϵ;𝑱,𝑿)Z_i(ϵ)={\displaystyle \underset{𝝈:ϵ_i(𝝈)=ϵ}{}}e^{\beta H(𝝈)}{\displaystyle \underset{k=1}{\overset{N}{}}}X_k^{\frac{1}{2}(1ϵ_k(𝝈))}`$ (3.2)
with $`H(𝝈)=_iJ_iϵ_i(𝝈)_ih_i\eta _i(𝝈)`$. Let us introduce some notations in order to write down the small $`X`$ expansion of $`Z_i(ϵ)`$: $`(k_1,\mathrm{},k_l)`$ is an $`l`$-uple (not ordered) of integers in $`\{1,\mathrm{},i1,i+1,\mathrm{},N\}`$; $`𝝈_0`$ is the configuration such that $`ϵ_i(𝝈)=+1`$ for all the sites $`i`$; $`𝝈(k,l,m,\mathrm{})`$ is the configuration such that $`ϵ_j(𝝈)=1`$ if $`j=k,l,m,\mathrm{}`$ and $`ϵ_j(𝝈)=1`$ otherwise (there is at most one such configuration once the boundary conditions have been specified); $`E_0H(𝝈_0)`$ is the energy of the ordered configuration; finally $`\mathrm{\Delta }(k,l,m,\mathrm{})H(𝝈(k,l,m,\mathrm{}))H(𝝈_0)`$. The following expressions are straightforward:

$`Z_i(+1)=e^{\beta E_0}{\displaystyle \underset{l=0}{\overset{N1}{}}}{\displaystyle \underset{(k_1,\mathrm{},k_l)}{}}X_{k_1}\mathrm{}X_{k_l}e^{\beta \mathrm{\Delta }(k_1,\mathrm{},k_l)}`$ (3.3)
$`Z_i(1)=X_ie^{\beta E_0}{\displaystyle \underset{l=0}{\overset{N1}{}}}{\displaystyle \underset{(k_1,\mathrm{},k_l)}{}}X_{k_1}\mathrm{}X_{k_l}e^{\beta \mathrm{\Delta }(i,k_1,\mathrm{},k_l)}`$ (3.4)
The “bookkeeping technique ” which we shall adopt in treating the above expansions consists in using the algebra of “generating polynomials” . This approach allows us to consider a general hamiltonian of the type (1.2). Let us define the following polynomials on $`_2`$: $`G(x)_{j=1}^{\mathrm{}}G_jx^j`$, with $`\sigma _j=(1)^{G_j}`$; $`g_n(x)=_{j=0}^r\kappa (j;n)x^j`$; $`𝒢^{(n)}(x)g_n(x)G(x)_{j=1}^{\mathrm{}}𝒢_j^{(n)}x^j`$. Notice that the boundary condition on $`𝝈`$ can be translated as follows: $`G(x)`$ is a series of strictly positive powers of $`x`$.

It is necessary to distinguish two types of models: in the first case $`g_1(x)`$ divides $`g_2(x)`$, i.e. $`g_2(x)/g_1(x)`$ is a polynomial (these are the “non recursive” models, a particular case being $`ϵ_i(𝝈)=\sigma _i`$); in the second one $`g_1(x)`$ does not divide $`g_2(x)`$, i.e. $`g_2(x)/g_1(x)`$ is a series (“recursive” models).

We shall treat the “recursive” models first. In this case the first order terms in the expansions (3.3) and (3.4) are exponentially small in the size. In order to prove this assertion, let us consider the configuration $`𝝈(l)`$. The relevant generating polynomials are $`𝒢^{(1)}(x)=x^l`$ and $`𝒢^{(2)}(x)=x^lg_2(x)/g_1(x)`$. The form of $`𝒢^{(2)}(x)`$ is given by the following result of algebra

###### Lemma 3.1

Let $`g(x)`$ and $`f(x)`$ be two polynomials on $`_2`$ such that $`g(0)=f(0)=1`$, $`f(x)1`$, and their greatest common divisor $`\mathrm{gcd}(f(x),g(x))`$ is equal to 1. Then there exists an integer $`\omega `$ such that $`g(x)/f(x)=_{n=0}^{\mathrm{}}x^{n\omega }p_n(x)`$ with $`\mathrm{deg}[p_n(x)]<\omega `$ and $`p_n(x)=p_{\mathrm{}}(x)0`$ if $`n`$ is large enough. Hereafter we shall call $`\omega (f)`$ the smallest of such integers.

An explicit expression for $`\omega (f)`$ is given in the Appendix A. The Lemma 3.1 applies to our case if we divide both $`g_1(x)`$ and $`g_2(x)`$ by their greater common divisor: $`f_k(x)g_k(x)/\mathrm{gcd}(g_1(x),g_2(x))`$, so that $`\mathrm{gcd}(f_1(x),f_2(x))=1`$. It implies that if we write down the numbers $`\eta _j(𝝈(i))=\pm 1`$ we get an antiperiod followed by a non trivial periodic sequence with period $`\omega (f_1)`$. Let us consider a site “in the bulk”: $`N\delta <i<N(1\delta )`$ with $`\delta `$ a (small) positive number. Then, using the convention $`h_j=0`$ for $`j>N`$, we get:

$`\mathrm{\Delta }(i)`$ $`=`$ $`2J_i+2{\displaystyle \underset{j=1}{\overset{N}{}}}𝒢_j^{(2)}h_j=2J_i+2{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \underset{k=0}{\overset{\omega (f_1)1}{}}}p_{n,k}h_{i+n\omega (f_1)+k}`$ (3.5)
which diverges almost surely in the thermodynamic limit if $`h>0`$ (see the Introduction on this point). In Eq. (3.1) we must sum also terms which are “near” the boundaries, i.e. $`iN\delta `$ or $`iN(1\delta )`$. These give however a negligible contribution.

Let us now consider the second order terms of the expansions (3.3) and (3.4). They involve configurations $`𝝈(k,l)`$ with two flipped $`ϵ(𝝈)`$’s. The only configurations which give a non negligible contribution are the ones which involve a finite (in the $`N\mathrm{}`$ limit) number of flipped $`\eta (𝝈)`$’s. This corresponds to choosing $`k`$ and $`l`$ such that $`(x^k+x^l)g_2(x)/g_1(x)`$ is a polynomial (and not an infinite series). The following useful result is proved in the Appendix A.

###### Lemma 3.2

Let $`f(x)`$ be a polynomial on $`_2`$ such that $`f(0)=1`$ and $`k`$ an integer. Then there exists an integer $`\omega (f)`$ such that $`f(x)`$ divides $`1+x^k`$ if and only if $`k`$ is a strictly positive multiple of $`\omega (f)`$.

As suggested by the notation the $`\omega (f)`$’s cited in Lemmas 3.1 and 3.2 are indeed equal. The terms which give a non vanishing contribution at order $`X^2`$ in the expansions (3.3-3.4) are the ones corresponding to configurations $`𝝈(k,l)`$ such that $`|kl|`$ is a multiple of $`\omega (f_1)`$. In order to evaluate these terms we must count the number of flipped $`\eta (𝝈)`$’s. This number is nothing but the number of non zero coefficients in the polynomial $`(x^k+x^l)g_2(x)/g_1(x)`$. Let us define the weight of a polynomial $`p(x)=_kp_kx^k`$ over $`_2`$ as the number of its non zero coefficients: $`\text{weight}(p)\mathrm{\#}\{p_k|p_k0\}`$. The weight of $`(x^k+x^l)g_2(x)/g_1(x)`$ is given, for a large class of hamiltonians, by the following lemma.

###### Lemma 3.3

Let $`f(x)`$ and $`g(x)`$ be two polynomial on $`_2`$ such that $`f(0)=g(0)=1`$, $`f(x)1`$, and $`\mathrm{gcd}(f(x),g(x))=1`$. If $`\mathrm{deg}(g)\omega (f)`$ then the weight of $`s_m(x)(1+x^{m\omega (f)})g(x)/f(x)`$ is given by $`\mathrm{weight}(s_m)=w_0(f,g)+w_1(f,g)m`$ for each $`m1`$. The coefficients $`w_0(f,g)`$ and $`w_1(f,g)`$ are positive integers whose explicit expressions are given by Eqs. (A.8-A.9).

Appendix A contains also an illustration of what could happen in the more general case.

By using Lemmas 3.2 and 3.3 we can linearize with respect to $`X`$ the expression on the r.h.s. of Eq. (3.1):

$`{\displaystyle \frac{1}{X_i}}{\displaystyle \frac{Z_i(1)}{Z_i(+1)}}={\displaystyle \underset{m0}{}}X_{i+m\omega (f_1)}e^{\beta \mathrm{\Delta }(i,i+m\omega (f_1))}+O(X^2)`$ (3.6)
and defining $`s_m(x)(1+x^{m\omega (f_1)})g_2(x)/g_1(x)=_js_{m,j}x^j`$ we get

$`\mathrm{\Delta }(k,l)=2J_k+2J_l+2{\displaystyle \underset{j}{}}s_{m,j}h_{\mathrm{min}(k,l)+j}`$ (3.7)
if $`|kl|=m\omega (f_1)`$. Clearly Eq. (3.6) holds only for $`i`$ in the “bulk” (i.e. $`N\delta <i<(1\delta )N`$) up to terms which are exponentially small in the size $`N`$.

Our first important observation is that the right hand side of Eq. (3.6) vanishes if $`X_k=0`$ for $`k=1,\mathrm{},N`$. This means that $`Q_{}(X)=\delta (X)`$ is a fixed point of Eq. (3.1) for “recursive” models. Recall that the change of variables which yields Eq. (3.1) is $`X=e^{2\beta x}`$ and that $`x`$ has the meaning of an effective field acting on $`ϵ_i(𝝈)`$. The solution $`Q_{}(X)`$ corresponds then to a phase with completely frozen spins: $`ϵ_i(𝝈)=+1`$.

We would like to understand if this phase is stable for some temperature $`\beta `$ and some distribution of the couplings. A possible approach is to study the turbo decoding dynamics (as described by Eq. (3.1)) when starting from a distribution “near” $`Q_{}(X)`$. Let us suppose that, for $`Q_t(X)`$ near enough to $`Q_{}(X)`$, we can safely neglect $`O(X^2)`$ terms on the r.h.s. of Eq. (3.6):

$`Q_{t+1}(Y)={\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle _0^{\mathrm{}}}𝑑Q_t[𝑿]{\displaystyle 𝑑𝒫[𝑱]\delta \left(Y\underset{m0}{}X_{i+m\omega (f_1)}e^{\beta \mathrm{\Delta }(i,i+m\omega (f_1))}\right)}`$ (3.8)
This equation is very similar to a class of recursive equations which appear in a completely different context: polymers on disordered trees . These are of the type

$`P_{t+1}(Z)={\displaystyle _0^{\mathrm{}}}{\displaystyle \underset{i=1}{\overset{K}{}}}dZ_iP_t(Z_i){\displaystyle \rho (V_1,\mathrm{},V_K)𝑑V_1\mathrm{}𝑑V_K\delta \left(Z\underset{i=1}{\overset{K}{}}e^{\beta V_i}Z_i\right)}`$ (3.9)
The only non trivial difference is that the linear function of $`𝑿`$ appearing inside the delta function on the r.h.s. of Eq. (3.8) depends upon a macroscopic (indeed linear in $`N`$) number of $`X`$’s. In Eq. (3.9), instead, only a finite number of variables appears: $`K`$ is the coordination number of the tree minus one. Notice however that, for $`m`$ large, $`\mathrm{\Delta }(i,i+m\omega (f_1))2\text{weight}(s_m)h2w_1(f_1,f_2)mh`$. We can thus truncate the sum in Eq. (3.8) to $`mM`$ by making an error of order $`O(e^{cM})`$ and we guess that the limit $`M\mathrm{}`$ can be taken at the end without problems 444This argument is not mathematically rigorous since it is not honest to use the central limit theorem in this case: we refer to Appendix B for more convincing arguments..

Let us summarize some results of  which are useful in our discussion. It turns out that Eq. (3.9) is equivalent to a discretization of the Kolmogorov-Petrovsky-Piscounov (KPP) equation  (a well studied partial differential equation). Using this equivalence the large time limit of Eq. (3.9) is obtained:

$`P_t(X)e^{\beta c(\beta )t}\overline{P}(Xe^{\beta c(\beta )t})`$ (3.10)
corresponding to a front wave solution of the KPP equation with front velocity $`c(\beta )`$. If we define the function

$`v(\beta ){\displaystyle \frac{1}{\beta }}\mathrm{log}\left({\displaystyle \underset{i=1}{\overset{K}{}}}{\displaystyle 𝑑V_1\mathrm{}𝑑V_K\rho (V_1,\mathrm{},V_K)e^{\beta V_i}}\right)`$ (3.11)
then the front velocity is given by the following construction:

$`c(\beta )=\{\begin{array}{ccc}v(\beta )& \text{if}& \beta \beta _c\\ v(\beta _c)& \text{if}& \beta >\beta _c\end{array}`$ (3.14)
with $`\beta _c`$ given by

$`{\displaystyle \frac{d}{d\beta }}|_{\beta _c}v(\beta )=0`$ (3.15)
At the critical temperature $`\beta _c`$ a freezing phenomenon takes place with the front velocity sticking to its minimal value.

Let us apply these results to our case, i.e. to Eq. (3.8). The large time solution $`Q_t(X)e^{\beta c(\beta )t}\overline{Q}(Xe^{\beta c(\beta )t})`$ gives the correct behavior for $`t\mathrm{}`$ only if $`c(\beta )<0`$. In this case $`lim_t\mathrm{}Q_t(X)=Q_{}(X)`$ and it is then correct to linearize Eq. (3.1): the frozen phase is stable. If, on the other hand, $`c(\beta )0`$ then we must take into account higher order terms in the low $`X`$ expansion and the asymptotic form is no longer of the type defined by Eq. (3.10): the frozen phase is unstable.

In the thermodynamic limit we get

$`e^{\beta v(\beta )}`$ $`=`$ $`{\displaystyle \underset{m0}{}}{\displaystyle 𝑑𝒫[𝑱]e^{\beta \mathrm{\Delta }(i,i+m\omega (f_1))}}=`$
$`=`$ $`2\left({\displaystyle 𝑑JP(J)e^{2\beta J}}\right)^2{\displaystyle \underset{m=1}{\overset{\mathrm{}}{}}}\left({\displaystyle 𝑑hP(h)e^{2\beta h}}\right)^{\mathrm{weight}(s_m)}`$
The front velocity $`c(\beta )`$ is obtained by applying the construction given in Eqs. (3.14-3.15) to Eq. (3). If the hypothesis of Lemma 3.3 are satisfied we can easily sum the series:

$`e^{\beta v(\beta )}`$ $`={\displaystyle \frac{2\left({\displaystyle 𝑑JP(J)e^{2\beta J}}\right)^2\left({\displaystyle 𝑑hP(h)e^{2\beta h}}\right)^{w_0(f_1,f_2)+w_1(f_1,f_2)}}{1\left({\displaystyle 𝑑hP(h)e^{2\beta h}}\right)^{w_1(f_1,f_2)}}}`$ (3.17)
We discuss now Eq. (3.17), the more general case being completely analogous. The series converges only if $`𝑑hP(h)e^{2\beta h}<1`$. If $`𝑑hP(h)h>0`$, as we supposed sinc the beginning, then convergence is assured for $`0<\beta <\beta _1`$ with $`𝑑hP(h)e^{2\beta _1h}=1`$. It is easy to see that $`\beta v(\beta )`$ is strictly convex for $`0<\beta <\beta _1`$ and thus $`v(\beta )`$ has either one global minimum or is strictly monotonic for $`0<\beta <\beta _1`$. Since $`lim_{\beta 0^+}v(\beta )=lim_{\beta \beta _1^{}}v(\beta )=+\mathrm{}`$ the first possibility is excluded and we conclude that $`0<\beta _c<\beta _1`$. The important point is that the right hand side of Eq. (3) is well defined every time we need of it, i.e. for $`0<\beta <\beta _c`$.

In applications to turbo codes a simplification occurs: we are interested in a particular temperature, $`\beta =1`$, and we are left with a unique parameter: the signal to noise ratio $`1/w^2`$. Moreover the probability distributions of the couplings are fixed by the characteristics of the communication channel . If we introduce the auxiliary variables $`\widehat{J}`$ and $`\widehat{h}`$, which correspond to the output of the channel, the probability distributions are obtained as follows

$`P(J)dJ=P(\widehat{J}|+1)d\widehat{J}\text{with}J={\displaystyle \frac{1}{2}}\mathrm{log}{\displaystyle \frac{P(\widehat{J}|+1)}{P(\widehat{J}|1)}}`$ (3.18)
where $`P(\widehat{J}|\tau )`$ is the probability distribution of the output of the channel conditional to the input $`\tau `$. A similar expression holds for $`h`$. If the channel is symmetric (i.e. if $`P(\widehat{J}|1)=P(\widehat{J}|+1)`$) one easily obtains $`\beta _1=1`$ and then $`c(\beta =1,w^2)=v(\beta _c,w^2)`$. We can distinguish the two cases defined below.

* If $`v(\beta ,w^2)<0`$ for some $`0<\beta <1`$ then we are in the no-error phase and the turbo decoding algorithm converges to the message with “velocity” $`c(\beta =1,w^2)=\mathrm{min}_{0<\beta <1}v(\beta ,w^2)`$. We expect the condition $`v(\beta _c,w^2)<0`$ to be verified in the “low noise” region $`w^2<w_{loc}^2`$.
* If $`v(\beta ,w^2)0`$ in the interval $`0<\beta <1`$ then $`c(\beta =1,w^2)0`$ and the linearization in Eq. (3.8) is no longer reliable. In this case $`\pi _t(x)`$ is expected to converge for $`t\mathrm{}`$ to some distribution supported on finite fields $`x`$. The decoded message will be plagued by a finite error probability per bit, no matter how many times do we iterate the turbo decoding algorithm.

Let us now study some examples. We consider a gaussian channel with:

$`P(\widehat{J}|\tau )={\displaystyle \frac{1}{(4\pi w^2)^{1/2}}}\mathrm{exp}\left\{{\displaystyle \frac{(\widehat{J}\tau )^2}{4w^2}}\right\}`$ (3.19)
$`P(\widehat{h}|\tau )={\displaystyle \frac{1}{(2\pi w^2)^{1/2}}}\mathrm{exp}\left\{{\displaystyle \frac{(\widehat{h}\tau )^2}{2w^2}}\right\}`$ (3.20)
This choice of the variances is justified since it corresponds to a code with rate $`1/3`$ (see Ref. ). It is useful to define the function

$`z(\beta ,w^2)={\displaystyle 𝑑hP(h)e^{2\beta h}}=\left({\displaystyle 𝑑JP(J)e^{2\beta J}}\right)^2=\mathrm{exp}\left[{\displaystyle \frac{2\beta (\beta 1)}{w^2}}\right]`$ (3.21)
The three cases below have been already considered in Ref. . We refer to the Appendix A for the calculation of the constants $`w_0`$ and $`w_1`$ to be used in Eq. (3.17).

1. A model with nearest neighbours interaction is: $`ϵ_i(𝝈)\sigma _i\sigma _{i1}`$ and $`\eta _i(𝝈)=\sigma _i`$ (which corresponds to the generating polynomials $`g_1(x)=1+x`$ and $`g_2(x)=1`$). Using Eq. (3.17) and the fact that $`w_0(f_1,f_2)=0`$ and $`w_1(f_1,f_2)=1`$ we get

$`v(\beta ,w^2)={\displaystyle \frac{1}{\beta }}\mathrm{log}{\displaystyle \frac{2z^2(\beta ,w^2)}{1z(\beta ,w^2)}}`$ (3.22)
It is easy to see that $`v(\beta ,w^2)0`$ for each $`0<\beta <1`$ if $`w^2w_{loc}^2=1/\mathrm{log}4`$.
2. For $`ϵ_i(𝝈)\sigma _i\sigma _{i1}\sigma _{i2}`$ and $`\eta _i(𝝈)=\sigma _i\sigma _{i2}`$ (generating polynomials: $`g_1(x)=1+x+x^2`$ and $`g_2(x)=1+x^2`$) we obtain $`w_0(f_1,f_2)=2`$ and $`w_1(f_1,f_2)=2`$ and then

$`v(\beta ,w^2)={\displaystyle \frac{1}{\beta }}\mathrm{log}{\displaystyle \frac{2z^5(\beta ,w^2)}{1z^2(\beta ,w^2)}}`$ (3.23)
Finally $`w_{loc}^2=1/(2\mathrm{log}z_c)`$ where $`z_c`$ is the only real solution of the equation $`2z^5+z^2=1`$.
3. If we consider the model given by $`ϵ_i(𝝈)\sigma _i\sigma _{i1}\sigma _{i2}\sigma _{i3}\sigma _{i4}`$ and $`\eta _i(𝝈)=\sigma _i\sigma _{i4}`$ (generating polynomials: $`g_1(x)=1+x+x^2+x^3+x^4`$ and $`g_2(x)=1+x^4`$) we obtain $`w_0(f_1,f_2)=2`$ and $`w_1(f_1,f_2)=2`$ as in the previous example. Both $`v(\beta ,w^2)`$ and $`w_{loc}^2`$ coincide with the ones obtained above.

Let us make a few observations about the validity of our calculation. The threshold $`w_{loc}^2`$ has been obtained by starting from a distribution $`Q(X)`$ very near to the “frozen” one $`Q_{}(X)`$ and linearizing Eq. (3.1) in $`X`$. It must then be interpreted as a threshold for local stability of the “frozen” solution. Moreover, if we take seriously the heuristic derivation of Eq. (2.9), we can deduce something about the dynamics of the turbo decoding algorithm in the error-free phase: the probability distribution of the auxiliary fields $`\mathrm{\Gamma }_i^{(k)}(t)`$ moves towards infinitely large fields with an average velocity $`c(\beta ,w^2)`$. This conclusion is compared with numerical data in Fig. (1): the agreement seems to be quite good. An interesting outcome of the previous calculation is that the approach to the perfect decoding becomes slower near to the critical signal to noise ratio.

Let us now discuss the “non recursive” models, that is models such that $`g_1(x)`$ divides $`g_2(x)`$. In this case the energy $`\mathrm{\Delta }(i)`$ to be paid for flipping $`\eta _i(𝝈)`$ remains finite in the thermodynamic limit. The low $`X`$ expansions in Eqs. (3.3-3.4) have a non vanishing term of order $`O(X)`$. This implies that $`Q_{}(X)=\delta (X)`$ is no longer a fixed point of Eq. (3.1). Let us compute $`\mathrm{\Delta }(i)`$. For “non recursive” models we can define the polynomial $`s(x)_ks_kx^kg_2(x)/g_1(x)`$. It is easy to show that $`\mathrm{\Delta }(i)=2J_i+2_ks_kh_{i+k}`$. A simple approximation of the fixed point of Eq. (3.1) is:

$`Q_{\mathrm{}}(X){\displaystyle 𝑑JP(J)\underset{i=1}{\overset{w}{}}dh_iP(h_i)\delta \left(Xe^{2\beta J2\beta _{i=1}^wh_i}\right)}`$ (3.24)
with $`w\mathrm{weight}(s)`$. This approximation is supposed to be good in the low noise region where we expect the distributions $`Q_t(X)`$ to be concentrated on small $`X`$’s.

## 4 The replica calculation.

The replica method  starts with the computation of the (integer) moments of the partition function. This can be done by introducing an appropriate order parameter (the choice is a matter of convenience) and by recurring to standard tricks. Here we choose to use the (multi)-overlaps $`q_{a_1\mathrm{}a_l}`$ and their complex conjugates $`\widehat{q}_{a_1\mathrm{}a_l}`$:

$`\overline{Z^n}`$ $`=`$ $`{\displaystyle \frac{N}{\pi }𝑑q_0𝑑\widehat{q}_0\underset{a}{}\frac{N}{\pi }dq_ad\widehat{q}_a\underset{(a,b)}{}\frac{N}{\pi }dq_{ab}d\widehat{q}_{ab}\mathrm{}e^{NS[q,\widehat{q}]}}`$ (4.1)
$`S[q,\widehat{q}]`$ $`=`$ $`1+q_0\widehat{q}_0+{\displaystyle \underset{a}{}}q_a\widehat{q}_a+{\displaystyle \underset{(a,b)}{}}q_{ab}\widehat{q}_{ab}+\mathrm{}+n\mathrm{log}2+`$
$`+\beta _{1d,n}[q]+\beta _{1d,n}[\widehat{q}]`$
$`_{1d,n}[q]`$ $``$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N\beta }}\mathrm{log}Z_{1d,n}[q]`$ (4.3)
$`Z_{1d,n}[q]`$ $``$ $`{\displaystyle \underset{\{\sigma _i^a\}}{}}{\displaystyle \underset{i=1}{\overset{N}{}}}[q_0+{\displaystyle \underset{a}{}}q_aϵ_i(𝝈^a)+{\displaystyle \underset{(a,b)}{}}q_{ab}ϵ_i(𝝈^a)ϵ_i(𝝈^b)+\mathrm{}]`$
$`{\displaystyle }d𝒫[𝑱]\mathrm{exp}\{\beta {\displaystyle \underset{a}{}}H(𝝈^a;𝑱)\}`$
where $`H(𝝈;𝑱)=_iJ_iϵ_i(𝝈)_ih_i\eta _i(𝝈)`$. and the replica indices $`a,b,\mathrm{}`$ run from $`1`$ to $`n`$. The usual mean field models have no geometrical structure at all. In those cases the introduction of the order parameters leads to a (replicated) partition function which factorizes over the sites. In our case we are left with the problem of computing the one dimensional partition functions $`Z_{1d,n}[q]`$. These correspond to the one dimensional sub-structures which are not destroyed by the randomness of the model. The saddle point equations are easily written

$`\widehat{q}_{a_1\mathrm{}a_l}=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle \frac{ϵ_i(𝝈^{a_1})\mathrm{}ϵ_i(𝝈^{a_l})}{[q_0+_aq_aϵ_i(𝝈^a)+\mathrm{}]}}_q`$ (4.5)
where the expectation values $`()_q`$, $`()_{\widehat{q}}`$ are defined as follows

$`()_q`$ $``$ $`{\displaystyle \frac{1}{Z_{1d,n}[q]}}{\displaystyle 𝑑𝒫[𝑱]\underset{\{\sigma _i^a\}}{}()\underset{i=1}{\overset{N}{}}[q_0+\underset{a}{}q_aϵ_i(𝝈^a)+\mathrm{}]e^{\beta _aH[𝝈{}_{}{}^{a};𝑱]}}`$ (4.6)
In the recursive case Eq. (4.5) admits the following solution 555In fact there is a one parameter family of solutions which are degenerate. This fact is due to a (not very interesting) symmetry of the action (4): $`S[q,\widehat{q}]=S[e^{i\theta }q,e^{i\theta }\widehat{q}]`$. However the integration over the parameter $`\theta `$ does not pose any problem. We shall fix this freedom by imposing $`q_0`$ to be real. corresponding to a no-error phase: $`q_{a_1\mathrm{}a_l}^{}=\widehat{q}_{b_1\mathrm{}b_l}^{}=2^{n/2}`$. The free energy of this phase is $`f_0(\beta )=2𝑑JP(J)J2𝑑hP(h)h`$. If we parametrize the replica symmetric ansatz as in Ref.

$`q_{a_1\mathrm{}a_l}={\displaystyle _{\mathrm{}}^+\mathrm{}}𝑑x\pi (x)\mathrm{cosh}^n(\beta x)\mathrm{tanh}^l(\beta x)`$ (4.7)
and analogously for $`\widehat{q}_{b_1\mathrm{}b_m}`$ (with a different distribution $`\widehat{\pi }(x)`$), the following free energy functional can is obtained in the limit $`n0`$:

$`f[\pi ,\widehat{\pi }]`$ $`=`$ $`{\displaystyle \frac{1}{\beta }}{\displaystyle 𝑑x𝑑y\pi (x)\widehat{\pi }(y)\mathrm{log}\left[2\mathrm{cosh}(\beta x+\beta y)\right]}+_{1d}^{RS}[\pi ]+_{1d}^{RS}[\widehat{\pi }]`$ (4.8)
$`_{1d}^{RS}[\pi ]`$ $``$ $`\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{\beta N}}{\displaystyle 𝑑𝒫[𝑱]𝑑\pi [𝒙]\mathrm{log}Z_{1d}^{RS}[𝑱,𝒙]}`$ (4.9)
$`Z_{1d}^{RS}[𝑱,𝒙]`$ $``$ $`{\displaystyle \underset{𝝈}{}}\mathrm{exp}\left[\beta {\displaystyle \underset{i=1}{\overset{N}{}}}(J_i+x_i)ϵ_i(𝝈)+\beta {\displaystyle \underset{i=1}{\overset{N}{}}}h_i\eta _i(𝝈)\right]`$ (4.10)
The distributions $`\pi `$ and $`\widehat{\pi }`$ are normalized ( $`𝑑x\pi (x)=𝑑y\widehat{\pi }(y)=1`$) and satisfy the saddle point equation below:

$`\pi (y)=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle _{\mathrm{}}^+\mathrm{}}𝑑\widehat{\pi }[𝒙]{\displaystyle 𝑑𝒫[𝑱]\delta \left(y\frac{1}{\beta }\text{arctanh}\left(ϵ_i(𝝈)_{𝑱,𝒙}\right)+x_i\right)}`$ (4.11)
which is identical to the fixed point equation corresponding to Eq. (2.9), if we suppose the order parameters to be real at the saddle point.

Equation (4.11) is unpractical since it involves the unknown distributions $`\pi (x)`$ and $`\widehat{\pi }(x)`$ infinitely many times. However due to the short range structure of the hamiltonians defined in Eq. (1.2), it can be rewritten as a simple integral equation. Obviously the precise form of this equation depends upon the form of the hamiltonian (1.2). In particular it becomes simpler as the range of the interaction becomes shorter. Let us illustrate this point by considering the model (a) of the previous Section: $`ϵ_i(𝝈)=\sigma _i\sigma _{i1}`$, $`\eta _i(𝝈)=\sigma _i`$. We start by defining the following (right and left) partition functions:

$`Z_{i,M}^{(R)}(\sigma _i)`$ $``$ $`{\displaystyle \underset{\sigma _{i+1}\mathrm{}\sigma _{i+M}}{}}\mathrm{exp}\left[\beta {\displaystyle \underset{k=i+1}{\overset{i+M}{}}}(J_k+x_k)\sigma _k\sigma _{k1}+\beta {\displaystyle \underset{k=i}{\overset{i+M}{}}}h_k\sigma _k\right]`$ (4.12)
$`Z_{i,M}^{(L)}(\sigma _i)`$ $``$ $`{\displaystyle \underset{\sigma _{iM}\mathrm{}\sigma _{i1}}{}}\mathrm{exp}\left[\beta {\displaystyle \underset{k=iM+1}{\overset{i}{}}}(J_k+x_k)\sigma _k\sigma _{k1}+\beta {\displaystyle \underset{k=iM}{\overset{i}{}}}h_k\sigma _k\right]`$ (4.13)
and the (right and left) fields:

$`x_i^{R/L}\underset{M\mathrm{}}{lim}{\displaystyle \frac{1}{2\beta }}\mathrm{log}{\displaystyle \frac{Z_{i,M}^{(R/L)}(+)}{Z_{i,M}^{(R/L)}()}}`$ (4.14)
We define now a new couple of order parameters, the probability distributions $`\omega (x)`$ and $`\widehat{\omega }(x)`$ of the right (or left) fields:

$`\omega (x)={\displaystyle \underset{i0}{}dh_iP(h_i)\underset{i1}{}dJ_iP(J_i)\underset{i1}{}dx_i\pi (x_i)\delta \left(xx_0^R[J_i;h_i;x_i]\right)}`$ (4.15)
It easy to show that, at the saddle point, $`\omega (x)`$ and $`\widehat{\omega }(x)`$ satisfy the following integral equation:

$`\omega (z)`$ $`=`$ $`{\displaystyle 𝑑hP(h)𝑑J_1P(J_1)𝑑J_2P(J_2)𝑑x_1\widehat{\omega }(x_1)𝑑x_2\widehat{\omega }(x_2)𝑑z^{}\omega (z^{})}`$ (4.16)
$`\delta \left\{zh\mathrm{\Theta }_\beta [z^{};J_1+J_2+\mathrm{\Theta }_\beta (x_1;x_2)]\right\}`$
$`\mathrm{\Theta }_\beta (x;y)`$ $``$ $`{\displaystyle \frac{1}{\beta }}\text{arctanh}[\mathrm{tanh}(\beta x)\mathrm{tanh}(\beta y)]`$ (4.17)
and that the solution of Eq. (4.11) is related to the solution of the previous equation as follows:

$`\pi (x)={\displaystyle 𝑑JP(J)𝑑x_L\widehat{\omega }(x_L)𝑑x_R\widehat{\omega }(x_R)\delta [xJ\mathrm{\Theta }_\beta (x_R;x_L)]}`$ (4.18)
Equation (4.16) reduces to the Dyson Schmidt equation  for a one dimensional model with nearest neighbour interaction if we keep the distribution $`\widehat{\omega }(x)`$ fixed. The interaction between the two one-dimensional subsystems turns it into a nonlinear equation. Moreover Eq. (4.16) can be treated numerically more easily than Eq. (4.11). A possible approach consists in representing the unknown distribution as $`\omega (x)=_{j=1}^K\delta (xx_j)`$ and iterating Eq. (4.16) until a fixed point is reached. An example of this kind of computations is shown in Fig. (2).

It is simple to obtain the analogous of Eq. (4.16) for the simplest non recursive model, defined by: $`ϵ_i(𝝈)=\sigma _i`$, $`\eta _i(𝝈)=\sigma _i\sigma _{i1}`$. The final result is

$`\omega (z)`$ $`=`$ $`{\displaystyle 𝑑hP(h)𝑑J_1P(J_1)𝑑J_2P(J_2)𝑑x_1\widehat{\omega }(x_1)𝑑x_2\widehat{\omega }(x_2)𝑑z^{}\omega (z^{})}`$ (4.19)
$`\delta \left(z\mathrm{\Theta }_\beta [h;J_1+J_2+x_1+x_2+z^{}]\right)`$
$`\pi (x)`$ $`=`$ $`{\displaystyle 𝑑JP(J)𝑑x_L\widehat{\omega }(x_L)𝑑x_R\widehat{\omega }(x_R)\delta (xJx_Lx_R)}`$ (4.20)
A simple approximation to the solution of Eq. (4.19) can be obtained by starting from a distribution $`\omega (x)`$ supported on very large fields $`x`$ and iterating Eq. (4.19) one time. The result is $`\pi (x)𝑑JP(J)𝑑h_1P(h_1)𝑑h_1P(h_1)\delta (xJh_1h_2)`$, which coincides with the more general Eq. (3.24) after the change of variables $`X=e^{2\beta x}`$. No such approximation is possible for Eq. (4.16).

Expressions equivalent to Eqs. (4.16-4.19) can be derived for more complicated types of interaction. In general the distribution $`\omega (x)`$, which is defined on the real line, will be replaced by a distribution defined on $`^{2^r1}`$, $`r`$ being the range of the hamiltonian.

## 5 The stability of the frozen solution.

We would like to study local stability of the no-error phase in the context of the replica method. This can be done666For similar calculations see Ref. . by computing the eigenvalues of the matrices:

$`M_{a_1\mathrm{}a_l,b_1\mathrm{}b_m}^\pm [q]=\delta _{a_1\mathrm{}a_l,b_1\mathrm{}b_m}\pm {\displaystyle \frac{^2\beta _{1d,n}[q]}{q_{a_1\mathrm{}a_l}q_{b_1\mathrm{}b_m}}}`$ (5.1)
$`M^\pm [q]`$ are the mass matrices for purely real ($`M^+[q]`$), or purely immaginary ($`M^{}[q]`$), fluctuations of the order parameter around the value $`q`$. We are interested in the saddle point $`q_{a_1\mathrm{}a_l}^{}=2^{n/2}`$. In order to write down all the $`2^n`$ eigenvectors of $`M^\pm [q^{}]`$ it is convenient to change slightly our notation for the overlaps. Let us denote by $`\mathrm{\Omega }\{1,2,\mathrm{},n\}`$ the set of $`l|\mathrm{\Omega }|`$ different indices $`(a_1^\mathrm{\Omega },\mathrm{},a_l^\mathrm{\Omega })`$. We can use the $`\mathrm{\Omega }`$’s as indices for the overlaps with the natural identification $`q_\mathrm{\Omega }q_{a_1^\mathrm{\Omega }\mathrm{}a_l^\mathrm{\Omega }}`$. It is not difficult to show that

$`T_{\mathrm{\Omega }_a,\mathrm{\Omega }_b}^{(N)}`$ $``$ $`{\displaystyle \frac{1}{N}}{\displaystyle \frac{^2\mathrm{log}Z_{1d,n}[q]}{q_{a_1\mathrm{}a_l}q_{b_1\mathrm{}b_m}}}|_{q=q^{}}=`$
$`=`$ $`{\displaystyle \frac{2^{1n}}{N}}\left\{{\displaystyle \underset{(i,j)}{}}{\displaystyle 𝑑𝒫[𝑱]e^{nN\beta fn\beta E_0}\left(1+e^{\beta \mathrm{\Delta }(i,j)}\right)^n\left[\mathrm{tanh}\left(\frac{\beta \mathrm{\Delta }(i,j)}{2}\right)\right]^u}{\displaystyle \frac{N^2}{2}}\right\}`$
where $`\mathrm{\Delta }(i,j)`$ is defined in Section 3, $`e^{nN\beta f}𝑑𝒫[𝑱]e^{n\beta H(𝝈_0)}`$ and $`uu_{a_1\mathrm{}a_l,b_1\mathrm{}b_m}`$ counts the indices which are either in the set in $`\mathrm{\Omega }_a(a_1,\mathrm{},a_l)`$ or in the set $`\mathrm{\Omega }_b(b_1,\mathrm{},b_m)`$ but not in both. If $`q`$ is an eigenvector of $`T^{(N)}`$ with eigenvalue $`\theta _N`$, then it is an eigenvector of $`M^\pm [q^{}]`$ with eigenvalue $`\mu ^\pm =1lim_N\mathrm{}\theta _N`$.

Notice that $`T^{(N)}`$ is an hermitian matrix with respect to to the scalar product:

$`q,q^{}_n{\displaystyle \underset{l=0}{\overset{n}{}}}{\displaystyle \underset{(a_1,\mathrm{},a_l)}{}}q_{a_1\mathrm{}a_l}^{}q_{a_1\mathrm{}a_l}^{}={\displaystyle \underset{\mathrm{\Omega }}{}}q_\mathrm{\Omega }^{}q_\mathrm{\Omega }^{}`$ (5.3)
We shall use another subset of $`\{1,\mathrm{},n\}`$ (let us call it $`\mathrm{\Lambda }`$) to label the different eigenvectors of $`T^{(N)}`$, which we now exhibit:

$`q_\mathrm{\Omega }^{(\mathrm{\Lambda })}{\displaystyle \frac{1}{2^{n/2}}}(1)^{|\mathrm{\Lambda }\mathrm{\Omega }|}`$ (5.4)
The vectors $`\{q^{(\mathrm{\Lambda })}\}`$ form an orthonormal set with respect to the scalar product defined in Eq. (5.3). This is easily proven by induction on $`n`$. The vector $`q^{(\mathrm{})}`$ is nothing but the constant one. The corresponding eigenvalue is $`\theta _N^{(\mathrm{})}=1`$, whence $`\mu _{(\mathrm{})}^+=2`$ and $`\mu _{(\mathrm{})}^{}=0`$. The eigenvalue $`\mu _{(\mathrm{})}^{}=0`$ is a remnant of the invariance of the action under the symmetry cited in the footnote 5 of the previous Section. In order to compute the eigenvalues in the subspace orthogonal to $`q^{(\mathrm{})}`$, the following formula turns out to be useful:

$`{\displaystyle \underset{\mathrm{\Omega }^{}}{}}x^{|\mathrm{\Omega }\mathrm{\Omega }^{}|}q_\mathrm{\Omega }^{}^{(\mathrm{\Lambda })}=(1x)^{|\mathrm{\Lambda }|}(1+x)^{n|\mathrm{\Lambda }|}q_\mathrm{\Omega }^{(\mathrm{\Lambda })}`$ (5.5)
where $`\mathrm{\Omega }\mathrm{\Omega }^{}`$ denotes the symmetric difference of $`\mathrm{\Omega }`$ and $`\mathrm{\Omega }^{}`$ (i.e. $`\mathrm{\Omega }\mathrm{\Omega }^{}(\mathrm{\Omega }\mathrm{\Omega }^{})(\mathrm{\Omega }^{}\mathrm{\Omega })`$). Using Eq. (5.5) and the results of algebra outlined in Section 3 we get (for $`\mathrm{\Lambda }\mathrm{}`$):

$`\theta _N\mathrm{}(\mathrm{\Lambda })=2\zeta _J^2{\displaystyle \underset{m=1}{\overset{\mathrm{}}{}}}\zeta _h^{\mathrm{weight}(s_m)}`$ (5.6)
where $`\mathrm{weight}(s_m)`$ is defined in Section 3 and

$`\zeta _C=\zeta _C(|\mathrm{\Lambda }|,n,\beta )={\displaystyle \frac{{\displaystyle 𝑑CP(C)e^{(n2|\mathrm{\Lambda }|)\beta C}}}{{\displaystyle 𝑑CP(C)e^{n\beta C}}}}`$ (5.7)
for $`Ch`$ or $`CJ`$. When the one dimensional hamiltonians (1.2) satisfy the hypothesis of Lemma 3.3, the sum in Eq. (5.6) can be explicitly computed yielding:

$`\theta _N\mathrm{}(\mathrm{\Lambda })={\displaystyle \frac{2\zeta _J^2\zeta _h^{w_0(f_1,f_2)+w_1(f_1,f_2)}}{1\zeta _h^{w_1(f_1,f_2)}}}`$ (5.8)
If $`n2|\mathrm{\Lambda }|`$ then $`\theta (\mathrm{\Lambda },n;\beta )`$ is positive and decreasing with $`\beta `$. Moreover $`lim_\beta \mathrm{}\theta (\mathrm{\Lambda },n;\beta )=0`$ and $`lim_{\beta 0}\theta (\mathrm{\Lambda },n;\beta )=\mathrm{}`$. We can thus define the critical temperatures $`\beta _{l,n}`$ for $`n/2l=|\mathrm{\Lambda }|1`$, by requiring 777Notice that Eq. (5.9) can have more than one solution for $`n<2|\mathrm{\Lambda }|`$. The “physical” critical point is obtained by taking the limit $`n0`$ of the solution of Eq. (5.9) which exists for any $`n`$.

$`\theta (\mathrm{\Lambda },n;\beta _{|\mathrm{\Lambda }|,n})=1`$ (5.9)
If $`\beta >\beta _{|\mathrm{\Lambda }|,n}`$ the “frozen” saddle point is stable with respect to the direction $`q^{(\mathrm{\Lambda })}`$. If $`\beta <\beta _{|\mathrm{\Lambda }|,n}`$ it becomes unstable: $`\mu _{(\mathrm{\Lambda })}^+=1\theta (\mathrm{\Lambda })<0`$ while $`\mu _{(\mathrm{\Lambda })}^{}=1+\theta (\mathrm{\Lambda })>0`$ (it could be guessed that the “imaginary” directions would be stable because of the physical interpretation of the overlaps). In the limit $`n0`$, $`\beta _{l,n}\beta _c/l`$: the critical directions are the ones corresponding to $`|\mathrm{\Lambda }|=1`$. It is easy to see that the critical temperature $`\beta _c`$ coincides with the one obtained in Section 3.

## 6 Conclusion.

We have presented two derivations of the local stability condition for the no-error phase. Both will be object of the criticism of the skeptical reader. In the first one we obtained the “mean field” equation describing the dynamics of the decoding algorithm, Eq. (2.9), by making use of heuristic arguments. Indeed we argued Eq. (2.9) to be valid only in the replica symmetric approximation. In the second derivation we made use of the replica method, which has not (yet) well founded mathematical basis.

We think that the two derivations compensate each other for their defects. Moreover they yield the same replica symmetric saddle point equation (4.11) and give the same picture of the instability which destroys the no-error (frozen) phase. This corresponds to couples of flipped $`ϵ(𝝈)`$’s. Finally thanks to the first derivation we get some insight on the behavior of the decoding algorithm. In particular we have seen that, in the frozen phase, it approaches a no-error fixed point. This approach becomes slower near to the boundary of the frozen phase.

In Ref.  the local stability threshold computed here has been compared with numerical simulations for two types of code, respectively the models (a) and (b) presented in Section 3. Good agreement was found only for model (a). We propose two possible explanations of the disagreement for model (b):

* the phase transition is a first order one;
* the turbo decoding algorithm used in Ref.  gets sticked in some local minimum of the free energy, characterized by a finite error probability per bit.

We have not yet enough informations for choosing between these two scenarios.

## Appendix A Useful algebra results.

In this Appendix we remind to the reader some known facts in the theory of finite fields and we prove the propositions stated in Section 3. These are nothing but simple exercises and we work out them in detail only for greater convenience of the reader. Finally we illustrate a few applications of the results obtained. The reader interested in a more complete treatment can consult Refs. .

Let us begin with some elementary definitions. The basic object is $`_2`$ i.e. the field of integer numbers modulo $`2`$. A polynomial over $`_2`$, $`f(x)_2[x]`$ is simply a polynomial whose coefficients are in $`_2`$. We say $`f(x)_2[x]`$ to be irreducible if there do not exist two noncostant polynomials $`g(x),h(x)_2[x]`$ such that $`f(x)=g(x)h(x)`$. Any $`f(x)_2[x]`$ possess an unique factorization, i.e. a decomposition of the form $`f(x)=f_1(x)^{r_1}\mathrm{}f_h(x)^{r_h}`$ where $`f_i(x)_2[x]`$ are irreducible and $`r_i1`$ are integer numbers. Given two polynomials $`f(x),g(x)_2[x]`$ we say that $`f(x)`$ divides $`g(x)`$ (in symbols $`f(x)|g(x)`$) if there exists $`h(x)_2[x]`$ such that $`g(x)=f(x)h(x)`$ 888Similarly, given two integer numbers $`p,q`$, we say that $`p`$ divides $`q`$ (and write $`p|q`$) if there exists $`m`$, such that $`q=mp`$.. For an irreducible polynomial $`f(x)_2[x]`$ it does make sense to define the order $`o(f)`$: $`o(f)`$ is the smallest positive integer $`k`$ such that $`f(x)|x^k+1`$. The basic result which we shall employ in this Appendix is the following:

###### Theorem A.1

Let $`f(x)`$ be an irreducible polynomial over $`_2`$. Then $`f(x)|x^k+1`$ if and only if $`o(f)|k`$.

It is useful to know how to compute the order of an irreducible polynomial. The main tool is the theorem below:

###### Theorem A.2

Let $`f(x)`$ be an irreducible polynomial of degree $`d`$ over $`_2`$. Then $`d`$ is the smallest positive integer for which $`o(f)|2^d1`$.

Moreover it is obvious from the definition that $`o(f)\mathrm{deg}(f)`$

Our first step will be the proof of Lemma 3.2 which we restate here as follows

###### Lemma A.1

Let $`f(x)`$ be a polynomial on $`_2`$ with the following factorization

$`f(x)=f_1^{r_1}(x)\mathrm{}f_h^{r_h}(x);r_i1`$ (A.1)
where the polynomials $`f_i(x)`$ are irreducible over $`_2`$. Let $`p_i`$ be the smallest integer such that $`2^{p_i}r_i`$. Then $`f(x)|(1+x^k)`$ if and only if $`2^{p_i}|k`$ and $`o(f_i)|k`$ for $`i\{1,\mathrm{},h\}`$.

Proof of Lemma A.1. Let us begin by noticing that, since the $`f_i(x)`$ are irreducible, $`f(x)|(1+x^k)`$ if and only if $`f_i^{r_i}(x)|(1+x^k)`$ for $`i\{1,\mathrm{},h\}`$. We can then limit ourselves to the case $`f(x)=h^r(x)`$ with $`h(x)`$ irreducible. It is convenient to work in an extension of $`_2`$, i.e. in a field containing $`_2`$ as a subfield. We choose an extension (let us call it $`S`$) of $`_2`$ such that both $`h(x)`$ and $`(1+x^k)`$ can be decomposed in linear factors. The existence of such an extension is a basic fact of field theory. We are then looking for the $`k`$ such that all the root of $`h(x)`$ (in $`S`$) are roots of $`(1+x^k)`$ with multiplicity at least $`r`$. It is then necessary to study the multiplicity of the roots of $`(1+x^k)`$. The first observation is that, if $`k`$ is odd, all the roots are simple. In fact $`\frac{d}{dx}(1+x^k)=kx^{k1}`$ has no roots in common with $`(1+x^k)`$. The second observation consists in noticing that $`(1+x^{2k})=(1+x^k)^2`$. We deduce that $`(1+x^{2^mk})`$ with $`k`$ odd has $`k`$ distinct roots (the same as $`(1+x^k)`$), each one with multiplicity $`2^m`$. The final outcome is that $`h^r(x)|(1+x^{2^mk})`$ if and only if $`2^mr`$ and $`o(h)|k`$ $`\mathrm{}`$

From Lemma A.1 the explicit form of the period $`\omega (f)`$ used in Sec. 3 is easily obtained:

$`\omega (f)=2^{\mathrm{max}(p_1,\mathrm{},p_h)}\mathrm{lcm}(o(f_1),\mathrm{},o(f_h))`$ (A.2)
The Lemmas 3.1 and 3.3 are easy consequences of Lemma 3.2.

Proof of Lemma 3.1. Let us begin by considering the series $`1/f(x)`$. We can always define the polynomials $`\phi _n(x)`$ with $`\mathrm{deg}(\phi _n)<\omega (f)`$ such that $`1/f(x)=_{n=0}^{\mathrm{}}\phi _n(x)x^{n\omega (f)}`$. Since $`f(x)`$ divides $`(1+x^{m\omega (f)})`$ for all $`m1`$, we conclude that $`\phi _n(x)=\phi _n^{}(x)\phi (x)`$ for all $`n,n^{}0`$ and $`(1+x^{m\omega (f)})/f(x)=_{k=0}^{m1}\phi (x)x^{k\omega (f)}`$. With the following definition

$`g(x)\phi (x){\displaystyle \underset{l=0}{\overset{L}{}}}g_l(x)x^{l\omega (f)},\mathrm{deg}[g_l(x)]<\omega (f)`$ (A.3)
we get

$`{\displaystyle \frac{g(x)}{f(x)}}={\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}x^{n\omega (f)}{\displaystyle \underset{l=0}{\overset{\mathrm{min}(n,L)}{}}}g_l(x){\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}x^{n\omega (f)}p_n(x)`$ (A.4)
Notice that, for $`nL`$, $`p_n(x)=p_{\mathrm{}}(x)g(x)/f(x)modx^{\omega (f)}`$. An upper bound on $`L`$ is easily obtained from Eq. (A.3) yielding999Here use the definition $`x\mathrm{min}\{n:n>x\}`$. $`p_n(x)=p_{\mathrm{}}(x)`$ for $`n(\mathrm{deg}[g(x)]1)/\omega (f)L`$. Clearly it cannot be $`p_{\mathrm{}}(x)=0`$ otherwise we would conclude that $`f(x)`$ divides $`g(x)`$ in contradiction with the hypothesis. In order to complete the proof of let us suppose the following equation to hold

$`{\displaystyle \frac{g(x)}{f(x)}}={\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}x^{n\omega ^{}}p_n^{}(x)`$ (A.5)
with $`\omega ^{}<\omega (f)`$, $`\mathrm{deg}(p_n^{})<\omega ^{}`$ and $`p_n^{}(x)=p_{\mathrm{}}^{}(x)`$ for $`n`$ large enough. This implies that $`f(x)`$ divides $`g(x)(1+x^\omega ^{})`$ but, since $`\mathrm{gcd}(f,g)=1`$, we would conclude that $`f(x)`$ divides $`(1+x^\omega ^{})`$ contradicting Lemma 3.2 $`\mathrm{}`$

Proof of Lemma 3.3. It suffices to specialize the content of the previous paragraph to the case $`\mathrm{deg}[g(x)]\omega (f)`$:

$`g(x)\phi (x)`$ $`=`$ $`g_0(x)+g_1(x)x^{\omega (f)}`$ (A.6)
$`s_m(x){\displaystyle \frac{g(x)}{f(x)}}(1+x^{m\omega (f)})`$ $`=`$ $`g_0(x)+\{g_0(x)+g_1(x)\}{\displaystyle \underset{h=1}{\overset{m1}{}}}x^{h\omega (f)}+g_1(x)`$ (A.7)
whence

$`\text{weight}[s_m(x)]`$ $`=`$ $`w_0+w_1m`$ (A.8)
$`w_0`$ $``$ $`\text{weight}[g_0(x)]+\text{weight}[g_1(x)]\text{weight}[g_0(x)+g_1(x)]`$ (A.9)
$`w_1`$ $``$ $`\text{weight}[g_0(x)+g_1(x)]`$ (A.10)
$`\mathrm{}`$

What does it happen when the hypothesis of Lemma 3.3 are not satisfied? It is easy to guess the answer. There exists a positive integer $`m_0`$ such that, for $`mm_0`$, $`\mathrm{weight}(s_m)`$ grows linearly with $`m`$: $`\mathrm{weight}(s_m)=\stackrel{~}{w}_0(f,g)+\stackrel{~}{w}_1(f,g)m`$ with $`\stackrel{~}{w}_1(f,g)=\mathrm{weight}(p_{\mathrm{}})`$. Thanks to this fact we can always sum the series in Eq. (3) in the interval $`0<\beta <\beta _1`$. The discussion of the behavior of Eq. (3.8) presented in Section 3 is then completely general.

Let us return down to the earth and make a few examples. We shall consider the codes presented in Ref. :

1. The simplest non trivial case: $`f(x)=1+x`$, $`g(x)=1`$. Clearly both the polynomials are irreducible. The degree of $`f(x)`$ is $`\mathrm{deg}[f(x)]=1`$. Because of Theorem A.2 $`o(f)|2^11=1`$ whence $`o(f)=1=\omega (f)`$. Theorem A.1 implies that $`f(x)|1+x^k`$ for each $`k1`$. This conclusion is easily confirmed by the well known formula $`(1+x^k)=(1+x)(1+x+\mathrm{}+x^{k1})`$. Lemma 3.1 tells us that $`g(x)/f(x)=_{n=0}^{\mathrm{}}p_nx^n`$ with $`p_n=p_{\mathrm{}}`$ for $`n0`$ and that $`p_{\mathrm{}}=1`$ ($`1`$ is the unique non zero polynomial of degree zero). We have thus rediscovered the simple fact that $`(1+x)^1=_{n=0}^{\mathrm{}}x^n`$. Finally we observe the hypothesis of Lemma 3.3 are satisfied and that (with the notation of Eq. (A.6)), $`g_0(x)=1`$ and $`g_1(x)=0`$. From Eqs. (A.8-A.9-A.10) it follows that $`\text{weight}[s_m(x)=(1+x^m)/(1+x)]=m`$ which is easily confirmed by observing that $`s_m(x)=1+x+\mathrm{}+x^{m1}`$.
2. A less elementary example is: $`f(x)=1+x+x^2`$, $`g(x)=1+x^2`$. It is easy to see that $`f(x)`$ is irreducible and that $`g(x)=(1+x)^2`$ whence $`\mathrm{gcd}(f,g)=1`$. From $`o(f)|2^{\mathrm{deg}(f)}1=3`$ and $`o(f)\mathrm{deg}(f)=2`$ we deduce that $`o(f)=3=\omega (f)`$. In fact

$`{\displaystyle \frac{1}{1+x+x^2}}`$ $`=`$ $`1+x+x^3+x^4+x^6+\mathrm{}={\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}\phi (x)x^{3n}`$ (A.11)
$`\phi (x)`$ $`=`$ $`1+x`$ (A.12)
Thus by Lemma 3.2 $`f(x)|(1+x^k)`$ if and only if $`k`$ is a multiple of $`3`$. We can use Lemma 3.3 in order to compute the weight of $`s_m(x)=(1+x^2)(1+x^{3m})/(1+x+x^2)`$. We see that $`g_0(x)=1+x+x^2`$ and $`g_1(x)=1`$ whence $`\text{weight}[h_m(x)]=2+2m`$. With some book-keeping one can confirm this result:

$`h_m(x)=x+{\displaystyle \underset{l=0}{\overset{m1}{}}}(x^{3l+1}+x^{3l+2})+x^{3m}`$ $``$ $`\text{weight}[h_m(x)]=2+2m`$ (A.13)
3. Finally the generating polynomials used in Ref.  to build the first example of turbo code: $`f(x)=1+x+x^2+x^3+x^4`$, $`g(x)=1+x^4`$. Also in this case $`f(x)`$ is irreducible and $`g(x)=(1+x)^4`$ yielding $`\mathrm{gcd}(f,g)=1`$. Since $`o(f)|2^{\mathrm{deg}(f)}1=15`$ and $`o(f)\mathrm{deg}(f)=4`$, we deduce that either $`o(f)=5`$ or $`o(f)=15`$. However we know that $`(1+x^5)=(1+x)(1+x+x^2+x^3+x^4)`$ and we conclude that $`o(f)=5=\omega (f)`$. In fact

$`{\displaystyle \frac{1}{1+x+x^2}}`$ $`=`$ $`1+x+x^5+x^6+x^{10}+x^{11}+\mathrm{}={\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}\phi (x)x^{5n}`$ (A.14)
$`\phi (x)`$ $`=`$ $`1+x`$ (A.15)
Using the fact that $`g_0(x)=1+x+x^4`$ and $`g_1(x)=1`$ we get $`\text{weight}[h_m(x)]=2m+2`$.

## Appendix B On the asymptotic behavior of the solutions of Eq. (3.8).

In this Appendix we study Eq. (3.8) in order to extend to this case the results concerning Eq. (3.9) used in Section 3. We shall examine both the approach of Ref. , which is based on the analogy with the KPP equation and is a non rigorous one, and the approach of Ref. , which employs probability theory and is entirely satisfactory from the mathematical point of view.

We would like to deal with this type of equation:

$`Q_{n+1}(Z)`$ $`=`$ $`{\displaystyle _{\mathrm{}}^{\mathrm{}}}P(V)𝑑V{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}p(h)dh{\displaystyle _0^{\mathrm{}}}{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}Q_n(Z_i)dZ_i`$ (B.1)
$`\delta \left(Z{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}\mathrm{exp}\left\{\beta V\beta {\displaystyle \underset{j=1}{\overset{i1}{}}}h_j\right\}Z_i\right)`$
with the requirement that $`𝑑hp(h)h>0`$ and the initial condition $`P_0(Z)=\delta (Z1)`$. Following Ref.  we introduce the function:

$`G_n(x){\displaystyle _0^{\mathrm{}}}𝑑ZQ_n(Z)\mathrm{exp}\{e^{\beta x}Z\}`$ (B.2)
which satisfy this recurrence equation

$`G_{n+1}(x)={\displaystyle _{\mathrm{}}^{\mathrm{}}}P(V)𝑑V{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}p(h_i)dh_i{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}G_n(x+V+{\displaystyle \underset{j=1}{\overset{i1}{}}}h_j)`$ (B.3)
Let us make a few elementary observations concerning Eq. (B.3): if $`0G_m(x)1`$ for some $`m`$ and all $`x`$ then $`0G_n(x)1`$ for all $`x`$ and $`n>m`$; if $`limsup_x\mathrm{}G_n(x)=g_{\mathrm{}}<1`$ then $`G_{n+1}=0`$; if $`G_n(x)`$ is increasing and $`0<G_n(x)<1`$ for some $`x`$ (both these hypothesis are implied by Eq. (B.2)) then $`lim_x\mathrm{}G_{n+1}(x)=0`$. The stationary uniform solutions of Eq. (B.3) are $`G_n^A(x)=0`$ and $`G_n^B(x)=1`$. The first one is obviously stable. If we consider a small fluctuation around $`G_n^B(x)`$, $`G_n(x)=1+\rho _n(x)`$ we get:

$`\rho _{n+1}(x){\displaystyle _{\mathrm{}}^{\mathrm{}}}P(V)𝑑V{\displaystyle _{\mathrm{}}^{\mathrm{}}}{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}p(h)dh{\displaystyle \underset{i=1}{\overset{\mathrm{}}{}}}\rho _n(x+V+{\displaystyle \underset{j=1}{\overset{i1}{}}}h_j)`$ (B.4)
which can be diagonalized in Fourier space:

$`\widehat{\rho }_{n+1}(k){\displaystyle \frac{\widehat{P}(k)}{1\widehat{p}(k)}}\widehat{\rho }_n(k)\lambda (k)\widehat{\rho }_n(k)`$ (B.5)
Notice that $`|\lambda (k)|>1`$ for $`k`$ small enough and that $`|\lambda (k)|`$ diverges at $`k=0`$ in agreement with the previous observation that if $`G_n(x)=1\rho `$ than $`G_{n+1}(x)=0`$. The preceding observations lead us to the hypothesis that the $`n\mathrm{}`$ behavior of our problem is controlled by front-like solutions $`G_n(x)=g(xc(\beta )n)`$ interpolating between the stable state $`G_n^A(x)=0`$ at $`x\mathrm{}`$ and $`G_n^B(x)=1`$ at $`x\mathrm{}`$.

This scenario is easily confirmed in the case without disorder. If $`P(V)=\delta (VV_0)`$ and $`p(h)=\delta (hh_0)`$ one obtains $`P_n(Z)=\delta (Ze^{\beta c(\beta )n})`$, $`G_n(x)=\mathrm{exp}\{e^{\beta (xc(\beta )n)}\}`$ with

$`c(\beta )={\displaystyle \frac{1}{\beta }}\mathrm{log}{\displaystyle \frac{e^{\beta V_0}}{1e^{\beta h_0}}}`$ (B.6)
In the general case we assume the existence of front-like solutions with the large $`x`$ behavior $`G_n(x)1e^{\beta (xc(\beta )n)}+o(e^{\beta x})`$. The front velocity is obtained through the construction given in Eqs. (3.14-3.15) with

$`v(\beta ){\displaystyle \frac{1}{\beta }}\mathrm{log}\varphi (\beta )={\displaystyle \frac{1}{\beta }}\mathrm{log}{\displaystyle \frac{e^{\beta V}}{1e^{\beta h}}}`$ (B.7)
Notice that $`h>0`$ implies that $`e^{\beta h}<1`$ in some interval $`0<\beta <\beta _1`$ and that $`\beta _c<\beta _1`$. This remark allows us to sum the series $`_ke^{\beta h}^k`$ in the range $`0<\beta <\beta _c`$, thus obtaining Eq. (B.7). The same remark will be useful in the following.

Let us consider now the more rigorous approach used in Ref. . We start by defining the polymer model which corresponds to Eq. (B.1). We have to use a tree with a numerable set of branches stemming from each node. A node of the $`n`$-th generation is identified by $`n`$ integer numbers $`\underset{¯}{\omega }(\omega _1,\mathrm{},\omega _n)`$; its generation is denoted by $`|\underset{¯}{\omega }|`$. We denote by $`\underset{¯}{0}`$ the root node (i.e. the only node of the zeroth generation). We say that the node $`\underset{¯}{\omega }^{}`$ belonging to the $`m`$-th generation is a descendant of the node $`\underset{¯}{\omega }`$ of the $`n`$-th generation (and write $`\underset{¯}{\omega }\underset{¯}{\omega }^{}`$ if $`n<m`$ or $`\underset{¯}{\omega }\underset{¯}{\omega }^{}`$ if $`nm`$ ) if $`\omega _1=\omega _1^{},\mathrm{},\omega _n=\omega _n^{}`$. The node $`\underset{¯}{\omega }^{}`$ is said to be an older brother of the node $`\underset{¯}{\omega }`$ with $`|\underset{¯}{\omega }^{}|=|\underset{¯}{\omega }|=n`$ if $`\omega _1=\omega _1^{},\mathrm{},\omega _{n1}=\omega _{n1}^{}`$ and $`\omega _n>\omega _n^{}`$. A pair of random variables $`V(\underset{¯}{\omega })`$ and $`h(\underset{¯}{\omega })`$ is attached at each node. All these variables are statistically independent and have marginal distributions $`p(h)`$ (the $`h(\underset{¯}{\omega })`$’s) and $`P(V)`$ (the $`V(\underset{¯}{\omega })`$’s). A directed polymer is given by a pair of nodes $`\underset{¯}{\omega }^1\underset{¯}{\omega }^2`$. To each polymer we assign an energy as follows:

$`E(\underset{¯}{\omega }^1,\underset{¯}{\omega }^2)={\displaystyle \underset{\underset{¯}{\omega }^1\underset{¯}{\omega }\underset{¯}{\omega }^2}{}}V(\underset{¯}{\omega })+{\displaystyle \underset{\underset{¯}{\omega }^1\underset{¯}{\omega }\underset{¯}{\omega }^2}{}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^{}:\underset{¯}{\omega }^{}\text{ is an older}}{\text{brother of }\underset{¯}{\omega }}}{}}h(\underset{¯}{\omega }^{})`$ (B.8)
Moreover we use the shorthand $`E(\underset{¯}{0},\underset{¯}{\omega })E(\underset{¯}{\omega })`$ and define the following partition functions:

$`Z_n(\beta ){\displaystyle \underset{\underset{¯}{\omega }:|\underset{¯}{\omega }|=n}{}}e^{\beta E(\underset{¯}{\omega })}`$ (B.9)
$`Z_n(\beta |\underset{¯}{\omega })={\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^{}\underset{¯}{\omega }:}{|\underset{¯}{\omega }^{}||\underset{¯}{\omega }|=n}}{}}e^{\beta E(\underset{¯}{\omega },\underset{¯}{\omega }^{})}`$ (B.10)
The velocity of the front wave studied in the previous paragraphs corresponds in this language to the random variable:

$`c(\beta )\underset{n\mathrm{}}{lim}{\displaystyle \frac{1}{n\beta }}\mathrm{log}Z_n(\beta )`$ (B.11)
The model has two phases. In the high temperature phase ($`\beta \beta _c`$) the fluctuations of $`Z_n(\beta )`$ are small and

$`c(\beta )=\underset{n\mathrm{}}{lim}{\displaystyle \frac{1}{n\beta }}\mathrm{log}Z_n(\beta )=v(\beta )`$ (B.12)
In the low temperature phase ($`\beta >\beta _c`$) the fluctuations become large and $`c(\beta )`$ is fixed by simple convexity and monotonicity arguments. The key point of the approach used in Ref.  is to estimate these fluctuations by proving that, for $`\beta <\beta _c`$:

$`{\displaystyle \frac{Z_n(\beta )^\alpha }{Z_n(\beta )^\alpha }}\text{Bound}(\alpha ,\beta )`$ (B.13)
for some $`1<\alpha <2`$ uniformly in $`n`$. This is enough for obtaining Eq. (B.12).

Let us define the normalized variables $`M_n(\beta )Z_n(\beta )/Z_n(\beta )`$. In Ref.  the bound in Eq. (B.13) is obtained starting with the second moment of $`M_n(\beta )`$, and then refining the inequality for the fractional moments of order $`1<\alpha <2`$. Notice that looking at the $`m`$-th moment of the partition function is a well known method  for obtaining an upper estimate on the critical temperature (the estimate becomes worser as $`m`$ gets larger). Let us have a look at the first two integer moments:

$`Z_{n+1}(\beta )`$ $`=`$ $`e^{\beta V}{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}e^{\beta h}^kZ_n(\beta )`$ (B.14)
$`Z_{n+1}^2(\beta )`$ $`=`$ $`\left(e^{\beta V}{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}e^{\beta h}^k\right)^2\left[Z_n^2(\beta )Z_n(2\beta )\right]+`$ (B.15)
$`+e^{2\beta V}{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}e^{2\beta h}^k\left(1+2{\displaystyle \underset{l=1}{\overset{\mathrm{}}{}}}e^{\beta h}^l\right)Z_n(2\beta )`$
In general the $`m`$-th moment is finite (but not necessarily uniformly bounded) only if $`e^{m\beta h}<1`$ i.e. if $`\beta <\beta _1/m`$. There is no integer moment of order greater than one which remains finite in the interval $`(0,\beta _c)`$. This fact forces us to a slight modification of the proof presented in Ref. . We use the trivial identity:

$`Z_{n+1}(\beta )={\displaystyle \underset{\underset{¯}{\omega }:|\underset{¯}{\omega }|=1}{}}e^{\beta E(\underset{¯}{\omega })}Z_n(\beta |\underset{¯}{\omega })`$ (B.16)
and estimate the $`\alpha `$-th moment (with $`1<\alpha <2`$) as follows:

$`Z_{n+1}^\alpha (\beta )`$ $`=`$ $`\left\{{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^1:}{|\underset{¯}{\omega }^1|=1}}{}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^2:}{|\underset{¯}{\omega }^2|=1}}{}}e^{\beta [E(\underset{¯}{\omega }^1)+E(\underset{¯}{\omega }^2)]}Z_n(\beta |\underset{¯}{\omega }^1)Z_n(\beta |\underset{¯}{\omega }^2)\right\}^{\alpha /2}`$ (B.17)
$``$ $`{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^1:}{|\underset{¯}{\omega }^1|=1}}{}}{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^2:}{|\underset{¯}{\omega }^2|=1}}{}}e^{\frac{\alpha \beta }{2}[E(\underset{¯}{\omega }^1)+E(\underset{¯}{\omega }^2)]}Z_n^{\alpha /2}(\beta |\underset{¯}{\omega }^1)Z_n^{\alpha /2}(\beta |\underset{¯}{\omega }^2)`$
For a temperature such that $`\alpha \beta <\beta _1`$ we can take the averages and sum up the series:

$`Z_{n+1}^\alpha (\beta )`$ $``$ $`{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }:}{|\underset{¯}{\omega }|=1}}{}}e^{\alpha \beta E(\underset{¯}{\omega })}Z_n^\alpha (\beta )+{\displaystyle \underset{\genfrac{}{}{0pt}{}{\underset{¯}{\omega }^1\underset{¯}{\omega }^2:}{|\underset{¯}{\omega }^i|=1}}{}}e^{\frac{\alpha \beta }{2}[E(\underset{¯}{\omega }^1)+E(\underset{¯}{\omega }^2)]}Z_n^{\alpha /2}(\beta )^2`$ (B.18)
$``$ $`\varphi (\alpha \beta )Z_n^\alpha (\beta )+2\varphi (\alpha \beta ){\displaystyle \underset{l=1}{\overset{\mathrm{}}{}}}e^{\frac{\alpha \beta }{2}h}^lZ_n(\beta )^\alpha `$
Rewriting this formula for the normalized variables we get

$`M_{n+1}^\alpha (\beta )`$ $``$ $`\left[{\displaystyle \frac{\varphi (\alpha \beta )}{\varphi (\beta )^\alpha }}\right]M_n^\alpha (\beta )+2\left[{\displaystyle \frac{\varphi (\alpha \beta )}{\varphi (\beta )^\alpha }}\right]{\displaystyle \underset{l=1}{\overset{\mathrm{}}{}}}e^{\frac{\alpha \beta }{2}h}`$ (B.19)
$``$ $`\psi (\alpha ,\beta )M_n^\alpha (\beta )+\chi (\alpha ,\beta )`$
At this point we observe, following Ref. , that, if $`\frac{dv}{d\beta }(\beta )<0`$ (i.e. $`\beta <\beta _c`$) then we can choose $`\alpha >1`$ such that $`\psi (\alpha ,\beta )<1`$. The condition to be imposed on $`\alpha `$ for obtaining this inequality is $`\alpha <\beta _c/\beta `$ (notice that this inequality implies the previous one $`\alpha <\beta _1/\beta `$). The desired bound is obtained by using Gronwall lemma together with the fact that $`M_0^\alpha (\beta )=1`$:

$`M_n^\alpha (\beta )\psi ^n(\alpha ,\beta )+{\displaystyle \frac{1\psi ^n(\alpha ,\beta )}{1\psi (\alpha ,\beta )}}\chi (\alpha ,\beta )1+{\displaystyle \frac{1}{1\psi (\alpha ,\beta )}}\chi (\alpha ,\beta )`$ (B.20)