format: text

text:
# Non-semisimple Lie algebras with Levi factor 𝔰𝔬(3),𝔰𝔩(2,ℝ) and their invariants

## 1 Introduction

The important role played by invariant theory in Physics has been recognized long ago. Electroweak interactions and quantum numbers in the study of particle states are based on the concept of symmetry, and their invariants provide fundamental information. Among the various types of symmetry, dynamical ones constitute one of the more important cases, as shown by Gell-Mann and Ne’eman in their hadron classification . The analysis of the group $`SU\left(3\right)`$ resulted in the prediction of new particles whose mass could be derived from the invariants of the group. The invariants of Lie algebras have also shown their efectiveness in the description of Hamiltonians , the labelling of irreducible representations or the study of coadjoint orbits . Other important applications of invariants arise in their combination with the theories of Lie algebra contractions, deformations and rigidity . For example, all kinematical algebras are related by a contraction procedure, which has allowed a further analysis of these algebras . The interest of invariants of rigid Lie algebras is fully justified by the fact that semisimple Lie algebras are rigid. The invariants of semisimple Lie algebras constitute a classical problem, and it is the only case which has been solved in a satisfactory manner. The invariants of solvable Lie algebras are only studied for specific classes, as they do not underly to a structure theory like the classical algebras. What refers to the Lie algebras with non-trivial Levi decomposition, invariants are known for physically important algebras, like the special affine algebras $`𝔰𝔞(n,)`$, the kinematical Lie algebras and their subalgebras.

A formula for the number $`𝒩\left(𝔤\right)`$ of functionally independent invariants of the coadjoint representation of a Lie algebra $`𝔤`$ was given by Beltrametti and Blasi  and Pauri and Prosperi  in the mid 1960s. This fact reduces the computation of this number to the determination of the rank of a skew-symmetric matrix $`A\left(𝔤\right)`$ whose entries correspond to the Lie brackets of $`𝔤`$. With some effort, this formula can be used to show that the number of invariants of semisimple Lie algebras coincides with its rank . Moreover, it proves that for direct sums $`𝔤_1𝔤_2`$ of Lie algebras the number $`𝒩\left(𝔤_1𝔤_2\right)`$ is $`𝒩\left(𝔤_1\right)+𝒩\left(𝔤_2\right)`$. One can ask whether for semi-direct sums $`𝔤=𝔰\stackrel{}{}_R𝔯`$, $`𝔰`$ being the Levi factor of $`𝔤`$, $`R`$ a representation of $`𝔰`$ and $`𝔯`$ the maximal solvable ideal (called radical) of $`𝔤`$ some formula exists which allows to express $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)`$ in terms of $`𝒩\left(s\right),𝒩\left(𝔯\right)`$ and some quantity related to the representation $`R`$. The motivation of this problem lies in the study of the special affine algebras $`𝔰𝔞(n,)`$, which are a semidirect sum of the simple Lie algebra $`𝔰𝔩(n,)`$ and an $`n`$-dimensional abelian Lie algebra . These algebras are known to have only one invariant (which turns out to be a Casimir operator), which shows that the representation plays a crucial role in the semidirect product, and that in principle the existence of a formula expressing the number of invariants in terms of the factors does not exist. The main reason for its nonexistence lies in the distinct possibilities of choice for radicals $`𝔯`$ for a fixed representation of $`𝔰`$. The question that arises naturally in this context is if there exist Lie algebras $`𝔰\stackrel{}{}_R𝔯`$ with non-trivial Levi decomposition (i.e. $`𝔰0`$ and $`[𝔰,𝔯]0`$) such that $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$.

In this work we show that such algebras exist for any dimension $`n6`$. Moreover, by considering the simple algebras $`𝔰𝔬\left(3\right)`$ and $`𝔰𝔩(2,)`$, we analyze the number $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)`$ for various kinds of representations $`R`$ and solvable Lie algebras $`𝔯`$.

Any Lie algebra $`𝔤`$ considered in this work is defined over the field $``$ of real numbers. We convene that nonwritten brackets are either zero or obtained by antisymmetry. We also use the Einstein summation convention. Abelian Lie algebras of dimension $`n`$ will be denoted by $`nL_1`$.

## 2 Invariants of Lie algebras. The Beltrametti-Blasi formula

The method to determine the invariants of a Lie algebra in terms of systems of partial differential equations (PDEs) has become standard in the physical literature , and it is the one we will use here. Let $`\{X_1,..,X_n\}`$ be a basis of $`𝔤`$ and $`\left\{C_{ij}^k\right\}`$ be the structure constants over this basis. We consider the representation of $`𝔤`$ in the space $`C^{\mathrm{}}\left(𝔤^{}\right)`$ given by:

$$\widehat{X}_i=C_{ij}^kx_k_{x_j},$$
(1)
where $`[X_i,X_j]=C_{ij}^kX_k`$ $`\left(1i<jn,\mathrm{\hspace{0.33em}1}kn\right)`$. This representation is isomorphic to $`ad\left(𝔤\right)`$, and therefore satisfies the brackets $`[\widehat{X}_i,\widehat{X}_j]=C_{ij}^k\widehat{X}_k`$. The invariants $`F(X_1,..,X_n)`$ of $`𝔤`$:

$$[X_i,F(X_1,..,X_n)],$$
(2)
are found by solving the system of linear first order partial differential equations:

$$\widehat{X}_iF(x_1,..,x_n)=C_{ij}^kx_k_{x_j}F(x_1,..,x_n)=0,\mathrm{\hspace{0.33em}1}in.$$
(3)
and then replacing the variables $`x_i`$ by the corresponding generator $`X_i`$ (possibly after symmetrizing). In recent years new algorithms to solve system $`\left(3\right)`$ have been developed, which simplify the calculation in some cases . A maximal set of functionally independent solutions of $`\left(3\right)`$ will be called a fundamental set of invariants. Polynomial solutions of system $`\left(3\right)`$ are therefore polynomials in the generators which commute with $`𝔤`$, thus correspond to the well known Casimir operators . The system does not impose additional conditions which imply that the solutions are polynomials, so that a non-polynomial solution will be called, in some analogy with the classical case, a generalized Casimir invariant or simply an invariant of $`𝔤`$. If $`F`$ reduces to a constant we say that the invariant is trivial. In the case of semisimple Lie algebras, the solutions found are in fact Casimir operators, and the number of functionally independent invariants is given by the dimension of its Cartan subalgebra. However, for non-semisimple Lie algebras there is no reason to suppose that only the polynomial invariants are of physical interest. A classical example for a Hamiltonian being a nonlinear function of the Casimir operators was described by Pauli in .

Another important task is to find the maximal number $`𝒩\left(𝔤\right)`$ of functionally independent solutions of $`\left(3\right)`$. For the case of the classical groups this number depends only on the dimension of a Cartan subalgebra, while for solvable Lie algebras no such general formula exists . However, for a fixed algebra, this number can be described in terms of the dimension and a certain matrix associated to the commutator table. More specifically, denote by $`A\left(𝔤\right)`$ the matrix whose $`(i,j)`$-entry is the bracket $`[X_i,X_j]`$. Such a matrix has necessarily even rank. Then $`𝒩\left(𝔤\right)`$ is given by

$$𝒩\left(𝔤\right)=dim𝔤\{rankA\left(𝔤^{}\right)|𝔤^{}𝔤\}.$$
(4)
This formula was first described by Beltrametti and Blasi  and Pauri and Prosperi . The number of polynomial solutions is generally lower than $`𝒩(𝔤)`$ , up to certain special classes of Lie algebras (like semisimple and nilpotent) .

Invariants of Lie algebras have been determined for some classes of non-semisimple Lie algebras, like solvable Lie algebras in low dimensions , the kinematical Lie algebras  or the special affine Lie algebras .

We give an example to illustrate the general method of obtaining the invariants.

Let $`𝔰=𝔰𝔬\left(3\right)`$ and consider the representation $`R=ad𝔰𝔬\left(3\right)`$. Let us suppose that the radical of the six dimensional Lie algebra $`𝔰\stackrel{}{}_R𝔯`$ is the three dimensional abelian algebra $`3L_1`$. The algebra $`𝔰\stackrel{}{}_R𝔯`$ is of interest for multidimensional extensions of the Bianchi type-IX cosmology , and the corresponding vacuum Einstein field equations have been solved in . Indeed this is the simplest embedding of a Bianchi type-IX algebra in an algebra with non-trivial Levi decomposition . It can easily be verified that $`𝔰\stackrel{}{}_R𝔯`$ satisfies $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=2`$. The invariants are solution of the system:

$$\begin{array}{c}\widehat{X}_1F=\left(x_3_{x_2}+x_2_{x_3}x_6_{x_5}+x_5_{x_6}\right)F=0\hfill \\ \widehat{X}_2F=\left(x_3_{x_1}x_1_{x_3}+x_6_{x_4}x_4_{x_6}\right)F=0\hfill \\ \widehat{X}_3F=\left(x_2_{x_1}+x_1_{x_2}x_5_{x_4}+x_4_{x_5}\right)F=0\hfill \\ \widehat{X}_4F=\left(x_6_{x_2}+x_5_{x_3}\right)F=0\hfill \\ \widehat{X}_5F=\left(x_6_{x_1}x_4_{x_3}\right)F=0\hfill \\ \widehat{X}_6F=\left(x_5_{x_1}+x_4_{x_2}\right)F=0\hfill \end{array}\},$$
(5)
Since the equations $`\left\{\widehat{X}_iF=0\right\}_{i=4,5,6}`$ do not depend on $`_{x_i}F`$ for $`i=4,5,6`$, we can extract the following system from $`\left(5\right):`$

$$\begin{array}{c}\widehat{X}_1^{}F=\left(x_6_{x_5}+x_5_{x_6}\right)F=0\hfill \\ \widehat{X}_2^{}F=\left(x_6_{x_4}x_4_{x_6}\right)F=0\hfill \\ \widehat{X}_3^{}F=\left(x_5_{x_4}+x_4_{x_5}\right)F=0\hfill \end{array}\},$$
(6)
which has the solution $`I_1=x_4^2+x_5^2+x_6^2`$. Now, as the rank of the coefficients matrix corresponding to this subsystem is two, the other solution of $`\left(5\right)`$ will depend also on $`x_1,x_2,x_3`$. This invariant can be chosen as $`I_2=x_1x_4+x_2x_5+x_3x_6`$. The important fact about this example is the solution found extracted from the subsystem $`\left(6\right)`$. In a following section we will see that this is not casual, but a property that holds in general.

## 3 Semidirect sums of Lie algebras

The classification of Lie algebras is simplified in some manner by the Levi decomposition theorem, which states that any Lie algebra is essentially formed from a semisimple Lie algebra $`𝔰`$ called the Levi factor of $`𝔤`$ and a maximal solvable ideal $`𝔯`$, called the radical . Since the latter is an ideal, the Levi factor $`𝔰`$ acts on $`𝔯`$, and there are two possibilities for this action:

$$\begin{array}{c}[𝔰,𝔯]=0\hfill \\ [𝔰,𝔯]0\hfill \end{array}$$

If the first holds, then $`𝔤`$ is a direct sum $`𝔰𝔯`$, whereas the second possibility implies the existence of a representation $`R`$ of $`𝔰`$ which describes the action, i.e.,

$$[x,y]=R\left(x\right).y,x𝔰,y𝔯$$
(7)
Unless there is no ambiguity, it is more convenient to write $`\stackrel{}{}_R`$ instead of $`\stackrel{}{}`$, which is the common symbol for denoting semidirect products. Since $`\left(7\right)`$ implies that the radical is a module over $`𝔰`$, we have to expect severe restrictions on the structure of the radical, while for direct sums any solvable Lie algebra is suitable as radical.

###### Proposition 1

Let $`𝔰`$ be a semisimple Lie algebra and $`R`$ an irreducible representation. If $`𝔰\stackrel{}{}_R𝔯`$ is the Levi decomposition of a Lie algebra, then $`𝔯`$ is an abelian algebra.

The proof is immediate, since the Jacobi condition implies that the ideals $`𝔯^{\left(0\right)}:=𝔯`$, $`𝔯^{\left(i\right)}:=[𝔯^{\left(i1\right)},𝔯^{\left(i1\right)}]`$ for $`i1`$ are invariant by the action of $`𝔰`$. If $`R`$ is irreducible, then either $`𝔯^{\left(1\right)}=0`$ or $`𝔯^{\left(1\right)}=𝔯`$, and since $`𝔯`$ is solvable, $`𝔯^{\left(1\right)}𝔯`$. Reasoning similarly, we can easily deduce that the radical $`𝔯`$ is mapped into its maximal nilpotent ideal $`𝔫`$ (usually called the nilradical of $`𝔯`$), from which the following property follows:

###### Proposition 2

Let $`𝔰\stackrel{}{}_R𝔯`$ be a Levi decomposition. If the representation $`R`$ does not posses a copy of the trivial representation, then the radical $`𝔯`$ is a nilpotent Lie algebra.

This result is in some manner surprising, since it implies the existence of a copy of the trivial representation whenever the radical is not nilpotent. Of course it does not imply that a nilpotent Lie algebra cannot be the radical when the representation contains copies of the trivial representation.

The Lie algebras having non-trivial Levi decomposition have been completely classified up to dimension 8 . For dimensions 9 and 10 some partial results do also exist, mainly Levi factors isomorphic to rank one simple Lie algebras. Since the algebra $`𝔰𝔬\left(3\right)`$ is a real form of $`𝔰𝔩(2,)`$, the number of (real) representations of $`𝔰𝔬\left(3\right)`$ is lower than for for $`𝔰𝔩(2,)`$ , which implies the existence of much more Lie algebras having the latter as Levi factor.

###### Lemma 1

Let $`𝔤=𝔰𝔯`$. Then $`𝒩\left(𝔤\right)=𝒩\left(𝔰\right)+𝒩\left(𝔯\right)`$.

This is an obvious consequence of the Beltrametti-Blasi formula. Since the sum is direct, we have that $`[𝔰,𝔯]=0`$ and therefore the rank of the matrix $`A\left(𝔤\right)`$ is the sum of the ranks of $`A\left(𝔰\right)`$ and $`A\left(𝔯\right)`$. Now one can ask what happens whenever we have a non-trivial Levi decomposition. Here no apparent relation between the number of invariants of the Levi factor and the radical and the number of invariants of the semidirect sum seems to exist. If we consider the simple algebra $`𝔰𝔩(2,)=\left\{X_1,X_2,X_3\right|[X_1,X_2]=2X_2,[X_1,X_3]=2X_3,[X_2,X_3]=X_1\}`$ and the representation $`R=D_{\frac{1}{2}}D_0`$, $`D_{\frac{1}{2}}`$ being the irreducible representation of highest weight $`\lambda =1`$, there are two choices of $`𝔯`$ such that $`𝔰𝔩(2,)\stackrel{}{}𝔯`$ is a six dimensional Lie algebra with non-trivial Levi decomposition: either the 3-dimensional Heisenberg Lie algebra $`𝔥_1=\left\{X_4,X_5,X_6\right|[X_4,X_5]=X_6\}`$ or the algebra $`A_{3,3}=\left\{X_4,X_5,X_6\right|[X_i,X_6]=X_i,i=4,5\}`$ (see  for this notation). It is a straightforward verification that $`𝒩\left(𝔥_1\right)=𝒩\left(A_{3,3}\right)=1`$, thus the formula, if existing, should give the same value for both cases. Now the Lie algebra $`𝔰𝔩(2,)\stackrel{}{}_R𝔥_1`$ admits two (polynomial) invariants $`I_1=x_6`$ and $`I_2=2x_1x_4x_5+4x_2x_3x_6+2x_2x_5^22x_3x_4^2+x_1^2x_6`$, while the algebra $`𝔰𝔩(2,)`$ $`\stackrel{}{}A_{3,3}`$ has no invariant. The conclusion is that the number of invariants will in general be not expressible in terms of its factors. This example points out another interesting fact: the existence of pairs $`(R,𝔯)`$ formed by representations $`R`$ of a semisimple Lie algebra $`𝔰`$ and a solvable Lie algebra $`𝔯`$ with structure of $`𝔰`$-module such that

$$𝒩\left(r\right)>0\mathrm{and}𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0.$$
(8)
This also shows that it is not sufficient to determine the invariants of solvable Lie algebras to have an overview of invariants of Lie algebras, implicitly assumed in some early works. Thus the Levi decomposition theorem does not simplify the determination of Casimir operators of Lie algebras, up to the case where we obtain a direct sum. The next step is naturally to try the classification of pairs $`(R,𝔯)`$ for fixed Levi factor $`𝔰`$ such that $`\left(8\right)`$ holds. This problem cannot be solved since the classification of solvable Lie algebras is probably not possible for dimensions $`n7`$ (the classification of six dimensional real Lie algebras contains some errors and some omissions). We must restrict ourselves to certain special cases that are of interest, either for matematical or physical reasons.

Table 1 shows the Lie algebras of dimension $`8`$ with non-trivial Levi decomposition and having no invariants. Due to the low dimenions, the only Levi factors that appear are the simple Lie algebras $`𝔰𝔬\left(3\right)`$ and $`𝔰𝔩(2,)`$. These algebras are of own interest, since they play an important role in multidimensional cosmologies .

We convene that the term $`D_J`$ denotes the real representation of $`𝔰𝔩(2,)`$ in its standard form, while $`R_4`$ denotes the four dimensional real irreducible representation of $`𝔰𝔬\left(3\right)`$ and $`D_0`$ denotes the trivial representation in both cases.

Although the general classification of these algebras seems not realizable, since it is based on the possibility of classifying the solvable Lie algebras, once an example is known we can deduce the following generic result:

###### Theorem 1

Let $`𝔰`$ be a semisimple Lie algebra and $`(R,𝔯)`$ be a pair formed by a representation of $`𝔰`$ and a solvable Lie algebra $`𝔯`$ such that $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$. Then, for any $`k1`$ there exists a Lie algebra $`𝔤_k`$ with Levi factor $`𝔰`$ and dimension $`n=dim\left(𝔰\stackrel{}{}_R𝔯\right)+2k`$ such that $`𝒩\left(𝔤\right)=0`$.

Proof. Consider the Lie algebra $`𝔤=𝔰\stackrel{}{}_R^{}𝔯^{}`$, where $`R^{}=R2kD_0`$ and the radical is $`𝔯^{}=𝔯k𝔯`$ 2, where $`𝔯_2`$ is the affine Lie algebra generated by $`Y,Z`$ and brackets $`[Y,Z]=Z.`$ The algebra $`𝔯^{}`$ is obviously a $`𝔰`$-module, and since $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$ and $`𝒩\left(𝔯_2\right)=0`$, the assertion follows from lemma 1.

###### Corollary 1

For any dimension $`n6`$ there exist Lie algebras $`𝔤`$ with non-trivial Levi decomposition such that $`𝒩\left(𝔤\right)=0`$.

This reduces the classification to the pairs $`(R,𝔯)`$ formed by a representation of $`𝔰`$ (this being fixed) and radicals $`𝔯`$ which are indecomposable, i.e., that do not decompose into a direct sum of ideals. Even for low dimensions like ten, it is far from being easy to find such pairs. As an example, consider the representation $`R=R_43D_0`$ of $`𝔰\mathfrak{0}\left(3\right)`$ and the radical $`𝔯`$ defined by the brackets

$$\begin{array}{c}[X_i,X_8]=X_i,\mathrm{\hspace{0.33em}4}i7\hfill \\ [X_4,X_9]=X_6,[X_5,X_9]=X_7,[X_6,X_9]=X_4\hfill \\ [X_7,X_9]=X_5,[X_9,X_{10}]=X_{10}\hfill \end{array}$$

over the basis $`\{X_4,..,X_{10}\}`$. This is the simplest non-decomposable solvable Lie algebra such that the semidirect sum $`𝔰𝔬\left(3\right)\stackrel{}{}_R𝔯`$ has no non-trivial invariants (for the considered representation). In fact more is true, namely the nonexistence of solvable Lie algebras $`𝔯`$ such that the action of the generators $`X𝔯[𝔯,𝔯]`$ over the nilradical $`[𝔯,𝔯]`$ is diagonal. This will happen also for other representations different from the one taken here.

## 4 Levi factors $`𝔰=𝔰𝔬\left(3\right),𝔰𝔩(2,)`$

Theorem 1 is a general result which holds for any Lie algebra satisfying $`(8)`$, and therefore non dependent on the particular Levi factor taken. Now an inspection of table 1 points out some interesting facts for the considered Levi factors $`𝔰=𝔰\mathfrak{0}\left(3\right)`$ and $`𝔰𝔩(2,)`$. In this section we analyze the semidirect sums $`𝔰\stackrel{}{}_R𝔯`$ with these Levi subalgebras in more detail. Through this section, and unless otherwise stated, the notation $`𝔰`$ will refer either to $`𝔰𝔩(2,)`$ or to $`𝔰𝔬\left(3\right)`$.

We saw in section 2 that in the computation of the invariants of the algebra $`𝔰𝔬\left(3\right)\stackrel{}{}_R𝔯`$ with $`R=ad𝔰𝔬\left(3\right)`$ and $`𝔯`$ the three dimensional abelian algebra $`3L_1`$ there was an invariant depending only on the variables associated to $`3L_1`$. We claimed that the existence of this invariant, coming from a special subsystem of $`\left(5\right)`$, was not casual. The next proposition shows that this property does not depend on the representation:

###### Theorem 2

Let $`R`$ be an irreducible representation of $`𝔰`$. Then the semidirect sum $`𝔰\stackrel{}{}_R𝔯`$ admits non-trivial invariants.
Moreover, if dim$`\left(𝔯\right)>dim\left(𝔰\right)`$, there exists a fundamental set of invariants formed by functions $`F_i`$ depending only on variables associated to elements of $`𝔯.`$

Proof. We prove it for $`𝔰=𝔰𝔩(2,)`$, the case of $`𝔰\mathfrak{0}\left(3\right)`$ being similar. At first, we only need to prove the result for odd dimensional representations $`D_j`$, since the remaining case follows at once from the odd dimensionality of the semidirect sum. By proposition 1, the radical $`𝔯`$ is abelian, and the maximal weight of $`R`$ is $`\lambda =2m4\left(m3\right).`$ Let $`\{X_1,X_2,X_3,..,X_{2m}\}`$ be a basis of $`𝔰\stackrel{}{}_R𝔯`$ such that $`\{X_1,X_2,X_3\}`$ is a basis of $`𝔰𝔩(2,)`$ (with $`[X_1,X_2]=2X_2,[X_1,X_3]=2X_3,[X_2,X_3]=X_1`$) and $`\{X_4,..,X_{2m}\}`$ a basis of the abelian radical $`𝔯`$. The system of PDEs giving the invariants of $`𝔰\stackrel{}{}_R𝔯`$ is:

$$\begin{array}{c}\widehat{X}_1F=\left(2x_2_{x_2}+2x_3_{x_3}_{i=0}^{2m4}\left(\lambda 2i\right)x_{4+i}_{x_{4+i}}\right)F=0\hfill \\ \widehat{X}_2F=\left(2x_2_{x_1}x_1_{x_3}_{i=1}^{2m4}\left(\lambda i+1\right)x_{3+i}_{x_{4+i}}\right)F=0\hfill \\ \widehat{X}_3F=\left(2x_3_{x_1}+x_1_{x_2}_{i=0}^{2m5}\left(i+1\right)x_{5+i}_{x_{4+i}}\right)F=0\hfill \\ \widehat{X}_{4+i}F=\left(\left(\lambda 2i\right)x_{4+i}_{x_1}\left(i+1\right)x_{5+i}_{x_2}+\left(\lambda i+1\right)x_{3+i}_{x_3}\right)F=0,\hfill \\ 0i2m4\hfill \end{array}\},$$
(9)
Observe that since $`𝔯`$ is abelian, the equations $`\left\{\widehat{X}_{4+i}F=0\right\}_{0i2m4}`$ do not involve the partial derivatives $`_{x_i}F`$ for $`4i2m.`$ This allows us to extract the subsystem:

$$\begin{array}{c}\widehat{X}_1^{}F=\left(_{i=0}^{2m4}\left(\lambda 2i\right)x_{4+i}_{x_{4+i}}\right)F=0\hfill \\ \widehat{X}_2^{}F=\left(_{i=1}^{2m4}\left(\lambda i+1\right)x_{3+i}_{x_{4+i}}\right)F=0\hfill \\ \widehat{X}_3^{}F=\left(_{i=0}^{2m5}\left(i+1\right)x_{5+i}_{x_{4+i}}\right)F=0\hfill \end{array}\},$$
(10)
and any solution is obviously an invariant of $`𝔰\stackrel{}{}_R𝔯`$. The question reduces to show that the system $`\left(10\right)`$ admits a non-trivial solution for any irreducible representation $`D_J`$. Observe that $`\left(10\right)`$ can be written as

$$\left(\begin{array}{ccccc}\lambda x_4& \left(\lambda 2\right)x_5& ..& \left(\lambda 2\right)x_{2m1}& \lambda x_{2m}\\ 0& \lambda x_4& ..& 2x_{2m2}& x_{2m1}\\ x_5& 2x_6& ..& \lambda x_{2m}& 0\end{array}\right)\left(\begin{array}{c}_{x_4}F\\ .\\ .\\ _{x_{2m}}F\end{array}\right)=0.$$
(11)
Now this matrix of coefficients has at most rank three (indeed three if $`m4`$ and rank one if $`m=3`$), so that $`\left(10\right)`$ has always a solution, which shows that $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)0`$. In particular the system $`\left(10\right)`$ gives the following number of solutions:

$$\begin{array}{c}1\mathrm{if}m=3\hfill \\ 2m6\mathrm{if}m4\hfill \end{array}\},$$
(12)
Observe that for $`m=3`$ the representation $`R`$ is the adjoint representation, and in this case we can find another invariant which depends also on the variables $`x_1,x_2,x_3`$. For $`m4`$ is it not difficult to see that $`_{x_i}F=0`$ for $`i=1,2,3`$, which shows that the $`\left(2m6\right)`$ functionally independent solutions of $`\left(10\right)`$ constitute a fundamental set of invariants for $`𝔰\stackrel{}{}_R𝔯`$.

###### Corollary 2

Let $`s=𝔰𝔩(2,),𝔰𝔬\left(3\right)`$. If the radical $`𝔯`$ is abelian then $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)0`$.

Proof. If the representation contains a copy of the trivial representation $`D_0`$ or $`dim𝔯`$ is even , we automatically have solutions of the corresponding system $`\left(2\right)`$. If $`R`$ does not contain a copy of $`D_0`$, we can again extract a subsystem from $`\left(2\right)`$, since the radical is abelian and its equations do not contain the partial derivatives corresponding to elements of $`𝔯`$. Now $`R`$ is a sum of irreducible representations, of which at least one summand $`R_0`$ must have even highest weight $`\lambda `$, in order to ensure the odd dimensionality of $`𝔯`$. Moreover, the variables involved in $`R_0`$ do not appear in the other summands of $`𝔯`$, which ensures that we can apply the preceding theorem. This shows that there exists a nontrivial of the subsystem corresponding to $`R_0`$, which, by the complete reducibility of $`R`$ and the abelianity of $`𝔯`$, is also an invariant of $`𝔰\stackrel{}{}_R𝔯`$.

The following example illustrates the procedure used in this proof: Let $`𝔰=𝔰𝔩(2,)`$ and consider the reducible representation $`D_1D_{\frac{1}{2}}`$. Suppose that the radical $`𝔯`$ is a five dimensional abelian Lie algebra. The invariants of $`𝔰\stackrel{}{}_R𝔯`$ are the solutions of the system:

$$\begin{array}{c}\left(2x_2_{x_2}+2x_3_{x_3}2x_4_{x_4}+2x_6_{x_6}x_7_{x_7}+x_8_{x_8}\right)F=0\hfill \\ \left(2x_2_{x_1}+x_1_{x_3}+2x_4_{x_5}+x_5_{x_6}+x_7_{x_8}\right)F=0\hfill \\ \left(2x_3_{x_1}x_1_{x_2}+x_5_{x_4}+2x_6_{x_5}+x_8_{x_7}\right)F=0\hfill \\ \left(2x_4_{x_1}x_5_{x_3}\right)F=0\hfill \\ \left(2x_4_{x_2}2x_6_{x_3}\right)F=0\hfill \\ \left(2x_6_{x_1}x_5_{x_2}\right)F=0\hfill \\ \left(x_7_{x_1}x_8_{x_3}\right)F=0\hfill \\ \left(x_8_{x_1}x_7_{x_2}\right)F=0\hfill \end{array}\},$$
(13)
We extract a subsystem from the first three equations:

$$\begin{array}{c}\left(2x_4_{x_4}+2x_6_{x_6}x_7_{x_7}+x_8_{x_8}\right)F=0\hfill \\ \left(2x_4_{x_5}+x_5_{x_6}+x_7_{x_8}\right)F=0\hfill \\ \left(x_5_{x_4}+2x_6_{x_5}+x_8_{x_7}\right)F=0\hfill \end{array}\},$$
(14)
and any solution of this system is an invariant of the algebra. $`\left(14\right)`$ can also be reduced to

$$\begin{array}{c}\left(2x_4_{x_4}+2x_6_{x_6}\right)F=0\hfill \\ \left(2x_4_{x_5}+x_5_{x_6}\right)F=0\hfill \\ \left(x_5_{x_4}+2x_6_{x_5}\right)F=0\hfill \end{array}\},$$
(15)
which is the subsystem corresponding to the adjoint representation. Clearly the polynomial $`I_1=4x_4x_6x_5^2`$ is a solution of $`\left(14\right)`$ and $`\left(15\right)`$, and therefore an invariant of the algebra. Since the other summand of $`R`$ is $`D_{\frac{1}{2}}`$, the other invariant will depend on all the variables $`x_4,..,x_8`$. We find $`I_2=x_4x_8^2x_5x_7x_8+x_6x_7^2`$. Thus $`I_1,I_2`$ form a fundamental set of invariants of $`𝔰\stackrel{}{}_R𝔯`$.

These two preceding results constitute an important restriction for a semidirect sum $`𝔰\stackrel{}{}_R𝔯`$ to satisfy $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$. Any representation in such an algebra must be reducible and contain a copy of the trivial representation $`D_0`$ (see table 1 and the examples in section 3).

###### Proposition 3

Let $`𝔰=𝔰𝔬\left(3\right),𝔰𝔩(2,)`$. If the radical $`𝔯`$ of $`𝔰\stackrel{}{}_R𝔯`$ has a one dimensional centre, then the representation $`R`$ describing the semidirect sum contains a copy of the trivial representation $`D_0`$. In particular, $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)0`$.

Proof. Let $`z`$ generate the centre $`Z\left(𝔯\right)`$ or $`𝔯`$. For any $`X𝔰`$ and $`Y𝔯`$ we have

$$[X,[Y,Z]]+[Z,[X,Y]]+[Y,[Z,X]]=0,$$

which shows that $`[𝔰,Z(𝔯)]Z\left(r\right)`$. Now

$$[X_2,[X_3,Z]]+[Z,[X_2,X_3]]+[X_3,[Z,X_2]]=0,$$

which shows that $`[X_1,Z]=0`$. Similarly it is proven that $`[X_2,Z]=[X_3,Z]=0`$, from which we deduce the existence of a copy of the trivial representation in the decomposition of $`R`$. Since the action of $`𝔰`$ over $`Z\left(𝔯\right)`$ is zero, we will obtain the monomial invariant $`I_1=z`$.

The results obtained so far for the Levi factors $`𝔰𝔬\left(3\right)`$ and $`𝔰𝔩(2,)`$ have important physical applications, like the classification of multidimensional spacetimes . In this frame, all ten dimensional real Lie algebras having a $`\left(7+d\right)`$-dimensional compact subalgebra have been determined. Of special interest are those which have non-trivial Levi decomposition, and which are the only candidates which could present the anomaly $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$. From the thirty classes found , only six are indecomposable, i.e., they do not decompose as a direct sum of lower dimensional Lie algebras. They have been listed in table 2, where the notation for the algebras is the same as in :

By theorem 2 and corollary 2 we see that, since the radical is always abelian, we will obtain non-trivial invariants. For these algebras, in contrast to the possible multidimensional cosmological models seen in section 3 and table 1, the existence of a compact subalgebra of dimension $`n7`$ implies that the algebra has non-vanishing invariants.

## 5 Application to radicals with a codimension one abelian ideal

In this section we analyze a special kind of radicals. We will suppose that $`𝔯`$ is a solvable non-nilpotent Lie algebra such that $`[𝔯,𝔯]`$ is a codimension one abelian ideal. We will see that such radicals always imply the existence of invariants, up to the lower dimensional cases. In particular the radicals found in table 1 for the 8 dimensional algebras $`𝔰\stackrel{}{}_R𝔯`$ will constitute the exception for radicals of this type.

###### Theorem 3

Suppose that $`R=R^{}2D_0`$, where $`R^{}`$ is a representation of $`𝔰`$. Then $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)>0`$.

Proof. Since $`R`$ contains at least two copies of the trivial representation, there exists an element $`Y[𝔯,𝔯]`$ such that $`[𝔰,Y]=0`$. Let $`T[𝔯,𝔯]`$ and $`[T,Y]=_{Y_i[𝔯,𝔯]}a_iY_i\left(a_i\right)`$. The equation $`\widehat{Y}F=0`$ of system $`\left(2\right)`$ has the form

$$\widehat{Y}F=\left(\underset{Y_i[𝔯,𝔯]}{}a_iy_i\right)_TF=0.$$
(16)
Now, if $`[T,Y]=0`$, the function $`F=y`$ is an invariant of $`𝔰\stackrel{}{}_R𝔯`$. If the bracket $`[T,Y]`$ is nonzero, then $`\left(16\right)`$ implies that $`_TF=0`$ for any invariant $`F`$. The complete reducibility of the representation $`R`$ (the ideal $`[𝔯,𝔯]`$ has codimension one in $`𝔯`$ and is an $`𝔰`$-module) implies that $`[𝔰,T]=0`$. The number $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)`$ is given by the difference of the dimension of $`𝔰\stackrel{}{}_R𝔯`$ and the rank of the matrix $`A\left(𝔰\stackrel{}{}_R𝔯\right)`$, which in this case has the form:

$$\left(\begin{array}{cccccccc}0& [X_1,X_2]& [X_1,X_3]& [X_1,Z_1]& \mathrm{}& [X_1,Z_r]& 0& 0\\ [X_2,X_1]& 0& [X_2,X_3]& [X_2,Z_1]& \mathrm{}& [X_2,Z_r]& 0& 0\\ [X_3,X_1]& [X_3,X_2]& 0& [X_3,Z_1]& \mathrm{}& [X_3,Z_r]& 0& 0\\ [Z_1,X_1]& [Z_1,X_2]& [Z_1,X_3]& 0& \mathrm{}& 0& 0& [T,Z_1]\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}& \mathrm{}\\ [Z_r,X_1]& [Z_r,X_2]& [Z_r,X_3]& 0& \mathrm{}& 0& 0& [T,Z_r]\\ 0& 0& 0& 0& \mathrm{}& 0& 0& [T,Y]\\ 0& 0& 0& [Z_1,T]& \mathrm{}& [Z_r,T]& [Y,T]& 0\end{array}\right),$$
(17)
where $`\{Z_1,..,Z_r,Y,T\}`$ is a basis of $`𝔯`$. Elementary methods show that the determinant of this matrix is the product of $`[T,Y]^2`$ and the following determinant:

$$det\left(\begin{array}{cccccc}0& [X_1,X_2]& [X_1,X_3]& [X_1,Z_1]& \mathrm{}& [X_1,Z_r]\\ [X_2,X_1]& 0& [X_2,X_3]& [X_2,Z_1]& \mathrm{}& [X_2,Z_r]\\ [X_3,X_1]& [X_3,X_2]& 0& [X_3,Z_1]& \mathrm{}& [X_3,Z_r]\\ [Z_1,X_1]& [Z_1,X_2]& [Z_1,X_3]& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}\\ [Z_r,X_1]& [Z_r,X_2]& [Z_r,X_3]& 0& \mathrm{}& 0\end{array}\right),$$
(18)
which must be zero, since the rank of the matrix in $`\left(18\right)`$ gives the number of invariants of the subalgebra $`𝔰\stackrel{}{}_{R2D_0}\left(rL_1\right)`$, which is non-maximal in virtue of theorem 1. Therefore the rank of $`A\left(𝔰\stackrel{}{}_R𝔯\right)`$ is less than its dimension, from which the existence of non-trivial invariants is ensured.

It should be remarked that if $`R`$ contains only one copy of $`D_0`$ or the codimension of $`[𝔯,𝔯]`$ is $`𝔯`$ is greater than one, then the conclusion is false, as can easily be extracted from table 1. We will finally see that radicals as considered in this section are only valid in low dimensions in order to obtain Lie algebras $`𝔰\stackrel{}{}_R𝔯`$ such that $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$.

###### Proposition 4

If $`dim\left(𝔯\right)7`$ then $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)0`$.

Proof. Like before, since $`[𝔯,𝔯]`$ is a codimension one $`𝔰`$-submodule of $`𝔯`$, the action of $`𝔰`$ on a generator $`T𝔯[𝔯,𝔯]`$ is zero. If $`dim\left(𝔯\right)=7`$, then $`dim\left(𝔰\stackrel{}{}_R𝔯\right)=10`$ and the matrix $`A\left(𝔰\stackrel{}{}_R𝔯\right)`$ has the form

$$\left(\begin{array}{ccccccc}0& [X_1,X_2]& [X_1,X_3]& [X_1,Z_1]& \mathrm{}& [X_1,Z_6]& 0\\ [X_2,X_1]& 0& [X_2,X_3]& [X_2,Z_1]& \mathrm{}& [X_2,Z_6]& 0\\ [X_3,X_1]& [X_3,X_2]& 0& [X_3,Z_1]& \mathrm{}& [X_3,Z_6]& 0\\ [Z_1,X_1]& [Z_1,X_2]& [Z_1,X_3]& 0& \mathrm{}& 0& [T,Z_1]\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& & \mathrm{}& \mathrm{}\\ [Z_6,X_1]& [Z_6,X_2]& [Z_6,X_3]& 0& \mathrm{}& 0& [T,Z_6]\\ 0& 0& 0& [Z_1,T]& \mathrm{}& [Z_6,T]& 0\end{array}\right).$$
(19)
It is routine to verify that the determinant of $`\left(19\right)`$ does not depend on the brackets, and that it is zero. Since for any radical $`𝔯`$ of the considered type such that $`dim\left(𝔯\right)7`$ the determinant of $`A\left(𝔰\stackrel{}{}_R𝔯\right)`$ is a linear combination of matrices of type $`\left(19\right)`$ and matrices like in $`\left(18\right)`$, it follows that $`detA\left(𝔰\stackrel{}{}_R𝔯\right)=0`$.

Observe that this result explains, in terms of the representation theory of $`𝔰𝔬(3)`$, why the ten dimensional Galilei algebra has two (Casimir) invariants depending only on the translations $`P_i`$ and the pure Galilean transformations $`K_i`$.

## 6 Conclusions

We have seen that for any dimension $`n6`$ there exist non-semisimple Lie algebras $`𝔰\stackrel{}{}_R𝔯`$ with non-trivial Levi factor $`𝔰`$ and such that $`𝒩\left(𝔰\stackrel{}{}_R𝔯\right)=0`$. This constitutes a proof that the Levi decomposition theorem  does not reduce the number of generalized Casimir invariants of $`𝔰\stackrel{}{}_R𝔯`$ to some combination of the numbers corresponding to the Levi factor $`𝔰`$ and the radical $`𝔯`$, but depends essentially on the pair $`(R,𝔯)`$ formed by the representation $`R`$ describing the semidirect sum and the radical.

For the rank one simple Lie algebras $`𝔰𝔬\left(3\right)`$ and $`𝔰𝔩(2,)`$ the number of invariants of a semidirect sum $`𝔰\stackrel{}{}_R𝔯`$ have been analized in some detail. In particular, the analysis undertaken has given a representation theoretic interpretation of the invariants obtained for the $`\left(3+1\right)`$ kinematical algebras like the Galilei algebra. The interest of these Levi factors is therefore justified not only by kinematical problems, but also by the extensions of Bianchi type-IX cosmology . Specially interesting are those admissible extensions which have no invariants. Therefore invariant quantities for these algebras should be searched using distribution theory . In particular, if the radical is abelian, we have proved that we will obtain solutions, some of them depending only on variables associated to elements of the radical. This confirms that the fact that the special affine algebras $`𝔰𝔞(n,)`$ have invariants (for being odd dimensional) is not an isolated case, but also the general pattern for those semidirect sums which are even dimensional. From the computed examples, it seems reasonable to expect that, whenever the radical $`𝔯`$ is a nilpotent Lie algebra, the number of invariants of a semidirect sum $`𝔰\stackrel{}{}_R𝔯`$ will be nonzero. However, for this case it is not sufficient to know which is the representation $`R`$ that describes the semidirect sum. We need more precise information on the structure of $`𝔫`$ (not merely the value of very general invariants like the nilpotence index), which impedes to establish a general result as for the abelian case.

The most important question that arises from our results is whether they can be extended to any semisimple Lie algebra of rank $`r2`$. At least for direct sums of $`𝔰𝔩(2,)`$ and $`𝔰𝔬\left(3\right)`$ this seems to hold. An example which is worth to be analyzed is the Schrödinger algebra $`𝔖`$ in $`\left(3+1\right)`$ dimensions . Over the basis $`\{J_i,K_i,P_i,P_0,C,D\}_{i=1,2,3}`$ this algebra is given by the brackets:

| $`[J_i,J_j]=\epsilon _{ijk}J_k,`$ | $`[J_i,K_j]=\epsilon _{ijk}K_k,`$ | $`[J_i,P_j]=\epsilon _{ijk}P_k,`$ | $`[K_i,P_0]=P_i,`$ |
| --- | --- | --- | --- |
| $`[P_i,D]=P_i,`$ | $`[D,K_j]=D_j,`$ | $`[D,P_0]=2P_0,`$ | $`[C,P_j]=K_j,`$ |
| $`[C,P_0]=D,`$ | $`[C,D]=2C.`$ |  |  |

where $`P_0`$ is the time translation, $`P_i`$ the space translations, $`J_i`$ the rotations and $`K_i`$ the pure Galilean transformations. It can easily be verified that the subalgebra $`𝔞`$ generated by $`\{K_i,P_i\}_{i=1,2,3}`$ is six dimensional and abelian, while $`\{P_0,C,D\}`$ generates a copy pf $`𝔰𝔩(2,)`$. Therefore we obtain the semisimple algebra $`𝔰𝔬\left(3\right)𝔰𝔩(2,)`$, and since $`𝔞`$ is an ideal, we have the Levi decomposition of $`𝔖`$ (by abuse of notation we can denote the corresponding representation by $`D_{\frac{1}{2}}ad𝔰𝔬(3)`$). If we extract a subsystem of the corresponding system $`\left(2\right)`$, as done in the proof of theorem 2, we obtain that $`𝔖`$ has a fourth order Casimir operator $`𝒫_4`$ depending only on the space translations and pure Galilei transformations:

$`𝒫_4`$ $`=`$ $`K_1^2\left(P_2^2+P_3^2\right)+K_2^2\left(P_1^2+P_3^2\right)+K_3^2\left(P_1^2+P_2^2\right)`$
$`2\left(P_1P_2K_1K_2+P_1P_3K_1K_3+P_2P_3K_2K_3\right)`$
For other simple Lie algebras a direct calculation of the rank of matrices $`A\left(𝔰\stackrel{}{}_R𝔯\right)`$ becomes a enormously difficult problem, and therefore the proofs of the generalization of the results obtained for rank one simple algebras, if they hold, must be approached by completely different means.

Finally, these results are of interest for the study of non-semisimple (maximal) regular subalgebras of simple Lie algebras. The example $`𝔰𝔩(2,)\stackrel{}{}_{D_{\frac{1}{2}}D_0}3L_1`$ of table 1 is a regular subalgebra of $`𝔰𝔩(3,)`$ and has no invariants. It would be important to obtain a detailed description of the non-semisimple maximal regular subalgebras of simple Lie algebras which do not have non-trivial invariants. This problem is of interest not only for symmetry breaking questions , but also for solving many fundamental problems which arise in rigidity and contraction theory , like the invariant theory of parabolic subalgebras of semisimple Lie algebras, the construction of contraction trees or the expansion problem .


text:
# Stability of shortest paths in complex networks with random edge weights

## I Introduction

A network is a new paradigm to study complex systems in many disciplines in science Strogatz01 ; AB02 . A complex system consists of a large number of interacting units, and the nature of the interaction determines equilibrium and dynamical properties of the system. Frequently the simplifying assumption is made that the units are arranged to form a simple pattern like a regular lattice or to interact with all others as in a mean-field theory. Recent studies, however, have revealed that the structure of complex systems is much richer Strogatz01 ; AB02 ; Watts98 . In general this structure is captured by a network which consists of vertices representing the units and edges connecting interacting vertex pairs.

Complex networks exhibit so-called small-world phenomena: vertices are highly clustered and the average separation between vertices grows slowly with the total number of vertices. Watts and Strogatz Watts98  introduced a small-world (SW) network as a model for these phenomena. It is obtained from a regular lattice with edges randomly rewired with probability $`p_r`$. Later it was found that some complex networks have a power-law distribution $`P_{deg.}(z)z^\gamma `$ of the degree $`z`$. The degree of a vertex is the number edges incident upon it. The class of networks with a power-law degree distribution is called the class of scale-free (SF) networks and is found in many areas including physics, computer science, biology, sociology, etc (we refer readers to Ref. AB02  for examples). The Barabási-Albert model BA99  generate a SF network ($`\gamma =3`$) growing via a preferential attachment rule BAsolution . Initially one starts with $`Z_0`$ vertices and introduces a new vertex at each step \[growing\]. It is then attached to $`Z`$ existing vertices, which are selected with probability linearly proportional to their degree \[preferential attachment\].

The discovery of the new classes of networks triggers extensive research. Order-disorder phase transitions Dorogovtsev ; Igloi ; KimBJ  and nonequilibrium phase transitions Pastor-Satorras  have been studied. Interestingly, the critical behavior is described well by mean-field theories and strongly depends on the degree distribution Igloi . Stability of complex networks has also been studied against a strong disorder such as a vertex dilution Albert00 ; Cohen00 ; Callaway00 . When the fraction of diluted vertices increases, a network may disintegrate into finite clusters undergoing a percolation-type transition. In this paper, we study the effect of weak disorder on the transport properties of networks.

The shortest path plays an important role for the transport within a network Goh01 ; Szabo02 . A path denotes a sequence of vertices, successive pairs of which are connected via edges. In general there exist many paths connecting two given vertices. The shortest path is the one with minimum path length among all the paths. The minimum path length is called a separation between the two vertices. Suppose one needs to send, e.g., a data packet from one computer to the other through the Internet. The shortest path provides an optimal path way since one would achieve a fastest transfer and save system resources. The shortest path is also important in studying an internal structure of a network Newman01 . The separation can be used as a measure of intimacy between vertices. The number of shortest paths that pass through a vertex is called the “betweenness” or “load” Newman01 ; Goh01 ; Szabo02 ; Goh02 . It reflects the importance of a vertex in mutual relationship or in transport. The load follows universal power-law distributions in scale-free networks Goh01 ; Szabo02 ; Goh02 .

Consider shortest paths from a vertex $`s`$, called the source, to all other vertices in a network. In an un-weighted network the length of a path is just the number of edges that it contains and shortest paths can simply be found using the “breadth-first search algorithm” Heiko . A sub-network consisting of all the shortest paths from $`s`$ is the spanning tree $`𝐓_s`$, which characterizes the optimal transport pattern. Figure 1 shows an example of a network and its spanning tree. It is convenient to represent the spanning tree by a diagram in which vertices are arranged hierarchically in the ascending order of their separation from the source. Then, the shortest path to each vertex is given by a directed path on $`𝐓_s`$. In general, the spanning tree does not have a tree structure. If there are degenerate shortest paths, $`𝐓_s`$ contains a loop. Some edges do not belong to $`𝐓_s`$. They do not contribute to any flow from/to $`s`$.

It has been assumed that all edges are equivalent having the same cost. However a real network would be described better with weighted edges. A weight of an edge may represent an access cost, a physical length, or an intimacy between vertices Newman01 ; Yook01 . For example, edges between scientists in scientific collaboration networks may have weights which depends on the number of coauthored papers Newman01 . In a weighted network, the path with the minimum number of edges is not necessarily an optimal one. In this work, we study disordered networks with randomly-weighted edges and investigate the effect of the disorder on the transport pattern. The regular network, the SW network Watts98 , and the Barabási-Albert SF network BA99  are considered. This paper is organized as follows: In Sec. II, we define the shortest path and the spanning tree in the disordered network. The disorder modifies the shape of the spanning tree. The response is described for the regular and SW networks in Sec. III and for the SF network in Sec. IV. We conclude in Sec. V.

## II Shortest paths and the spanning tree of disordered networks

Consider a disordered undirected network. An edge $`e`$ between two vertices $`u`$ and $`v`$ will be denoted as $`e=[u;v]=[v;u]`$. To each edge $`e`$ a non-negative weight $`c(e)`$ is assigned which is called the edge cost of $`e`$. Here we neglect all system-dependent details and assume that

$$c(e)=1+\eta (e),$$
(1)
where $`\eta (e)`$’s are random variables distributed independently with distribution $`(\eta )`$ ($`\eta (e)>1`$).

In a disordered network, a minimum-cost path plays the role of the shortest path in a pure ($`\eta =0`$) network. For given vertices $`u`$ and $`v`$, the minimum-cost path is given by the one with minimum path cost. The path cost is defined as the sum of all edge costs in the path. Without disorder ($`\eta (e)=0`$ for all $`e`$), the path cost is equivalent to the path length and the minimum-cost path is the same as the shortest path. Hereafter, the minimum-cost path will be called the shortest path, and the minimum cost is denoted as a distance. The path length of the shortest path is called the separation of the two vertices connected by it.

The spanning tree $`𝐓_s`$ of a disordered network can be found using the “Dijkstra algorithm” Heiko : Divide all vertices into two sets $`S`$ and its complement $`\overline{S}`$. Initially $`S=\{s\}`$ and the source is assigned to a distance label $`d(s)=0`$ and a separation label $`l(s)=0`$. At each iteration, one selects an optimal edge $`e^{}=[u^{};v^{}]`$ that has a minimum value of $`d(u)+c([u;v])`$ among all edges $`e=[u;v]`$ with $`uS`$ and $`v\overline{S}`$. Then, the vertex $`v^{}`$ gets the labels $`d(v^{})=d(u^{})+c([u^{};v^{}])`$ and $`l(v^{})=l(u^{})+1`$ and a predecessor label $`pred(v^{})=u^{}`$, and is shifted from $`\overline{S}`$ to $`S`$. The iteration terminates when the set $`\overline{S}`$ is empty. The shortest path to each vertex is then found by tracing the predecessor iteratively back to $`s`$. The distance and separation from $`s`$ to each vertex $`v`$ are given by $`d(v)`$ and $`l(v)`$, respectively. The average separation $`D_s=\frac{1}{N1}_{vs}l(v)`$ will be called a diameter.

In a homogeneous (e.g. regular) network and a weakly disordered network (e.g. SW network), all vertices are equivalent after an average over all disorder realizations. The diameter is independent of the source, $`D_s=D`$. In such cases we select the source $`s`$ arbitrarily. On the other hand, the SF network has a highly inhomogeneous structure. For the SF network, we select the hub which has the largest degree as the source $`s`$ since it plays the most important role in the transport Goh01 .

The spanning tree $`𝐓_s`$ of a disordered network will be different from $`𝐓_s^0`$ of the same network without disorder. If the disorder has a continuous distribution, with probability one all shortest paths are uniquely determined. Therefore, $`𝐓_s`$ has a tree structure, whereas $`𝐓_s^0`$ may have loops. Without loops, $`𝐓_s`$ consists of only $`(N1)`$ edges. Moreover, a vertex may have a shortest path that cannot be found in $`𝐓_s^0`$. For example, a path $`(s,v_1,v_9,v_8,v_6)`$ in a network in Fig. 1 may be a shortest path to $`v_6`$, so that $`𝐓_s`$ includes the edge $`[v_8;v_6]`$ which does not belong to $`𝐓_s^0`$. Such an edge of $`𝐓_s`$ that does not belong to $`𝐓_s^0`$ will be called an activated edge. The disorder activates it to play a role in the transport. The activated edge results in a drastic change in the shape of the spanning tree and increases the network diameter. We quantify the change by the density of disorder-induced activated edges $`\mathrm{\Phi }`$, which is given by the number of activated edges in $`𝐓_s`$ divided by $`(N1)`$, and the diameter-expansion coefficient $`\mathrm{{\rm Y}}=(D_sD_s^0)/D_s^0`$ with $`D_s`$ ($`D_s^0`$) the diameter with (without) disorder. The activated edge emerges as a result of competition between all paths connecting a vertex to the source. So networks with different structures respond differently. In the next section we will study the evolution of the spanning trees of the regular network and the small-world network Watts98 .

## III Small-world network

Consider a regular network consisting of $`N`$ vertices on a one-dimensional ring, each of which is connected up to $`Z`$th nearest neighbors with undirected edges. The small-world (SW) network is obtained by rewiring each edge with probability $`p_r`$ (see Ref. Watts98  for a detailed procedure). Except for extreme cases with $`p_r=0`$ (regular network) and $`p_r=1`$ (random network), the SW network displays the small-world phenomena Watts98 . We introduce a quenched disorder in edge costs as in Eq.(1) with the disorder distribution

$$(\eta )=\{\begin{array}{ccc}\frac{1}{2\epsilon }& & \text{for }\epsilon \eta <\epsilon \hfill \\ 0& & \text{otherwise.}\hfill \end{array}$$
(2)
Disorder strength is controlled by the parameter $`\epsilon `$ ($`<1`$). First we focus on the regular network ($`p_r=0`$) with $`Z=2`$, which gives us a lot of insights.

### III.1 Regular network ($`p_r=0`$) with $`Z=2`$

A regular network with $`Z=2`$ and $`N=18`$ is shown in Fig. 2(a). We consider the shortest path from the source $`s`$. Without disorder ($`\epsilon =0`$), the shortest path to $`b_n`$ is unique. On the other hand, there are $`n`$ degenerate shortest paths to $`a_n`$. So the spanning tree $`𝐓_s^0`$ has a ladder shape with diagonal rungs from $`b_n`$ to $`a_{n+1}`$ as shown in Fig. 2(b) comment . All edges $`\{[a_n;b_n]\}`$ are missing in $`𝐓_s^0`$.

With infinitesimal disorder, all loops break up in the spanning tree. So either $`[a_{n1};a_n]`$ or $`[b_{n1};a_n]`$ should be removed from $`𝐓_s`$. Consequently, $`𝐓_s`$ has a tree shape with a single branch for $`b_n`$’s and with sub-branches for $`a_n`$’s, cf., Fig. 2(c). This shape will be denoted as a type-B tree. The branching points are determined from recursion relations for the distances $`d(a_n)`$ and $`d(b_n)`$:

$`d(a_n)`$ $`=`$ $`\mathrm{min}\{d(a_{n1})+c([a_{n1};a_n]),`$ (3)
$`d(b_{n1})+c([b_{n1};a_n])\}`$
$`d(b_n)`$ $`=`$ $`d(b_{n1})+c([b_{n1};b_n]).`$ (4)
If $`d(a_{n1})+c([a_{n1};a_n])<d(b_{n1})+c([b_{n1};a_n])`$, the predecessor of $`a_n`$ is $`a_{n1}`$, otherwise the predecessor is $`b_{n1}`$. The recursion relation (3,4) holds if $`𝐓_s`$ has the type-B structure, which is valid as long as

$$d(a_n)+c([a_n;b_n])>d(b_n).$$
(5)
When it is violated, the predecessor of $`b_n`$ is $`a_n`$, $`[a_n;b_n]`$ becomes activated, and $`𝐓_s`$ changes its shape.

We introduce now a random walk interpretation of the recursion relation. Define $`X_A(n)d(a_n)n`$ and $`X_Bd(b_n)n`$ and insert it into Eq. (4). Using Eq. (1), one obtains $`X_B(n)=X_B(n1)+\eta ([b_{n1};b_n])`$; $`X_B(n)`$ can be interpreted as the coordinate of a one-dimensional random walker (walker $`B`$) after $`n`$ jumps. $`X_A(n)`$ is given by the minimum of $`X_A(n1)+\eta ([a_{n1};a_n])`$ and $`X_B(n1)+\eta ([b_{n1};a_n])`$. The first term also suggests that $`X_A(n)`$ can be interpreted as the coordinate of another random walker (walker $`A`$) after $`n`$ jumps. But its motion is constrained: After each jump, one has to compare the current position of $`A`$ \[the first term\] with the position of $`B`$ \[the second term$`X_B(n)+𝒪(\epsilon )`$\], and take the minimum as $`X_A(n)`$. Therefore, one may assume a hard-core repulsion between two walkers (the interaction range fluctuates by an amount of $`𝒪(\epsilon )`$). The inequality in Eq. (5) can be rewritten as $`X_B(n)X_A(n)<c([a_n;b_n])=1+𝒪(\epsilon )`$, which imposes a constraint on the random-walk motion.

It is convenient to introduce $`X_R(n)X_B(n)X_A(n)`$. It can be interpreted as the coordinate of a one-dimensional random walker $`R`$ in the presence of a fluctuating reflecting wall at $`X_R=𝒪(\epsilon )`$ and a fluctuating absorbing wall at $`X_R=1+𝒪(\epsilon )`$. At each time step, the walker $`R`$ performs a jump of size $`\eta ^{}`$ obeying the distribution $`_R(\eta ^{})𝑑\eta _1𝑑\eta _2(\eta _1)(\eta _2)\delta (\eta ^{}\eta _1+\eta _2)`$. Hereafter the boundary walls are assumed to be fixed at $`X_R=0`$ and $`X_R=1`$. The fluctuations do not modify the scaling behavior of $`\mathrm{\Phi }`$ and $`\mathrm{{\rm Y}}`$ with a possible change in the coefficient of the leading order term.

The random walker $`R`$ determines the shape of the spanning tree. If the walker does not touch either wall at $`X_R=0`$ or $`1`$ at a moment $`n`$, then the predecessor of $`a_n`$ ($`b_n`$) is $`a_{n1}`$ ($`b_{n1}`$). When it bounces at the reflecting wall in step $`n`$, $`a_n`$ has $`b_{n1}`$ as its predecessor, and the spanning tree has a new sub-branch, cf. $`a_3`$, $`a_4`$, and $`a_7`$ in Fig. 2(c). If it collides with the absorbing wall at step $`n_0`$, the inequality (5) is violated and $`b_{n_0}`$ has $`a_{n_0}`$ as predecessor instead of $`b_{n_01}`$ (see the spanning tree in Fig. 2(d) which has $`n_0=5`$).

The same random-walk mapping can be established after an edge $`[a_{n_0};b_{n_0}]`$ is activated. If one interprets $`s^{}=a_{n_0}`$ as a new source and re-defines $`a_n^{}=a_{n+n_0}`$ and $`b_n^{}=b_{n+n_01}`$, the distances from $`s^{}`$ to $`a_n^{}`$ and $`b_n^{}`$ satisfy the same recursion relation as in Eqs. (3) and (4) and the same constraint as in Eq. (5) with $`a(b)`$ replaced by $`b^{}(a^{})`$. Thus, the spanning tree consists of a single branch for $`a^{}`$’s and sub-branches for $`b^{}`$’s. This shape will be denoted as a type A, see Fig. 2(d). The creation of sub-branches and the switch into type-A tree are described by the same random-walk mapping used for the type-B segment.

Combining the mappings for type-A and type-B segments, the shape of the whole spanning tree can be determined by the the random walker $`R`$ in the presence of two hard-core walls at $`X_R=0`$ and $`1`$. Initially $`X_R(0)=0`$, and the wall at $`X_R=0(1)`$ is reflecting (absorbing). When the absorbing wall is at $`X_R=1(0)`$, the spanning tree has the type-B (type-A) shape. The sub-branch emerges when the random walker collides with the reflecting wall. When it collides with the absorbing wall, the role of the two walls are exchanged and the spanning tree switches its shape. It is interesting to note that the random walk with two types of boundary walls were used to find the exact ground states of one-dimensional random-field Ising-spin chain Schroder .

The shape of $`𝐓_s`$ is characterized by two length scales $`\xi _1`$ and $`\xi _2`$, see Fig. 2. The former characterizes the length of the sub-branch, and the latter the length of each type-A or type-B segment. They are given by the mean time scales between successive collisions with the reflecting wall and the absorbing wall, respectively. Then, $`\xi _1`$ can be approximated as the life time of the random walker $`R`$, being at the origin initially, in the presence of two absorbing walls at $`X=0`$ and $`X=1`$. And $`\xi _2`$ is given by the mean life time of the random walker $`R`$, being at the origin initially, in the presence of two absorbing walls at $`X=\pm 1`$. Such time scales are calculated in time-continuum limit in Appendix. Using the results in Eqs. (16) and (17) with $`a=\sigma `$ and $`\sigma ^2𝑑\eta ^{}_R(\eta ^{})\eta ^2=\frac{2}{3}\epsilon ^2`$, we obtain that $`\xi _1\sqrt{3/2}\epsilon ^1`$ and $`\xi _2=(3/2)\epsilon ^2`$. Note that the $`𝒪(\epsilon )`$ fluctuation of the walls does not change the scaling exponents, but may modify the coefficient of $`\xi _1`$.

One edge among $`Z`$ edges in a row is activated when a sub-branch appears only in the type-A segment (see Fig. 2(d)). So, the activated-edge density is inversely proportional to $`\xi _1`$:

$$\mathrm{\Phi }_{REG}(\epsilon )=\frac{1}{Z}\frac{Z1}{Z}\xi _1^1\frac{1}{\sqrt{24}}\epsilon ,$$
(6)
where $`Z=2`$ and $`(Z1)/Z`$ is the fraction of the type-A segments. When the spanning tree changes its shape at a certain vertex (cf. $`a_5`$ in Fig. 2(d)), its all descendent vertices increases their separation from $`s`$ by one. So, the diameter-expansion coefficient is inversely proportional to $`\xi _2`$:

$$\mathrm{{\rm Y}}_{REG}(\epsilon )=\frac{1}{Z}\xi _2^1=\frac{1}{3}\epsilon ^2.$$
(7)
The results are valid in the asymptotic limit where $`N\mathrm{max}[\xi _1,\xi _2]=\xi _2`$, which suggests the finite-size-scaling form $`\mathrm{\Phi }_{REG}(\epsilon ,N)=N^{1/2}𝒢_\mathrm{\Phi }(\epsilon N^{1/2})`$ and $`\mathrm{{\rm Y}}_{REG}(\epsilon ,N)=N^1𝒢_\mathrm{{\rm Y}}(\epsilon N^{1/2})`$. The scaling functions behave as $`𝒢_\mathrm{\Phi }(x)\chi _\mathrm{\Phi }x`$ and $`𝒢_\mathrm{{\rm Y}}(x)\chi _\mathrm{{\rm Y}}x^2`$ for $`x1`$. The scaling behavior is confirmed numerically. We compute both quantities for the regular network with $`Z=2`$ and $`N=10000,\mathrm{},80000`$, which were averaged over 200 samples. They are plotted in Fig. 3, where data collapse very well. From a least-square fitting we obtained that $`\chi _\mathrm{\Phi }0.24`$ and $`\chi _\mathrm{{\rm Y}}0.32`$, which is close to the analytic results (6) and (7).

The extension to the regular networks with $`Z>2`$ is straightforward. Vertices are labelled as $`(s,v_1^1,\mathrm{},v_1^Z`$, $`v_2^1,\mathrm{},v_2^Z,\mathrm{})`$ starting from the source $`s`$. Then, without disorder, the spanning tree $`𝐓_s^0`$ has a $`Z`$-leg ladder structure with diagonal rungs. Each leg ($`i=1,\mathrm{},Z`$) consists of vertices $`\{v_n^i\}`$. The predecessors of a node $`v_{n+1}^i`$ are $`v_n^j`$ with $`j=i,\mathrm{},Z`$. Edges $`\{[v_n^i;v_n^j]\}`$ with $`ij`$ do not belong to $`𝐓_s^0`$. When the disorder turns on, there emerge activated edges. Until one finds an activated edge, the distance to each vertex from the source satisfies recursion relations

$$d(v_n^i)=\underset{j=i,\mathrm{},Z}{\mathrm{min}}\{d(v_{n1}^j)+c([v_{n1}^j;v_n^i])\}.$$
(8)
The recursion relations are valid as long as

$$d(v_n^i)+c([v_n^i;v_n^j])>d(v_n^j)$$
(9)
for all $`ij`$. With the mapping $`X_i(n)=d(v_n^i)n`$, one can interpret $`X_i(n)`$ as a coordinate of a random walker $`A_i`$ after $`n`$ jumps (each jump has the distribution $`(\eta )`$). Then, Eq. (8) implies a hard-core interaction between walkers, so $`A_i`$ cannot overtake $`A_j`$’s with $`j>i`$. Effectively, it suffices to consider the hard-core interaction only between $`A_i`$ and $`A_{i+1}`$. If $`A_i`$ and $`A_{i+1}`$ collide at step $`n`$, then the vertex $`v_n^i`$ takes $`v_{n1}^{i+1}`$ as its predecessor. Otherwise, $`v_{n1}^i`$ is the predecessor of $`v_n^i`$. The constraint (9) implies that the relative distance between all walkers should be less than $`1+𝒪(\epsilon )`$, that is, $`|X_1X_Z|1`$. An activated edge $`[a_{n_0}^1;a_{n_0}^Z]`$ appears when this inequality is violated in the $`(n_0+1)`$th step. Then, we can use the same random-walk mapping after a cyclic permutation $`(A_1,\mathrm{},A_Z)(A_2,\mathrm{},A_Z,A_1)`$, which continues repeatedly. As in the case with $`Z=2`$, the shape of the spanning tree is characterized by the length scale $`\xi _1`$, the mean time scale for a collision between adjacent walkers, and $`\xi _2`$, the mean time scale for violating the constraint $`|X_1X_Z|1`$. The time scales are approximately equal to those for the two-random-walker problem with a constraint $`|X_1X_2|2/Z`$. With this approximation, one gets $`\xi _1(Z\epsilon )^1`$ and $`\xi _2(Z\epsilon )^2`$. Using $`\mathrm{\Phi }_{REG}=\frac{Z1}{Z^2\xi _1}`$ and $`\mathrm{{\rm Y}}_{REG}=\frac{1}{Z\xi _2}`$, we finally obtain $`\mathrm{\Phi }_{REG}\chi _\mathrm{\Phi }\epsilon ^1`$ and $`\mathrm{{\rm Y}}_{REG}\chi _\mathrm{{\rm Y}}\epsilon ^2`$ with $`Z`$-dependent coefficients $`\chi _\mathrm{\Phi }(1\frac{1}{Z})`$ and $`\chi _\mathrm{{\rm Y}}Z`$. The scaling exponents are universal for all $`Z`$. We determine the coefficients of $`\epsilon `$ and $`\epsilon ^2`$ for $`\mathrm{\Phi }_{REG}`$ and $`\mathrm{{\rm Y}}_{REG}`$, respectively, numerically and plot them as a function of $`Z`$ in the insets of Fig. 3. One sees that $`\chi _\mathrm{\Phi }(11/Z)`$ and $`\chi _\mathrm{{\rm Y}}Z`$, as estimated above.

We conclude that quenched disorder is a relevant perturbation to the spanning tree of the regular network. Using the random-walk mapping, we have shown that a finite fraction of edges in the spanning tree are modified at nonzero disorder strength. This fraction is linearly proportional to the disorder strength, $`\mathrm{\Phi }_{REG}\epsilon `$. We have also shown that the diameter-expansion coefficient is proportional to the square of the disorder strength, $`\mathrm{{\rm Y}}_{REG}\epsilon ^2`$.

### III.2 Small-world network

Next we study the effect of the quenched disorder in the SW network. Figure 4 shows an example of a SW network and its spanning tree $`𝐓_s^0`$ without disorder ($`\epsilon =0`$). The random rewiring of edges randomizes $`𝐓_s^0`$, too, which is not suited for an exact description. Therefore we study $`\mathrm{\Phi }_{SW}`$ and $`\mathrm{{\rm Y}}_{SW}`$ first numerically. We calculate $`\mathrm{\Phi }_{SW}`$ in SW networks with $`Z=4`$ and $`p_r=0.2`$ and compare it with $`\mathrm{\Phi }_{REG}`$ in Fig. 5. $`\mathrm{\Phi }_{SW}`$ shows two noticeable features: (i) At small $`\epsilon `$, $`\mathrm{\Phi }_{SW}`$ appears to display a threshold behavior at a nonzero value of $`\epsilon `$. (ii) $`\mathrm{\Phi }_{SW}`$ has a strong size dependence. $`\mathrm{\Phi }_{SW}`$ does not approach an asymptotic saturation at any value of $`\epsilon `$ and $`N`$ considered. The same feature is commonly observed at other values of $`Z`$ and $`p_r`$, and also for $`\mathrm{{\rm Y}}_{SW}`$. In what follows we describe the response of the spanning tree with an effective random walk process and we will show that the origin of the apparent threshold behavior is the presence of a well-defined $`\epsilon `$-dependent crossover size in the network.

All edges that connect vertices at the same hierarchy level in $`𝐓_s^0`$, as represented by dashed lines in the example in Fig. 4, are candidates for an activated edge. Focus on a pair of vertices $`a`$ and $`b`$ with $`[a;b]𝐓_s^0`$ in Fig. 4. They are descendants of a common ancestor $`s^{}`$. The edge $`[a;b]`$ belongs to $`𝐓_s`$ if a difference between costs of the two paths (denoted by thick lines) from $`s^{}`$ to $`a`$ and to $`b`$ is larger than the edge cost $`c([a;b])=1+\eta ([a;b])=1+𝒪(\epsilon )`$, where $`𝒪(\epsilon )`$ term can be neglected. The probability with which this happens will be denoted as $`P_{act.}([a;b])`$. Let $`l(a,b)`$ be the separation of $`a`$ and $`b`$ to their common ancestor $`s^{}`$ in $`𝐓_s^0`$. Using Eq. (1), the path costs are given by a sum of $`l(a,b)`$ independent random variables $`\eta `$’s (plus $`l(a,b)`$). So, with the common term $`l(a,b)`$ discarded, they can be interpreted as coordinates of two one-dimensional random walkers after $`l(a,b)`$ jumps. Each jump follows the distribution $`(\eta )`$. $`P_{act.}([a;b])`$ is then given by the probability that the distance between two random walkers is larger than $`1`$ after $`l`$ jumps. Or equivalently, it is given by the probability that a random walker deviates from a starting position by a distance larger than $`1`$ after $`l`$ jumps, where each jump follows a distribution $`_R(\eta ^{})=𝑑\eta _1\eta _2(\eta _1)(\eta _2)\delta (\eta ^{}\eta _1+\eta _2)`$. The probability distribution of the random walker after $`l`$ steps is given by $`P_{R.W.}(x,l)=(2\pi \sigma ^2l)^{1/2}e^{x^2/(2\sigma ^2l)}`$ with $`\sigma ^2𝑑\eta ^{}\eta ^2_R(\eta ^{})=2\epsilon ^2/3`$. Therefore, one obtains

$$P_{act.}([a;b])=\mathrm{erfc}\left(\frac{\sqrt{3}}{2\epsilon \sqrt{l(a,b)}}\right),$$
(10)
where $`\mathrm{erfc}(x)\frac{2}{\sqrt{\pi }}_x^{\mathrm{}}e^{x^2}`$ is the complementary error function.

Now we make a mean-field-type approximation that each edge $`e𝐓_s^0`$ may be an activated edge independently. That is only true for the edges $`\{e_i=[a_i;b_i]𝐓_s^0\}`$ if the paths from $`a_i`$ and $`b_i`$ to their common ancestor do not overlap for different $`e_i`$’s. Otherwise, two probabilities $`P_{act.}(e)`$ and $`P_{act.}(e^{})`$ are not independent. If $`e`$ is activated, it modifies the shape of the spanning tree and hence $`P_{act.}(e^{})`$, and vice versa. The approximation would give the correct scaling behavior if the spanning tree would be random and self-averaging. In the mean-field scheme, the activated edge density is proportional to the probability in Eq. (10) with $`l(a,b)`$ replaced by the average value, i.e., the diameter of the network $`D_s\mathrm{ln}N`$ Newman00 :

$$\mathrm{\Phi }_{SW}(N,\epsilon )\alpha _1\mathrm{erfc}\left(\frac{\alpha _2}{\epsilon \sqrt{\mathrm{ln}N}}\right)$$
(11)
with constants $`\alpha _{1,2}`$ being independent of $`\epsilon `$ and $`N`$.

The scaling function behaves as $`\mathrm{erfc}(x)1\frac{2}{\sqrt{\pi }}x`$ for small $`x`$. So, in the asymptotic limit where $`NN_ce^{\alpha _2^2\epsilon ^2}`$, the activated edge density is a constant \[$`\mathrm{\Phi }_{SW}\alpha _1`$\] in the infinite ($`N\mathrm{}`$) network for all values of $`\epsilon 0`$. Therefore, the spanning tree of the SW network undergoes a discontinuous transition at $`\epsilon =\epsilon _c=0`$ in the asymptotic limit, which is contrasted to the continuous transition in the regular network.

The asymptotic behavior sets in when the network size is bigger than the crossover size $`N_ce^{\alpha _2^2\epsilon ^2}`$. It grows very fast as $`\epsilon `$ goes to zero. For instance, when $`\epsilon =0.1`$ with $`\alpha _21`$, only SW networks with $`NN_c10^{43}`$ are in the asymptotic region, which is improbable in any real networks. So, the behavior in the non-asymptotic regime is more important in practice. Using $`\mathrm{erfc}(x)\frac{1}{\sqrt{\pi }x}e^{x^2}`$ for $`x1`$, we obtain that

$$\mathrm{\Phi }_{SW}\frac{\alpha _1\epsilon \sqrt{\mathrm{ln}N}}{\alpha _2\sqrt{\pi }}\mathrm{exp}\left[\frac{\alpha _2^2}{\epsilon ^2\mathrm{ln}N}\right]$$
(12)
for $`NN_c`$. It has an essential singularity at $`\epsilon =0`$ and increases continuously and extremely slowly. Therefore, the spanning tree of finite SW networks undergoes an infinite-order transition at $`\epsilon =0`$.

Numerical data are in good agreement with the mean-field results. In Fig. 6, we plot $`\mathrm{\Phi }_{SW}`$ as a function of the scaling variable $`\epsilon \sqrt{\mathrm{ln}N}`$. Data at different values of $`N`$ collapse onto a single curve, which supports the scaling form in Eq. (11). In the inset, we plot $`\mathrm{\Phi }_{SW}`$ at given values of $`\epsilon `$ against $`1/\mathrm{ln}N`$ for $`N=100,\mathrm{},800000`$ in the semilog scale. We observe that the data align along straight lines, which support the result in Eq. (12). Extrapolating the straight lines to the limit $`\mathrm{ln}N\mathrm{}`$, we obtained that $`\mathrm{\Phi }_{SW}`$’s converge to $`\alpha _10.25`$.

In the regular network, an activated edge may or may not increase the separation of vertices from the source, which leads to the different scaling behaviors of $`\mathrm{\Phi }_{REG}\epsilon `$ and $`\mathrm{{\rm Y}}_{REG}\epsilon ^2`$. However, in the SW network, all activated edges considered above increase the separation. So $`\mathrm{{\rm Y}}_{SW}`$ shows the same scaling behavior as $`\mathrm{\Phi }_{SW}`$, which we also confirmed numerically.

## IV Barabási-Albert Scale-free network

In this section we study the response of the spanning tree of a SF network to the quenched disorder. We consider the Barabási-Albert (BA) network with the degree-distribution exponent $`\gamma =3`$ BA99 . Among all vertices, the hub which has the largest degree plays an important role in the SF network Goh01 . So we consider the spanning tree of the BA network with the hub as the source. $`\mathrm{\Phi }_{SF}`$ is measured for the BA network with $`Z_0=Z=4`$, and compared with $`\mathrm{\Phi }_{REG}`$ and $`\mathrm{\Phi }_{SW}`$ in Fig. 5. $`\mathrm{\Phi }_{SF}`$ behaves similarly to $`\mathrm{\Phi }_{SW}`$.

Though the SF network is different from the SW network in many aspects, its spanning tree also has a random structure. Thus, we expect that the scaling behavior of $`\mathrm{\Phi }_{SF}`$ can be explained with the same mean-field-type approximation as $`\mathrm{\Phi }_{SW}`$. Under the approximation, each edge that does not belong to $`𝐓_s^0`$ may be activated independently. Then, the mean density of the activated edges is obtained by replacing $`l(a,b)`$ in Eq. (10) with the diameter of the network. Recently, it was found that the scale-free network is ultra small in diameter Cohen . In particular, for $`\gamma =3`$ ($`\gamma `$: the degree-distribution exponent) the diameter scales as $`D\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N`$, i.e., with a double logarithmic correction to the SW scaling $`D\mathrm{ln}N`$. It leads us to conclude that

$$\mathrm{\Phi }_{SF}=\alpha _1^{}\mathrm{erfc}\left(\frac{\alpha _2^{}}{\epsilon \sqrt{\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N}}\right)$$
(13)
with constants $`\alpha _1^{}`$ and $`\alpha _2^{}`$.

This scaling form is indeed supported by our numerical data. In Fig. 7, we plot $`\mathrm{\Phi }_{SF}`$ for the BA network with $`Z=Z_0=2`$ as a function of the scaling variable $`\epsilon \sqrt{\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N}`$, and obtain a good data collapse. Though the double-logarithmic correction is very weak, the data do not collapse at all without it. We note that the data also scale well with a scaling variable $`\epsilon (\mathrm{ln}N)^{1/4}`$, however, we presume that this is accidental since the ratio between $`(\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N)`$ and $`(\mathrm{ln}N)^{1/2}`$ remains almost constant up to $`N=800000`$. The inset in Fig. 7 shows that $`\mathrm{ln}\mathrm{\Phi }_{SF}`$ is linear in $`1/(\epsilon ^2\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N)`$. It implies that the scaling function has the essential singularity as in Eq. (12). The same scaling behavior is observed universally for other values of $`Z=Z_0=3`$ and $`4`$, and also for $`\mathrm{{\rm Y}}_{SF}`$.

The SF network shares the same scaling behavior with the SW network with the scaling variable $`\epsilon [\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N]^{1/2}`$. The spanning tree of the SF network undergoes a discontinuous transition in the asymptotic regime: $`\mathrm{\Phi }_{SF}`$ and $`\mathrm{{\rm Y}}_{SF}`$ in the infinite SF networks jump from zero at $`\epsilon =0`$ to finite values as the disorder turns on. The asymptotic behavior sets in only when $`NN_c\mathrm{exp}[\alpha |\mathrm{ln}\epsilon |\epsilon ^2]`$ with a positive constant $`\alpha `$. In the transient regime with $`NN_c`$, the spanning tree of the SF networks undergoes a continuous infinite-order transition with the essential singularity in $`\mathrm{\Phi }_{SF}`$ and $`\mathrm{{\rm Y}}_{SF}`$ at $`\epsilon =0`$. Note that the crossover size $`N_c`$ of the SF network grows much faster than that of the SW network. Therefore we conclude that the scale-free network has the most stable transport pattern.

## V Conclusion

In a network the shortest paths between vertices play an important role. The optimal transport pattern from/to a vertex $`s`$ is characterized by the spanning tree $`𝐓_s`$, a set of all shortest paths. We have investigated the response of the spanning tree of complex networks to a quenched randomness in edge costs, and found that quenched disorder is a relevant perturbation. As the disorder turns on, the spanning tree evolves with a finite fraction of edges modified and the network diameter expands.

For the regular network, the shape of the spanning tree can be described exactly using the random-walk mapping. The spanning tree undergoes a continuous transition with $`\mathrm{\Phi }_{REG}\epsilon `$ and $`\mathrm{{\rm Y}}_{REG}\epsilon ^2`$ with $`\epsilon `$ the disorder strength. For the SW and SF networks, we obtain the scaling form $`\mathrm{\Phi }(\epsilon ,N)=\stackrel{~}{\mathrm{\Phi }}(\epsilon D^{1/2})`$ where $`D`$ is the network diameter. It scales as $`D\mathrm{ln}N`$ in the SW network and $`D\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N`$ in the BA network Cohen . The diameter-expansion coefficient satisfies the same scaling form. The scaling function approaches a constant as its argument $`x=\epsilon D^{1/2}\mathrm{}`$. It has the essential singularity, $`\stackrel{~}{\mathrm{\Phi }}(x)\mathrm{exp}[\alpha x^2]`$ with a positive constant $`\alpha `$, as $`x0`$. Therefore, $`\mathrm{\Phi }`$ and $`\mathrm{{\rm Y}}`$ have a discontinuous jump at $`\epsilon =0`$ in infinite-size SW and SF networks. It shows that the SW network and the SF network are more affected by the quenched disorder than the regular network. However, the asymptotic scaling behavior emerges only when the network size is larger than the crossover size $`N_c`$. It grows as $`N_c\mathrm{exp}[\alpha \epsilon ^2]`$ for the SW network and $`N_c\mathrm{exp}[\alpha |\mathrm{ln}\epsilon |\epsilon ^2]`$ for the BA network with a positive constant $`\alpha `$ as $`\epsilon `$ vanishes. Since the crossover size grows extremely fast as $`\epsilon `$ goes to zero, the behavior in the transient regime with $`NN_c`$ is more important in practice. In contrast to the discontinuous jump when $`NN_c`$, $`\mathrm{\Phi }`$ at $`NN_c`$ grows continuously and very slowly with the essential singularity at $`\epsilon =0`$. Numerically we obtained that $`\mathrm{\Phi }<10^7`$ for $`\epsilon 0.1`$ up to $`N=800000`$. Therefore, we conclude that the transport pattern in finite SW and SF networks is extremely robust against the quenched disorder. In particular, the SF network is most stable.

The interesting scaling behavior of the SW and SF networks can be explained within a mean-field picture. $`\mathrm{\Phi }`$ and $`\mathrm{{\rm Y}}`$ are proportional to the probability that a displacement of a random walker with diffusion constant $`𝒪(\epsilon ^2)`$ is larger than 1 after $`D`$, the network diameter, time steps. The crossover size is determined from the condition $`\epsilon ^2D(N_c)1`$, and the spanning tree is very stable against the disorder as long as $`NN_c`$. So, the exponential divergence of the crossover size $`N_c`$ and hence the extreme stability of the spanning tree are the direct consequence of the small-worldness, i.e., $`D(N)\mathrm{ln}N`$ Newman00  and $`D(N)\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N`$ Cohen , for the small-world and the scale-free network, respectively. The diameter of the SF networks with $`2<\gamma <3`$ scales as $`D(N)\mathrm{ln}\mathrm{ln}N`$ Cohen  and within the mean-field picture one expects the crossover size of these networks to scale like $`N_c\mathrm{exp}[\mathrm{exp}[\alpha \epsilon ^2]]`$.

Another consequence of the disorder is that the shortest path from one vertex to the other becomes unique. Recently, it has been reported that the load distribution in SF networks follows a power-law distribution with the universal load-distribution exponent $`\eta 2.2`$ or $`2.0`$ Goh01 ; Goh02 . Phenomenologically, the SF networks with degenerate shortest paths seem to have $`\eta 2.2`$ Goh01 ; Goh02 , whereas those without or only a few degenerate shortest paths seem to have $`\eta 2.0`$ Goh02 ; Szabo02 . It would be interesting to study the load distribution in the disordered SF networks, which will shed light on the role of the degeneracy on the universality of the load distribution. This work is in progress.

###### Acknowledgements.

We would like to thank B. Kahng for useful discussions. This work has been financially supported by the Deutsche Forschungsgemeinschaft (DFG).

## Appendix A Random walk in the presence of absorbing wall

Consider a discrete-time random walk in one dimension in the presence of absorbing walls at $`x=0`$ and $`x=L`$. The walker is killed upon a collision with the absorbing walls. Initially it is at $`x=a`$ and its position after $`t`$ steps is given by $`x(t)=a+_{i=1}^tx_i`$ with random variables $`x_i`$’s with $`x_i=0`$ and $`x_i^2=\sigma ^2`$. In the time-continuum limit, the probability density $`P(x,t)`$ satisfies a diffusion equation $`P/t=\mu ^2P/x^2`$ with a diffusion constant $`\mu =\sigma ^2/2`$. The absorbing walls impose boundary conditions $`P(0,t)=P(L,t)=0`$, and the initial condition implies $`P(x,0)=\delta (xa)`$. In the Fourier series expansion $`P(x,t)=_{n=1}^{\mathrm{}}p_n(t)\mathrm{sin}\frac{n\pi x}{L}`$, the diffusion equation becomes $`dp_n/dt=(\mu \pi ^2/L^2)n^2p_n`$ with the solution $`p_n(t)=p_n(0)e^{(\pi ^2\mu /L^2)n^2t}`$. The coefficients $`p_n(0)`$ are determined from the initial condition. Using the Fourier series expansion of the delta function, we obtain that

$$P(x,t)=\frac{2}{L}\underset{n=1}{\overset{\mathrm{}}{}}\left(\mathrm{sin}\frac{n\pi a}{L}\right)\left(\mathrm{sin}\frac{n\pi x}{L}\right)e^{\mu ^{}n^2t}.$$
(14)
The survival probability $`S(t)`$ of the random walker is given by the spatial integral of the probability density:

$$S(t)=\frac{4}{\pi }\underset{n=0}{\overset{\mathrm{}}{}}\frac{\mathrm{sin}((2n+1)\pi a/L)}{2n+1}e^{(\pi ^2\mu /L^2)(2n+1)^2t}.$$

Then the death probability during $`t`$ and $`t+dt`$ is given by $`S(t)S(t+dt)D(t)dt`$ with $`D(t)\frac{dS}{dt}`$. Therefore the mean life time of the walker is given as $`\tau =_0^{\mathrm{}}𝑑ttD(t)=_0^{\mathrm{}}𝑑tS(t)`$. Using (14), one obtains that

$$\tau =\frac{8L^2}{\sigma ^2\pi ^3}\underset{n=0}{\overset{\mathrm{}}{}}\frac{\mathrm{sin}((2n+1)\pi a/L)}{(2n+1)^3}.$$
(15)
It becomes simpler in a special case. When $`a=L/2`$, $`\tau =\frac{8L^2}{\sigma ^2\pi ^3}\beta (3)`$ with $`\beta (s)_{n=0}^{\mathrm{}}(1)^n(2n+1)^s`$. Using $`\beta (3)=\pi ^3/32`$ Abramowitz , one obtains that

$$\tau =\frac{L^2}{4\sigma ^2}.$$
(16)
When $`aL`$, one can use an expansion $`\mathrm{sin}(n\pi a/A)n\pi a/A`$, which yields that $`\tau =\frac{8aL}{\sigma ^2\pi ^2}_{\mathrm{odd}n}n^2`$. Using that $`_{\mathrm{odd}n}n^2=\frac{3}{4}\zeta (2)=\frac{\pi ^2}{8}`$ with Riemann zeta function $`\zeta (s)_{n=1}^{\mathrm{}}n^s`$ Abramowitz , one obtains

$$\tau =\frac{aL}{\sigma ^2}.$$
(17)


text:
# Criterion for local distinguishability of arbitrary bipartite orthogonal states

## Abstract

In this paper we present a necessary and sufficient condition of distinguishability of bipartite quantum states. It is shown that the operators to reliably distinguish states need only rounds of projective measurements and classical comunication. We also present a necessary condition of distinguishability of bipartite quantum states which is simple and general. With this condition one can get many cases of indistinguishability. The conclusions may be useful in understanding the essence of nonlocality and calculating the distillable entanglement and the bound of distillable entanglement.

One of the interesting features of non-locality in quantum mechanics is that a set of orthogonal quantum states cannot be distinguished if only a single copy of these states is provided and only local operations and classical communication (LOCC) are allowed, in general. The procedure of distinguishing quantum states locally is: Alice and Bob hold a part of a quantum system, which occupies one of $`m`$ possible orthogonal states $`|\mathrm{\Psi }_1,|\mathrm{\Psi }_2,\mathrm{},|\mathrm{\Psi }_i,\mathrm{},|\mathrm{\Psi }_m`$. Alice and Bob know the precise form of these states, but don’t know which of these possible states they actually hold. To distinguish these possible states they will perform some operations locally: Alice (or Bob) first measures her part. Then she tell the Bob her measurement result, according to which Bob measure his part. With the measurement results they can exclude some possibilities of the system. Briefly speaking, the procedure of distinguishing quantum states locally is to exclude all or some possibilities by measurement on the system. Many authors have considered some schemes for distinguishing locally between a set of quantum states , both inseparable and separable. Bennett et al showed that some orthogonal product states cannot be distinguished by LOCC. Walgate et al showed that any two states can be distinguished by LOCC. For two-qubit systems (or $`22`$ systems), any three of the four Bell states:

$`|A_1`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|00+|11)`$ (1)
$`|A_2`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|00|11)`$ (2)
$`|A_3`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|01+|10)`$ (3)
$`|A_4`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2}}}(|01|10)`$ (4)
cannot be distinguished by LOCC if only a single copy is provided. The distinguishability of quantum states has some close connections with distillable entanglement and the information transformation. On one hand, using the upper bound of distillable entanglement, relative entropy entanglement and logarithmic negativity, the authors in Ref  proved that some states are indistinguishable. On the other hand, using the rules on distinguishability one can discuss the distillable entanglement. So the further analysis for distinguishability is meaningful. In this paper, we will give a necessary and sufficient condition of distinguishability of bipartite quantum states. It is shown that the operators to reliably distinguish states need only rounds of projective measurements and classical comunication. We also present a necessary condition of distinguishability of bipartite quantum states which is simple and general. With this condition one can get many cases of indistinguishability.

Consider $`m`$ possible orthogonal states shared between Alice and Bob. Any protocol to distinguish the $`m`$ possible orthogonal states can be conceived as successive rounds of measurement and communication by Alice and Bob. Let us suppose Alice is the first person to perform a measurement (Alice goes first ), and the first round measurement by Alice can be represented by operators $`\left\{A_{1_j}\right\}`$, where $`A_{1_j}^+A_{1_j}`$ is known as a POVM element realized by Alice , and $`_jA_{1_j}^+A_{1_j}=I.`$ If the outcome $`1_j`$ occurs, then the given $`|\mathrm{\Psi }`$ becomes $`A_{1_j}|\mathrm{\Psi },`$ up to normalization. After communicating the result of Alice’s measurement to Bob, he carries out a measurement and obtain outcome $`1_k`$. The given possible state $`|\mathrm{\Psi }`$ becomes $`A_{1_j}B_{1_k}(1_j)|\mathrm{\Psi }`$, where $`B_{1_k}(1_j)`$ is an arbitrary measurement operator of Bob which depend on the outcome $`1_j`$ of Alice’s measurement. After N rounds of measurements and communication, there are many possible outcomes which corresponding to many measurement operators acting on the Alice and Bob’s Hilbert space. Each of these operators is a product of the N sequential and relative operators $`A_{1_j}B_{1_k}(1_j)A_{2_j}(1_j,1_k)B_{2_k}(1_j,1_k,2_j)\mathrm{}A_{N_j}(1_j,1_k,\mathrm{},(N1)_j)B_{N_k}(1_j,1_k,\mathrm{},(N1)_j,N_k)`$ carried out by Alice and Bob. We denote these operators as $`\left\{A_iB_i\right\},`$ where, $`A_i`$ $`B_i`$ denotes one of these operators, which represent the effects of the N measurements and communication. If the outcome $`i`$ occurs, the given $`|\mathrm{\Psi }`$ becomes:

$$A_iB_i|\mathrm{\Psi }$$
(5)
The probability $`p_i`$ Alice and Bob gain outcome $`i`$ is

$$p_i=\mathrm{\Psi }\left|A_i^+B_i^+A_iB_i\right|\mathrm{\Psi },$$
(6)
and

$$\underset{i}{}A_i^+B_i^+A_iB_i=I$$
(7)
Suppose we define:

$$E_i=A_i^+B_i^+A_iB_i,$$
(8)
then $`E_i`$ is a positive operator and that $`_iE_i=I.`$ $`E_i`$ is similar to the POVM element $`A_i^+A_i.`$ We can regard $`E_i`$ as a generalized POVM (GPOVM) element, which has same property as known POVM element. In fact, $`A_i`$ can be written in the form $`A_i=U_{A2}f_{Ai}U_{A1}`$, where $`f_{Ai}`$ is a diagonal positive operator, $`U_{A2},U_{A1}`$ are two unitary operators, and similarly for $`B_i.`$ If each of $`N`$ Alice’s operators denoted by $`A_i`$ and each of $`N`$ Bob’s operators denoted by $`B_i`$ are projectors, the final operators $`A_iB_i`$ are also projectors, i.e., $`A_iB_iA_jB_j=\delta _{ij}A_iB_i`$, and $`\left\{E_i\right\}`$ is a set of projective measurement.

The discuss above means that: whatever Alice and Bob choose to do, including they decide to involve an ancillary system; they perform local unitary operators and measurement; they use one-way or two-way communication, and do many rounds of measurements and communication, their final actions will be described by a set positive operators $`\left\{E_i\right\}.`$ The probability of a given possible state $`|\mathrm{\Psi }`$ yielding a certain outcome $`i`$ is $`\mathrm{\Psi }\left|A_i^+B_i^+A_iB_i\right|\mathrm{\Psi }.`$

Since a GPOVM element $`E_i`$ has similar property as a POVM element, $`E_i`$ can be represented in the form

$`E_i`$ $`=`$ $`(a_1^i|\phi _1^i_A\phi _1^i|+\mathrm{}+a_{m_a}^i|\phi _{m_a}^i_A\phi _{m_a}^i|+\mathrm{})`$ (10)
$`(b_1^i|\eta _1^i_B\eta _1^i\left|+\mathrm{}+b_{m_b}^i\right|\eta _{m_b}^i_B\eta _{m_b}^i|+\mathrm{})`$
$`0`$ $``$ $`a_{m_a}^i1,0b_{m_b}^i1;1m_aN_a,1m_bN_b`$ (11)
where $`\left\{|\phi _{m_a}^i\right\},\left\{|\eta _{m_b}^i\right\}`$ is a set of bases of Alice’s and Bob’s, respectively; $`N_a,N_b`$ is the dimensions of Alice’s and Bob’s Hilbert space, respectively.

Theorem 1. If a set of $`m`$ orthogonal states $`\left\{|\mathrm{\Psi }_i\right\}`$ is reliably locally distinguishable, if and only if there is a set of locally distinguishable product vectors, $`\left\{|\phi _i^{j_i}_A|\eta _i^{j_i}_B\right\},`$ such that each state $`|\mathrm{\Psi }_i`$ can be written as a superposition of some different product vectors in the set of these product vectors:

$$|\mathrm{\Psi }_i=c_i^1|\phi _i^1_A|\eta _i^1_B+\mathrm{}+c_i^{n_i}|\phi _i^{n_i}_A|\eta _i^{n_i}_B$$
(12)
where $`i=1,\mathrm{},m`$; $`j_i=1,\mathrm{},n_i.`$ $`n_i`$ is the number of product bases in the state $`|\mathrm{\Psi }_i`$

Proof: The proof of sufficiency is obviously. Now we prove the necessarity. If a set of states is reliably locally distinguishable, there must be a set of GPOVM element $`\left\{E_i\right\}`$ such that if every outcome $`i`$ occurs Alice and Bob know with certainty that they were given the state $`|\mathrm{\Psi }_i`$. In a simple way we say that $`E_i`$ can and only can “indicate” $`|\mathrm{\Psi }_i.`$

Since each $`E_i`$ only indicate a state $`|\mathrm{\Psi }_i,`$ the rank of $`E_i`$ should be less than $`N_aN_b`$. Otherwise, $`E_i`$ will indicates all states $`\left\{|\mathrm{\Psi }_i\right\}`$. Without loss of generality, we suppose $`a_1^i,\mathrm{},a_{m_a}^i,b_1^i,\mathrm{},b_{m_b}^i`$ in Eq. (10) are nonzero, the other coefficient are zero, then the state $`|\mathrm{\Psi }_i`$ should have all or part of the component

$$|\phi _1^i_A|\eta _1^i_B,\mathrm{},|\phi _1^i_A|\eta _{m_b}^i_B,\mathrm{},|\phi _{m_a}^i_A|\eta _1^i_B,\mathrm{},|\phi _{m_a}^i_A|\eta _{m_b}^i_B.$$
(13)
The state$`|\mathrm{\Psi }_j`$ $`(ij)`$ should have not these component. Otherwise, $`E_i`$ will indicates more than one state. The effect of the operator $`E_i`$ is project out the component

$$|\phi _1^i_A|\eta _1^i_B,\mathrm{},|\phi _1^i_A|\eta _{m_b}^i_B,\mathrm{},|\phi _{m_a}^i_A|\eta _1^i_B,\mathrm{},|\phi _{m_a}^i_A|\eta _{m_b}^i_B$$
(14)
which only belongs to $`|\mathrm{\Psi }_i.`$ Because of the completeness of $`\left\{E_i\right\}`$ ( which assures that each component in all possible states can be indicated by a GPOVM element) and the necessarity of reliably distinguishing the possible states (which askes a GPOVM element only indicate the component only belonging to a possible states), the $`m`$ possible states can be divided into many component each of which can be indicatd by a GPOVM element. It is to say that these component are locally distinguishable. If a operator $`E_i`$ only indicate a state, then $`E_i`$ can be replaced by a set of operators

$$E_{i1}=|\phi _1^i_A\phi _1^i||\eta _1^i_B\eta _1^i|;\mathrm{};$$
(15)
$$E_{im_b}=|\phi _1^i_A\phi _1^i||\eta _{m_b}^i_B\eta _{m_b}^i|;\mathrm{};$$
(16)
$`E_{im_am_b}=|\phi _{m_a}^i_A\phi _{m_a}^i||\eta _{m_b}^i_B\eta _{m_b}^i|,`$

each of which also only indicates the same state as $`E_i`$ does. The effect of each operator $`E_{ij}(j=1,\mathrm{},m_am_b)`$ is to project out a component which only belong to a single state, for example, operator project out the component $`|\phi _1^i_A`$ $`|\phi _1^i_B`$. Thus all product vectors which only belong to a state can be indicated by a est of operators $`\left\{E_{ij}\right\},`$ so all the product vectors are locally distinguishable and then are orthogonal. Because of the completeness of $`\left\{E_i\right\}`$ and the necessarity of reliably distinguishing the possible states, each state $`|\mathrm{\Psi }_i`$ must be the superposition of some locally distinguishable orthogonal product bases. This end the proof.

From theorem 1 it follows that if a set of operators $`\left\{E_i\right\}`$ can distinguish a set of states, there is a set of orthogonal projective operators $`\left\{E_{ij}\right\}`$ which can achieve the distinguishing the possible states. These operators can always be carried out by rounds of projective measurements and classical communication. It is to say that if a set of $`m`$ states are distinguishable, the operator to distinguish the states can be always described as: First, Alice and Bob choose a person to go first to do measurement with her or his a set of orthogonal bases; After measurement, their Hilbert space collapse into a subspace which is orthogonal to the subpace discarded. According to the outcome, they know that the $`m`$ possible states collapses into $`n`$ ($`nn)`$ distinguishable new states, and choose a person to do measurement with her or his other set of orthogonal bases once more, and so on. After many rounds of projective measurements and classical communication, they may get a final state which only belongs to one of the possible states, and the Hilbert space collapses into a lower subspace. The final state may be entangled state or separable state. If the final state is entangled one can choose end of the operators, also can choose continue to do measurement such that it collapses into one of it’s orthogonal product states. In each round of measurement and communication, Alice and Bob must choose an appropriate person to do measurement. The different round of operator many need different person to do first, in general. For example, six states in a $`44`$ system,

$$|\mathrm{\Psi }_1=|0_A|0_B;|\mathrm{\Psi }_2=|1_A(|0+|1)_B;|\mathrm{\Psi }_3=|0_A|1_B+|1_A(|0|1)_B$$
(17)
$$|\mathrm{\Psi }_4=|2_A|2_B;|\mathrm{\Psi }_5=(|2+|3)_A|3_B;|\mathrm{\Psi }_6=|3_A|2_B+(|2|3)_A|3_B$$
(18)
one can first choose to do measurement with Alice’s bases

$`E_1=|0_A0|+|1_A1|;E_1=|2_A2|+|3_A3|`$

if the outcome is $`E_1`$ they must choose Alice to do first to do the second measurement; if the outcome is $`E_2`$ they must choose Bob to go first to do the second measurement. The distinguishability of states in $`2n`$ systems is a special example in which after Alice do measurement, the possible states collapse into some orthogonal product bases, so the possible states can be written as the form in the Theorem 1 of Walgate’s paper .

Before giving theorem 2 in this paper, we define a concept of Schmidt number. If a pure state $`|\mathrm{\Psi }`$ have following Schmidt decomposition:

$$|\mathrm{\Psi }=\underset{i=1}{\overset{l}{}}\sqrt{P_i}|\nu _i_A|\eta _i_B,\underset{i=1}{\overset{l}{}}P_i=1$$
(19)
where $`|\nu _i_A^{}s`$ and $`|\eta _i_B^{}s`$ are orthogonal bases of Alice and Bob, respectively, we say $`|\mathrm{\Psi }`$ has Schmidt number $`l.`$ Keep this in mind we will start from the following theorem.

Theorem 2: Alice and Bob share a quantum system, which possesses one of pure orthogonal states $`|\mathrm{\Psi }_1,|\mathrm{\Psi }_2,\mathrm{},|\mathrm{\Psi }_i,\mathrm{},|\mathrm{\Psi }_m.`$ If the dimensions of Hilbert space of Alice’s part and Bob’s part are $`N_a`$ and $`N_b,`$ respectively, one cannot distinguish deterministically a set of orthogonal states for which the sum of Schmidt numbers is more than $`N_aN_b`$ when only a single copy is provided.

Theorem 2 can be expressed briefly as: one cannot distinguish a set of orthogonal states the sum of Schmidt number of which is more than the dimensions of whole Hilbert space of the quantum system.

From theorem 2 one can get the following interesting cases:

Case1: For $`nn`$ systems one cannot distinguish deterministically $`n+1`$ states, each of which has Schmidt number $`n.`$ For example, one can at most distinguish two entangled states in $`22`$ systems.

Case 2: For $`nn`$ systems, if one can distinguish $`n^2`$ orthogonal states, these states must be orthogonal bases .

Proof of theorem 2: If the $`m`$ possible orthogonal states are reliably locally distinguishable there are a set of orthogonal product basis each of which only emerges in one state of the $`m`$ possible states, and therefore only “indicates” one state. A pure state with Schmidt numbers $`l`$ includes at least $`l`$ orthogonal product bases, so if the sum of Schmidt numbers of the $`m`$ possible states is more than $`N_aN_b`$, these possible states surely include product bases more than $`N_aN_b`$. However, the number of orthogonal product bases in a $`N_aN_b`$ system is at most $`N_aN_b.`$ So these $`m`$ possible states with Schmidt number more than $`N_aN_b`$ cannot be written as the form in theorem 1, which means they are not distinguishable. This completes the proof theorem 2.

According to the theorem 2 we can discuss completely the case for $`22`$ systems in which there are at most four orthogonal states, as be shown in Ref . Four orthogonal states can be distinguished deterministically if and only if they are four product states. This is obviously from the theorem above or case 2; three orthogonal states can be distinguished deterministically if and only if almost one state is entangled state and the other states are product states. This is because any two product orthogonal states can be written as: $`|\nu _1|\eta _1`$ and $`|\nu _2|\eta _2,`$ where at least one of the inner product $`\nu _1|\nu _2`$ and $`\eta _1|\eta _2`$ is zero. Without loss of generality, we let $`\nu _1|\nu _2=0`$, then $`|\nu _1,|\nu _2`$ consist of a complete set of orthogonal bases in two dimensions Hilbert space. Any entangled state in $`22`$ systems can be expressed as: $`a|\nu _1|\eta _1^{^{}}+b|\nu _2|\eta _2^{^{}}.`$ As these three states are orthogonal, the following relation should hold: $`\eta _1|\eta _1^{^{}}=\eta _2|\eta _2^{^{}}=0.`$ This means the three states are distinguishable deterministically. If more than two states of the three orthogonal states are entangled, the sum of their Schmidt numbers would be more than four, which does not satisfy the necessary condition for distinguishability in the theorem above. So if and only if not less than two states of three orthogonal states are product states, the three states are distinguishable.

In summary, we present a necessary and sufficient condition of distinguishability of bipartite quantum states. It is shown that the operators to reliably distinguish states need only rounds of projective measurements and classical communication.. We also present a necessary condition of distinguishability of bipartite quantum states which is simple and general. With this condition one can get many cases of indistinguishability. These results come directly from the limits on local operations, not from the upper bound of distillable entanglement, So we believe that they may be useful in calculating the distillable entanglement or the bound of distillable entanglement. The further works may be the applications of these results.

###### Acknowledgements.

We would like to thank professor M.B. Plenio for his helpful suggestions and professor Guangcan Guo for his help to this work.