text:
# Surface induced ordering in thin film diblock copolymers: tilted lamellar phases

## I Introduction

Diblock copolymers are made up of two chemically distinct polymer chains which are covalently bonded together. The process of macroscopic phase separation usually occurring for incompatible chains is suppressed because of the imposed connectivity between the two blocks. Instead, the system may undergo a mesoscopic phase separation. The thermodynamic state of the system depends on two parameters : the fraction of the A monomers $`f=N_A/N`$ and $`\chi N`$, where $`N_A`$ and $`N_B`$ are the lengths of the A- and B-block, respectively, and $`N`$ is the polymerization index, $`N=N_A+N_B`$. The Flory parameter $`\chi `$ measures the interaction energy (in units of $`k_BT`$, the thermal energy) between two monomers and is positive if the two monomers repel each other. For symmetric melt ($`f=1/2`$) and small $`\chi `$ (high temperature) the disordered, homogeneous phase has the lowest free energy. Increasing $`\chi `$ above the order disorder transition (ODT) point, $`\chi =\chi _c`$, (lowering the temperature) results in a phase transition to a lamellar phase. For a fixed $`\chi >\chi _c`$, and as function of the A/B asymmetry ($`f1/2`$) the prevailing mesoscopic ordered phases can have hexagonal or cubic symmetries as well.

When a block copolymer (BCP) melt is put in contact with a surface, the surface reduces the chain entropy. In addition, it interacts chemically with the blocks, leading to a surface behavior which can be very different from that of the bulk. Fredrickson  has considered BCP in contact with a uniform surface having preferred interaction to one of the blocks. In the weak-segregation regime, he used mean-field theory to investigate systems both below and above the ODT. Above, but close to the ODT, the order parameter (being the deviation of the A monomer concentration from its average value $`f`$) has decaying oscillations characterized by a correlation length $`\xi `$. Approaching the ODT, $`\xi `$ diverges and below the ODT the system is characterized by a spatially modulated order parameter.

The situation is more complex for a copolymer melt confined between two surfaces. For a thin-film of BCP melt, the interplay of the spacing $`2L`$ between the surfaces, the Flory parameter $`\chi `$ and the surface interactions results in a rich interfacial behavior.  The phase behavior of thin BCP films subject to uniform surface fields has been investigated numerically using self-consistent fields (SCF) theory  and Monte-Carlo simulations, and was found to consist of parallel, perpendicular and mixed lamellae denoted $`L_{}`$, L and $`L_M`$, respectively. The latter $`L_M`$ phase has parallel lamellae extending from one surface, which are jointed in a T-junction defect with perpendicular lamellae extending from the opposite surface. At a given inter-surface spacing, increasing the (uniform) surface interactions promotes a parallel orientation with either A-type or B-type monomers adsorbed to the surface. However, if the spacing $`2L`$ between the surfaces is incommensurate with the lamellar periodicity, or the incompatibility $`\chi `$ is increased, a perpendicular orientation is favored.

In the present paper we analytically derive expressions for the order parameter of a BCP melt confined between two parallel flat surfaces, below the bulk ODT temperature and in the weak-segregation limit. In Sec. II we introduce a model of a confined BCP melt in contact with either homogeneous or sinusoidally patterned surfaces. Contrary to the system above the ODT, studied earlier in a separate work, a linear response theory assuming small order parameter as a response to the surface fields is inadequate, since the bulk phase has an inherent spatially varying structure. Instead, in Sec. III an expansion is carried out around a tilted lamellar phase of the bulk. A simple ansatz for the deviation of the order parameter from its bulk value is suggested, utilizing the symmetry of the problem. A close similarity is shown between this problem and the symmetric tilt grain boundaries, with mathematical solution very similar to what has been derived in Ref. . In Sec. IV the problem of one patterned surface is extended to a melt confined between two surfaces, one being chemically patterned while the second is chemically homogeneous. We obtain confined tilted lamellar phases, and, in particular, $`L_M`$ phases. The lamellae extending from the patterned surface merge with the parallel ordering induced by the homogeneous surface.

## II The model

When a BCP system in the disordered (high temperature) phase is cooled below the ODT, a lamellar phase forms  for $`f=1/2`$ (symmetric) or when $`|f1/2|`$ is small. The behavior of such systems was modeled numerous times in the past  using coarse grained Ginzburg-Landau free energy. A possible form (in units of $`k_BT`$) used throughout this paper is:

$$_b=\left\{\frac{1}{2}\tau \varphi ^2+\frac{1}{2}h\left[\left(^2+q_0^2\right)\varphi \right]^2+\frac{u}{4!}\varphi ^4\mu \varphi \right\}\mathrm{d}^3𝐫$$
(1)
where

$`q_01.95/R_g,`$ (2)
$`\tau =2\rho N\left(\chi _c\chi \right),`$ (3)
$`\chi _c10.49/N,`$ (4)
$`h=3\rho c^2R_g^2/2q_0^2.`$ (5)
The copolymer order parameter $`\varphi `$ is defined as $`\varphi (𝐫)\varphi _A(𝐫)f`$, the deviation of the local A monomer concentration from its average value. $`R_g`$ is the gyration radius of the chains ($`R_g^2\frac{1}{6}Na^2`$ for Gaussian chains) and the chain density $`\rho `$ is equal to $`1/Na^3`$ for an incompressible melt. The chemical potential is $`\mu `$ while $`u/\rho `$ and $`c`$ are dimensionless parameters of order unity. Hereafter we set the monomer size to unity, $`a=1`$, expressing all lengths in units of $`a`$. By choosing $`u/\rho =c=1`$ (and recalling that $`f=1/2`$), all parameters in the model are given in terms of $`\chi `$ and $`N`$.

Above the ODT, $`\chi <\chi _c`$, the free energy (1) describes a system in the homogeneous, disordered phase having a uniform order parameter $`\varphi =0`$. This system has been previously studied by us in Ref. . Below the ODT, $`\chi >\chi _c`$, the lamellar phase of period $`d_0=2\pi /q_0`$ becomes stable. Close to the ODT, $`\chi \chi _c`$, (weak segregation limit), the order parameter is given in the single $`q`$-mode approximation as $`\varphi (𝐫)=\varphi _0+\varphi _q\mathrm{cos}(𝐪_\mathrm{𝟎}𝐫)`$, and for symmetric BCP ($`f=1/2`$), used throughout the paper, $`\varphi (𝐫)=\varphi _0=0`$. It is worthwhile to mention that similar free energy functionals have been used to describe bulk and surface phenomena in diblock copolymers, amphiphilic systems,  Langmuir films  and magnetic (garnet) films.

The interaction of the BCP with the confining surfaces is assumed to be short-range and limited to the surface only. The surface free energy $`_s`$ (in units of $`k_BT`$) has the form:

$$_s=\left\{\sigma (𝐫_𝐬)\varphi (𝐫_𝐬)+\tau _s\varphi ^2(𝐫_𝐬)\right\}\mathrm{d}^2𝐫_𝐬$$
(6)
where the integration is carried out over all surface positions $`\{𝐫_𝐬\}`$. At a point $`𝐫_𝐬`$ on the surface, the first term is proportional to the order parameter, with $`\sigma (𝐫_𝐬)`$ being a surface field. The magnitude $`\sigma (𝐫_𝐬)`$ of this surface field can be controlled by coating the substrate with random copolymers. The second (quadratic) term allows us to describe cases where the local surface segregation is different than the bulk: a positive $`\tau _s`$ means local increase of the Flory parameter $`\chi `$ and a lower phase transition temperature.

The surface effects are contained in the correction to the order parameter

$$\delta \varphi (𝐫)\varphi (𝐫)\varphi _b(𝐫)$$
(7)
where the bulk order parameter $`\varphi _b(𝐫)`$ in the symmetric lamellar phase is given by

$`\varphi _b(𝐫)`$ $`=`$ $`\varphi _q\mathrm{cos}\left(𝐪_\mathrm{𝟎}𝐫\right),`$ (8)
$`\varphi _q^2`$ $`=`$ $`8\tau /u.`$ (9)
The bulk $`\varphi _b`$ does not depend on surface properties, and recall that $`\tau <0`$ below the ODT. The total free energy $`=_b+_s`$ is now expanded about its bulk value $`[\varphi _b]`$ to second order in $`\delta \varphi `$ : $`=[\varphi _b]+\mathrm{\Delta }`$, with

$`\mathrm{\Delta }`$ $`=`$ $`{\displaystyle }\{[(\tau +hq_0^4)\varphi _b+{\displaystyle \frac{1}{6}}u\varphi _b^3+hq_0^2^2\varphi _b\mu ]\delta \varphi `$ (10)
$`+`$ $`{\displaystyle \frac{1}{2}}(\tau +{\displaystyle \frac{1}{2}}u\varphi _b^2)\left(\delta \varphi \right)^2+{\displaystyle \frac{1}{2}}h\left[(^2+q_0^2)\delta \varphi \right]^2\}\mathrm{d}^3𝐫`$ (11)
$`+`$ $`{\displaystyle \left\{\sigma (𝐫_s)\delta \varphi (𝐫_s)+\tau _s\left(2\varphi _b(𝐫_s)\delta \varphi (𝐫_s)+\delta \varphi (𝐫_s)^2\right)\right\}\mathrm{d}^2𝐫_s}`$ (12)
This expansion is valid in the weak segregation limit and for small enough surface fields. In the next section we find the function $`\delta \varphi (x,y,z)`$ that minimizes the free energy functional $`\mathrm{\Delta }`$ for a given choice of bulk morphology $`\varphi _b(𝐫)`$ and surface field $`\sigma (𝐫_𝐬)`$.

## III BCP melt confined by one patterned surface

When the confining substrate is spatially modulated, at least one additional length scale enters the problem. Numerical studies of thin BCP film below the ODT temperature in the presence of sinusoidally patterned surfaces of period $`d_x`$ have been carried out by Petera and Muthukumar. It was found that the lamellae are tilted with an angle $`\theta \mathrm{arccos}(d_0/d_x)`$ with respect to the normal to the surface. We proceed along similar lines, assuming that the pattern located at $`y=0`$ \[see Fig. 1(a)\] is described by a single harmonic,

$$\sigma (x,z)=\sigma (x)=\sigma _0+\sigma _q\mathrm{cos}(q_xx)$$
(13)
and is translational invariant in the $`z`$-direction. The parameter $`\sigma _q`$ sets the strength of the modulation mode, while the average $`\sigma (x)`$ is given by $`\sigma _0`$. At this point we assume $`\sigma _0=0`$, hence the surface is overall neutral to the A/B adsorption. Furthermore, the periodicity $`d_x=2\pi /q_x`$ along the $`x`$–axis is assumed to be longer than the natural lamellar periodicity $`d_0`$ in the bulk, $`d_x>d_0`$.

The surface field $`\delta \varphi `$ is the response of the BCP system to the presence of the surface field $`\sigma `$. It is expected to vanish far away from the surface:

$$\underset{y\mathrm{}}{lim}\delta \varphi (x,y,z)=0$$
(14)
recovering the bulk $`\varphi =\varphi _b`$ phase. In general, the bulk lamellae can be tilted with respect to the $`y=0`$ surface:

$$\varphi _b(x,y)=\varphi _q\mathrm{cos}\left(q_0\mathrm{cos}\theta x+q_0\mathrm{sin}\theta y+\alpha \right)$$
(15)
and this form of $`\varphi _b`$ will be used as a zeroth order approximation to $`\varphi (x,y)`$. Note that the bulk free energy Eq. (1) is invariant with respect to rotations and translations of the lamellae, and does not depend on the tilt angle $`\theta `$ and the phase shift $`\alpha `$. These parameters are chosen such that they minimize the surface free energy Eq. (6). The tilt angle $`\theta `$ determines the overlap of the lamellae with the surface inhomogeneities, while the phase shift $`\alpha `$ distinguishes between two identical tilts, in-phase ($`\alpha =0`$) and out-of-phase ($`\alpha =\pi `$) with respect to the surface. Upon integrating the $`x`$ variable, the surface free energy Eq. (6) is minimized if the angle $`\theta `$ obeys $`\mathrm{cos}\theta =q_x/q_0`$ and $`\alpha =\pi `$. Therefore, we use below a bulk phase $`\varphi _b`$ given by

$`\varphi _b=\varphi _q\mathrm{cos}\left(q_xx+q_yy\right)`$ (16)
$`q_x=q_0\mathrm{cos}\theta ,q_y=q_0\mathrm{sin}\theta ,`$ (17)
For the correction order parameter $`\delta \varphi `$ we choose

$$\delta \varphi (x,y)=g(y)\mathrm{cos}(q_xx).$$
(18)
This correction describes a lamellar ordering perpendicular to the surface, and commensurate with its periodicity $`d_x=2\pi /q_x`$. The overall morphology of the lamellae is a superposition of the correction field $`\delta \varphi `$ with the bulk tilted phase, having a periodicity $`d_0`$. The region where the commensurate correction field $`\delta \varphi `$ is important is dictated by the amplitude and range of the amplitude function $`g(y)`$. It is now possible to use ansatz (18) to integrate out the $`x`$ dependence in the free energy, Eq. (10), resulting in an effective one-dimensional free energy

$`\mathrm{\Delta }F(y)`$ $`=`$ $`{\displaystyle \frac{1}{2}}\tau \mathrm{cos}^2(q_yy)g^2+{\displaystyle \frac{1}{4}}h\left(q_y^2g+g^{\prime \prime }\right)^2`$ (19)
$`+`$ $`{\displaystyle \frac{1}{2}}\left[\sigma _qg+\tau _s\left(2\varphi _qg+g^2\right)\right]\delta (y)`$ (20)
For convenience we have included the surface free energy terms of Eq. (6) by the use of a Dirac delta function $`\delta (y)`$.

Applying the variational principle with respect to $`g(y)`$ yields a master equation:

$$\left[A+C\mathrm{cos}(2q_yy)\right]g(y)+Bg^{\prime \prime }(y)+g^{\prime \prime \prime \prime }(y)=0,$$
(21)
with parameters $`A,B`$ and $`C`$ given by:

$`A`$ $`=`$ $`\tau /h+q_y^4,`$ (22)
$`B`$ $`=`$ $`2q_y^2,`$ (23)
$`C`$ $`=`$ $`\tau /h.`$ (24)
The equation is linear in $`g(y)`$ since the free energy is expanded to second order around its bulk solution $`\varphi _b`$. Clearly the bulk solution ($`g0`$) solves the Euler-Lagrange equation, and hence Eq. (21) is homogeneous. The boundary conditions on the $`y=0`$ surface are

$`\left(\sigma _q2\tau _s\varphi _q\right)/h+2\tau _sg(0)/h+q_y^2g^{}(0)+g^{\prime \prime \prime }(0)`$ $`=`$ $`0,`$ (25)
$`q_y^2g(0)+g^{\prime \prime }(0)`$ $`=`$ $`0.`$ (26)
Hence the fourth order differential equation (21) has to satisfy two boundary conditions, mixing the value $`g(0)`$ and its first three derivatives at the surface.

Consider the Euler-Lagrange equation (21) obeyed by the function $`g(y)`$. It is similar to the Schröedinger equation for an electron in a periodic one–dimensional potential $`V(y)=C\mathrm{cos}(2q_yy)`$, the “kinetic energy” term being proportional to $`B`$, and the electron “ total energy” $`A`$. Note that unlike the quantum mechanical problem, here we have in addition a fourth order derivative term $`g^{\prime \prime \prime \prime }`$. Moreover, the coefficient $`B`$ depends on the periodicity of the potential. Nevertheless, the general form of $`g(y)`$ can be written, similar to the quantum mechanical problem, in terms of the Bloch form:

$$g(y)=e^{ky}\underset{n}{}a_ne^{2inq_yy}+c.c.$$
(27)
The surface induced deformations of lamellar phases are similar to the deformations appearing in the symmetric tilt grain boundaries.  The plane of symmetry between adjacent grains corresponds to the solid confining surface of our system, and in both cases packing frustration near the interface plays an important role. However, the fact that the surface can have (nonuniform) interactions with the copolymer melt results in a richer set of phenomena in the system studied here.

We now briefly mention how Eq. (21) can be solved. More details can be found in Refs.  and . The form (27) is substituted in Eq. (21) yielding a recurrence relation between the coefficients $`\{a_n\}`$. Only for a special value of the eigenvalue (wavenumber) $`k`$, the series in Eq. (27) converges. Once $`k`$ is determined iteratively, the full solution of Eq. (21) is given analytically by Eq. (27). If $`k`$ is a solution, then so are $`k`$, $`k^{}`$ and $`k^{}`$, recalling that Eq. (21) is a fourth-order differential equation. The periodicity of the “potential term” is determined by $`q_y`$, which depends on the surface periodicity $`d_x=2\pi \mathrm{tan}\theta /q_y`$. Modification of $`d_x`$ smoothly changes $`\mathrm{Im}(k)`$ until it becomes equal to an integer multiple of $`q_y`$. At these degenerate values of $`d_x`$, the plot of $`\mathrm{Re}(k)`$ as a function of $`d_x`$ has two branches, each branch corresponding to one possible solution of $`k`$. The values of $`d_x`$ where the degeneracy appears are determined by the proximity to the ODT. For a semi-infinite BCP bounded by a single surface, the function $`g(y)`$ vanishes at infinity, allowing the use of only those $`k`$ eigenvalues whose real part is positive, $`g\mathrm{exp}(\mathrm{Re}(k)y)0`$ as $`y\mathrm{}`$.

In Fig. 2 we examine the BCP melt confined by one sinusoidally patterned surface, $`\sigma (x)=\sigma _q\mathrm{cos}(q_xx)`$, with no preference on average to one of the blocks, $`\sigma =0`$, for several values of surface period $`d_x=2\pi /q_x`$ and for fixed value of the Flory parameter $`\chi >\chi _c`$. The main effect of increasing the surface period $`d_x`$ with respect to $`d_0`$ is to stabilize tilted lamellae, with increasing tilt angle. Note that even for $`d_x=d_0`$ \[Fig. 2a\] yielding no tilt, the perpendicular lamellae have a different structure close to the surface as is induced by the surface pattern.

Although the surface interactions are assumed to be strictly local, the connectivity of the chains causes surface-bound distortions to propagate into the bulk of the BCP melt. Using the analogy with the grain boundary problem, we conclude that the width $`D`$ of the deformation close to the surface has a $`D1/\theta `$ scaling for small $`\theta `$, which means that $`D(1d_0/d_x)^{1/2}`$. However, in a thin film system as is realized in experiments, this width may be too large to be detected if $`D`$ is larger than the inter-surface separation $`2L`$.

The copolymer deformations are particularly important close to the ODT ($`\chi \chi _c`$), where deviations from the optimal lamellar shape do not cost much energy (in contrast to the strong segregation case $`\chi \chi _c`$), and the melt can adjust more easily to the surface pattern. In Fig. 3 we show the same series of plots as in Fig. 2, but with the value of the Flory parameter $`\chi N=10.6`$, closer to its critical value, $`\chi _c10.49`$. The perfect lamellar shape is more distorted.

Concentration variations are governed by the profile function $`g(y)`$, and increase as $`\sigma _q`$ increases. In Fig. 4 the Flory parameter $`\chi `$ and the repeat period $`d_x`$ are held fixed, while the correction $`\delta \varphi `$ increases as $`\sigma _q`$ is increased from $`1`$ in (a), to $`2`$ in (b), to $`4`$ in (c), in units of $`hq_0^3\varphi _q`$. Strong surface fields give rise to strong chain stretching near the surface. Very large amplitude $`\sigma _q`$ increases $`\delta \varphi `$ on the expense of the bulk order parameter, $`\varphi _b`$, which remains constant. Note the similarity of these plots to the contour plots of Ref. .

## IV BCP thin films: One homogeneous and one patterned surface

Until now we have considered the semi-infinite problem of a BCP melt confined by one patterned surface. It is of experimental and theoretical interest to study thin films of BCP when they are confined between a heterogeneous (patterned) surface and a second chemically homogeneous surface. This situation is encountered when a thin BCP is spread on a patterned surface. The second interface is the film/air interface (neglecting any height undulations), and is homogeneous. Usually the free surface has a lower surface tension with one of the two blocks. This bias can be modeled by adding a constant $`\sigma _0`$ term to the $`\sigma (x)`$ surface field. For simplicity, we assume that the $`y=L`$ surface remains purely sinusoidal while the $`y=L`$ surface is attractive to one of the A/B blocks:

$`\sigma (x)`$ $`=`$ $`\sigma _q\mathrm{cos}(q_xx),\text{at }y=L,`$ (28)
$`\sigma (x)`$ $`=`$ $`\sigma _0,\text{at }y=L\text{.}`$ (29)
A neutral surface at $`y=L`$ is obtained as a special case with $`\sigma _0=0`$. The striped surface pattern is at $`y=L`$ and the expression (16) for the bulk tilted phase is modified accordingly,

$$\varphi _b=\varphi _q\mathrm{cos}\left[q_xx+q_y(y+L)\right]$$
(30)
The surface free energy per unit length in the $`z`$-direction, Eq. (6), reads:

$`_s`$ $`=`$ (33)
$`{\displaystyle }\mathrm{d}x\{\sigma _q\mathrm{cos}(q_xx)\varphi (x,y=L)+\tau _s\varphi ^2(x,y=L)`$
$`+\sigma _0\varphi (x,y=L)+\tau _s\varphi ^2(x,y=L)\},`$
where for simplicity the surface parameter $`\tau _s`$ is taken to be the same on the two boundaries $`y=\pm L`$.

For inter-surface separations $`2L`$ much larger than the bulk lamellar period, $`d_0`$, the BCP morphology is similar to the one-surface case. Bringing the two surfaces closer together changes the melt morphology. In our formalism, $`\varphi _b(x,y)`$, being the zero-order approximation, remains unchanged, while the correction $`\delta \varphi `$ changes (recalling that the spatial variations of $`\varphi _b`$, Eq. (30), comes from the imposed tilt between the bulk lamellar phase and the surface direction). The homogeneous surface field at $`y=L`$ induces a lamellar layering parallel to the surface, since the two A/B blocks are covalently linked together. The simplest way to account for this layering effect is to extend Eq. (18) to include an $`x`$-independent term $`w(y)`$ in our ansatz for the order parameter:

$$\delta \varphi (x,y)=g(y)\mathrm{cos}(q_xx)+w(y).$$
(34)
The free energy of the system is now written as a sum of two contributions:

$$\mathrm{\Delta }=\left\{\mathrm{\Delta }F_g+\mathrm{\Delta }F_w\right\}dy,$$
(35)
where $`\mathrm{\Delta }F_g`$ is given by

$`\mathrm{\Delta }F_g(y)`$ $`=`$ $`{\displaystyle \frac{1}{2}}\tau \mathrm{cos}^2(q_yy)g^2+{\displaystyle \frac{1}{4}}h\left(q_y^2g+g^{\prime \prime }\right)^2`$ (36)
$`+`$ $`{\displaystyle \frac{1}{2}}\left(\sigma _qg+\tau _s\left(2\varphi _qg+g^2\right)\right)\delta (y+L)`$ (37)
$`+`$ $`{\displaystyle \frac{1}{2}}\tau _s\left(2\varphi _q\mathrm{cos}(2q_yL)g+g^2\right)\delta (yL)`$ (38)
and

$`\mathrm{\Delta }F_w(y)`$ $`=`$ $`{\displaystyle \frac{1}{2}}\tau w^2+{\displaystyle \frac{1}{2}}h\left(q_0^2w+w^{\prime \prime }\right)^2\mu w`$ (39)
$`+`$ $`\left(\sigma _0w+\tau _sw^2\right)\delta (yL)+\tau _sw^2\delta (y+L).`$ (40)
We note here that in the expansion of the free energy to second order in $`\delta \varphi `$ the mixed terms which couple $`w`$ and $`g`$ in $`\mathrm{\Delta }`$ vanish. Again, the $`w`$-dependent terms in the surface free energy Eq. (33) are expressed via a Dirac delta function. The chemical potential $`\mu `$ couples only to $`w(y)`$ and not to $`g(y)`$, and fixes the total A/B ratio in the system as is imposed by the parameter $`f`$ of the BCP chains (taken to be $`f=1/2`$ in this paper). The Euler-Lagrange equation corresponding to this free energy, Eq. (39), is a linear, ordinary fourth-order differential equation. Its solution can be written as a superposition of four exponential functions and a constant term:

$`w(y)`$ $`=`$ $`A_we^{k_wy}+B_we^{k_wy}`$ (41)
$`+`$ $`A_w^{}e^{k_w^{}y}+B_w^{}e^{k_w^{}y}+const.`$ (42)
with

$$k_w^2=q_0^2+\sqrt{\tau /h}.$$
(43)
The boundary conditions obeyed by $`w(y)`$ at $`y=\pm L`$ are

$`q_0^2w(\pm L)+w^{\prime \prime }(\pm L)=0,`$ (44)
$`2\tau _sw(L)+hq_0^2w^{}(L)+hw^{\prime \prime \prime }(L)=0,`$ (45)
$`\sigma _0+2\tau _sw(L)hq_0^2w^{}(L)hw^{\prime \prime \prime }(L)=0,`$ (46)
and those obeyed by $`g(y)`$ are similar to those in Eqs. (25):

$`q_y^2g(\pm L)+g^{\prime \prime }(\pm L)=0,`$ (47)
$`\sigma _q2\tau _s\varphi _q+2\tau _sg(L)+hq_y^2g^{}(L)+hg^{\prime \prime \prime }(L)=0,`$ (48)
$`2\tau _s\varphi _q\mathrm{cos}(2q_yL)+2\tau _sg(L)hq_y^2g^{}(L)hg^{\prime \prime \prime }(L)=0.`$ (49)
In general the wavenumber $`k_w`$ and the amplitudes $`A_w`$ and $`B_w`$ are complex. Expressions (43) and (41) are identical to the zero $`q`$-mode response of a BCP in presence of a surface field for a system found above its ODT temperature in the disordered phase. Expression (41) has decaying modulations, as the wavevector $`k_w`$ has both real and imaginary parts. The decay length $`\xi =1/\mathrm{Re}(k_w)`$ diverges as $`(\chi \chi _c)^{1/2}`$, while the modulation periodicity is slightly longer than that of the bulk lamellar phase (to order $`\chi \chi _c`$). Lastly, the constant term in Eq. (41) \[and the chemical potential $`\mu `$ in Eq. (39)\] are determined by requiring that the total A/B ratio of monomers is conserved, $`w(y)dy=0`$.

Figure 5 demonstrates two different thin-film morphologies, for a melt confined between two patterned surfaces, one at $`y=L=2d_0`$ and another which is homogeneously attractive to the B monomers at $`y=L=2d_0`$. The BCP close to the lower and upper surfaces show different behavior, as the bottom surface is chemically patterned and the top is uniform. In Fig. 5(a) the top surface has a weak overall preference to the B monomers (in black), while in (b) this attraction is stronger, thus enhancing parallel lamellar ordering (layering).

This tilted lamellar phase confined by one homogeneous and one patterned surface is a generalization of the mixed (perpendicular and parallel) lamellar phase, usually referred to as $`L_M`$. The latter morphology occurs when the surface (imposed) periodicity $`d_x`$ is equal to the bulk periodicity $`d_0`$. This “T-junction” morphology, shown in Fig. 6, has perpendicular lamellae extending from the patterned surface. The homogeneous field at the opposite surface favors a parallel orientation of the lamellae. The crossover region between the two orientations is found in the middle of the film, and its morphology depends on the temperature, as can be seen by comparing (a) in which $`\chi N=11`$ with (b) where $`\chi N=10.7`$. In the latter case the effect of the homogeneous field is more evident, as parallel ordering extends from the top surface. For homogeneous surfaces and symmetric ($`f=1/2`$) BCP melts, these phases were considered unstable with respect to the $`L_{}`$ and $`L_{}`$ phases,  recalling that bulk T-junction defects are not usually found in experiments.  However, strong enough modulated surface fields stabilize the tilted lamellar phases, and in particular the $`L_M`$.

It is important to check the self-consistency of our free energy variation by studying the difference between the film and bulk free energies. We show the free energy decrease as a function of surface separation $`2L`$ in Fig. 7, where $`\mathrm{\Delta }`$ is taken from Eq. (35). The free energy has a characteristic oscillatory behavior as a function of surface separation $`2L`$. The period of these energy barriers is different from the bulk lamellar spacing $`d_0`$, and depends on the tilt angle of the lamellae.

For separations larger than what is shown in the figure ($`2L>8d_0`$) the free energy difference tends to zero, since the correction field $`\delta \varphi `$ has an important contribution only at a finite range away from the surface. As one approaches the ODT temperature the free energy difference $`\mathrm{\Delta }`$ becomes larger compared to the bulk one because $`D`$, the width of surface induced ordering, increases and the bulk free energy decreases. Far from the ODT, i.e. in the strong segregation limit, the bulk lamellar ordering is strong, and these surface corrections are important only for large surface fields $`\sigma `$.

## V conclusion

We have employed a Ginzburg-Landau expansion of the free energy to study analytically the confinement effects of block copolymers between two surfaces as well as the interfacial behavior close to a single surface. For a BCP melt below its bulk ODT temperature, tilted lamellar phases are shown to exist between one patterned and one homogeneous surface if the chemical pattern is strong enough, and if no other defects exist inside the film.

Our approach consists of expressing the copolymer order parameter $`\varphi `$ as a sum of two terms. The first term accounts for the bulk phase $`\varphi _b`$ having the unperturbed periodicity $`d_0`$, while the presumably small correction, $`\delta \varphi `$, is entirely due to the surface and has the surface periodicity $`d_x`$.  The extent of the commensurate region far from the surface is determined by the range of the amplitude function $`g(y)`$ introduced above, and it diverges at the ODT. This mean-field approach is valid close to the ODT, but not too close, where critical fluctuations are important. In addition, the linear response field $`\delta \varphi `$ is assumed small, $`\delta \varphi \varphi _b`$, and this can be justified if the surface field $`\sigma `$ is not too large.

The deviation from the perfect diagonal lamellae $`\varphi _b`$ relieves the BCP elastic energy near the surface, and induces an almost locally-parallel ordering. The analytic expressions presented here capture the effects Petera and Muthukumar investigated using the self-consistent field theory.  Moreover, in the weak segregation limit studied here, $`\chi \chi _c`$, the energetic difference between the lamellar and the disordered phases is small, leading to lamellae which are more amenable to deformations. In this weak segregation regime the correction to the order parameter, $`\delta \varphi `$, gives an important contribution to the free energy (as can be seen quantitatively in Fig. 7), and to the resulting morphology. This description, however, is accurate only when the surface interactions at $`y=L`$ are large, and the overall state is that of the tilted lamellae morphology.

We find a similarity between thin BCP films and that of the symmetric tilt grain boundaries. In the latter system, the tilt angle is determined by the externally imposed relative orientation of the two grains. In both systems, packing frustration of the polymer chains occur at the interface. However, the BCP film we consider here has a richer behavior because the model contains a real surface interacting chemically with the chains. The analogy shows that the width $`D`$ of surface deformation scales as $`D(1d_0/d_x)^{1/2}`$, for $`1d_0/d_x1`$.

We consider in particular the case where one of the surfaces uniformly prefers on of the blocks. This can be, for example, the free surface of the film (polymer/air interface) and is accommodated in our model by considering an additional response field, $`w(y)`$. Tilted lamellae appear at the patterned surface while parallel lamellae are created at the opposite surface, generalizing the mixed lamellar phases $`L_M`$ found for homogeneous surfaces.  Morphologies similar to T–junction defects are then obtained when the pattern period is the natural period. Although the energetic penalty for a T–junction in the bulk is high, chemically interacting surfaces can stabilize these structures.

The field $`w(y)`$ is also used to describe the perpendicular $`L_{}`$ and parallel oriented $`L_{}`$ lamellar phases found in the presence of uniform surfaces. The free energies of these phases change considerably under the influence of the surface fields, and hence the features of the phase diagram may be different from that of the strong segregation regime.

###### Acknowledgements.

The authors would like to thank G. Krausch, M. Muthukumar, G. Reiter, T. Russell, M. Schick and U. Steiner for useful discussions. Partial support from the U.S.-Israel Binational Foundation (B.S.F.) under grant No. 98-00429 and the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities — centers of Excellence Program is gratefully acknowledged.     * Figure 1: Schematic drawing of the BCP film. In (a) the BCP melt of periodicity $`d_0`$ is confined by a flat patterned surface at $`y=0`$. The tilt angle with the normal to the surface is $`\theta `$, (see Sec. III). In (b) the melt is confined by a patterned surface at $`y=L`$ and a homogeneous surface at $`y=L`$ (Sec. IV).
* Figure 2: Tilted lamellar phase between two parallel patterned surfaces. The surface patterning is modeled by the term $`\sigma _q\mathrm{cos}(2\pi x/d_x)`$. The lamellae tilt angle $`\theta =\mathrm{arccos}(d_0/d_x)`$ increase as the periodicity of the surface $`d_x`$ increase: $`\theta =0`$ for $`d_x=d_0`$ in (a), $`\theta 48.1^o`$ for $`d_x=\frac{3}{2}d_0`$ in (b) and $`\theta 70.5^o`$ for $`d_x=3d_0`$ in (c). The correction field $`\delta \varphi `$ is more important for large tilt angles, as it relieves the elastic stress near the surface. In the plots $`\sigma _q/hq_0^3\varphi _q=1`$ and the Flory parameter, $`N\chi =11.5`$. In this and subsequent figures $`\tau _s/hq_0^3=0.1`$ and maximum (A-rich) and minimum (B-rich) values of $`\varphi `$ correspond to white and black colors, respectively.
* Figure 3: The same sequence of tilt angles as in Fig. 2, but with the Flory parameter $`N\chi =10.8`$ much closer to its critical value $`N\chi _c10.49`$. The sinusoidally modulated surface field $`\sigma (x)`$ causes strong distortions of the tilted lamellar phase \[parts (b) and (c)\], even farther away from the surface.
* Figure 4: Variation of the tilted lamellar morphology with $`\sigma _q`$, the amplitude of surface fields. The value of $`\sigma _q/hq_0^3\varphi _q`$ is varied from $`1`$ in (a), to $`2`$ in (b), to $`4`$ in (c), while the Flory parameter $`N\chi =11>N\chi _c`$, and the repeat period $`d_x=\frac{3}{2}d_0`$ are held fixed.
* Figure 5: A contour plot for a BCP melt between a top homogeneous surface at $`y=L`$, and a modulated bottom surface at $`y=L`$. The inter-surface separation $`2L`$ is chosen to be $`4d_0`$ and the modulated surface amplitude is $`\sigma _q/hq_0^3\varphi _q=2`$. The homogeneous top field is $`\sigma _0/hq_0^3\varphi _q=0.6`$ in (a), and larger $`\sigma _0/hq_0^3\varphi _q=2`$ in (b), preferring adsorption of the B monomers (black). The effect of this field is clearly seen close to the $`y=L`$ surface. In both plots the Flory parameter was chosen to be $`N\chi =11`$ and the repeat period of the bottom surface is $`d=\frac{3}{2}d_0`$.
* Figure 6: A BCP confined film showing a crossover from perpendicular lamellae at the $`y=L=2d_0`$ surface to parallel lamellae at $`y=L`$. The pattern on the bottom surface, $`\sigma (x)=\sigma _q\mathrm{cos}(q_0x)`$, has the bulk periodicity $`d_0`$, and amplitude $`\sigma _q=2hq_0^3`$, while the top surface ($`y=L`$) is homogeneously attractive to the B polymer (in black), $`\sigma _0=4hq_0^3`$. In (a) the Flory parameter is $`N\chi =11`$, while in (b) the temperature is closer to the ODT, $`N\chi =10.7`$.
* Figure 7: The correction free energy $`\mathrm{\Delta }`$ (divided by $`[\varphi _b]`$, the bulk lamellar free energy) as a function of the film thickness $`2L`$. Lengths are scaled by the bulk lamellar period $`d_0`$. The period of the oscillations characterizing the free energy $`\mathrm{\Delta }`$ is different from $`d_0`$, because the lamellae are tilted with respect to the surface. For all points in the plot, the modulated surface field at $`y=L`$ has an amplitude $`\sigma _q/hq_0^3\varphi _q=0.5`$ and a period $`d_x=2\pi /q_x=\frac{3}{2}d_0`$, while the surface field at $`y=L`$ is homogeneous with $`\sigma _0=\sigma _q`$. The Flory parameter is $`N\chi =10.7`$ and $`\tau _s=0.7hq_0^3`$.


format: text

text:
# Complexity Through Nonextensivity

\[

## Abstract

The problem of defining and studying complexity of a time series has interested people for years. In the context of dynamical systems, Grassberger has suggested that a slow approach of the entropy to its extensive asymptotic limit is a sign of complexity. We investigate this idea further by information theoretic and statistical mechanics techniques and show that these arguments can be made precise, and that they generalize many previous approaches to complexity, in particular unifying ideas from the physics literature with ideas from learning and coding theory; there are even connections of this statistical approach to algorithmic or Kolmogorov complexity. Moreover, a set of simple axioms similar to those used by Shannon in his development of information theory allows us to prove that the divergent part of the subextensive component of the entropy is a unique complexity measure. We classify time series by their complexities and demonstrate that beyond the ‘logarithmic’ complexity classes widely anticipated in the literature there are qualitatively more complex, ‘power–law’ classes which deserve more attention.

\]

The problem of quantifying complexity is very old. Interest in the field has been fueled by three sorts of questions. First, one would like to make precise an impression that some systems, such as life on earth or a turbulent fluid flow, evolve toward a state of higher complexity, and one would like to classify these states; this is the realm of dynamical systems theory. Second, in choosing among different models that describe an experiment, one wants to quantify a preference for simpler explanations or, equivalently, provide a penalty for complex models that can be weighed against the more conventional goodness of fit criteria; this type of question usually is investigated in statistics. Finally, there are questions about how hard it is to compute or to describe the state of a complex system; this is the area of formal mathematics and computer science.

Research in each of these three directions has given birth to numerous definitions of complexity. The usual objective is to make these definitions focused enough to be operational in particular contexts but general enough to connect with our intuitive notions. For many years the dominant candidate for a universal measure has been the mathematically rigorous notion of Kolmogorov or algorithmic complexity that measures (roughly) the minimum length of a computer program that can recreate the observed time series . Unfortunately there is no algorithm that can calculate the Kolmogorov complexity of all data sets. Therefore, for applications to statistics, Rissanen  and others have developed a new concept: stochastic complexity of the data with respect to a particular class of models, which measures the shortest total description of the data and the model within the class, but cannot rule out the possibility that a different model class could generate a shorter code.

The main difficulty of all these approaches is that the Kolmogorov complexity is closely related to the Shannon entropy, which means that it measures something closer to our intuitive concept of randomness than to the intuitive concept of complexity . A true random string cannot be compressed and hence requires a long description, yet the physical process that generates this string may be very simple. As physicists, our intuitive notions of complexity correspond to statements about the underlying process, and not directly to the description length or Kolmogorov complexity: a dynamics with a predictable constant output (small algorithmic complexity) is as trivial as one for which the output is completely unpredictable and random (large algorithmic complexity), while really complex processes lie somewhere in between.

The two extreme cases, however, have one feature in common: the entropy of the output strings (or, equivalently, the Kolmogorov complexity of a typical one) either is a fixed constant or grows exactly linearly with the length of the strings. In both cases, corrections to the asymptotic behavior do not grow with the size of the data set. This allowed Grassberger  to identify the slow approach of the entropy to its extensive limit as a sign of complexity. He has proposed several functions to analyze this slow approach and studied systems that exhibited a broad range of complexity properties.

To deal with the same problem, Rissanen has emphasized strongly that fitting a model to data represents an encoding of those data, or predicting future data. Shorter encodings generally mean better prediction or generalization. However, much of the code usually describes the meaningless, nongeneralizable “noise”—statistical fluctuations within the model. Only model description is relevant to prediction, and this part of the code has been termed the model complexity . While systems with model complexity of very different types are known, the two extreme examples above are similar: it only takes a fixed number of bits to code either a call to a random number generator or to a constant function.

The present work may be viewed as expanding on the notions of subextensivity and effective prediction. We construct a coherent theory that brings these ideas together in an intuitive way, but nonetheless is sufficiently general to be applied in many different contexts. We will show that with only a little bit of work Grassberger’s definitions may be made as mathematically precise as they are aesthetically pleasing. Finally, we will argue that the definitions are unique if one accepts a set of simple axioms in the spirit of Shannon’s original work, and that these definitions relate to the usual Kolmogorov complexity in a straightforward way. Much of this paper follows closely a more detailed analysis in Ref. , to which we refer for calculation details and a thorough discussion of the relevant literature.

Our path to connecting the various complexity measures begins by noticing that the subextensive components of entropy identified by Grassberger in fact determine the information available for making predictions. This also suggests a connection to the importance or value of information, especially in a biological or economic context: information is valuable if it can be used to guide our actions, but actions take time and hence observed data can be useful only to the extent that those data inform us about the state of the world at later times. It would be attractive if what we identify as “complex” in a time series were also the “useful” or “meaningful” components.

While prediction may come in various forms, depending on context, information theory allows us to treat all of them on the same footing. For this we only need to recognize that all predictions are probabilistic, and that, even before we look at the data, we know that certain futures are more likely than others. This knowledge can be summarized by a prior probability distribution for the futures. Our observations on the past lead us to a new, more tightly concentrated distribution, the distribution of futures conditional on the past data. Different kinds of predictions are different slices through or averages over this conditional distribution, but information theory quantifies the “concentration” of the distribution without making any commitment as to which averages will be most interesting.

Imagine that we observe a stream of data $`x(t)`$ over a time interval $`T<t<0`$; let all of these past data be denoted by the shorthand $`x_{\mathrm{past}}`$. We are interested in saying something about the future, so we want to know about the data $`x(t)`$ that will be observed in the time interval $`0<t<T^{}`$; let these future data be called $`x_{\mathrm{future}}`$. In the absence of any other knowledge, futures are drawn from the probability distribution $`P(x_{\mathrm{future}})`$, while observations of particular past data $`x_{\mathrm{past}}`$ tell us that futures will be drawn from the conditional distribution $`P(x_{\mathrm{future}}|x_{\mathrm{past}})`$. The greater concentration of the conditional distribution can be quantified by the fact that it has smaller entropy than the prior distribution, and this reduction in entropy is Shannon’s definition of the information that the past provides about the future. We can write the average of this predictive information as

$`_{\mathrm{pred}}(T,T^{})`$ $`=`$ $`\mathrm{log}_2\left[{\displaystyle \frac{P(x_{\mathrm{future}}|x_{\mathrm{past}})}{P(x_{\mathrm{future}})}}\right]`$ (1)
$`=`$ $`\mathrm{log}_2P(x_{\mathrm{future}})\mathrm{log}_2P(x_{\mathrm{past}})`$ (3)
$`\left[\mathrm{log}_2P(x_{\mathrm{future}},x_{\mathrm{past}})\right],`$
where $`\mathrm{}`$ denotes an average over the joint distribution of the past and the future, $`P(x_{\mathrm{future}},x_{\mathrm{past}})`$.

Each of the terms in Eq. (3) is an entropy. Since we are interested in predictability or generalization, which are associated with some features of the signal persisting forever, we may assume stationarity or invariance under time translations. Then the entropy of the past data depends only on the duration of our observations, so we can write $`\mathrm{log}_2P(x_{\mathrm{past}})=S(T)`$, and by the same argument $`\mathrm{log}_2P(x_{\mathrm{future}})=S(T^{})`$. Finally, the entropy of the past and the future taken together is the entropy of observations on a window of duration $`T+T^{}`$, so that $`\mathrm{log}_2P(x_{\mathrm{future}},x_{\mathrm{past}})=S(T+T^{})`$. Putting these equations together, we obtain

$$_{\mathrm{pred}}(T,T^{})=S(T)+S(T^{})S(T+T^{}).$$
(4)
In the same way that the entropy of a gas at fixed density is proportional to the volume, the entropy of a time series (asymptotically) is proportional to its duration, so that $`lim_T\mathrm{}S(T)/T=𝒮_0`$; entropy is an extensive quantity. But from Eq. (4) any extensive component of the entropy cancels in the computation of the predictive information: predictability is a deviation from extensivity. If we write

$$S(T)=𝒮_0T+S_1(T),$$
(5)
then Eq. (4) tells us that the predictive information is related only to the nonextensive term $`S_1(T)`$.

We know two general facts about the behavior of $`S_1(T)`$. First, the corrections to extensive behavior are positive, $`S_1(T)0`$. Second, the statement that entropy is extensive is the statement that the limit $`lim_T\mathrm{}S(T)/T=𝒮_0`$ exists, and for this to be true we must also have $`lim_T\mathrm{}S_1(T)/T=0.`$ Thus the nonextensive terms in the entropy must be subextensive, that is they must grow with $`T`$ less rapidly than a linear function. Taken together, these facts guarantee that the predictive information is positive and subextensive. Further, if we let the future extend forward for a very long time, $`T^{}\mathrm{}`$, then we can measure the information that our sample provides about the entire future,

$$I_{\mathrm{pred}}(T)=\underset{T^{}\mathrm{}}{lim}_{\mathrm{pred}}(T,T^{})=S_1(T),$$
(6)
and this is precisely equal to the subextensive entropy.

If we have been observing a time series for a (long) time $`T`$, then the total amount of data we have collected in is measured by the entropy $`S(T)`$, and at large $`T`$ this is given approximately by $`𝒮_0T`$. But the predictive information that we have gathered cannot grow linearly with time, even if we are making predictions about a future which stretches out to infinity. As a result, of the total information we have taken in by observing $`x_{\mathrm{past}}`$, only a vanishing fraction is of relevance to the prediction:

$$\underset{T\mathrm{}}{lim}\frac{\mathrm{Predictive}\mathrm{Information}}{\mathrm{Total}\mathrm{Information}}=\frac{I_{\mathrm{pred}}(T)}{S(T)}0.$$
(7)
In this precise sense, most of what we observe is irrelevant to the problem of predicting the future. Since the average Kolmogorov complexity of a time series is related to its (total) Shannon entropy, this result means also that most of the algorithm that is required to encode the data encodes aspects of the data that are useless for prediction or for guiding our actions based on the data. This is a strong indication that the usual notions of Kolmogorov complexity in fact do not capture anything at all like the (intuitive) utility of the data stream.

Consider the case where time is measured in discrete steps, so that we have seen $`N`$ time points $`x_1,x_2,\mathrm{},x_N`$. How much is there to learn about the underlying pattern in these data? In the limit of large number of observations, $`N\mathrm{}`$ or $`T\mathrm{}`$ the answer to this question is surprisingly universal: predictive information may either stay finite, or grow to infinity together with $`T`$; in the latter case the rate of growth may be slow (logarithmic) or fast (sublinear power).

The first possibility, $`lim_T\mathrm{}I_{\mathrm{pred}}(T)=`$ constant, means that no matter how long we observe we gain only a finite amount of information about the future. This situation prevails, in both extreme cases mentioned above. For example, when the dynamics are too regular, such as it is for a purely periodic system, complete prediction is possible once we know the phase, and if we sample the data at discrete times this is a finite amount of information; longer period orbits intuitively are more complex and also have larger $`I_{\mathrm{pred}}`$, but this doesn’t change the limiting behavior $`lim_T\mathrm{}I_{\mathrm{pred}}(T)=`$ constant.

Similarly, the predictive information can be small when the dynamics are irregular but the best predictions are controlled only by the immediate past, so that the correlation times of the observable data are finite. This happens, for example, in many physical systems far away from phase transitions. Imagine, for example, that we observe $`x(t)`$ at a series of discrete times $`\{t_\mathrm{n}\}`$, and that at each time point we find the value $`x_\mathrm{n}`$. Then we always can write the joint distribution of the $`N`$ data points as a product,

$`P(x_1,x_2,\mathrm{},x_N)`$ $`=`$ $`P(x_1)P(x_2|x_1)P(x_3|x_2,x_1)\mathrm{}.`$ (8)
For Markov processes, what we observe at $`t_\mathrm{n}`$ depends only on events at the previous time step $`t_{\mathrm{n}1}`$, so that

$`P(x_\mathrm{n}|\{x_{1\mathrm{i}\mathrm{n}1}\})`$ $`=`$ $`P(x_\mathrm{n}|x_{\mathrm{n}1}),`$ (9)
and hence the predictive information reduces to

$`I_{\mathrm{pred}}=\mathrm{log}_2\left[{\displaystyle \frac{P(x_\mathrm{n}|x_{\mathrm{n}1})}{P(x_\mathrm{n})}}\right].`$ (10)
The maximum possible predictive information in this case is the entropy of the distribution of states at one time step, which in turn is bounded by the logarithm of the number of accessible states. To approach this bound the system must maintain memory for a long time, since the predictive information is reduced by the entropy of the transition probabilities. Thus systems with more states and longer memories have larger values of $`I_{\mathrm{pred}}`$.

More interesting are those cases in which $`I_{\mathrm{pred}}(T)`$ diverges at large $`T`$. In physical systems we know that there are critical points where correlation times become infinite, so that optimal predictions will be influenced by events in the arbitrarily distant past. Under these conditions the predictive information can grow without bound as $`T`$ becomes large; for many systems the divergence is logarithmic, $`I_{\mathrm{pred}}(T\mathrm{})\mathrm{log}T`$.

Long range correlation also are important in a time series where we can learn some underlying rules. Suppose a series of random vector variables $`\{\stackrel{}{x}_\mathrm{i}\}`$ are drawn independently from the same probability distribution $`Q(\stackrel{}{x}|𝜶)`$, and this distribution depends on a (potentially infinite dimensional) vector of parameters $`𝜶`$. The parameters are unknown, and before the series starts they are chosen randomly from a distribution $`𝒫(𝜶)`$. In this setting, at least implicitly, our observations of $`\{\stackrel{}{x}_\mathrm{i}\}`$ provide data from which we can learn the parameters $`𝜶`$. Here we put aside (for the moment) the usual problem of learning—which might involve constructing some estimation or regression scheme that determines a “best fit” $`𝜶`$ from the data $`\{\stackrel{}{x}_\mathrm{i}\}`$—and treat the ensemble of data streams $`P[\{\stackrel{}{x}_\mathrm{i}\}]`$ as we would any other set of configurations in statistical mechanics or dynamical systems theory. In particular, we can compute the entropy of the distribution $`P[\{\stackrel{}{x}_\mathrm{i}\}]`$ even if we can’t provide explicit algorithms for solving the learning problem.

As is shown in , the crucial quantity in such analysis is the density of models in the vicinity of the target $`\overline{𝜶}`$—the parameters that actually generated the sequence. For two distributions, a natural distance measure is the Kullback–Leibler divergence $`D(\overline{𝜶}||𝜶)=d\stackrel{}{x}Q(\stackrel{}{x}|\overline{𝜶})\mathrm{log}[Q(\stackrel{}{x}|\overline{𝜶})/Q(\stackrel{}{x}|𝜶)]`$, and the density is

$$\rho (D;\overline{𝜶})=d^K\alpha 𝒫(𝜶)\delta [DD_{\mathrm{KL}}(\overline{𝜶}||𝜶)].$$
(11)
If $`\rho `$ is large as $`D0`$, then one easily can get close to the target for many different data; thus they are not very informative. On the other hand, small density means that only very particular data lead to $`\overline{𝜶}`$, so they carry a lot of predictive information. Therefore, it is clear that the density, but not the number of parameters or any other simplistic measure, characterizes predictability and the complexity of prediction. If, as often is the case for $`dim𝜶<\mathrm{}`$, the density behaves in the way common to finite dimensional systems of the usual statistical mechanics,

$$\rho (D0,\overline{𝜶})AD^{(K2)/2},$$
(12)
then the predictive information to the leading order is

$$I_{\mathrm{pred}}(N)K/2\mathrm{log}N.$$
(13)
The modern theory of learning is concerned in large part with quantifying the complexity of a model class, and in particular with replacing a simple count of parameters with a more rigorous notion of dimensionality for the space of models; for a general review of these ideas see Ref. , and for discussion close in spirit to ours see Ref. . The important point here is that the dimensionality of the model class, and hence the complexity of the class in the sense of learning theory, emerges as the coefficient of the logarithmic divergence in $`I_{\mathrm{pred}}`$. Thus a measure of complexity in learning problems can be derived from a more general dynamical systems or statistical mechanics point of view, treating the data in the learning problem as a time series or one dimensional lattice. The logarithmic complexity class that we identify as being associated with finite dimensional models also arises, for example, at the Feigenbaum accumulation point in the period doubling route to chaos .

As noted by Grassberger in his original discussion, there are time series for which the divergence of $`I_{\mathrm{pred}}`$ is stronger than a logarithm. We can construct an example by looking at the density function $`\rho `$ in our learning problem above: finite dimensional models are associated with algebraic decay of the density as $`D0`$, and we can imagine that there are model classes in which this decay is more rapid, for example

$$\rho (D0)A\mathrm{exp}\left[B/D^\mu \right],\mu >0.$$
(14)
In this case it can be shown that the predictive information diverges very rapidly, as a sublinear power law,

$$I_{\mathrm{pred}}(N)N^{\mu /(\mu +1)}.$$
(15)
One way that this scenario can arise is if the distribution $`Q(\stackrel{}{x})`$ that we are trying to learn does not belong to any finite parameter family, but is itself drawn from a distribution that enforces a degree of smoothness . Understandably, stronger smoothness constraints have smaller powers (less to predict) than the weaker ones (more to predict). For example, a rather simple case of predicting a one dimensional variable that comes from a continuous distribution produces $`I_{\mathrm{pred}}(N)\sqrt{N}`$.

As with the logarithmic class, we expect that power–law divergences in $`I_{\mathrm{pred}}`$ are not restricted to the learning problems that we have studied in detail. The general point is that such behavior will be seen in problems where predictability over long scales, rather then being controlled by a fixed set of ever more precisely known parameters, is governed by a progressively more detailed description—effectively increasing the number of parameters—as we collect more data. This seems a plausible description of what happens in language, where rules of spelling allow us to predict forthcoming letters of long words, grammar binds the words together, and compositional unity of the entire text allows to make predictions about the subject of the last page of the book after reading only the first few. Indeed, Shannon’s classic experiment on the predictability of English text (by human readers!) shows this behavior , and more recently several groups have extracted power–law subextensive components from the numerical analysis of large corpora of text (see, for example, , ).

Interestingly, even without an explicit example, a simple argument ensures existence of exponential densities and, therefore, power law predictive information models. If the number of parameters in a learning problem is not finite then in principle it is impossible to predict anything unless there is some appropriate regularization. If we let the number of parameters stay finite but become large, then there is more to be learned and correspondingly the predictive information grows in proportion to this number. On the other hand, if the number of parameters becomes infinite without regularization, then the predictive information should go to zero since nothing can be learned. We should be able to see this happen in a regularized problem as the regularization weakens: eventually the regularization would be insufficient and the predictive information would vanish. The only way this can happen is if the predictive information grows more and more rapidly with $`N`$ as we weaken the regularization, until finally it becomes extensive (equivalently, drops to zero) at the point where prediction becomes impossible. To realize this scenario we have to go beyond $`I_{\mathrm{pred}}\mathrm{log}T`$ with $`I_{\mathrm{pred}}N^{\mu /(\mu +1)}`$; the transition from increasing predictive information to zero occurs as $`\mu 1`$.

This discussion makes it clear that the predictive information (the subextensive entropy) distinguishes between problems of intuitively different complexity and thus, in accord to Grassberger’s definitions , is probably a good choice for a universal complexity measure. Can this intuition be made more precise?

First we need to decide whether we want to attach measures of complexity to a particular signal $`x(t)`$ or whether we are interested in measures that are defined by an average over the ensemble $`P[x(t)]`$. One problem in assigning complexity to single realizations is that there can be atypical data streams. Second, Grassberger  in particular has argued that our visual intuition about the complexity of spatial patterns is an ensemble concept, even if the ensemble is only implicit. The fact that we admit probabilistic models is crucial: even at a colloquial level, if we allow for probabilistic models then there is a simple description for a sequence of truly random bits, but if we insist on a deterministic model then it may be very complicated to generate precisely the observed string of bits. Furthermore, in the context of probabilistic models it hardly makes sense to ask for a dynamics that generates a particular data stream; we must ask for dynamics that generate the data with reasonable probability, which is more or less equivalent to asking that the given string be a typical member of the ensemble generated by the model. All of these paths lead us to thinking not about single strings but about ensembles in the tradition of statistical mechanics, and so we shall search for measures of complexity that are averages over the distribution $`P[x(t)]`$.

Once we focus on average quantities, we can provide an axiomatic proof (much in the spirit of Shannon’s  arguments establishing entropy as a unique information measure) that links $`I_{\mathrm{pred}}`$ to complexity. We can start by adopting Shannon’s postulates as constraints on a measure of complexity: if there are $`N`$ equally likely signals, then the measure should be monotonic in $`N`$; if the signal is decomposable into statistically independent parts then the measure should be additive with respect to this decomposition; and if the signal can be described as a leaf on a tree of statistically independent decisions then the measure should be a weighted sum of the measures at each branching point. We believe that these constraints are as plausible for complexity measures as for information measures, and it is well known from Shannon’s original work that this set of constraints leaves the entropy as the only possibility. Since we are discussing a time dependent signal, this entropy depends on the duration of our sample, $`S(T)`$. We know of course that this cannot be the end of the discussion, because we need to distinguish between randomness (entropy) and complexity. The path to this distinction is to introduce other constraints on our measure.

First we notice that if the signal $`x`$ is continuous, then the entropy is not invariant under transformations of $`x`$ that do not mix point at different times (reparameterizations). It seems reasonable to ask that complexity be a function of the process we are observing and not of the coordinate system in which we choose to record our observations. However, that it is not the whole function $`S(T)`$ which depends on the coordinate system for $`x`$; it is only the extensive component of the entropy that has this noninvariance. This can be seen more generally by noting that subextensive terms in the entropy contribute to the mutual information among different segments of the data stream (including the predictive information defined here), while the extensive entropy cannot; mutual information is coordinate invariant, so all of the noninvariance must reside in the extensive term. Thus, any measure complexity that is coordinate invariant must discard the extensive component of the entropy.

If we continue along these lines, we can think about the asymptotic expansion of the entropy at large $`T`$. The extensive term is the first term in this series, and we have seen that it must be discarded. What about the other terms? In the context of predicting in a parameterized model, most of the terms in this series depend in detail on our prior distribution in parameter space, which might seem odd for a measure of complexity. More generally, if we consider transformations of the data stream $`x(t)`$ that mix points within a temporal window of size $`\tau `$, then for $`T>>\tau `$ the entropy $`S(T)`$ may have subextensive terms which are constant, and these are not invariant under this class of transformations. On the other hand, if there are divergent subextensive terms, these are invariant under such temporally local transformations . So if we insist that measures of complexity be invariant not only under instantaneous coordinate transformations, but also under temporally local transformations, then we can discard both the extensive and the finite subextensive terms in the entropy, leaving only the divergent subextensive terms as a possible measure of complexity.

To illustrate the purpose of these two extra conditions, we may think of the following example: measuring velocity of a turbulent fluid flow at a given point. The condition of invariance under reparameterizations means that the complexity is independent of the scale used by the speedometer. On the other hand, the second condition ensures that the temporal mixing due to the finiteness of the inertia of the speedometer’s needle does not change the estimated complexity of the flow.

In our view, these arguments (or their slight variation also presented in ) settle the question of the unique definition of complexity. Not only is the divergent subextensive component of the entropy the unique complexity measure, but it is also a universal one since it is connected in a straightforward way to many other measures that have arisen in statistics and in dynamical systems theory. A bit less straightforward is the connection to the Kolmogorov’s definition that started the whole discussion, but even this can also be made.

To make this connection we follow the suggestion of Standish  that one should focus not on the complexity of particular strings but of equivalence classes. In the present case it is natural to define an equivalence class of data $`x(T<t0)`$ as those data that generate indistinguishable conditional probability distributions for the future, $`P[x(t>0)|x(T<t0)]`$. If this conditional distribution has sufficient statistics, then there exists a compression of the past data $`x(T<t0)`$ into exactly $`I_{\mathrm{pred}}(T)`$ bits while preserving all of the mutual information with the future. But this means that the ensemble of data in an equivalence class can be described, on average, using exactly this many bits. Thus, for dynamics such that the prediction problem has sufficient statistics, the average Kolmogorov complexity of equivalence classes defined by the indistinguishability of predictions is equal to the predictive information. By the arguments above, prediction is the useful thing which we can do with a data stream, and so in this case it makes sense to say that the Kolmogorov complexity of representing the useful bits of data is equal to the predictive information. Note also that Kolmogorov complexity is defined only up to a constant depending on the computer used . A computer independent definition requires ignoring constant terms and focusing only on asymptotic behavior. This agrees very well with our arguments above that identified only the divergent part of the predictive information with the complexity of a data stream.

In the terminology suggested by Grassberger, the statement that the prediction problem has sufficient statistics means that the True Measure Complexity is equal to the Effective Measure Complexity ; similarly, the statistical complexity defined by Crutchfield and coworkers  then also is equal to predictive information defined here. These are strong statements, and it is likely that they are not true precisely for most natural data streams. More generally one can ask for compressions that preserve the maximum fraction of the relevant (in this case, predictive) information, and our intuitive notion of data being “understandable” or “summarizable” is that these selective compressions can be very efficient —here efficiency means that we can compress the past into a description with length not much larger than $`I_{\mathrm{pred}}(T)`$ while preserving a finite fraction of the (diverging) information about the future; an example is when we summarize data by the parameters of the model that describes the underlying stochastic process. The opposite situation is illustrated by certain cryptographic codes, where the relevant information is accessible (at best) only from the entire data set. Thus we can classify data streams by their predictive information, but additionally by whether this predictive information can be represented efficiently. For those data where efficient representation is possible, the predictive information and the mean Kolmogorov complexity of future–equivalent classes will be similar; with more care we can guarantee that these quantities are proportional as $`T\mathrm{}`$. Perhaps Wigner’s famous remarks about the unreasonable effectiveness of mathematics in the natural sciences could be rephrased as the conjecture that the data streams occurring in nature—although often complex as measured by their predictive information—nonetheless belong to this efficiently representable class.