text:
# 1 Introduction

## 1 Introduction

The $`q`$-state Potts antiferromagnet (PAF)  exhibits nonzero ground state entropy, $`S_0>0`$ (without frustration) for sufficiently large $`q`$ on a given lattice $`\mathrm{\Lambda }`$ or, more generally, on a graph $`G`$. This is equivalent to a ground state degeneracy per site $`W>1`$, since $`S_0=k_B\mathrm{ln}W`$. Such nonzero ground state entropy is important as an exception to the third law of thermodynamics . One physical example is provided by ice, for which the residual molar entropy is $`S_0=0.82\pm 0.05`$ cal/(K-mole), i.e., $`S_0/R=0.41\pm 0.03`$, where $`R=N_{Avog.}k_B`$ . Indeed, residual entropy at low temperatures has been observed in a number of molecular crystals, including nitrous oxide, NO and FClO3 (a comprehensive review is given in Ref. ). In these physical examples, the entropy occurs without frustration, i.e., the configurational energy can be minimized, just as in the Potts antiferromagnet for sufficiently large $`q`$.

There is a close connection with graph theory here, since the zero-temperature partition function of the above-mentioned $`q`$-state Potts antiferromagnet on a graph $`G=(V,E)`$ satisfies

$$Z(G,q,T=0)_{\mathrm{PAF}}=P(G,q)$$
(1.1)
where $`G`$ is defined by its set of vertices $`V`$ and edges $`E`$ and $`P(G,q)`$ is the chromatic polynomial expressing the number of ways of coloring the vertices of $`G`$ with $`q`$ colors such that no two adjacent vertices have the same color (for reviews, see -). The minimum number of colors necessary for such a coloring of $`G`$ is called the chromatic number, $`\chi (G)`$. Thus

$$W(\{G\},q)=\underset{n\mathrm{}}{lim}P(G,q)^{1/n}$$
(1.2)
where $`n=|V|`$ is the number of vertices of $`G`$ and we denote the formal infinite-length limit of strip graphs of type $`G`$ as $`\{G\}=lim_n\mathrm{}G`$. At certain special points $`q_s`$ (typically $`q_s=0,1,..,\chi (G)`$), one has the noncommutativity of limits

$$\underset{qq_s}{lim}\underset{n\mathrm{}}{lim}P(G,q)^{1/n}\underset{n\mathrm{}}{lim}\underset{qq_s}{lim}P(G,q)^{1/n}$$
(1.3)
and hence it is necessary to specify the order of the limits in the definition of $`W(\{G\},q_s)`$. Denoting $`W_{qn}`$ and $`W_{nq}`$ as the functions defined by the different order of limits on the left and right-hand sides of (1.3), we take $`WW_{qn}`$ here; this has the advantage of removing certain isolated discontinuities that are present in $`W_{nq}`$. Using the expression for $`P(G,q)`$, one can generalize $`q`$ from $`_+`$ to $``$. The zeros of $`P(G,q)`$ in the complex $`q`$ plane are called chromatic zeros; a subset of these may form an accumulation set in the $`n\mathrm{}`$ limit, denoted $``$, which is the continuous locus of points where $`W(\{G\},q)`$ is nonanalytic. For some families of graphs $``$ may be null, and $`W`$ may also be nonanalytic at certain discrete points. The maximal region in the complex $`q`$ plane to which one can analytically continue the function $`W(\{G\},q)`$ from physical values where there is nonzero ground state entropy is denoted $`R_1`$. The ground state degeneracy per site $`W(\{G\})`$ is an analytic function of real $`q`$ from large values down to the value $`q_c`$, which is the maximal value where $``$ intersects the (positive) real axis. For some families of graphs, $``$ does not cross or intersect the real $`q`$ axis; in these cases, no $`q_c`$ is defined. However, even in cases where no such intersection occurs, $``$ often includes complex-conjugate arcs with endpoints close to the positive real axis, and hence, in these cases, it can be useful to define a quantity $`(q_c)_{\mathrm{eff}}`$ equal to the real part of the endpoints. We shall use this definition here.

In this work we present exact solutions for chromatic polynomials $`P(G,q)`$ for sections of the simple cubic (sc) lattice with fixed transverse size $`L_x\times L_y`$ and arbitrarily great length $`L_z`$, for cross sections $`L_x\times L_y=3\times 2`$ and $`4\times 2`$. These calculations are carried out for the cases (a) $`(FBC_x,FBC_y,FBC_z)`$ (rectangular solid) and (b) $`(PBC_x,FBC_y,FBC_z)`$ (homeomorphic to an annular cylindrical solid), where $`FBC_i`$ and $`PBC_i`$ denote free and periodic boundary conditions in the $`i`$’th direction, respectively. We shall use the notation $`(L_i)_\mathrm{F}`$ and $`(L_i)_\mathrm{P}`$ to denote free and periodic boundary conditions in the $`i`$’th direction, so that, for example, the $`3\times 2\times L_z`$ sections of the simple cubic lattice with the boundary conditions of type (a) and (b) are denoted $`3_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$ and $`3_\mathrm{P}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$, respectively. For each family of graphs, taking the infinite-length limit $`L_z\mathrm{}`$, we calculate $`W(\{G\},q)`$, $``$, and hence $`q_c`$.

We also present corresponding results for a tube of arbitrarily great length whose transverse cross section is formed from the complete bipartite graph $`K_{m,m}`$, for the cases $`m=2`$ and 3. Here the complete graph $`K_n`$ is defined as the graph consisting of $`n`$ vertices such that each vertex is connected by edges (bonds) to every other vertex, and the complete bipartite graph $`K_{m,n}`$ is defined as the join $`K_m+K_n`$, where the join of two graphs $`G`$ and $`H`$, denoted $`G+H`$ is the graph obtained by joining each of the vertices of $`G`$ to each of the vertices of $`H`$. Although the complete bipartite graphs are not regular lattices as studied in statistical mechanics, they are useful since they allow us to obtain exact results for cases of high effective coordination number.

There are several motivations for this work. We have mentioned the basic importance of nonzero ground state entropy in statistical mechanics and physical examples of this phenomenon. From the point of view of rigorous statistical mechanics, exact analytic solutions are always valuable since they complement results from approximate series expansions and numerical methods. We have defined the point $`q_c`$ above in terms of the function $`W(\{G\},q)`$. This point has another important physical significance: for the $`n\mathrm{}`$ limit of a given family of graphs, $`\{G\}`$, the $`q`$-state Potts antiferromagnet has no finite-temperature phase transition but is disordered for all $`T0`$ if $`q>q_c(\{G\})`$, and has a zero-temperature critical point for $`q=q_c(\{G\})`$ . For the Potts model on the (infinite) square lattice, via a mapping to a vertex model, it has been concluded that $`q=3`$ . However, the value of $`q_c`$ is not known for any lattice of dimension three or higher. One of the main motivations for our study is the insight that one gains concerning the dependence of $`q_c`$ on the coordination number $`\mathrm{\Delta }=2d`$ of a $`d`$-dimensional Cartesian lattice $`𝔼^d`$ for the case $`d=3`$. Furthermore, although infinite-length sections of higher-dimensional lattices with fixed finite $`(d1)`$-dimensional volume transverse to the direction in which the length goes to infinity are quasi-one-dimensional systems and hence (for finite-range spin-spin interactions) do not have finite-temperature phase transitions, their zero-temperature critical points are of interest. Finally, in addition to the physics motivations, the present results are of interest in mathematical graph theory. Some related earlier work is in Refs. -.

Our exact calculations of $`q_c`$ for the infinite-length limits of tube sections of the simple cubic lattice yield information relevant to estimates of $`q_c`$ for the infinite cubic lattice. The point here is that as the area of the transverse cross section of the tube increases to infinity, the corresponding sequence of exact $`q_c`$ or $`(q_c)_{\mathrm{eff}}`$ values is expected to converge to a limit. For the tube sections considered here, which have free longitudinal boundary conditions, this limit is a lower bound for the true $`q_c`$ of the infinite simple cubic lattice. The reason that one can only say that it is a lower bound is that for these families with free longitudinal boundary conditions the respective limiting curve $``$ exhibits a complex-conjugate pair of prongs that protrude to the right. It is possible that, as the area of the transverse cross section goes to infinity, the endpoints of these prongs will extend over and meet on the real axis, thereby defining a point $`q_c`$ which could lie to the right of the limit of the $`q_c`$ points for each of the tubes with finite transverse cross section. In this case, $`lim_{L_x,L_y\mathrm{}}q_c(sc,(L_x)_{BCx}\times (L_y)_{BCy}\times \mathrm{}_\mathrm{F})`$ is not equal to, but instead less than, the value $`q_c(sc)`$ for the infinite simple cubic lattice. Indeed, for finite-width, infinite-length strips of the triangular lattice with free longitudinal ($`z`$) boundary conditions and periodic transverse $`y`$ boundary conditions, $`lim_{L_y\mathrm{}}q_c((L_y)_\mathrm{P}\times \mathrm{}_\mathrm{F})3.81967\mathrm{}`$ while $`q_c=4`$ for the infinite triangular lattice . This occurs because of the above-mentioned phenomenon in which the endpoints of the complex-conjugate pair of prongs protruding to the right on the limiting curve $``$ move inward toward the real axis and, as $`L_y\mathrm{}`$, finally touch each other, thereby defining the true $`q_c=4`$ about 5 % greater than the above limit at $`3.82`$. The presence of these types of prongs protruding to the right on the limiting curves was also observed for a variety of infinite-length, finite-width 2D lattice strips with free longitudinal boundary conditions (for both free and periodic transverse boundary conditions) . Calculations for $`L_\mathrm{P}\times \mathrm{}_\mathrm{F}`$ (i.e. cylindrical) strips of the square lattice have been carried out in  with widths $`L`$ extending up to 13 , with $`q_c(sq,13_\mathrm{P}\times \mathrm{}_\mathrm{F})2.916`$. This value is within about 3 % of the value for the infinite square lattice, $`q_c(sq)=3`$. As the width increases, the endpoints of the prongs do move in toward the real axis. These calculations for $`L_\mathrm{P}\times \mathrm{}_\mathrm{F}`$ strips of the square lattice are consistent with either of the two possibilities, that $`lim_L\mathrm{}q_c(sq,L_\mathrm{P}\times \mathrm{}_\mathrm{F})`$ is equal to, or slightly less than, $`q_c(sq)`$.

It is interesting that the exact calculations of the singular loci $``$ for infinite-length, finite-width strips of various lattices with periodic longitudinal boundary conditions  (and either free or periodic transverse boundary conditions) yielded loci without such complex-conjugate prongs (or line segments on the real axis) . For these families of strips it was found that $``$ always crossed the positive real axis at $`q=0`$ and at a maximal point, so $`q_c`$ is always defined; furthermore, $`L_\mathrm{F}\times \mathrm{}_\mathrm{P}`$, the value of $`q_c`$ is a monotonically nondecreasing function of the width. For $`L_\mathrm{P}\times \mathrm{}_\mathrm{P}`$ strips, although $`q_c`$ is not a nondecreasing function of the width, it is, for a given width, closer to the value for the infinite 2D lattice if one uses periodic, rather than free transverse boundary conditions, as one would expect since the former minimize finite-size effects.

Some definitions from graph theory will be useful here. The degree of a vertex in a graph $`G=(V,E)`$ is the number of edges to which it is attached. A graph $`G`$ defined to be $`\mathrm{\Delta }`$-regular iff each of its vertices has the same degree, $`\mathrm{\Delta }`$. This is, in particular, true of an infinite regular lattice, where this degree is the coordination number. Even if some vertices have different degrees from others, one can define an effective coordination number,

$$\mathrm{\Delta }_{\mathrm{eff}}=\underset{|V|\mathrm{}}{lim}\frac{2|E|}{|V|}.$$
(1.4)
For example, for a strip of the square lattice of size of the type $`(L_x)_\mathrm{F}\times (L_y)_\mathrm{F}`$, in the limit in which the length $`L_x\mathrm{}`$ with fixed finite width, $`L_y`$,

$$\mathrm{\Delta }_{\mathrm{eff}}(sq,(L_x)_\mathrm{F}\times (L_y)_\mathrm{F};L_x\mathrm{})=4\frac{2}{L_y}.$$
(1.5)
For the same strip, but with periodic transverse boundary conditions, if $`L_y3`$ to avoid double edges, we have

$$\mathrm{\Delta }_{\mathrm{eff}}(sq,(L_x)_\mathrm{F}\times (L_y)_\mathrm{P};L_x\mathrm{})=4.$$
(1.6)
For the $`(L_x)_\mathrm{F}\times (L_y)_\mathrm{F}\times (L_z)_\mathrm{F}`$ section of the simple cubic lattice with free boundary conditions in all three directions, the interior vertices have degree 6, the vertices on the surface away from the corners have degree 4, and the corner-vertices have degree 3. For the minimal case $`2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$, there are no interior vertices in the 3D sense, so that

$$\mathrm{\Delta }_{\mathrm{eff}}(sc,2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F};L_z\mathrm{})=4.$$
(1.7)
For the next case $`(L_x)_F\times 2_F\times (L_z)_\mathrm{F}`$ with $`L_x3`$ there are also no interior vertices in the 3D sense; in this case

$$\mathrm{\Delta }_{\mathrm{eff}}(sc,(L_x)_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F};FBC_x,FBC_y,FBC_z;L_z\mathrm{})=5\frac{2}{L_x}.$$
(1.8)
For the $`L_z\mathrm{}`$ limit of the $`L_x\times L_y\times L_z`$ section with $`L_x3`$, $`L_y3`$, we have

$$\mathrm{\Delta }_{\mathrm{eff}}(sc,(L_x)_\mathrm{F}\times (L_y)_\mathrm{F}\times (L_z)_\mathrm{F};L_z\mathrm{})=62\frac{(L_x+L_y)}{L_xL_y}.$$
(1.9)
We shall also use the corresponding formulas when periodic rather than free boundary conditions are imposed in one of the transverse directions. Of course, in the usual thermodynamic limit of the Cartesian lattice $`𝔼^d`$, with $`L_i\mathrm{}`$, $`i=1,..,d`$ and $`lim_{L_i\mathrm{}}L_i/L_j`$ equal to a finite nonzero constant, the effective degree is $`\mathrm{\Delta }_{\mathrm{eff}}(𝔼^d)=2d`$ independent of boundary conditions. In this case, although free boundary conditions in one or more directions entails vertices of lower degree than $`2d`$, these vertices occupy a vanishing fraction of the total vertices in the thermodynamic limit. Concerning the chromatic number, for the sections of 3D lattices considered here, we have

$$\chi (sc,(L_x)_\mathrm{F}\times (L_y)_\mathrm{F}\times (L_z)_\mathrm{F})=2$$
(1.10)
i.e., these graphs are bipartite. For the sections of the simple cubic lattice with periodic boundary conditions in one of the transverse direction, taking this to be the $`x`$ direction with no loss of generality,

$$\chi (sc,(L_x)_\mathrm{P}\times (L_y)_\mathrm{F}\times (L_z)_\mathrm{F})=\{\begin{array}{cc}2\hfill & \text{if }L_x\text{ is even}\hfill \\ 3\hfill & \text{if }L_x\text{ is odd}\hfill \end{array}$$
(1.11)
For an infinite regular lattice having coordination number $`\mathrm{\Delta }`$, a rigorous upper bound on $`q_c`$ was derived in  using the Dobrushin theorem:

$$q_c2\mathrm{\Delta }.$$
(1.12)
Aside from the general property that, for cases where there is a $`q_c`$, this point satisfies $`q_c2`$, we are not aware of a published lower bound on $`q_c`$.

We have noted that in the infinite-length limit of given family of lattice strip graphs, $``$ does not necessarily intersect or cross the real $`q`$ axis, and for such a family, there is no $`q_c`$. It has been found that for a graph consisting of a strip of a regular lattice, a sufficient condition for $``$ to cross the (positive) real $`q`$ axis is that there be periodic boundary conditions in the longitudinal direction, i.e., the direction in which the length goes to infinity as $`n\mathrm{}`$ -.

An interesting question is how $`q_c`$ depends on the lattice coordination number, equivalent to the vertex degree for an infinite lattice. For families of $`L_x\times L_y`$ lattice strip graphs with periodic longitudinal ($`L_x`$) boundary conditions, whose $`L_x\mathrm{}`$ limits are guaranteed to have a $`q_c`$, it is found that the value of $`q_c`$ is a nondecreasing function of the effective vertex degree $`\mathrm{\Delta }_{\mathrm{eff}}`$. Thus, for the family of cyclic strips of the square lattice with free transverse boundary conditions, besides the the $`1_F\times \mathrm{}_F`$ case with $`\mathrm{\Delta }=2`$ and $`q_c=2`$, one finds the following results: (i) $`2_F\times \mathrm{}_F`$ ($`\mathrm{\Delta }=3`$) yields $`q_c=2`$ , (ii) $`3_F\times \mathrm{}_F`$ ($`\mathrm{\Delta }_{\mathrm{eff}}=10/3`$) yields $`q_c2.3365`$ , (iii) $`3_F\times \mathrm{}_F`$ ($`\mathrm{\Delta }_{\mathrm{eff}}=7/2`$) yields $`q_c2.4928`$ . When one makes both the longitudinal and transverse boundary conditions periodic, the vertex degree is fixed. In this case, $`q_c`$ does not necessarily increase with increasing width, $`L_y`$. For example, for strips of the square lattice with toroidal boundary conditions and hence $`\mathrm{\Delta }=4`$, the $`3_P\times \mathrm{}_P`$ strip yields $`q_c=3`$  while the $`4_P\times \mathrm{}_P`$ strips yields the smaller value $`q_c2.78`$ .

When one considers strips without periodic longitudinal boundary conditions, there may or may not be a $`q_c`$. We have found that for strips with free transverse and longitudinal boundary conditions, $`q_c`$ or $`(q_c)_{\mathrm{eff}}`$, where the latter can be defined, is a monotonically increasing function of $`L_y`$, and since in these families of lattice strips, $`\mathrm{\Delta }_{\mathrm{eff}}`$ is a monotonically increasing function of $`L_y`$, this means that $`(q_c)_{\mathrm{eff}}`$ is also a monotonically increasing function of $`\mathrm{\Delta }_{\mathrm{eff}}`$. Thus, for $`1_F\times \mathrm{}_F`$ with $`\mathrm{\Delta }_{\mathrm{eff}}=2`$ and $`2_F\times \mathrm{}_F`$ with $`\mathrm{\Delta }_{\mathrm{eff}}=3`$, $`=\mathrm{}`$ and there is no $`(q_c)_{\mathrm{eff}}`$, while $`3_F\times \mathrm{}_F`$ with $`\mathrm{\Delta }_{\mathrm{eff}}=10/3`$ yields $`q_c=2`$ , $`4_F\times \mathrm{}_F`$ with $`\mathrm{\Delta }_{\mathrm{eff}}=7/2`$ yields $`q_c2.3014`$ , $`5_F\times \mathrm{}_F`$ with $`\mathrm{\Delta }_{\mathrm{eff}}=3.60`$ yields $`q_c2.428`$ , etc. up to $`8_F\times \mathrm{}_F`$ with $`\mathrm{\Delta }_{\mathrm{eff}}=3.75`$, which yields arc endpoints at $`q2.6603\pm 0.0013i`$ and hence $`(q_c)_{\mathrm{eff}}=2.6603`$ .

In contrast, for strips with free longitudinal and periodic transverse boundary conditions, $`\mathrm{\Delta }_{\mathrm{eff}}`$ is fixed, e.g., equal to 4 for strips of the square lattice. Insofar as one expects $`q_c`$ or $`(q_c)_{\mathrm{eff}}`$ to depend on $`\mathrm{\Delta }_{\mathrm{eff}}`$, it is not clear, a priori, how these quantities should behave as functions of $`L_y`$. Indeed, one finds that $`q_c`$ or $`(q_c)_{\mathrm{eff}}`$ have no monotonic dependence on $`L_y`$. For example, for $`3_P\times \mathrm{}_F`$, $`=\mathrm{}`$, $`4_P\times \mathrm{}_F`$ yields $`q_c2.3517`$ , $`5_P\times \mathrm{}_F`$ yields $`q_c2.6917`$ , but $`6_P\times \mathrm{}_F`$ yields $`q_c2.6132`$ . For $`7_P\times \mathrm{}_F`$, $``$ has arc endpoints near the real axis at $`q2.7515\pm 0.0025i`$, so $`(q_c)_{\mathrm{eff}}2.7515`$ . For the cases $`(L_y)_P\times \mathrm{}`$ up to $`L=11`$, it is found empirically that $`q_c`$ or $`(q_c)_{\mathrm{eff}}`$ is monotonically increasing separately for the even-$`L_y`$ and odd-$`L_y`$ sequences .

Since $`q_c`$ has thermodynamic significance as the value of $`q`$ above which the Potts antiferromagnet has no finite-temperature phase transition and is disordered even at $`T=0`$, the value of $`q_c`$ for a lattice with dimensionality $`d2`$ should be independent of the boundary conditions used to take the thermodynamic limit. (Strictly speaking, this is not true for $`d=1`$, since no $`q_c`$ is defined for the infinite-length limit of the line graph, while $`q_c=2`$ for the infinite-length limit of the circuit graph, but this may be considered to be an exception due to the special nature of this graph.) For the infinite 2D lattices where $`q_c`$ is known exactly, it is also a monotonically increasing function of the lattice coordination number. Specifically, as noted above, on the square lattice ($`\mathrm{\Delta }=4`$), one has $`q_c=3`$ . For the kagomé lattice, again with $`\mathrm{\Delta }=4`$, one finds $`q_c=3`$ , and on the triangular lattice with $`\mathrm{\Delta }=6`$, one has $`q_c=4`$ .

These exact results are all consistent with the inference that the value of $`q_c`$ increases as a function of the coordination number for the thermodynamic limit of a regular lattice or, more generally, for infinite-length strips or tubes of regular lattices with prescribed boundary conditions in the transverse directions. A plausibility argument for this is as follows. For $`q>q_c`$, the zero-temperature Potts antiferromagnet has nonzero ground state entropy per site, $`S=k_B\mathrm{ln}W>0`$, i.e., ground state degeneracy per site $`W>1`$. This entropy reflects the fact that the number of ways of carrying out a proper coloring of the lattice or lattice strip increases exponentially with the number of vertices. Roughly speaking, the constraint that no two adjacent vertices can be assigned the same color is more restrictive the greater the number of neighboring vertices there are, i.e., the greater $`\mathrm{\Delta }_{\mathrm{eff}}`$ is. Therefore, as one increases $`\mathrm{\Delta }_{\mathrm{eff}}`$ for a fixed $`q`$, $`W`$ decreases This is borne out by exact and numerical calculations of $`W`$ (for 2D lattices, see, e.g., Fig. 5 of  or Fig. 6 of ). In the context of $`d`$-dimensional Cartesian lattices, this means that $`q_c`$ should increase as a function of $`d`$. Such a monotonicity relation is valuable to have since the value of $`q_c`$ is not known exactly for lattices with dimension $`d3`$.

It is useful to define a ratio of the actual value of $`q_c`$ to the upper bound in (1.12), namely,

$$R_{q_c}=\frac{q_c}{2\mathrm{\Delta }}.$$
(1.13)
Evidently, $`R_{q_c}=0.5`$ for the infinite-length limit of the circuit graph and $`R_{q_c}=0.375`$ for the infinite square lattice. Similarly, for other exactly known cases, the actual value of $`q_c`$ is considerably less than the rigorous upper bound (1.12). This suggests that it may be possible to improve the upper bound (1.12).

A generic form for chromatic polynomials for a strip graph of type $`G_s`$, or, more generally, a recursive family of graphs composed of $`m`$ repetitions of a basic subgraph, is

$$P(G_s,m,q)=\underset{j=1}{\overset{N_{G_s,\lambda }}{}}c_{G_s,j}(q)(\lambda _{G_s,j}(q))^m$$
(1.14)
where $`c_{G_s,j}(q)`$ and the $`N_{G_s,\lambda }`$ terms (eigenvalues) $`\lambda _{G_s,j}(q)`$ depend on the type of strip graph $`G_s`$ including the boundary conditions but are independent of $`m`$. Here, $`N_\lambda dim(T)`$, where $`dim(T)`$ is the dimension of the transfer matrix in the Fortuin-Kasteleyn representation, and the difference, $`N_{0a}=dim(T)N_\lambda `$, is the number of zero amplitudes (coefficients). The coefficients $`c_{G_s,j}`$ can be regarded as the multiplicities of the eigenvalues $`\lambda _{G_s,j}`$ (for some real positive $`q`$ values, these coefficients can be zero or negative, so that this interpretation presumes a sufficiently large real positive $`q`$, followed by analytic continuation to other values of $`q`$).

## 2 Tubes of the Simple Cubic Lattice with Free Transverse Boundary Conditions

The computations of the transfer matrix and the chromatic polynomials were performed following the methods described in Section 3 of Ref. . The idea is to construct the partition function by building the lattice layer by layer. In all the computations we have chosen the Fortuin-Kasteleyn representation of the transfer matrix. Thus, our basis will be the connectivities of the top layer, whose basis elements $`𝐯_𝒫`$ are indexed by partitions $`𝒫`$ of the single-layer vertex set $`V^0`$. We shall abbreviate delta functions $`\delta (\sigma _1,\sigma _3)`$ as $`\delta _{1,3}`$. Moreover, we shall also abbreviate partitions $`𝒫`$ by writing instead the corresponding product $`𝐯_𝒫`$ of delta functions: e.g., in place of $`𝒫=\{\{1,3\},\{2,4\},\{5\}\}`$ we shall write simply $`𝒫=\delta _{1,3}\delta _{2,4}`$. The transfer matrix can be expressed as

$$𝖳=𝖵𝖧$$
(2.1)
where the matrices $`𝖧`$ and $`𝖵`$ are defined as

$`𝖧`$ $`=`$ $`{\displaystyle \underset{<xx^{}>E^0}{}}\left[IJ_{xx^{}}\right]`$ (2.2)
$`𝖵`$ $`=`$ $`{\displaystyle \underset{xV^0}{}}\left[I+D_x\right].`$ (2.3)
In these formulae $`E^0`$ is the single-layer edge set, and $`J_{x,x^{}}`$ and $`D_x`$ are respectively the “join” and “detach” operators whose action on the elements of the basis $`𝐯_𝒫`$ is as follows

$`J_{xx^{}}𝐯_𝒫`$ $`=`$ $`𝐯_{𝒫xx^{}}`$ (2.4)
$`D_x𝐯_𝒫`$ $`=`$ $`\{\begin{array}{cc}𝐯_{𝒫x}\hfill & \mathrm{if}\{x\}𝒫\hfill \\ q𝐯_𝒫\hfill & \mathrm{if}\{x\}𝒫\hfill \end{array}`$ (2.7)
where $`𝒫xx^{}`$ is the partition obtained from $`𝒫`$ by amalgamating the blocks containing $`x`$ and $`x^{}`$ (if they were not already in the same block); and $`𝒫x`$ is the partition obtained from $`𝒫`$ by detaching $`x`$ from its block (and thus making it what we term a “singleton”). In eq. (2.3) we have written the formulae for $`𝖧`$ and $`𝖵`$ in the zero-temperature Potts antiferromagnet limit; the general expressions can be found in .

Finally, the partition function can be written as

$$Z(L_x\times L_y\times L_z;q)=𝐮^\mathrm{T}𝖧(\mathrm{𝖵𝖧})^{L_z1}𝐯_{\mathrm{id}}$$
(2.8)
where “id” denotes the partition in which each site $`xV^0`$ is a singleton, and $`𝐮^\mathrm{T}`$ is defined by

$$𝐮^\mathrm{T}𝐯_𝒫=q^{|𝒫|}.$$
(2.9)
In the zero-temperature limit the horizontal operator $`𝖧`$ is a projection. This implies that we can work in its image subspace by using the modified transfer matrix $`𝖳^{}=\mathrm{𝖧𝖵𝖧}`$ in place of $`𝖳=\mathrm{𝖵𝖧}`$, and using the basis vectors

$$𝐰_𝒫=𝖧𝐯_𝒫$$
(2.10)
in place of $`𝐯_𝒫`$. Note that $`𝐰_𝒫=0`$ if $`𝒫`$ contains nay pair of nearest neighbors in the same block. In the following subsections we will list the basis $`𝐏=\{𝐯_𝒫\}`$, although we performed the actual computations with the basis $`\{𝐰_𝒫\}`$.

The computation of the limiting curves $``$ was performed with either the resultant and the direct-search methods (See ref.  for details). The computation of the zeros of the chromatic polynomials was done using the package MPSolve designed by Bini and Fiorentino , whose performance is superior to that of Mathematica for this particular task .

### 2.1 $`2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$ Section of the Simple Cubic Lattice

Before proceeding to our new results, we note the identity

$$sc(2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F})=sq(4_\mathrm{P}\times (L_z)_\mathrm{F}).$$
(2.1.1)
The left-hand side of this identity is evidently a tube of the simple cubic lattice with a minimal-size transverse cross section, viz., a single square; the right-hand side of the identity is a strip of the square lattice of width 4 squares, and periodic transverse boundary conditions. The chromatic polynomials for the family of graphs on the right-hand side of this identity were calculated in section 7 of  and, in the infinite-length limit, $`W`$ and $``$ were determined (see Fig. 3(a) of ). In Ref. , the longitudinal direction was taken as $`L_x`$, while we take it to be $`L_z`$ here. In -, a generating function formalism was developed and used; for a given strip graph $`G_s`$ of length $`m`$, the chromatic polynomial $`P((G_s)_m,q)`$ is given as the coefficient of $`z^m`$, where $`z`$ is the auxiliary expansion variable:

$$\mathrm{\Gamma }(G_s,q,z)=\underset{m=0}{\overset{\mathrm{}}{}}P((G_s)_m,q)z^m,$$
(2.1.2)
This generating function is a rational function of $`q`$ and $`z`$. For the strip considered here, of length $`L_z=m`$ edges,

$$\mathrm{\Gamma }(G_s,q,z)=\frac{a_0+a_1z}{1+b_1z+b_2z^2}$$
(2.1.3)
where

$$a_0=q(q1)(q^23q+3)$$
(2.1.4)
$$a_1=q(q1)(q^47q^3+16q^213q+5)$$
(2.1.5)
$$b_1=q^4+8q^329q^2+55q46$$
(2.1.6)
$$b_2=q^612q^5+61q^4169q^3+269q^2231q+85$$
(2.1.7)
(Here we have converted the numerator coefficients from  to be in accord with the labelling convention of eq. (2.1.2); in the labelling convention of , the strip with length $`m+1`$ edges.) The chromatic polynomial can equivalently be written as in 2.8: in the basis $`𝐏=\{1,\delta _{1,4}+\delta _{2,3}\}`$ it is given by

$$Z(2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F};q)=\left(\begin{array}{c}q(q1)(q^23q+3)\\ 2q(q1)^2\end{array}\right)^\mathrm{T}T(2_\mathrm{F}\times 2_\mathrm{F})^{L_z1}\left(\begin{array}{c}1\\ 0\end{array}\right)$$
(2.1.8)
The transfer matrix $`T(2_\mathrm{F}\times 2_\mathrm{F})`$ is equal to

$$T(2_\mathrm{F}\times 2_\mathrm{F})=\left(\begin{array}{cc}4151q+28q^28q^3+q^4& 2(12+14q6q^2+q^3)\\ 5+2q& 54q+q^2\end{array}\right)$$
(2.1.9)
Note that in general, we should have considered an additional element in the basis, namely the partition $`\delta _{1,4}\delta _{3,2}`$; however, its amplitude vanishes identically. This can be easily understood by noting that this particular graph (2.1.1) is planar and $`\delta _{1,4}\delta _{3,2}`$ is a crossing partition.

For this family, $``$ consists of two complex-conjugate arcs, a self-conjugate arc that crosses the real axis at $`q2.3026`$, and a line segment on this axis extending from $`q2.2534`$ to $`q2.3517`$, which latter point is thus $`q_c`$. It should be noted also that although this graph is included here as the minimal-transverse-size member of a family of $`L_x\times L_y\times L_z`$ sections of the simple cubic lattice, it is degenerate in the sense that it is actually planar, in contrast to the others that we shall study here. There are eight endpoints in $``$; two of them are given by the real values $`q2.3026`$ and $`q2.3517`$; the other six endpoints are the complex-conjugate pairs $`q0.7098\pm 2.0427i`$, $`q1.9923\pm 1.5942i`$, and $`q2.9953\pm 1.4266i`$.

### 2.2 $`3_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$ Section of Simple Cubic Lattice

The section of the simple cubic lattice with the next larger transverse cross section is the $`3_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$, or equivalently, $`2_\mathrm{F}\times 3_\mathrm{F}\times (L_z)_\mathrm{F}`$, family. For this family, the dimension of the transfer matrix is 13. (In general the transfer matrix has dimension 15, but two basis elements, namely $`\delta _{1,5}\delta _{2,6}\delta _{3,4}+\delta _{2,4}\delta _{3,5}\delta _{1,6}`$ and $`\delta _{1,3,5}\delta _{2,4,6}`$, can be eliminated as they have zero amplitudes.) Since the entries in the transfer matrix are rather long, we relegate them to the Mathematica file transfer\_sc.m that is available with this paper in the LASL cond-mat archive. We have computed the chromatic zeros for $`L_z=15`$ and 30, i.e., $`n=90`$ and 180 vertices, respectively. These are shown in Fig. 1. This value of $`L_z`$ is sufficiently large that these zeros give a reasonably accurate indication of the location of the asymptotic limiting curves comprising the locus $``$. As is generally true, for the larger value of $`L_z`$, and hence $`n`$, the chromatic zeros move slightly outward, approaching the limiting curve $``$ from smaller values of $`|q|`$.

The limiting curve $``$ consists of two complex-conjugate arcs, a self-conjugate arc that crosses the real $`q`$-axis at $`q2.8645`$, and a horizontal real segment from $`q2.8566`$ to $`q2.8723`$. This latter value corresponds to the value of $`q_c`$ for this family. This information is listed, together with that from other lattices, in Table 1. There are 16 endpoints: two are the real values $`q2.8566`$ and $`q2.8723`$; the other 14 are the complex-conjugated pairs: $`q0.2943\pm 1.9150i`$, $`q1.9371\pm 2.4040i`$, $`q2.6374\pm 1.0937i`$, $`q2.8250\pm 1.4087i`$, $`q2.6255\pm 1.4647i`$, $`q3.2410\pm 1.2920i`$, and $`q2.2645\pm 2.4605i`$. Finally, there are four T points at $`q2.670\pm 1.117i`$ and $`q2.689\pm 1.500i`$.

### 2.3 $`4_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$ Section of Simple Cubic Lattice

The section of the simple cubic lattice with the next larger transverse cross section is the $`4_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$, or equivalently, $`2_\mathrm{F}\times 4_\mathrm{F}\times (L_z)_\mathrm{F}`$, family. For this family, the dimension of the transfer matrix is 156. However, there are 20 basis elements that correspond to zero amplitudes, so the effective dimension of the transfer matrix is 136. This transfer matrix $`T(4_\mathrm{F}\times 2_\mathrm{F})`$, as well as the vectors $`𝐯`$ and $`𝐮_{\mathrm{id}}`$ can be found in the Mathematica file transfer\_sc.m. We have computed the chromatic zeros for $`L_z=20`$ and 40, i.e., $`n=160`$ and 320 vertices, respectively. These are shown in Fig. 2.

The limiting curve $``$ consists of eight complex-conjugate arcs; none of them crosses the real axis, so, strictly speaking, there is no value of $`q_c`$. However, we can define $`(q_c)_{\mathrm{eff}}3.1498`$. This value is larger than the corresponding value for the family $`3_\mathrm{F}\times 2_\mathrm{F}\times L_\mathrm{F}`$ $`q_c2.8723`$ and larger than the value for the square lattice $`q_c(sq)=3`$. There are 11 pairs of complex-conjugate endpoints: $`q0.073\pm 1.747i`$, $`q1.582\pm 2.845i`$, $`q1.684\pm 2.871i`$, $`q2.379\pm 2.503i`$, $`q2.513\pm 1.569i`$, $`q2.661\pm 1.816i`$, $`q2.697\pm 1.889i`$, $`q3.034\pm 1.367i`$, $`q3.035\pm 1.385i`$, $`q3.150\pm 0.002i`$, and $`q3.383\pm 1.157i`$. Finally, there are three pairs of complex-conjugate T points: $`q2.381\pm 2.404i`$, $`q2.695\pm 1.793i`$, and $`q2.972\pm 1.578i`$.

## 3 Tubes of the Simple Cubic Lattice with Transverse Periodic Boundary Conditions

The method we have used to compute the chromatic polynomials and the transfer matrix is the same as in Section 2. The only difference is that we enlarge the single-layer edge set $`E^0`$.

### 3.1 $`2_\mathrm{P}\times 2_\mathrm{P}\times (L_z)_\mathrm{F}`$ Section of Simple Cubic Lattice

This family has (trivially) the same chromatic polynomials as the family $`sc(2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F}`$. (This is not true for the finite-temperature Potts model partition function, or equivalently, the Tutte polynomial; however we only deal with the chromatic polynomial here.) Thus, the transfer matrix and chromatic polynomials are given respectively by (2.1) and (2.8).

### 3.2 $`3_\mathrm{P}\times 2_\mathrm{P}\times (L_z)_\mathrm{F}`$ Section of Simple Cubic Lattice

In general, finite-size artifacts are minimized if one uses periodic boundary conditions in as many directions as possible. Hence, it is useful to calculate $`P`$ and $``$ for the same section of the simple cubic lattice as in the previous section, but with periodic boundary conditions imposed on the longer of the two transverse directions. This family is again bipartite. In this case, the dimension of the transfer matrix is 4.

In the basis $`𝐏=\{1,\delta _{2,4}+\delta _{2,6}+\delta _{1,5}+\delta _{3,5}+\delta _{1,6}+\delta _{3,4},\delta _{1,5}\delta _{2,6}+\delta _{2,4}\delta _{3,5}+\delta _{3,4}\delta _{1,5}+\delta _{3,4}\delta _{2,6}+\delta _{1,6}\delta _{3,5}+\delta _{1,6}\delta _{2,4},\delta _{1,6}\delta _{3,4}+\delta _{1,5}\delta _{2,4}+\delta _{2,6}\delta _{3,5}\}`$, the transfer matrix can be written as

$$T(3_\mathrm{P}\times 2_\mathrm{P})=\left(\begin{array}{cccc}T_{11}& T_{12}& T_{13}& T_{14}\\ T_{21}& T_{22}& T_{23}& T_{24}\\ 1& 2(3+q)& 126q+q^2& 2(4+q)\\ 0& 2& 4(3+q)& 157q+q^2\end{array}\right)$$
(3.2.1)
where

$`T_{11}`$ $`=`$ $`10891578q+1054q^2417q^3+103q^415q^5+q^6`$ (3.2.2)
$`T_{12}`$ $`=`$ $`6(292+394q231q^2+74q^313q^4+q^5)`$ (3.2.3)
$`T_{13}`$ $`=`$ $`6(110117q+51q^211q^3+q^4)`$ (3.2.4)
$`T_{14}`$ $`=`$ $`3(154149q+60q^212q^3+q^4)`$ (3.2.5)
$`T_{21}`$ $`=`$ $`90+71q20q^2+2q^3`$ (3.2.6)
$`T_{22}`$ $`=`$ $`203189q+71q^213q^3+q^4`$ (3.2.7)
$`T_{23}`$ $`=`$ $`109+80q21q^2+2q^3`$ (3.2.8)
$`T_{24}`$ $`=`$ $`81+52q12q^2+q^3`$ (3.2.9)
The vectors $`𝐯`$ and $`𝐮_{\mathrm{id}}`$ are given by

$`𝐯`$ $`=`$ $`\left(\begin{array}{c}(2+q)(1+q)q(13+14q6q^2+q^3)\\ 6(2+q)^3(1+q)q\\ 6(2+q)^2(1+q)q\\ 3(3+q)(2+q)(1+q)q\end{array}\right)`$ (3.2.14)
$`𝐮_{\mathrm{id}}`$ $`=`$ $`\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)`$ (3.2.19)
We remark that in this case the most general basis contains an additional partition: $`\delta _{1,5}\delta _{2,6}\delta _{3,4}+\delta _{2,4}\delta _{3,5}\delta _{1,6}`$. This one can be dropped, as it corresponds to a vanishing amplitude.

We have computed the chromatic zeros for $`L_z=15`$ and 30, i.e., $`n=90`$ and 180, respectively. These are shown in Fig. 3. The limiting curve $``$ contains three pairs of self-conjugated arcs. Although the arcs do not cross the real axis, so that, strictly speaking, no $`q_c`$ is defined, $`(q_c)_{\mathrm{eff}}3.33`$, which is larger than the value $`q_c=3`$ for the square lattice. The locus $``$ has 12 endpoints: $`q0.5061\pm 2.6413i`$, $`q2.1301\pm 2.4407i`$, $`q3.0251\pm 2.5249i`$, $`q3.0412\pm 1.2643i`$, $`q2.9328\pm 1.1238i`$, and $`q3.3255\pm 0.01839i`$.

### 3.3 $`4_\mathrm{P}\times 2_\mathrm{P}\times (L_z)_\mathrm{F}`$ Section of Simple Cubic Lattice

In this case we have 56 basis elements. However, there are 11 trivial basis element that lead to a vanishing amplitude. The transfer matrix and the vectors $`𝐯`$ and $`𝐮_{\mathrm{id}}`$ are listed in the Mathematica file transfer\_sc.m. Among the other 45 basis elements, we have numerical indications that there are 19 additional vanishing amplitudes.

The limiting curve $``$ (see Fig. 4) contains eight self-conjugate arcs. As in the $`4_\mathrm{P}\times 2_\mathrm{P}\times \mathrm{}_\mathrm{F}`$ case, this locus does not actually cross the positive real $`q`$ axis, but again has endpoints that lie very close to this axis, and we obtain $`(q_c)_{\mathrm{eff}}3.36`$. As expected, this is larger than the value $`(q_c)_{\mathrm{eff}}3.33`$ that we found for the tube $`3_\mathrm{P}\times 2_\mathrm{P}\times \mathrm{}_\mathrm{F}`$. There are nine pairs of complex-conjugate endpoints: $`q0.095\pm 2.700i`$, $`q1.803\pm 3.031i`$, $`q2.176\pm 3.196i`$, $`q2.841\pm 1.954i`$, $`q2.910\pm 2.080i`$, $`q3.263\pm 1.333i`$, $`q3.279\pm 1.377i`$, $`q3.362\pm 0.006i`$, and $`q3.892\pm 1.542i`$. Finally, there is one pair of complex-conjugate T points: $`q3.204\pm 1.665i`$.

Another property that was observed in our earlier calculations of chromatic polynomials for strips of 2D lattices is that, for a given type of transverse boundary conditions, for infinite-length strips with free longitudinal boundary conditions, as the width increases, the number of arcs on $``$ increases and the endpoints of these arcs move in such a manner as to reduce the gaps between the arcs. Here we observe the same qualitative behavior as the area of the transverse cross section of the tube section increases. If this trend continues for progressively larger transverse widths or cross sectional areas, then the number of arcs could increase without bound as one approaches the respective infinite 2D or 3D lattices. Now in the two cases where the loci $``$ have been calculated exactly for regular lattices, namely the $`d=1`$ lattice (with periodic boundary conditions; for free boundary conditions, $`=\mathrm{}`$) and the triangular lattice (defined as the limit $`L\mathrm{}`$ of $`L_\mathrm{P}\times \mathrm{}_F`$ strips ), this locus has no prongs or endpoints. Thus, one could imagine that as the width or cross sectional area of the strips or tubes increases to infinity, the endpoints of arcs join so that the gaps between these arcs disappear, and prongs either have lengths that go to zero or have endpoints that join to form closed boundaries. We also observe that, for a given width or, for the present families of tube sections, for a given transverse cross sectional area, there tend to be fewer arcs when one uses periodic rather than free boundary conditions for the transverse direction(s). This is in accord with the fact that calculations for strips with periodic longitudinal boundary conditions  found no prongs (or line segments) on the respective loci $``$, i.e. in all cases studied, these loci did not contain endpoints. Finally, our calculations are consistent with the expectation that as the area of the transverse cross section goes to infinity, the outer envelope of the locus $``$ approaches a limit, which crosses the real axis at $`q=0`$, $`q_c(sc)`$, and other point(s) between these two.

## 4 Further Remarks on the Structure of $``$

In the introductory section, we discussed some differences in the locus $``$ that depend on whether one uses periodic or free longitudinal boundary conditions. Here we include some further remarks relevant to our present results. It has been established that the structure of $``$ inside of its outer envelope and, in particular, the question of whether and where it crosses the positive real axis between $`q=0`$ and $`q=q_c(\{G\})`$ are dependent upon the boundary conditions used. For example, exact calculations for $`L_\mathrm{F}\times \mathrm{}_\mathrm{P}`$ and $`L_\mathrm{P}\times \mathrm{}_\mathrm{P}`$ strips of the triangular lattice show that the respective loci $``$ cross the real axis at $`q=2`$ , corresponding to the fact that the Ising antiferromagnet has a (frustrated) $`T=0`$ critical point on these strips; however the loci $``$ obtained in  for $`L_\mathrm{P}\times \mathrm{}_\mathrm{F}`$ strips or in  for $`L_\mathrm{F}\times \mathrm{}_\mathrm{F}`$ strips of the triangular lattice do not, in general, cross the real axis at $`q=2`$, nor is this crossing obtained for the infinite-width limit of the cylindrical strips calculated in . Similarly, for $`L_\mathrm{F}\times \mathrm{}_\mathrm{P}`$ and $`L_\mathrm{P}\times \mathrm{}_\mathrm{P}`$ strips of the square lattice it was found that $``$ passes through $`q=0`$, $`q=2`$, and a maximal value, $`q=q_c(\{G\})`$ . In contrast, for the corresponding strips of the square lattice with free longitudinal boundary conditions, it has been found that $``$ does not contain $`q=0`$ or, in general, $`q=2`$, and while the arc endpoints nearest to the origin move toward this point as the width increases (leading to the inference that for infinite width, $``$ would pass through $`q=0`$), there is no analogous tendency of arcs on $``$ to elongate toward $`q=2`$ . There is also no tendency for the arcs on the loci $``$ for our tube sections of the simple cubic lattice with free longitudinal boundary conditions to move toward $`q=2`$ as the cross sectional area increases.

A second point concerns the positions of the leftmost arcs. We find from the exact calculations reported here that for the infinite-length tube sections of the simple cubic lattice of the form $`(L_x)_\mathrm{P}\times (L_y)_\mathrm{P}\times \mathrm{}_F`$ with sufficiently large transverse cross section, namely $`L_x=4`$, $`L_y=2`$, $``$ contains support in the $`Re(q)<0`$ half-plane. This suggests that for this family of tube sections of the simple cubic lattice with periodic transverse boundary conditions, as the transverse area $`L_xL_y\mathrm{}`$, the complex-conjugate curves on $``$ could approach the origin from the $`Re(q)<0`$ half-plane, as happens for the limit $`L\mathrm{}`$ of $`L_\mathrm{P}\times \mathrm{}_\mathrm{F}`$ strips of the triangular lattice  and sufficiently wide strips of the square lattice of the form $`L_\mathrm{F}\times \mathrm{}_\mathrm{F}`$ , $`L_\mathrm{P}\times \mathrm{}_\mathrm{F}`$ , and $`L_\mathrm{F}\times \mathrm{}_\mathrm{P}`$ .

## 5 Behavior of $`q_c`$ for $`𝔼^d`$ with large $`d`$

For the $`d`$-dimensional Cartesian lattice $`𝔼^d`$, Mattis suggested the ansatz

$$W(𝔼^n,q)1+\frac{(q2)^d}{(q1)^{d1}}.$$
(5.1)
This agrees with the general results $`W(\{C\},q)=q1`$ for $`d=1`$, and, for the square lattice $`𝔼^2`$ with $`q=3`$ yields the estimate $`W(sq,q=3)=3/2`$, which is within 4 % of the known result $`W(𝔼^2,q=3)=(4/3)^{3/2}=1.5396..`$ . Mattis addressed the question of $`d_c(q)`$, i.e. the lower critical dimensionality of the $`q`$-state Potts antiferromagnet, below which it is disordered for $`T0`$. An equation yielding $`d_c`$ as a function of $`q`$ can also be solved to yield $`q_c`$ as a function of $`d`$, so $`d_c(q)`$ and $`q_c(d)`$ constitute equivalent information about the system. Mattis argued that $`d_c(q)`$ could be estimated by noting that $`W`$ is a measure of disorder, and if it is significantly greater than 1, then the system would be sufficiently disordered that one would not expect there to be a phase transition at $`T0`$. Taking the criterion that $`W<2`$ as the demarcation value for which a zero-temperature phase transition could occur, this yields the result

$$d_c(q)=\frac{\mathrm{ln}(q1)}{\mathrm{ln}\left(\frac{(q1)}{(q2)}\right)}.$$
(5.2)
As noted, this may equivalently be regarded as an equation for $`q_c`$ as a function of $`d`$ and for $`d=3`$, this ansatz gives

$$q_c(d=3)4.15$$
(5.3)
Our exact results $`W`$ and $`q_c`$ for tube sections of the simple cubic are consistent with this estimate from the ansatz (5.1).

It is also of interest to ask what the behavior of $`q_c`$ is for large $`d`$ on Cartesian lattices. The ansatz (5.1) yields the asymptotic behavior

$$q_c\frac{d}{\mathrm{ln}d}\mathrm{for}d\mathrm{}.$$
(5.4)
This is in agreement with the upper bound (1.12)

$$q_c4d$$
(5.5)
and evidently is a smaller and smaller fraction of this upper bound as $`d`$ gets large, with

$$R_{q_c}\frac{1}{4\mathrm{ln}d}\mathrm{for}d\mathrm{}.$$
(5.6)
## 6 Family $`(K_{m,m})^{L_z}`$

It is also useful to calculate $``$ and study the dependence of $`q_c`$ on vertex degree for infinite-length limits of other families of tube graphs. We report calculations here for a family of tube graphs whose transverse cross section is the complete bipartite graph $`K_{m,m}`$. The graph $`K_{m,m}`$ is $`\mathrm{\Delta }`$-regular graphs with $`\mathrm{\Delta }=m`$. We construct our tubes with the $`K_{m,m}`$ transverse cross section connected lengthwise $`L_z`$ times, so that each vertex of one $`K_{m,m}`$ subgraph is connected “vertically” to the corresponding vertex of the next $`K_{m,m}`$. This recursive family of graphs is denoted as $`(K_{m,m})^{L_z}`$. The value of $`\mathrm{\Delta }_{\mathrm{eff}}`$ is for this family

$$\mathrm{\Delta }_{\mathrm{eff}}\left((K_{m,m})^{L_z};FBC_z;L_z\mathrm{}\right)=m+2.$$
(6.1)
The computational method is the same as in the simple-cubic families: the transfer matrix and the partition function are computed using the same formulae (2.1)/(2.8). The only difference is the single-layer edge set $`E^0`$.

### 6.1 Family $`(K_{2,2})^{L_z}`$

The family $`(K_{2,2})^{L_z}`$ is trivially equivalent to the family $`\mathrm{sq}(4_\mathrm{P}\times L_\mathrm{F})`$, so by (2.1.1) it is also equivalent to the family $`\mathrm{sc}(2_\mathrm{F}\times 2_\mathrm{F}\times (L_z)_\mathrm{F})`$ The transfer matrix, written in the basis $`𝐏=\{1,\delta _{1,2}+\delta _{3,4}\}`$, takes the same form as (2.1.9); and the partition function is equivalent to (2.1.8).

### 6.2 Family $`(K_{3,3})^{L_z}`$

The transfer matrix for the family $`(K_{3,3})^{L_z}`$ has dimension 5. In the basis $`𝐏=\{1,\delta _{1,2}+\delta _{1,3}+\delta _{2,3}+\delta _{4,5}+\delta _{4,6}+\delta _{5,6},\delta _{1,2,3}+\delta _{4,5,6},\delta _{1,2}\delta _{4,5}+\delta _{1,2}\delta _{4,6}+\delta _{1,2}\delta _{5,6}+\delta _{1,3}\delta _{4,5}+\delta _{1,3}\delta _{4,6}+\delta _{1,3}\delta _{5,6}+\delta _{2,3}\delta _{4,5}+\delta _{2,3}\delta _{4,6}+\delta _{2,3}\delta _{5,6},\delta _{1,2,3}\delta _{4,5}+\delta _{1,2,3}\delta _{4,6}+\delta _{1,2,3}\delta _{5,6}+\delta _{4,5,6}\delta _{1,2}+\delta _{4,5,6}\delta _{1,3}+\delta _{4,5,6}\delta _{2,3}\}`$, we can write the transfer matrix as

$$T(K_{33})=\left(\begin{array}{ccccc}T_{11}& T_{12}& T_{13}& T_{14}& T_{15}\\ T_{21}& T_{22}& T_{23}& T_{24}& T_{25}\\ T_{31}& T_{32}& T_{33}& T_{34}& T_{35}\\ 1& 2(3+q)& 0& T_{44}& 2(2+q)\\ 0& 1& 0& 3& 2q\end{array}\right)$$
(6.2.1)
where

$`T_{11}`$ $`=`$ $`12341747q+1137q^2437q^3+105q^415q^5+q^6`$ (6.2.2)
$`T_{12}`$ $`=`$ $`6(252+337q198q^2+65q^312q^4+q^5)`$ (6.2.3)
$`T_{13}`$ $`=`$ $`2(3656q+33q^29q^3+q^4)`$ (6.2.4)
$`T_{14}`$ $`=`$ $`9(8994q+43q^210q^3+q^4)`$ (6.2.5)
$`T_{15}`$ $`=`$ $`6(25+24q8q^2+q^3)`$ (6.2.6)
$`T_{21}`$ $`=`$ $`113+91q27q^2+3q^3`$ (6.2.7)
$`T_{22}`$ $`=`$ $`174153q+54q^210q^3+q^4`$ (6.2.8)
$`T_{23}`$ $`=`$ $`10+13q6q^2+q^3`$ (6.2.9)
$`T_{24}`$ $`=`$ $`3(40+28q8q^2+q^3)`$ (6.2.10)
$`T_{25}`$ $`=`$ $`2921q+4q^2`$ (6.2.11)
$`T_{31}`$ $`=`$ $`5527q+3q^2`$ (6.2.12)
$`T_{32}`$ $`=`$ $`3(2917q+3q^2)`$ (6.2.13)
$`T_{33}`$ $`=`$ $`912q+6q^2q^3`$ (6.2.14)
$`T_{34}`$ $`=`$ $`18(3+q)`$ (6.2.15)
$`T_{35}`$ $`=`$ $`3(75q+q^2)`$ (6.2.16)
$`T_{44}`$ $`=`$ $`125q+q^2`$ (6.2.17)
Finally,

$`𝐯`$ $`=`$ $`\left(\begin{array}{c}(1+q)q(3147q+28q^28q^3+q^4)\\ 6(1+q)q(7+10q5q^2+q^3)\\ 2(1+q)^3q\\ 9(1+q)q(33q+q^2)\\ 6(1+q)^2q\end{array}\right)`$ (6.2.23)
$`𝐮_{\mathrm{id}}`$ $`=`$ $`\left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ 0\end{array}\right)`$ (6.2.29)
We remark that in this case there is an additional element of the basis $`\delta _{1,2,3}\delta _{4,5,6}`$ that should be taken into account in general. However, it corresponds to a vanishing amplitude.

Chromatic zeros for $`(K_{3,3})^{L_z}`$ with $`L_z=15`$ and $`L_z=30`$ are shown in Fig. 5, as well as the limiting curve $``$. The limiting curve $``$ contains six connected pieces. None of them crosses the real axis. Thus, strictly speaking, there is no $`q_c`$ defined. However, by extrapolating the closest points to the real axis we get $`q_c3.045`$, which is slightly greater than the value for the square lattice $`q_c=3`$.

There are 14 endpoints: $`q0.8197\pm 2.9764i`$, $`q1.9761\pm 2.5559i`$, $`q2.8190\pm 1.5587i`$, $`q2.9364\pm 2.5742i`$, $`q3.6220\pm 2.0051i`$, $`q3.0283\pm 1.3476i`$, and $`q3.0452\pm 0.008246i`$. There are two complex-conjugated T points at $`q2.949\pm 1.870i`$.

### 6.3 Family $`(K_{4,4})^{L_z}`$

In this case the transfer matrix has 15 elements. However, three of them correspond to null amplitudes, so we have an effective 12-dimensional transfer matrix. This matrix is listed in the Mathematica file transfer\_Knn\_tube.m that is available with this paper in the LASL cond-mat archive.

There are eight connected pieces (See Figure 6), and none of them crosses the real axis. The closest points to that axis are the complex-conjugated pair $`q3.6743\pm 0.0085i`$. There are ten endpoints (that were computed using the resultant method): $`q1.0084\pm 3.7740i`$, $`q1.9104\pm 3.4341i`$, $`q2.9457\pm 3.2436i`$, $`q3.0385\pm 2.8658i`$, $`q3.5456\pm 1.3512i`$, $`q3.6006\pm 3.2332i`$, $`q3.6260\pm 1.4516i`$, $`q3.6743\pm 0.0085i`$, $`q3.7857\pm 2.3839i`$, and $`q3.8460\pm 2.7980i`$. There are four T-points at $`q3.070\pm 2.904i`$, and $`q3.567\pm 3.158i`$.

## 7 Conclusions

In this paper we have reported exact solutions for the zero-temperature partition function of the $`q`$-state Potts antiferromagnet on tubes of the simple cubic lattice with various transverse cross sections and boundary conditions and with arbitrarily great length. We have used these to calculate, in the infinite-length limit, the resultant ground state degeneracy per site $`W`$ and the singular locus $``$ which is the continuous accumulation set of the chromatic zeros. In particular, we have calculated the value of $`q_c`$ or $`(q_c)_{\mathrm{eff}}`$ for these infinite-length tubes. Our results show quantitatively how this quantity increases as the effective coordination number for a given family of graphs increases and are a step toward determining $`q_c`$ is for the infinite simple cubic lattice. We have also presented similar calculations for another interesting family of tube graphs whose transverse cross section is formed from the complete bipartite graph $`K_{m,m}`$.

Acknowledgment: The research of R. S. was supported in part by the NSF grant PHY-9722101 The research of J.S. was partially supported by CICyT (Spain) grants AEN97-1880 and AEN99-0990. J.S. would like to acknowledge the warm hospitality of the C.N. Yang Institute for Theoretical Physics, where this work was initiated. We thank S.-C. Chang and A. Sokal for recent discussions on related research projects.


format: text

text:
# A process-reconstruction analysis of market fluctuations

## 1 Introduction

When a physical phenomenon is measured with a set of instruments, what we register is a sequence of values of some variable $`X`$

$$\mathrm{}X_2X_1X_0X_1X_2\mathrm{}$$

which takes values in a space $`Y`$. We will call $`Y`$ the state space and the space of sequences $`Y^{}`$ the path space. Statistical properties of the phenomenon may be described at three different levels:

(1) By the expectation values of the observables;

(2) By the probability measures on the state space $`Y`$;

(3) By the probability measures on path space $`Y^Z`$.

One obtains three different characterizations of the phenomenon which represent successively finer levels of description of the statistical properties. Borrowing a terminology used in large deviation theory , we will call these three types of description, respectively, level 1, 2 and 3- statistical indicators.

To obtain expectation values and probability measures we would require infinite samples and a law of large numbers. For any finite sample we obtain finite versions of the expectation values, the probability on state space and the probability on path space which are called the mean partial sums, the empirical measures (or empirical probability distribution functions - pdf’s) and the measures on the empirical process.

Level-1 and level-2 analysis are the most common ones and their statistical indicators the most commonly quoted when a stochastic process is analyzed. However to the same expectation values for the observables or to the same pdf’s, different processes may be associated. Therefore full understanding of the process requires the determination of the level-3 indicators. Recent advances have been obtained on the identification of processes, especially in connection with the analysis of hydrodynamic turbulence data    . In particular it has been clarified that analysis and reconstruction of the process involves two different but related steps. One is the identification of the grammar of the process, that is, the allowed transitions in the state space or the subspace in path space that corresponds to actual orbits of the system. The second step is the identification of the measure, which concerns the occurrence frequency of each orbit in typical samples. Although largely independent from each other, this two features have a related effect on the constraints they impose on the statistical indicators.

Identification of grammars and measures (in particular Gibbs measures) has been dealt with recently, in particular in the context of hydrodynamic turbulence and other dynamical systems. Market fluctuations is an interesting stochastic process . Some analogies have been found between this process and some of the features of turbulence data . However, when statistical indicators are computed, it turns out that the two processes are different  . Nevertheless the statistical tools that have been developed for turbulence are mathematical devices which are not process-dependent and they may be applied to any stochastic process process. Of course, underlying this approach is the working hypothesis that statistical methods, by themselves, are an appropriate tool to describe and reconstruct the market fluctuation process. This hypothesis underlies the modern view of the efficient market, namely the idea that the market appears to overreact in some circumstances and underreact in others is pure chance . In other words, the expected value of abnormal returns is zero. Contrariwise, if a well defined deterministic pattern of over- and underreaction is ever found then, in addition to chance, a behavioral component   must always be included in any description of the market. Behavioral trends, however, may turn out not inconsistent with a pure statistical description if the different reaction times of the diverse market components are taken into account, as well as the secondary reactions of the components to each other moves .

The emphasis on this paper will be on level-3 analysis and on the reconstruction of the processes. Nevertheless we have also dedicated some time to the computation, for market fluctuations, of the level-1 and level-2 statistical indicators used in the past for turbulence data. In particular the behavior of some of these indicators already provides information on the nature of the grammars. This analysis is carried out in Sect. 3. Sect. 4 is dedicated to the search for a Gibbs measure and, once the long-memory features of the market processes are exhibited, Sect. 5 attempts to describe the processes in the framework of chains with complete connections.

However, the first step in the analysis of any stochastic process is to inquire about the stationarity of the process and whether typical samples are available. This is the subject of the next section.

## 2 Is there an asymptotically stationary market fluctuation phenomenon?

Large samples of high-frequency finance data are now available. However high-frequency data may not be the more appropriate data to begin understanding the stochastic process that underlies the market mechanism. This is because, when comparing minute to monthly variations for example, one is comparing systems with very different compositions, trading agents operating on the minute scale being in general different from those operating in longer time scales. This is evidenced, for example, by the different scaling laws for low and high-frequency data. In market data one faces a complexity versus statistics trade-off. The high frequency data certainly provides better statistics but it also involves the interplay of many more reaction time scales and market compositions in the trading process. For this reason, to “purify” as much as possible our samples, we have decided to concentrate on daily data. The price to be paid for this choice is the fact that, as compared for example with a large scale hydrodynamics experiment, the available amount of one-day market fluctuation data is relatively small. If, in addition, the data is non-stationary, the chances to obtain a reliable statistical analysis would be rather slim.

Reliable application of statistical mechanics tools to any kind of signal, presupposes that two conditions are fulfilled. First, that the process that generates the data has some kind of underlying stationarity or asymptotic stationarity. Second, that the time sequence that is presented to the analysis is a typical sample of the process. The second condition, of course, we can only hope that it is realized and to improve our belief in this condition several different signals of a similar nature should be analyzed (several different stocks, or currencies or markets). As to the first condition it requires some preprocessing of the data. We will concentrate in this paper in the daily fluctuation data of industrial stocks and indexes and the objective is to try to extract the features of the market process that acts on them. We look at each stock as an experimental probe that, while reacting to the market pressures, may reveal some of the mechanisms of the market process.

Market prices are by nature non-stationary entities. They fluctuate, they have general trends that depend on the general state of the economy, on the total amount of capital flowing to the market, on the general acceleration of the economy, on long and medium term political decisions and expectations, etc. Nevertheless, our hypothesis is that, if all these global factors are extracted from the data, there are still some invariant features that characterize this peculiar human phenomenon.

The type of data that will be analyzed is displayed in Fig.1 that shows daily price data $`p(t)`$ for three stocks and the NYSE composite index. Its non-stationary nature is very apparent. The first step is to extract the general trend. This is done, in a smooth way by a polynomial fit $`q(t)`$ (Fig.2 shows an example, where a 7-degree polynomial is used). Fig.3 shows the difference $`p(t)q(t)`$. Clearly the data is still very far from stationary, because due to the market volume acceleration recent fluctuations carry a much larger weight. Therefore the last step is a rescaling of the data, by the average $`<p(t)>`$, that is

$$x(t)=\left(p(t)q(t)\right)\frac{<p(t)>}{q(t)}$$
(1)
are the signals to be analyzed.. They are shown in Fig.4. To anyone used to examine turbulence data, it looks as if the market signals are now somewhat stable. That does not mean, of course, that they are stationary in the strict sense. However it suggests that in spite of currency adjustments, increased number of players, trade volumes and other macroeconomic indicators, there is something more or less permanent in this human game.

Detrending and rescaling of the data is important because we will be analyzing price differences over large time intervals. For one-day differences of log-price, the results would be identical to those obtained from the raw data. Detrending and rescaling the data, the overall amplitude of price fluctuations becomes reasonably uniform over the time span of the data. However the process is not (locally) stationary, as seen in Figs.5 and 6 that show the strong variation in time of the volatility (here defined as the standard deviation of the price fluctuations). The two figures on the left show the standard deviation computed on a sliding time window of 10 days. On the right one compares the cumulative standard deviation for the rescaled (full line) and the non-rescaled data (dashed line). It is quite apparent that only the rescaled data has the chance to belong to an asymptotically stationary process. Once the data is detrended and rescaled there is in fact no evidence for an abnormal increase, in recent times, of the volatility in the underlying process.

A direct test of stationarity of the detrended and rescaled data was obtained by coding with a 5-symbols alphabet (as explained in Sect. 4). Then, computing the entropies of multi-symbol words, in the first and the second half of the samples, no significant difference is found.

## 3 Statistical indicators for typical samples

Here we concentrate on level-1 and level-2 analysis of the regularized samples discussed in Sect.2, that is, we compute quantities related to averages values and to probability distribution functions (pdf ’s). The level-3 analysis of the processes will be done in the latter sections.

The main variables that are used to construct the statistical indicators are the differences of log-prices

$$r(t,n)=\mathrm{log}p\left(t+n\right)\mathrm{log}p\left(t\right)$$
(2)
sometimes called the $`n`$days return. For each experimental sample, three main statistical indicators are computed:

(i) The maximum (over $`t`$) of $`r(t,n)`$

$$\delta \left(n\right)=\underset{t}{\mathrm{max}}\left\{r(t,n)\right\}$$
(3)
(ii) The moments of the distribution of $`\left|r(t,n)\right|`$

$$S_q(n)=\left|r(t,n)\right|^q$$
(4)
with $``$ meaning the sample average

(iii) If inside a certain range, the moments satisfy

$$S_q(n)n^{\chi (q)}$$
(5)
then the scaling exponent $`\chi (q)`$ is another important statistical indicator.

The results obtained from our detrended and rescaled samples are displayed in Figs.7 to 9. Fig.7 refers to $`\delta \left(n\right)`$ and Fig.8 shows $`S_q(n)`$ as a function of $`n`$ for different values of $`q`$ (from top to bottom $`q=1`$ to $`q=8`$). The large fluctuations in $`\delta \left(n\right)`$ for large values of $`n`$ and in $`S_q(n)`$ for large $`q`$ are quite natural given the size of the data samples.

In the range $`n=2`$ to $`n=60`$ the moments follow an approximate power law of the type of Eq.(5) and from the behavior in this region we have extracted the scaling exponent $`\chi (q)`$ shown in Fig.9. The main conclusions from this analysis of the statistical indicators are:

(a) $`\delta \left(n\right)`$ is log-concave, that is, $`\mathrm{log}\delta \left(n\right)`$ is concave as a function of $`\mathrm{log}n`$, increasing and probably (with better statistics) asymptotically constant for large $`r`$;

(b) $`S_q(n)`$ is also an increasing log-concave function of $`n`$, allowing a power law approximation in a limited range;

(c) The scaling law $`\chi (q)`$ is an increasing concave function of $`q`$;

(d) For all samples, $`\chi (1)`$ computed in the scaling region ($`n=2`$ to $`n=60`$) is very close to 0.5;

(e) The scaling properties of the NYSE index seem somewhat different from those of the other stocks. However this is only apparent for $`q5`$, where poor statistics effects may already be felt.

From this analysis one also obtains precise statements concerning the similarities and differences between hydrodynamic turbulence and the market fluctuation process. Properties (a) to (c) are shared by the turbulence data, although the numerical values of the statistical indicators are quite different. For example, for turbulence data $`\chi (1)=\frac{1}{3}`$ whereas here $`\chi (1)0.5`$, showing the essentially uncorrelated nature of the signal for $`n2`$. The correlation function of one-day returns and its absolute value

$$C(r(1),T)=r(t+T,1)r(t,1)$$
(6)
and

$$C(\left|r(1)\right|,T)=\left|r(t+T,1)\right|\left|r(t,1)\right|$$
(7)
are shown in Fig.10. One sees that for $`T2`$ the returns are uncorrelated, their correlation function remaining at the noise level. In contrast the correlation for the absolute value remains non-negligible for a longer time (at least up to $`T=10`$). This means that although the returns are linearly uncorrelated, non-linear functions of the returns remain correlated for longer periods.

The behavior of the statistical indicators $`\delta \left(n\right)`$, $`S_q(n)`$ and $`\chi (q)`$ already has some strong implications on the level-3 features of the process, namely on the structure of its grammar. In fact, without restrictions on the allowed transitions $`\delta \left(n\right)`$ and $`S_q(n)`$ would be independent of $`n`$ and $`\chi (q)=0`$ for all $`q`$. In particular, property (a) implies that if the process is a topological Markov chain the transitions allowed by the transition matrix $`T`$ must lie inside a strictly convex domain around the diagonal of $`T`$.

Fig.11 illustrates the dynamics of one-day returns

$$r(t,1)r(t+1,1)$$
(8)
It shows that the bulk of the data consists of a central core of small fluctuations with a few large flights away from this core. This structure of the data will have a strong influence on the results obtained in the next section.

## 4 Looking for a Gibbs measure

Let us assume a coding of the dynamical system by a finite alphabet $`\mathrm{\Sigma }`$. Then the space $`\mathrm{\Omega }`$ of orbits of the system are infinite sequences $`\omega =i_1i_2\mathrm{}i_k\mathrm{}`$, $`i_k\mathrm{\Sigma }`$, with the dynamical law being a shift $`\sigma `$ on these symbol sequences.

$$\sigma \omega =i_2\mathrm{}i_k\mathrm{}$$
(9)
Depending on the dynamical law of the coded system, not all sequences will be allowed. The set of allowed sequences in $`\mathrm{\Omega }`$ defines the grammar of the shift. The set of all sequences which coincide on the first $`n`$ symbols is called a $`n`$cylinder (or $`n`$block) and is denoted $`[i_1i_2\mathrm{}i_n]`$. The probability measures over the cylinders is the main tool that is used to characterize the dynamical properties and is a piece of information that may be inferred from the data.

A particularly important measure on the cylinders is the Gibbs measure defined by

$$c_1\frac{\mu \left([i_1(\omega )i_2(\omega )\mathrm{}i_n(\omega )]\right)}{\mathrm{exp}\left(nP+\left(S_n\varphi \right)(\omega )\right)}c_2$$
(10)
with $`\left(S_n\varphi \right)(\omega )=_{k=0}^{n1}\varphi \left(\sigma ^k\omega \right)`$, $`\varphi `$ being a Hölder continuous function on $`\mathrm{\Omega }`$ called the potential and $`P(\varphi ,G)`$ a function depending on the potential and the grammar called the pressure of $`\varphi `$.

The (equilibrium) Gibbs measure and the pressure bear an important relationship to the entropy

$$h\left(\mu \right)=\underset{n\mathrm{}}{lim}\frac{H_n}{n}=\underset{n\mathrm{}}{lim}\frac{1}{n}\underset{i_1\mathrm{}i_n}{}\mu \left([i_1i_2\mathrm{}i_n]\right)\mathrm{log}\mu \left([i_1i_2\mathrm{}i_n]\right)$$
(11)
This is the variational principle that states that, for each potential and grammar, the $`sup_\eta \left\{h\left(\eta \right)+\varphi 𝑑\eta \right\}`$ taken over all $`\sigma `$invariant measures $`\eta `$ is reached only for the Gibbs measure $`\mu `$ and equals the pressure

$$P(\varphi ,G)=h\left(\mu \right)+\varphi 𝑑\mu $$
(12)
The potential may be chosen in such a way that $`P=0`$. Such potential is called a normalized potential. In this case we have the following result

$$\varphi \left(\omega \right)=\underset{n\mathrm{}}{lim}\mathrm{log}\frac{\mu \left([i_1(\omega )\mathrm{}i_n(\omega )]\right)}{\mu \left([i_2(\omega )\mathrm{}i_n(\omega )]\right)}$$
(13)
In principle this formula may be used to construct the potential using the empirical measures $`\stackrel{~}{\mu }\left([i_1(\omega )\mathrm{}i_n(\omega )]\right)`$ obtained from the experimental sample. The problem is that Eq.(13) requires the use of blocks of length $`n`$ as large as possible but, for a finite sample, the statistics of such blocks suffers from large uncertainties.

For practical purposes the most important class of Gibbs measures is the one associated to finite range potentials, that is, functions on $`\mathrm{\Omega }`$ that depend only on the first $`r`$ symbols of a sequence $`\omega \mathrm{\Omega }`$. The importance of finite range potentials lies in the fact that they may be used to uniformly approximate any Hölder continuous potential and, on the other hand, given a limited amount of experimental data, only finite-range potentials may be reliably inferred from experiment.

An important property of range$`r`$ potentials is that for all values $`i_1i_2\mathrm{}i_n`$ with $`nr`$

$$\mu \left([i_1\mathrm{}i_n]\right)=\frac{\mu \left([i_1\mathrm{}i_r]\right)\mu \left([i_2\mathrm{}i_{r+1}]\right)\times \mathrm{}\times \mu \left([i_{nr+1}\mathrm{}i_n]\right)}{\mu \left([i_2\mathrm{}i_r]\right)\mu \left([i_3\mathrm{}i_{r+1}]\right)\times \mathrm{}\times \mu \left([i_{nr+1}\mathrm{}i_{n1}]\right)}$$
(14)
We will make use of this important relation in our attempt to look for a Gibbs measure for the market fluctuation data. On the one hand the relation (14) allows to express the entropy in terms of measures of cylinders of finite length only, namely

$$h\left(\mu \right)=\underset{i_1\mathrm{}i_k}{}\mu \left([i_1\mathrm{}i_k]\right)\mathrm{log}\frac{\mu \left([i_1\mathrm{}i_k]\right)}{\mu \left([i_1\mathrm{}i_{k1}]\right)}=H_kH_{k1}$$
(15)
for all $`kr`$ if $`r>1`$. If $`r=1`$ $`h\left(\mu \right)=H_1`$. $`H_k`$ is the entropy associated to cylinders of length $`k`$

$$H_k=\underset{i_1\mathrm{}i_k}{}\mu \left([i_1\mathrm{}i_k]\right)\mathrm{log}\mu \left([i_1\mathrm{}i_k]\right)$$
(16)
This provides a criterium to find the range of the potential. Using the empirical cylinder probabilities one computes $`H_k`$ for successively larger $`k`$. Then, the range of the potential is found when $`H_kH_{k1}`$ tends to a constant value. Once the range is found, the potential may be constructed directly from the empirical weights $`\stackrel{~}{\mu }\left([i_1\mathrm{}i_k]\right)`$.

Another important consequence of Eq.(14) is that for $`k>r`$

$$\mu \left([i_1\mathrm{}i_{k+1}]\right)=\frac{\mu \left([i_1\mathrm{}i_k]\right)\mu \left([i_2\mathrm{}i_{k+1}]\right)}{\mu \left([i_2\mathrm{}i_k]\right)}$$
(17)
We will use both the criterium following from (15) and Eq.(17) to test for the possibility to construct a Gibbs measure for the market fluctuation data.

A five-symbols code $`\mathrm{\Sigma }`$

$$\mathrm{\Sigma }=\{2,1,0,1,2\}$$
(18)
is used for the one-day return data $`r\left(t\right)`$

$$r\left(t\right)=\mathrm{log}p\left(t+1\right)\mathrm{log}p\left(t\right)$$
(19)
The average $`\overline{r\left(t\right)}`$ and standard deviation $`s=\sqrt{\overline{\left(r^2\left(t\right)\overline{r\left(t\right)}^2\right)}}`$ of the returns are computed. Then,

$$\begin{array}{ccc}\left(r\left(t\right)\overline{r\left(t\right)}\right)>s& \hfill & 2\\ s\left(r\left(t\right)\overline{r\left(t\right)}\right)>\frac{s}{3}& \hfill & 1\\ \frac{s}{3}\left(r\left(t\right)\overline{r\left(t\right)}\right)>\frac{s}{3}& \hfill & 0\\ \frac{s}{3}\sigma \left(r\left(t\right)\overline{r\left(t\right)}\right)>s& \hfill & 1\\ s\left(r\left(t\right)\overline{r\left(t\right)}\right)& \hfill & 2\end{array}$$
(20)
This coding is used and the empirical frequencies $`\stackrel{~}{\mu }\left([i_1\mathrm{}i_n]\right)`$ for blocks of successively larger order $`n`$ are found. Of course $`n`$ cannot be arbitrarily large because of statistics. Results will not be reliable whenever $`5^n`$ is larger than the size $`N`$ of the data sample. The statistical reliability may be directly tested either by comparing the number of different occurring blocks and $`5^n`$ or by observing the fall-off of the empirically computed $`H_nH_{n1}`$.

First we try to estimate a possible range for the potential using the criterium discussed above. The results are shown in Figs.12 and 13 for the analyzed stocks and the NYSE index. The plots on the left show the quantity $`H_kH_{k1}`$ and the plots on the right compare the number $`p\left(k\right)`$ of occurring blocks of size $`k`$ in the data with the maximum possible number, $`5^k`$. Already for $`k=2`$ the difference $`H_kH_{k1}`$ seems to stabilize, staying nearly constant until $`k=4`$. After $`k=4`$ it falls off, reflecting the lack of statistics also apparent in the comparison of $`p\left(k\right)`$ with $`5^k`$ in the right hand side plots. These results seem to suggest that the data is described by a very short range potential. Notice that for a similar analysis performed on hydrodynamic turbulence data the results are quite different with $`H_kH_{k1}`$ rising smoothly up to a certain saturation level and then decreasing when one reaches the lack of statistics level.

To check whether the short-range potential suggested by this criterium is reliable or whether it simply results from some misleading feature of the data, we have performed the test following from Eq.(17). For successively higher $`k`$ we estimate $`\mu _e\left([i_1\mathrm{}i_{k+1}]\right)=\frac{\stackrel{~}{\mu }\left([i_1\mathrm{}i_k]\right)\stackrel{~}{\mu }\left([i_2\mathrm{}i_{k+1}]\right)}{\stackrel{~}{\mu }\left([i_2\mathrm{}i_k]\right)}`$ from the empirical $`\stackrel{~}{\mu }\left([i_1\mathrm{}i_k]\right)`$ and $`\stackrel{~}{\mu }\left([i_1\mathrm{}i_{k1}]\right)`$, which is then compared with the empirically observed $`\stackrel{~}{\mu }\left([i_1\mathrm{}i_{k+1}]\right)`$. The standard deviation of the relative positive errors

$$\epsilon _k=\mathrm{max}(0,\frac{\stackrel{~}{\mu }\left([i_1\mathrm{}i_{k+1}]\right)\mu _e\left([i_1\mathrm{}i_{k+1}]\right)}{\frac{1}{2}\left(\stackrel{~}{\mu }\left([i_1\mathrm{}i_{k+1}]\right)+\mu _e\left([i_1\mathrm{}i_{k+1}]\right)\right)})$$
(21)
is computed and the number of blocks for which this error is one and two standard deviations above the mean is computed. The result is plotted in Fig.14 where the number of underestimation errors that are one (o) and two (\*) standard deviations away from the mean error are compared with the total number $`p(k)`$ of different observed blocks of each length $`k`$.

One sees that the number of large deviation errors is very large and, identifying the blocks for which these errors occur, one finds out that they all correspond to blocks involving large positive or negative $`r\left(t\right)`$’s ($`2`$ and $`2`$). The conclusion is that a short-range potential would describe the small fluctuations in the data, the large fluctuations being badly described by it. The reason why the empirically found difference $`H_kH_{k1}`$ seems to saturate for a small $`k`$ is because, as is apparent from Fig.11, the bulk of the data consists mostly of small fluctuations plus a few large flights. The saturation of $`H_kH_{k1}`$ for small $`k`$ is a reflection of the largely uncorrelated nature of the small fluctuations, whereas other features like the large deviations, persistence of non-linear correlations (volatility), etc. are not captured by a short-range potential.

Large deviations being misrepresented by an empirically constructed measure is typical of situations where the actual measure is non-Gibbsian . In our case, however, it may also occur that the measure is Gibbsian but with a long-range potential. This would correspond to a sharp rise of $`H_kH_{k1}`$ at $`k=2`$ followed by a very slow increase above $`k=2`$. In the empirical results a small increase may be hidden by the fact that, as the block length increases, the statistics becomes poorer. A large deviation analysis applied to the calculation of $`H_k`$ , using a standard technique to construct the free energy and the deviation function from the data, is consistent with this hypothesis.

In any case, whether a Gibbs measure exists or not, the finite-range potential framework does not seem to be the more convenient way to describe the market fluctuation process. In the next section we will explore another approach specially suited to deal with long-memory processes.

## 5 Market fluctuations as a chain with complete connections

Processes with long memory have been studied in the past. Under certain conditions, that is, when the dependence on the past does not decay too slowly, existence and uniqueness of a well defined process may be proved. A particularly well established framework is the one of chains with complete connections and summable decays (   and references therein).

A stochastic process $`\{X_n\}_n`$ with alphabet $`\mathrm{\Sigma }`$ is said to be a chain with complete connections (CCC) if the following conditions are satisfied

1. $`a_i\mathrm{\Sigma }`$

$$P\left(X_1=a_1,\mathrm{},X_n=a_n\right)>0$$
(22)
2. The limit

$$\underset{m\mathrm{}}{lim}P(X_0=a_0|X_j=a_j,mj1)=P(X_0=a_0|X_j=a_j,j1)$$
(23)
exists $`a_i,j1`$
3. There is a sequence $`\left(\gamma _m\right)_{m1}`$ with $`lim_m\mathrm{}\gamma _m=0`$, such that for all $`\{a_j,b_j\mathrm{\Sigma },j1\}`$ with $`a_j=b_j`$ for $`mj1`$

$$\left|\left(\frac{P(X_0=a_0|X_j=a_j,j1)}{P(X_0=a_0|X_j=b_j,j1)}1\right)\right|\gamma _m$$
(24)

The process is said to be a chain with complete connections and summable decay (CCCSD) if $`\gamma _m<\mathrm{}`$

Conditions 1. and 2. are implicitly assumed when we considered the processes (and pre-processed the data) to be asymptotically stationary. As for the decays $`\gamma _m`$ they may be estimated from a typical sample of the process. From the empirical probabilities for

$$P\left(a_0|a_1\mathrm{}a_mA\right)=\frac{P\left(a_0a_1\mathrm{}a_mA\right)}{P\left(a_1\mathrm{}a_mA\right)}$$
(25)
where $`A`$ is a block of arbitrary length, ones computes for each fixed set $`a_0a_1\mathrm{}a_m`$ the maximum and the minimum over $`A`$,

$$g\left(a_0a_1\mathrm{}a_m\right)=\left(\frac{\mathrm{max}_AP\left(a_0|a_1\mathrm{}a_mA\right)}{\mathrm{min}_AP\left(a_0|a_1\mathrm{}a_mA\right)}1\right)$$
(26)
obtaining for $`\gamma _m`$

$$\gamma _m=\underset{a_0a_1\mathrm{}a_m}{\mathrm{max}}g\left(a_0a_1\mathrm{}a_m\right)$$
(27)
However if the statistics for very long blocks is poor, which is in general the case for finite samples, the computation of the maximum from empirical data is not reliable. A better estimate of the decay behavior of the decay rates is obtained from the following quantity, which smooths out the large fluctuations due to poor statistics

$$g(m)=\overline{g\left(a_0a_1\mathrm{}a_m\right)}$$
(28)
the average being taken over all sets $`a_0a_1\mathrm{}a_m`$ of size $`m`$.

The results obtained for the $`\mathrm{\Sigma }`$coded data of the detrended fluctuations (of BMW data) using $`A`$ blocks of length 5 to 8 ($`\times ,+,o,`$) is plotted in Fig.15. Similar results are obtained for the other data. The result is compatible with exponential decay, which would probably imply the existence of a Gibbs measure (albeit with a long range potential). The data for the maxima of $`g\left(a_0a_1\mathrm{}a_m\right)`$ displays large fluctuations and slower decay. However, with the amount of available data it is not reliable for long blocks. In any case, in the present context of CCC-processes, what the result suggests is the summability of the $`\gamma _m`$’s. ($`_m\gamma _m<\mathrm{}`$). For practical purposes the most importance consequence of this fact is that a CCC-process with summable decays is the $`\overline{d}`$limit of its Markov approximations of order $`k`$. The nature of this approximation should however be clearly understood.

The $`\overline{d}`$distance between two processes refers not to the processes themselves but to the process that implements the coupling of the two processes. A coupling between two processes $`X=\left\{X_n\right\}`$ and $`Y=\left\{Y_n\right\}`$ over the alphabet $`\mathrm{\Sigma }`$ is another process $`\{\stackrel{~}{X}_n,\stackrel{~}{Y}_n\}`$ defined over $`\mathrm{\Sigma }\times \mathrm{\Sigma }`$ such that the marginal probabilities of $`\stackrel{~}{X}`$ and $`\stackrel{~}{Y}`$ coincide with those of $`X`$ and $`Y`$. Then the $`\overline{d}`$distance between $`X`$ and $`Y`$ is

$$\overline{d}(X,Y)=inf\{P\left(\stackrel{~}{X}_0\stackrel{~}{Y}_0\right):\{\stackrel{~}{X}_n,\stackrel{~}{Y}_n\}\text{ is a stationary coupling of }X\text{ and }Y\}$$
(29)
For some types of coupling the two processes $`\stackrel{~}{X}`$ and $`\stackrel{~}{Y}`$ are know to coincide after a certain random time. However, for the original processes $`X`$ and $`Y`$, if the $`\overline{d}`$distance tends to zero it does mean that the processes will coincide after a certain time. It only means that it will occur for some other processes with the same marginal probabilities.

This fact has an important bearing on the correct interpretation of the “perfect simulation” schemes  proposed for CCC’s. Perfect simulation is always understood in the $`\overline{d}`$distance sense and it does mean perfect prediction. It means simply that a process is constructed with the same conditional probabilities of the original process, whenever the conditional probabilities of the original process are known. In practice not all conditional probabilities involving infinite pasts are needed, because going back to a regeneration time, only a finite number of back steps are required. Several simulation schemes have been proposed for CCC’s with summable decays. The most important one for the applications, when the conditional probabilities are inferred from experiment, is the sequence of canonical Markov approximations of finite order $`k`$ ($`k`$CMA). A $`k`$CMA of a process $`X`$ is a Markov chain $`Y^{(k)}`$ of order $`k`$ with conditional probabilities $`P^{(k)}`$ such that

$$P^{(k)}\left(a_0|a_1\mathrm{}a_k\right)=P\left(a_0|a_1\mathrm{}a_k\right)=\underset{A}{}P\left(a_0|a_1\mathrm{}a_kA\right)$$
(30)
For a CCC $`X`$ with summable decays

$$\overline{d}(X,Y^{(k)})C\gamma _k$$
(31)
$`C>0`$ being a constant. Actually the property of the Markov approximation that is essential for the approximation result (31) is

$$\underset{A}{inf}P\left(a_0|a_1\mathrm{}a_kA\right)P^{(k)}\left(a_0|a_1\mathrm{}a_k\right)\underset{A}{sup}P\left(a_0|a_1\mathrm{}a_kA\right)$$
(32)
meaning that for Markov approximation schemes, other than the canonical one, Eq.(31) holds provided (32) is satisfied. In fact, when the conditional probabilities are inferred from limited experimental data a different Markov approximation is more convenient.

The following approximation scheme is proposed for the market fluctuation data, which we call the $`k`$Markov approximation:

i) Empirical transition probabilities $`\stackrel{~}{P}\left(a_0|a_1\mathrm{}a_m\right)`$ are inferred from the occurrence probability of blocks of order $`m+1`$. up to a certain order $`m_{Max}`$. Of course, only probabilities that correspond to blocks $`a_1\mathrm{}a_m`$ that appear in the data will be available and especially for large $`m`$ many will be missing.

ii) For the simulation, with an approximation of order $`k`$, one looks at the current block $`\left(a_1\mathrm{}a_k\right)`$ of order $`k`$ and uses the $`k`$empirical probability to infer the next state $`a_0`$. If that block has not appeared in the data that was used to construct the empirical probabilities, then one looks at the $`k1`$ sized block $`a_2\mathrm{}a_k`$ and uses the $`k1`$ order empirical probabilities. If necessary the process is repeated until an available empirical probability is found. This is the reason why this is called the $`k`$Markov approximation.

This approximation scheme has been applied to the market fluctuation data and for each $`k`$order the successor $`a_0`$ of each block $`\left(a_1\mathrm{}a_k\right)`$ is compared with a prediction $`\stackrel{~}{a}_0`$ obtained by throwing a random number with the probabilities $`\stackrel{~}{P}\left(a_0|a_1\mathrm{}a_k\right)`$. Figs.16 shows some of the results. In all cases the quantity that is plotted is the averaged squared error

$$e^2=\left(\stackrel{~}{a}_0a_0\right)^2$$
(33)
the average being taken over the samples and 100 different runs. The two upper plots and the left lower plot show the results obtained (for each approximation order $`k`$) when half of the data for each company is used to predict the other half. The points labelled ($`o`$) correspond to the past used to predict the future and those labelled ($``$) to the future used to predict the past. Finally the right lower plot shows the results obtained when $`\stackrel{~}{a}_0`$ is chosen at random (for the 3 companies, IBM $`\left(o\right)`$, Bayer $`()`$ and BMW $`(+)`$). The main conclusions that may be extracted from these results are:

* The average prediction obtained from using the empirical probabilities is better than a random choice.
* However, the main improvement is a result of a correct accounting of the two-symbol probabilities ($`k=1`$).
* After the improvement due to the use of the lowest order blocks a small (but consistent) improvement is found by using the past information up $`k=4`$ or $`5`$. No significant improvement is obtained by using higher order approximations. This is consistent with the poorer statistics of large blocks. Actually for each individual simulation the result of using $`k>5`$ leads to much larger fluctuations.

The main conclusion is that although the bulk of the data is represented by a short-memory process, there is nevertheless evidence for a small long-memory component that is captured by the higher-order Markov approximations. Depending on the amount of data that is available to infer the empirical conditional probabilities there is a maximum $`k=k_m`$ that should be used for the simulation process. This $`k_m`$ value may be estimated from the quantity $`p\left(k\right)`$ plotted in Figs 12 and 13. Finally, although a mild gain is obtained from using $`k_m`$block probabilities rather than one-symbol probabilities, it should be remembered that perfect simulation in the $`\overline{d}`$distance sense is not perfect prediction for the actual process. This is a point to keep in mind when attempting to develop any trading strategies based on the empirical block probabilities.

We have also explored the use of the empirical probabilities of one company to predict the behavior of the others. In all cases the improvement coming from the one-symbol probabilities (as compared to random choice) is obtained. This means that the one-symbol probabilities are similar in all companies. However for the long-memory component the behavior is very much company-dependent. For example there seems to be no correlation of this component between IBM and the other two companies, with the prediction being actually worse when the empirical probabilities for longer blocks are used. The same happens also when the empirical probabilities of BMW and Bayer are used to predict IBM. However there is some statistical correlation between the long-memory components (and some mild prediction improvement) between BMW and Bayer. This suggests that the statistical short-memory component of the market process might be similar for many different stocks, whether the long-memory component might be different from market to market and to divide the stocks into classes. A similar conclusion follows from the stocks taxonomy obtained by Mantegna , although that work does not distinguish between the short- and long-memory components of the process.

## 6 Conclusions

1. The bulk of the market fluctuation process seems to be a short-memory process. In addition it has a small long-memory component, which however is very important for practical purposes because it is associated with the large fluctuations of the returns.
2. Existence of the long-memory component suggests the chains with complete connections and summable decays as the appropriate framework to describe these processes. Although the decays may be exponentially converging, the lack of accurate data concerning long blocks prevent an accurate description by a finite range Gibbs potential.
3. The sequence of empirical based $`k`$Markov approximations discussed in Sect.5 seems the most unbiased simulation of the process. Eventual convergence in the $`\overline{d}`$distance sense is expected to hold because the market fluctuation process seems to fit in the framework of chains with complete connections and summable decays.
4. Except for cases where one is sure of the existence of a finite potential, Markov approximations must always be used if only finite data is available. This true whether a Gibbs measure exists or not. What the chains with complete connections framework provides though, is a rationale for the convergence of the Markov approximations and a criterium to estimate, through the $`\gamma _m`$ decays, how good this approximation is. Notice however the trade-off between higher order approximations and lack of statistics, that leads to an optimal block length for the empirical probabilities to be used in the simulations.
5. As work for the future we point out that it would be interesting to analyze in this framework the high frequency market data. Here however attention should be paid to the possibly multi-scale and multi-component nature of the processes.