text:
# Polynomial iterative algorithms for coloring and analyzing random graphs

## I Introduction

The Graph Coloring problem is a very basic problem in combinatorics GaJo  and in statistical physics WU . Given a graph, or a lattice, and given a number $`q`$ of available colors, the problem consists in finding a coloring of all vertices such that no edge has the two ending vertices of the same color. The minimally needed number of colors is the chromatic number of the graph.

For planar graphs there exists a famous theorem four\_colors  showing that four colors are sufficient, and that a coloring can be found by an efficient algorithm, while for general graphs the problem is computationally hard to solve. In 1972 it was shown that Graph Coloring is NP-complete Karp72  which means, roughly speaking, that the time required for determining the existence of a proper coloring grows exponentially with the graph size. On the other hand if an efficient algorithm for solving coloring in its worst case instances exists, the same algorithm up polynomial-reduction can be applied to efficiently solve all other problems in the class NP (for a physicist’s approach to complexity theory see Mer ).

In modern computer science, graph coloring is taken as one of the most widely used benchmarks for the evaluation of algorithm performance satlib . The interest in coloring stems from the fact that many real-world combinatorial optimization problems have component sub-problems which can be easily represented as coloring problems. For instance, a classical application is the scheduling of registers in the central processing unit of computers register . All variables manipulated by the program are characterized by ranges of times during which their values are left unchanged. Any two variables that change during the same time interval cannot be stored in the same register. One may represent the overall computation by constructing a graph where each variable is associated with a vertex and edges are placed between any two vertices whose corresponding variables change during the same time interval. A proper coloring with a minimal number of colors of this graph provides an optimal scheduling for registers: two variables with the same color will not be connected by an edge and so can be assigned to the same register (since they change in different time intervals).

The $`q`$-coloring problem of random graphs represents a very active field of research in discrete mathematics which constitutes the natural evolution of the percolation theory initiated by Erdös and Rènyi in the 50’s Erdos\_Renyi . One point of contact between computer science and random graph theory arises from the observation that, for large random graphs, there exists a critical average connectivity beyond which the graphs become uncolorable by $`q`$ colors with probability tending to one as the graph size goes to infinity. This transition will be called the $`q`$-COL/UNCOL transition throughout this paper. The precise value of the critical connectivity depends of course on the number $`q`$ of allowed colors and on the ensemble of random graphs under consideration. Graphs generated close to their critical connectivity are extraordinarily hard to color and therefore the study of critical instances is at the same time a well posed mathematical question as well as an algorithmic challenge for the understanding of the onset of computational complexity AI ; TCS . The notion of computational complexity refers to worst-case instances and therefore results for a given ensemble of problems might not be of direct relevance. However, on the more practical side, algorithms which are used to solve real-world problems display a huge variability of running times and a theory for their typical-case behavior, on classes of non-trivial random instances, constitutes the natural complement to the worst-case analysis. Similarly to what happens for other very famous combinatorial problem, e.g. the satisfiability problem of Boolean formulas, critical random instances of $`q`$-coloring are a popular test-bed for the performance of search algorithms satlib .

From the physics side $`q`$-coloring has a direct interpretation as a spin-glass model BOOKS\_SG . A proper coloring of a graph is simply a zero-energy ground state configuration of a Potts anti-ferromagnet with $`q`$-state variables. For most lattices such a system is frustrated and displays all the equilibrium and out-of-equilibrium features of spin glasses (the ‘Potts glass’).

Here we focus on the $`q`$-coloring problem (or Potts anti-ferromagnet) over random graphs of finite average connectivity, given by the $`𝒢(N,p)`$ ensemble: Graphs are composed of $`N`$ vertices, every pair of them independently being connected by an edge with probability $`p`$, and being not directly connected with probability $`1p`$. The relevant case of finite connectivity graphs is described by $`p=c/N`$, with $`c`$ staying constant in the thermodynamic limit $`N\mathrm{}`$. In this case, the expected number of edges becomes $`M=c/N\left(\genfrac{}{}{0pt}{}{N}{2}\right)cN/2`$, i.e. proportional to the vertex number. Each of the vertices is, on average, connected to $`c`$ other vertices. This connectivity fluctuates according to a Poissonian, i.e. the probability of randomly selecting a vertex with exactly $`d`$ neighbors is given by $`e^cc^d/d!`$.

Two types of questions can be asked. One type is algorithmic, i.e. finding an algorithm that decides whether a given graph is colorable. The other type is more theoretical and amounts to asking whether a typical problem instance is colorable or not and what the typical structure of the solution space is. Here we address both questions using the so called cavity method MePa . First we provide a detailed description of the analytical calculations beyond the results presented in MuPaWeZe , where the question of the coloring threshold and of typical solution properties were addressed. Second this analytical description is modified and applied to single graph instances. This leads to an efficient graph coloring algorithm for the region slightly below the COL/UNCOL transition. In this region, known complete and stochastic algorithms are known to fail already for moderate system sizes.

Let us start with reviewing some known results on the $`q`$-COL/UNCOL transition on random graphs. One of the first important finite-connectivity results was obtained by Luczak about one decade ago Lu . He proved that the threshold asymptotically grows like $`c_q2q\mathrm{ln}q`$ for large numbers of colors, a result, which up to a pre-factor coincides with the outcome of a replica calculation on highly connected graphs KaSo  ($`p=𝒪(1)`$ for large $`N`$). For fixed number $`q`$ of colors, all vertices with less than $`q`$ neighbors, i.e. of degree smaller $`q`$, can be colored for sure. The hardest to color structure is thus given by the maximal subgraph having minimal degree at least $`q`$, the so-called $`q`$-core. Pittel, Spencer and Wormald PiSpWo  showed that the emergence of a 2-core coincides with the percolation transition of random graphs at $`c=1`$ Erdos\_Renyi , and is continuous. For $`q3`$, however, the $`q`$-core arises discontinuously, jumping from zero to a finite fraction of the full graph. For $`q=3`$ they found e.g. that the core emerges at $`c3.35`$ and immediately contains about 27% of all vertices. Shortly after, it was realized that the existence of the core is necessary, but in no way sufficient for uncolorability Mo . In fact, the best lower bound for the 3-COL/UNCOL transition is 4.03 AcMo1 , and numerical results predict a threshold of about 4.7 Numerical . The currently best rigorous upper bound is 4.99 AcMo2 . It was obtained using a refined first moment method. In statistical mechanics, the latter is known as the annealed approximation. More recently, a replica symmetric analysis of the problem has been performed MoSa . The resulting threshold 5.1 exceeds, however, the rigorous bound, and one has to go beyond replica symmetry. At the level of one-step replica-symmetry breaking we are able to calculate a threshold value $`c_34.69`$ which we believe to be exact. We also describe the solution space structure which undergoes a clustering transition at $`c_d4.42`$.

The remaining of the paper is organized as follows: In section II we present the replica symmetric (RS) solution of the problem and discuss why it fails. In section III the one-step replica-symmetry breaking (RSB) solution is presented. From this we derive the average graph connectivity for the q-COL/UNCOL transition, and we demonstrate the existence of a dynamic threshold associated with the appearance of solution clusters in configuration space. Then, in the next section we show that the previous ideas are valid even in the analysis of single-case instances. This allows, in section V, to propose an algorithm that colors, in the hard region, single instances in polynomial time. Finally, in Sec. VI some conclusions of the work are presented.

## II Replica Symmetric Solution

As stated above, the question if a given graph is $`q`$-colorable is equivalent to the question if there are zero-energy ground states of the anti-ferromagnetic $`q`$-state Potts model defined on the same graph. Denoting the set of all edges by $`E`$, the problem can thus be described by the Hamiltonian

$$H_𝒢=\underset{\{i,j\}E}{}\delta (\sigma _i,\sigma _j)$$
(1)
where $`\{\sigma _i\}\{1,2,\mathrm{},q\}`$ are the usual Potts spins, and $`\delta (,)`$ denotes the Kronecker symbol. This Hamiltonian obviously counts the number of edges being colored equally on both extremities, a proper coloring of the graph thus has energy zero. Since this Hamiltonian cannot take negative values, the combinatorial task of finding a coloring is translated to the physical task of finding a zero-energy ground state, i.e. to the statistical physics of the above model at zero temperature.

### II.1 The cavity equation

In this paper we therefore apply the cavity method in a variant recently developed for finite-connectivity graphs directly at zero temperature MePaZe ; MePa2 ; MeZe . This approach consists of a self-consistent iterative scheme which is believed to be exact over locally tree-like graphs, like $`𝒢(N,c/N)`$, the set we consider here. It includes the possibility of dealing with the existence of many pure states. One has to first evaluate the energy shift of the system due to the addition of a new new spin $`\sigma _0`$. Let us assume for a moment that the new spin is only connected to a single spin, say $`\sigma _1`$, in the pre-existing graph. Before adding the new site 0, the ground-state energy of the system with fixed $`\sigma _1`$ can be expressed as:

$$E^N(\sigma _1)=A\underset{\tau =1}{\overset{q}{}}h_1^\tau \delta (\tau ,\sigma _1)$$
(2)
where we have introduced the effective field $`\stackrel{}{h}_1=(h_1^1,\mathrm{},h_1^q)`$ and used the superscript $`N`$ to stress that the previous quantity refers to the $`N`$-sites systems. Note that a $`(q1)`$-dimensional field would be sufficient since one of the $`q`$ fields above can be absorbed in $`A`$. We, however, prefer to work with $`q`$ field components in order to keep evident the global color symmetry. When we connect $`\sigma _0`$ to $`\sigma _1`$ we can express the minimal energy of the $`N+1`$-sites graph at fixed $`\sigma _0,\sigma _1`$ as:

$$E^{N+1}(\sigma _0,\sigma _1)=A\underset{\tau =1}{\overset{q}{}}h_1^\tau \delta (\tau ,\sigma _1)+\delta (\sigma _0,\sigma _1)$$
(3)
The minimum energy for the $`N+1`$-sites system at fixed $`\sigma _0`$ is thus obtained by minimizing $`E^{N+1}(\sigma _0,\sigma _1)`$ with respect to $`\sigma _1`$, it can be written as:

$$E^{N+1}(\sigma _0)=\underset{\sigma _1}{\mathrm{min}}E^{N+1}(\sigma _0,\sigma _1)A\omega (\stackrel{}{h}_1)\underset{\tau =1}{\overset{q}{}}\widehat{u}^\tau (\stackrel{}{h}_1)\delta (\tau ,\sigma _0)$$
(4)
with

$`\omega (\stackrel{}{h})`$ $`=`$ $`\mathrm{min}(h^1,\mathrm{},h^q)`$ (5)
$`\widehat{u}^\tau (\stackrel{}{h})`$ $`=`$ $`\mathrm{min}(h^1,\mathrm{},h^\tau +1,\mathrm{},h^q)\omega (\stackrel{}{h})`$ (6)
where we have introduced the cavity biases  $`\widehat{u}(\stackrel{}{h})`$. This choice of $`\omega `$ and $`\widehat{u}`$ is not unique but, according to the previous discussion, we have chosen the only manifestly color-symmetric notation. The structure of the cavity biases is easily understood if we distinguish among two different cases:

* $`h^\tau >h^1,\mathrm{},h^{\tau 1},h^{\tau +1},\mathrm{},h^q`$ for some $`\tau `$ : Then $`\widehat{u}^\tau =1`$ and $`\widehat{u}^\sigma =0`$ for all $`\sigma \tau `$.
* $`h^{\tau _1}=h^{\tau _2}h^1,\mathrm{},h^q`$ for some $`\tau _1,\tau _2`$ : Then $`\widehat{u}=(\widehat{u}^1,\mathrm{},\widehat{u}^q)=(0,0,\mathrm{},0)=\stackrel{}{0}`$.

Only vectors $`\stackrel{}{h}`$ with non-degenerate maximal component give rise to non trivial cavity bias $`\stackrel{}{u}`$ in the direction of the minimal component. This is physically understandable: A unique maximal field component in $`\stackrel{}{h}`$ fixes the corresponding color, which thus is forbidden to the newly added site. If there are two or more maximal field components, the color of the old site is not fixed, thus there cannot be any forbidden color for the new vertex. Each cavity bias in our problem thus belongs to the $`q+1`$-elements set $`\{\stackrel{}{0},\stackrel{}{e}_1,\mathrm{},\stackrel{}{e}_q\}`$, where $`\stackrel{}{e}_\tau `$ has all components $`0`$ but the $`\tau ^{th}`$ equal to $`1`$.

If the new spin $`\sigma _0`$ is connected to $`k`$ randomly chosen sites with fields $`\stackrel{}{h}_1,\mathrm{},\stackrel{}{h}_k`$, the cavity bias has to be linearly superposed and the resulting cavity field on vertex 0 is given by $`\stackrel{}{h}_0=_{i=1}^k\widehat{u}(\stackrel{}{h}_i)`$. With high probability (tending to one for large $`N`$) the $`k`$ sites will be far from each other in the original graph: Although an extensive number of loops is surely present for $`c>1`$ Erdos\_Renyi , these loops have lengths of the order $`\mathrm{log}N`$. Inside one Boltzmann state we can thus invocate the clustering propriety  BOOKS\_SG  resulting in a statistical independence of the $`k`$ selected sites and there cavity fields $`h_i`$ (for a more detailed discussion of this point see MeZe ; MePa2 ). The simplest ansatz assumes that there exists just one such state (or a finite number, like in ferromagnets at low temperature), which is equivalent to the Bethe-Peierls iterative scheme or the replica-symmetric ansatz in the replica method. Assuming further-on the existence of a well defined thermodynamic limit of the energy density $`E/N`$ and of the probability distributions of local fields (for recent rigorous studies in this direction see GUERRA1 ; FraLeo ; Tala ), the distribution of the fields $`\stackrel{}{h}_0`$ of the newly added vertex becomes the equal to those of the $`k`$ neighbors. It is consequently determined by the closed expression

$`P(\stackrel{}{h})`$ $`=`$ $`e^c{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c^k}{k!}}{\displaystyle d^q\stackrel{}{h}_1},\mathrm{},d^q\stackrel{}{h}_nP(\stackrel{}{h}_1)\mathrm{}P(\stackrel{}{h}_n)\delta (\stackrel{}{h}{\displaystyle \underset{i=0}{\overset{k}{}}}\widehat{u}_i(\stackrel{}{h}_i))`$ (7)
$`Q(\stackrel{}{u})`$ $`=`$ $`{\displaystyle d^q\stackrel{}{h}P(\stackrel{}{h})\delta (\stackrel{}{u}\widehat{u}(\stackrel{}{h}))}`$ (8)
where we have already used that the connectivities $`k`$ are distributed according to a Poissonian of mean $`c`$. The previous equations can be combined in order to have a closed form for the $`Q(\stackrel{}{u})`$:

$$Q(\stackrel{}{u})=e^c\underset{k=0}{\overset{\mathrm{}}{}}\frac{c^k}{k!}\underset{i=1}{\overset{k}{}}d^q\stackrel{}{u_i}Q(\stackrel{}{u_i})\delta (\stackrel{}{u}\widehat{u}(\stackrel{}{u_1}+\stackrel{}{u_2}+\mathrm{}+\stackrel{}{u_k})).$$
(9)
From the symmetry of our model under arbitrary permutations of the colors we conclude that

$$Q(\stackrel{}{e}_1)=Q(\stackrel{}{e}_2)=\mathrm{}=Q(\stackrel{}{e}_q)=\eta \mathrm{and}Q(\stackrel{}{0})=1q$$
(10)
i.e. we need a single real number $`\eta `$ with $`0<\eta <\frac{1}{q}`$ to completely specify the probability distribution function $`Q(\stackrel{}{u})`$. Noting that the probability $`P^{(k)}(\stackrel{}{h})`$ for a site with $`k`$ neighbors can be expressed by

$$P^{(k)}(\stackrel{}{h})=\underset{i=1}{\overset{k}{}}d^q\stackrel{}{u}_iQ(\stackrel{}{u}_i)\delta (h\underset{i=1}{\overset{k}{}}\stackrel{}{u}_i),$$
(11)
and recalling that $`\stackrel{}{u}_i\{\stackrel{}{0},\stackrel{}{e}_1,\mathrm{},\stackrel{}{e}_q\}`$ it is easy to rewrite this probability distribution in a compact multinomial form

$$P^{(k)}(\stackrel{}{h})P^{(k)}(h^1,h^2,\mathrm{},h^q)=\frac{k!\eta ^{_{\tau =1}^qh^\tau }(1q\eta )^{k+_{\tau =1}^qh^\tau }}{(k+_{\tau =1}^qh^\tau )!_{\tau =1}^q(h^\tau )!}$$
(12)
with the convention that $`1/n!=0`$ for $`n<0`$. Note that $`h^\tau (0,1,\mathrm{},k)`$ and that there are correlations among the different components of the cavity fields such that $`P^{(k)}(h^1,\mathrm{},h^q)_{\tau =1}^q𝒫(h^\tau )`$. Now we are ready to calculate the graph average over the Poissonian connectivity distribution of mean $`c`$,

$$P(h^1,\mathrm{},h^q)=e^c\underset{k}{}\frac{c^k}{k!}P^k(h^1,\mathrm{},h^q)=e^{c\eta q}\underset{\tau =1}{\overset{q}{}}\frac{(c\eta )^{h^\tau }}{(h^\tau )!}\underset{\tau =1}{\overset{q}{}}𝒫_{c\eta }(h^\tau )$$
(13)
It is interesting to note that after the average the correlations among the different colors disappear and $`P`$ is the product of $`q`$ Poissonian distributions with average $`c\eta `$. From Eq. (8) it is possible to derive a self-consistence equation for the order parameter noting that the probability $`\eta `$ to obtain a non-trivial cavity bias - say $`\stackrel{}{e}_\tau `$ \- is simply given by the probability that the $`\tau ^{\mathrm{t}h}`$ component of the local field is the non-degenerate smaller, so setting $`\tau =1`$

$$\eta =\underset{h^1=0}{\overset{\mathrm{}}{}}\underset{h^2=h1+1}{\overset{\mathrm{}}{}}\mathrm{}\underset{h^q=h1+1}{\overset{\mathrm{}}{}}P(h^1,\mathrm{},h^q)=e^{c\eta }\underset{n=0}{\overset{\mathrm{}}{}}\frac{(c\eta )^n}{n!}\left(1\frac{\mathrm{\Gamma }(n+1,c\eta )}{\mathrm{\Gamma }(n+1)}\right)^{q1}$$
(14)
where $`\mathrm{\Gamma }(n,x)`$ is the incomplete Gamma function defined from the following useful relation

$$e^x\underset{k=n}{\overset{\mathrm{}}{}}\frac{x^k}{k!}=1\frac{\mathrm{\Gamma }(n,x)}{\mathrm{\Gamma }(n)}$$
(15)
The sum in Eq. (14) converges very fast. It is therefore easy to numerically construct a solution to this equation as a function of $`c`$. For $`q>2`$ it turns out that $`\eta `$ jumps discontinuously from zero to a finite value as shown in Fig. (1) where the order parameter $`\eta `$ jumps at $`c=5.141`$ in the case of $`q=3`$.

This means that, up to $`c=5.141`$ and at the level of the replica symmetric assumption, we only find the paramagnetic solution $`\eta =0`$. The solution $`\eta >0`$ would account to a spontaneous breaking of this symmetry, there should be a finite number of pure states (similar to Neel order in Ising anti-ferromagnets).

### II.2 The calculation of the energy

One can easily compute the average shift in the ground state energy when a new spin is added to the $`N`$-sites system and it is connected to $`k`$ spins of the system. The energy of the original graph is given by $`A_{i=1}^k\omega (\stackrel{}{h}_i)`$ while the energy of the $`N+1`$-sites system is $`A_{i=1}^k[\omega (\stackrel{}{h}_i)+\omega (\widehat{u}(\stackrel{}{h}_i))]`$. Therefore the average shift is given by

$$\mathrm{\Delta }E_1=\underset{k=0}{\overset{\mathrm{}}{}}e^cc^k/k!d^q\stackrel{}{u}_1\mathrm{}d^q\stackrel{}{u}_kQ(\stackrel{}{u}_1)\mathrm{}𝑑Q(\stackrel{}{u}_k)\omega \left(\underset{i=1}{\overset{k}{}}\stackrel{}{u}_i\right)=d^q\stackrel{}{h}P(\stackrel{}{h})\omega (\stackrel{}{h}).$$
(16)
One might be tempted to conclude that Eq. (16) equals the energy density of the system, at least for $`N`$ large enough, but this is not true. There is a correction term due to the change in the number of links per variable in the iteration $`NN+1`$. In fact, generating links with probability $`c/N`$ in a $`N+1`$ system, instead of $`c/(N+1)`$ we are slightly over-generating links. So, we need to calculate the average energy shift in a system when two sites \- say spins $`\sigma _1`$ and $`\sigma _2`$ \- are joined by an anti-ferromagnetic link.

Again, the energy of the original graph is $`A\omega (\stackrel{}{h}_1)\omega (\stackrel{}{h}_2)`$, while the energy after the two spins are joined is given by $`A\mathrm{min}_{\sigma _1,\sigma _2}(h_1^{\sigma _1}h_2^{\sigma _2}+\delta (\sigma _1,\sigma _2))`$. The difference between the two contributions can be written as

$`\mathrm{\Delta }E_{\mathrm{link}}`$ $`=`$ $`\underset{\sigma _1}{\mathrm{min}}(h_1^{\sigma _1}+\underset{\sigma _2}{\mathrm{min}}(h_2^{\sigma _2}+\delta (\sigma _1,\sigma _2)))+\omega (\stackrel{}{h}_1)+\omega (\stackrel{}{h}_2)`$ (17)
$`=`$ $`\underset{\sigma _1}{\mathrm{min}}(h_1^{\sigma _1}u^{\sigma _1}(\stackrel{}{h}_2)\omega (\stackrel{}{h}_2))+\omega (\stackrel{}{h}_1)+\omega (\stackrel{}{h}_2)`$
$`=`$ $`\omega (\stackrel{}{h}_1+\widehat{u}(\stackrel{}{h}_2))+\omega (\stackrel{}{h}_1)`$
This allows as to express the average link-energy shift as

$$\mathrm{\Delta }E_2=d^q\stackrel{}{h}_1d^q\stackrel{}{h}_2P(\stackrel{}{h}_1)P(\stackrel{}{h}_2)\left(\omega (\stackrel{}{h}_1)\omega (\stackrel{}{h}_1+\widehat{u}(\stackrel{}{h}_2))\right)$$
(18)
It is interesting to observe that Eqs. (16) and (17) are model-independent, in the sense that the actual Hamiltonian is encoded into the functions $`\omega (\stackrel{}{h})`$ and $`\widehat{u}(\stackrel{}{h})`$ defined by Eq. (5).

Using Eq. (5) and (13) one shows easily that Eq. (16) reduces to:

$`\mathrm{\Delta }E_1`$ $`=`$ $`{\displaystyle \underset{h^1\mathrm{}h^q}{}}𝒫_{c\eta }(h^1)\mathrm{}𝒫_{c\eta }(h^q)\mathrm{min}(h^1,h^2,\mathrm{},h^q)`$ (19)
$`=`$ $`{\displaystyle \underset{\alpha =0}{\overset{q1}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{q}{q\alpha }}\right){\displaystyle \underset{h=0}{\overset{\mathrm{}}{}}}h𝒫_{c\eta }(h)^{q\alpha }\left({\displaystyle \underset{g<h}{\overset{\mathrm{}}{}}}𝒫_{c\eta }(g)\right)^\alpha `$
It is also not hard to prove that the average link-energy shift $`\mathrm{\Delta }E_2=q\eta ^2`$. This result can be obtained either by direct computation of the integral, or following a simple probabilistic argument: $`\mathrm{\Delta }E_{\mathrm{link}}`$ is different from zero whenever the two unlinked sites have the same color, but this happens with probability $`\eta ^2`$ for each of the colors. Finally we have the the following equation for the energy which is equivalent to the replica-symmetric approximation:

$$E=N\left(\mathrm{\Delta }E_1\frac{c}{2}\mathrm{\Delta }E_2\right)=\underset{\alpha =0}{\overset{q1}{}}\left(\genfrac{}{}{0pt}{}{q}{q\alpha }\right)\underset{h=0}{\overset{\mathrm{}}{}}h𝒫_{c\eta }(h)^{q\alpha }\left(\underset{g<h}{\overset{\mathrm{}}{}}𝒫_{c\eta }(g)\right)^\alpha \frac{c}{2}q\eta ^2$$
(20)
The behavior of the energy for $`q=3`$ as a function of the average connectivity $`c`$ is displayed in Fig. (2). Let us note that for average connectivity $`5.141<c<5.497`$ the energy is negative, a particularly baffling result if we consider that the Hamiltonian (1) is at least positively defined. This phenomenon is analogous to what already observed for the RS approximation in random 3-SAT MonZec , and is a consequence of the approximation used. We will see in the next section how the 1-RSB ansatz cures this pathology. However, before leaving the RS approximation we would like to compare our RS results with the RS approximation presented recently by van Mourik and Saad in MoSa  since their result clearly differs from ours. At the origin of the discrepancy is the fact that they work a population dynamics at very low but finite temperature finding a transition around $`c=5.1`$ but without negative energy region. Analogously to what is reported in MePa2 , if one works directly a zero temperature the distribution $`P(\stackrel{}{h})`$ must be concentrated around integer field components, but this is not true anymore at temperature different from zero, as it happens in MoSa . They find that, in the zero-temperature limit, there remain non-integer field components. In our opinion these are a direct hint to the existence of RSB. Instead of including these fields into an extended replica-symmetric approach, we directly switch to a replica-symmetry broken solution.

## III 1 step RSB solution

The RS results show some evident pathologies and are at odd with numerical simulations Numerical ; MoSa  which predict a lower threshold around $`c=4.7`$, and with the rigorous upper bound $`c=4.99`$ AcMo2 . What can be wrong in our analysis? The main assumption we have made is the statistical independence of the of the $`k`$ cavity fields. Is it true that long distance among spins imply statistical independence? In general the answer we obtain from statistical mechanics is no: The assumption holds only inside pure states.

In this section we will focus on how the cavity method could be used to handle a situation in which there exist many different pure states. More precisely we assume that their number $`𝒩e^{N\mathrm{\Sigma }}`$ is exponentially large in $`N`$. The connectivity-dependent exponent $`\mathrm{\Sigma }`$ is called complexity and denotes the entropy density of clusters. Note that it differs in general from the solution entropy since each cluster may contain as well an exponential number of solutions. The first basic assumption we made is that inside each pure state the clustering condition holds. Under this assumption the iteration can still be applied but we have to take into account the reshuffling of energies of different states when new spins are added.

### III.1  1 RSB cavity equation

We proceed following the same steps of the previous section. Let us take the new spin $`\sigma _0`$ and let us connect it to $`k`$ spins $`\sigma _1,\mathrm{},\sigma _k`$ in the same state $`\alpha `$. Thanks to the fast decrease of correlations inside a pure state the energy of state $`\alpha `$ for fixed value of the $`k`$ spins is

$$E_\alpha ^N(\sigma _1,\mathrm{},\sigma _k)=A_\alpha \underset{i=1}{\overset{k}{}}\underset{\tau =1}{\overset{q}{}}h_{i,\alpha }^\tau \delta (\tau ,\sigma _{i,\alpha })$$
(21)
The optimization step within each pure state $`\alpha `$ runs still in close analogy to the RS computation: when we connect $`\sigma _0`$ to $`\sigma _1,\mathrm{},\sigma _k`$, we express the minimal energy of the $`N+1`$-sites graph with fixed $`\sigma _0`$, by minimizing the $`N+1`$-sites system at fixed $`\sigma _0`$ is thus obtained by minimizing $`E_\alpha ^{N+1}`$ with respect to the $`k`$ spins:

$$E_\alpha ^{N+1}(\sigma _0)=A_\alpha \underset{i=1}{\overset{k}{}}\omega (\stackrel{}{h}_{i,\alpha })\underset{i=1}{\overset{k}{}}\underset{\tau =1}{\overset{q}{}}\widehat{u}^\tau (\stackrel{}{h}_{i,\alpha })\delta (\tau ,\sigma _0)$$
(22)
This last equation shows that the local field acting on the new spin $`\sigma _0`$ in the state $`\alpha `$ is

$$\stackrel{}{h}_{0,\alpha }=\underset{i=1}{\overset{k}{}}\widehat{u}(\stackrel{}{h}_{i,\alpha })$$
(23)
and that the energy shift inside a state is

$$\mathrm{\Delta }E_\alpha =\underset{i=1}{\overset{k}{}}\omega \left(\widehat{u}(\stackrel{}{h}_{i,\alpha })\right)$$
(24)
All the previous equation are completely equivalent to those in the RS case except for the fact that now we have a $`\alpha `$-index labeling the different pure states. One natural question is how cavity fields and the related cavity biases are distributed for a given site among the different pure states. This leads us to the notion of survey MePaZe ; MePa2 ; MeZe , i.e. the site dependent normalized histogram over the different states of both cavity biases and cavity fields:

$`Q_i(\stackrel{}{u}_i)`$ $`=`$ $`{\displaystyle \frac{1}{}}{\displaystyle \underset{\alpha =1}{\overset{}{}}}\delta (\stackrel{}{u}_i\stackrel{}{u}_{i,\alpha })`$
$`P_i(\stackrel{}{h}_i)`$ $`=`$ $`{\displaystyle \frac{1}{}}{\displaystyle \underset{\alpha =1}{\overset{}{}}}\delta (\stackrel{}{h}_i\stackrel{}{h}_{i,\alpha })`$ (25)
In close analogy with what we have already done in the RS case, the existence of a well defined thermodynamic limit implies that there must exist unique functional probability distributions $`𝒬[Q(\stackrel{}{u})]`$ and $`𝒫[P(\stackrel{}{u})]`$ for all the surveys. One may wander how could we handle such a big functional space: Fortunately the $`Q`$-surveys are described in terms of a single real number $`0\eta 1/q`$, cf. Eq. (10), and scalar function $`\rho (\eta )`$ is enough for specifying their distribution:

$$𝒬[Q(\stackrel{}{u})]=𝑑\eta \rho (\eta )\delta \left[Q(\stackrel{}{u})(1q\eta )\delta (\stackrel{}{u})\eta \underset{\tau =1}{\overset{q}{}}\delta (\stackrel{}{u}\stackrel{}{e}_\tau )\right]$$
(26)
with $`\delta []`$ denoting a functional Dirac distribution. Assuming that the survey of site $`0`$ is distributed equally to those of all its k neighbors, we can write:

$`P_0(\stackrel{}{h})`$ $`=`$ $`e^c{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c^k}{k!}}C_k{\displaystyle d^q\stackrel{}{u}_1Q_1(\stackrel{}{u}_1)\mathrm{}d^q\stackrel{}{u}_kQ_k(\stackrel{}{u}_k)e^{y\omega (_{i=1}^k\stackrel{}{u}_i)}\delta (\stackrel{}{h}\underset{i=1}{\overset{k}{}}\stackrel{}{u}_i)}`$ (27)
$`Q_0(\stackrel{}{u})`$ $`=`$ $`{\displaystyle d^q\stackrel{}{h}P_0(\stackrel{}{h})\delta (\stackrel{}{u}\widehat{u}(\stackrel{}{h}))}`$ (28)
Note the presence of the reweighting factor $`\mathrm{exp}(y\omega (_{i=1}^k\stackrel{}{u}_i))`$ that arise after conditioning the probability distributions of the $`\stackrel{}{h}`$s to a given value of energy MePa2 , the prefactors $`C_k`$ are normalization constants depending on $`Q_1(\stackrel{}{u}),\mathrm{},Q_k(\stackrel{}{u})`$. The reweighting parameter $`y`$ is a number equal to the derivative of the complexity $`\mathrm{\Sigma }(e)`$ of metastable states with respect to their energy density $`e=E/N`$:

$$y=\frac{\mathrm{\Sigma }}{e}$$
(29)
Intuitively, this reweighting factor can be understood as a penalty $`e^{y\mathrm{\Delta }E_\alpha }`$ one has to pay for positive energy shifts. Note that Eqs. (27) and (28) can be cast in the following form

$`Q_0(\stackrel{}{u}_0)`$ $`=`$ $`e^c{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c^k}{k!}}C_k{\displaystyle d^q\stackrel{}{u}_1Q_1(\stackrel{}{u}_1)\mathrm{}d^q\stackrel{}{u}_kQ_k(\stackrel{}{u}_k)e^{y\omega (_{i=1}^k\stackrel{}{u}_i)}\delta (\stackrel{}{u}_0\widehat{u}(\stackrel{}{u}_1+\mathrm{}+\stackrel{}{u}_k))}`$ (30)
$`=`$ $`e^c{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c^k}{k!}}C_k{\displaystyle d^q\stackrel{}{h}\stackrel{~}{P}(\stackrel{}{h})e^{y\omega (\stackrel{}{h})}\delta (\stackrel{}{u}_0\widehat{u}(\stackrel{}{h}))}`$
In the last line we have introduced the auxiliary distribution $`\stackrel{~}{P}(\stackrel{}{h})`$ which would result in Eq. (27) without reweighting (i.e. by setting $`y=0`$). It has no direct physical meaning in this context, but it will be of great technical help in the following calculations.

Let us first concentrate on the colorable phase, where the ground states are proper q-colorings and have zero energy. Consequently no positive energy shifts are allowed, so this phase is characterized by $`y=\mathrm{}`$. Let us first calculate the value of the normalization constants $`C_k`$ in this limit. Note that $`\omega (\stackrel{}{h})0`$ for all allowed $`\stackrel{}{h}`$ (each component of $`\stackrel{}{h}`$ is non-positive as $`\stackrel{}{h}`$ results from a sum over $`\stackrel{}{u}`$s). This means that the only surviving terms in Eq. (30) are those with zero energy shift $`\omega (\stackrel{}{h})=0`$, i.e. all fields must have at least one zero component, allowing for the selecting of at least one color without violating an edge. Let us first specialize to the case $`q=3`$ for clarity, the generalization to arbitrary $`q`$ is straightforward. Summing over $`\stackrel{}{u}_0`$ both sides of Eq. (30) we have:

$$\frac{1}{C_k}=\stackrel{~}{P}(0,0,0)+3\underset{h^1<0}{}\stackrel{~}{P}(h^1,0,0)+3\underset{h^1,h^2<0}{}\stackrel{~}{P}(h^1,h^2,0)$$
(31)
where the combinatorial factors 3 appearing in the r.h.s. are obtained by noting that $`\stackrel{~}{P}(h,0,0)=\stackrel{~}{P}(0,h,0)=\stackrel{~}{P}(0,0,h)`$ and that $`\stackrel{~}{P}(h^1,h^2,0)=\stackrel{~}{P}(h^1,0,h^2)=\stackrel{~}{P}(0,h^1,h^2)`$. Combining Eqs. (27),(28) and (10) we get

$`\stackrel{~}{P}(0,0,0)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{k}{}}}(13\eta _i)`$ (32)
$`{\displaystyle \underset{h^1<0}{}}\stackrel{~}{P}(h^1,0,0)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{k}{}}}(12\eta _i)\stackrel{~}{P}(0,0,0)={\displaystyle \underset{i=1}{\overset{k}{}}}(12\eta _i){\displaystyle \underset{i=1}{\overset{k}{}}}(13\eta _i)`$ (33)
$`{\displaystyle \underset{h^1,h^2<0}{}}\stackrel{~}{P}(h^1,h^2,0)`$ $`=`$ $`{\displaystyle \underset{i=1}{\overset{k}{}}}(1\eta _i)2{\displaystyle \underset{h^1<0}{}}\stackrel{~}{P}(h^1,0,0)\stackrel{~}{P}(0,0,0)`$ (34)
$`=`$ $`{\displaystyle \underset{i=1}{\overset{k}{}}}(1\eta _i)2{\displaystyle \underset{i=1}{\overset{k}{}}}(12\eta _i)+{\displaystyle \underset{i=1}{\overset{k}{}}}(13\eta _i)`$
Plugging these relations into Eq. (31) we finally get

$$\frac{1}{C_k}=3\underset{i=1}{\overset{k}{}}(1\eta _i)3\underset{i=1}{\overset{k}{}}(12\eta _i)+\underset{i=1}{\overset{k}{}}(13\eta _i)$$
(35)
Note also that in close analogy to the analysis that lead to Eq. (14), we can interpret (34) as the (un-normalized) probability of having the survey in site $`0`$ pointing in direction $`\stackrel{}{e}_3`$. Therefore combining Eqs. (34) and (35) we obtain

$$\eta _0=\widehat{f}_k(\eta _1,\mathrm{},\eta _k)=\frac{_{i=1}^k(1\eta _i)2_{i=1}^k(12\eta _i)+_{i=1}^k(13\eta _i)}{3_{i=1}^k(1\eta _i)3_{i=1}^k(12\eta _i)+_{i=1}^k(13\eta _i)}$$
(36)
At this point we are ready to write the 1-RSB iterative equation for the $`Q`$-surveys:

$$\rho (\eta )=e^c\underset{k=0}{\overset{\mathrm{}}{}}\frac{c^k}{k!}𝑑\eta _1\rho (\eta _1)\mathrm{}𝑑\eta _k\rho (\eta _k)\delta (\eta \widehat{f}_k(\eta _1,\mathrm{},\eta _k))$$
(37)
Eq. (36) can be easily generalized to an arbitrary number $`q`$ of colors,

$$\widehat{f}_k(\eta _1,\mathrm{},\eta _k)=\frac{_{l=0}^{q1}(1)^l\left(\genfrac{}{}{0pt}{}{q1}{l}\right)_{i=1}^k[1(l+1)\eta _i]}{_{l=0}^{q1}(1)^l\left(\genfrac{}{}{0pt}{}{q}{l+1}\right)_{i=1}^k[1(l+1)\eta _i]}$$
(38)
The self-consistent equation (37) resembles a replica-symmetric equation and can be solved numerically using a population dynamic algorithm:

* Start with an initial population $`\eta _1,\mathrm{},\eta _{}`$ of size $``$ which can be easily chosen to be as large as $`10^6`$ to generate high-precision data.
* Randomly draw a number $`k`$ from the Poisson distribution $`e^cc^k/k!`$;
* Randomly select $`k+1`$ indices $`i_0,i_1,\mathrm{},i_k`$ from $`\{1,\mathrm{},\}`$;
* Update the population by replacing $`\eta _{i_0}`$ by $`f_d(\eta _{i_1},\mathrm{},\eta _{i_k})`$;
* GOTO (ii) until convergence of the algorithm is reached.

One obvious solution of Eq. (37) and (38) is the paramagnetic solution $`\delta (\eta )`$. For small average connectivities $`c`$ it is even the only one. The appearance of a non-trivial solution coincides with a clustering transition of ground states into an exponentially large number of extensively separated clusters. In spin-glass theory, this transition is called dynamical. Still, $`\rho (\eta )`$ will contain a non-trivial peak in $`\eta =0`$ due to small disconnected subgraphs, dangling ends, low-connectivity vertices etc. The shape of $`\rho (\eta )`$ in the case $`q=3`$ is displayed in Fig. (3) for connectivities $`c`$ ranging from $`c_d`$ to $`c_c`$.

The weight $`t`$ of this peak can be computed self-consistently. Let us again consider first the case $`q=3`$. Keeping in mind that for $`y\mathrm{}`$ the field $`\stackrel{}{h}`$ has at least one vanishing component, the only possibilities to obtain $`\widehat{u}(\stackrel{}{h})=\stackrel{}{0}`$ are given by $`\stackrel{}{h}=\stackrel{}{0}`$ or by a field $`\stackrel{}{h}`$ with one single non-zero component. So the probability that the cavity field acting on a given site with $`k`$ neighbors equals zero is given by the sum of the probabilities that all neighboring cavity fields are zero (equal to $`t^k`$), plus the probability that exactly one cavity bias among the $`k`$ is non-trivial (equal to $`k(1t)t^{k1}`$). The average over the Poissonian degree distribution leads to

$$t=e^c\underset{k=0}{\overset{\mathrm{}}{}}\frac{c^k}{k!}\left(t^k+kt^{k1}(1t)\right)=e^{(1t)c}\left(1+(1t)c\right)$$
(39)
Generalizing Eq. (39) to a general number $`q`$ of colors easily gives

$$t=e^{(1t)c}\underset{l=0}{\overset{q2}{}}\frac{(1t)^lc^l}{l!}.$$
(40)
This equation is quite interesting, since a non-trivial solution forms a necessary condition for Eq. (37) to have a non-trivial solution. In fact, this equation was first found in PiSpWo , the fraction of edges belonging to the $`q`$-core is given by $`(1t_{min})`$ with $`t_{min}`$ being the smallest positive solution of Eq. (40). Thus, we also find that the existence of an extensive $`q`$-core is necessary for a non-trivial $`\rho (\eta )`$, and forms a lower bound for the $`q`$-COL/UNCOL transition.

Unlike in the case of finite-connectivity $`p`$-spin-glasses or, equivalently, random XOR-SAT problems RiWeZe ; CoDuMo ; MeRiZe , the existence of a solution $`t<1`$ is not sufficient for a non-trivial $`\rho (\eta )`$ to exist. The latter appears suddenly at the dynamical transition $`c_d`$, which can be determined to high precision using the population dynamical algorithm. This solution does not imply uncolorability, but the set of solutions is separated into an exponentially large number of clusters. The number of these clusters, or more precisely its logarithm divided by the graph size $`N`$, is called the complexity $`\mathrm{\Sigma }`$ and can be calculated from $`\rho (\eta )`$.

### III.2 The calculation of energy and complexity

More generally, we expect also a large number of metastable states at non-zero energy to exist. Hereafter we will assume that they are exponentially many, $`𝒩(e)\mathrm{exp}(N\mathrm{\Sigma }(e))`$, where the complexity $`\mathrm{\Sigma }(e)`$ is (despite of the use of a capitol letter!) an intensive function of the energy density $`e=E/N`$. We can introduce a thermodynamic potential $`\varphi (y)`$ Educated\_Reader  as

$$\varphi (y)=\frac{1}{yN}\mathrm{ln}\left(𝑑ee^{N\{ye+\mathrm{\Sigma }(e)\}}\right)$$
(41)
For large $`N`$, we calculate this integral by its saddle point:

$$\varphi (y)=\underset{e}{\mathrm{min}}\left(e\frac{1}{y}\mathrm{\Sigma }(e)\right)=e_{sp}\frac{1}{y}\mathrm{\Sigma }(e_{sp})$$
(42)
It is easily verified that the potential $`\varphi `$ calculated at the saddle point energy $`e_{sp}(y)`$ fulfills the usual Legendre relations:

$`_y\left[y\varphi (y,e_{sp}(y))\right]`$ $`=`$ $`e_{sp}`$ (43)
$`y^2_y\varphi (y,e_{sp}(y))`$ $`=`$ $`\mathrm{\Sigma }(e_{sp})`$ (44)
Around the saddle point the complexity can be approximated, according to equation (42), by

$$\mathrm{\Sigma }(e)\mathrm{\Sigma }(e_{sp})+y(ee_{sp})=y\varphi (y)+ye$$
(45)
We will now consider a cavity argument: let us denote by $`E_N`$ the energy of a system composed of $`N`$ sites, the density of configurations is given by

$$d𝒩_N(E_N)e^{y\mathrm{\Phi }_N(y)+yE_N}dE_N$$
(46)
with $`\mathrm{\Phi }_N(y)`$ denoting the extensive thermodynamic potential with limit $`\mathrm{\Phi }_N(y)/N\varphi (y)`$. Now we add a spin to the system. If we consider that the total energy is $`E_{N+1}=E_N+\mathrm{\Delta }E`$, we can express the density of configurations in terms of $`E_N`$ and $`\mathrm{\Delta }E`$:

$$d𝒩_{N+1}(E_N,\mathrm{\Delta }E)e^{y\mathrm{\Phi }_N(y)+y(E_N+\mathrm{\Delta }E)}dE_NP(\mathrm{\Delta }E)d\mathrm{\Delta }E.$$
(47)
Integrating over $`\delta E`$ we get

$`d𝒩_{N+1}(E_{N+1})`$ $`=`$ $`Ce^{y\mathrm{\Phi }_{N+1}(y)+yE_{N+1}}dE_{N+1}`$ (48)
$`C`$ $`=`$ $`{\displaystyle \frac{1}{y}}{\displaystyle P(\mathrm{\Delta }E)e^{y\mathrm{\Delta }E}𝑑\mathrm{\Delta }E}{\displaystyle \frac{1}{y}}e^{y\mathrm{\Delta }E}_{P(\mathrm{\Delta }E)}`$ (49)
Comparing the previous equations with (46) we can deduce that

$$\mathrm{\Phi }_{N+1}(y)=\mathrm{\Phi }_N(y)\frac{1}{y}\mathrm{ln}\mathrm{exp}(y\mathrm{\Delta }E)_{P(\mathrm{\Delta }E)}.$$
(50)
In the thermodynamic limit we can thus identify

$$\varphi (y)=\frac{1}{y}\mathrm{ln}\mathrm{exp}(y\mathrm{\Delta }E)_{P(\mathrm{\Delta }E)}$$
(51)
In close analogy with what we have already done in the RS case, and using Eq. (24), we can compute $`\varphi `$ as a site contribution plus a link contribution in the 1-RSB scenario:

* Site Addition

$$\mathrm{exp}\left(y\mathrm{\Delta }\varphi _1\right)=d^q\stackrel{}{u}_{i_1}Q_{i_1}(\stackrel{}{u}_{i_1})\mathrm{}d^q\stackrel{}{u}_{i_k}Q_{i_k}(\stackrel{}{u}_{i_k})\mathrm{exp}\left(y\omega (\underset{j=1}{\overset{k}{}}\stackrel{}{u}_{i_j})\right)=\frac{1}{C_k}$$
(52)
* Link Addition

$`\mathrm{exp}\left(y\mathrm{\Delta }\varphi _2\right)`$ $`=`$ $`{\displaystyle d^q\stackrel{}{h}_{i_1}P_{i_1}(\stackrel{}{h}_{i_1})d^q\stackrel{}{h}_{i_k}P_{i_2}(\stackrel{}{h}_{i_2})\mathrm{exp}\left(y\omega (\stackrel{}{h}_{i_1})+y\omega \left(\stackrel{}{h}_{i_1}+\widehat{u}(\stackrel{}{h}_{i_2})\right)\right)}`$ (53)
$`=`$ $`{\displaystyle d^q\stackrel{}{h}P_{i_1}(\stackrel{}{h})d^q\stackrel{}{u}Q_{i_2}(\stackrel{}{u})\mathrm{exp}[y\left(\omega (\stackrel{}{h})\omega (\stackrel{}{h}+\stackrel{}{u})\right)]}`$
$`=`$ $`1+q\eta _{i_1}\eta _{i_2}(e^y1)`$

Note that in the limit $`y0`$ and assuming $`P_i=P`$ for each site, we obtain the RS expressions. Once the functional distributions $`𝒬[Q(\stackrel{}{u})]`$ and $`𝒫[P(\stackrel{}{h})]`$ are known we can eventually average the energy shifts $`\mathrm{\Delta }\varphi _1`$, $`\mathrm{\Delta }\varphi _2`$ in the usual linear combination:

$$\varphi (y)=\overline{\mathrm{\Delta }\varphi _1}\frac{c}{2}\overline{\mathrm{\Delta }\varphi _2}$$
(54)
where the over-lines denote the average over both disorder and functional distributions. One finally finds

$`\varphi (y)`$ $`=`$ $`{\displaystyle \frac{1}{y}}{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}e^c{\displaystyle \frac{c^k}{k!}}{\displaystyle \underset{i=0}{\overset{k}{}}𝒟Q_i𝒬[Q_i]}\mathrm{ln}\left({\displaystyle \underset{i=0}{\overset{k}{}}d^q\stackrel{}{u}_iQ_i(\stackrel{}{u}_i)\mathrm{exp}\left(y\omega (\underset{i=1}{\overset{k}{}}\stackrel{}{u}_i)\right)}\right)+`$ (55)
$`+{\displaystyle \frac{c}{2y}}{\displaystyle 𝒟P_1𝒫[P_1]𝒟P_2𝒫[P_2]\mathrm{ln}\left(d^q\stackrel{}{h}_1P_1(\stackrel{}{h}_1)d^q\stackrel{}{h}_2P_2(\stackrel{}{h}_2)\mathrm{exp}\left(y\omega (\stackrel{}{h}_1)y\omega \left(\stackrel{}{h}_1+\widehat{u}(\stackrel{}{h}_2)\right)\right)\right)}`$
In the limit $`y\mathrm{}`$ these relations can be written in a more explicit form. Let us consider first the term $`\mathrm{\Delta }\varphi _1`$ in Eq. (52). Referring to Eq. (35) it easy to see that:

$$\underset{y\mathrm{}}{lim}e^{y\mathrm{\Delta }\varphi _1}=\underset{l=0}{\overset{q1}{}}(1)^l\left(\genfrac{}{}{0pt}{}{q}{l+1}\right)\underset{i=1}{\overset{k}{}}[1(l+1)\eta _i]$$
(56)
such that

$$\underset{y\mathrm{}}{lim}y\overline{\mathrm{\Delta }\varphi _1}=\underset{k=1}{\overset{\mathrm{}}{}}e^c\frac{c^k}{k!}𝑑\rho (\eta _1)\mathrm{}𝑑\rho (\eta _k)\mathrm{ln}\left(\underset{l=0}{\overset{q1}{}}(1)^l\left(\genfrac{}{}{0pt}{}{q}{l+1}\right)\underset{i=1}{\overset{k}{}}[1(l+1)\eta _i]\right).$$
(57)
In order to compute the average link contribution $`\overline{\mathrm{\Delta }\varphi _2(y)}`$ we need to evaluate the large $`y`$ limit of Eq. (53) which gives:

$$\underset{y\mathrm{}}{lim}y\overline{\mathrm{\Delta }\mathrm{\Phi }_2(y)}=𝑑\rho (\eta _1)𝑑\rho (\eta _2)\mathrm{ln}\left(1q\eta _1\eta _2\right)$$
(58)
This equation has a nice probabilistic interpretation complementary to that used in the derivation of $`\mathrm{\Delta }E_2`$ in the RS case. In fact the integrand of (53) is different from zero for $`y\mathrm{}`$ only when both sites $`i_1`$ and $`i_2`$ have a different color, and this happens with probability $`(1q\eta _{i_1}\eta _{i_2})`$ (note that $`q\eta _{i_1}\eta _{i_2}`$ is the probability that the two sites have same color). It is now clear from Eq. (42) that taking the $`y\mathrm{}`$ of $`y\mathrm{\Phi }(y)`$ gives us the complexity at least in the COL region where $`e=0`$:

$`\mathrm{\Sigma }(e=0)`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}e^c{\displaystyle \frac{c^k}{k!}}{\displaystyle 𝑑\eta _1\rho (\eta _1)\mathrm{}𝑑\eta _k\rho (\eta _k)\mathrm{ln}\left(\underset{l=0}{\overset{q1}{}}(1)^l\left(\genfrac{}{}{0pt}{}{q}{l+1}\right)\underset{i=1}{\overset{k}{}}[1(l+1)\eta _i]\right)}`$ (59)
$`{\displaystyle \frac{c}{2}}{\displaystyle 𝑑\eta _1\rho (\eta _1)𝑑\eta _2\rho (\eta _2)\mathrm{ln}\left(1q\eta _1\eta _2\right)}`$
### III.3 Results

The previous analysis results for the q-coloring problem in the existence of a dynamic transition, characterized by the sudden appearance of an exponential number of clusters that disconnect the solutions of the problem. This is represented in figure 4 for $`q=3`$ and $`4`$, where the complexity is plotted as a function of the graph connectivity. Note, that at a certain value average connectivity $`c=c_d`$ the complexity abruptly jumps from zero to a positive value. Then it decreases with growing $`c`$ and disappears at $`c_q`$ where the number of solutions become zero. It is not possible any more to find a zero-energy ground state for the system, i.e. the graph becomes uncolorable with $`q`$ colors, and its chromatic number grows by one.

In the following table, we present the results for $`q=3,4,`$ and 5, for the dynamical transition we show the corresponding values of $`c_d`$, of the entropy $`s(c_d)=\mathrm{ln}q+c_d\mathrm{ln}(11/q)/2`$ entro\_remark  and the complexity $`\mathrm{\Sigma }(c_d)`$. For the $`q`$-COL/UNCOL transition, the critical connectivity $`c_q`$ and the solution entropy are given. Like in random 3-satisfiability MoZe  and vertex covering WeHa , this entropy is found to be finite at the transition point.

| q | $`c_d`$ | $`s(c_d)`$ | $`\mathrm{\Sigma }(c_d)`$ | $`c_q`$ | $`s(c_q)`$ |
| --- | --- | --- | --- | --- | --- |
| 3 | 4.42 | 0.203 | 0.0223 | 4.69 | 0.148 |
| 4 | 8.27 | 0.197 | 0.0553 | 8.90 | 0.106 |
| 5 | 12.67 | 0.196 | 0.0794 | 13.69 | 0.082 |

In Fig. (6) we display the average complexity $`\mathrm{\Sigma }`$ as a function of the energy density $`e`$ in the 1-RSB approximation. Recently Montanari and Ricci showed in MoRi1  that in the $`p`$-spin spherical spin glass the 1-RSB scheme is correct only up to a certain critical energy density $`e_G`$, above which this solution become unstable and a FRSB calculation is required. It is possible that such a phenomenon might happen also in this case.

The dynamical transition is not only characterized by a sudden clustering of ground states, at the same point an exponential number of meta-stable states of positive energy appears MeZe . Such states (besides algorithm-dependent entropic barriers which may exist even below $`c_d`$) are expected to act as traps for local search algorithms causing an exponential slowing down of the search process. Well known examples of search processes that are overwhelmed by the presence of excited states are simulated annealing or greedy algorithms based on local information.

To test this prediction, we have applied several of the best available solvers for Coloring and SAT problems available in the net satlib ; culberson\_HP . After some preliminary simulations we observed that the best results could be obtained with the smallk program culberson\_HP  and concentrated our efforts on it. The simulation results, as shown in the lower half of Fig. 4, were obtained in the following way: First a random graph ($`N=10^3`$) was generated and we tried to color it with a small number of colors (here $`q=3`$). If, after some cutoff time (we probed with 10 seconds, 1 minute and 2 minutes without substantial changes), the graph was not colored, we stop and tried to color it with larger $`q`$. For each connectivity we averaged over 100 samples. As it can be clearly seen, the algorithm fails with $`q`$ colors slightly below the dynamical transition, confirming our expectations. In Sec. IV we explain how the cavity approach helps to design an algorithm being able to deal also with this problem.

### III.4 The large-$`q`$ asymptotic

From Eqs. (37) and (38) one can easily deduce the large-$`q`$ asymptotics of $`\rho (\eta )`$. For average connectivities $`c>>q`$ (the threshold $`c_q`$ is expected to scale like $`𝒪(q\mathrm{ln}q)`$), $`f_k`$ is dominated by the $`l=0`$-contributions in the numerator and in the denominator, leading to $`\rho (\eta )=\delta (\eta 1/q)`$ in leading order. Plugging this result into the Eq. (59) one can easily calculate the COL/UNCOL threshold $`c_q`$ by setting the complexity to zero. Taking care only of the dominant contribution we find

$$c_q=2q\mathrm{ln}q+o(q\mathrm{ln}q).$$
(60)
This result coincides with the exact asymptotics found by Luczak Lu . Note, however, that the same dominant term can also be obtained from the vanishing of the replica-symmetric (paramagnetic) entropy $`s(c)`$ which is expected to be exact up to the COL/UNCOL transition. This means that, for $`q\mathrm{}`$, the threshold entropy goes to zero. This behavior could already be conjectured from the above table where the threshold entropies are given for small $`q`$. The derivation of the sub-dominant terms in Eq. (60) requires a much more detailed analysis and goes beyond the scope of this paper. It will be presented in a future publication together with analogous results for $`K`$-SAT BrMeWeZe .

## IV Working with single graph instances: Survey propagation

Up to now we have solved analytically the coloring problem averaged over the set of Erdös-Renyi graphs at given average connectivity. In this way we derived the $`q`$-dependent threshold connectivities of $`c_q`$ at which the graph becomes almost surely uncolorable with $`q`$ colors, i.e. the location of the COL/UNCOL transition. We have also demonstrated the existence of another threshold value $`c_d`$ above which a clustering phenomenon takes place in the space of solutions.

However, one of the relevant consequences of this cavity approach is that it can be naturally implemented to study single case instances, i.e. specific non-random graphs which have to have a locally tree-like structure to fulfill the conditions of the cavity approach. In the average-case analysis at each step of the iteration, we selected randomly $`k`$ sites from the $``$ possible ones to be used in Eq. (36), and we substituted another randomly chosen entry $`\eta _0`$ from the $``$ possible entries. From here on, we will assume that the iteration procedure used above is also valid for single instances – with one significant change: For the generation of survey for one vertex (or edge) we have to use its actual neighbors, the connections between sites are fixed once for ever by the specific graph under consideration.

### IV.1 The survey propagation algorithm

This algorithm works in a way similar to the sum product algorithm KsFrLo . In the latter, to each vertex arrive $`u`$-messages from $`k1`$ neighbors, then this messages are transformed (become $`h`$-fields) and sent as a new message through the link to the descendant $`k`$ neighbors. So, at each time step, in the links of the graphs you will have messages traveling, like in a communication network. The survey propagation algorithm (SP), works with the same principle. The basic difference is that now the messages are replaced by $`usurveys`$ of the messages (i.e. by probability distributions of messages). SP is defined for one given value of the reweighting parameter $`y`$ that must be optimized to minimize the “free energy” of the system. To each edge $`\{i,j\}`$ of the graph we associate two u-surveys $`Q_{ij}(\stackrel{}{u})`$ and $`Q_{ji}(\stackrel{}{u})`$ of messages traveling in the two possible directions. The algorithm self-consistently determines these surveys by a message passing procedure to be described below, and finds consequently all the thermodynamic properties of the model defined on the specific graph. Let us now describe how SP works in practice for the 3-coloring problem:

1. Select a graph $`G=(V,E)`$.
2. All the $`Q_{ij}(\stackrel{}{u})`$ with $`\{i,j\}E`$ are randomly initialized.
3. We sequentially consider all sites $`i`$ and randomly update the links $`\{i,j\}`$ to all neighbors $`j`$ in the following way:

1. For each neighbor $`j`$ of $`i`$ we calculate:

    $$P_{i|j}(\stackrel{}{h})=C_{i|j}\left[\underset{kV(i)j}{}d^q\stackrel{}{u}_kQ_{ki}(\stackrel{}{u}_k)\right]\delta \left(\stackrel{}{h}\underset{kV(i)j}{}\stackrel{}{u}_k\right)\mathrm{exp}\left\{y\omega \left(\underset{kV(i)j}{}\stackrel{}{u}_k\right)\right\}$$
    (61)
    where with the symbol $`V(i)`$ denotes all neighbors of $`i`$. The prefactor $`C_{i|j}`$ is chosen such that $`P_{i|j}`$ is properly normalized to one.
    2. From $`P_{i|j}(\stackrel{}{h})`$ we derive the new u-surveys of all edges $`\{i,j\}`$:

    $$Q_{ij}(\stackrel{}{u})=d^q\stackrel{}{h}P_{i|j}(\stackrel{}{h})\delta \left(\stackrel{}{u}\widehat{u}(\stackrel{}{h})\right)$$
    (62)
4. The iteration step 3. is repeated until convergence is reached.

It was already shown in MeZe  that the free energy of the system may be written as:

$$\varphi (y)=\frac{1}{N}\left[\underset{\{i,j\}E}{}\varphi _{i,j}^{link}(y)\underset{i}{}(n_i1)\varphi _i^{node}(y)\right]$$
(63)
where $`n_i`$ is the connectivity of the vertex $`i`$, and $`\varphi _{i,j}^{link}(y)`$ and $`\varphi _i^{node}(y)`$ represent the contributions of links and vertices which are given by:

$$\varphi _{i,j}^{link}(y)=\frac{1}{y}\mathrm{ln}\left(d^q\stackrel{}{h}P_{i|j}(\stackrel{}{h})d^q\stackrel{}{u}Q_{ji}(\stackrel{}{u})\mathrm{exp}\left\{y\left[\omega (\stackrel{}{h})\omega (\stackrel{}{h}+\stackrel{}{u})\right]\right\}\right)$$
(64)
and

$$\varphi _i^{node}(y)=\frac{1}{y}\mathrm{ln}\left(\underset{kV(i)}{}d^q\stackrel{}{u}_kQ_{ki}(\stackrel{}{u}_k)\mathrm{exp}\left\{y\omega \left(\underset{i=1}{\overset{k}{}}\stackrel{}{u}_i\right)\right\}\right).$$
(65)
Repeating the above procedure for various values of $`y`$, Eqs. (64) and (65) do not only provide the values of $`\varphi (y)`$, but also $`\mathrm{\Sigma }(y)=y^2\varphi (y)/y`$ and the energy density $`e(y)=(y\mathrm{\Phi }(y))/y`$ of states. The parametric plot of $`\mathrm{\Sigma }(y)`$ versus $`ϵ(y)`$ gives the complexity of states as a function of their energy. For example, Fig. (7) shows the free energy $`\varphi (y)`$ of single graphs with $`N=10000`$ vertices as a function of $`y`$ for three different values of the average connectivity $`c`$.

We observe that for high enough connectivities the maximum of $`\varphi (y)`$ is located at finite values of $`y`$. While decreasing $`c`$, the location of the maximum grows and approaches $`y\mathrm{}`$ at the coloring threshold. From these curves and by means of numerical derivatives, we may also calculate the complexity and energy. Fig. (8) shows the two branches obtained in the parametric plot of $`\mathrm{\Sigma }(y)`$ vs. $`e(y)`$ for various connectivities $`c`$. While the physical meaning of the upper branches is not clear MePa2  we wanted to stress that they interpolate between the RS solution and the maximum complexity point.

From the previous figure we may extract two characteristic values of the energy: The first one, is associated with the minimal number $`e_0N`$ of miscolored edges in the graph, i.e. it gives the ground state energy of the instance. The value of $`e_gs`$ is determined as the positive point where the lower branch of the complexity curve intersects the energy axis, or it equals zero if $`\mathrm{\Sigma }(e=0)>0`$ on the lower branch.

The other relevant energy value is the threshold energy $`e_{th}`$. It is determined by the point where the complexity reaches its maximum. It is therefore the point where e.g. simulated annealing gets stuck. The same remark of Sec. (III.3) holds here: this calculation should be probably improved along the line of MoRi1  in order to take into account the FRSB instability at higher energy density as in the case of the $`p`$-spin spherical model.

From the practical side this is of course not the way to determine this values, it is much more desirable to look for the value of $`y`$ at which $`\varphi (y)`$ becomes maximal, cf. Eq. (44). Fig. (9), shows a plot of these two energies as a function of the connectivities obtained using this single-instance algorithm.

Of course, the exact meaning of the numerical values of these quantities is an open question. In principle they were defined for infinite systems, whereas our single-instance algorithm works for systems of finite sizes $`N`$. We expect that the numerical values give good approximations once we look to large values of $`N`$, where e.g. the scales dividing distances of solutions inside one state from those between states are well separated. A more detailed discussion about this may be found in MePa ; MeZe .

## V A polynomial algorithm to color graphs

The Survey Propagation described above was very useful for the design of an efficient algorithm to find a solution of randomly generated 3-SAT formulas MePaZe ; MeZe  in the hard but satisfiable phase. Here we will show that, with small modifications, the same idea can be extended to the q-coloring problem.

The relevant idea in this algorithm is to fix spins which are strongly biased toward (or away from) one color. Therefore, we have to first determine the distributions of local magnetic fields in the system using SP, and select those which have the strongest bias. Once these are fixed, the problem is reduced. We can rerun SP on the reduced instance, new spins may be biased and fixed. The procedure will be repeated until only paramagnetic spins remain. At this point SP cannot help any more, but surprisingly the decimated coloring problem becomes “easy”. Using any reasonable local solver known in the literature, we can proceed to construct a proper coloring.

In the case of $`q`$-COL the subject is technically slightly more complex than in K-SAT, since spins can be biased in $`q`$ different directions and it is hard to decide what do we mean precisely by biased. In addition, by fixing the color of one vertex, all its neighbors have to have different colors, i.e. they are left with $`q1`$ colors. In the reduction process the problem, initially being a pure $`q`$-coloring problem, becomes a list coloring problem where each vertex has an own list of allowed colors. In this way the permutation symmetry of colors is broken, which requires a modification of the SP given above to non-symmetric surveys.

In order to keep the presentation as simple as possible we concentrate our efforts on the 3-coloring problem and hence, from now on, all the discussion will be associated for the case $`q=3`$. The extension of the results to higher $`q`$ is, however, straightforward although exponential in $`q`$.

As mentioned above, the first things we should do are a generalization of SP to non-color-symmetric situations, and to correctly define a biased spin. Let us start first noting that equation (26) may be written as

$$𝒬[Q(\stackrel{}{u})]=d^q\stackrel{}{\eta }\rho (\stackrel{}{\eta })\delta \left[Q(\stackrel{}{u})\eta ^0\delta (\stackrel{}{u})\underset{\tau =1}{\overset{q}{}}\eta ^\tau \delta (\stackrel{}{u}\stackrel{}{e}_\tau )\right]$$
(66)
where we simply avoid to consider the color symmetry of the problem, and where we introduce $`\eta ^0=(1_{\tau =1}^3\eta ^\tau )`$. Then, following the same lines of reasoning that lead from (26) to (36) we may deduce the following update of the surveys in the limit $`y\mathrm{}`$:

$$\eta _{ij}^r=\frac{_{kV(i)/j}(1\eta _{ki}^r)_{pr}_{kV(i)/j}(\eta _{ki}^0+\eta _{ki}^p)+_{kV(i)/j}\eta _{ki}^0}{_{p=1,2,3}_{kV(i)/j}(1\eta _{ki}^p)_{p=1,2,3}_{kV(i)/j}(\eta _{ki}^0+\eta _{ki}^p)+_{kV(i)/j}\eta _{ki}^0},$$
(67)
for $`r\{1,2,3\}`$. The value of $`\eta _{ij}^0`$ can be calculated by imposing the normalization condition. Using this update rule instead of the one proposed in the above version of SP, we directly work with a reweighting parameter $`y=\mathrm{}`$ which forbids any positive energy changes and thus characterizes proper colorings.

Having $`\eta _i^\tau `$, for all the sites of the graph, we have to define the site dependent color polarizations

$$\mathrm{\Pi }_i^r=\frac{_{jV(i)}(1\eta _{ji}^r)_{pr}_{jV(i)}(\eta _{ji}^0+\eta _{ji}^p)+_{jV(i)}\eta _{ji}^0}{_{p=1,2,3}_{jV(i)}(1\eta _{ji}^p)_{p=1,2,3}_{jV(i)}(\eta _{ji}^0+\eta _{ji}^p)+_{kV(i)}\eta _{ji}^0},$$
(68)
for $`r=1,2,3`$. This equation is analogous to Eq. (67) but the products are extended to all neighbors. The polarization $`\mathrm{\Pi }_i^r`$ is the probability that vertex $`i`$ is fixed to color $`r`$ in a randomly selected cluster of solutions. Vertices which may change their color within one cluster are characterized by $`\mathrm{\Pi }_i^0=(1_{r=1}^3\mathrm{\Pi }_i^r)`$. Once these polarizations are known, many strategies can be adopted for coloring the graph. We believe that the simplest and most intuitive one is the following:

* If one spin is very biased to one color, fix that spin and remove it from the graph. Forbid this color to all neighbors.
* If the bias of one spin toward some color is very low, forbid that color.

Forbidding a color $`c`$ to a node $`i`$ implies rewritting Eq. (67) using only two colors for that particular node. This can be achieved simply by takin Eq. (67) and (68) but setting $`\eta _{ik}^c=0`$ and $`\eta _{ki}^c=1`$ for all $`kV(i)`$.

Furthermore, during the processes discussed above, it turned out, that many vertices get surrounded by neighbors with fixed colors. In that case, the spin can be fixed to one of their remaining allowed colors immediately, and it is removed from the graph.

In practice, we put a cutoff for the value of the bias to be used for the previous criteria. We use rule (i) every time a bias towards some color is greater than $`0.8`$ and rule (ii) if the bias was lower than $`0.15`$. There is no special reason for selecting specifically these values, but we found numerically a fast convergence to solvable paramagnetic problem instances. It could be useful to make a systematic analysis for improving this choice, and also to discuss other selection rules. However, this is not the objective of the present work. Here we just want to demonstrate that the algorithm works substantially better than every other local search algorithm we know, even without any parameter optimization.

Summarizing, the discussion above, our algorithm follows the next steps

1. Take the original graph and run SP in its infinite-$`y`$ version defined by Eq. (67).
2. Calculate the biases of all spins according to (68).
3. Select spins whose bias to one color is larger than 0.8, fix and remove these spins from the graph. Forbid the color to all neighbors.
4. Select spins whose bias to one color is lower than 0.15 and forbid that color to these spins.
5. Take all spins where just one color is allowed, fix these spins, and remove then from the graph. Forbid the fixed color to all neighbors.
6. If the the graph is not completely paramagnetic: rerun SP and go to 2.
7. Run any smart program that solves the coloring sub-problem.

Actually, we did not find any free program in the web which was able to easily handle large graphs for the coloring problem. The best we could find was the smallk-program by Culberson culberson\_HP , but even in the easy region it exploded in memory for graphs with sizes larger than $`N=2000`$. So step 7 above was changed into:

1. Transform the resulting graph into a satisfiability problem.
2. Run walk-SAT satlib  on this satisfiability problem.

An interesting point about the algorithm described above is the fact that we can fix a certain percentage of spins in every algorithmic step, without rerunning SP every time. This drastically reduces the computational time. How many spins we may fix, depends in a non-trivial way on the system size and on the distance from the COL/UNCOL transition.

Figure 10 shows the success rate of our algorithm in 3-coloring random graphs in the hard region $`c[4.42,4.69]`$. From left to right the sample sizes increase: $`N=410^3`$, $`810^3`$, $`1610^3`$, $`3210^3`$ and $`6410^3`$. In all the cases we fixed the 0.5 percentage of the spins in every iteration step. Note that keeping this value fix we find a clear improvement of the algorithm for sizes going from $`N=410^3`$, $`810^3`$ to $`N=1610^3`$ the performance is roughly the same for larger lattices suggesting that we should reduce the fraction of spins to fix. However, note that even within these conditions the algorithm works quite well in the hard region of the system.

Note, that strong finite size effects are present, in fact the algorithm doesn’t behave very well for small lattice sizes. Two reasons may explain this: First there are short short loops that disappear in the thermodynamic limit, second there is some shift in the location of the COL/UNCOL transition towards higher connectivities for larger graphs. This point should be clarified in a fortcoming work.

Another relevant feature of the curve is the following: The closer our graph is to the critical point, the smaller is also the percentage of spins we may fix in one algorithmic step. However, extrapolating the results, the worst we can find is to fix only one single spin at the time. This would change the complexity of our algorithm from $`N\mathrm{ln}N`$ (resulting from sorting spins with respect to their biases) to $`N^2`$, i.e. the algorithm remains polynomial.

## VI Conclusions and outlook

In this work we presented a detailed derivation of the one-step replica-symmetry broken solution of the coloring problem on random graphs. The problem consists in finding a coloring of all vertices of the graph such that no two adjacent vertices carry equal colors. From the average case point of view, the one-step RSB approach allowed to determine the $`q`$-COL/UNCOL transition $`c_q`$ for arbitrary color numbers $`q`$. This means that large random graphs of average connectivity below $`c_q`$ have proper $`q`$-colorings with high probability (approaching one for $`N\mathrm{}`$), whereas graphs with higher connectivity require more colors for a proper coloring. Moreover, we find the existence of a clustering transition in the colorable region. This transition is characterize by the appearance of an exponential number of states separated by large energetic barriers. The clustering transition is accompanied by the sudden appearance of an exponential number of metastable states that - intuitively - cause local algorithm to get stuck.

We also extended our results to the study of single case instances, i.e. specific realizations of random graphs, showing that the previous analysis remains valid. With this understanding we also implemented a new algorithm, based on the idea of a survey propagation that enabled us to solve the coloring problem in the hard clustering region in polynomial time. We present results for sizes as large as $`N10^5`$ vertices, which is far beyond the performance of other algorithms on random graphs.

There are many interesting direction to extend this work. A first one concerns the survey-propagation algorithm. We were able to report quite encouraging results for the SP inspired graph reduction procedure if applied to the clustered, i.e. hard but colorable phase on random graphs. These graphs are characterized by a locally tree-like structure, loop are of length $`𝒪(\mathrm{ln}N)`$. This structure allowed us to use the statistical independence of surveys restricting a randomly selected vertex inside each pure state. This assumption fails, however, if the graph has some non-trivial local structure as given by small loops, small highly connected subgraphs etc. Before being of real practical value, SP should be extended to such situations, following e.g. the lines used by Yedidia et al. in YeFrWe  in their generalization of belief propagation to locally non-treelike graphs.

A second possible extension of our work concerns the interpretation of colorings as ground-states of a Potts-antiferromagnet, which is a model known to show glassy behavior at low temperatures (the so-called Potts-glass), see e.g. BOOKS\_SG . In the present work we have directly worked at zero temperature, but the extension to non-zero temperature is straight-forward. In this context it is interesting to see that for $`q=3`$ a continuous full replica-symmetry breaking transition appears at the level of fields of $`𝒪(T)`$ \- before the one-step solution appears for fields of $`𝒪(1)`$. So we expect that the one-step RSB transition in this model exists in a strict sense only at zero temperature, in temperature it is only a (sharp) cross-over to glass-like behavior. This phenomenon disappears for larger $`q`$, but it is interesting in how far it can influence the usual glassy phenomenology known from fully-connected spin-glass models. Let us also point out that interestingly enough a similar scenario holds also in the random K-SAT MerMezZec  case. Using in addition the approach suitable for single graph instances, one can, e.g., study inhomogeneities arising in the glassy phase MoRi2  and thus go beyond the usual paradigm of disorder averaged results for randomly disordered models.

###### Acknowledgements.

We are grateful to A. Montanari, J. Culberson, B. Hayes, and F. Ricci-Tersenghi for their interest and many helpfull discussions.


format: text

text:
# A Luminous Recurrent Supersoft X-ray Source in NGC 300

## 1 Introduction

Supersoft X-ray sources (SSSs) form a distinct class of objects, first established through ROSAT observations. The hallmarks of SSSs are very soft X-ray emission ($`kT`$ typically $`<100`$ eV) and bolometric luminosities of $`10^{36}10^{38}`$$`\text{erg}\text{s}^1`$. The advent of Chandra and XMM-Newton provides good opportunities to detect and study SSSs in nearby galaxies. Luminous ($`10^{3840}`$$`\text{erg}\text{s}^1`$) SSSs have been found in several nearby galaxies including M31 (Kong et al. 2002; Di Stefano et al. 2002a), M81 (Swartz et al. 2002), M101 (Pence et al. 2001; Mukai et al. 2003; Di Stefano & Kong 2003 \[DK03\]), NGC4697 (Sarazin, Irwin & Bregman 2001; DK03), M51 (DK03), and M83 (Soria & Wu 2003; DK03).

NGC 300 is an SA(s)d galaxy, seen near face-on (inclination angle 46; Tully 1988) at a distance of $`2.0\pm 0.1`$ Mpc (Freedman et al. 2001). The galaxy has been observed by ROSAT (Read et al. 1997; Read & Pietsch 2001) and XMM-Newton (Soria & Kong 2003).

In this Letter, we report the reappearance of a luminous SSS in NGC 300 as observed with XMM-Newton.

## 2 Observations and Data Reduction

### 2.1 ROSAT

NGC 300 was observed by ROSAT five times from 1991 to 1997. A detailed analysis of the ROSAT data was done by Read & Pietsch (2001). Briefly, the datasets consist of 2 Position Sensitive Proportional Counter (PSPC) and 3 High Resolution Imager (HRI) pointings. The exposures range from $`9`$ ks to $`37`$ ks. The luminous supersoft source was only detected in a 37 ks PSPC observation taken on 1992 May and June (see Read & Pietsch 2001). Spectral analysis was also done by Read et al. (1997). We have reanalyzed the PSPC spectrum taken on 1992 May/June, and used other data to set upper limits on the luminosity for the long-term lightcurve.

We extracted the source spectrum from a $`30^{\prime \prime }`$ circular region, while background was from an annulus region ($`45^{\prime \prime }`$ and $`60^{\prime \prime }`$ radii) centered on the source. The spectrum was grouped into at least 20 counts per spectral bin to allow $`\chi ^2`$ statistics to be used.

### 2.2 XMM-Newton

The XMM-Newton instrument modes were full-frame, medium filter for the three European Photon Imaging Cameras (EPIC). The first observation was taken on 2000 December 26 for 37 ks and the second observation was on 2001 January 1 for about 47 ks. After rejecting intervals with a high background level, we considered a good time interval of $`28`$ ks and $`40`$ ks for the first and second observation, respectively. Data were reduced and analyzed with the XMM-Newton SAS package v5.3.3.

We used here the MOS images to determine the position of the source because the spatial resolution of MOS detector is slightly better than that of pn. The source is located at R.A.=00h55m10s.7, Dec.=$`37^{}38^{}55^{\prime \prime }`$ (J2000), $`4^{}`$ (2.4 kpc) from the galactic center; the derived positions from the two XMM-Newton observations agree with each other. This position is about $`5^{\prime \prime }`$ off from previous ROSAT PSPC observation, and is consistent with the positional error ($`7.3^{\prime \prime }`$) quoted by Read & Pietsch (2001).

Source spectra and lightcurves of XMMU J005510.7-373855 were extracted with the SAS task xmmselect. Source-free regions were used for background to avoid the chip boundary and a nearby faint source. In order to allow $`\chi ^2`$ statistics to be used, all the spectra were binned such that there are at least 20 counts per spectral bin. Response matrices were created by rmfgen and arfgen.

## 3 Analyses and Results

Spectral analysis was performed by making use of XSPEC v11.2. Table 1 shows the best-fitting spectral parameters for the three ROSAT and XMM-Newton observations.

For the ROSAT observation, the spectrum (see Figure 1) can be fit with a blackbody model with $`N_H=1.1\times 10^{21}`$ cm-2 and $`kT=48.7`$ eV; the 0.2–2 keV luminosity is $`10^{39}`$$`\text{erg}\text{s}^1`$. We note that Read et al. (1997) fit the spectrum with a thermal bremsstrahlung model with temperature of a 0.1 keV and we confirmed that it is also an acceptable model. Using the thermal bremsstrahlung model, the luminosity becomes $`3.8\times 10^{38}`$$`\text{erg}\text{s}^1`$ \[the luminosity quoted by Read et al. (1997) is $`1.6\times 10^{37}`$$`\text{erg}\text{s}^1`$, which is an absorbed luminosity corrected for absorption in our own Galaxy\], a factor of 2.5 lower than the blackbody model. While we cannot distinguish between the two models statistically, we prefer the blackbody model as subsequent XMM-Newton observations confirm the supersoft nature of the source (see below). Also, the XMM-Newton observations would have detected the high energy photons associated with the thermal bremsstrahlung model, had the model been correct. Finally, the XMM-Newton observations provide more photons than ROSAT.

We fit the pn, MOS1 and MOS2 data simultaneously with several single-component models with interstellar absorption (including absorbed power-law, thermal bremsstrahlung, blackbody and Raymond-Smith); only the blackbody model provides an acceptable fit. The blackbody temperature of both observations ranges between 57 eV and 67 eV, while the $`N_H`$ varies from $`1.5\times 10^{21}`$ cm-2 in the first observation to $`5.3\times 10^{20}`$ cm-2 in the second observation. The 0.2–2 keV luminosity also drops from $`9\times 10^{38}`$$`\text{erg}\text{s}^1`$ to $`1.2\times 10^{38}`$$`\text{erg}\text{s}^1`$, indicating that the source is a variable on timescale of days. The spectra of the two observations are shown in Figure 1.

The combined ROSAT and XMM-Newton long-term lightcurve of the SSS is shown in Figure 2, which is constructed from a series of ROSAT and XMM-Newton pointings. The source was below the detection limit of other ROSAT observations. In these cases, we estimated the $`3\sigma `$ limits, assuming a blackbody model with mean $`N_H`$ ($`10^{21}`$ cm-2) and $`kT`$ (58 eV). The value of $`N_H`$ plays an important role in estimating the luminosity. For instance, if we lower the $`N_H`$ to $`5.3\times 10^{20}`$ cm-2, as found in the second XMM-Newton observation, the upper limits decrease by a factor of $`3`$. In other words, the source varies by as much as factor of 30 between the “low” state and the “high” state spanning 8.5 years.

To search for short-term variability, we computed the Lomb-Scargle periodogram (LSP; Lomb 1976; Scargle 1982), a modification of the discrete Fourier transform which is generalized to the case of uneven spacing. In each observation, we extracted the combined background subtracted lightcurve from pn and MOSs to increase the signal-to-noise. Individual lightcurves from each of the three detectors were also used to verify the result. By applying the LSP to the combined lightcurve, we found that there is a sharp peak at 5.4 hr in the “low” state observation (see Figure 3). Independent checks from the pn and MOS data also confirmed the periodicity. We determined the 99.9% confidence level by generating Gausiaan noise datasets with the same time intervals and variance as the true data, and then performed the LSP analysis on the resulting datasets (see Kong, Charles & Kuulkers 1998). The peak power in each periodogram (which must be purely due to noise) was then recorded. This was repeated 10000 times to obtain good statistics. The peak at 5.4 hr is well above the 99.9% confidence level. The folded lightcurve of the “low” state data in 5.4 hr is also shown in Figure 3.

Similar analysis was also carried out in the “high” state data, but there is no significant peak in the LSP. The folded lightcurve shows no obvious periodic variability at 5.4 hr (see Figure 3). It is not clear if it is due to geometric effect but the exposure time of the “high” state covers less than 8 hr, corresponding to 1.4 cycles of the 5.4-hr period in contrast to the 2.1 cycles in the “low” state. We therefore performed Kolmogorov-Smirnov test to test for variability and found significant variability at the 99.9% levels. We also search for variability of the hardness ratio but no significant change was found in both observations.

We also examined an Digitized Sky Survey image of NGC 300 to search for possible optical counterpart. Within a $`4^{\prime \prime }`$ error circle of the XMM-Newton position, there is no obvious optical counterpart with limiting $`B`$ and $`R`$ magnitudes of 21 and 18.1, respectively. However, the source is surrounded by Hii regions (Deharveng et al. 1988; Blair & Long 1997), OB associations (Pietrzynski et al. 2001) and supernova remnants (Blair & Long 1997). The nearest Hii region (source 136; Deharveng et al. 1988) is located about $`20^{\prime \prime }`$ ($`200`$ pc) south-east of the X-ray source. Within $`50^{\prime \prime }`$ ($`500`$ pc) of the SSS, we found an OB association (AS99; Pietrzynski et al. 2001), two supernova remnant candidates (N300-S21, N300-N23; Blair & Long 1997) and a Hii region (N300-H20; Blair & Long 1997). We also looked for UV counterpart from the Optical Monitor (OM) image (see Soria & Kong 2003 for details of the OM observations); no counterpart is found at the position of the SSS in both observations.

## 4 Discussion

It is clear from the spectral fits of all ROSAT and XMM-Newton observations that the XMMU J005510.7-373855 is very soft ($`kT4867`$ eV) and is highly variable. Such a soft spectrum is consistent with SSSs seen in our own Galaxy, the Magellanic Clouds, M31 (Greiner 2000 111see http://www.aip.de/$``$jcg/sss/ssscat.html for updated catalog) and several nearby galaxies (see § 1). Since the Galactic and Magellanic Cloud SSSs are conjectured to be white dwarfs (WDs), it is reasonable to consider a WD model for the source in NGC 300. Since, however, the luminosity in the high state may be too large to be consistent with the standard SSS WD model, we also consider black hole (BH) and neutron star (NS) models.

The X-ray emission of the SSS could come from a WD that burns accreting hydrogen in a quasi-steady manner. The maximum luminosity is the Eddington luminosity for a $`1.4M_{}`$ object. WD models therefore seem to be ruled out by the high bolometric luminosities during 2 of the observations. It is nevertheless worth noting that the WD model temperatures are comparable to those we observed, and that X-ray variability by a factor of a few over times of days and months has been observed in SSSs. (see e.g., Greiner and Di Stefano 2002 and references therein.) If the 5.4-hour variation detected during the X-ray low state corresponds to an orbital period, then this system may be similar to 1E0035.4-7230, a Magellanic Cloud SSS that appears to have a $`4`$ hour period (Kahabka 1996). In such a short-period binary, it is likely that a radiation-driven wind plays an important role in the binary evolution. (see, e.g., van Teeseling & King 1998) A WD model would perhaps be the most natural explanation for the SSS in NGC 300, were it not for the high estimated bolometric luminosities. Note that it may be difficult to use beaming to circumvent the Eddington limit in these systems, since the inner region of the accretion disk can also become a luminous emitter of SSS radiation (Popham & Di Stefano 1996).

SSS emission is expected from accreting BHs. Modeling the accretion disk as a thin disk which is optically thick, we can derive a relationship between the minimum mass of the accretor, and the observed temperature and luminosity (Frank, King, & Raine 2002). Using $`kT=60`$ eV and $`L_X=10^{38}`$$`\text{erg}\text{s}^1`$ ($`10^{39}`$$`\text{erg}\text{s}^1`$), we find that the accretor mass is greater than $`890M_{}`$ ($`2800M_{}`$). Although the fact that the observed luminosity is $`10^210^3`$ times smaller than the Eddington luminosity may call the validity of the disk model into question, this calculation suggests that the accretor is an intermediate-mass BH. If the accretor is a BH, we may use $`L_{obs}=0.1\dot{m}c^2(\eta /0.1)`$, where $`\dot{m}`$ is the accretion rate and $`\eta `$, the efficiency factor, is likely to be close to 0.1. This yields $`\dot{m}1.8\times 10^8M_{}`$/yr ($`1.8\times 10^7M_{}`$/yr) for $`L_{obs}=10^{38}`$$`\text{erg}\text{s}^1`$ ($`L_{obs}=10^{39}`$$`\text{erg}\text{s}^1`$). This would be consistent with an irradiation-driven wind from a low-mass donor. Measurement of the orbital period could provide supporting evidence. Indeed, if the donor fills its Roche lobe, then $`P_{orb}(8.9\mathrm{hrs})(M_d/M_{})`$, where $`M_d`$ is the mass of the donor star. If $`P_{orb}=5.4`$ hrs, then $`M_d0.61M_{}`$.

It is of course possible that the observed emission emanates from an accreting NS. In this case the SSS emission would presumably emanate from a photosphere which is much larger than the neutron star itself. The photospheric radius would be different in each observation: $`3.7\times 10^9`$ cm during the ROSAT observation, $`2.6\times 10^9`$ cm during the XMM-Newton high-state observation, and $`6.8\times 10^8`$ cm during the XMM-Newton low-state observation, corresponding to the different temperatures and luminosities.

At this point, neutron star models seem conceptually unattractive because there is no obvious explanation for why the photosphere should achieve these relatively large sizes, and no way to relate them to the system’s fundamental physical parameters. In addition, just as in the WD models, the luminosity appears to be super-Eddington during two of the observations, unless the neutron star has a mass as large as $`34M_{}.`$ In this case, if the efficiency of turning accretion energy into X-rays is the same during all $`3`$ observations, then the accretion rate must have changed by an order of magnitude, approaching $`2\times 10^8M_{}`$ yr-1 during the high state. (see Di Stefano et al. 2002b for a similar model of the X-ray source in the globular cluster Bo 375.) If, on the other hand, the mass of the neutron star is close to $`1.4M_{},`$ then other ways around the Eddington limit must be found; e.g., the energy could be beamed into a smaller solid angle during the $`2`$ high-state observations. In this case, the accretion rate could be significantly lower.

## 5 Summary

We have studied a recurrent luminous SSS in NGC300 with XMM-Newton. The source was seen by ROSAT in 1992 and fell below the detection limit in subsequent ROSAT observations. It reappeared in recent XMM-Newton observations with bolometric luminosities between $`10^{38}`$ and $`10^{39}`$$`\text{erg}\text{s}^1`$. During the “low” state, the source showed a 5.4-hr periodicity. If we consider the periodicity is due to the orbital period, then the X-ray emission can be explained by WD, BH, and NS models. However, WD and NS models appear to be unlikely due to the high X-ray luminosity during the “high” state. Further repeated X-ray observations of the SSS in different states may permit discrimination among these models.

This work was supported by NASA under an LTSA grant, NAG5-10705. A.K.H.K. acknowledges support from the Croucher Foundation.


text:
# Eutactic quantum codes

## Abstract

We consider sets of quantum observables corresponding to eutactic stars. Eutactic stars are systems of vectors which are the lower-dimensional “shadow” image, the orthogonal view, of higher-dimensional orthonormal bases. Although these vector systems are not comeasurable, they represent redundant coordinate bases with remarkable properties. One application is quantum secret sharing.

quantum information theory

The increased experimental feasibility to manipulate single or few particle quantum states, and the theoretical concentration on the algebraic properties of the mathematical models underlying quantum mechanics have stimulated a wealth of applications in information and computation theory Gruska (1999); Nielsen and Chuang (2000). In this line of reasoning, we shall consider quantized systems which are in a coherent superposition of constituent states in such a way that only the coherent superposition of these pure states is in a predefined state; whereas one or all of the constituent states are not. Heuristically speaking, only the coherently combined states yield the “encoded message,” the constituents or “shares” do not.

This feature could be compared to “quantum secret sharing” schemes Hillery et al. (1999); Cleve et al. (1999); Gottesman (2000); Terhal et al. (2001); DiVincenzo et al. (2002), as well as to “entangled entanglement scenarios Krenn and A.Zeilinger (1996); Cereceda (1997). There, mostly entangled multipartite system are investigated. Thus, while the above cases concentrate mainly on quantum entanglement, in what follows quantum coherence will be utilized: in the secret-sharing scheme proposed here, one party receives part of a quantum state and the other party receives the other part. The parts are components of a vector lying in subspaces of a higher-dimensional Hilbert space. While the possible quantum states to be sent are orthogonal, the parts are not, so that the parties must put their parts together to decipher the message.

We shall deal with the general case first and consider examples later. Consider an orthonormal basis $`=\{𝐞_1,\mathrm{},𝐞_n\}`$ of the $`n`$-dimensional real Hilbert space $`^n`$ \[whose origin is at $`(0,\mathrm{},0)`$\]. Every point $`𝐱`$ in $`^n`$ has a coordinate representation $`x_i=𝐱𝐞_i`$, $`i=1,\mathrm{},n`$ with respect to the basis $``$. Hence, any vector from the origin $`𝐯=𝐱`$ has a representation in terms of the basis vectors given by $`𝐯=_{i=1}^n𝐯𝐞_𝐢𝐞_𝐢=𝐯_{i=1}^n[𝐞_{𝐢}^{}{}_{}{}^{T}𝐞_𝐢]`$, where the matrix notation has been used, in which $`𝐞_𝐢`$ and $`𝐯`$ are row vectors and ”T” indicates transposition. ($``$ and the matrix $`[𝐞_{𝐢}^{}{}_{}{}^{T}𝐞_𝐢]`$ stands for the scalar product and the dyadic product of the vector $`𝐞_𝐢`$ with itself, respectively). Hence, $`_{i=1}^n[𝐞_{𝐢}^{}{}_{}{}^{T}𝐞_𝐢]=𝕀_n`$, where $`𝕀_n`$ is the $`n`$-dimensional identity matrix.

Next, consider more general, redundant, bases consisting of systems of “well-arranged” linear dependent vectors $`=\{𝐟_1,\mathrm{},𝐟_m\}`$ with $`m>n`$, which are the orthogonal projections of orthonormal bases of $`m`$\- (i.e., higher-than-$`n`$-) dimensional Hilbert spaces. Such systems are are often referred to as eutactic stars Schläfli (1901); Hadwiger (1940); Coxeter (1973); Seidel (1976); Hasse and Stachel (1996). When properly normed, the sum of the dyadic products of their vectors yields unity; i.e., $`_{i=1}^m[𝐟_{𝐢}^{}{}_{}{}^{T}𝐟_𝐢]=𝕀_n`$, giving raise to redundant eutactic coordinates $`x_i^{}=𝐱𝐟_i`$, $`i=1,\mathrm{},m>n`$. Indeed, many properties of operators and tensors defined with respect to standard orthonormal bases directly translate into eutactic coordinates Hasse and Stachel (1996).

In terms of $`m`$-ary (radix $`m`$) measures of quantum information based on state partitions Svozil (2002), $`k`$ elementary $`m`$-state systems can carry $`k`$ nits Zeilinger (1999); Brukner and Zeilinger (1999); Donath and Svozil (2002). A nit can be encoded by the one-dimensional subspaces of $`^m`$ spanned by some orthonormal basis vectors $`^{}=\{𝐞_1,\mathrm{},𝐞_m\}`$. In the quantum logic approach pioneered by Birkhoff and von Neumann (e.g., Birkhoff and von Neumann (1936); von Neumann (1932); Mackey (1963); Svozil (1998)), every such basis vector corresponds to the physical proposition that “the system is in a particular one of $`m`$ different states.” All the propositions corresponding to orthogonal base vectors are comeasurable.

On the contrary, the propositions corresponding to the eutactic star

$$=\{P𝐞_1,\mathrm{},P𝐞_m\}$$

formed by some orthogonal projection $`P`$ of $`^{}`$ is no longer comeasurable (or it just spans a one-dimensional subspace). Neither is the eutactic star

$$^{}=\{P^{}𝐞_1,\mathrm{},P^{}𝐞_m\}$$

formed by the orthogonal projection $`P^{}`$ of $`^{}`$. Indeed, the elements of $``$ and $`^{}`$ may be considered as “shares” in the context of quantum secret sharing. Thereby, not all shares may be equally suitable for cryptographic purposes. This scenario can be generalized to multiple shares in a straightforward way.

Let us consider an example for a two-component two-share configuration, in which each party obtains one substate from two possible ones. In particular, consider the two shares $`\{𝐰,𝐱\}`$ and $`\{𝐲,𝐳\}`$ defined in fourdimensional complex Hilbert space by

$$\begin{array}{cccc}𝐰=(0,0,\frac{1}{2\sqrt{2}},\frac{1}{\sqrt{2}}),& 𝐱=\frac{1}{2}(0,0,\frac{3}{2},1),& & \\ 𝐲=\frac{1}{2}(\frac{1}{\sqrt{2}},1,0,0),& 𝐳=\frac{1}{2\sqrt{2}}(\frac{1}{\sqrt{2}},1,0,0),& & \end{array}$$
(1)
While $`\{𝐰,𝐱\}`$ and $`\{𝐲,𝐳\}`$ constitute eutactic stars in $`^2`$, the coherent superposition of $`𝐰`$ with $`𝐲`$, and $`𝐱`$ with $`𝐳`$ yield two orthogonal vectors in $`^4`$

$$\{𝐰+𝐲,𝐱+𝐳\}=\{\frac{1}{2}(\frac{1}{\sqrt{2}},1,\frac{1}{\sqrt{2}},\sqrt{2}),\frac{1}{2}(\frac{1}{2},\frac{1}{\sqrt{2}},\frac{3}{2},1)\}$$
(2)
which could be used as a bit representation. As can be readily verified, the shares in (1) are obtained by applying the projections $`P=\mathrm{diag}(1,1,0,0)`$ and $`P^{}=\mathrm{diag}(0,0,1,1)`$ to the vectors in (2) \[“$`\mathrm{diag}(a,b,\mathrm{})`$” stands for the diagonal matrix with $`a,b,\mathrm{}`$ at the diagonal entries\]. The comeasurable projection operators corresponding to the vectors in (2) are given by

$`\left[(𝐰+𝐲)^T(𝐰+𝐲)\right]`$ $`=`$ $`{\displaystyle \frac{1}{4}}\left(\begin{array}{ccccccc}\frac{1}{2}& \frac{1}{\sqrt{2}}& \frac{1}{2}& 1& & & \\ \frac{1}{\sqrt{2}}& 1& \frac{1}{\sqrt{2}}& \sqrt{2}& & & \\ \frac{1}{2}& \frac{1}{\sqrt{2}}& \frac{1}{2}& 1& & & \\ 1& \sqrt{2}& 1& 2& & & \end{array}\right)\mathrm{and}`$ (7)
$`\left[(𝐱+𝐳)^T(𝐱+𝐳)\right]`$ $`=`$ $`{\displaystyle \frac{1}{4}}\left(\begin{array}{cccccc}\frac{1}{4}& \frac{1}{2\sqrt{2}}& \frac{3}{4}& \frac{1}{2}& & \\ \frac{1}{2\sqrt{2}}& \frac{1}{2}& \frac{3}{2\sqrt{2}}& \frac{1}{\sqrt{2}}& & \\ \frac{3}{4}& \frac{3}{2\sqrt{2}}& \frac{9}{4}& \frac{3}{2}& & \\ \frac{1}{2}& \frac{1}{\sqrt{2}}& \frac{3}{2}& 1& & \end{array}\right),`$ (12)
whereas the shares given to the parties are not comeasurable; i.e., $`[𝐰^T𝐰][𝐱^T𝐱][𝐱^T𝐱][𝐰^T𝐰]0`$, and $`[𝐲^T𝐲][𝐳^T𝐳][𝐳^T𝐳][𝐲^T𝐲]0`$. Only after recombining the shares it is possible to reconstruct the information; i.e., to decide whether $`(𝐰+𝐲)`$ or $`(𝐱+𝐳)`$ has been communicated. This configuration demonstrates the protocol, but it is not optimal, as four dimensions have been used to represent a single bit. A more effective coding in base four could utilize the additional two “quadrit” states $`(1/2)(1,\sqrt{2},1,0)`$ and $`(1/2)(3/2,1/\sqrt{2},1/2,1)`$.

A possible experimental realization of an arbitrary $`m`$-dimensional configuration could be a general interferometer with $`m`$ inputs and $`m`$ output terminals Reck et al. (1994), which are partitioned according to the orthogonal projections involved. They should be arranged in such a way that the single input/output terminals each correspond to one dimension. Consider, for example, the two-component two-share configuration discussed above. The two bit states (2) can be constructed from the orthogonal pair of vectors $`𝐞_1=(0,0,0,1)`$ and $`𝐞_2=(1,0,0,0)`$ by subjecting them to four successive rotations in two-dimensional subspaces of $`^4`$; i.e., $`𝐰+𝐲=R_{13}(\pi /4)R_{12}(\pi /4)R_{14}(\pi /4)R_{13}(\pi /4)𝐞_1`$ and $`𝐱+𝐳=R_{13}(\pi /4)R_{12}(\pi /4)R_{14}(\pi /4)R_{13}(\pi /4)𝐞_2`$, where $`R_{12}`$, $`R_{14}`$, $`R_{13}`$ represent the usual clockwise rotations in the 1–2, 1–4, and 1–3 planes. The corresponding (lossless) interferometric configuration is depicted in Fig. 1; the boxes standing for a 50:50 mixing.

The encoding phase depicted in Fig. 1(a) consist of either inserting a particle into the first or the fourth terminal. Formally, its state undergoes the particular types of mixing transformations outlined above. Finally, the two upper and two lower exit terminals are subdivided into the two shares. The decoding phase depicted in Fig. 1(b) requires both shares, which are recombined in a reverse interferometric setup, in which the original states are reconstructed by performing the reverse mixings in reverse order.

Some configurations are not usable for secret sharing. The “worst case” scenario might be one in which the first share coincides with a basis vector of the orthonormal basis spanning $`^m`$. In this case, the second share just consists of the remaining base states, making possible the detection of the original message. Take, for instance, the basis $`\{(0,0,1),(0,1,0),(1,0,0)\}`$ which, when projected along the $`z`$-axis, results in the shares $`\left\{(0,0,1)\right\}`$ and $`\{(0,1,0),(1,0,0)\}`$. These shares enable the parties to deterministically discriminate between the first state and the rest (first share), and between all states (second share).

A simple setup would correspond to a two-dimensional case, in which a particle would enter one of two input ports. A successive beam splitter would then scramble the original signal. In this setup, the two shares would just correspond to the two output ports of the beam splitter. Even though both parties would know that the other party would possess a one-dimensional share, due to phase coherence it would not be possible in a straightforward manner to reconstruct the secret message by manufacturing the missing one-component share.

As has already been pointed out, the proposed scheme does not necessarily involve entangled multipartite states; thus the parties are not given particles as shares. Rather, in the interferometric realization they are given interferometric channels; and in order to reconstruct the original message, it is important to keep quantum coherence among all the parties. Thus, in the encrypted stage, that is, before the decoding, no particle detection is allowed, since this would destroy coherence. The decoding transformation is the coherent combination of the two shares whose channels each correspond, respectively, to one and only one secret message.

Here we have proposed to look into possibilities to utilize the higher-dimensional components of the quantum state by combining two or more states defined in effectively lower-dimensional subspaces. Only after all parties have put their parts of the states together, are they able to decypher the message. The “extra dimensions” not used by the “flattened out” subspaces might be very useful for other purposes as well. For instance, one might speculate that they could be exploited for computational purposes such as speedups; analogously to the introduction of the complex plane for the solution of certain problems, such as integrals, in analysis. There, the challenge might be to extend the existing quantum algorithms to higher dimensions, thereby exploiting multidimensional connectedness in search spaces and the like, and at the same time being able to reconstruct the results in lower dimensions.