text:
# The Number of Nowhere-Zero Flows on Graphs and Signed Graphs

## 1. Introduction

A *nowhere-zero flow* on a graph $`\mathrm{\Gamma }=(V,E)`$, with values in an abelian group $`A`$, is a mapping $`x:EA`$ such that, for every node $`vV`$,

$$\underset{h(e)=v}{}x(e)=\underset{t(e)=v}{}x(e),$$
(1.1)
and which never takes the value $`0`$. Here $`h(e)`$ and $`t(e)`$ are respectively the head and tail of the edge $`e`$ in a (fixed) orientation of $`\mathrm{\Gamma }`$. (In a certain sense, described below, $`x`$ is independent of the chosen orientation.) A *nowhere-zero $`k`$-flow* is an integral flow (i.e., $`A=`$) whose absolute values are in $`[k1]:=\{1,2,\mathrm{},k1\}`$. Nowhere-zero flows are nicely surveyed in  and .

It has long been known that the number of nowhere-zero flows with values in a finite abelian group of order $`k`$ is a polynomial function of $`k`$ (Tutte ). Recently Kochol  discovered that the number of nowhere-zero $`k`$-flows is also a polynomial in $`k`$, although not the same polynomial. Here we show that this fact is a consequence of a general theory of counting lattice points in inside-out polytopes . Furthermore, we extend Kochol’s theorem in two ways: by a reciprocity law that combinatorially interprets negative arguments, and to signed graphs (in which each edge is positive or negative), where the polynomial becomes a quasipolynomial of period two: that is, a pair of polynomials, one for odd values of $`k`$ and the other for even $`k`$ (Theorem 4.5); and we partially extend to signed graphs Tutte’s counting theory for nowhere-zero flows in abelian groups (Theorem 4.1). Still further, the concept of reciprocity in lattice-point counting leads us to a geometrical interpretation of the number of totally cyclic orientations that are compatible with a given $`k`$-flow (Theorems 3.1 and 4.5 and Corollary 4.4), a fact which parallels Stanley’s theorem  that the chromatic polynomial of $`\mathrm{\Gamma }`$ evaluated at negative integers counts acyclic orientations compatible with a node-labelling of $`\mathrm{\Gamma }`$.

## 2. The method of inside-out polytopes

The theory of inside-out polytopes was motivated by the problem of counting the integral points of a *rational convex polytope* (the convex hull of finitely many rational points in $`^d`$) that do not lie in any of the members of a particular rational hyperplane arrangement. A (homogeneous, real) *hyperplane arrangement* is a finite set of homogeneous hyperplanes in $`^d`$ (that is, hyperplanes that contain the origin); it is *rational* if each of its hyperplanes is spanned by the rational points it contains or, alternatively, if each hyperplane has a rational normal vector. Suppose we are given a rational convex polytope $`P`$ spanning $`^d`$ and a rational hyperplane arrangement $``$. Then $`(P,)`$ is a *rational inside-out polytope*. More generally, $`P`$ and $``$ may lie in a rational (and homogeneous) subspace $`Z`$ that is spanned by $`P`$. We introduced inside-out polytopes recently ; one motivation was to explain graph-theoretic enumeration functions geometrically. We consider inside-out theory essential to understanding our results on integral flows.

A *region* (more precisely, an *open region*) of $``$ is a connected component of $`^d`$; its closure is a *closed region*. The arrangement *induced* by $``$ in a subspace $`S`$ of $`^d`$ is

$$^S:=\{HS:H,HS\}.$$

The *intersection lattice* of $``$ is

$$():=\{𝒮:𝒮\},$$

ordered by reverse inclusion ; its elements are the *flats* of $``$. $``$ is a *geometric lattice* with $`\widehat{0}=\mathrm{}=^d`$ and $`\widehat{1}=`$. (For matroids and geometric lattices we refer to  or .) The *Möbius function* of $``$ is the function $`\mu :\times `$ defined recursively by

$$\mu (R,S):=\{\begin{array}{cc}0\hfill & \text{if }RS,\hfill \\ 1\hfill & \text{if }R=S,\hfill \\ _{RU<S}\mu (R,U)\hfill & \text{if }R<S.\hfill \end{array}$$

(Sources for the Möbius function are, *inter alia*,  and .)

### 2.1. Ehrhart theory

We outline the classical Ehrhart theory of lattice-point enumeration in polytopes. (See , \[21, Section 4.6, pp. 235–241\], or .) We have a rational convex polytope $`P`$ that spans a subspace $`Z`$. $`P^{}`$ denotes the relative interior of $`P`$. The *denominator* of $`P`$ is the least common denominator of all the coordinates of vertices of $`P`$. We denote by $`\mathrm{vol}P`$ the *volume* of $`P`$, normalized with respect to $`Z^d`$; that is, we take the volume of a fundamental domain of the integer lattice in $`Z`$ to be 1. To explain this last, we note that $`Z^d`$ is linearly equivalent to $`^{dimZ}^{dimZ}`$; a *fundamental domain* is a domain in $`Z`$ that corresponds to the unit hypercube $`[0,1]^{dimZ}^{dimZ}`$, under some invertible linear transformation that carries $`Z^d`$ to $`^{dimZ}`$. (See \[21, pp. 238–239\] or \[3, Section 5.4\] for more detail.) When $`Z=^d`$ this is the ordinary volume.

A *quasipolynomial* is a function $`Q(t)=_0^dc_i(t)t^i`$ defined on $``$ with coefficients $`c_i`$ that are periodic functions of $`t`$. Then $`Q`$ is a polynomial $`Q_{\overline{t}}`$ on each residue class $`\overline{t}`$ modulo some integer, called the *period* of $`Q`$; these polynomials are the *constituents* of $`Q`$. (For an introduction to quasipolynomials see, e.g., \[21, Chapter 4\] or .)

The subject of Ehrhart theory is the (closed) Ehrhart counting function

$$E_P(t):=\mathrm{\#}(tP^d)$$

and the open Ehrhart counting function, $`E_P^{}(t)`$. Ehrhart’s theorem is that $`E_P`$ and $`E_P^{}`$ are quasipolynomials with leading term $`(\mathrm{vol}P)t^{dimP}`$ and with periods that divide the denominator of $`P`$. It follows that one can define both counting functions for negative integers; the Ehrhart–Macdonald Reciprocity Theorem is that $`E_P^{}(t)=(1)^{dimP}E_P(t)`$.

### 2.2. Inside-out Ehrhart theory

An *open region of $`(P,)`$* is a nonempty intersection with $`P^{}`$ of an open region of $``$ (thus it is full-dimensional in the span of $`P`$). A *closed region of $`(P,)`$* is the closure of an open region. A *vertex* of $`(P,)`$ is a vertex of any such region. The *denominator* of $`(P,)`$ is the least common denominator of all coordinates of all vertices.

The fundamental counting functions associated with $`(P,)`$ are two quasipolynomials: the (*closed*) *Ehrhart quasipolynomial*,

$`E_{P,}(t)`$ $`:={\displaystyle \underset{xt^1^d}{}}m_{P,}(x),`$
where the *multiplicity* $`m_{P,}(x)`$ of $`x^d`$ with respect to $``$ and $`P`$ is defined through
$`m_{P,}(x)`$ $`:=\{\begin{array}{cc}\text{the number of closed regions of }(P,)\text{ that contain }x,\hfill & \text{if }xP,\hfill \\ 0,\hfill & \text{if }xP,\hfill \end{array}`$
and the *open Ehrhart quasipolynomial*,
$`E_{(P,)^{}}(t)`$ $`:=\mathrm{\#}\left(t^1^d\left[P^{}\left({\displaystyle }\right)\right]\right).`$
(This is simplified from the notation $`E_{P^{},}^{}`$ of . The reader may think of $`(P,)^{}`$ as the set $`P^{}\left(\right)`$, called the *relative interior* of $`(P,)`$, but that is not necessary in order to read this paper.) If $`P`$ spans a subspace $`Z`$, then $``$ also lies in $`Z`$ and the multiplicity of $`x`$ is defined to be 0 if $`xZ`$. The names of our counting functions are justified by the fact that in the absence of $``$ we recover classical Ehrhart theory, and by one of the main results in :

###### Theorem 2.1 (\[4, Theorem 4.1\]).

If $`(P,)`$ is a closed, full-dimensional, rational inside-out polytope in $`Z^d`$, then $`E_{P,}(t)`$ and $`E_{(P,)^{}}(t)`$ are quasipolynomials in $`t`$, with period equal to a divisor of the denominator of $`(P,)`$, with leading term $`(\mathrm{vol}P)t^{dimP}`$, and with constant term $`E_{P,}(0)`$ equal to the number of regions of $`(P,)`$. Furthermore,

$$E_{(P,)^{}}(t)=(1)^{dimP}E_{P,}(t).$$
(2.1)
In particular, if $`(P,)`$ is integral then $`E_{P,}`$ and $`E_{(P,)^{}}`$ are polynomials. The proof, though more general (and arrived at independently), is similar to Kochol’s proof of Theorem 3.1(a): we sum the Ehrhart quasipolynomials of the pieces into which $``$ dissects $`P`$.

For the second theorem of  we will use here, we need the notion of transversality: $``$ is called *transverse* to $`P`$ if every flat $`U()`$ that intersects $`P`$ also intersects $`P^{}`$, and $`P`$ does not lie in any of the hyperplanes of $``$.

###### Theorem 2.2 (\[4, Theorem 4.2\]).

If $`P`$ and $``$ are as in Theorem 2.1, then

$$E_{(P,)^{}}(t)=\underset{U()}{}\mu (\widehat{0},U)E_{P^{}U}(t),$$
(2.2)
and if $``$ is transverse to $`P`$,

$$E_{P,}(t)=\underset{U()}{}|\mu (\widehat{0},U)|E_{PU}(t).$$
(2.3)
Transversality is always satisfied in the applications here.

### 2.3. Matrix matroids

We shall want a general lemma about matroids of hyperplane arrangements induced by coordinate arrangements. We start with the hyperplane arrangement $`_m`$, consisting of the coordinate hyperplanes in $`F^m`$ for some field $`F`$, and we take any subspace $`S`$. Then $`S`$ induces an arrangement $`_m^S`$ in $`S`$. (We are interested in the reals, but the lemma is valid for any field.)

Any homogeneous hyperplane arrangement $``$ has a matroid $`M()`$, whose ground set is the set of hyperplanes and whose rank function is $`\mathrm{rk}𝒮=\mathrm{codim}\left(𝒮\right)`$ for $`𝒮`$. This matroid is simply the linear dependence matroid of the normal vectors of the hyperplanes. The *column matroid* of a matrix $`A`$, $`M(A)`$, is the matroid of linear dependence of its columns; to keep the notation correct we take the ground set to be the set of indices of columns. The *chain-group matroid* of a subspace $`SF^m`$ is the matroid $`N(S)`$ on $`[m]`$ whose circuits are the minimal nonempty supports of vectors in $`S`$. $`\mathrm{Lat}M`$ denotes the lattice of closed sets of a matroid $`M`$. Thus $`\mathrm{Lat}M()()`$.

We refer in the following lemma to orientations of oriented matroids. The reader who is not familiar with oriented matroids should think of orientations of a graph or (later, in Section 4) of a signed graph.

###### Lemma 2.3.

Let $`A`$ be an $`n\times m`$ matrix with entries in a field $`F`$, let $`_m=\{H_e:e[m]\}`$ be the arrangement of coordinate hyperplanes in $`F^m`$, and let $`U=\mathrm{Row}A`$, the row space, and $`Z=\mathrm{Nul}A`$, the null space.

1. The mapping $`eH_eU`$ is a matroid isomorphism from $`M(A)`$ to $`M(_m^U)`$. Also, $`eH_eZ`$ is a matroid isomorphism of $`N(\mathrm{Row}A)`$ with $`M(_m^Z)`$.
2. The mapping

$$SE_U(S):=\{e[m]:H_eS\}$$

is the isomorphism of $`(_E^U)`$ with $`\mathrm{Lat}M(A)`$ induced by the first mapping in (a). The mapping

$$SE_Z(S):=\{e[m]:H_eS\}$$

is the isomorphism of $`(_E^Z)`$ with $`\mathrm{Lat}N(\mathrm{Row}A)`$ induced by the second mapping in (a).
3. If $`F`$ is an ordered field, then the regions of $`_m^U`$ correspond bijectively to the acyclic orientations of the oriented matroid of columns of $`A`$, and those of $`_m^Z`$ correspond to the totally cyclic orientations.

###### Proof.

(a) Each coordinate hyperplane $`H_e`$ equals $`b_e^{}`$ for a basis vector $`b_e`$ along the $`e`$-axis. Therefore, $`H_eU`$ is the orthogonal complement in $`U`$ of $`a_e`$, the orthogonal projection of $`b_e`$ into $`U`$. Let $`B:=\{b_e:e[m]\}`$. We may take $`A`$ to be the matrix whose columns are the vectors $`a_e`$, since it has the same row space as the original matrix $`A`$. By linear duality, $`M(A)M(_m^U)`$ under the correspondence $`eH_eU`$.

We treat $`_m^Z`$ by taking $`A^{}`$, a matrix whose row space is $`\mathrm{Nul}A`$, and applying the first part to $`\mathrm{Row}A^{}`$. $`N(\mathrm{Row}A)`$ is dual to $`M(A)`$; hence it is $`M(A^{})`$ because $`\mathrm{Row}A`$ and $`\mathrm{Nul}A`$ are dual chain-groups. (See, e.g., Tutte \[25, Chapter VIII\] on primitive chain-groups.)

(b) Obvious from (a) and the definitions.

(c) Write $`(A)`$ for the oriented matroid. The proof is as in part (a), but relying on the dual relationship between $`(A)`$ and $`(A^{})`$ \[31, Section 6.3(c)\]. Our $`(A)`$ is Ziegler’s $`(\mathrm{Nul}A)`$, so our $`(A^{})=(\mathrm{Row}A)`$, which is dual to $`(\mathrm{Nul}A)`$ because the row and null spaces are orthogonal complements. ∎

## 3. Flows on graphs

A *flow* on a graph $`\mathrm{\Gamma }`$ with values in an abelian group $`A`$, called an *$`A`$-flow*, is a function $`x:EA`$ which satisfies (1.1) for every node $`vV`$ (so it is like a nowhere-zero flow, but the flow value zero is allowed). This definition requires that the edges be oriented in a fixed way. The orientation is arbitrary; it is an artifact of notation, and to overcome this artificiality we define, for an oriented edge $`e`$, $`e^1`$ to be the same edge in the opposite orientation and $`x(e^1):=x(e)`$. With this law for flows, the validity of Equation 1.1 is independent of the choice of the orientation of $`\mathrm{\Gamma }`$.

Tutte \[22, Section 6\] proved that the number of nowhere-zero $`A`$-flows on $`\mathrm{\Gamma }`$ is a polynomial in $`|A|`$, independent of the actual group. We shall write $`\overline{\phi }_\mathrm{\Gamma }`$ for this polynomial and call it the *(strict) modular flow polynomial* of $`\mathrm{\Gamma }`$. (Usually $`\overline{\phi }_\mathrm{\Gamma }`$ is called just the “flow polynomial” but we need to distinguish it from other flow polynomials.) As Tutte showed, the modular flow polynomial $`\overline{\phi }_\mathrm{\Gamma }(k)`$ is the evaluation $`(1)^{\xi (\mathrm{\Gamma })}t_\mathrm{\Gamma }(0,1k)`$ of the Tutte polynomial of $`\mathrm{\Gamma }`$. ($`\xi (\mathrm{\Gamma })`$ is the cyclomatic number $`|E||V|+c(\mathrm{\Gamma })`$, where $`c(\mathrm{\Gamma })`$ is the number of connected components.) We should mention that the total number of $`A`$-flows is the simple polynomial $`|A|^{\xi (\mathrm{\Gamma })}`$. Tutte further proved (in \[24, pp. 83–84\], based on \[23, Theorem VI\]) that a nowhere-zero $`_k`$-flow exists if and only if there is a nowhere-zero $`k`$-flow, a *$`k`$-flow* being an integer-valued flow whose values all satisfy $`|x(e)|<k`$. However, the actual number of nowhere-zero $`k`$-flows for $`k>0`$, which we write as $`\phi _\mathrm{\Gamma }(k)`$, does not equal the number of nowhere-zero $`_k`$-flows and indeed was never known to be a polynomial until the recent work of Kochol . Kochol employed standard Ehrhart theory combined with a special construction to prove this. We shall show that Kochol’s theorem is a natural consequence of inside-out polytope theory and can be extended to a reciprocity theorem that interprets $`\phi _\mathrm{\Gamma }(k)`$ at negative arguments.

A *circle* in a graph is a 2-regular connected subgraph. A *cycle* (or *directed cycle*) is a circle in which the edges are oriented in a consistent direction. An orientation of $`\mathrm{\Gamma }`$ is *acyclic* if it has no cycles and *totally cyclic* if every edge lies in a cycle. We call a totally cyclic orientation $`\tau `$ and a flow $`x`$ *compatible* if $`x0`$ when it is expressed in terms of $`\tau `$. Taking the standpoint of the flow $`x`$, the nonzero edge set $`\mathrm{supp}x`$ has a preferred orientation, the one in which $`x0`$ (we call this $`\tau (x)`$; note that it orients only $`\mathrm{supp}x`$) and the zero edges are free to take up any orientation that makes $`\mathrm{\Gamma }`$ totally cyclic. An *isthmus* of a graph is an edge whose deletion increases the number of connected components. There is no totally cyclic orientation if $`\mathrm{\Gamma }`$ has an isthmus.

The *real cycle space* $`Z`$ is defined in $`^E`$ by Equation (1.1). To this space $`Z`$ we associate the polytope and arrangement

$$P:=Z[1,1]^E,:=(_E)^Z,$$

where $`_E`$ is the arrangement of coordinate hyperplanes in $`^E`$. A $`(k+1)`$-flow is then precisely a point $`xZ^d`$ such that $`\frac{1}{k}xP`$ and a nowhere-zero $`k`$-flow is just a point $`xZ^d`$ such that $`\frac{1}{k}xP\left(\right)`$. Consequently,

$$\phi _\mathrm{\Gamma }^0(k+1)=E_P(k)$$
(3.1)
and

$$\phi _\mathrm{\Gamma }(k)=E_{(P,)^{}}(k).$$
(3.2)
###### Theorem 3.1.

Given: a graph $`\mathrm{\Gamma }`$ and its real cycle space $`Z`$.

1. (Kochol ) $`\phi _\mathrm{\Gamma }(k)`$ is a polynomial function of $`k`$ for $`k=1,2,3,\mathrm{}`$ . It has leading term $`(\mathrm{vol}P)k^{\xi (\mathrm{\Gamma })}`$ if $`\mathrm{\Gamma }`$ has no isthmi; otherwise it is identically zero.
2. Furthermore, $`(1)^{\xi (\mathrm{\Gamma })}\phi _\mathrm{\Gamma }(k)`$ for $`k0`$ equals the number of $`(k+1)`$-flows counted with multiplicity equal to the number of totally cyclic orientations of $`\mathrm{\Gamma }`$ that are compatible with the flow.
3. In particular, the constant term $`\phi _\mathrm{\Gamma }(0)`$ equals the number of totally cyclic orientations of $`\mathrm{\Gamma }`$, which equals $`(1)^{\xi (\mathrm{\Gamma })}\overline{\phi }_\mathrm{\Gamma }(1)`$.
4. Finally, the total number of $`k`$-flows for $`k>0`$, nowhere-zero or not, is a polynomial $`\phi _\mathrm{\Gamma }^0(k)`$ satisfying $`\phi _\mathrm{\Gamma }^0(k)=(1)^{\xi (\mathrm{\Gamma })}\phi _\mathrm{\Gamma }^0(1k)`$, whose leading term is the same as that of $`\phi _\mathrm{\Gamma }(k)`$ and whose constant term is $`(1)^{\xi (\mathrm{\Gamma })}`$.

We call $`\phi _\mathrm{\Gamma }`$ the *(strict) integral flow polynomial* of $`\mathrm{\Gamma }`$ and $`\phi _\mathrm{\Gamma }^0(k)`$ the *weak integral flow polynomial*. $`\phi _\mathrm{\Gamma }^0(k)`$ already gives rise to a number of interesting computational problems, as discussed, for example, in .

The reciprocity formula $`\phi _\mathrm{\Gamma }^0(k)=(1)^{\xi (\mathrm{\Gamma })}\phi _\mathrm{\Gamma }^0(1k)`$ leads to the conclusion that $`\phi _\mathrm{\Gamma }^0`$ has no integral zeros. For any $`k>0`$ there is an integral flow, the all-zero flow. Reciprocity takes care of $`k0`$.

###### Proof.

For (a) we apply Theorem 2.1 in $`Z`$. We call upon the total unimodularity of the matrix of the cycle equations (1.1) to deduce that $`P`$ is a convex hull of integer lattice points. Thus, $`E_{(P,)^{}}`$ is a polynomial, and as we saw in (3.2), it equals $`\phi _\mathrm{\Gamma }`$.

Since $`E_{P,}(k)`$ counts pairs $`(x,R)`$ where $`x^dP`$ and $`R`$ is a closed region of $``$ that contains $`x`$, part (b) follows if we show that the regions of $``$ correspond to the totally cyclic orientations of $`\mathrm{\Gamma }`$ and a region of $``$ whose closure contains a chosen point $`xZ^d`$ corresponds to a totally cyclic orientation that is compatible with $`x`$. The first statement was demonstrated by Greene and Zaslavsky in \[8, Section 8\], based on the obvious bijection (given the fixed orientation of $`\mathrm{\Gamma }`$) between orthants of $`^E`$ and orientations of $`\mathrm{\Gamma }`$. The second is then obvious.

Thus the constant term is the number of totally cyclic orientations. The fact that this equals $`t_\mathrm{\Gamma }(0,2)`$ is a theorem originally due to Las Vergnas (see \[13, Proposition 8.1\] and \[14, remark after Theorem 1, p. 296\]) and independently proved by Greene and Zaslavsky \[8, Corollary 8.2\].

Part (d) is standard Ehrhart theory, because a $`k`$-flow is simply a point $`x^d`$ such that $`\frac{1}{k}xP^{}`$. That is, $`\phi _\mathrm{\Gamma }^0(k)=E_P^{}(k)=(1)^{\xi (\mathrm{\Gamma })}E_P(k)`$ by Ehrhart reciprocity. The constant term of $`E_P(k)`$ is $`1`$, the Euler characteristic of $`P`$. It is easy to see that $`E_P^{}(k)=E_P(k1)`$ for $`k>0`$. Consequently,

$$\phi _\mathrm{\Gamma }^0(k)=(1)^{\xi (\mathrm{\Gamma })}E_P(k)=(1)^{\xi (\mathrm{\Gamma })}E_P^{}(1k)=(1)^{\xi (\mathrm{\Gamma })}\phi _\mathrm{\Gamma }^0(1k)$$

if $`k`$ is a positive integer, whence for all $`k`$. ∎

###### Problem 3.2.

Find a formula for, or a combinatorial interpretation of, the leading coefficient $`\mathrm{vol}P`$ of the integral flow polynomials.

###### Problem 3.3.

Is there a combinatorial interpretation of $`\overline{\phi }_\mathrm{\Gamma }(k)`$ for $`k2`$?

###### Example 3.4 (Small graphs).

We calculated the integral flow polynomials of some small graphs by counting integral $`k`$-flows on a computer for $`1k\xi (\mathrm{\Gamma })+2`$ and interpolating to get the polynomial. The graphs were $`mK_2`$, the graph of $`m`$ parallel links, for $`m=3,4,5,6`$, and $`K_4`$. We state our results along with the modular flow polynomials for comparison; the latter are $`\overline{\phi }_\mathrm{\Gamma }^0(k)=k^{\xi (\mathrm{\Gamma })}`$ and $`\overline{\phi }_\mathrm{\Gamma }(k)=\chi _\mathrm{\Gamma }^{}(k)/k`$, $`\mathrm{\Gamma }^{}`$ being the planar dual graph. First, $`3K_2`$:

$`\overline{\phi }^0(k)`$ $`=k^2,`$ $`\overline{\phi }(k)`$ $`=(k1)(k2),`$
$`\phi ^0(k)`$ $`=3k^23k+1,`$ $`\phi (k)`$ $`=3(k1)(k2).`$
Next, $`4K_2`$:

$`\overline{\phi }^0(k)`$ $`=k^3,`$ $`\overline{\phi }(k)`$ $`=(k1)(k^23k+3),`$
$`\phi ^0(k)`$ $`={\displaystyle \frac{(2k1)(8k^28k+3)}{3}},`$ $`\phi (k)`$ $`={\displaystyle \frac{2(k1)(8k^222k+21)}{3}}.`$
Next, $`5K_2`$:

$`\overline{\phi }^0(k)`$ $`=k^4,\overline{\phi }(k)=(k1)(k^34k^2+6k4),`$
$`\phi ^0(k)`$ $`={\displaystyle \frac{115k^4230k^3+185k^270k+12}{12}},`$
$`\phi (k)`$ $`={\displaystyle \frac{5(k1)(k2)(23k^241k+36)}{12}}.`$
Next, $`6K_2`$:

$`\overline{\phi }^0(k)`$ $`=k^5,\overline{\phi }(k)=(k1)(k^45k^3+10k^210k+5),`$
$`\phi ^0(k)`$ $`={\displaystyle \frac{2(2k1)(44k^488k^3+71k^227k+5)}{10}},`$
$`\phi (k)`$ $`={\displaystyle \frac{(k1)(176k^4839k^3+1571k^21404k+620)}{10}}.`$
Finally, $`K_4`$:

$`\overline{\phi }^0(k)`$ $`=k^3,`$ $`\overline{\phi }(k)`$ $`=(k1)(k2)(k3),`$
$`\phi ^0(k)`$ $`=(2k1)(2k^22k+1),`$ $`\phi (k)`$ $`=4(k1)(k2)(k3).`$
###### Problem 3.5.

Is there any general reason why in some of these examples ($`3K_2`$ and $`K_4`$) both of the integral flow polynomials have integral coefficients and the integral nowhere-zero flow polynomial is a multiple of the modular polynomial?

The totally cyclic orientations that are compatible with a flow $`x`$ are the totally cyclic extensions of $`\tau (x)`$ to $`\mathrm{\Gamma }`$. We get such an extension by orienting the contraction $`\mathrm{\Gamma }/\mathrm{supp}x`$ in a totally cyclic manner. The number of such orientations is given by Theorem 3.1(c). Thus we have the following version of Theorem 3.1(b):

###### Corollary 3.6.

$`|\phi _\mathrm{\Gamma }(k)|=_{xPk^1^E}|\overline{\phi }_{\mathrm{\Gamma }/\mathrm{supp}x}(1)|.`$ $`\mathrm{}`$

The *multiplicity* of an integral point $`x`$ with respect to a rational hyperplane arrangement $``$ is the number of closed regions of $``$ that contain $`x`$. As we pointed out in proving Theorem 3.1(b), the number of closed regions of $`_E^Z`$ that contain a flow $`x`$ is equal to the number of totally cyclic extensions to $`\mathrm{\Gamma }`$ of $`\tau (x)`$. Hence, the multiplicity of the integral flow $`x`$ with respect to $`_E^Z`$ is another interpretation of the quantity $`(1)^{\xi (\mathrm{\Gamma }/\mathrm{supp}x)}\overline{\phi }_{\mathrm{\Gamma }/\mathrm{supp}x}(1)`$.

Other formulas arise from the intersection expansions of Theorem 2.2, but as we need its Möbius function, first we have to find the lattice $`()`$ explicitly. We do so in the more general context of signed graphs.

## 4. Flows on signed graphs

The best way to understand the cycle equations (1.1) is in terms of the incidence matrix, which we expound in the general context of signed or bidirected graphs.

Formally, a *signed graph* $`\mathrm{\Sigma }=(\mathrm{\Gamma },\sigma )`$ consists of a graph $`\mathrm{\Gamma }`$ and a function $`\sigma `$ from the set of links and loops of $`\mathrm{\Gamma }`$ to $`\{+,\}`$. (A *link* has two distinct endpoints; a *loop* has two coinciding endpoints. In signed and bidirected graph theory it is convenient to have two more kinds of edges: a *halfedge* has one endpoint and a *loose edge* has no endpoints; neither of these has a sign.) If $`TE`$, then $`\mathrm{\Gamma }|T`$ or $`\mathrm{\Sigma }|T`$ denotes the spanning subgraph whose edge set is $`T`$. Each circle has a sign, which is the product of the signs of its edges. A subgraph or edge set is called *balanced* if it contains no halfedges and every circle in it has positive sign. (See  for the origin of signed graphs and balance; for the general theory of signed graphs see .)

The *bias matroid* (or *signed-graphic matroid*) of $`\mathrm{\Sigma }`$ \[27, Section 5 and Erratum\], written $`G(\mathrm{\Sigma })`$, can be defined by its rank function,

$$r(T)=|V|b(\mathrm{\Sigma }|T)\text{ for an edge set }T,$$

where $`b(\mathrm{\Sigma }|T)`$ is the number of components of the subgraph $`\mathrm{\Sigma }|T`$ that are balanced subgraphs, ignoring any loose edges. The circuits of $`G(\mathrm{\Sigma })`$ are of three kinds: a positive circle, a pair of negative circles that have a single common node, or a pair of node-disjoint negative circles together with a minimal connecting path; here one or both negative circles may be replaced by halfedges. A *coloop* of $`G(\mathrm{\Sigma })`$ is an edge $`e`$ whose deletion makes an unbalanced component balanced; or which is an isthmus connecting two components of $`\mathrm{\Sigma }e`$ of which at least one is balanced (all this by \[27, Theorem 5.l as corrected\]). We define the *cyclomatic number* of $`\mathrm{\Sigma }`$ to be $`|E||V|+b(\mathrm{\Sigma })`$. This is the rank of the dual $`G^{}(\mathrm{\Sigma })`$ of the bias matroid.

A graph is *bidirected* when each end of each edge is independently oriented. We express the bidirection by means of an *incidence function* $`\eta `$ defined on the edge ends: the function is $`+1`$ if the arrow on that end points into the incident node, and $`1`$ otherwise. For an edge end $`\epsilon `$, let $`e(\epsilon )`$ denote the edge and $`v(\epsilon )`$ the node incident to $`\epsilon `$. We define

$$\eta (v,e):=\{\eta (\epsilon ):v(\epsilon )=v\text{ and }e(\epsilon )=e\}.$$

Thus, $`\eta (v,e)=0`$ if $`v`$ and $`e`$ are not incident or $`e`$ is a loose edge or positive loop. The *bidirected incidence matrix* is

$$\mathrm{H}(\mathrm{\Gamma },\eta ):=\left(\eta (v,e)\right)_{V\times E}.$$

A bidirection of a graph is really an orientation of a signed graph. A link or loop $`e`$ with ends $`\epsilon _1`$ and $`\epsilon _2`$ has sign

$$\sigma (e):=\eta (\epsilon _1)\eta (\epsilon _2).$$

In plain language, if the two arrows on $`e`$ point in the same direction, then $`e`$ is positive, but if they conflict, $`e`$ is negative. We call $`\eta `$ an *orientation of the signed graph $`\mathrm{\Sigma }`$*. (See . This notion corresponds to the ordinary notion of graph orientation if we identify an unsigned graph $`\mathrm{\Gamma }`$ with the all-positive graph $`+\mathrm{\Gamma }`$.) We call an *(oriented) incidence matrix of $`\mathrm{\Sigma }`$* any incidence matrix of an orientation of $`\mathrm{\Sigma }`$, writing it $`\mathrm{H}(\mathrm{\Sigma })`$ (and $`\mathrm{H}(\mathrm{\Gamma }):=\mathrm{H}(+\mathrm{\Gamma })`$). The ambiguity arising from the unspecified orientation can usually be ignored, since the only effect of changing the orientation is to negate some columns. Recall that reorienting $`e`$ to $`e^1`$ also has the effect of replacing $`x(e)`$ by $`x(e^1)=x(e)`$ for every $`xA^E`$ ($`A`$ an abelian group). With these conventions we define a *flow* on $`\mathrm{\Sigma }`$ *with values in $`A`$* as any $`xA^E`$ for which

$$\mathrm{H}(\mathrm{\Sigma })x=0,$$
(4.1)
in other words, for which $`x\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma })`$. This definition generalizes that of a flow on a graph; naturally, then, we generalize theorems about flows. A *$`k`$-flow* is an integral flow $`x`$ for which every $`|x(e)|<k`$, just as before. Nowhere-zero $`k`$-flows on signed graphs were studied by Bouchet  and Khelladi , searching for the smallest possible $`k`$.

A *cycle* in an oriented signed graph is a circuit such that no node has all arrows pointing into the node or all arrows pointing out of the node. An orientation is *acyclic* if it has no cycles and *totally cyclic* if every edge belongs to a cycle.

Suppose we have a bidirected graph. *Switching* a node $`v`$ means changing $`\eta `$ to $`\eta ^v`$ defined by

$$\eta ^v(\epsilon )=\{\begin{array}{cc}\eta (\epsilon )\hfill & \text{ if }v(\epsilon )v,\hfill \\ \eta (\epsilon )\hfill & \text{ if }v(\epsilon )=v.\hfill \end{array}$$

The associated switched signed graph is denoted $`\mathrm{\Sigma }^v`$. It is obtained from $`\mathrm{\Sigma }`$ by negating all links incident with $`v`$.

### 4.1. Group-valued flows

We begin our treatment of signed graphs with the analog of the modular flow polynomial, since as far as we know it has not been published. The *Tutte polynomial* $`t_\mathrm{\Sigma }(x,y)`$ of $`\mathrm{\Sigma }`$ is defined to be that of $`G(\mathrm{\Sigma })`$. (It is not equal to that of the underlying graph unless $`\mathrm{\Sigma }`$ is balanced. See  for the Tutte polynomial of a matroid.)

###### Theorem 4.1.

For each signed graph $`\mathrm{\Sigma }`$ there is a polynomial $`\overline{\phi }_\mathrm{\Sigma }(k)`$ such that the number of nowhere-zero flows on $`\mathrm{\Sigma }`$ with values in a finite abelian group $`A`$ of odd order is $`\overline{\phi }_\mathrm{\Sigma }(|A|)`$. In fact,

$$\overline{\phi }_\mathrm{\Sigma }(k)=(1)^{\xi (\mathrm{\Sigma })}t_\mathrm{\Sigma }(0,1k).$$

###### Proof.

For our proof by induction on $`|E|`$ we need deletion and contraction of edges in signed graphs, as in . Deletion is simply removing the edge with no other change. The contraction $`\mathrm{\Sigma }/e`$ by an edge $`e`$ is done differently for the four kinds of edge. A loose edge or positive loop is simply deleted. A halfedge or negative loop is deleted and its supporting node is also deleted, but any other edges incident to that node are retained; such an edge that was a link becomes a halfedge, but if it was a loop or halfedge it becomes a loose edge. A positive link is deleted and its endpoints are identified to a single node. To contract a negative link we switch an endpoint so the link becomes positive; then the link is deleted and the endpoints are identified.

In the proof we fix $`A`$ and an orientation $`\eta `$ of $`\mathrm{\Sigma }`$ and write $`\overline{\phi }_\mathrm{\Sigma }(A)`$ for the number of nowhere-zero $`A`$-flows on $`\mathrm{\Sigma }`$.

It is clear that if $`\mathrm{\Sigma }`$ has components $`\mathrm{\Sigma }_1,\mathrm{},\mathrm{\Sigma }_c`$, then $`\overline{\phi }_\mathrm{\Sigma }(A)=\overline{\phi }_{\mathrm{\Sigma }_1}(A)\mathrm{}\overline{\phi }_{\mathrm{\Sigma }_c}(A)`$. Analogously, $`t_\mathrm{\Sigma }=t_{\mathrm{\Sigma }_1}\mathrm{}t_{\mathrm{\Sigma }_c}`$. Therefore, we may assume $`\mathrm{\Sigma }`$ is connected.

Suppose $`e`$ is a positive link of $`\mathrm{\Sigma }`$, oriented from $`v`$ to $`w`$, such that deleting $`e`$ from $`\mathrm{\Sigma }`$ does not increase the number of balanced components; that is, $`e`$ is not a coloop. Let $`x^{\prime \prime }`$ be a nowhere-zero $`A`$-flow on $`\mathrm{\Sigma }/e`$. We can define a flow on $`\mathrm{\Sigma }`$ by

$`x(f)`$ $`=x^{\prime \prime }(f)\text{ if }fe,`$
$`x(e)`$ $`={\displaystyle \underset{fe}{}}\eta (v,f)x(f).`$
Then $`\mathrm{H}(\mathrm{\Sigma })x=0`$. If $`x(e)0`$, $`x`$ is a nowhere-zero flow on $`\mathrm{\Sigma }`$; if $`x(e)=0`$, $`x`$ is a nowhere-zero flow on $`\mathrm{\Sigma }e`$. Conversely, any nowhere-zero flow on $`\mathrm{\Sigma }e`$ or $`\mathrm{\Sigma }`$ gives rise to one on $`\mathrm{\Sigma }/e`$. Since the assumption about $`e`$ guarantees that $`\mathrm{\Sigma }`$, $`\mathrm{\Sigma }/e`$, and $`\mathrm{\Sigma }e`$ all have the same number of balanced components,

$$(1)^{\xi (\mathrm{\Sigma })}\overline{\phi }_\mathrm{\Sigma }(A)=(1)^{\xi (\mathrm{\Sigma }/e)}\overline{\phi }_{\mathrm{\Sigma }/e}(A)+(1)^{\xi (\mathrm{\Sigma }e)}\overline{\phi }_{\mathrm{\Sigma }e}(A).$$
(4.2)
If $`e`$ is a negative link, subject to the same hypothesis on balance, with endpoints $`v`$ and $`v^{}`$, we switch $`v`$ to make $`e`$ positive. Because a flow on $`\mathrm{\Sigma }`$ remains a flow after switching, $`\overline{\phi }_{\mathrm{\Sigma }^v}(A)=\overline{\phi }_\mathrm{\Sigma }(A).`$ Thus, (4.2) is valid for a negative link.

The analogous Tutte-polynomial formula, $`t_\mathrm{\Sigma }=t_{\mathrm{\Sigma }/e}+t_{\mathrm{\Sigma }e}`$, is valid as long as $`e`$ is not a coloop in $`G(\mathrm{\Sigma })`$, but that is our balance assumption. In this case, therefore, the theorem is valid for $`\mathrm{\Sigma }`$ by induction.

If on the other hand an edge $`e`$ is a coloop, then $`t_\mathrm{\Sigma }(0,y)=0`$ and, by the proofs of Bouchet’s Lemmas 2.4 and 2.5 , also $`\overline{\phi }_\mathrm{\Sigma }(A)=0`$. (The oddness of $`A`$, so that $`2a=0`$ implies $`a=0`$ in $`A`$, is needed at this point.)

The preceding arguments reduce the theorem to the case of a signed graph with a single node $`v`$. The flow in a loose edge or positive loop can be any nonzero value in $`A`$, independent of all other flow values. Therefore, $`\overline{\phi }_\mathrm{\Sigma }(A)=(|A|1)^l\overline{\phi }_{\mathrm{\Sigma }_0}(A)`$ where $`l`$ is the number of positive loops and loose edges and $`\mathrm{\Sigma }_0`$ is $`\mathrm{\Sigma }`$ with all such edges deleted. Now let us assume $`\mathrm{\Sigma }`$ has one node and its edges are halfedges $`e_1,\mathrm{},e_i`$ and negative loops $`f_1,\mathrm{},f_j`$. We may assume they are oriented into $`v`$, so the total inflow at $`v`$ is

$$x(e_1)+\mathrm{}+x(e_i)+2x(f_1)+\mathrm{}+2x(f_j)=0$$

by the cycle condition (4.1). If $`i+j=0`$, there is one such flow, in agreement with $`t_\mathrm{\Sigma }=1`$. If $`i+j=1`$, there is none (again we require $`|A|`$ odd) so $`\overline{\phi }_\mathrm{\Sigma }=0`$, in agreement with $`t_\mathrm{\Sigma }(0,y)=0`$. If $`i+j>1`$, we get a nowhere-zero $`A`$-flow by taking arbitrary nonzero values for $`x`$ except on one edge, say $`x(e)`$, which is determined by the rest through the cycle equations. The number of such choices in which $`x(e)0`$ is $`\overline{\phi }_\mathrm{\Sigma }(A)`$; the number in which $`x(e)=0`$ is $`\overline{\phi }_{\mathrm{\Sigma }e}(A)`$. Therefore,

$`\overline{\phi }_\mathrm{\Sigma }(A)`$ $`=(1)^{i+j1}(1|A|)^{i+j1}\overline{\phi }_{\mathrm{\Sigma }e}(A)`$
$`=(1)^{\xi (\mathrm{\Sigma }/e)}t_{\mathrm{\Sigma }/e}(0,1|A|)(1)^{\xi (\mathrm{\Sigma }e)}t_{\mathrm{\Sigma }e}(0,1|A|)`$
by the fact that $`G(\mathrm{\Sigma }/e)`$ has rank 0 and induction on $`i+j=|E|`$,
$`=(1)^{\xi (\mathrm{\Sigma })}t_\mathrm{\Sigma }(0,1|A|)`$
by the fact that $`e`$ is not a loop or coloop in $`G(\mathrm{\Sigma })`$. Our theorem now follows by induction. ∎

###### Problem 4.2.

Is there any significance to $`\overline{\phi }_\mathrm{\Sigma }^0`$ or $`\overline{\phi }_\mathrm{\Sigma }`$ evaluated at even natural numbers?

Theorem 4.1 means there is a polynomial $`\overline{\phi }_\mathrm{\Sigma }(k)`$, which we call the *(strict) modular flow polynomial*, such that for any odd positive number $`k`$, $`\overline{\phi }_\mathrm{\Sigma }(k)`$ is the number of nowhere-zero flows on $`\mathrm{\Sigma }`$ with values in any fixed abelian group of order $`k`$. This is reminiscent of signed-graph coloring, where only odd values of $`\lambda `$ can be interpreted in the chromatic polynomial $`\chi _\mathrm{\Sigma }(\lambda )`$ . For coloring, though, there is another polynomial which counts restricted colorings when evaluated at even integers; and the two polynomials are related (as we showed in ). We wonder whether there could be something similar with the modular flow polynomial, and whether flows and colorings might be connected through duality of signed graphs, analogously to the duality of colorings and flows on planar graphs.

###### Example 4.3.

The number of $`A`$-flows depends on the group $`A`$ when it has even order. Consider the signed graph consisting of two negative loops at a node $`v`$. Orient both loops into $`v`$. The cycle equation (1.1) is $`2x(e)+2x(f)=0`$. We compare two groups of order 4. If $`A`$ is the Klein four-group $`_2\times _2`$, then every $`x:EA`$ satisfies the cycle equations and we have

$$\overline{\phi }_\mathrm{\Sigma }^0(A)=16,\overline{\phi }_\mathrm{\Sigma }(A)=9.$$

If $`A=_4`$, then the $`A`$-flows are $`(x(e),x(f))\{0,2\}^2\{1,3\}^2`$ and

$$\overline{\phi }_\mathrm{\Sigma }^0(A)=8,\overline{\phi }_\mathrm{\Sigma }(A)=5.$$

For comparison, at odd values of $`k`$ we have

$$\overline{\phi }_\mathrm{\Sigma }^0(k)=k,\overline{\phi }_\mathrm{\Sigma }(k)=k1.$$

###### Corollary 4.4.

The number of totally cyclic orientations of $`\mathrm{\Sigma }`$ equals $`(1)^{\xi (\mathrm{\Sigma })}\overline{\phi }_\mathrm{\Sigma }(1)`$.

###### Proof.

The number of totally cyclic reorientations of an orientation of a matroid $`M`$ is $`t_M(0,2)`$ . Since cycles in an orientation of $`\mathrm{\Sigma }`$ are the same as cycles in the corresponding orientation of $`G(\mathrm{\Sigma })`$ , the number of totally cyclic orientations of $`\mathrm{\Sigma }`$ equals $`t_{G(\mathrm{\Sigma })}(0,2)=(1)^{\xi (\mathrm{\Sigma })}\overline{\phi }_\mathrm{\Sigma }(1)`$. ∎

### 4.2. Integral $`k`$-flows on signed graphs

Now it is time for integral flows. For $`k>0`$ let

$$\phi _\mathrm{\Sigma }(k):=\text{ the number of nowhere-zero }k\text{-flows on }\mathrm{\Sigma }.$$

As with abelian-group flows, $`\phi _\mathrm{\Sigma }=0`$ if there is a coloop in $`G(\mathrm{\Sigma })`$. Let

$$\phi _\mathrm{\Sigma }^0(k):=\text{ the number of all }k\text{-flows on }\mathrm{\Sigma },$$

also for $`k>0`$. We take $`Z`$ to be the real cycle space $`\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma })`$—this is the solution space of Equation (1.1)—and, just as with unsigned graphs,

$$P:=Z[1,1]^E\text{ and }:=_E^Z$$

where $`_E`$ is the coordinate-hyperplane arrangement. As with ordinary graphs, a flow $`x`$ and an orientation $`\eta `$ are *compatible* if $`x0`$ when expressed in terms of $`\eta `$.

###### Theorem 4.5.

1. For any signed graph $`\mathrm{\Sigma }`$, $`\phi _\mathrm{\Sigma }(k)`$ is a quasipolynomial function of $`k`$ for $`k=1,2,3,\mathrm{}`$ . Its period is 1 or 2, and is 1 if $`\mathrm{\Sigma }`$ is balanced. $`\phi _\mathrm{\Sigma }(k)`$ has leading term $`(\mathrm{vol}P)k^{\xi (\mathrm{\Sigma })}`$ if $`G(\mathrm{\Sigma })`$ has no coloops; otherwise $`\phi _\mathrm{\Sigma }(k)`$ is identically zero.
2. Furthermore, $`(1)^{\xi (\mathrm{\Sigma })}\phi _\mathrm{\Sigma }(k)`$ for $`k0`$ equals the number of $`(k+1)`$-flows counted with multiplicity equal to the number of compatible totally cyclic orientations of $`\mathrm{\Sigma }`$.
3. In particular, the constant term $`\phi _\mathrm{\Sigma }(0)`$ equals the number of totally cyclic orientations of $`\mathrm{\Sigma }`$, which equals $`(1)^{\xi (\mathrm{\Sigma })}\overline{\phi }_\mathrm{\Sigma }(1)`$.
4. Finally, $`\phi _\mathrm{\Sigma }^0(k)`$ is a quasipolynomial of period 1 or 2 (period 1 if $`\mathrm{\Sigma }`$ is balanced) whose leading term is the same as that of $`\phi _\mathrm{\Sigma }(k)`$ and whose constant term is $`(1)^{\xi (\mathrm{\Gamma })}`$. Furthermore, $`\phi _\mathrm{\Sigma }^0(k)=(1)^{\xi (\mathrm{\Gamma })}\phi _\mathrm{\Sigma }^0(1k)`$.

From (d) we see that, even when $`\phi ^0`$ has period $`2`$, in a way it consists only of one polynomial. The odd constituent, $`\phi _{\text{odd}}^0`$, is determined by the even constituent through

$$\phi _{\text{odd}}^0(2j+1)=(1)^{\xi (\mathrm{\Gamma })}\phi _{\text{even}}^0(2j).$$

###### Problem 4.6.

Is there a nontrivial unbalanced signed graph for which $`\phi _\mathrm{\Sigma }`$ has period $`1`$? (For the dual function, the chromatic quasipolynomial, there is not. See the second remark after \[4, Corollary 5.9\].) The graph of one node in Example 4.8 shows that trivial examples exist. As for $`\phi _\mathrm{\Sigma }^0`$, there exists at least one such graph with more than one node, but still very small; see Example 4.8.

The mere existence of such examples is significant: it suggests that the duality between flows and colorings is imperfect and limited.

###### Lemma 4.7.

The vertices of $`(P,)`$ are half integral.

###### Proof.

We may as well assume $`\mathrm{\Sigma }`$ has a halfedge at every node; thus $`\mathrm{H}(\mathrm{\Sigma })`$ contains an identity matrix $`I_n`$. A vertex is a solution of $`\mathrm{H}(\mathrm{\Sigma })x=0`$ with $`|E|n`$ coordinates of $`x`$ set equal to fixed values in $`\{0,1,1\}`$. Let $`B`$ be the edge set whose coordinates in $`x`$ are left undetermined, let $`B^c:=EB`$, and write $`x=(x_B,x_{B^c})^\text{T}`$. Then $`x`$ is the unique solution of $`\mathrm{H}(\mathrm{\Sigma }|B)x_B=\mathrm{H}(\mathrm{\Sigma }|B^c)x_{B^c}`$.

The remainder of the proof is based on work of Jon Lee. Lee proved that the null space $`\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma })`$ is 2-regular \[15, Proposition 9.1\] and that if $`A`$ is a nonsingular square matrix for which $`\mathrm{Nul}[IA]`$ is 2-regular, then $`A^1b`$ is half integral for every integral vector $`b`$ (a special case of \[15, Proposition 6.1\]; the definition of 2-regularity need not concern us). These facts applied to $`A=\mathrm{H}(\mathrm{\Sigma }|B)`$ imply that the solution of $`\mathrm{H}(\mathrm{\Sigma }|B)x=b`$ is half integral for any $`b^B`$. Apply this to $`b=\mathrm{H}(\mathrm{\Sigma }|B^c)x_{B^c}`$. ∎

###### Proof of Theorem 4.5.

The proof is similar to that of Theorem 3.1. In (a) and (d), instead of total unimodularity we have Lemma 4.7 to tell us that the denominator of $`(P,)`$, hence the period of the Ehrhart quasipolynomials, divides 2.

For (b) we need to show that the regions of $``$ correspond to the totally cyclic orientations of $`\mathrm{\Sigma }`$. The latter are the totally cyclic reorientations of the natural orientation of $`G(\mathrm{\Sigma })`$, which is the oriented matroid of columns of $`\mathrm{H}(\mathrm{\Sigma })`$ \[29, Theorem 3.3\]. Now we apply Lemma 2.3(b).

For (c) we use Corollary 4.4. ∎

###### Example 4.8.

We calculated the flow polynomials and modular flow polynomials of some small signed graphs. First we treat the signed graph with two negative loops at one node, for comparison with the modular flow polynomials in Example 4.3:

$$\phi _\mathrm{\Sigma }^0(k)=2k1,\phi _\mathrm{\Sigma }(k)=2(k1).$$

Another signed graph, only slightly larger, has two nodes joined by positive and negative edges and at each node either a halfedge or a negative loop. We write $`\pm K_2^{(i,j)}`$ for this graph if $`i`$ nodes have halfedges and $`j`$ other nodes have negative loops and $`\phi _{(i,j)}`$ for the polynomials; the examples we calculated are where $`i+j=2`$. The modular nowhere-zero flow polynomial is the characteristic polynomial of the dual matroid of $`G(\pm K_2^{(i,j)})`$, which is the four-point line. The modular polynomials are

$`\overline{\phi }_{(i,j)}^0(k)`$ $`=k^2,`$
$`\overline{\phi }_{(i,j)}(k)`$ $`=(k1)(k3).`$
The integral polynomials are

$`\phi _{(0,2)}^0(k)=\phi _{(2,0)}^0(k)`$ $`=2k^22k+1,`$
$`\phi _{(0,2)}(k)=\phi _{(2,0)}(k)`$ $`=\{\begin{array}{cc}2(k1)(k3)\hfill & \text{if }k\text{ is odd},\hfill \\ 2(k2)^2\hfill & \text{if }k\text{ is even}\hfill \end{array}`$
and

$`\phi _{(1,1)}^0(k)`$ $`=\{\begin{array}{cc}\frac{1}{2}(3k^22k+1)\hfill & \text{if }k\text{ is odd},\hfill \\ \frac{1}{2}(3k^24k+2)\hfill & \text{if }k\text{ is even},\hfill \end{array}`$
$`\phi _{(1,1)}(k)`$ $`=\{\begin{array}{cc}\frac{1}{2}(3k^212k+9)\hfill & \text{if }k\text{ is odd},\hfill \\ \frac{1}{2}(3k^214k+16)\hfill & \text{if }k\text{ is even}.\hfill \end{array}`$
###### Problem 4.9.

We do not understand why $`\pm K_2^{(0,2)}`$ and $`\pm K_2^{(2,0)}`$ have the same flow quasipolynomials but $`\pm K_2^{(1,1)}`$ does not, nor why $`\phi _{(0,2)}^0`$ has period one, nor why the odd constituent of $`\phi _{(0,2)}`$ is an integral multiple of $`\overline{\phi }_{(i,j)}`$.

### 4.3. Half integrality and the incidence matrix

In our geometric treatment of graph coloring in \[4, Section 5\] we noticed an important half-integrality property of the signed-graphic hyperplane arrangement $`[\mathrm{\Sigma }]`$, which consists of the dual hyperplanes to all the columns in the incidence matrix of $`\mathrm{\Sigma }`$. It is the next lemma, which involves a polytope $`P=[0,1]^d`$ and the affine arrangement $`^{\prime \prime }[\mathrm{\Sigma }]`$ which is $`[\mathrm{\Sigma }]`$ translated by the vector $`\frac{1}{2}(1,1,\mathrm{},1)^\text{T}`$.

###### Lemma 4.10 (\[4, Lemma 5.7\]).

If $`\mathrm{\Sigma }`$ is a signed graph, $`(P,^{\prime \prime }[\mathrm{\Sigma }])`$ has half-integral vertices.

Despite their appearance, not only are Lemmas 4.7 and 4.10 similar in statement, both also involve the incidence matrix. A *basic solution* of a linear program $`\mathrm{H}(\mathrm{\Sigma })^\text{T}xb`$, $`x0`$ is the solution of $`\mathrm{H}(\mathrm{\Sigma }|B)^\text{T}x=b`$ for some set $`B`$ of $`n`$ linearly independent columns of $`\mathrm{H}(\mathrm{\Sigma })`$.

###### Proposition 4.11.

Every basic solution of $`\mathrm{H}(\mathrm{\Sigma })^\text{T}xb`$, $`x0`$ is half integral for any $`b^n`$.

###### Proof that Lemma 4.10 and Proposition 4.11 are equivalent..

We may assume that $`\mathrm{\Sigma }`$ contains a negative loop at every node. Write $`a_e`$ for the column of the incidence matrix that belongs to $`e`$. The equations of the hyperplanes in $`^{\prime \prime }[\mathrm{\Sigma }]`$ are $`a_e^\text{T}x=\frac{1}{2}a_e^\text{T}(1,1,\mathrm{},1)^\text{T}`$; this is 0 or 1 if $`e`$ is a loop or link but it is $`\frac{1}{2}`$ if $`e`$ is a halfedge at node $`v_i`$ and in that case the equation simplifies to $`x_i=\frac{1}{2}`$. In the situation of Lemma 4.10, the vertices of $`(P,^{\prime \prime }[\mathrm{\Sigma }])`$ are obtained by choosing from among the equations $`x_i=0`$, $`x_i=1`$ (from $`P`$) and $`x_i=\frac{1}{2}`$, $`a_e^\text{T}x=0`$ or $`1`$ (from $`^{\prime \prime }[\mathrm{\Sigma }]`$) a subset of $`n`$ equations whose coefficient matrix is nonsingular. An equation $`x_i=0`$ or 1 has the form $`a_e^\text{T}x=0`$ or 1 with $`e`$ the negative loop at $`v_i`$, so we need not consider it separately. Thus, half integrality of vertices of $`([0,1]^n,^{\prime \prime }[\mathrm{\Sigma }])`$ implies half integrality of the solution of $`\mathrm{H}(\mathrm{\Sigma }|B)^\text{T}x=b`$ for any $`b^n`$. The converse is obvious. ∎

Our attention was drawn to the relationship between Lemma 4.10 and half integrality (and Lee’s work) by a recent manuscript of Appa and Kotnyek .

### 4.4. Nowhere-zero flows reduce to flows with Möbius complications

The last main result expresses the nowhere-zero integral flow polynomial in terms of the weak integral flow polynomials of subgraphs. We begin with structural lemmas. As before, $`Z`$ is the cycle space, $`P:=[1,1]^EZ`$, and $`:=_E^Z`$. For a flat $`S()`$ we define

$$E(S):=\{eE:SH_e\}=\{eE:x(e)=0\text{ for all }xS\}.$$

This is the $`E_Z(S)`$ of Lemma 2.3(b). We see that $`E(S)^c`$ is the union of the suppports of the vectors in $`S`$.

###### Lemma 4.12.

The lattice of flats of $``$ is isomorphic to the lattice of closed sets of the dual of the bias matroid, $`G^{}(\mathrm{\Sigma })`$. The isomorphism is given by $`SE(S)`$. The corresponding matroid isomorphism $`G^{}(\mathrm{\Sigma })M()`$ is given by $`eH_eZ`$.

###### Proof.

This is an application of Lemma 2.3. The matrix is $`\mathrm{H}(\mathrm{\Sigma })`$. We know $`M(\mathrm{H}(\mathrm{\Sigma }))`$ is the bias matroid $`G(\mathrm{\Sigma })`$ by \[27, Theorem 8A.1\], so $`G^{}(\mathrm{\Sigma })`$ is the chain-group matroid of $`\mathrm{Row}\mathrm{H}(\mathrm{\Sigma })`$. The lemma applies because the real cycle space $`Z=\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma })`$. ∎

(Lemma 4.12 holds good for the canonical hyperplane representation of any $`F^{}`$-gain graph $`\mathrm{\Phi }`$, for any field $`F`$ \[30, Section 2\]. Denoting an incidence matrix by $`\mathrm{H}(\mathrm{\Phi })`$ and taking $`Z=\mathrm{Nul}\mathrm{H}(\mathrm{\Phi })`$, we have $`M(_E^Z)=G^{}(\mathrm{\Phi })`$. But we digress.)

###### Lemma 4.13.

$`\phi _\mathrm{\Sigma }`$ is identically zero if and only if $`G(\mathrm{\Sigma })`$ has a coloop.

###### Proof.

This is an application of Bouchet’s theorem on integral chain-group matroids \[5, Proposition 3.1\]: the chain-group has a nowhere-zero chain if and only if the matroid has no coloop. In our case the chain-group is the group of integral flows, $`\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma })`$. Its chain-group matroid is dual to that of $`\mathrm{Row}\mathrm{H}(\mathrm{\Sigma })`$, which is dual to the column matroid of $`\mathrm{H}(\mathrm{\Sigma })`$, which is $`G(\mathrm{\Sigma })`$. ∎

###### Lemma 4.14.

A flat $`S`$ of $``$ can be represented as $`[\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma }|E(S)^c)]\times \{0\}^{E(S)}`$.

###### Proof.

The lemma is obvious from the definitions of $`Z`$ and $`E(S)`$. ∎

###### Theorem 4.15.

Take a signed graph $`\mathrm{\Sigma }`$. Letting $`T`$ range over all subsets of $`E`$, or merely over all for which $`G(\mathrm{\Sigma })|T`$ has no coloops (that is, all complements of flats of the dual bias matroid $`G^{}(\mathrm{\Sigma })`$),

$$\phi _\mathrm{\Sigma }(k)=\underset{T}{}|\mu (\widehat{0},T^c)|\phi _{\mathrm{\Sigma }|T}^0(k+1)$$
(4.3)
and

$$\phi _\mathrm{\Sigma }(k)=\underset{T}{}\mu (\widehat{0},T^c)\phi _{\mathrm{\Sigma }|T}^0(k+1),$$
(4.4)
where $`\mu `$ is the Möbius function of $`G^{}(\mathrm{\Sigma })`$ and $`\widehat{0}`$ is the set of coloops of $`G(\mathrm{\Sigma })`$.

###### Proof.

The polytope and the arrangement are transverse because $``$ intersects $`P^{}`$.

Since $`\phi _{\mathrm{\Sigma }|T}=0`$ if $`G(\mathrm{\Sigma })|T`$ has a coloop by Lemma 4.13, the two ranges of summation are equivalent. For $`S()`$, by Lemma 4.14 we know that

$$PS=[1,1]^E\left([\mathrm{Nul}\mathrm{H}(\mathrm{\Sigma }|E(S)^c)]\times \{0\}^{E(S)}\right).$$

Take $`T=E(S)^c`$. Then

$$PS=\left([1,1]^TZ^{}\right)\times \{0\}^{T^c}$$

where $`Z^{}`$ is the real cycle space of $`\mathrm{\Sigma }|T`$. Its Ehrhart polynomial equals $`\phi _{\mathrm{\Sigma }|T}^0(k+1)`$.

Now the result follows from Lemma 4.12, Theorem 2.2, Equation (3.2), and Theorem 3.1(d). ∎

A reminder: to apply the theorem to a graph $`\mathrm{\Gamma }`$, take $`\mathrm{\Sigma }=+\mathrm{\Gamma }`$.

Thus, the strict integral flow polynomial can be expressed in terms of the weak polynomial and invariants of $`G^{}(\mathrm{\Sigma })`$. If the weak polynomial were as simple as in the case of colorings, where it is a monomial \[4, Section 5\], we would have a nice formula for the number of nowhere-zero $`k`$-flows. But such is not the case.

It may be helpful to list some characterizations of the edge sets that support nowhere-zero integral flows.

###### Proposition 4.16.

For $`TE:=E(\mathrm{\Sigma })`$, the following properties are equivalent.

1. $`G(\mathrm{\Sigma })|T`$ has no coloops.
2. $`\mathrm{\Sigma }|T`$ has a totally cyclic orientation.
3. $`\mathrm{\Sigma }|T`$ has a nowhere-zero integral flow.
4. $`\mathrm{\Sigma }|T`$ has a nowhere-zero real flow.
5. $`T^c`$ is closed in the dual bias matroid $`G^{}(\mathrm{\Sigma })`$.
6. $`T=E(S)^c`$ for some flat $`S((_E)^Z)`$.

###### Proof.

(i) $``$ (ii) for graphs is Robbins’ theorem . We could prove it for signed graphs, but the simplest approach is via oriented matroids. We know that the number of totally cyclic reorientations of an orientation of a matroid $`M`$ is $`t_M(0,2)`$  and that this equals 0 if and only if $`M`$ has a coloop. Apply that to the natural orientation of $`G(\mathrm{\Sigma })`$.

(i) $``$ (iii) by Lemma 4.13.

(iii) $``$ (iv) is trivial.

(iv) $``$ (i) by the proofs of \[5, Lemmas 2.4 and 2.5\], which amount to saying that any flow on $`\mathrm{\Sigma }`$ with values in an abelian group where $`2a=0a=0`$ must be zero on every coloop. Here the group is the additive group of $``$.

(v) $``$ (i): By matroid duality the complements of the closed sets in $`G^{}(\mathrm{\Sigma })`$ are the edge sets that do not contain a coloop of $`G(\mathrm{\Sigma })`$.

(v) $``$ (vi): This is Lemma 4.12. ∎


format: text

text:
# On the stability and the similarity of 𝑁=82 isotones

## Abstract

Here we study the stability and the similarity of all even $`58Z70`$, $`N=82`$ isotones. We confirm the two decades old study of one of the authors (AA) regarding the extra-ordinary stability and the similarity of these nuclei. We present here a new evidence which shows very strongly the said magicity of those nuclei and as such there exists a new “plateau” of magicity. Three well studied theoretical models which have been successfully applied in nuclear physics are used here to study the above phenomena. None of these model is able to reproduce the similarity and the doubly magic character of these nuclei. Therefore this hints at “new physics” in these $`N=82`$ isotones.

The $`N=82`$ isotones display a high level of regularity and thus have been of great interest to both the experimentalists and the theorists Aba84 ; Ham90 ; And90 ; Hol97 ; Mat00 . Though there have been claims that $`Z=64`$ Gd isotone was something special, through systematic study of diverse empirical data, it was argued by one of the authors (AA) that there was a whole “plateau” of stability for all even $`58Z70`$, $`N=82`$ isotones and that as such all these be treated as doubly magic nuclei Aba84 . Also all these nuclei were found to be strikingly similar to each other Aba84 . The idea of “changing magicities” was rather novel then. However today, one does speak of changing magicity for low mass nuclei, for example new magic numbers at $`N=`$ 6, 14, 34 etc Tan01 ; Thi00 ; Dlo03 . In this letter we would like to reexamine this two decades old idea of Abbas Aba84  regarding the “plateau of doubly magic $`N=82`$ isotones and their similarity. In particular we shall study a new “smoking gun” kind of evidence to confirm Abbas’ plateau of stability Aba84 . We shall also study this “plateau” of stability using theoretical models like Skyrme–Hartree–Fock-Bogoliubov (HFB), relativistic mean field (RMF) theory etc. We find that all these models fail to reproduce the new magicities.

Abbas has studied even $`58Z70`$, $`N=82`$ isotones through empirical evidence available then (i.e. 1983) Aba84 . We have reexamined the same in the light of more accurate and recent experimentally available data. We reconfirm the analysis as per the empirical data. We would not like to repeat the same here and refer the reader to Ref. Aba84  as to the similarity and the magicity of these nuclei. However for the sake of completeness we would like to summarize and tabulate a few of the arguments therein Aba84 .

1. In $`Z=`$ 58, 60, 62, 64, 66, 68, 70, $`N=82`$ isotones the lowest first excited state (level $`2^+`$ or $`3^{}`$) is very high and steady at about 1.6 MeV for all the nuclei
2. A study of low lying states in $`N=81`$, 80, 79 and 78 isotones with $`Z=`$ 58, 60, 62, 64, 66, 68, 70 indicates amazing similarity and stability
3. The ratio $`E_1(4^+)/E_1(2^+)`$ for all these nuclei is $``$ 1.3. This puts all these nuclei in the category of “doubly-magic” as per standard interpretation.
4. The rms radii change very slowly as mass number changes over this whole region. Plus many other arguments in support of the said statement regarding the similarity and the stability of these nuclei. Here we discuss a further “smoking gun” kind of evidence in support of the above idea.

To discuss magicity one normally plots separation energies $`S_{1n}`$ and $`S_{2n}`$ as a function of neutron number $`N`$ for a particular proton number $`Z`$ or plot $`S_{1p}`$ and $`S_{2p}`$ as a function of proton number $`Z`$ for a particular $`N`$. If we do so for $`N=82`$ isotones then we would like to point out here that the evidences for magicity continue to be there but that it is not very prominentAba84 . It is very common to plot $`S_{2p}`$ and look for kinks as evidence for magicity Thi00 ; Dlo03 ; Tho03 . However it should be pointed out that this one in itself should not be taken as very conclusive evidence in favour or against magicity Aba84 ; Plo81 .

We therefore plot separation energies differently. We plot $`S_{1n}`$ as a function of proton number $`Z`$ for a particular $`N`$. We show this in Fig. 1 for the magic numbers $`N=28`$ and $`N=50`$ isotones. We immediately note that in $`N=28`$ case the magic number $`Z=20`$ and $`Z=28`$ show up very prominently. For $`N=50`$ case though the $`Z`$-number does not pass through any standard magic number it does indicate extra stability at $`Z=34`$, 36 and 38. We know that the $`Z=38`$ case 88Sr anyway is known to form a stable structure, enabling good shell model description of 90Zr excited states Aba84 . These $`N=50`$ isotones actually are precursors of a more interesting effect to be discussed below.

We plot $`S_{1n}`$ as a function of $`Z`$ for $`N=82`$ in Fig. 2. The magicity at $`Z=50`$ is very clearly demonstrated here. But amazingly exactly the same magicity is indicated, very prominently at $`Z=62`$, 64, 68 and 70. The magnitude of $`S_{1n}`$ at all these neighbouring even $`Z`$-numbers is comparable to the magnitude of $`S_{1n}`$ at $`Z=50`$. We know $`Z=50`$ (Sn nucleus) is one of the “best ” magic number in nuclear physics. As per Fig. 2 if we can call $`Z=50`$ magic there is no reason why we should not do the same for all the even $`Z`$ number discussed above. This “smoking gun” evidence supplemented with those already provided by Abbas Aba84  should convince one that all these nuclei are indeed “doubly magic”.

Does this magicity persist when two or even four neutrons are pulled out ? The corresponding $`N=80`$ plot (inset, Fig. 2) shows that indeed it is so. We also plot the same for $`N=78`$ (inset, Fig. 2) which also continues to show stability. All this should be treated as strong evidence for double magicity of all these even $`Z`$ nuclei. We would like to point out that we do see similar effect for $`N=50`$, $`N=48`$ case but some other evidences of double magicity and similarity are missing in these nuclei (as discussed in ref. Aba84 ) and hence these should be actually treated as precursor of the amazing phenomenon pointed out in this paper.

Today we do have elaborate theoretical framework of various kind which are being successfully applied to study nuclear phenomena. We pick up three of these very successful models which are used in nuclear physics.

We have carried out extensive study microscopically in the nonlinear relativistic mean field theory of Boguta and Bodmer 12 , is an extended version of Walecka 4  theory. We have adopted the NL3 14  interactions in our study. The NL3 interaction has been widely used in recent years in the calculation of varieties of nuclear properties like binding energy, rms radii and giant resonances etc. and have been accepted to be very successful. In the present study, we expanded the fields in harmonic oscillator basis and studied the stability of the result for each nucleus by varying the number of harmonic oscillator shells between $`N_F=N_B=12`$ to 14. We did the same exercise taking quadrupole deformation in our calculation, where the basis deformation parameter $`\beta _0`$, was varied between $`0.4`$ to 0.4 in the step of 0.1. We used a constant gap BCS pairing calculation to take into account the pairing correlation. The pairing constant gap is taken for the drip-line nuclei following the prescription of Medland and Nix 16 . The formalism and calculation are quite standard and have been widely used in the literature, the details of which can be seen in Refs. 17 ; 18 . It is to be noted that in the present study, we have performed three different calculations as to pairing, i.e. (a) taking pairing in both even and odd nucleon, (b) without pairing and (c) pairing correlation is considered for even nucleons and neglected for the odd case (mixed pairing). We found almost similar results for the without and the mixed pairing cases (cases (b) and (c)). However, we noticed only a smooth increasing in $`S_{1n}`$ value for the case (a). In this case, the sudden rise of $`S_{1n}`$ value at Z=50 could not be reproduced (not shown in Fig. 3), which anyway is experimentally observed. On the other hand for the other two cases ((a) and (b)), the characteristic jump at Z=50 is clearly visible (here we have plotted case (c) only in Fig. 3).

To see the other theoretical behaviour we have also displayed the calculated data of HFB Sam01  and the infinite nuclear mass (INM) model Sat01  calculations in Fig. 3. From the figure it is clear that the HFB and INM models are not even able to reproduce the magic jump at Z=50 for the N=82 isotonic series. A further inspection of the figure, makes it clear that the RMF formalism is somewhat able to reproduce the known jump of Z=50, whereas it fails to reproduce the odd-even type of staggering for $`Z=`$ 58, 60, 62, 64, 66, 68, 70, $`N=82`$ which are experimentally observed. However this model produces some spurious tendency like a sudden jump at $`Z=56`$ for the N=82 nucleus, which is experimentally ruled out and some odd-even type of staggering in the heavier region of the N=82 isotonic series.

For new magicities at $`N=`$ 6, 14, 16, 34 etc, all kind of new ideas are being proposed Thi00 ; Dlo03 ; Tho03 . We also feel that the new magicities at $`Z=58`$, 60, 62, 64, 66, 68, 70 are also indicative of new physics. From our present investigation, it may be seen that the HFB and INM models are missing some important physics to incorporate the experimental strggering for the considered region. On the other hand, the RMF explains the characteristic jump at Z=50, but fails to reproduce other odd-even effects. The reproduction of odd-even trends for heavier mass nuclei of the N=82 isotonic series in the frame work of RMF model, gives some hints that the progress of relativistic mean field formalism may be in the proper direction. However, it is still missing some important ingredients. As it has been argued by several authors, the inclusion of self-coupling of scalar fields simulate the effect of three-body forces. But still the absence of many-body correlations is very much there in this theory. A possible improvement of the RMF theory may be to include the higher order couplings as it is suggested in Ref. aru03 . The other possible feature, which is not taken either in the RMF or in the HFB or the INM models is the possibility of $`A=3,4`$ clustering abbas01 . Once these two effects are taken into account, we hope that the theories may be compartible with the experimental data. Work in this direction is in progress aru04 .


text:
# Progress Calculating Decay Constants with NRQCD and AsqTad Actions

## 1 INTRODUCTION

The “AsqTad” improved staggered quark action has made feasible the simulation of QCD with 3 flavors of sea quarks, with 2 of the flavors varying in mass from $`m_s`$ to below $`m_s/5`$. Unquenched simulation with this action at light sea quark masses produces agreement with experiment for several quantities: the $`\mathrm{{\rm Y}}`$ spectrum, $`B`$ masses, and $`\pi `$ and $`K`$ decay constants. Using a single set of input parameters, these quantities could not previously reproduce experiment .

Having removed this discrepancy and constructed actions with good scaling properties, the uncertainties arising from chiral extrapolations can be studied more accurately.

In recent work  we proposed and tested the use of improved staggered quarks as the light quark in heavy-light mesons. Since the heavy quark does not have the doubling problem, taste-breaking effects present in light staggered hadrons are suppressed in heavy-light mesons. Consequently the same operators used in Wilson fermion simulations can be used here, employing the identity between naive and staggered quark propagators.

This work utilizes a subset of the public MILC configurations, the parameters of which we summarize in Table 1; further details appear in . The correct experimental kaon mass is obtained by tuning the valence strange quark mass to $`au_0m_q=0.040(1)`$ on the $`au_0m_{ud}^{\mathrm{sea}}=0.01`$ lattice. For clarity, we will quote quark masses in units of the mass, $`m_s`$, corresponding to the physical strange mass.

The NRQCD (improved through $`1/M_0^2`$) and improved staggered actions are exactly as in  (see references therein). The operator matching has been carried out through $`𝒪(1/M_0)`$ at 1-loop order in perturbation theory .

## 2 $`𝒇_{𝑩_𝒔}`$ AND $`𝒇_{𝑫_𝒔}`$

The $`B_s`$ decay constant is the simplest for us to compute since no extrapolations in valence quark mass are necessary and dynamical quark mass dependence is found to be small (see discussion below). The strange and bottom quark masses are fixed by tuning the bare masses to the physical $`K`$ and $`\mathrm{{\rm Y}}`$ masses. On the lattice with $`m_{ud}^{\mathrm{sea}}m_s/4`$ we find

$$f_{B_s}=260\pm 7\pm 26\pm 8\pm 5\mathrm{MeV}.$$
(1)
The first uncertainty is the statistical errors in the matrix elements and lattice spacing. The dominant uncertainty is the estimate of $`𝒪(\alpha _s^2)`$ effects neglected in the 1-loop matching calculation. The last two uncertainties estimate the errors due to higher orders in the heavy quark expansion and discretization errors.

Figure 1 shows the mass dependence of the combination $`f_{H_s}\sqrt{m_{H_s}}`$. We would like to extrapolate to the charm region, where we are unable to calculate using NRQCD at this lattice spacing. Fits to a power series

$$f_{H_s}\sqrt{m_{H_s}}=\mathrm{\Phi }^{\mathrm{stat}}\left(1+\underset{n=1}{\overset{N}{}}\frac{C_n}{m_{H_s}^n}\right)$$
(2)
give acceptable $`\chi ^2`$’s for $`N2`$ – a linear fit gives an unacceptably large $`\chi ^2`$/DoF = 3. The extrapolated value for $`f_{D_s}`$ is 290 MeV. The largest uncertainty is again $`𝒪(\alpha _s^2)10\%`$ perturbative corrections. Other uncertainties are still being estimated.

Within statistical errors, there is no sea quark mass dependence apparent in Fig. 1. In Fig. 2 we plot the same quantity for 2 values of heavy quark mass and with 2 definitions of the lattice spacing. Note from Table 1 that with $`m_{ud}^{\mathrm{sea}}(3/4)m_s`$ we see the reappearance of a scale ambiguity. With $`m_{ud}^{\mathrm{sea}}m_s/2`$ the 2 lattice spacings differ by $`1.5\sigma `$. This effect apparently masks any sea quark mass dependence, as can be seen in Fig. 2, consequently we conclude that a chiral extrapolation in $`m_{ud}^{\mathrm{sea}}`$ will be an effect smaller than the other quoted errors. We emphasize that within statistical errors of 1.3% no scale ambiguity exists for $`m_{ud}^{\mathrm{sea}}m_s/4`$ which is where our result (1) is taken.

## 3 CHIRAL BEHAVIOR

The main benefit of using staggered fermions is being able to simulate closer to the chiral limit. In order to make maximal use out of the gauge field configurations, several values of valence quark mass $`m_q`$ are used. So far we have accumulated data with $`m_{ud}^{\mathrm{sea}}m_s/4`$ and $`m_qm_s/8`$, compared to $`m_q0.7m_s`$ which is the state-of-the-art using Wilson-like fermions .

In Fig. 3 we plot $`f_{B_s}/f_{B_q}`$ (times $`\sqrt{m_{B_s}/m_{B_q}}`$ or $`1.01`$) against $`m_q/m_s`$. Crosses are unquenched, except that the dynamical strange quark mass is slightly heavier ($`m^{\mathrm{sea}}=(5/4)m_s`$) than the valence strange quark mass ($`m^{\mathrm{val}}=m_s`$), and squares have light sea quark mass fixed to $`m_s/4`$. A partially quenched analysis will utilize the correlations between data points computed on the same configurations.

Bećirević et al. recently noticed that the coefficient of the chiral logs in the double ratio

$$R\frac{f_{B_s}\sqrt{m_{B_s}}}{f_B\sqrt{m_B}}/\frac{f_K}{f_\pi }$$
(3)
is numerically smaller than in either ratio individually . Combining our results with the MILC collaboration results  for $`f_K/f_\pi `$ (which is 1.22 experimentally) yields Fig. 4. Extrapolating $`R`$ to $`r=0`$, a range of 1.0 – 1.1 would correspond to $`\xi `$ between 1.22 and 1.34. ($`\sqrt{B_{B_s}/B_{B_d}}=1.01(3)`$ .) Much work remains to be done before we have a trustworthy and precise final result, but these simulations with masses below $`m_s/2`$ should cast new light on the chiral extrapolation of this important quantity.

## ACKNOWLEDGMENTS

We are grateful for the availability of the MILC gauge field configurations. Our simulations were run at NERSC. This work was supported by the DOE and PPARC.


text:
# References

Optimization Strategies in Complex Systems

L. Bussolari, P. Contucci, C. Giardinà Dipartimento di Matematica, Università di Bologna, Piazza di Porta S. Donato 5, 40127 Bologna, {bussolar, contucci, giardina}@dm.unibo.it C. Giberti Dipartimento di Informatica e Comunicazione, Università dell’Insubria, Via Mazzini 5, 21100 Varese claudio.giberti@uninsubria.it F. Unguendoli, C. Vernia Dipartimento di Matematica Pura ed Applicata, Università di Modena e Reggio Emilia, Via Campi 213/b, 41100 Modena {unguendoli, vernia}@unimore.it

Abstract We consider a class of combinatorial optimization problems that emerge in a variety of domains among which: condensed matter physics, theory of financial risks, error correcting codes in information transmissions, molecular and protein conformation, image restoration. We show the performances of two algorithms, the“greedy” (quick decrease along the gradient) and the“reluctant” (slow decrease close to the level curves) as well as those of a“stochastic convex interpolation”of the two. Concepts like the average relaxation time and the wideness of the attraction basin are analyzed and their system size dependence illustrated.

A decision-making problem is often formulated as minimization of a function of several variables (the cost function) possibly subjected to some constraints. Consider, for example, the following combinatorial optimization problem 111from the Millennium Prize Problems list at Clay Mathematics Institute, http://www.claymath.org : “Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice”. It is clear that one may check “easely” (in a polynomial time) if a proposed solution is correct; nevertheless the extensive search of the solution is extremely hard because the total number of possible accommodations is as large as $`\left(\genfrac{}{}{0pt}{}{400}{100}\right)`$, a number which is larger of the estimated number of atoms in the universe! This is an example of a so-called NP complete problem, i.e. a problem for which no polynomial algorithm is known to find the solution. There are many instances of NP complete problems coming for very different subjects. In the classical formulation of the theory of financial risk with short-selling included, the choice of the optimal portfolio from the historical prices correlations is casted in the selection of an investment strategy among a huge number of possibilities . Another example comes from the theory of error-correcting codes, where one faces the problem of reconstructing an original sequence of bits which has been corrupted during transmission . More familiar to physicists is the NP complete problem coming from the realm of condensed matter. Here particles carrying a magnetic moment (spin) is modeled by dichotomic variables $`\sigma _i=\pm 1`$. The interaction between different atoms is described by a function $`H(J,\sigma )`$ (the Hamiltonian or energy), which plays the role of the cost function, and which depends also on some randomness through the set of variables $`J`$. The optimization problem amounts to find, for a given instance of the problem specified by the variables $`J`$, the ground state configuration, i.e. the spin configuration which minimize energy.

It is our aim in this report to show how new concepts and techniques from Statistical Mechanics can be helpful in finding approximated optimal solutions to complex NP complete problems .

We perform a statistical analysis of energy-decreasing algorithms on a specific mean-field spin model with complex energy landscape. We specifically address the following question: in the search of low energy configurations is it convenient (and in which sense) a quick decrease along the gradient (greedy dynamics) or a slow decrease close to the level curves (reluctant dynamics)? Average time and wideness of the attraction basins are introduced for each algorithm together with a convex interpolation among the two and experimental results are presented for different system sizes. We found that while the reluctant algorithm performs better for a fixed number of trials, the two algorithms become basically equivalent for a given elapsed time due to the fact that the greedy has a shorter relaxation time which scales linearly with the system size compared to a quadratic dependence for the reluctant. A final test is also performed in a stochastic convex combination of the two algorithms: at each step the motion is greedy with probability $`P`$ and reluctant with probability $`1P`$. It is found that for large $`N`$ and for fixed running times a substantial improvement is obtained with a $`P=0.1`$

Model and Algorithms

We consider the paradigmatic model of complex spin systems, the so-called Sherrington-Kirkpatrick model . This is defined by the following Hamiltonian

$$H(J,\sigma )=\frac{1}{2}\underset{i,j=1}{\overset{N}{}}J_{ij}\sigma _i\sigma _j$$
(1)
where $`\sigma _i=\pm 1`$ for $`i=1,\mathrm{},N`$ are Ising spin variables and $`J_{ij}`$ is an $`N\times N`$ symmetric matrix which specifies local interaction between them. The $`J_{ij}`$ are independent identically distributed symmetric gaussian random variables $`(J_{ij}=J_{ji},J_{ii}=0)`$ with zero mean and variance $`1/N`$, in order to have a sensible thermodynamic limit. Since this is a disordered model one is interested in the quenched average ground state energy. For each $`N`$ this is defined as:

$$e_N^{GS}=Av\left\{\frac{1}{N}\underset{\sigma }{inf}H_N(J,\sigma )\right\}$$
(2)
where we denoted by $`Av\{\}`$ the average over the couplings. Analytical knowledge of this quantity is available in the thermodynamical limit $`N\mathrm{}`$ using Parisi Ansatz for replica symmetry breaking theory: $`e_{\mathrm{}}^{GS}=0.7633`$ , a result which has been confirmed by numerical simulations using finite size scaling, yielding $`e_{\mathrm{}}^{GS}=0.76\pm .01`$ .

The greedy and reluctant dynamics work as follows. The initial spin configuration at time $`t=0`$ is chosen at random with uniform probability. Then, at each step $`t`$, the whole spectrum of energy change obtained by flipping one of the spin is calculated

$$\mathrm{\Delta }E_i=\sigma _i(t)\underset{ji}{}J_{ij}\sigma _j(t)$$
(3)
The configuration is then updated at time $`t+1`$ by flipping the spin which corresponds to the largest (greedy) or smallest (reluctant) energy decrease. Both the dynamics follow an energy descent trajectory till they arrive to a $`1`$-spin-flip stable configuration, i.e. a configuration whose energy can not be decreased by a single spin-flip. These represent local minima in energy landscape at zero temperature and the ground state is one of them. Moreover, we investigate the efficiency of a stochastic convex combination of the two algorithms: with probability $`0P1`$ we perform a greedy move and with probability $`1P`$ the corresponding reluctant move. The deterministic dynamics are obtained at $`P=1`$ (greedy) and $`P=0`$ (reluctant), respectively. Intermediate values of $`P`$ are stochastic dynamics where the greedy and reluctant moves are weighted by the probability $`P`$.

Computational Resources and Results

Our simulations used about 5000 hours of CPU time on the machine IBM SP3. Parallelization has been highly efficient due to the fact that we run different disorder realization and/or different initial conditions on each processor, simply averaging the results at the end of the elaboration.

First of all, we analyzed the average time $`\tau `$ of the dynamics for different values of $`P`$, which is easily accessible to measurements and has good self-averaging properties. This is defined as

$$\tau =\frac{1}{M}\underset{i=1}{\overset{M}{}}t_i$$
(4)
where $`t_i`$, $`i=1,\mathrm{},M`$ is the time of each realization of the dynamics, measured by counting the number of “spin flip” necessary to reach a metastable configuration.. The number of trials $`M`$ is an increasing function of the system size. For the largest sizes $`(N=250,300)`$ we used up to $`10^9`$ initial configurations. Results are shown in Fig. (1), together with the best numerical fits. Note the progressive increase of the slope in log-log scale from an almost linear law for greedy (bottom) $`\tau (N)N^{1.04}`$ to an almost quadratic law for reluctant (top) $`\tau (N)N^{2.07}`$. However, an interesting result is that for $`P=0.1`$ we have still have $`\tau (N)N^{1.26}`$, i.e. a stochastic algorithm which makes on average one greedy move (and nine reluctant moves) out of ten has a much smaller average time than the deterministic reluctant algorithm $`P=0`$. We notice that the exponents for greedy (resp. reluctant) algorithm are very close to the integers 1 (resp. 2) with an observed slow crossover between the two for intermediate $`P`$. It would be interesting to have a theoretical understanding of this phenomenon even if only at a heuristic level. We plan to return over this problem in a future work.

Next, we measured the lowest energy value found for a fixed number of initial conditions for different probabilities $`P`$. One has to choose a protocol to fix the number of initial conditions. Obviously, the larger the system size the bigger must be the number of trials. We tried different choices obtaining similar results. For the sake of space we show in Fig. (2) the results of the run where we choose $`N`$ initial conditions for a system of size $`N`$. The data have been averaged on $`1000`$ disorder realizations. We see that the smaller is the probability of making greedy moves, the lower is the energy found. The best result is obtained for $`P=0`$, which corresponds to deterministic reluctant dynamics. This means that, ignoring the total amount of time and imposing constraint only on the number of initial conditions, reluctant dynamic is the most efficient in reaching low energy states, i.e. it has a larger basin of attraction.

Finally, we compared results of different probabilities in the case one considers a fixed elapsed time. As an example, we present results for an elapsed time of $`100`$ hours of CPU on a IBM SP3 for $`N`$ in the range $`[50,300]`$. We considered again $`1000`$ disorder realizations and assigned the same time length to each sample ($`6`$ minutes). Obviously, in this way reluctant dynamics starts from a smaller number of initial conditions than greedy, because its relaxation time is longer. In Fig. (3) we plot the values of the lowest energy state as a function of $`N`$. We can see from the data that, for a fixed elapsed time, greedy dynamics ($`P=1`$) find lower energy states than reluctant ($`P=0`$). Moreover, we observe that the best result is obtained for $`P=0.1`$. Thus, we suggest that the more power full strategy to find low energy state using greedy and reluctant dynamic is a combination of them, where most of the steps the move is reluctant and on a small fraction of steps (say $`0.1`$) the move is greedy.

The results of the present work is extensively presented in ref . Improvements of the greedy and reluctant algorithms is presently under study (on IBM SP4), by permitting also increase in energy with exponential decrease in time, in the same spirit of the well-known Simulated Annealing strategies .

Acknowledgments We thank the Cineca staff for technical support and in particular Dr. Erbacci and Dr. Calonaci for kind assistance. We thank Prof. S. Graffi and Prof. I. Galligani for all the encouragement and the support of Cineca grant.