text:
# Rational parametrization of strata in orbit spaces of compact linear groups

## 1 Introduction

The determination of properties of functions which are covariant or invariant under the transformations of a compact linear group (hereafter abbreviated in CLG) $`G`$ is often a basic problem to solve in many physical contexts. $`G`$-invariant functions play an important role, for instance, in the determination of patterns of spontaneous symmetry breaking and structural phase transitions (Landau’s theory), in covariant bifurcation theory, in crystal field theory and in most areas of solid state theory where use is made of symmetry adapted functions.

It will not be essentially restrictive, in the following, to assume that $`G`$ is a matrix subgroup of $`O_n(1\mathrm{R})`$; it will be thought to act in $`1\mathrm{R}^n`$, thus defining the $`G`$-space $`(G,1\mathrm{R}^n)`$. Complex linear groups can always be transformed into real linear groups through a process of realification and compact real linear groups are equivalent to orthogonal linear groups.

A possible approach to the study of invariant functions, that fully exploits invariance and regularity properties , is based on the fact that a $`G`$-invariant function $`f(x)`$, $`x1\mathrm{R}^n`$, is a constant along each $`G`$-orbit and can, therefore, be considered as a function $`\widehat{f}`$ in the orbit space of $`(1\mathrm{R}^n/G)`$ 111The orbit space $`1\mathrm{R}^n/G`$ is defined as the quotient space obtained through the equivalence relation between points belonging to the same orbit), endowed with the quotient topology and differentiable structure..

Geometric invariant theory  suggests how to get, in principle, $`\widehat{f}`$ and $`1\mathrm{R}^n/G`$. In fact, theorems by Hilbert, Schwarz and Nagata  assure that a polynomial or $`C^{\mathrm{}}`$, $`G`$-invariant function $`f(x)`$, $`x1\mathrm{R}^n`$, can be expressed as a polynomial or, respectively, $`C^{\mathrm{}}`$ function $`\widehat{f}(p)`$ of a finite minimal set $`p(x)=(p_1(x),\mathrm{},p_n(x))`$ of polynomial $`G`$-invariant functions (minimal integrity basis of the ring of $`G`$-invariant polynomial functions (hereafter abbreviated in MIB)). The elements of a MIB separate the orbits of $`G`$.

Depending on $`G`$, there may be relations among the elements of a MIB (non-coregular $`G`$):

$$\widehat{F}_A(p(x))=\mathrm{\hspace{0.17em}0},x1\mathrm{R}^n\mathrm{and}A=1,\mathrm{},.$$
(1)
The associated equations

$$\widehat{F}_A(p)=\mathrm{\hspace{0.17em}0},A=1,\mathrm{},,$$
(2)
define an algebraic variety in $`1\mathrm{R}^q`$, that is called the variety $`𝒵`$ of the relations (among the elements of the MIB).

The range $`p(1\mathrm{R}^n)`$ of the orbit map $`p`$ provides a diffeomorphic image of $`1\mathrm{R}^n/G`$ in $`𝒵1\mathrm{R}^q`$. The set $`p(1\mathrm{R}^n)`$ is a connected semi-algebraic subset (i.e., a subset defined by algebraic equalities and inequalities) of $`1\mathrm{R}^q`$, formed by the union of semialgebraic (connected) manifolds of different dimensions, called primary strata. The $`G`$-orbits with the same isotropy type form semialgebraic sets (isotropy type strata), whose connected components are primary strata. Almost all the points of $`1\mathrm{R}^n/G`$ belong to a unique stratum, the principal stratum, which is a connected open dense subset of $`1\mathrm{R}^n/G`$. The boundary of the principal stratum is the union of disjoint singular isotropy type strata. All the strata lying on the boundary of an isotropy type stratum are open in its topological closure. The following partial ordering can be introduced in the set of all the orbit types: $`[H]<[K]`$, if $`H`$ is conjugated with a proper subgroup of $`K`$. The orbit type of an isotropy type stratum is contained in the orbit types of all the strata lying in its boundary; therefore, more peripheral strata are formed by orbits with higher symmetry under $`G`$ transformations. The number of distinct orbit types of $`G`$ is finite and there is a unique minimum orbit type, the principal orbit type, pertaining to the principal stratum; there is also a unique maximum orbit type $`[G]`$, corresponding to the image through $`\pi `$ of all the points of $`1\mathrm{R}^n`$, which are invariant under $`G`$.

The principal stratum is connected, open and dense in $`1\mathrm{R}^n/G`$. The orbit type $`[H]`$ of a stratum222$`[H]`$ is the class of subgroups of $`G`$ conjugate with $`H`$ and, by definition, is the class of isotropy subgroups of $`G`$ at points of the stratum. is contained in the orbit types of all the strata lying in its boundary; therefore, more peripheral strata of $`1\mathrm{R}^n/G`$ are formed by orbits with higher symmetry under $`G`$, the principal orbit type is minimum and the maximum orbit type is $`[G]`$, corresponding to the image through the canonical projection, $`\pi :1\mathrm{R}^n1\mathrm{R}^n/G`$, of the set of points of $`1\mathrm{R}^n`$, which are invariant under $`G`$. This set contains at least the origin of $`1\mathrm{R}^n`$.

The following theorem offers a simple recipe to derive the algebraic equations and inequalities defining the range of an orbit map and its strata  (see also ).

Let $`\widehat{P}(p)`$, $`p1\mathrm{R}^q`$ denote the $`q\times q`$ real symmetric matrix defined through the relations

$$\widehat{P}_{ab}(p(x))=\underset{j=1}{\overset{n}{}}_jp_a(x)_jp_b(x),x𝐑^n.$$
(3)
Then, $`p(1\mathrm{R}^n)=\{p𝒵\widehat{P}(p)0\}`$ and the $`k`$-dimensional primary strata are the connected components of the semialgebraic set $`\{p𝒵\widehat{P}(p)0,\mathrm{rank}(\widehat{P}(p))=k\}`$.

If $`G`$ is coregular, the $`p_i`$’s, with range in the semialgebraic set $`\mathrm{\Delta }`$ defined by the inequalities $`\widehat{P}(p)>0`$ (and no equation!) provide a one-to-one parametrization of the principal stratum of $`1\mathrm{R}^n/G`$. If the stratum is singular, the $`p_i`$’s are not independent parameters, being bounded also by the equations defining the stratum. In applications or, simply, to get a better understanding of the geometry of the stratum (its connectivity properties, its boundary, etc..), one often needs to solve explicitly these equations, which are obtained in implicit form from the proposition recalled above. Often, this cannot be done using standard algorithms.

In this paper we propose a general method to derive the equations defining the singular strata of the orbit space of any CLG in the form of explicit rational parametric relations. In the next Section we shall present and prove our results and in Section 3, we shall illustrate them, by working out an example.

## 2 Parametrization of strata in orbit spaces of compact linear groups

In this section, we shall prove that the possibility of parametrizing the principal stratum of the orbit space of a coregular group in terms of parameters related to the elements of a MIB can be extended to singular strata. The result stems from the proof of the following statement: The set of internal points of the topological closure of an isotropy type stratum, with orbit type $`[H]`$, is diffeomorphic to the principal stratum of the orbit space of a group space of the stabilizer of $`H`$ (in $`G`$). If the stabilizer turns out to be coregular, the constructive proof of this proposition will provide a one-to-one rational parametrization of the stratum.

Since, in view of possible applications, we are mainly interested in the possibility of getting a one-to-one parametrization of a stratum, in the presentation of our results, stress will be laid on this aspect of the matter.

Let $`G`$ and $`\{p\}`$ be defined as in the previous section (no coregularity assumption will be done on $`G`$) and $`H`$ be a proper isotropy subgroup of the $`G`$-space $`(G,1\mathrm{R}^n)`$. We shall denote by $`S`$ the stratum of $`(G,1\mathrm{R}^n)`$ with orbit type $`[H]`$ and by $`\widehat{S}`$ its image in the orbit space $`1\mathrm{R}^n/G`$. In the following, we shall identify $`1\mathrm{R}^n/G`$ and its strata $`\widehat{S}`$ with their images $`p(1\mathrm{R}^n)`$ and $`p(\widehat{S})`$. Let us, also, define

$$\begin{array}{ccc}\hfill V& =& \{x1\mathrm{R}^nG_xH\},\hfill \\ & & \\ \hfill 𝒱& =& \{x1\mathrm{R}^nG_x=H\}.\hfill \end{array}$$
(4)
The non trivial sets $`V`$ and $`𝒱`$ have the following properties, which are more or less immediate consequences of their definitions:

1. $`V=\{x1\mathrm{R}^nhx=x,hH\}`$ is a linear subspace of $`1\mathrm{R}^n`$, let us call $`\nu `$ its dimensions;
2. $`V`$ is the topological closure of $`𝒱`$: $`V=\overline{𝒱}`$;
3. $`𝒱=SV`$, so that every $`G`$-orbit lying in $`S`$ has at least a point in $`𝒱`$ and $`S=G𝒱`$, $`\overline{S}=GV`$, where the bar denotes topological closure, so that

$$p(𝒱)=\widehat{S},p(V)=\overline{\widehat{S}}$$
(5)
and

$$\mathrm{rank}(P(x)|_{x𝒱})=\mathrm{dim}(\widehat{S}),\mathrm{rank}(P(x)|_{xV\backslash 𝒱})<\mathrm{dim}(\widehat{S}).$$
(6)

A $`G`$-orbit of $`S`$ may intersect $`𝒱`$ in one or more points. In the first case, every $`G`$-orbit of $`S`$ intersects $`𝒱`$ in a point and, owing to item 3, the coordinates of the points of $`𝒱`$ provide a one-to-one rational (in effect, linear) parametrization of the orbits of G lying in $`S`$, obtained by solving the system of linear equations $`hx=xhH`$. The allowed range of $`x`$, $`x𝒱`$, is determined by the inequalities assuring that rank$`(P(x))=`$ dim$`(\widehat{S})`$. The parameters $`x`$, with range $`𝒱`$, would provide, in this case, the one-to-one parametrization of the stratum, thus solving our problem.

In general, however, the intersection of a $`G`$-orbit, of orbit type $`[H]`$, with the stratum $`S`$ does not reduce to a single point. So, a sounder analisys is required, that will be the object of the rest of this section.

Two distinct points, $`x`$ and $`gx`$, $`gG`$, of the same $`G`$-orbit, lay in $`𝒱`$ iff $`hgx=gxhH`$. This is equivalent to the condition that $`g`$ is an element of the stabilizer Stab$`(H,G)`$ of $`H`$ in $`G`$:

$$\mathrm{Stab}(H,G)=\{gGgHg^1=H\}.$$
(7)
The intersection of a $`G`$-orbit of $`S`$ with $`𝒱`$ is, therefore, the Stab($`H`$, $`G`$)-orbit through $`x`$.

This result can be refined. In fact, it is easy to realize that the relation $`hgx=gx`$ is satisfied for all $`xV`$ and all $`hH`$, iff $`g`$ Stab($`H`$, $`G`$). Therefore, Stab($`H`$, $`G`$) is the largest subgroup of $`G`$ under which $`V`$ is stable; a known result.

In the group space (Stab($`H`$, $`G`$),V), the isotropy subgroup at a point of general position is $`H`$ (or, more precisely, the linear group obtained by restriction to $`V`$ of the action of $`H`$). Therefore, the principal isotropy type is $`[H]=\{H\}`$ and the principal stratum $`\mathrm{\Sigma }`$ satisfies the following relation:

$$V\mathrm{\Sigma }𝒱.$$
(8)
It has to be noted that, the principal stratum $`\mathrm{\Sigma }`$ could contain $`𝒱`$ in a strict sense, since, at points of $`V\backslash 𝒱`$, the conjugacy class of the isotropy subgroup of Stab$`(H,G)`$ could be smaller than the conjugacy class of the isotropy subgroup of $`G`$.

$`H`$ is an invariant subgroup of Stab$`(H,G)`$ and it is a subgroup of all the isotropy subgroups of (Stab$`(H,G),V)`$. Thus, the restriction of the action of Stab$`(H,G)`$ to $`V`$ defines a linear group $`K`$ (and the group space $`(K,V)`$), isomorphic to the quotient group Stab($`H`$, $`G`$)/$`H`$, through the relation

$$(sH)v=sv,s\mathrm{Stab}(H,G),sH\mathrm{Stab}(H,G)/H.$$
(9)
So, we can conclude that the intersection of a $`G`$-orbit of $`S`$ with $`𝒱`$ is an orbit of $`(K,V)`$. Obviously, the orbit spaces $`V/K`$ and $`V/\mathrm{Stab}(H,G)`$ are isomorphic and can be identified.

We can rephrase the result just obtained, by claiming that the points of $`\widehat{S}`$ are in a one-to-one correspondence with the points of a, possibly proper, subset $`\widehat{𝒱}`$ of the principal stratum $`\widehat{\mathrm{\Sigma }}`$ of the orbit space $`V/K`$ and the following relations hold true:

$$\overline{\widehat{S}}=p(V)p(\mathrm{\Sigma })p(𝒱)=\widehat{S}.$$
(10)
Since, as stressed, we know how to parametrize a principal stratum, our problem is reduced to the determination of $`\widehat{𝒱}`$. We shall show that this can be easily done, making use of (6).

To make simpler the solution of the problem, let us assume that an orthonormal basis has been introduced in $`1\mathrm{R}^n`$ such that the first $`\nu `$ elements of the basis yield a basis for the vector space $`V`$. Then, if we denote by $`V_{}`$ the orthogonal complement of $`V`$ in $`1\mathrm{R}^n`$, the subspace $`V_{}`$ is stable under ($`K`$ and) $`H`$, owing to the orthogonality of the transformations of $`G`$. Since $`V`$ contains all the $`H`$-invariant vectors of $`1\mathrm{R}^n`$, there is no non trivial $`H`$-invariant vector in $`V_{}`$.

To attain our goal, we shall start from a convenient parametrization of the principal statum $`\widehat{\mathrm{\Sigma }}`$ of $`V/K`$ in terms of $`l`$ real parameters $`\lambda `$, related to a MIB $`(\lambda _1(v),\mathrm{},\lambda _l(v))`$ of the ring of polynomial $`K`$-invariant functions. This parametrization will be global and one-to-one, if $`K`$ turns out to be coregular. In this case, the range of $`\lambda `$ has to be restricted to the positivity region of the $`\widehat{P}`$-matrix $`\widehat{\mathrm{\Lambda }}(\lambda )`$, associated to the MIB $`\{\lambda \}`$:

$$\widehat{\mathrm{\Lambda }}_{\alpha \beta }(\lambda (v))=\mathrm{\Lambda }_{\alpha \beta }(v)=\underset{i=1}{\overset{\nu }{}}_i\lambda _\alpha (x_1,\mathrm{},x_\nu )_i\lambda _\beta (x_1,\mathrm{},x_\nu ).$$
(11)
As recalled in the previous Section, in fact, the orbit space $`V/K`$ and its principal stratum $`\widehat{\mathrm{\Sigma }}`$ can be identified, respectively, by the semialgebraic sets $`\lambda (V)`$ and $`\lambda (\mathrm{\Sigma })`$:

$$\widehat{\mathrm{\Sigma }}=\lambda (\mathrm{\Sigma })=\{\lambda 1\mathrm{R}^l\widehat{\mathrm{\Lambda }}(\lambda )>0\},\overline{\widehat{\mathrm{\Sigma }}}=\lambda (V)=\{\lambda 1\mathrm{R}^l\widehat{\mathrm{\Lambda }}(\lambda )0\},$$
(12)
the second set being the closure of the first one. Moreover, the definition of $`\widehat{𝒱}`$ and equation (8) imply

$$\widehat{𝒱}=\lambda (𝒱)\lambda (\mathrm{\Sigma })=\widehat{\mathrm{\Sigma }}.$$
(13)
If $`K`$ is not coregular, only a local one-to-one parametrizations can be obtained for $`\widehat{\mathrm{\Sigma }}`$, by eliminating redundant elements in the set of parameters $`(\lambda _1,\mathrm{},\lambda _l)`$, through the solution of the algebraic relation(s) among the elements of the MIB $`\{\lambda \}`$, and imposing convenient semi-positivity and rank conditions on the matrix $`\widehat{\mathrm{\Lambda }}(\lambda )`$.

A one-to-one local or global parametrization of $`\widehat{\mathrm{\Sigma }}`$ yields, obviously, also a local or global one-to-one parametrization of $`\widehat{𝒱}`$, provided that additional restrictions are imposed on the range of $`\lambda `$, whenever $`\widehat{𝒱}`$ is a proper subset of $`\widehat{\mathrm{\Sigma }}`$. The correct bounds can be obtained in the following way.

We shall only consider the case of a coregular $`K`$, the extension of the results to non coregular $`K`$’s will be straightforward, but, as just stressed, may lead to a loss of globality.

When $`x`$ spans $`V`$, the elements of the MIB $`(p_1(x),\mathrm{},p_q(x))`$ of $`G`$ define a set of $`K`$-invariant polynomial functions of $`v=(x_1,\mathrm{},x_\nu )V`$. Therefore, by the Hilbert theorem recalled in the previous Section, they can be expressed as polynomial functions of $`\lambda `$, that is,

$$p|_V=\varphi \lambda .$$
(14)
Let us remark that, in our assumptions, there are no relations among the elements of the MIB $`\{\lambda \}`$ and, consequently, possible relations $`F_\alpha (p)=0`$ among the $`p_i`$’s are identically satisfied for $`p=\varphi (\lambda )`$.

¿From (14) and (8), one immediately obtains

$$\overline{\widehat{S}}=p(V)=\varphi (V/K)\varphi (\widehat{\mathrm{\Sigma }})\varphi (\widehat{𝒱})=p(𝒱)=\widehat{S}.$$
(15)
and, since $`\widehat{\mathrm{\Sigma }}`$ is the set of internal points of $`V/K`$, $`\varphi (\widehat{\mathrm{\Sigma }})`$ will coincide with the set of internal points of the closure $`\overline{\widehat{S}}`$ of $`\widehat{S}`$. This set does not coincide with $`\widehat{S}`$ if $`\overline{\widehat{S}}`$ contains, in its interior, points representing bordering strata of $`\widehat{S}`$. This happens if the set $`\widehat{S}`$ is not connected or not multiply connected.

The identification of points $`\lambda \widehat{\mathrm{\Sigma }}`$, whose image $`\varphi (\lambda )\widehat{S}`$ can be obtained in the following way, using (6).

Let $`x=vv_{}`$ yield the decomposition of $`x1\mathrm{R}^n`$ in its vector components $`vV`$ and $`v_{}V_{}`$: $`v=(x_1,\mathrm{},x_\nu )`$, $`v_{}=(x_{\nu +1},\mathrm{},x_n)`$. Then, a $`G`$-invariant polynomial $`f(x)`$, can be thought of as a polynomial in $`v`$ and $`v_{}`$ and it is easy to realize that it cannot contain linear terms in $`v_{}`$, being $`v`$ invariant under $`H`$. As a consequence,

$$_if(x)=0,\mathrm{for}xV\mathrm{and}i=\nu +1,\mathrm{},n.$$
(16)
Now, starting from the very definition of $`P(x)`$ (see (3)), for every $`x=vV`$ we obtain, using (16) and the identity $`p(v)=\varphi (\lambda (v))`$,

$$\begin{array}{ccc}\hfill \widehat{P}_{ab}(p(v))& =& _{i=1}^\nu _ip_a(v)_ip_b(v)\hfill \\ & & \\ & =& _{\alpha ,\beta =1}^l_\alpha \varphi _a(\lambda )_\beta \varphi _b(\lambda )|_{\lambda =\lambda (v)}_{i=1}^\nu _i\lambda _\alpha (v)_i\lambda _\beta (v)\hfill \\ & & \\ & =& \left(J(\lambda )^T\widehat{\mathrm{\Lambda }}(\lambda )J(\lambda )|_{\lambda =\lambda (v)}\right)_{ab},\hfill \end{array}$$
(17)
where, the apex $`T`$ denotes transposition and $`J(\lambda )`$ is the Jacobian matrix of the transformation $`p=\varphi (\lambda )`$:

$$J_{\alpha a}(\lambda )=_a\varphi _\alpha (\lambda ),a=1,\mathrm{},q,\alpha =1,\mathrm{},l.$$
(18)
So, we can conclude that, for all $`\lambda V/K`$,

$$\widehat{P}(\varphi (\lambda ))=J(\lambda )^\mathrm{T}\widehat{\mathrm{\Lambda }}(\lambda )J(\lambda ).$$
(19)
Equation (19) leads to an easy identification of the points $`\lambda \widehat{𝒱}`$, that is, of the points $`\lambda \widehat{\mathrm{\Sigma }}`$ whose image $`p=\varphi (\lambda )`$ is in $`\widehat{S}`$. In fact, from (6), these points are characterized by the conditions $`\lambda \widehat{\mathrm{\Sigma }}`$ and rank($`\widehat{P}(\varphi (\lambda )))=l`$. Since, for $`\lambda \widehat{\mathrm{\Sigma }}`$, the matrix $`\widehat{\mathrm{\Lambda }}(\lambda )`$ is positive definite with rank $`l`$, we can conclude that the range of $`\lambda `$ assuring the location of the point $`p=\varphi (\lambda )`$ in $`\widehat{S}`$ is the semialgebraic subset $`\mathrm{\Delta }`$ of $`1\mathrm{R}^l`$, determined by the following inequalities:

$$\mathrm{\Delta }=\{\lambda 1\mathrm{R}^l\mathrm{\Lambda }(\lambda )>0\mathrm{and}\mathrm{rank}(J(\lambda ))=l\}.$$
(20)
For $`\lambda \mathrm{\Delta }`$, the relation $`p=\varphi (\lambda )`$ yields a global rational parametrization for $`\widehat{S}`$.

It will be worthwhile to stress that the parametrization we have suggested is, in some way, canonical: The unique arbitrariness in the choice of the parameters is related to the choice of the MIB’s.

An important byproduct of the result just proved is a simple test of the connection of $`\widehat{S}`$, that could be difficult or impossible to read directly from the equations of the stratum in implicit form. In fact, the condition

$$\mathrm{boundary}\mathrm{of}\overline{\widehat{S}}=\mathrm{boundary}\mathrm{of}\widehat{S}$$

is equivalent to rank($`J(\lambda ))=l`$ for all $`\lambda \widehat{\mathrm{\Sigma }}`$.

If $`K`$ is not coregular, there are polynomial relations $`F_A(\lambda )=0`$ among the elements of the MIB $`(\lambda _1,\mathrm{},\lambda _l)`$ and $`l>`$dim$`(\widehat{S})`$. As already stressed, to obtain a one-to-one parametrization of the points of $`\widehat{S}`$ by means of the $`\lambda _\alpha `$’s, one has to eliminate the redundant parameters by solving the equations $`F_A(\lambda )=0`$. This may be feasible, but only locally and the resulting parametrization will not be global and possibly not rational.

## 3 An Example

In this Section we shall show how the parametrization technique works in a simple example. The notations will be the same defined in the previous sections.

We shall consider the orthogonal linear group $`G`$ defined by the action of the real group $`O(3)`$ in the real eighth-dimensional space spanned by the independent components $`x_1,\mathrm{},x_5`$ of a symmetric and traceless tensor $`Q`$ and the three components $`x_6,x_7,x_8`$ of a polar vector $`\stackrel{}{P}`$. To be specific, if $`O`$ is a generic $`3\times 3`$ real orthogonal matrix, the transformation rules of the $`x_i`$ are obtained from the following relations:

$$Q=\frac{1}{\sqrt{2}}\left(\begin{array}{ccc}\frac{2}{\sqrt{3}}x_1& x_3& x_4\\ x_3& \frac{x_1}{\sqrt{3}}x_2& x_5\\ x_4& x_5& \frac{x_1}{\sqrt{3}}+x_2\end{array}\right)$$
(21)
$$\begin{array}{cccc}\hfill Q_{\alpha \beta }^{}& =& _{\gamma \delta =1}^3O_{\alpha \gamma }Q_{\gamma \delta }O_{\beta \delta }\hfill & \\ & & & \alpha ,\beta =1,2,3.\hfill \\ \hfill P_\alpha ^{}& =& _{\beta =1}^3O_{\alpha \beta }P_\beta ,\hfill & \end{array}$$
(22)
It will be worthwhile to remark that the reflection $`I=\text{diag}(1,1,1)`$ O(3) reverses only the signs of the last three coordinates $`(x_6,x_7,x_8)`$ and, due to the symmetry of the tensor $`Q`$, each $`G`$-orbit contains points where the tensor $`Q`$ takes on a diagonal form ($`x_3=x_4=x_5=0)`$. This remark makes much easier the determination of “typical points” in strata, from which the orbit type of the stratum can be identified.

The real orthogonal linear group $`G`$, just defined, is coregular (see ) and its isotropy subgroup at a generic point of $`1\mathrm{R}^8`$ is trivial. As a consequence, the principal orbits are 3-dimensional manifolds, the principal stratum has dimensions 5 and there will be five independent elements in a MIB (see, for instance ), which can be chosen in the following way:

$`p_1`$ $`=`$ $`\text{Tr}Q^2+\stackrel{}{P}\stackrel{}{P}`$
$`=`$ $`{\displaystyle \underset{j=1}{\overset{8}{}}}x_{j}^{}{}_{}{}^{2},`$
$`p_2`$ $`=`$ $`\stackrel{}{P}\stackrel{}{P}`$
$`=`$ $`{\displaystyle \underset{j=6}{\overset{8}{}}}x_{j}^{}{}_{}{}^{2},`$
$`p_3`$ $`=`$ $`6\sqrt{2}\text{Tr}Q^3`$
$`=`$ $`2\sqrt{3}x_{1}^{}{}_{}{}^{3}+6\sqrt{3}x_1x_{2}^{}{}_{}{}^{2}3\sqrt{3}x_1x_{3}^{}{}_{}{}^{2}9x_2x_{3}^{}{}_{}{}^{2}`$
$`3\sqrt{3}x_1x_{4}^{}{}_{}{}^{2}+9x_2x_{4}^{}{}_{}{}^{2}+18x_3x_4x_5+6\sqrt{3}x_1x_{5}^{}{}_{}{}^{2},`$
$`p_4`$ $`=`$ $`3\sqrt{2}{\displaystyle \underset{\alpha \beta }{}}P_\alpha Q_{\alpha \beta }P_\beta `$
$`=`$ $`2\sqrt{3}x_1x_{6}^{}{}_{}{}^{2}+6x_3x_6x_7+\sqrt{3}x_1x_{7}^{}{}_{}{}^{2}3x_2x_{7}^{}{}_{}{}^{2}`$
$`+6x_4x_6x_8+6x_5x_7x_8+\sqrt{3}x_1x_{8}^{}{}_{}{}^{2}+3x_2x_{8}^{}{}_{}{}^{2},`$
$`p_5`$ $`=`$ $`6{\displaystyle \underset{\alpha \beta }{}}P_\alpha Q_{}^{2}{}_{\alpha \beta }{}^{}P_\beta `$
$`=`$ $`4x_{1}^{}{}_{}{}^{2}x_{6}^{}{}_{}{}^{2}+3x_{3}^{}{}_{}{}^{2}x_{6}^{}{}_{}{}^{2}+3x_{4}^{}{}_{}{}^{2}x_{6}^{}{}_{}{}^{2}2\sqrt{3}x_1x_3x_6x_7`$
$`6x_2x_3x_6x_7+6x_4x_5x_6x_7+x_{1}^{}{}_{}{}^{2}x_{7}^{}{}_{}{}^{2}2\sqrt{3}x_1x_2x_{7}^{}{}_{}{}^{2}`$
$`+3x_{2}^{}{}_{}{}^{2}x_{7}^{}{}_{}{}^{2}+3x_{3}^{}{}_{}{}^{2}x_{7}^{}{}_{}{}^{2}+3x_{5}^{}{}_{}{}^{2}x_{7}^{}{}_{}{}^{2}2\sqrt{3}x_1x_4x_6x_8`$
$`+6x_2x_4x_6x_8+6x_3x_5x_6x_8+6x_3x_4x_7x_8+4\sqrt{3}x_1x_5x_7x_8`$
$`+x_{1}^{}{}_{}{}^{2}x_{8}^{}{}_{}{}^{2}+2\sqrt{3}x_1x_2x_{8}^{}{}_{}{}^{2}+3x_{2}^{}{}_{}{}^{2}x_{8}^{}{}_{}{}^{2}+3x_{4}^{}{}_{}{}^{2}x_{8}^{}{}_{}{}^{2}+3x_{5}^{}{}_{}{}^{2}x_{8}^{}{}_{}{}^{2}.`$
The corresponding $`\widehat{P}`$-matrix elements can be easily calculated from their very definition (3)

$$\begin{array}{ccc}\hfill \widehat{P}_{1a}& =& 2d_ap_a,1a5\hfill \\ \hfill \widehat{P}_{\mathrm{2\hspace{0.17em}2}}& =& 4p_2\hfill \\ \hfill \widehat{P}_{\mathrm{2\hspace{0.17em}3}}& =& 0\hfill \\ \hfill \widehat{P}_{\mathrm{2\hspace{0.17em}4}}& =& 4p_4\hfill \\ \hfill \widehat{P}_{\mathrm{2\hspace{0.17em}5}}& =& 4p_5\hfill \\ \hfill \widehat{P}_{\mathrm{3\hspace{0.17em}3}}& =& 108\left(p_1p_2\right)^2\hfill \\ \hfill \widehat{P}_{\mathrm{3\hspace{0.17em}4}}& =& 18\left(2p_1p_2+2p_{2}^{}{}_{}{}^{2}+p_5\right)\hfill \\ \hfill \widehat{P}_{\mathrm{3\hspace{0.17em}5}}& =& 12\left(p_2p_3+p_1p_4p_2p_4\right)\hfill \\ \hfill \widehat{P}_{\mathrm{4\hspace{0.17em}4}}& =& 12\left(p_{2}^{}{}_{}{}^{2}+p_5\right)\hfill \\ \hfill \widehat{P}_{\mathrm{4\hspace{0.17em}5}}& =& 4\left(p_2p_3+3p_1p_4p_2p_4\right)\hfill \\ \hfill \widehat{P}_{\mathrm{5\hspace{0.17em}5}}& =& \frac{4}{3}\left(p_3p_4+p_{4}^{}{}_{}{}^{2}+9p_1p_5\right),\hfill \end{array}$$
(24)
where the set $`\{d_1,d_2,d_3,d_4,d_5\}=\{2,2,3,3,4\}`$ specifies the degrees of the polynomials of the MIB.

The determinant of the matrix $`\widehat{P}(p)`$ factorizes and only one of the two real irreducible factors, that we shall call $`A(p)`$, turns out to be active , that is, to be relevant in the determination of the boundary of the orbit space $`1\mathrm{R}^8/G`$:

$$\begin{array}{ccc}\hfill A(p)& =& 3p_{2}^{}{}_{}{}^{3}p_{3}^{}{}_{}{}^{2}+18p_1p_{2}^{}{}_{}{}^{2}p_3p_418p_{2}^{}{}_{}{}^{3}p_3p_4+27p_{1}^{}{}_{}{}^{2}p_2p_{4}^{}{}_{}{}^{2}\hfill \\ & & 54p_1p_{2}^{}{}_{}{}^{2}p_{4}^{}{}_{}{}^{2}+27p_{2}^{}{}_{}{}^{3}p_{4}^{}{}_{}{}^{2}+p_3p_{4}^{}{}_{}{}^{3}9p_2p_3p_4p_5\hfill \\ & & 9p_1p_{4}^{}{}_{}{}^{2}p_5+9p_2p_{4}^{}{}_{}{}^{2}p_527p_1p_2p_{5}^{}{}_{}{}^{2}+27p_{2}^{}{}_{}{}^{2}p_{5}^{}{}_{}{}^{2}+9p_{5}^{}{}_{}{}^{3}.\hfill \end{array}$$
(25)
The relations assuring that $`\widehat{P}(p)0`$ and has rank 4, define a unique 4-dimensional stratum $`\widehat{S}^{(4)}`$ in the orbit space. Using well known matrix theory results, these conditions could be explicitly written, for instance, in the form $`A(p)=0`$ and $`M_i(p)>0`$, $`i=1,\mathrm{},4`$, where $`M_i`$ is the sum of the order $`i`$ principal minors of the matrix $`\widehat{P}(p)`$: A frightening set of conditions that it is not worthwhile to write down explicitly.

Even in this simple example one immediately realizes that the choice of a minimal set of explicit algebraic relations providing a cylindrical decomposition for the semi-algebraic subset $`\widehat{S}^{(4)}`$ of $`1\mathrm{R}^5`$ would be a really hard task (for the more peripheral strata, instead, the problem is much easier to solve). An immediate application of the results proved in the previous Section, on the contrary, leads to a simple rational global parametrization of the sub-principal stratum $`\widehat{S}^{(4)}`$.

A “typical point” of the stratum is $`x_\mathrm{t}=(1,1,0,0,0,0,1,1)`$. The corresponding isotropy subgroup $`H`$ of $`G`$ is the $`\text{ }\mathrm{ZZ}_2`$ group generated by the reflection

$$\text{diag}(1,1,1,1,1,1,1,1)G,$$

representing the element diag$`(1,1,1)`$ O(3).

The vector space $`V`$ formed by the $`H`$-invariant vectors of $`1\mathrm{R}^n`$ turns out to be be the following:

$$V=\left\{x1\mathrm{R}^8\right|x_3=x_4=x_6=0\}.$$

The elements of O(3), corresponding to elements of $`\text{Stab }(H,G)`$, are block-diagonal matrices of the form diag$`(\pm 1,O)`$, with $`O`$ O(2). Therefore, $`\text{Stab }(H,G)`$ is isomorphic to a group $`\text{ }\mathrm{ZZ}_2`$O(2) and the quotient group $`K=\text{Stab }(H,G)/H`$ is the representation in $`1\mathrm{R}^8`$ (induced by the representation $`G`$ of O(3)) of the O$`{}_{1}{}^{}(2)`$ subgroup of O(3), formed by the rotations around the first axis.

Using coordinate $`v=(x_1,x_2,x_5,x_7,x_8)`$ for a vector $`vV`$, the elements of $`K`$ turn out to be block diagonal matrices leaving stable the following subspaces $`V^A`$, $`1A3`$:

$`V^1`$ $`=`$ $`\{(x_1,0,0,0,0)V|x_11\mathrm{R}\},`$
$`V^2`$ $`=`$ $`\{(0,x_2,x_5,0,0)V|x_2,x_51\mathrm{R}\},`$
$`V^3`$ $`=`$ $`\{(0,0,0,x_7,x_8)V|x_7,,x_81\mathrm{R}\}.`$ (26)
A proper rotation $`r(\varphi )`$ O$`{}_{1}{}^{}(2)`$ of an angle $`\varphi `$ and the reflection diag(-1,1)$`\mathrm{O}_1(2)`$ are represented in the primed basis of $`V`$ by the $`5\times 5`$ matrices $`h(\varphi )=1r(2\varphi )r(\varphi )`$ and $`j=\mathrm{diag}(1,1,1,1,1)`$.

Noting that the complex variables $`z_1=x_2+ix_5`$ and $`z_2=x_7+ix_8`$ transform into $`e^{2i\varphi }z_1`$ and, respectively, $`e^{i\varphi }z_2`$ under a rotation $`\stackrel{~}{h}(\varphi )`$ and into $`z_1^{}`$ and, respectively, $`z_2^{}`$ under a reflection $`j`$, it is easy to realize that a possible MIB. for $`(\stackrel{~}{H},V)`$ is the following:

$`\lambda _1`$ $`=`$ $`x_1,`$
$`\lambda _2`$ $`=`$ $`|z_1|^2=x_2^2+x_5^2,`$
$`\lambda _3`$ $`=`$ $`|z_2|^2=x_7^2+x_8^2,`$
$`\lambda _4`$ $`=`$ $`2\text{Re}(z_1z_{2}^{}{}_{}{}^{2})=\mathrm{\hspace{0.17em}2}\left(x_2x_{7}^{}{}_{}{}^{2}2x_5x_7x_8x_2x_{8}^{}{}_{}{}^{2}\right).`$ (27)
It is, now, easy to express the $`p`$’s in term of the $`\lambda `$’s, $`p=\varphi (\lambda )`$, and to check that the following expressions, obtained in this way, identically satisfy the equation $`A(p(\lambda ))=0`$ (see (25)) entering the definition of the stratum $`\widehat{S}^{(4)}`$:

$`\varphi _1(\lambda )`$ $`=`$ $`\lambda _{1}^{}{}_{}{}^{2}+\lambda _2+\lambda _3,`$
$`\varphi _2(\lambda )`$ $`=`$ $`\lambda _3,`$
$`\varphi _3(\lambda )`$ $`=`$ $`2\sqrt{3}\left(\lambda _{1}^{}{}_{}{}^{3}3\lambda _1\lambda _2\right),`$
$`\varphi _4(\lambda )`$ $`=`$ $`{\displaystyle \frac{\sqrt{3}}{2}}\left(2\lambda _1\lambda _3+\sqrt{3}\lambda _4\right),`$
$`\varphi _5(\lambda )`$ $`=`$ $`\lambda _{1}^{}{}_{}{}^{2}\lambda _3+3\lambda _2\lambda _3+\sqrt{3}\lambda _1\lambda _4.`$ (28)
As explained in the previous section, since the group $`K`$ is coregular, the range $`\mathrm{\Delta }`$ for $`\lambda `$, is the region where the $`\widehat{P}`$-matrix, $`\widehat{\mathrm{\Lambda }}(\lambda )`$ associated to the MIB $`\{\lambda \}`$ is positive definite and the rank of the jacobian matrix $`J(\lambda )`$ of the transformation $`\varphi (\lambda )`$ is maximum (=4). The matrices $`\widehat{\mathrm{\Lambda }}(\lambda )`$ and $`J(\lambda )`$ are easily calculated to be

$$\widehat{\mathrm{\Lambda }}(\lambda )=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 4\lambda _2& 0& 2\lambda _4\\ 0& 0& 4\lambda _3& 4\lambda _4\\ 0& 2\lambda _4& 4\lambda _4& 4\left(\lambda _{3}^{}{}_{}{}^{2}+4\lambda _2\lambda _3\right)\end{array}\right)$$
(29)
and

$$J(\lambda )^\mathrm{T}=\left(\begin{array}{cccc}2\lambda _1& 1& 1& 0\\ 0& 0& 1& 0\\ 6\sqrt{3}\left(\lambda _{1}^{}{}_{}{}^{2}\lambda _2\right)& 6\sqrt{3}\lambda _1& 0& 0\\ \sqrt{3}\lambda _3& 0& \sqrt{3}\lambda _1& \frac{3}{2}\\ 2\lambda _1\lambda _3+\sqrt{3}\lambda _4& 3\lambda _3& \lambda _{1}^{}{}_{}{}^{2}+3\lambda _2& \sqrt{3}\lambda _1\end{array}\right).$$
(30)
The conditions assuring the positivity of $`\widehat{\mathrm{\Lambda }}(\lambda )>0`$ can be written in the form

$$\mathrm{\Delta }=\left\{(\lambda _1,\lambda _2,\lambda _3,\lambda _4)1\mathrm{R}^4\right|\lambda _2>0\text{and}\lambda _3>0\text{and}\lambda _4^2<4\lambda _2\lambda _{3}^{}{}_{}{}^{2}\}$$
(31)
and the rank of $`J(\lambda )`$ turns out to equal four for all $`\lambda \mathrm{\Delta }`$. So we can conclude that the stratum is connected, a piece of information that would be difficult to derive directly from the relations defining the stratum in implicit form ($`(A(p)=0`$ and $`M_i(p)>0`$).

The parametrization obtained for the sub-peripheral stratum $`\widehat{S}^{(4)})`$ turns out to be useful, also, because bordering values of $`\lambda `$ immediately determine bordering values of $`p`$, corresponding to more peripheral strata of $`1\mathrm{R}^8/G`$.

## Aknowledgements

This paper is partially supported by INFN and MIURST.


format: text

text:
# Optimization and self-organized criticality in a magnetic system

## I Introduction

Nature which is composed of dead and living things is a system far out of equilibrium. This can be evidenced by measuring nature’s evolution with the appropriate scales of space and time. In particular, the dynamics of the living things is basically governed by the theory of natural selection first proposed by Charles Darwin cd . This theory is certainly one of greatest scientific achievements of the nineteenth century. Very briefly, this theory simply says that evolution occurs not by breeding species best adapted to their environment but by driven to extinction those less or poorly adapted. This mechanism leads to the emergence of highly specialized structures. If we also consider the astonishing variability of the species, we then can say that nature is a complex system. Indeed, for all we know, nature operates at the self-organized critical state bak .

One of the most fundamental characteristics of a system with self-organized criticality (SOC) is to exhibit a stationary state with a long-range power law decay of the spatial and temporal correlations btw . Power law is a very abundant behavior found either in natural phenomena such as the light emitted from quasars, the earthquake’s intensity, the water level of the Nile or as a direct result of human activities like the distribution of cities by size, the repetition of words in the Bible and in traffic jams.

Self-organized critical systems evolve to the complex critical state without the interference of any external agent. Differently from what happens in the usual critical phase transition, in SOC there is not a tuning parameter. The prototypical example of SOC is a pile of sand btw . Another common property of SOC is that the self-organization state only takes place after a very long transient period. Last but not least, a minor change in the system can cause colossal instabilities called avalanches. Intermittent bursts of activity separating long periods of quiescence is called punctuated equilibrium. Gould has conjectured that the biological evolution itself shows, in fact, this kind of equilibrium gou .

Now, if nature can really be found in a critical self-organized state, is this state optimal or extremal in some sense?. Through the systematic rejection of the worst, the Darwinian evolutionary theory is a born optimization structure. By adding interactions and competition between the species we will witness the emergence of co-evolution.

One model specially tailored to represent the co-evolutionary activities of the species is the Bak-Sneppen model bs . In this model, each species is located on the sites of a lattice and has associated a fitness value between 0 and 1 (randomly drawn from an uniform distribution). At each time step, the species with the smallest associated value as well as its nearest neighbors are selected to replace their fitness with new random numbers. In one dimension, after a long transient time, almost all species have fitness larger than the critical value 0.67 bs .

Recently, inspired by natural processes, some heuristic optimization techniques have been proposed: genetic algorithms hol , simulated annealing kirkpa  and extremal optimization boe . The extremal optimization (EO) method seems to be the most efficient of them since it brings the system faster and closer to its ground-state boe . In a few words, this method consists of the following rules: i) a discrete dynamical variable $`S_i`$ (initially chosen at random) is associated to each site $`i`$ of a lattice with $`N`$ points; ii) a fitness $`\lambda _i`$ is attributed to that site using some given prescription; iii) all lattice sites are then increasingly ranked according to their fitness (the site with the worst fitness is of rank 1); iv) a site of rank $`k`$ ($`1kN`$) is selected with probability $`P(k)k^\tau `$ ($`\tau `$ is an arbitrary real positive number) and its dynamical variable $`S_i`$ is changed to $`S_i^{^{}}`$ ($`S_i^{^{}}S_i`$, compulsorily); v) repeat at step iii) as long as desired.

In this paper, a kind of Bak-Sneppen dynamics is applied to a spin system which possesses a complex ground state structure in one dimension. The discrete fitness variability is identified as being responsible for the absence of a critical self-organized state. By introducing a noise in the spin configuration space, we show that the system can now reach a critical self-organized state with power law correlations. This simple trick can easily be extended to other types of discrete systems. On the other hand, through an analysis of the spatial and temporal correlations, we provided a numerical confirmation that the extremal optimization method is not a SOC dynamics but a non-critical algorithm with an infinite spatial range and an exponential time decay of the avalanches. The two dynamics: the Bak-Sneppen with noise (BSN) and the extremal optimization (EO) are then investigated with respect to their efficiency to minimize energy. There is an optimal interval of the parameter $`\tau `$ where EO is superior to BSN.

## II The p-states chiral clock model

To explain our main ideas, we have chosen the one dimensional p-states chiral clock model ($`CC_p`$) ost ; huse  as our experimental system. In higher dimensions, this system exhibits a complex phase transition diagram with commensurate and incommensurate phases. In one dimension, the competition between the applied magnetic field, which tries to align the spins, and the chirality, which tries to flip them, gives rise to a rich ground-state diagram in the space of the parameters. The hamiltonian is given by

$`H={\displaystyle \underset{i=1}{\overset{N}{}}}\{1\mathrm{cos}(2\pi ({\displaystyle \frac{S_{i+1}S_i}{p}}\mathrm{\Delta }))+`$
$`h[1\mathrm{cos}(2\pi ({\displaystyle \frac{S_i1}{p}}))]\}={\displaystyle }_{i=1}^N\lambda _i`$ (1)
where $`p`$ is a positive integer number, $`S_i=1,..,p`$ is the spin variable at the site $`i`$ (with periodic boundary conditions applied) and $`h`$ and $`\mathrm{\Delta }`$ are the magnetic field and chirality, respectively. By symmetry arguments, $`h`$ and $`\mathrm{\Delta }`$ may be restricted to the intervals $`[0,\mathrm{}]`$ and $`[0,1/2]`$.

For $`p=3`$, the chiral clock model has 3 regions with different ground-states (see Fig.1). We denote by $`<1>`$, $`<1213>`$ and $`<123>`$ the regions with periods 1, 2 and 3, respectively. The numbers correspond directly to the sequence of the spin states. The region $`<1213>`$ is super degenerate, i. e., the spin state sequence 12 may be equally followed by 12 or 13. For a finite ring, this means that the degenerescence of this region grows exponentially with the lattice size.

## III Searching the ground-state with a Bak-Sneppen dynamics

We choose the following form for the fitness $`\lambda _i`$

$`\lambda _i`$ $`=`$ $`{\displaystyle \frac{1}{2}}[1\mathrm{cos}(2\pi ({\displaystyle \frac{S_{i+1}S_i}{p}}\mathrm{\Delta }))]+`$ (2)
$`{\displaystyle \frac{1}{2}}[1\mathrm{cos}(2\pi ({\displaystyle \frac{S_iS_{i1}}{p}}\mathrm{\Delta }))]+`$
$`{\displaystyle \frac{1}{3}}h[1\mathrm{cos}(2\pi ({\displaystyle \frac{S_{i+1}1}{p}}))]+`$
$`{\displaystyle \frac{1}{3}}h[1\mathrm{cos}(2\pi ({\displaystyle \frac{S_i1}{p}}))]+`$
$`{\displaystyle \frac{1}{3}}h[1\mathrm{cos}(2\pi ({\displaystyle \frac{S_{i1}1}{p}}))]`$
There is a certain art and arbitrariness to select the fitness form. For instance, one could equally well have chosen a pre-factor 1/4 for the magnetic fields at the sites $`i+1`$ and $`i1`$ and 1/2 for the site $`i`$. Different fitness forms may lead to quite different values of some physical quantities determined by the dynamics, e. g., the average energy in the stationary state. The fitness defined by Equation (2) is the form with the highest symmetry - the magnetic field is equally distributed between the sites $`i1`$, $`i`$ and $`i+1`$ as well as is the chirality between the pair of sites $`[i,i1]`$ and $`[i+1,i]`$. It represents the best result we got for the average energy in a bunch of trials.

Let us now describe our procedure. Initially, to each site $`i`$ of the ring, we attribute by chance one of the $`p`$ possible values of the spin variable $`S_i`$. Using equation (2), we calculate all the corresponding fitness $`\lambda _i`$ and find the smaller (worst) one $`\lambda _j`$. New spin variables are then randomly assigned to the sites $`j`$, $`j+1`$ and $`j1`$. So although the dynamics involves 3 spins, due to our fitness definition, it affects (changes) 5 consecutive fitness (from the site $`j2`$ to $`j+2`$). Observe that here the Bak-Sneppen dynamics is being applied to the spin configuration space not to the fitness space itself (as it was originally done in the evolutionary context bs ). In the final step, a new site with the smallest fitness is searched and the whole process continues as long as we wish. However, even for a modest lattice size, this dynamics is hampered by the discrete fitness variability. Let us explain why. If $`p=3`$ ($`h`$ and $`\mathrm{\Delta }`$ fixed) there are at most 27 possible values of the fitness (besides, some of these may be degenerate). This means that, for a lattice with a reasonable size, we will generally find not just one but a large number of sites with exactly the same(smallest) fitness value. The simplest solution to the problem seems to put all those sites in a list and to choose one of them at random. We will call this dynamics as the Bak-Sneppen with draw (BSD). As we shall see later, neither from the point of view of the spatial correlations nor from the time correlations is this dynamics a true SOC.

## IV The noise

It is the discrete variability of the fitness (or, equivalently, of the spin variable) which precludes the establishment of a self-organized critical state, so we searched a simple way to solve the problem. Suppose that a noise $`\eta `$ is added to the original spin variable $`S_i`$ (an integer in the interval $`[1,p]`$), i. e.

$$S_i^{^{}}=S_i+\eta (12r)$$
(3)
where $`r[0,1]`$ is a random number generated from a flat distribution. The new spin variable $`S_i^{^{}}`$ as well as the corresponding fitness have now the desired continuous characteristic. By choosing the noise $`\eta `$ sufficiently small the relevant physical properties (like the energy per site or the magnetization per site) will not be affected. In this paper we set $`\eta =10^3`$. Using double numerical precision, we varied $`\eta `$ from $`10^{12}`$ up to $`10^3`$ with no important difference for the physical quantities. With this trick, any previously discrete fitness $`\lambda `$ is turned into a continuous variable inside some interval $`\mathrm{\Delta }\lambda `$ controlled by the noise $`\eta `$, the chirality $`\mathrm{\Delta }`$ and the magnetic field $`h`$. We will call this dynamics as the Bak-Sneppen with noise (BSN). Our next objective is to compare the 3 dynamics EO, BSD and BSN with respect to their efficiencies.

In order to guarantee that the stationary state had already been reached and to get good averages for the physical quantities, a huge amount of computation was performed. Using the same fitness definition (equation (2)) for all the three algorithms BSD, BSN and EO, we simulated each one of them over $`2`$ $`10^9`$ runs on a ring of 4001 sites. Discarding the first $`2`$ $`10^8`$ runs ($`10\%`$ of the total) as the transient time, averages were then taken over the remaining steps. The results for the energy histograms are shown in Figure 2.

The simulations were done at the point $`III`$ of the region $`<123>`$ (see Figure 1) where the ground state energy per spin is equal to $`0.8055`$. The best performance was obtained by the EO algorithm with $`\tau =2.1`$, followed by the EO with $`\tau =1.2`$, BSN and BSD. Their respective mean energies were $`0.828\pm 0.003`$, $`0.969\pm 0.009`$, $`0.973\pm 0.004`$ and $`0.983\pm 0.005`$.

## V The spatial and temporal distributions

To study the spatial correlation, we measured the distribution $`D(x)`$, of the distance $`x`$ between two subsequent activated sites bs . Recall that for the three algorithms we activate a site $`i`$ by changing its spin state $`S_i`$ and the corresponding fitness $`\lambda _i`$. We plotted $`D(x)`$ in the Figure 3.

Clearly, EO is an algorithm with an infinite spatial range \- it doesn’t matter how far one site is of the other, the activation probability is constant. On the other hand, the BSN algorithm exhibits a power law dependence $`D(x)x^{3.19\pm 0.02}`$ with the exponent being compatible with that of the Bak-Sneppen model ($`3.23\pm 0.02`$ maya ). Moreover, we got at the points $`I`$, $`II`$, $`III`$ and $`IV`$ (see Figure 1) the same exponent value, indicating that the universality principle holds in the space of the parameters $`h`$ and $`\mathrm{\Delta }`$. Finally, from the Figure 3 we conclude that the BSD algorithm is of a mixed kind, having the BSN behavior for small distances and the EO for large distances.

In the stationary regime, the BSN dynamics shows an intermittent time evolution with long periods of passivity interrupted by sudden bursts of activity, i. e., it exhibits a punctuated equilibrium. This abrupt change of activity is called an avalanche. We say that an avalanche is happening if there exist one site of the ring whose fitness is smaller than a certain threshold $`\lambda _c`$. The size $`A`$ of an avalanche is defined as the number of subsequent time steps with at least one fitness below that threshold. For each one of the three dynamics we calculated the probability distribution of the avalanches $`P(A)`$. The results are illustrated in the Figure 4.

The Figures 4(a), 4(b) and 4(c) correspond to the BSN, EO and BSD algorithms, respectively. Before we analyze $`P(A)`$, let us first discuss how the critical thresholds were obtained. At the time step $`2`$ $`10^8`$ (the end of the transient period) and with the magnetic field and chirality fixed at the values $`0.8`$ and $`0.35`$, respectively, we determined the fitness histograms of the whole ring. They are shown as insets of the Figure 4. Since in the EO and the BSD algorithms there are only some few possible values for the fitness $`\lambda `$ (a maximum of 27 when $`p=3`$ and many of them are degenerate), we may vary the (discrete) $`\lambda `$ values until the avalanches are founded. Remember that if $`\lambda <\lambda _c`$ there will be no avalanches while if $`\lambda >\lambda _c`$ only one (infinite) avalanche is present. Due to the discreteness values of $`\lambda `$, it is very improbable to find the system in a sub or supercritical regime. We found $`\lambda _c=0.8055`$ and $`\lambda _c=1.5061`$ for the EO and BSD dynamics, respectively. For the BSN algorithm, however, the fitness is continuous. There is a fitness fluctuation $`\mathrm{\Delta }\lambda `$ due to the presence of the noise $`\eta `$. In our case, the maximum value of the relative fluctuation $`\mathrm{\Delta }\lambda `$ / $`\lambda `$ is $`1.86`$ $`10^3`$. To find the critical threshold, we wrote a program which varies the fitness values (inside the range $`\mathrm{\Delta }\lambda `$) until the resulting avalanches have sizes between 500 and 2000 (which seems reasonable to avoid the sub and supercritical regimes). We determined $`\lambda _c=1.5059`$.

We can now go back to the probability distribution of the avalanches $`P(A)`$. They were all calculated at their respective thresholds $`\lambda _c`$. The EO algorithm (Figure 4(b)) shows an exponential decay with $`A`$. The BSN (Figure 4(a)), on the other hand, has a power law scaling $`P(A)A^{0.87\pm 0.01}`$. This value is somewhat discrepant from that of the evolutionary Bak-Sneppen model ($`1.07\pm 0.01`$ maya ), but we should remember that, for our system, the exact determination of the critical threshold position is much more difficult and one can easily be found in a sub or supercritical regime. For the BSD algorithm (Figure 4(c)), we found once more a mixed behavior described by $`P(A)A^{0.68}e^{0.002A}`$.

## VI Conclusions

Based on the Bak-Sneppen ideas, we proposed an optimization algorithm whose dynamics, in the steady state regime, exhibits self-organized criticality. It has been successfully applied to find the ground states of the clock chiral model and it can be easily extended to any other magnetic system. From the three dynamics studied in this paper, we conclude that only the BSN algorithm conducts the system to a self-organized critical state. The essential point was to recognize that the discrete fitness values, present in the EO and BSD algorithms, preclude the system to have a power law decay of the spatial correlation. To overcome this problem we introduced a small noise in the spin configuration space. Another important conclusion we arrived is that to possess SOC characteristics does not guarantee a dynamics to be optimal. This statement was proved here for the EO algorithm. The EO algorithm, which is not SOC since it has an infinite spatial range and the avalanches decay exponentially, has a peak of the energy histogram (with $`\tau =2.1`$) which is only $`2.7\%`$ further from the exact ground state value. This is a stunning result which cannot be beaten by the BSN dynamics. At $`\tau =1.2`$, the EO and BSN are almost equivalent. On the other hand, the BSD algorithm is of a mixed type. It can be obtained by taking the limit $`\eta 0`$ in the BSN.

Finally, it is important to observe that, contrary to what happens with BSN, the EO algorithm has one arbitrary and free parameter $`\tau `$. If $`\tau 0`$, EO becomes a random walk and if $`\tau \mathrm{}`$, the system may stack in a dead end. In both limits, the EO efficiency is completely spoiled and an optimal value of $`\tau `$ should be found in somewhere between. In the BSN dynamics there is no tuning parameter. Using the ideas described here, we wish to develop a SOC optimization algorithm to some classical combinatorial problems like the bipartition of graphs.

This work was supported in part by the CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico) and by the FAPESP (Fundação de Amparo a Pesquisa do Estado de São Paulo).